Intelligence Artificielle - Algorithme ID3¶
NB : ne pas confondre avec le modèle de voiture ...
Algorithme ID3¶
Iterative Dichotomiser (version) 3¶
Algorithme de classification par apprentissage supervisé.
Les objets sont représéntés par des caractéristiques (ici appelés attributs) prises dans des ensembles finis,
Les classes sont $C_1, C_2, ... C_n$,
on dispose de $N$ objets déjà classés (ici appelés exemples)
L'algorithme construit un arbre de décision à partir de l'ensemble d'apprentissage¶
Qu'est-ce qu'un arbre de décision ??
Exemple d'arbre de décision¶
Etant donnée la météo du jour, va-t-on jouer au golf, ou non ?¶
sur la base des jours passés (données d'entraînement)¶
Traductions¶
4 caractéristiques (à valeurs discrètes)¶
météo (outlook) : soleil (sunny) / nuageux (overcast) / pluie (rain)
température : chaud (hot) / moyen (mild) / froid (cold)
humidité : élevé (high) / normal (normal)
vent (windy) : oui (true) / non (false)
2 classes¶
- décision (positive/negative) : OUI / NON
Ensemble d'entraînement : 14 exemples¶
NON
OUI
Algorithme de classification à partir de l'arbre¶
(Facile ...)
Pour classer un objet dont les valeurs d'attributs sont $(a_1, a_2, ..., a_d)$ :
on part de la racine
si c'est un noeud interne (attribut), on suit la branche correspondant à la valeur d'attribut de l'objet à classer, et on itère
si c'est une feuille (classe), on renvoie la classe indiquée
Principe de construction de l'arbre de décision¶
(Plus dur ...)
A partir de l'ensemble d'entraînement $E$ :
on considère un attribut : par exemple Humidité
on sépare l'ensemble d'entraînement selon les valeurs de cet attribut : élevé/normal
Rappel :
On note $E_{|Humidité = élevé}$ : les exemples pour lesquels le taux d'humidité est élevée¶
On note $E_{|Humidité = élevé}$ : les exemples pour lesquels le taux d'humidité est élevée¶
$E_{|Humidité = élevé}$¶
3 OUI, 4 NON¶
On ne peut pas conclure ...¶
on peut utiliser les autres attributs, par exemple Météo
$E_{|Humidité = élevé, Météo = soleil}$¶
$E_{|Humidité = élevé, Météo = nuageux}$¶
$E_{|Humidité = élevé, Météo = pluie}$¶
Arbre en cours de construction :¶
Arbre en cours de construction :¶
Construction complète : cf Fiche¶
NB¶
- si tous les attributs ont été exploités, et qu'on ne peut toujours pas conclure, on conclut avec la classe la plus représentée (classe prépondérante)
- en cas d'égalité, on peut utiliser la classe prépondérante au niveau du noeud parent
- l'ordre des attributs examinés peut varier d'une branche à l'autre
- selon l'ordre dans lequel on examine les attributs, on obtient des arbres différents
Un "bon" arbre de décision¶
Un "mauvais" arbre de décision¶
"bon" ou "mauvais" arbre de décision ?¶
- Plus l'arbre a de noeuds internes, plus il occupera d'espace mémoire
- La moyenne de la profondeur des feuilles donne le coûteux moyen pour prédire la classe d'un objet
NB : dans le pire des cas, la profondeur sera égale au nombre d'attributs
Algorithme ID3 : choix de l'attribut "séparateur"¶
Etant donné un ensemble annoté, quel attribut sélectionner pour obtenir un "bon" arbre ?
Idée :
- c'est celui qui séparera le "mieux" l'ensemble des objets annotés
- c'est celui qui mettra le plus d'ordre dans les sous-ensembles obtenus
Comment mesurer l'ordre ?
Comment mesurer le désordre ?
Mesure du désordre en physique ?
L'ENTROPIE !¶
Entropie (théorie de l'information) :¶
Très similaire à la notion d'"entropie thermodynamique"
L'entropie (de Shannon) mesure le "désordre" :
- entropie élevée : beaucoup de désordre (ex : 123312132231)
- entropie faible : moins de désordre (ex : 11121113111)
- entropie nulle : absence de désordre (ex : 22222222222)
 |
père de la "Théorie de l'Information" (1948, Bell Labs) notions de bit, bruit, codage / décodage, entropie ... applications : traitement du signal, télécommunications |
| Claude Shannon |
Entropie (théorie de l'information)¶
Définition formelle :
Pour $X$ variable aléatoire discrète, d'univers image $\{x_1, x_2, ... x_n\}$, et sa loi de probabilité (distribution de probabilité) $\forall i, P(X=x_i) = p_i$,
$H(X) = -\displaystyle\sum_{i=1}^np_i\log_2(p_i)$
$H(X) = -\displaystyle\sum_{i=1}^np_i\log_2(p_i)$
NB :
- pour $p_i = 0$, on considère que $p_i\log_2p_i = 0$ (limite lorsque $p_i \to 0$)
- $p_i \in ]0;1]$ donc $\log_2(p_i) \leq 0$
- donc $H(X) \geq 0$
"Entropie d'un ensemble d'exemples" pour ID3¶
Soit $E$ un de $N$ exemples.
la probabilité associée à la classe $c$ est la fréquence de $c$ dans $E$ : $\dfrac{nb\;exemples\; de\;classe\;c}{nb\;total\;d'exemples} = \dfrac{n_c}{N}$
On note $H(E) = -\displaystyle \sum_{c \in \mathcal{C}}\dfrac{n_c}{N} \log_2{\dfrac{n_c}{N}}$
$H(E) = -\displaystyle \sum_{c \in \mathcal{C}}\dfrac{n_c}{N} \log_2{\dfrac{n_c}{N}}$
Prop : L'entropie est nulle si tous les objets sont de même classe (facile)
un terme de la somme vaut $\dfrac{N}{N} \log_2{\dfrac{N}{N}} = 1\log_21 = 0$
tous les autres valent $\dfrac{0}{N} \log_2{\dfrac{0}{N}} = 0\log_20 = 0$ (limite)
Prop : l'entropie est maximale si toutes les classes ont même fréquence (plus difficile)
Exemples de calcul de l'entropie¶
Avec $\mathcal{C} = \{OUI, NON\}$ : $H(E) = -\dfrac{n_{OUI}}{N}\log_2\dfrac{n_{OUI}}{N} -\dfrac{n_{NON}}{N}\log_2\dfrac{n_{NON}}{N}$
0 OUI, 6 NON : $H(E) = -\dfrac{0}{6}\log_2\dfrac{0}{6} (limite) - \dfrac{6}{6}\log_2\dfrac{6}{6} = 0 $
5 OUI, 1 NON : $H(E) = -\dfrac{5}{6}\log_2\dfrac{5}{6} - \dfrac{1}{6}\log_2\dfrac{1}{6} \simeq 0.65$
2 OUI, 4 NON : $H(E) = -\dfrac{2}{6}\log_2\dfrac{2}{6} - \dfrac{4}{6}\log_2\dfrac{4}{6} \simeq 0.92$
4 OUI et 2 NON : $H(E) = -\dfrac{4}{6}\log_2\dfrac{4}{6} - \dfrac{2}{6}\log_2\dfrac{2}{6} \simeq 0.92$
3 OUI et 3 NON : $H(E) = -\dfrac{3}{6}\log_2\dfrac{3}{6} - \dfrac{3}{6}\log_2\dfrac{3}{6} = 1$
Représentation graphique de la fonction entropie¶
Avec $\mathcal{C} = \{OUI, NON\}$ :
$H(E) = -\dfrac{n_{OUI}}{N}\log_2\dfrac{n_{OUI}}{N} -\dfrac{n_{NON}}{N}\log_2\dfrac{n_{NON}}{N}$
or $\dfrac{n_{NON}}{N} = \dfrac{N - n_{OUI}}{N} = 1-\dfrac{n_{OUI}}{N}$
donc $H(E) = -\dfrac{n_{OUI}}{N}\log_2\dfrac{n_{OUI}}{N} -(1-\dfrac{n_{OUI}}{N})\log_2(1-\dfrac{n_{OUI}}{N})$
En posant $x = \dfrac{n_{OUI}}{N} \in [0;1]$, $H(x) = -x \log_2 x - (1-x)\log_2 (1-x)$
Graphe de $x\mapsto H(x) = -x \log_2 x - (1-x)\log_2 (1-x)$¶
Graphe de $x\mapsto H(x)$¶
s'il n'y a que des NONs : $x = \dfrac{n_{OUI}}{N} = 0$ et H(0) = 0 : pas de désordre ,
s'il n'y a que des OUIs : $x = \dfrac{n_{OUI}}{N} = 1$ et H(1) = 0 : pas de désordre ,
s'il y a autant de OUIs que de NONs : $x = \dfrac{n_{OUI}}{N} = 0.5$ et H(0.5) = 1, maximal : désordre maximal
Retour à l'algorithme ID3¶
On choisit l'attribut pour lequel l'entropie pondérée des sous-ensembles obtenus après séparation est minimale¶
On appelle gain pour l'attribut A : $G(A) = H(E) - \displaystyle \sum_{a \in \mathcal{A}}\dfrac{ card(E_{|A=a})}{card(E)}H(E_{|A=a})$
NB : c'est une diminution d'entropie. On calcule : "H initial - pondération des H finaux"
On choisit comme attribut séparateur l'attribut de gain maximal
- c'est-à-dire celui qui fait diminuer le plus l'entropie
- c'est-à-dire celui qui fait diminuer le désordre
- c'est-à-dire celui qui fait le mieux régner l'ordre !
Quelques variantes de l'algorithme ID3¶
- garder les fréquences des classes au niveau des feuilles
- travailler sur des attributs numériques continus
Variante d'ID3 : garder les fréquences / probabilités au niveau des feuilles¶
(Attention, exemple morbide ...)
on obtient une réponse avec un certain degré de fiabilité
3 attributs
- sexe : masculin / feminin
- age : adulte / enfant
- voyage : 3e classe (classe éco) / (1ere ou 2eme classe)
2 classes
- rescapé /mort
sur le Titanic : "sauvez les enfants et les femmes d'abord (sauf la classe éco ...)"
Variante d'ID3 : travailler avec des attributs continus¶
Obtention d'un prêt bancaire :¶
| Age | revenu mensuel | patrimoine | obtention du prêt |
|---|---|---|---|
| 19 | 1600 | 0 | NON |
| 40 | 1200 | 0 | NON |
| 25 | 4000 | 0 | OUI |
| 27 | 2000 | 20 k€ | OUI |
| 52 | 3200 | 300 k€ | OUI |
| 70 | 1200 | 100 k€ | NON |
| ... | ... | ... | ... |
3 attributs : âge, revenu, patrimoine
2 classes : OUI / NON
Les "questions" de l'arbre de décision : on utilise de "tranches" d'âge / revenu / patrimoine