L'apprentissage d'arbres de décision avec ID3

Jérémie Decock (www.jdhp.org)

Attention:

Veuillez noter que ce document est en cours de rédaction. Dans son état actuel, il n'est pas destiné à être lu par d'autres personnes que ses auteurs.

Principales implémentations en Python

Les arbres de décision

Générer un arbre de décisions à partir d'une base d'exemples

On cherche à générer (apprendre) un arbre de décision à partir de la base d'exemples suivante:

(Tiré de Quinlan 1983)

Out[2]:
ciel temperature humidite vent golf
0 soleil chaud haute faux NePasJouer
1 soleil chaud haute vrai NePasJouer
2 couvert chaud haute faux Jouer
3 pluie bon haute faux Jouer
4 pluie frais normale faux Jouer
5 pluie frais normale vrai NePasJouer
6 couvert frais normale vrai Jouer
7 soleil bon haute faux NePasJouer
8 soleil frais normale faux Jouer
9 pluie bon normale faux Jouer
10 soleil bon normale vrai Jouer
11 couvert bon haute vrai Jouer
12 couvert chaud normale faux Jouer
13 pluie bon haute vrai NePasJouer

L'algorithme ID3

Quinlan, 1979

On construit automatiquement un arbre à partir d'une base d'exemples.

  1. Construction de l'arbre: algorithme récursif
    • ..., ..., critère d'arret, ...
  2. Choix des attributs
    • on pourrait se contenter de choisir les attributs au hasard pour chaque noeud de l'arbre dans l'algorithme précédent
  3. d'accord mais si on veut construire l'arbre le plus simple possible
    • (une des bonnes raisons de vouloir faire un arbre simple: un arbre simple a plus de chance d'être bon en généralisation qu'un arbre inutilement compliqué)
    • d'abord qu'est-ce qu'un arbre simple ?
    • un critère possible (arbitraire): un arbre simple est un arbre qui minimise le nombre de questions en moyenne (ie qui minimise le nombre de noeuds traversé en moyenne pour définir la classe d'un exemple)
  4. ok mais comment on fait ?
    • une première approche très naive pourrait consister à générer tous les arbres possible suivant l'algorithme 1., compter (ou calculer avec des probas) le nombre moyen de question sur la base des exemples et retenir l'arbre qui minimise ce nombre moyen de question
    • problème: c'est pas très rusé et ça peut être très long si il y a beaucoup d'attributs et/ou d'exemples
  5. ok mais on peut faire mieux que ça non ?
    • Entropie = mesure du désordre dans une collection d'objets
    • Si tous les objets appartiennent à la même classe, pas de désordre (entropie nuelle)
    • On choisi l'attribut qui minimise le désordre de la partition résultante
  6. ok mais comment on mesure l'entropie d'un ensemble d'exemples ? ...
    • Shannon a proposé une mesure de l'entropie ...

Pourquoi? ...

slide 18:

Meilleur ensemble de questions (code de Huffman)

Nombre moyen de questions:

$$ P(rouge) \times 1 + P(bleu) \times 2 + P(vert) \times 3 + P(marron) \times 3 = \frac12 \times 1 + \frac14 \times 2 + \frac18 \times 3 + \frac18 \times 3 = 1.75 $$

Ok, c'est intuitif si on regarde l'arbre des tirages possibles dans le slide d'avant.

Les couleurs représentent les classes de notre problème.

Entropie:

$$ Entropie d'un ensemble d'exemples = - \sum_{i \in \Omega} p_i \log_2 (p_i) $$

Avec $\Omega$ l'ensemble des classes du problème.

  • $b$ bits permettent de coder $i = 2^b$ informations.
  • $b = \log_2(i)$ bits permettent de coder $i$ informations.

Une implémentation en Python

Algorithme

In [3]:
# TODO

Exemple 1

Tiré de "exemple1.txt" de JG Ganascia

(Tiré de Quinlan 1983)

Out[4]:
ciel temperature humidite vent golf
0 soleil chaud haute faux NePasJouer
1 soleil chaud haute vrai NePasJouer
2 couvert chaud haute faux Jouer
3 pluie bon haute faux Jouer
4 pluie frais normale faux Jouer
5 pluie frais normale vrai NePasJouer
6 couvert frais normale vrai Jouer
7 soleil bon haute faux NePasJouer
8 soleil frais normale faux Jouer
9 pluie bon normale faux Jouer
10 soleil bon normale vrai Jouer
11 couvert bon haute vrai Jouer
12 couvert chaud normale faux Jouer
13 pluie bon haute vrai NePasJouer

Exemple 2

Tiré de "exemple2.txt" de JG Ganascia.

La seule différence avec l'exemple 1: première colonne de la ligne 6 (du dataframe).

(Tiré de Quinlan 1983)

Out[5]:
ciel temperature humidite vent golf
0 soleil chaud haute faux NePasJouer
1 soleil chaud haute vrai NePasJouer
2 couvert chaud haute faux Jouer
3 pluie bon haute faux Jouer
4 pluie frais normale faux Jouer
5 pluie frais normale vrai NePasJouer
6 pluie frais normale vrai Jouer
7 soleil bon haute faux NePasJouer
8 soleil frais normale faux Jouer
9 pluie bon normale faux Jouer
10 soleil bon normale vrai Jouer
11 couvert bon haute vrai Jouer
12 couvert chaud normale faux Jouer
13 pluie bon haute vrai NePasJouer

Exemple 3

Tiré de "lentilles.txt" de JG Ganascia

Out[6]:
age prescription astigmatic tear_rate lenses
0 young myope no reduced none
1 young myope no normal soft
2 young myope yes reduced none
3 young myope yes normal hard
4 young hypermetrope no reduced none
5 young hypermetrope no normal soft
6 young hypermetrope yes reduced none
7 young hypermetrope yes normal hard
8 pre-presbyopic myope no reduced none
9 pre-presbyopic myope no normal soft
10 pre-presbyopic myope yes reduced none
11 pre-presbyopic myope yes normal hard
12 pre-presbyopic hypermetrope no reduced none
13 pre-presbyopic hypermetrope no normal soft
14 pre-presbyopic hypermetrope yes reduced none
15 pre-presbyopic hypermetrope yes normal none
16 presbyopic myope no reduced none
17 presbyopic myope no normal none
18 presbyopic myope yes reduced none
19 presbyopic myope yes normal hard
20 presbyopic hypermetrope no reduced none
21 presbyopic hypermetrope no normal soft
22 presbyopic hypermetrope yes reduced none
23 presbyopic hypermetrope yes normal none