Paquetage id3_template

Contient l'algorithme ID3. Plus de détails...

Classes

class Noeud

Represente un noeud dans l'arbre de décision. Plus de détails...

Fonctions

def initID3

Initialise le module ID3.

def classifie

Permet de classer un set d'exemples à l'aide de l'arbre de décision.

def construitArbreDecision

Construit l'arbre de decision pour les exemples de tousLesExemples et le sauvegarde dans la variable globale classification.

def construitArbreDecisionAux

Fonction auxiliaire de construction de l'arbre de décision.

def meilleurAttribut

Retourne le meilleur attribut à choisir dans la liste disponible.

def entropie

Retourne l'entropie totale pour l'attribut passé en paramètre.

def H_C_Aj

Retourne l'entropie conditionnelle de l'attribut passé en paramètre pour une certaine valeur.

def P_Ci_Aj

Calcule la probabilité P(Ci|Aj) = P(class-value|attribute=value).

def P_Aj

Retourne la probabilité P_Aj.

def retourneValeurAttribut

Retourne la valeur de l'attribut donné en paramètre pour l'exemple donné.

def retourneClasse

Retourne la classe de l'exemple passé en paramètre.

def partition

Partitionne les exemples selon les valeur de l'attribut.

def memeClasse

Indique si tous les exemples passés en paramètre appartiennent à la même classe.

def retourneValeursPossiblesAttribut

Retourne la liste de toutes les valeurs pour un certain attribut.

def retourneClassesPossibles

Retourne la liste de toutes les classes possibles de la liste des exemples.

def nombreOccurences

Retourne le nombre d'exemples dont l'attribut vaut une certaine valeur.

def nombreOccurencesCond

Retourne le nombre d'exemples respectant une condition particulière.

def retourneValeursAttribut

Retourne la liste de toutes les valeurs possibles de l'attribut d'index attribut.

def construitListeAttributs

Retourne la liste des index des attributs, i.e.

def retourneNomAttribut

Retourne le nom de l'attribut d'index attribut.

def retourneIndiceMinimum

Retourne l'index de la plus petite valeur de la liste liste.

Variables

list tousLesExemples = []

La liste des exemples.

list attributsEtValeurs = []

La liste des attributs.

list classification = []

L'arbre de decision trouvé.

Description détaillée

Contient l'algorithme ID3.

Documentation des fonctions

def id3_template.classifie ( n = classification )

Permet de classer un set d'exemples à l'aide de l'arbre de décision.

Cette fonction s'appuye sur l'arbre de décision construit par la fonction construitArbreDecision(). Pour classifier les exemples, on part depuis le noeud n et on descend recursivement dans les sous-noeuds.

Paramètres:

[in] n le noeud d'où part la classification

Définition à la ligne 229 du fichier id3_template.py.

def id3_template.construitArbreDecision ( )

Construit l'arbre de decision pour les exemples de tousLesExemples et le sauvegarde dans la variable globale classification.

Cette fonction s'appuye sur construitArbreDecisionAux pour construire l'arbre de décision à partir des exemples donnés.

Définition à la ligne 274 du fichier id3_template.py.

def id3_template.construitArbreDecisionAux	(	exemples,
		attributs
	)

Fonction auxiliaire de construction de l'arbre de décision.

Cette fonction est la fonction qui construit vraiment l'arbre de décision. Elle est appelée depuis construitArbreDecision() pour initialiser la création de l'arbre à partir d'un set d'exemples et une liste d'attributs

Paramètres:

`[in]`	exemples	la liste d'exemples servant à la construction de l'arbre
`[in]`	attributs	la liste des attributs

Renvoie:: une branche de l'arbre de décision

Définition à la ligne 297 du fichier id3_template.py.

def id3_template.construitListeAttributs	(	actuel = `1`,
		dernier = `-1`
	)

Retourne la liste des index des attributs, i.e.

une liste de actuel a dernier-1.

Cette fonction crée une liste d'indices correspondant à chaque élément de la liste attributsEtValeurs.

Paramètres:

`[in]`	actuel	l'indice de l'attribut courant
`[in]`	dernier	l'indice du dernier attribut

Renvoie:: une liste d'indices pour chaque attribut

Définition à la ligne 545 du fichier id3_template.py.

def id3_template.entropie	(	attribut,
		exemples
	)

Retourne l'entropie totale pour l'attribut passé en paramètre.

Cette fonction calcule et retourne l'entropie totale pour l'attribut d'indice attribut, a savoir: H(C|A) = H(C|attribute).

Paramètres:

`[in]`	attribut	l'indice de l'attribut dont on cherche l'entropie
`[in]`	exemples	la liste des exemples sur laquelle on calcule l'entropie

Définition à la ligne 334 du fichier id3_template.py.

def id3_template.H_C_Aj	(	attribut,
		valeur,
		exemples
	)

Retourne l'entropie conditionnelle de l'attribut passé en paramètre pour une certaine valeur.

Cette fonction calcule l'entropie conditionnelle pour l'attribut attribut ayant comme valeur d'attribut valeur, en d'autres termes : H(C|Aj) = H(C|attribute=value).

Paramètres:

`[in]`	attribut	l'indice de l'attribut
`[in]`	valeur	la valeur de l'attribut
`[in]`	exemples	la liste des exemples sur laquelle calculer l'entropie

Définition à la ligne 348 du fichier id3_template.py.

def id3_template.initID3	(	exemples,
		attrsEtValeurs
	)

Initialise le module ID3.

Cette fonction initialise le module ID3 avec les exemples exemples et la description des classes et attributs attrsEtValeurs.

Paramètres:

`[in]`	exemples	les exemples à classifier
`[in]`	attrsEtValeurs	les attributs ainsi que leur valeur

Définition à la ligne 206 du fichier id3_template.py.

def id3_template.meilleurAttribut	(	attributs,
		exemples
	)

Retourne le meilleur attribut à choisir dans la liste disponible.

Cette fonction retourne le meilleur attribut dans la liste des attributs. Pour ce faire, cette fonction retourne l'attribut dont l'entropie est la plus faible.

Paramètres:

`[in]`	attributs	la liste des attributs
`[in]`	exemples	la liste des exemples

Renvoie:: l'attribut ayant la plus faible entropie

Définition à la ligne 315 du fichier id3_template.py.

def id3_template.memeClasse ( exemples )

Indique si tous les exemples passés en paramètre appartiennent à la même classe.

Cette fonction indique si les exemples passés dans la liste exemples appartiennent ou non à la même classe. Elle procède en dénombrant les classes possibles parmi les exemples. Si le nombre est 1, alors cela signifie que les exemples font partie d'une même classe

Paramètres:

[in] exemples la liste des exemples dont on veut savoir s'ils sont de la même classe

Renvoie:: True si tous les exemples sont de la même classe, False sinon

Définition à la ligne 441 du fichier id3_template.py.

def id3_template.nombreOccurences	(	attribut,
		valeur,
		exemples
	)

Retourne le nombre d'exemples dont l'attribut vaut une certaine valeur.

Cette fonction retourne le nombre d'exemples de la liste exemples dont la valeur de l'attribut d'indice attribut vaut valeur.

Paramètres:

`[in]`	attribut	l'indice de l'attribut
`[in]`	valeur	la valeur de l'attribut
`[in]`	exemples	la liste des exemples à parcourir

Renvoie:: le nombre d'exemples de même valeur que valeur

Définition à la ligne 488 du fichier id3_template.py.

def id3_template.nombreOccurencesCond	(	classe,
		attribut,
		valeur,
		exemples
	)

Retourne le nombre d'exemples respectant une condition particulière.

Cette fonction retourne le nombre d'exemples d'exemples appartenant à la classe classe et qui ont valeur comme valeur de l'attribut d'index attribut.

Paramètres:

`[in]`	classe	le nom de classe
`[in]`	attribut	l'indice de l'attribut
`[in]`	valeur	la valeur de l'attribut
`[in]`	exemples	la liste des exemples

Renvoie:: le nombre d'exemples respectant la condition

Définition à la ligne 507 du fichier id3_template.py.

def id3_template.P_Aj	(	attribut,
		valeur,
		exemples
	)

Retourne la probabilité P_Aj.

Cette fonction retourne la probabilité que la valeur de l'attribut d'indice attribut soit valeur. Cette probabilité est tout simplement le nombre d'exemples dont l'attribut attribut a la valeur valeur, divisé par le nombre d'exemples de la liste exemples.

Paramètres:

`[in]`	attribut	l'attribut cherché
`[in]`	valeur	la valeur de l'attribut
`[in]`	exemples	la liste des exemples

Renvoie:: la probabilité P_Aj

Définition à la ligne 377 du fichier id3_template.py.

def id3_template.P_Ci_Aj	(	classe,
		attribut,
		valeur,
		exemples
	)

Calcule la probabilité P(Ci|Aj) = P(class-value|attribute=value).

Cette fonction calcule la probabilite que la valeur de la classe soit classe lorsque attribut vaut valeur, en d'autres termes : P(Ci|Aj) = P(class-value|attribute=value).

Paramètres:

`[in]`	classe	la nom de la classe
`[in]`	attribut	l'indice de l'attribut
`[in]`	valeur	la valeur de l'attribut
`[in]`	exemples	la liste des exemples sur laquelle on calcule la probabilité.

Définition à la ligne 362 du fichier id3_template.py.

def id3_template.partition	(	exemples,
		attribut
	)

Partitionne les exemples selon les valeur de l'attribut.

Retourne une liste dont chaque element est une liste des exemples avec un valeur commune pour attribut. Cette liste contient pour chaque valeur d'attribut vi un liste d'exemples dont la valeur est vi.

Paramètres:

`[in]`	exemples	la liste des exemples à partitionner
`[in]`	attribut	l'attribut pivot qui sert au partitionnement

Renvoie:: un liste de sous-listes d'exemples partitionnés par valeur d'attrib.

Définition à la ligne 426 du fichier id3_template.py.

def id3_template.retourneClasse ( exemple )

Retourne la classe de l'exemple passé en paramètre.

Cette fonction retourne la classe d'un exemple. Cette classe est tout simplement le premier élément de la liste exemple.

Paramètres:

[in] exemple l'exemple dont on cherche la classe

Renvoie:: le nom de la classe à laquelle l'exemple appartient

Définition à la ligne 409 du fichier id3_template.py.

def id3_template.retourneClassesPossibles ( exemples )

Retourne la liste de toutes les classes possibles de la liste des exemples.

Cette fonction parcourt les exemples et cherche toutes les classes que l'on peut extraire à partir de cette liste.

Paramètres:

[in] exemples la liste des exemples à parcourir

Renvoie:: la liste des classes possibles à partir des exemples

Définition à la ligne 474 du fichier id3_template.py.

def id3_template.retourneIndiceMinimum ( liste )

Retourne l'index de la plus petite valeur de la liste liste.

Cette fonction cherche parmi tous les éléments de la liste liste passée en paramètre le plus petit et retourne sa position

Paramètres:

[in] liste la liste dans laquelle l'on doit chercher

Renvoie:: l'indice du plus petit élément de la liste

Définition à la ligne 581 du fichier id3_template.py.

def id3_template.retourneNomAttribut ( attribut )

Retourne le nom de l'attribut d'index attribut.

Cette fonction retourne, dans la liste des attributs et de leur valeur, le nom de l'attribut correspondant à l'indice attribut. Le codage de la liste attributsEtValeurs est le suivant :

 attributEtValeur = [ 'nom_attribut', 'valeur_1', ..., 'valeur_n' ]
 attributsEtValeurs = [ attributEtValeur[0], ...., attributEtValeur[m] ]

Le nom de l'attribut attribut se trouve donc en attributsEtValeurs[attribut][0].

Paramètres:

[in] attribut l'indice de l'attribut dont on cherche le nom

Renvoie:: le nom de l'attribut d'indice attribut

Définition à la ligne 570 du fichier id3_template.py.

def id3_template.retourneValeurAttribut	(	exemple,
		attribut
	)

Retourne la valeur de l'attribut donné en paramètre pour l'exemple donné.

Cette fonction retourne la valeur de l'attribut d'indice attribut dans l'exemple exemple. Un exemple est une liste de la forme:

 exemple = [ 'nom-classe', 'valeur-attribut1', ..., 'valeur-attributn']

Paramètres:

`[in]`	exemple	l'exemple dont on veut la valeur de l'attribut
`[in]`	attribut	l'indice de l'attribut dont on cherche la valeur

Renvoie:: la valeur de l'attribut pour l'exemple passé en paramètre.

Définition à la ligne 398 du fichier id3_template.py.

def id3_template.retourneValeursAttribut ( attribut )

Retourne la liste de toutes les valeurs possibles de l'attribut d'index attribut.

Cette fonction retourne la liste de toutes les valeurs possible pour un attribut donné. Les valeurs d'un attribut sont stockées dans une liste dont le premier élément est le nom de l'attribut. Donc, pour obtenir les valeurs, il suffit de retourner les éléments de 1 à len(attributsEtValeurs[attribut])

Paramètres:

[in] attribut l'indice de l'attribut

Renvoie:: une liste de valeurs correspondant à l'attribut d'indice attribut

Définition à la ligne 532 du fichier id3_template.py.

def id3_template.retourneValeursPossiblesAttribut	(	attribut,
		exemples
	)

Retourne la liste de toutes les valeurs pour un certain attribut.

Cette fonction retourne une liste de toutes les valeurs possibles pour l'attribut d'indice attribut que l'on trouve dans les exemples de la liste exemples.

Paramètres:

`[in]`	attribut	l'indice de l'attribut dont on cherche les valeur
`[in]`	exemples	la liste des exemples dans laquelle on cherche

Renvoie:: une liste contenant toutes les valeurs possibles de l'attribut

Définition à la ligne 458 du fichier id3_template.py.

Documentation des variables

list id3_template.attributsEtValeurs = []

La liste des attributs.

La liste des attributs (dans le meme ordre que celui des exemples) avec leur valeur. Format: attributsEtValeurs ::= [ attribut1 attribut2 ... ] attribut ::= [ nom-attribut valeur-1 .. valeur-m ]

Définition à la ligne 39 du fichier id3_template.py.

list id3_template.classification = []

L'arbre de decision trouvé.

Contient l'arbre de décision

Définition à la ligne 44 du fichier id3_template.py.

list id3_template.tousLesExemples = []

La liste des exemples.

La liste des exemples, selon le format suivant: tousLesExemples ::= [ exemple1 exemple2 ... ] exemple ::= [ classe valeur-attribut-1 ... valeur-attribut-n]

Définition à la ligne 31 du fichier id3_template.py.


Classes
class	Noeud
	Represente un noeud dans l'arbre de décision. Plus de détails...
Fonctions
def	initID3
	Initialise le module ID3.
def	classifie
	Permet de classer un set d'exemples à l'aide de l'arbre de décision.
def	construitArbreDecision
	Construit l'arbre de decision pour les exemples de `tousLesExemples` et le sauvegarde dans la variable globale `classification`.
def	construitArbreDecisionAux
	Fonction auxiliaire de construction de l'arbre de décision.
def	meilleurAttribut
	Retourne le meilleur attribut à choisir dans la liste disponible.
def	entropie
	Retourne l'entropie totale pour l'attribut passé en paramètre.
def	H_C_Aj
	Retourne l'entropie conditionnelle de l'attribut passé en paramètre pour une certaine valeur.
def	P_Ci_Aj
	Calcule la probabilité P(Ci\|Aj) = P(class-value\|attribute=value).
def	P_Aj
	Retourne la probabilité P_Aj.
def	retourneValeurAttribut
	Retourne la valeur de l'attribut donné en paramètre pour l'exemple donné.
def	retourneClasse
	Retourne la classe de l'exemple passé en paramètre.
def	partition
	Partitionne les exemples selon les valeur de l'attribut.
def	memeClasse
	Indique si tous les exemples passés en paramètre appartiennent à la même classe.
def	retourneValeursPossiblesAttribut
	Retourne la liste de toutes les valeurs pour un certain attribut.
def	retourneClassesPossibles
	Retourne la liste de toutes les classes possibles de la liste des exemples.
def	nombreOccurences
	Retourne le nombre d'exemples dont l'attribut vaut une certaine valeur.
def	nombreOccurencesCond
	Retourne le nombre d'exemples respectant une condition particulière.
def	retourneValeursAttribut
	Retourne la liste de toutes les valeurs possibles de l'attribut d'index `attribut`.
def	construitListeAttributs
	Retourne la liste des index des attributs, i.e.
def	retourneNomAttribut
	Retourne le nom de l'attribut d'index `attribut`.
def	retourneIndiceMinimum
	Retourne l'index de la plus petite valeur de la liste `liste`.
Variables
list	tousLesExemples = []
	La liste des exemples.
list	attributsEtValeurs = []
	La liste des attributs.
list	classification = []
	L'arbre de decision trouvé.