ID3

Durée estimée : 2 heures.

Objectifs de la série

  • Quel est l’objectif d’ID3.
  • Qu’est-ce que l’entropie dans le cadre d’ID3.
  • Quelles sont les limites inhérentes à tout arbre de décision.

Fichiers

Les arbres de décision

Si vous voulez investir dans une compagnie informatique et que vous demandez conseil à un expert financier, celui-ci vous posera toute une série de questions concernant l’entreprise, comme par exemple la concurrence à laquelle elle est soumise, son âge etc... avant de vous répondre (en admettant qu’il ne connaisse pas déjà l’entreprise). En supposant que vous possédez de nombreux exemples de profils d’entreprises avec la conclusion de l’expert, vous avez à disposition une partie de son expertise qu’il serait intéressant de pouvoir réutiliser sans avoir recours à cet expert lorsque vous voulez analyser de nouvelles entreprises.

Un arbre de décision est une structure qui est souvent utilisée pour représenter des connaissances. Il permet de remplacer un expert humain lorsqu’une caractéristique sur un objet, appelée sa classe par la suite, est désirée. C’est un arbre qui modélise le cheminement intellectuel de l’expert, où :

  • Chaque noeud intermédiaire correspond à une question sur une propriété de l’objet. Nous appellerons une telle propriété un attribut.
  • Chaque lien correspond à une valeur de l’attribut.
  • Chaque noeud terminal correspond à une collection d’objets de même classe, et donc à une classe. Il peut y avoir plusieurs noeuds terminaux différents de même classe.

En parcourant cet arbre (en répondant aux questions des noeuds intermédiaires et en suivant les liens correspondants), vous parvenez à un noeud terminal qui vous renseigne sur la classe de l’objet.

ID3 est un algorithme de construction d’un arbre de décision qui minimise le nombre de questions à poser. Il construit l’arbre de décision à partir d’un ensemble d’exemples, c’est à dire d’objets décrits par leurs attributs et leur classe. Son algorithme est le suivant:

 ID3(exemples, attributs)
 1. IF exemples est vide THEN
 2.   /* Il n'y a pas d'objet dans cette `sous-classification': noeud terminal 'spécial' */
 3.   RETOURNER NULL
 4. ELSE IF tous les objets de exemples font partie de la même classe THEN
 5.   /* Noeud terminal */
 6.   RETOURNER un noeud terminal contenant tous les objets de exemples
 7. ELSE
 8.   /* Noeud intermédiaire */
 9.   A <- attribut de attributs minimisant l'entropie de la classification
10.   vals <- liste des valeurs possibles pour A
11.   FOR i IN vals DO
12.     /* Partitionnement: */
13.     part[i] <- objets de exemples qui ont i comme valeur pour A
14.     /* Calcul des noeuds fils: */
15.     fils[i] <- ID3(part[i], attributs - A)
16.   END FOR
17.   RETOURNER un noeud avec fils comme successeurs
18. END IF
END ID3

Note

Bien évidemment, la qualité de l’arbre de décision construit par ID3 dépend des exemples : plus ils sont variés et nombreux, plus la classification de nouveaux objets sera fiable.

Voyons les structures de données dont vous aurez besoin.

Les examples d’apprentissage

Un exemple d’apprentissage (un objet avec sa classe) est une liste de la forme:

exemple ::= [val-classe, {attribut-1: val-attribut-1, ... , attribut-k: val-attribut-k}]

où k est le nombre d’attributs. Chaque exemple doit être donné avec une valeur pour chaque attribut. Les exemples pour l’apprentissage sont contenus dans les fichiers maladie.py et profit.py.

Les attributs et les classes

On utilise aussi:

  • Un dictionnaire qui fait correspondre chaque attribut à son domaine de valeurs:
attributs ::= {attribut-1: [val-attribut-1-1, …], …, attribut-k: [val-attribut-1-k, …]}
  • Une liste contenant toutes les classes des exemples d’apprentissage:
classes ::= [val-classe-1, ...]

La classe Noeud

Un noeud de l’arbre de décision est modélisé par la classe Noeud, avec trois champs :

  • attribut: l’attribut de partitionnement d’un noeud. Ce champ vaut None pour un noeud terminal.
  • exemples: la liste des exemples qui tombent dans la sous-classification du noeud.
  • enfants: la liste des noeuds fils pour un noeud. Cette liste est ordonnée selon les valeur de l’attribut de partitionnement (champ attribut): à la i-ième valeur de l’attribut correspond le i-ième fils. Ce champ vaut None pour un noeud terminal.

Exercice 1: L’entropie

L’entropie est une mesure de l’information, ou plutôt de l’incertitude sur la classification d’un objet. ID3 utilise cette information pour calculer l’arbre de décision le plus petit, ne conservant alors que les informations absolument nécessaires pour classer un objet. Par conséquent, à chaque fois qu’il faut choisir un attribut pour partitionner les exemples, il faut choisir celui qui génère une classification dont l’entropie est minimale.

H(C|A) est l’entropie sur la classification après avoir choisi de partitionner les exemples suivant la valeur de l’attribut A. Elle est donnée par l’équation suivante :

H(C|A) = \sum_{j=1}^{M}p(a_j)H(C|a_j)

où a j est une valeur de l’attribut A, M est le nombre total de valeurs pour l’attribut A et p(a j) la probabilité que la valeur de l’attribut A soit a j.

H(C|aj) est l’entropie sur la classification parmi les exemples pour lesquels l’attribut A vaut aj. Elle est donnée par l’équation suivante :

H(C|a_j) = -\sum_{i=1}^{N}p(c_i|a_j)log_2 p(c_i|a_j)

où N est le nombre de classes différentes, et p(ci|aj) la probabilité conditionnelle qu’un objet soit de la classe ci étant donné que l’attribut A vaut aj.

Dans la classe ID3 (fichier id3.py), écrivez une fonction p, avec quatre arguments: attribut, valeur, exemples et classe. Donnez None comme valeur par défaut à classe. Si classe vaut None, la méthode p retourne retourne la probabilité P(attribut = valeur) (p(a_j)), c’est-à-dire la probabilité que l’attribut attribut vaille valeur dans l’ensemble exemples. Sinon p retourne la probabilité conditionnelle P(classe = classe | attribut = valeur) (p(c_i | a_j)), c’est-à-dire la probabilité qu’un objet soit de la classe classe lorsque l’attribut attribut vaut valeur. Cette probabilité devra être calculée par rapport aux objets d’exemples.

Écrivez une fonction entropie_conditionnelle, avec quatre arguments: attribut, valeur, exemples et classes, qui retourne l’entropie de la sous-classification H(C|aj), où aj est la valeur valeur pour l’attribut attribut. Aidez-vous de la deuxième équation ci-dessus.

Note

Lorsque p(c_i | a_j) = 0, le résultat de p(c_i|a_j)log_2 p(c_i|a_j) est indéfini. Il faut alors prendre la limite et donc traiter ce cas comme p(c_i|a_j)log_2 p(c_i|a_j) = 0

Écrivez une fonction entropie, avec quatre arguments: attribut, valeurs, exemples et classes, qui retourne l’entropie de la classification des objets de exemples après avoir choisi l’attribut attribut H(C|A). Aidez-vous de la première équation ci-dessus.

Exercice 2: La fonction partitions

Écrivez une fonction partitions. Cette fonction prend trois paramètres :

  • attribut - l’attribut A de partitionnement.
  • valeurs - une liste contenant les valeurs aj de l’attribut A.
  • exemples - les exemples d’apprentissage a partitionner.

La méthode retournera une liste des partitions selon la valeur de attribut. Chaque sous-liste lj contiendra les exemples pour lesquels l’attribut A vaut aj.

Note

Si une certaine valeur aj n’apparaît pas dans exemples, la partition correspondante vaudra [].

Exercice 3: La fonction construit_arbre

Ecrivez une fonction construit_arbre qui accepte trois paramètres :

  • attributs - les attributs encore disponibles pour partitionner les exemples.
  • exemples - les exemples de la sous-classification courante.
  • classes - les classes des exemples.

Aidez-vous de l’algorithme ID3 donné ci-dessus.

Indice

Utilisez la fonction entropie pour construire une liste qui associe un attribut à son entropie puis triez la liste pour faire le choix de l’attribut avec l’entropie la plus petite. Utilisez la fonction partitions pour la partition d’exemples selon les valeurs de cet attribut.

Testez ID3

Testez votre module avec les fichiers d’exemples suivants :

  • profit.py: présente des profils d’entreprises informatiques avec les espoirs de profit.
  • maladie.py: essaye de trouver de quelle maladie souffre un enfant.

Utilisez la méthode print_tree de la classe Noeud afin d’afficher l’arbre de décision résultant de construire_arbre.

Essayez d’utiliser l’arbre de décision comme un expert humain de manière interactive à l’aide de la fonction classifie de la classe Noeud.