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

TODO:

faire un document séparé pour ID3, CART, C4.5, etc. ou mettre tout dans ce notebook ???



In [ ]:

    
import pandas as pd

Principales implémentations en Python

Les arbres de décision

TODO:

mettre un exemple: illustration générée à partir d'une bibliothèque dédiée
expliquer la signification des noeuds, des entrées, des sorties, etc.

Les noeuds des arbres de décisions sont appelés des attributs.
Ils ont un ensemble fini de valeurs possibles.
Les feuilles de l'arbre sont les classes.

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)



In [ ]:

    
data_list = [['soleil', 'chaud', 'haute', 'faux', 'NePasJouer'],
             ['soleil', 'chaud', 'haute', 'vrai', 'NePasJouer'],
             ['couvert', 'chaud', 'haute', 'faux', 'Jouer'],
             ['pluie', 'bon', 'haute', 'faux', 'Jouer'],
             ['pluie', 'frais', 'normale', 'faux', 'Jouer'],
             ['pluie', 'frais', 'normale', 'vrai', 'NePasJouer'],
             ['couvert', 'frais', 'normale', 'vrai', 'Jouer'],
             ['soleil', 'bon', 'haute', 'faux', 'NePasJouer'],
             ['soleil', 'frais', 'normale', 'faux', 'Jouer'],
             ['pluie', 'bon', 'normale', 'faux', 'Jouer'],
             ['soleil', 'bon', 'normale', 'vrai', 'Jouer'],
             ['couvert', 'bon', 'haute', 'vrai', 'Jouer'],
             ['couvert', 'chaud', 'normale', 'faux', 'Jouer'],
             ['pluie', 'bon', 'haute', 'vrai', 'NePasJouer']]

columns_list = ['ciel', 'temperature', 'humidite', 'vent', 'golf']

df = pd.DataFrame(data_list, columns=columns_list)
df

L'algorithme ID3

Quinlan, 1979

TODO...

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

Construction de l'arbre: algorithme récursif
- ..., ..., critère d'arret, ...
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
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)
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
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
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 [ ]:

    
# TODO

Exemple 1

Tiré de "exemple1.txt" de JG Ganascia

(Tiré de Quinlan 1983)



In [ ]:

    
data_list = [['soleil', 'chaud', 'haute', 'faux', 'NePasJouer'],
             ['soleil', 'chaud', 'haute', 'vrai', 'NePasJouer'],
             ['couvert', 'chaud', 'haute', 'faux', 'Jouer'],
             ['pluie', 'bon', 'haute', 'faux', 'Jouer'],
             ['pluie', 'frais', 'normale', 'faux', 'Jouer'],
             ['pluie', 'frais', 'normale', 'vrai', 'NePasJouer'],
             ['couvert', 'frais', 'normale', 'vrai', 'Jouer'],
             ['soleil', 'bon', 'haute', 'faux', 'NePasJouer'],
             ['soleil', 'frais', 'normale', 'faux', 'Jouer'],
             ['pluie', 'bon', 'normale', 'faux', 'Jouer'],
             ['soleil', 'bon', 'normale', 'vrai', 'Jouer'],
             ['couvert', 'bon', 'haute', 'vrai', 'Jouer'],
             ['couvert', 'chaud', 'normale', 'faux', 'Jouer'],
             ['pluie', 'bon', 'haute', 'vrai', 'NePasJouer']]

columns_list = ['ciel', 'temperature', 'humidite', 'vent', 'golf']

df = pd.DataFrame(data_list, columns=columns_list)
df

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)



In [ ]:

    
data_list = [['soleil', 'chaud', 'haute', 'faux', 'NePasJouer'],
             ['soleil', 'chaud', 'haute', 'vrai', 'NePasJouer'],
             ['couvert', 'chaud', 'haute', 'faux', 'Jouer'],
             ['pluie', 'bon', 'haute', 'faux', 'Jouer'],
             ['pluie', 'frais', 'normale', 'faux', 'Jouer'],
             ['pluie', 'frais', 'normale', 'vrai', 'NePasJouer'],
             ['pluie', 'frais', 'normale', 'vrai', 'Jouer'],
             ['soleil', 'bon', 'haute', 'faux', 'NePasJouer'],
             ['soleil', 'frais', 'normale', 'faux', 'Jouer'],
             ['pluie', 'bon', 'normale', 'faux', 'Jouer'],
             ['soleil', 'bon', 'normale', 'vrai', 'Jouer'],
             ['couvert', 'bon', 'haute', 'vrai', 'Jouer'],
             ['couvert', 'chaud', 'normale', 'faux', 'Jouer'],
             ['pluie', 'bon', 'haute', 'vrai', 'NePasJouer']]

columns_list = ['ciel', 'temperature', 'humidite', 'vent', 'golf']

df = pd.DataFrame(data_list, columns=columns_list)
df

Exemple 3

Tiré de "lentilles.txt" de JG Ganascia

TODO: traduire la base suivante en Français...



In [ ]:

    
data_list = [['young', 'myope', 'no', 'reduced', 'none'],
             ['young', 'myope', 'no', 'normal', 'soft'],
             ['young', 'myope', 'yes', 'reduced', 'none'],
             ['young', 'myope', 'yes', 'normal', 'hard'],
             ['young', 'hypermetrope', 'no', 'reduced', 'none'],
             ['young', 'hypermetrope', 'no', 'normal', 'soft'],
             ['young', 'hypermetrope', 'yes', 'reduced', 'none'],
             ['young', 'hypermetrope', 'yes', 'normal', 'hard'],
             ['pre-presbyopic', 'myope', 'no', 'reduced', 'none'],
             ['pre-presbyopic', 'myope', 'no', 'normal', 'soft'],
             ['pre-presbyopic', 'myope', 'yes', 'reduced', 'none'],
             ['pre-presbyopic', 'myope', 'yes', 'normal', 'hard'],
             ['pre-presbyopic', 'hypermetrope', 'no', 'reduced', 'none'],
             ['pre-presbyopic', 'hypermetrope', 'no', 'normal', 'soft'],
             ['pre-presbyopic', 'hypermetrope', 'yes', 'reduced', 'none'],
             ['pre-presbyopic', 'hypermetrope', 'yes', 'normal', 'none'],
             ['presbyopic', 'myope', 'no', 'reduced', 'none'],
             ['presbyopic', 'myope', 'no', 'normal', 'none'],
             ['presbyopic', 'myope', 'yes', 'reduced', 'none'],
             ['presbyopic', 'myope', 'yes', 'normal', 'hard'],
             ['presbyopic', 'hypermetrope', 'no', 'reduced', 'none'],
             ['presbyopic', 'hypermetrope', 'no', 'normal', 'soft'],
             ['presbyopic', 'hypermetrope', 'yes', 'reduced', 'none'],
             ['presbyopic', 'hypermetrope', 'yes', 'normal', 'none']]

columns_list = ['age', 'prescription', 'astigmatic', 'tear_rate', 'lenses']

df = pd.DataFrame(data_list, columns=columns_list)
df