Apprentissage automatique : les

Chapitre 2
arbres de décision
 Les arbres de décision
 Exemple introductif et préliminaires
 Généralités sur l'apprentissage des arbres de décision
 Un premier algorithme : CART (Breiman et al. [BFOS84])
 Un deuxième algorithme : C4.5 (Quinlan 93 [Qui93])
 Conclusion

Pour certains domaines d'application, il est essentiel de produire des procédures de

classification compréhensibles par l'utilisateur. C'est en particulier le cas pour l'aide au
diagnostic médical où le médecin doit pouvoir interpréter les raisons du diagnostic. Les arbres
de décision répondent à cette contrainte car ils représentent graphiquement un ensemble de
règles et sont aisément interprétables. Pour les arbres de grande taille, la procédure globale
peut être difficile à appréhender, cependant, la classification d'un élément particulier est
toujours compréhensible. Les algorithmes d'apprentissage par arbres de décision sont
efficaces, disponibles dans la plupart des environnements de fouille de données. Ils
constituent l'objet de ce chapitre.

2.1 Les arbres de décision

Exemple 7 La population est constituée d'un ensemble de patients. Il y a deux classes :
malade et bien portant. Les descriptions sont faites avec les deux attributs : Température
qui est un attribut à valeurs décimales et gorge irritée qui est un attribut logique. On
considère l'arbre de décision de la figure ??.

Figure 2.1 : Un exemple d'arbre de décision.

Un arbre de décision est un arbre au sens informatique du terme. On rappelle que les noeuds
d'un arbre sont repérés par des positions qui sont des mots sur {1,...,p}*, où p est l'arité
maximale des noeuds. Si on note le mot vide par , les positions pour l'arbre de la figure ??
sont :
  étiquetée par le test Température<37,5,
 1 étiquetée par le test Gorge irritée,
 2 étiquetée par la feuille malade,
 21 étiquetée par la feuille malade,
 22 étiquetée par la feuille bien portant.

Les noeuds internes sont appelés noeuds de décision. Un tel noeud est étiqueté par un test qui
peut être appliqué à toute description d'un individu de la population. En général, chaque test
examine la valeur d'un unique attribut de l'espace des descriptions. Les réponses possibles au
test correspondent aux labels des arcs issus de ce noeud. Dans le cas de noeuds de décision
binaires, les labels des arcs sont omis et, par convention, l'arc gauche correspond à une
réponse positive au test. Les feuilles sont étiquetées par une classe appelée classe par défaut.

Un arbre de décision est la représentation graphique d'une procédure de classification. En

effet, à toute description complète est associée une seule feuille de l'arbre de décision. Cette
association est définie en commençant à la racine de l'arbre et en descendant dans l'arbre selon
les réponses aux tests qui étiquettent les noeuds internes. La classe associée est alors la classe
par défaut associée à la feuille qui correspond à la description. La procédure de classification
obtenue a une traduction immédiate en terme de règles de décision. Les systèmes de règles
obtenus sont particuliers car l'ordre dans lequel on examine les attributs est fixé et les règles
de décision sont mutuellement exclusives.

Exemple 8 Soit l'arbre de décision de la figure ??. Un patient ayant une température de 39
et ayant la gorge non irritée sera classé comme malade par cet arbre. La traduction de cet
arbre en règles de décision est :
 SI Température<37,5 ET gorge irritée ALORS malade
 SI Température<37,5 ET NON(gorge irritée) ALORS bien portant
 SI NON(Température<37,5) ALORS malade

Nous allons dans ce chapitre étudier différents algorithmes d'apprentissage par arbres de
décision, c'est-à-dire des algorithmes qui, prenant en entrée un échantillon S, construisent un
arbre de décision. Nous allons, tout d'abord, introduire quelques notations. Étant donnés un
échantillon S, un ensemble de classes {1,...,c} et un arbre de décision t, à chaque position p de
t correspond un sous-ensemble de l'échantillon qui est l'ensemble des exemples qui satisfont
les tests de la racine jusqu'à cette position. Par conséquent, on peut définir, pour toute position
p de t, les quantités suivantes :

N(p) est le cardinal de l'ensemble des exemples associé à p,

N(k/p) est le cardinal de l'ensemble des exemples associé à p qui sont de classe k,

P(k/p) = N(k/p)/N(p) la proportion d'éléments de classe k à la position p.

Exemple 9 On considère l'arbre de décision de la figure ??. De plus, on dispose d'un
échantillon de 200 patients. On sait que 100 sont malades et 100 sont bien portants, la
répartition entre les deux classes M (pour malade) et S (pour bien portant) est donnée par :

gorge irritée gorge non irritée

température < 37,5 (6 S, 37 M) (91 S, 1 M)
température  37,5 (2 S, 21 M) (1 S, 41 M)

On a alors : N(11)=43 ; N(S/11)=6 ; N(M/11)=37 ; P(S/11)=6/43 et P(M/11)=37/43.

2.2 Exemple introductif et préliminaires

Nous allons considérer l'exemple très simple suivant pour introduire les algorithmes
d'apprentissage par arbres de décision. Une banque dispose des informations suivantes sur un
ensemble de clients:

client M A R E I
1 moyen moyen village oui oui
2 élevé moyen bourg non non
3 faible âgé bourg non non
4 faible moyen bourg oui oui
5 moyen jeune ville oui oui
6 élevé âgé ville oui non
7 moyen âgé ville oui non
8 faible moyen village non non

L'attribut ternaire M décrit la moyenne des montants sur le compte client. Le second attribut
ternaire A donne la tranche d'âge du client. Le troisième attribut ternaire R décrit la localité de
résidence du client. Le dernier attribut binaire E a la valeur oui si le client a un niveau
d'études supérieures. La classe associée à chacun de ces clients correspond au contenu de la
colonne I. La classe oui correspond à un client qui effectue une consultation de ses comptes
bancaires en utilisant Internet. On souhaite trouver un arbre de décision qui soit capable de
dire si un client effectue des consultations de ses comptes par Internet en connaissant les
valeurs des attributs M (montant), A (âge), R (résidence) et E (études) pour ce client.

À partir de ce tableau, il s'agit donc de construire un arbre de décision qui classifie les clients.
Les algorithmes construisent les arbres de façon descendante. Lorsqu'un test est choisi, on
divise l'ensemble d'apprentissage pour chacune des branches et on réapplique récursivement
l'algorithme. Sur notre exemple, on initialise avec l'arbre vide. L'échantillon contient 8
éléments, 3 sont de classe oui et 5 de classe non. Donc, à la racine de l'arbre qui n'est étiqueté
par aucun test, l'échantillon peut être caractérisé par le couple (3,5). On se pose alors la
question de savoir si ce noeud est terminal, c'est-à-dire encore s'il est nécessaire de rechercher
un test qui discrimine de façon intéressante l'échantillon. Par exemple, on attribuerait une
feuille si nous étions dans le cas (0,8), c'est-à-dire si aucun client n'utilise Internet. Pour notre
cas supposons que nous devions choisir un test. Nous aurions quatre choix possibles qui sont
décrits dans la figure ??.

(3,5)  M (1,2) (2,1) (0,2)

(3,5)  A (1,0) (2,2) (0,3)

(3,5)  R (1,1) (1,2) (1,2)

(3,5)  E (3,2) (0,3)

Figure 2.2 : choix possibles en racine où les branches du test M sont labellés
dans l'ordre par faible, moyen et élevé ; du test A dans l'ordre par jeune,
moyen et âgé ; du test R dans l'ordre par village, bourg et ville ; du test E
dans l'ordre par oui et non.

Laquelle des quatre possibilités faut-il choisir ? Si on regarde le test sur le type de résidence
R, on remarque que ce test ne permet une discrimination sur aucune des branches, on peut
donc se dire que le choix de ce test ne fait rien gagner, il sera donc à rejeter. Par contre, pour
le test sur l'âge A, on remarque que sur la première branche, tous les éléments correspondants
de l'échantillon sont de classe oui et que sur la troisième branche, tous les éléments sont de
classe non. Ce test peut donc être considéré comme << intéressant >>. Ce raisonnement
informel doit être automatisé.

Par conséquent, il nous faut introduire des quantités qui permettent de comparer les différents
choix possibles. Dans ce but, on définit des fonctions qui permettent de mesurer le degré de
mélange des exemples entre les différentes classes. Une telle fonction doit vérifier la propriété
suivante : elle doit prendre son minimum lorsque tous les exemples sont dans une même
classe (le noeud est pur) et son maximum lorsque les exemples sont équirépartis. Par exemple,
si on dispose de 8 éléments et de deux classes, une telle fonction devra prendre son minimum
pour les couples (0,8) et (8,0) et son maximum pour le couple (4,4). Il existe différentes
fonctions qui satisfont ces propriétés, nous en citerons deux : la fonction de Gini et la fonction
entropie. Soit S un échantillon, soit p une position, en reprenant les notations définies
précédemment, ces fonctions sont définies par :
 Entropie(p) = -k=1c P(k/p) × log(P(k/p)) (2.1)

Gini(p)= 1 - k=1c P(k/p)2 (2.2)

= 2 k < k' P(k/p)P(k'/p) (2.3)

Considérons le cas de deux classes et appelons x la proportion d'éléments de classe 1 en

position p. On a donc Entropie(p)= - x log x - (1-x) log (1-x). Cette fonction de x prend ses
valeurs dans l'intervalle [0,1], a son minimum pour x=0 et x=1 qui vaut 0 et a son maximum
pour x=1/2 qui vaut 1. La fonction de Gini est définie par Gini(p) = 2x(1-x). Cette fonction de
x prend ses valeurs dans l'intervalle [0,1/2], a son minimum pour x=0 et x=1 qui vaut 0 et a
son maximum pour x=1/2 qui vaut 1/2. Ces deux fonctions sont symétriques par rapport à
x=1/2. Pour notre exemple courant, considérons, par exemple, l'arbre construit à l'aide de
l'attribut E, nous avons :

 Entropie()= -3/8 log 3/8-5/8 log 5/8~ 0,954

 Entropie(1)= -3/5 log 3/5-2/5 log 2/5 ~ 0.970
 Entropie(2)= -0/3 log 0/3-3/3 log 3/3=0
 Gini()= 2 × 3/8 × 5/8 ~ 0,469
 Gini(1)= 2 × 3/5 × 2/5 = 0.480
 Gini(2)= 2 × 0/3× 3/3=0

On dispose ainsi de fonctions permettant de mesurer le degré de mélange des classes pour tout
échantillon et donc pour toute position de l'arbre en construction. Appelons i la fonction
choisie. Il reste à définir une fonction permettant de choisir le test qui doit étiqueter le noeud
courant. Rappelons que, sur notre exemple, à la racine de l'arbre, il nous faut choisir entre les
quatre tests correspondants aux quatre attributs disponibles. Dans ce but, on introduit une
fonction gain par :
n

Gain(p,t) = i(p)-

j=1
Pj × i(pj) (2.4)

où p désigne une position, test un test d'arité n et Pj est la proportion d'éléments de S à la

position p qui vont en position pj (qui satisfont la jème branche du test test). Si on considère
comme fonction i la fonction entropie, le terme i(p) représente l'entropie actuelle du noeud p,
le deuxième terme de la différence représente l'entropie espérée en introduisant le test test qui
est égale à la somme pondérée des entropies des nouveaux noeuds créés. On souhaite obtenir
des entropies les plus faibles possibles car, d'après les propriétés de la fonction entropie, si
l'entropie est faible, la plupart des éléments se trouvent dans une même classe. On cherche
donc à obtenir le gain maximum. Sur notre exemple, nous obtenons :

 Gain(,M)=Entropie()-(3/8 Entropie(1) + 3/8 Entropie(2) + 2/8 Entropie(3)) =

Entropie() - 0,620
 Gain(,A)=Entropie()-(1/8 Entropie(1) + 4/8 Entropie(2) + 3/8 Entropie(3))=
Entropie() - 0,500
 Gain(,R)=Entropie()-(2/8 Entropie(1) + 3/8 Entropie(2) + 3/8 Entropie(3)) =
Entropie() - 0,870
 Gain(,E)=Entropie()-(5/8 Entropie(1) + 3/8 Entropie(2))= Entropie() - 0,607
Le gain maximal ou encore l'entropie espérée minimale est obtenue pour le choix du test A.
On remarque que le choix du test R est très mauvais, ce qui correspond bien à l'intuition. Dans
ce paragraphe, nous avons introduit la problématique et quelques éléments fondamentaux
utilisés par les algorithmes d'apprentissage par arbre de décision. Nous allons, dans le
paragraphe suivant, présenter le schéma général des algorithmes, puis présenter deux
algorithmes particuliers CART et ID3.

2.3 Généralités sur l'apprentissage des arbres de décision

Idée centrale : Diviser récursivement et le plus efficacement possible les exemples de
l'ensemble d'apprentissage par des tests définis à l'aide des attributs jusqu'à ce que l'on
obtienne des sous-ensembles d'exemples ne contenant (presque) que des exemples
appartenant tous à une même classe.

Dans toutes les méthodes, on trouve les trois opérateurs suivants :

1. Décider si un noeud est terminal, c'est-à-dire décider si un noeud doit être étiqueté
comme une feuille. Par exemple : tous les exemples sont dans la même classe, il y a
moins d'un certain nombre d'erreurs, ...
2. Sélectionner un test à associer à un noeud. Par exemple : aléatoirement, utiliser des
critères statistiques, ...
3. Affecter une classe à une feuille. On attribue la classe majoritaire sauf dans le cas où
l'on utilise des fonctions coût ou risque.

Les méthodes vont différer par les choix effectués pour ces différents opérateurs, c'est-à-dire
sur le choix d'un test (par exemple, utilisation du gain et de la fonction entropie) et le critère
d'arrêt (quand arrêter la croissance de l'arbre, soit quand décider si un noeud est terminal). Le
schéma général des algorithmes est le suivant :

Algorithme d'apprentissage générique

entrée : langage de description ; échantillon S
début
Initialiser à l'arbre vide ; la racine est le noeud courant
répéter
Décider si le noeud courant est terminal
Si le noeud est terminal alors
Affecter une classe
sinon
Sélectionner un test et créer le sous-arbre
FinSi
Passer au noeud suivant non exploré s'il en existe
Jusqu'à obtenir un arbre de décision
fin

Avec un tel algorithme, on peut calculer un arbre de décision dont l'erreur apparente est
faible, voire nulle. Un arbre de décision parfait est un arbre de décision tel que tous les
exemples de l'ensemble d'apprentissage soient correctement classifiés. Un tel arbre n'existe
pas toujours (s'il existe deux exemples tels que à deux descriptions identiques correspondent
deux classes différentes). L'objectif est de construire un arbre d'erreur de classification la plus
petite possible. Mais, on retrouve les problèmes signalés dans le chapitre précédent, c'est-à-
dire :

 l'erreur apparente est une vision très optimiste de l'erreur réelle,

 trouver un arbre de décision d'erreur apparente minimale est, en général, un problème
NP-complet.

L'algorithme présenté précédemment recherche un << bon >> arbre d'erreur apparente faible.
En effet, l'algorithme procède de façon descendante sans jamais remettre en question les choix
effectués et on ne peut jamais exclure qu'un autre choix de test conduise en fait à un meilleur
arbre. L'arbre construit est d'erreur apparente faible car les feuilles sont étiquetées de telle
manière qu'il y ait peu d'erreurs. Mais, comme nous l'avions signalé dans le chapitre sur les
généralités, il se peut que l'erreur réelle soit importante, c'est-à-dire que l'arbre construit soit
bien adapté à l'échantillon mais ait un pouvoir de prédiction faible. Si on examine l'exemple
présenté dans la Figure ??, on constate que l'erreur apparente diminue constamment lors de la
construction de l'arbre mais que l'erreur réelle diminue, se stabilise, puis augmente.

L'idéal serait de trouver un critère qui permette d'arrêter la croissance de l'arbre au bon
moment. Malheureusement, dans l'état actuel des recherches, un tel critère n'a pu être trouvé.
De plus, le risque d'arrêter trop tôt la croissance de l'arbre est plus important que de l'arrêter
trop tard. Par conséquent, les méthodes utilisées procèdent souvent en deux phases. La
première phase correspond à l'algorithme présenté dans ce paragraphe ; dans une seconde
phase, on élague l'arbre obtenu pour essayer de faire diminuer l'erreur réelle (élaguer un arbre
consiste à en supprimer certains sous-arbres). Les méthodes se distinguent donc les unes des
autres par les choix des opérateurs, mais aussi par les méthodes d'élagage utilisées. Nous
revenons plus en détail sur ces choix et ces problèmes dans les deux paragraphes suivants
dans lesquelles nous présentons deux méthodes.

Un premier algorithme : CART (Breiman et al.

2.4
[BFOS84])
Cette méthode permet d'inférer des arbres de décision binaires, i.e. tous les tests étiquetant les
noeuds de décision sont binaires. Le langage de représentation est constitué d'un certain
nombre d'attributs. Ces attributs peuvent être binaires, qualitatifs (à valeurs dans un ensemble
fini de modalités) ou continus (à valeurs réelles). Le nombre de tests à explorer va dépendre
de la nature des attributs. A un attribut binaire correspond un test binaire. A un attribut
qualitatif ayant n modalités, on peut associer autant de tests qu'il y a de partitions en deux
classes, soit 2n-1 tests binaires possibles. Enfin, dans le cas d'attributs continus, il y a une
infinité de tests envisageables. Dans ce cas, on découpe l'ensemble des valeurs possibles en
segments, ce découpage peut être fait par un expert ou fait de façon automatique.

Nous supposons prédéfini un ensemble de tests binaires. Pour définir l'algorithme, nous allons
définir les trois opérateurs utilisés par la méthode CART pour calculer un bon arbre de
décision (phase d'expansion), puis nous verrons la phase d'élagage. Nous nous plaçons dans le
cas d'un échantillon S << assez grand >> qui peut être découpé en un ensemble
d'apprentissage A et un ensemble test T.

 Phase d'expansion. On dispose en entrée d'un ensemble d'apprentissage A. La

fonction utilisée pour mesurer le degré de mélange est la fonction de Gini (ou indice
d'impureté de Gini) définie par l'équation ??.
 1. Décider si un noeud est terminal. Un noeud p est terminal si Gini(p)  i0 ou
N(p)  n0, où i0 et n0 sont des paramètres à fixer.
2. Sélectionner un test à associer à un noeud. Soit p une position et soit test un
test. Si ce test devient l'étiquette du noeud à la position p, alors on appelle Pgauche
(respectivement Pdroite) la proportion d'éléments de l'ensemble des exemples
associés à p qui vont sur le noeud en position p1 (respectivement p2). La
réduction d'impureté définie par le test test est identique au gain et définie par :

Gain(p,test) = Gini(p)-(Pgauche × Gini(p1) + Pdroite × Gini(p2)) .

Cette équation correspond à la définition du gain de l'équation ?? dans le cas de

deux classes en choisissant pour fonction i la fonction de Gini. En position p
(non maximale), on choisit le test qui maximise la quantité Gain(p,test).

3. Affecter une classe à une feuille. On attribue la classe majoritaire.

Soit t l'arbre obtenu en sortie. Pour élaguer, on utilise l'ensemble test T. On suppose,
en effet, que l'erreur apparente sur T est une bonne estimation de l'erreur réelle. Un
élagué de t est obtenu en remplaçant un sous-arbre de t par une feuille. Une première
solution serait d'estimer l'erreur réelle pour tous les élagués de t. Cette méthode est
trop coûteuse en temps de calcul. Il faut, par conséquent, introduire une heuristique
permettant de limiter le nombre d'élagués de t sur lesquels on va estimer l'erreur réelle.
Nous décrivons maintenant la phase d'élagage qui prend pour entrée l'ensemble
d'apprentissage A, l'arbre t produit et un ensemble test T.

 Phase d'élagage.

1. construction de la suite des arbres. On construit une suite t0=t,...,tp telle que t0
soit l'arbre obtenu à la fin de la phase d'expansion, pour tout i, ti+1 est un élagué
de ti et le dernier arbre de la suite tp est réduit à une feuille. Il nous faut définir
le procédé de construction de ti+1 à partir de ti. Pour toute position p de ti, on
note up le sous-arbre de ti en position p. On calcule la quantité
app(p)
g(p) = ,
|up|-1
2. où app(p) est la variation d'erreur apparente mesurée sur l'ensemble
d'apprentissage A lorsqu'on élague t en position p et |up| est la taille de up. On
peut remarquer que
MC(p)-MC(up)
app(p) = ,
N(p)
3. où N(p) est le cardinal de l'ensemble des exemples de A associé à la position p
de ti, MC(p) est le nombre d'éléments de A mal classés à la position p lorsqu'on
élague ti en position p et MC(up) est le nombre d'éléments de A associés à la
position p de ti mal classés par up.

On considère alors la position p pour laquelle g(p) est minimale et ti+1 est
l'élagué de ti en position p.
 4. choix final. On calcule pour chaque arbre ti de la suite construite au point
précédent l'erreur apparente sur l'ensemble Test T. Cette valeur est prise
comme estimation de l'erreur réelle. On retourne donc l'arbre qui minimise
l'erreur apparente sur T.

Lorsque la taille de l'échantillon ne permet pas le découpage en ensembles de test et

d'apprentissage, on utilise alors d'autres méthodes d'élagage. Le principe reste similaire, la
différence est que l'on utilise la validation croisée pour obtenir des approximations de l'erreur
réelle.

Les principes de base de l'algorithme CART sont l'utilisation de la fonction de Gini et un

élagage effectué soit à l'aide d'un ensemble test soit par validation croisée. Cependant, CART
a été intégré a de nombreux environnements de fouille de données et a subi de nombreuses
modifications et améliorations.

2.5 Un deuxième algorithme : C4.5 (Quinlan 93 [Qui93])

2.5.1 Algorithme de base
On suppose toujours que le langage de représentation est constitué d'un certain nombre
d'attributs. Ces attributs peuvent être binaires, qualitatifs (à valeurs dans un ensemble fini de
modalités) ou continus (à valeurs réelles). Pour les attributs continus, on utilise des
heuristiques qui permettent de les discrétiser. On utilise pour cela des critères statistiques qui
permettent d'atteindre les deux objectifs suivants : un nombre de classes pas trop important et
une bonne répartition entre les différentes classes. On peut par exemple utiliser la fonction
entropie pour atteindre ces objectifs. Nous supposons maintenant que les attributs ont été
discrétisés.

Nous supposons prédéfini un ensemble de tests n-aires. Pour définir l'algorithme, nous allons
définir les trois opérateurs utilisés par l'algorithme C4.5 pour calculer un bon arbre de
décision (phase d'expansion), puis nous verrons la phase d'élagage. On suppose disposer d'un
ensemble d'apprentissage A.

 On dispose en entrée d'un ensemble d'apprentissage A. On utilise la fonction entropie

définie par l'équation ??.

1. Décider si un noeud est terminal. Un noeud p est terminal si tous les

éléments associés à ce noeud sont dans une même classe ou si aucun test n'a pu
être sélectionné (voir ci-après).
2. Sélectionner un test à associer à un noeud. À chaque étape, dans l'ensemble
des tests disponibles, ne peuvent être envisagés que les tests pour lesquels il
existe au moins deux branches ayant au moins deux éléments (cette valeur par
défaut peut être modifiée). Si aucun test ne satisfait cette condition alors le
noeud est terminal. Soit p une position, on choisit alors le test test qui
maximise le gain défini dans l'équation ?? en utilisant la fonction entropie
définie dans l'équation ?? pour mesurer le degré de mélange. La fonction Gain,
ainsi définie, privilégie les attributs ayant un grand nombre de valeurs (voir
exercice ??). Elle est donc pondérée par une fonction qui pénalise les tests qui
répartissent les éléments en un trop grand nombre de sous-classes. Cette
mesure de la répartition est nommée SplitInfo et est définie par :
SplitInfo(p,test) = - n P'(j/p) × log(P'(j/p)) (2.5)
 j=1
3.
dans laquelle n est l'arité de test et P'(j/p) est la proportion des éléments
présents à la position p prenant la j-ème valeur de test. Il faut remarquer que,
contrairement à l'entropie, la définition précédente est indépendante de la
répartition des exemples à l'intérieur des différentes classes. La valeur de
Splitinfo ne dépend que de la répartition entre les différentes valeurs possibles
pour le test. Cette fonction a des valeurs grandes lorsque le test a un grand
nombre de valeurs possibles avec peu d'éléments pour chacune des valeurs. En
effet, considérons le cas extrême d'un attribut n-aire avec un exemple par
classe, la fonction vaut alors log n. À l'inverse, considérons la cas d'un attribut
binaire pour lequel les exemples sont répartis uniformément entre ces deux
valeurs, la fonction vaut alors 1. La nouvelle fonction de gain, appelée ratio de
gain et notée GainRatio, est alors définie par :
Gain(p,T)
GainRatio(p,T) = (2.6)
SplitInfo(p,T)
4.
En position p (non maximale), on choisit le test qui maximise le GainRatio
(option par défaut de C4.5). On peut modifier les options pour utiliser le Gain.
5. Affecter une classe à une feuille. On attribue la classe majoritaire. Si il n'y a
aucun exemple on attribue la classe majoritaire du noeud père.

2.5.2 Phase d'élagage de C4.5

C4.5 utilise l'ensemble d'apprentissage pour élaguer l'arbre obtenu. Le critère d'élagage est
basé sur une heuristique permettant d'estimer l'erreur réelle sur un sous-arbre donné. Bien
qu'il semble peu pertinent d'estimer l'erreur réelle sur l'ensemble d'apprentissage, il semble
que la méthode donne des résultats corrects. Citons Quinlan :

Although this method does have the subtle flaw of << indirecly training on test
cases >> it performs quite well on large samples with at least 1000 test cases.
With fewer cases, the risks of training on the test cases is greater.

Cette méthode est présentée dans l'exercice ??. Une autre heuristique est proposée par C4.5.
On construit le système à base de règles associé à l'arbre de décision produit en sortie de la
phase d'expansion. On choisit ensuite une méthode permettant de coder à la fois les règles et
les exceptions (exemples mal classifiés par les règles). Lorsqu'on supprime une règle, on
risque de voir augmenter le nombre d'exceptions. Mais il se peut aussi que la taille du codage
diminue globalement. Dans ce cas, on choisit la règle dont la suppression produit la plus forte
diminution. On applique ce procédé de façon itérative tant que la taille des codages diminue.
Cette méthode est une application du principe MDL (Minimum Description Length) qui
consiste à choisir parmi plusieurs théories celle dont le codage (théorie plus exceptions) est
minimal.

2.5.3 Améliorations
Attributs discrets
 Pour les attributs discrets possédant un grand nombre de valeurs, nous avons vu que la
fonction GainRatio permettait d'éviter de privilégier ces attributs. Il existe, de plus,
une option de C4.5 qui permet le regroupement des valeurs. Par exemple, si on dispose
d'un attribut A prenant les valeurs a, b, c et d, en standard le test considéré serait 4-
aire. Si on active l'option regroupement, seront également considéré des tests de la
forme : le test binaire A {a,b} et A {c,d} ; le test ternaire A=a , A=c et A
{b,d} ; ...
Attributs continus
Pour les attributs continus, la discrétisation peut être laissée à un expert du domaine
d'application. Par exemple, en médecine, l'expérience du domaine peut avoir permis la
mise en évidence l'existence de valeurs seuil pour un attribut correspond à une mesure
médicale. Sinon, l'algorithme gère les attributs continus de la façon suivante : les
exemples sont triés dans l'ordre croissant pour l'attribut continu A considéré, on
considère alors tous les tests de la forme A>ai + ai+1/2 où ai et ai+1 sont deux valeurs
consécutives de l'attribut A. Par exemple, supposons que A prenne les valeurs 1 ; 3 ; 6 ;
10 ; 12, alors on considère les tests A>1,5 ; A>4,5 ; A>8 et A>11, ces tests participent
alors à la compétition dans la recherche du test apportant le meilleur gain (fonction
Gain ou GainRatio, selon l'option choisie).
Attributs à valeurs manquantes
Dans de nombreux problèmes concrets, il existe certains attributs dont les valeurs ne
sont pas renseignées. Par exemple, si on dispose du descriptif de patients, il est très
probable que toutes les mesures ne soient pas disponibles car elles n'ont pas pu être
faites pour tous les patients. Pour classifier un exemple possédant des valeurs
manquantes à l'aide d'arbres de décision, on procède comme dans le cas standard,
lorsque l'on rencontre un test et que la valeur de l'attribut est manquante, on considère
la branche majoritaire. Pour la phase d'apprentissage, on suppose que la valeur de cet
attribut suit la distribution des valeurs connues. Le lecteur peut se reporter à l'exercice
??.
2.6 Conclusion
Les méthodes à base d'arbres de décision les plus importantes sont :
 CART développée par Breiman et al. en 84. Cette méthode, développée par des
statisticiens, construit des arbres de décision binaires. Cette méthode peut être étendue
pour traiter le cas d'attributs continus. Le critère de Gini est utilisé pour associer un
test à un noeud. L'élagage de l'arbre se fait par estimation de l'erreur réelle en utilisant
un ensemble test. La phase d'élagage peut être modifiée pour le cas d'échantillons de
plus petite taille, on utilise alors la validation croisée comme estimation de l'erreur
réelle.
 ID3 développée par Quinlan en 83, améliorée en 93 par une nouvelle version C4.5
(voir [Qui93]). On ne se restreint pas à des attributs binaires. Le choix du test associé à
un noeud se fait à l'aide de la fonction Gain ou de la fonction GainRatio basées sur la
fonction entropie. La méthode peut prendre en compte le cas où les valeurs de certains
attributs sont non spécifiées. Elle prend également en compte le problème des attributs
continus. On peut choisir entre arbres et règles, l'élagage se fait sur l'arbre ou sur le
système de règles et se base sur une estimation de l'erreur réelle à partir de l'ensemble
d'apprentissage.
 Signalons une dernière méthode basée sur le principe MDL (Minimum Description
Length) de Rissanen. Cette méthode a été développée par Quinlan et Rivest [QR89].
Elle construit l'arbre de décision qui permet de coder de la façon la plus courte
possible l'échantillon (on code l'arbre et les exceptions). Cette méthode permet de faire
 des ponts intéressants entre codages et probabilités et a des performances
satisfaisantes.

Les arbres de décision fournissent des méthodes effectives qui obtiennent de bons résultats
dans la pratique. Les arbres de décision possèdent l'avantage d'être compréhensibles par tout
utilisateur (si la taille de l'arbre produit est raisonnable) et d'avoir une traduction immédiate en
terme de règles de décision. Pour le système à base de règles induit, les règles sont
mutuellement exclusives et l'ordre dans lequel sont examinés les attributs est figé. Les
méthodes sont non optimales : les arbres produits ne sont pas les meilleurs. En effet, les choix
dans la construction des arbres, basées sur de nombreuses heuristiques, ne sont jamais remis
en question (pas de retour en arrière (ou backtraking)). Enfin, il est possible de modifier les
valeurs de nombreux paramètres, de choisir entre de nombreuses variantes et faire le bon
choix n'est pas toujours aisé. La taille des échantillons influera sur les critères d'élagage à
choisir (sur l'ensemble d'apprentissage, sur un ensemble test, validation croisée, ...).

Enfin, comme les algorithmes présentés dans ce chapitre permettent la génération de systèmes
à base de règles, il nous faut faire le lien avec l'approche Systèmes Experts. Les deux
approches << à partir de données >> et << par expertise >> être considérées comme
concurrentes et complémentaires :
 L'approche système expert peut être envisagée si l'on dispose d'une expertise
suffisante dans le domaine d'application visé et si cette expertise est formalisable en
terme de règles. La taille du domaine d'application doit être bien délimitée.
L'expérience a prouvé que la maintenance et l'évolution des systèmes experts était une
tâche difficile.
 Les méthodes d'apprentissage sont utilisés dans des domaines où les experts n'arrivent
pas à dégager les règles qu'ils utilisent (et d'ailleurs, en utilisent-ils ?). Les règles sont
générées à partir de données (souvent des données historiques pour le problème).
 Mais il arrive également que ces deux approches soient utilisées conjointement : des
experts seront souvent de bon conseil pour dégager les attributs pertinents relativement
à un problème donné ; dans certains cas, des systèmes d'apprentissage produiront
automatiquement des règles qui pourront être directement insérés dans un système
expert.