Notes de Cours : Data Mining
Séance 6, 21 Octobre 2013
Prof. Chiraz Ben Abdelkader, ENSI
Plan: Classification par arbres de decision
Introduction
1)
2) Construction d’un arbre de décision
Références :
(Disponibles sur mon Google Drive, sous le dossier « Références & Ressources »)
1) Notes de cours (en Français) : Prof. Philippe Preux, Chapitre 3, p. 15 -24
Comme il y en a quelques graves fautes de frappes, ne l’utiliser pas comme référence primaire.
2) Livre (en Anglais): Data Mining, Practical ML tools and techniques, Chapitre 4 p. 99-103
1) Introduction
Il s’agit d’une des méthodes de classification supervisée les plus fréquemment
utilisées. C’est une méthode à base de modèle (et non pas à base d’exemplaires
représentatifs).
On se rappelle du problème de la classification supervisée :
o On se donne un ensemble X de n exemples notés (xi,yi), ou xi consiste des
valeurs de p attributs, qui peuvent être soit quantitatifs ou qualitatifs ; et
yi est un attribut qualitatif nommé la classe (ou étiquette). Le couple (xi,yi)
caractérise un exemple d’une population d’objets quelconque.
o On vise à induire un classeur pour les nouvelles données ; c’est-à-dire
construire un algorithme qui, étant donné une nouvelle donnée
quelconque x, il prédit la classe y qui lui correspond.
Définitions :
o Un arbre de décision est un classeur (donc un algorithme de classification)
basé sur la notion abstraite d’un arbre.
o De point de vue mathématique, un arbre est une catégorie spéciale de
graphes. Un arbre a une racine, des nœuds, des branches, et des feuilles.
o Un arbre de décision ressemble à un organigramme de programmation
(une représentation graphique de l'enchaînement des opérations et des
décisions effectuées par un algorithme ou programme d'ordinateur), ou :
Chaque nœud (y compris la racine) correspond à un test logique
sur la valeur d’un ou plusieurs attributs,
Chaque branche partant d’un nœud correspond à une ou plusieurs
valeurs de ce test,
A chaque feuille est associée une valeur de la classe, y Y.
o L’exécution (application) du classeur avec une nouvelle donnée
quelconque x consiste à parcourir l’arbre de décision de la racine à une
feuille, selon les valeurs des attributs dans x. La feuille à la fin de ce
chemin est la prédiction de la classe qui correspond à x.
o On dit qu’une donnée x est couverte par un nœud (dans un arbre de
décision) si ce nœud est inclut dans le chemin qui correspond à x.
o Un arbre de décision est dit optimal s’il minimise le nombre d’erreurs de
classification, c’est-à-dire maximise le taux de classification correcte.
Exemple : L’arbre de décision au-dessous s’agit d’un classeur pour «Jouer Tennis»
Source: Notes de cours, Prof. Philippe Preux, Chapitre 3, p. 24
o Il a trois nœuds :
nœud Ciel (racine): test sur la valeur de l’attribut « Ciel » avec 3
branches
nœud Vent: test sur la valeur de l’attribut « Vent » avec 2 branches
nœud Humidité: test sur la valeur de l’attribut «Humidité » avec 2
branches
o Il a cinq feuilles : trois feuilles qui correspondent à la classe « oui » et deux
feuilles qui correspondent à la classe « non ».
o Chaque branche est marquée de la valeur correspondante de l’attribut.
o Questions :
Quel est le chemin et la classe qui correspondent aux données :
(Couvert,Fraiche,Elevee,Fort) ?
Quel sont les données couvertes par chaque nœud ?
Publicité
la racine couvre tous les exemplaires.
Le sous-nœud droit de la racine couvre tous les exemplaires
dont la valeur de l’attribut Humidité est Elevée.
Etc.
Interprétation de l’arbre : quels attributs sont les plus pertinents ?
2) Construction d’un Arbre de Décision
a) Introduction
Comme pour toutes les méthodes de classification supervisées, il faut tout
d’abord construire le classeur en utilisant une approche systématique.
Pour les arbres de décision, les approches d’induction les plus fréquemment
utilisées sont ID3, C4.5, et C5.0.
o ID3 : ne prend en compte que des attributs nominaux.
o C4.5 et C5.0: extensions de l’ID3, pour prendre en compte des
attributs quantitatifs (numériques).
Dans ce qui suit, on discute seulement l’algorithme ID3. (C4.5 et C5.0 sont en
fait assez similaires à ID3.)
ID3 = Iterative Dichotomiser 3, par Ross Quinlan en 1979.
Caractéristiques importantes de l’algorithme ID3 :
o ne prend en compte que les attributs nominaux.
o chaque nœud correspond à un test logique sur la valeur d’un seul
attribut (et non pas plusieurs attributs, comme dans le cas général).
Donc, chaque feuille correspond à une combinaison unique des valeurs
des p attributs.
b) Description Récursive de l’Algorithme ID3
Interface : ID3(X,A)
o Données : X l’ensemble des exemplaires, A l’ensemble d’attributs
o Sorties : un sous-arbre de décision.
Cas général de l’algorithme :
1) construire la racine de l’arbre en choisissant un attribut am de l’ensemble
A qui va être testé dans ce nœud,
2) construire une branche partant de la racine pour chaque valeur de am.
3) pour chaque valeur de am, appel récursif a ID3(Xi,A - am) , ou Xi est le
sous-ensemble de X pour lesquels am prend cette valeur.
Donc X et A diminuent petit à petit avec chaque nouvel appel récursif à
l’algorithme.
Cas dégénéré de l'algorithme : la récursion s’arrête lorsque les éléments de
X sont tous de la même classe, ou si X et/ou A sont vides. Dans tous ces cas,
on construit une nouvelle feuille associée à la classe suivante :
o Si les éléments de X sont tous de la même classe y : y.
o Si X est vide: la classe la plus fréquente dans le nœud-père.
o Si X est non vide et A est vide : la classe la plus fréquente dans X.
On note que dans chaque étape (appel récursif a l’algorithme), l’ensemble X
se partitionne a des sous-ensembles disjoints selon l’attribut choisit am :
o un sous-ensemble pour chaque valeur de am .
o nombre de branches (et donc sou-nœuds) = nombre d’appels récursifs
= nombre de valeurs de am.
Source: Notes de cours, Prof. Philippe Preux, Chapitre 3, p. 22
c) Méthode de choix de l’attribut am
L’étape clé de l’ID3, s’effectue en déterminant l’attribut qui maximise le gain
Publicité
d’information--un concept lié à la notion d’entropie.
Définition: L’entropie d’un ensemble d’exemplaires X est définit comme :
(
XH
)
p
y
log
p
y
Yy
ou py est la proportion d’exemplaires dans X ayant y comme classe.
o H(X) est donc toujours dans l’intervalle [0,1]
(on note que 0log0 = 0)
o Intuitivement, H(X) mesure le degré d’hétérogénéité de l’ensemble X
par apport aux classes de ses éléments. Elle est minimale (0) quand
tous les exemplaires ont la même classe. Elle est maximale (1) quand
les exemplaires sont uniformément repartis sur toutes les classes.
Définition: Le gain d’information pour un attribut aj est définit comme :
1
G
(
,
a
)
j
H
(
)
j
i
H
(
j
i
)
ou
j
i
est le sous-ensemble de X associée à l’ieme valeur de aj .
i
o La quantité à droite de la soustraction est en fait l’entropie moyenne
.
sur tous les sous-ensembles
j
i
o Les opérandes de cette soustraction sont tous les deux dans l’intervalle
[0,1], donc G est toujours dans l’intervalle [-1,1].
o De plus, on peut prouver que G est toujours supérieur à zéro, donc G
est toujours dans l’intervalle [0,1].
On rappelle que l’ID3 choisit am qui maximise le gain d’information, donc :
a
m
arg
a
Publicité
j
max
G
(
,
a
)
j
max
H
(
)
arg
a
j
1
i
j
i
H
(
j
i
)
max
arg
a
j
i
j
i
H
(
j
i
)
min
arg
a
j
i
j
i
H
(
j
i
)
o Evidemment, plus G(X,aj) est grande, plus H(Xi
j) sont petites, plus les
sou-ensembles, Xi
sont homogènes.
j , associés à chaque branche de la racine actuelle
o Donc, en choisissant am avec maximum gain d’information, on veut que
les exemplaires associé à chaque branche soient le plus homogènes
possible ; donc, que leurs entropies soient minimales.
d) Exemple
Voir TD no. 4
Publicité