# -*- coding: cp1252 -*- ################################################################################# print "Chargement du module ID3" ################################################################################# import math import copy import sys ## La liste des exemples, selon le format suivant: ## exemples ::= [ { exemple } ] ## exemple ::= [ classe valeur-attribut-1 ... valeur-attribut-n] allExamples = [] ## La liste des attributs (dans le meme ordre que celui des exemples) ## avec leurs valeurs. Format: ## attributs ::= [ classes { attribut } ] ## classes ::= [ nom-attribut classe-1 .. classe-m ] ## attribut ::= [ nom-attribut valeur-1 .. valeur-n ] attributesAndValues = [] ## L'arbre de decision trouve: classification = [] ###=================================================================== ### INITIALISATION et CONSULTATION DE L'ARBRE DE DECISION ###=================================================================== ## Initialise le module ID3 avec les exemples <examples> et la ## description des classes et attributs <attributes-and-values>. def initID3(examples, theAttributesAndValues): global allExamples global attributesAndValues global classification allExamples = examples attributesAndValues = theAttributesAndValues classification = [] print("DB: initID3 -> attributesAndValues: %s" % (attributesAndValues)) ## Permet de classer un exemple a l'aide de l'arbre de decision ## classification, calculé par buildDecisionTree. def classify(n=classification): if n == []: ## On ne sait pas classer cet exemple print("L'exemple ne peut être classé") elif n.terminalNode(): ## L'exemple peut être classé: print(">>> L'exemple est de la classe %s" % (n.getClass())) else: ## L'exemple ne peut encore être classé, il faut des informations ## complémentaires: splitAttribute = n.attribute validValues = getAllAttributeValues(splitAttribute) while True: print("> Valeur de l'attribut %s? " % (attributeName(splitAttribute))) value = sys.stdin.readline().strip() if value in validValues: return classify(n.children[validValues.index(value)]) print("## Valeur %s inconnue pour l'attribut %s" % (value, attributeName(splitAttribute))) ###=================================================================== ### CALCUL DE L'ARBRE DE DECISION ###=================================================================== class Node: ## Constructeur ## @param attribute L'attribut de partitionnement du noeud. ## @param examples Les exemples du noeud (s'il est terminal). ## @param children Les noeuds fils (s'il n'est pas terminal). def __init__(self, attribute, examples, children): self.attribute = attribute self.examples = examples self.children = children def __str__(self): out = ("\n********** DECISION TREE **********\n") return out + self.printNodeAux(" ") def printNodeAux(self, space): if self.terminalNode(): ## Noeud terminal: out = ("%s Noeud terminal: classe %s\n" % (space, self.getClass())) for ex in self.examples: out = out + ("%s %s\n" % (space, ex)) else: ## Noeud non terminal: out = ("%s Partitionnement selon %s\n" % (space, attributeName(self.attribute))) values = getAllAttributeValues(self.attribute) successors = self.children newSpace = space + " " while len(successors) > 0: out = out + ("%s Valeur %s\n" % (space, values[0])) out = out + successors[0].printNodeAux(newSpace) values = values[1:] successors = successors[1:] return out ## Retourne la classe correspondant au noeud <n> s'il est terminal, ## [] si c'est un noeud intermediaire def getClass(self): if self.terminalNode(): return getClassValue(self.examples[0]) ## Retourne True ssi self est un noeud terminal, càd s'il n'a pas ## d'attribut de partitionnement def terminalNode(self): return (self.attribute == []) ## Construit l'arbre de decision pour les exemples de allExamples et ## la sauvegarde dans la variable globale classification. def buildDecisionTree(): global allExamples global classification classification = buildDecisionTreeAux(allExamples, buildAttributesList()) #print(classification) def buildDecisionTreeAux(examples, attributes): if not examples: return [] if oneClass(examples): return Node([], examples, []) a = bestAttribute(attributes, examples) part = partition(examples, a) fils = [] for p in part: fils.append(buildDecisionTreeAux(p, list(set(attributes).difference(set([a]))))) return Node(a, [], fils) ##=================================================================== ## CALCUL DE L'ENTROPIE ##=================================================================== ## Retourne le meilleur attribut, càd celui avec l'entropie ## (càd l'incertitude) la plus faible. def bestAttribute(attributes, examples): print("DB: bestAttribute -> attributes: %s" % (attributes)) return attributes[getIndexOfMinimum(map(lambda attribute : entropy(attribute, examples), attributes))] ## Retourne l'entropie totale pour <attribute>, a savoir: ## H(C|A) = H(C|attribute). def entropy(attribute, examples): s = 0.0 for v in getAllAttributeValues(attribute): s = s + P_Aj(attribute, v, examples) * H_C_Aj(attribute, v, examples) return s ## Retourne l'entropie conditionnelle de <attribute> avec pour ## valeur <value>, en d'autres termes: ## H(C|Aj) = H(C|attribute=value). def H_C_Aj(attribute, value, examples): s = 0.0 for c in getPossibleClassValues(examples): t = P_Ci_Aj(c, attribute, value, examples) if t != 0: s = s + t * math.log(t, 2) return -s def calculateProb(classValue,attribute, value, examples): prob = P_Ci_Aj(classValue, attribute, value, examples) #print("DB: calculateProb -> prob: %s" % (prob)) if prob == 0: return 0 else: return prob * math.log(prob,2) ## Calcule la probabilite que la valeur de la classe est ## <class-value> lorsque <attribut> vaut <value>, en d'autres ## termes: P(Ci|Aj) = P(class-value|attribute=value). def P_Ci_Aj(classValue, attribute, value, examples): ct = 0.0 for e in examples: if getClassValue(e) == classValue: if getAttributeValue(e, attribute) == value: ct = ct+1 pAB = ct/len(examples) pB = P_Aj(attribute, value, examples) if pB > 0: return pAB/pB else: return 0 ## Retourne la probabilite que <attribut> vaut <value>. def P_Aj(attribute, value, examples): return countOccurences(attribute, value, examples)/len(examples) ##=================================================================== ## EXEMPLES ##=================================================================== ## Retourne la valeur de l'attribut d'index <attribute> pour ## <example>. def getAttributeValue(example, attribute): return example[attribute] ## Retourne la classe de <example>. def getClassValue(example): return example[0] ##=================================================================== ## OPERATIONS SUR UNE LISTE D'EXEMPLES ##=================================================================== ## Partitionne les <examples> selon la valeur de <attribute>. ## Retourne une liste tq chaque element est une liste des exemples ## avec un valeur commune pour <attribute>. def partition(examples, attribute): r = [] for v in getAllAttributeValues(attribute): r.append(findAll(examples, lambda e: (getAttributeValue(e, attribute) == v))) return r ## Retourne True ssi tous les exemples de <examples> font partie de la ## meme classe. def oneClass(examples): res = len(getPossibleClassValues(examples)) == 1 print("DB: --------------------- oneClass -> getPossibleClassValues(examples) %s" % (getPossibleClassValues(examples))) print("DB: --------------------- oneClass -> res %s" % (res)) return res ## Retourne la liste de toutes les valeurs pour l'attribut d'index ## <attribute> que l'on trouve dans les exemples de <examples>. def getPossibleAttributeValues(attribute, examples): res = [] for ex in examples: value = getAttributeValue(ex,attribute) if not value in res: res = [value] + res return res ## Retourne la liste de toutes les classes que l'on trouve dans ## <examples>. def getPossibleClassValues(examples): res= getPossibleAttributeValues(0,examples) #print("DB: getPossibleClassValues -> res: %s" % (res)) return res ## Retourne le nombre d'exemples de <examples> dont l'attribut ## d'index <attribute> vaut <value>. def countOccurences(attribute, value, examples): res = 0 for ex in examples: if getAttributeValue(ex,attribute) == value: res = res + 1 # if res <> 0: # print("DB: countOccurences -> res: DIFFERENT FROM ZERO!!!!!!!!!! %s" % (res)) return res ## Retourne le nombre d'exemples de <examples> appartenant a la ## classe <class-value> et qui ont <value> comme valeur de ## l'attribut d'index <attribute>. def countOccurencesIf(classValue, attribute, value, examples): res = 0 for ex in examples: if (getClassValue(ex) == classValue) and (getAttributeValue(ex,attribute) == value): res = res + 1 return res ##=================================================================== ## UTILITAIRES ##=================================================================== ## Retourne la liste de toutes les valeurs possibles de l'attribut ## d'index <attribute>. def getAllAttributeValues(attribute): global attributesAndValues return attributesAndValues[attribute][1:] ## ATTENTION!!!!!!!!!!!!!!!!!!!!!!! ## VERIFIER QUE LES INDEXS SONT CORRECTS ## Retourne la liste des index des attributs, i.e. une liste de 1 a ## last-1. def buildAttributesList(current=1,last=-1): if last == -1: last = len(attributesAndValues) if current < last: return [current] + buildAttributesList(current + 1, last) else: return [] ## Retourne le nom de l'attribut d'index <attribute>. def attributeName(attribute): global attributesAndValues return attributesAndValues[attribute][0] ## Retourne l'index de la plus petite valeur de la liste <l>. def getIndexOfMinimum(l): print("DB: getIndexOfMinimum -> l: %s" % (l)) return l.index(min(l)) ## Retourne la liste de tous les elements de la liste <l> qui ## satisfont <test>. def findAll(l, test): res = [] for item in l: if test(item): res = [item] + res return res ## TESTING ----------------------------------------- ## Construction d'un arbre de decision (ID3). ## Exemple: estimation du profit d'une entreprise informatique. def test1(): initID3([['down', 'old', 'no', 'software'], ['down','midlife','yes','software'], ['up', 'midlife','no', 'hardware'], ['down','old', 'no', 'hardware'], ['up', 'new', 'no', 'hardware'], ['up', 'new', 'no', 'software'], ['up', 'midlife','no', 'software'], ['up', 'new', 'yes','software'], ['down','midlife','yes','hardware'], ['down','old', 'yes','software']], [['profit', 'down','up'], ['age', 'old', 'midlife', 'new'], ['competition', 'no', 'yes'], ['type', 'software', 'hardware']]) buildDecisionTree() ## Construction d'un arbre de decision (ID3). ## Exemple: maladies chez l'enfant def test2(): initID3([['angine-erythemateuse','elevee','gonflees', 'oui','oui','non','non','non','normale','normales', 'normaux'], ['angine-pultacee', 'elevee','point-blancs','oui','oui','non','non','non','normale','normales', 'normaux'], ['angine-diphterique', 'legere','enduit-blanc','oui','oui','non','non','non','normale','normales', 'normaux'], ['appendicite', 'legere','normales', 'non','non','oui','non','non','normale','normales', 'normaux'], ['bronchite', 'legere','normales', 'oui','non','non','oui','oui','gene', 'normales', 'normaux'], ['coqueluche', 'legere','normales', 'non','oui','non','oui','oui','gene', 'normales', 'normaux'], ['pneumonie', 'elevee','normales', 'non','non','non','oui','non','rapide', 'rouges', 'normaux'], ['rougeole', 'legere','normales', 'non','oui','non','oui','oui','normale','normales', 'larmoyants'], ['rougeole', 'legere','normales', 'non','oui','non','oui','oui','normale','taches-rouges','larmoyants'], ['rubeole', 'legere','normales', 'oui','non','non','non','non','normale','taches-rouges','normaux'], ['rubeole', 'non', 'normales', 'oui','non','non','non','non','normale','taches-rouges','normaux'], ['rubeole', 'non', 'normales', 'oui','non','non','non','non','normale','normales', 'normaux']], [['maladies','angine-erythemateuse','angine-pultacee','angine-diphterique','appendicite','bronchite','coqueluche','pneumonie','rougeole','rubeole'], ['fievre','non','legere','elevee'], ['amygdales','normales','gonflees', 'points-blancs', 'enduit-blanc'], ['ganglions','non','oui'], ['gene-a-avaler','non','oui'], ['mal-au-ventre','non','oui'], ['toux','non','oui'], ['rhume','non','oui'], ['respiration','normale','gene','rapide'], ['joues','normales','rouges','taches-rouges'], ['yeux','normaux','larmoyants']]) buildDecisionTree() if __name__ == '__main__': #test1() test2() #execfile('invest.py') classify(classification)