Classification Supervis e (par Apprentissage)
Introduction
Une premi re approche possible pour classifier des individus est lapproche bas e sur les syst mes
experts. En effet, la connaissance dun, ou de plusieurs, expert(s) peut tre d crite sous la forme
dun ensemble de r gles. Cet ensemble forme un syst me expert qui est utilis pour classifier de
nouveaux cas. Cette approche, largement utilis e en 80, d pend fortement de la capacit extraire
et formaliser les connaissances de lexpert. Nous consid rons ici une autre approche pour laquelle
la proc dure de classification sera extraite automatiquement partir dun ensemble dexemples,
sachant quun exemple consiste en la description dun cas avec la classification correspondante.
En effet, un syst me dapprentissage extrait, partir de cet ensemble dexemples (base
dapprentissage), une proc dure de classification. Il sagit ainsi dinduire une proc dure de
classification g n rale partir dun ensemble dexemples. Le probl me est ainsi inductif, puisque il
sagit dextraire une r gle g n rale partir dexemples observ es. La proc dure g n r e devrait
classifier correctement les exemples de l chantillon mais surtout avoir un bon pouvoir pr dictif
pour classifier correctement de nouvelles donn es. En particulier, les m thodes issues de
lintelligence artificielle sont des m thodes non param triques. On distingue les m thodes
symboliques (la proc dure de classification produite peut tre crite sous forme de r gles) des
m thodes non symboliques ou adaptatives (la proc dure de classification produite est de type
bo te noire ). Parmi les m thodes symboliques, les plus utilis es sont bas es sur les arbres de
d cision. Pour les m thodes adaptatives, on distingue deux grandes classes : les r seaux de neurones
et les algorithmes g n tiques.
Apprentissage automatique : les arbres de d cision
Il est souvent essentiel de produire des proc dures de classification compr hensibles par lutilisateur
(e.g. laide 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 facilement interpr tables.
Exemple : La population est un ensemble de patients. Il y a 2 classes: malade et bien
portant. Les descriptions sont faites avec les 2 attributs: Temp rature qui est un attribut
valeurs d cimales et gorge irrit e qui est un attribut logique.
Les nSuds internes sont appel s nSuds de d cision. Un tel nSud est tiquet par un test qui peut
tre appliqu toute description dun individu de la population. En g n ral, chaque test examine la
valeur dun seul attribut de lespace des descriptions. Les r ponses possibles au test correspondent
aux labels des arcs issus de ce nSud. Dans le cas de nSuds de d cision binaires, les labels des arcs
sont facultatifs et, par convention, larc gauche correspond une r ponse positive au test.
Les feuilles sont tiquet es par une classe (dite classe par d faut).
W. Barhoumi
Un arbre de d cision est la repr sentation graphique dune proc dure de classification. En effet,
toute description compl te est associ e une seule feuille de larbre. Cette association est d finie en
commen ant la racine de larbre et en descendant dans larbre selon les r ponses aux tests qui
tiquettent les nSuds 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 termes de r gles de d cision. Les syst mes de r gles obtenus sont particuliers car lordre dans
lequel on examine les attributs est fix et les r gles de d cision sont mutuellement exclusives.
Pour l'arbre de d cision de lexemple, 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 ceci 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
Advertisement
Nous tudions ici diff rents algorithmes dapprentissage par arbres de d cision. Ces algorithmes
prenant en entr e un chantillon S et construisent un arbre de d cision. 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 lensemble 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 lensemble des exemples associ p,
N(k/p) est le cardinal de lensemble des exemples associ p qui sont de classe k,
P(k/p)
= N(k/p)/N(p)
d l ments
proportion
classe k
de
la
la
position p.
Pour larbre de d cision de lexemple, si en plus, on dispose dun chantillon de 200 patients. On
sait que 100 sont malades et 100 sont bien portants, et 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.
Exemple introductif et pr liminaires
Consid rons lexemple suivant pour introduire les algorithmes d'apprentissage par arbres de
informations suivantes sur un ensemble de clients:
d cision. Une banque dispose des
client M
E
A
I
R
1 moyen moyen village Oui oui
Non non
2 lev moyen bourg
Non non
bourg
3 faible g
Oui oui
4 faible moyen bourg
Oui oui
5 moyen jeune ville
Oui non
ville
6 lev g
7 moyen g
Oui non
Advertisement
ville
8 faible moyen village Non non
W. Barhoumi
Lattribut 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.
Il sagit de construire, partir de ce tableau, un arbre de d cision qui classifie les clients de fa on
descendante. Lorsquun test est choisi, on divise lensemble dapprentissage pour chacune des
branches et on r applique r cursivement lalgorithme. Sur notre exemple, on initialise avec larbre
vide. L chantillon contient 8 l ments, 3 sont de classe oui et 5 de classe non. Ainsi, la racine
de larbre qui nest 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 nSud est terminal (i.e. est-il 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 nutilise Internet. Pour notre cas supposons que
nous devions choisir un test, nous aurions quatre choix possibles.
(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)
Ceci illustre les choix possibles en racine o les branches du test M sont labellis 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 ; et 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 . Pour ce faire,
il faut introduire des quantit s qui permettent de comparer les diff rents choix possibles. Ceci
revient d finir 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 : prendre son minimum
lorsque tous les exemples sont dans une m me classe (le nSud 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, parmi lesquelles figurent 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) = -S
c P(k/p) log(P(k/p))
k=1
Gini(p) = 1 - S
= 2 S
c P(k/p)2
k=1
Advertisement
k < k' P(k/p)P(k'/p)
W. Barhoumi
Consid rons le cas de deux classes et soit 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 lintervalle
[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
lintervalle [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, larbre construit laide de lattribut E, nous avons :
" Entropie(e )= -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(e )= 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 larbre en construction. Appelons i la fonction choisie. Il
reste d finir une fonction permettant de choisir le test qui doit tiqueter le nSud courant.
Rappelons que, sur notre exemple, la racine de larbre, il nous faut choisir entre les quatre tests
correspondants aux quatre attributs disponibles. Dans ce but, on introduit une fonction gain par :
Gain(p,t) = i(p)-
Pj i(pj)
N
j=1
o p d signe une position, test un test darit 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 lentropie actuelle du nSud p, le deuxi me
terme de la diff rence repr sente lentropie esp r e en introduisant le test test qui est gale la
somme pond r e des entropies des nouveaux nSuds cr s. On souhaite obtenir des entropies les
plus faibles possibles car, dapr 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(e ,M)=Entropie(e )-(3/8 Entropie(1) + 3/8 Entropie(2) + 2/8 Entropie(3)) = Entropie(e ) - 0,620
" Gain(e ,A)=Entropie(e )-(1/8 Entropie(1) + 4/8 Entropie(2) + 3/8 Entropie(3))= Entropie(e ) - 0,500
" Gain(e ,R)=Entropie(e )-(2/8 Entropie(1) + 3/8 Entropie(2) + 3/8 Entropie(3)) = Entropie(e ) - 0,870
" Gain(e ,E)=Entropie(e )-(5/8 Entropie(1) + 3/8 Entropie(2))= Entropie(e ) - 0,607
Le gain maximal ou encore lentropie 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 confirme lintuition. Apr s lintroduction de
la probl matique et de quelques l ments fondamentaux utilis s par les algorithmes dapprentissage
par arbre de d cision, nous allons pr senter le sch ma g n ral des algorithmes, puis pr senter deux
algorithmes particuliers CART et ID3.
G n ralit s sur l'apprentissage des arbres de d cision
Id e : Diviser r cursivement les exemples dapprentissage par des tests d finis laide des attributs
jusqu ce que les sous-ensembles dexemples ne contiennent (presque) que des exemples
appartenant une m me classe. Dans toutes les m thodes, on trouve les 3 op rateurs suivants :
1. D cider si un nSud est terminal, cest- -dire d cider si un nSud doit tre tiquet comme
une feuille. Par exemple : tous les exemples sont dans la m me classe, il y a moins dun
certain nombre derreurs, ...
Advertisement
2. S lectionner un test associer un nSud. Par exemple : al atoirement, utiliser des
crit res statistiques, ...
W. Barhoumi
3. Affecter une classe une feuille. On attribue la classe majoritaire sauf dans le cas o lon
utilise des fonctions co t ou risque.
Les m thodes vont diff rer par les choix effectu s pour ces diff rents op rateurs, cest- -dire sur le
choix dun test (par exemple, utilisation du gain et de la fonction entropie) et le crit re darr t
(quand arr ter la croissance de larbre, soit quand d cider si un nSud est terminal). Le sch ma
g n ral est comme suit :
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 lerreur apparente est faible,
voire nulle. Un arbre de d cision parfait est un arbre de d cision tel que tous les exemples de
lensemble d'apprentissage soient correctement classifi s. Un tel arbre nexiste pas toujours (sil
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. En
effet, lerreur apparente est une vision tr s optimiste de lerreur r elle, et trouver un arbre de
d cision derreur apparente minimale est un probl me NP-complet. Ainsi, lalgorithme pr sent
pr c demment recherche un bon arbre derreur apparente faible. Lalgorithme proc de de fa on
descendante sans jamais remettre en question les choix effectu s et on ne peut jamais exclure quun
autre choix de test conduise en fait un meilleur arbre. L arbre construit est derreur apparente
faible car les feuilles sont tiquet es de telle mani re quil y ait peu d'erreurs. Mais, il se peut que
lerreur r elle soit importante (i.e. larbre construit soit bien adapt l' chantillon mais ait un
pouvoir de pr diction faible). Il est possible que lerreur apparente diminue constamment lors de la
construction de larbre alors que lerreur r elle diminue, se stabilise, puis augmente.
Lid al serait de trouver un crit re qui permette darr ter la croissance de larbre au bon moment.
Malheureusement, dans l tat actuel des recherches, un tel crit re nest pas encore disponible. De
plus, le risque darr ter trop t t la croissance de larbre est plus important que de larr 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 lerreur 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. Les m thodes les plus utilis es, et qui
diff rent par leurs choix (op rateurs + lagage), sont CART et C4.5
W. Barhoumi