Slises Tanagra

ère !) le meilleur couple (attribut;test) pour créer un nœud - ce test sépare X en 2 parties Xg et Xd - contruire-arbre(Xg) - construire-arbre(Xd)

Brève introduction aux arbres de décision

Fabien Moutarde, CAOR, MINES ParisTech

21/05/2008

7

Critère de choix attribut et test

• Mesure de l’hétérogénéité du nœud candidat :

– entropie (ID3, C4.5) – indice Gini (CART) – indice d’erreur

• Entropie : H = - Σk p(wk) log2(p(wk)) avec p(wk) proba de la classe wk (estimée par proportion Nk/N) minimum (=0) si une seule classe représentée maximum (=log2(nb_classes)) si classes équi-réparties • Indice Gini : Gini = 1 – Σk p2(wk) • Indice d’erreur : Er = 1 – maxk(p(wk))

Brève introduction aux arbres de décision Fabien Moutarde, CAOR, MINES ParisTech 21/05/2008 8

Gain d’homogénéité apporté par un test

• Soit un test T à m alternatives et divisant le nœud N en m sous-nœud Nj • Soit I(Nj) les mesures d’hétérogénéité (entropie, Gini, …) des sous-nœuds, et p(Nj) les proportions des éléments de N dirigés vers Nj par le test T le gain d’homogénéité/information apporté par le test T est Gain(N,T) = I(N)- Σj p(Nj)I(Nj) À chaque nœud, choix du test maximisant le gain

(ou éventuellement le « rapport des gains » G(N,T)/H(T), utilisé par C4.5 pour éviter biais vers m grand)

Brève introduction aux arbres de décision

Fabien Moutarde, CAOR, MINES ParisTech

21/05/2008

9

Tests sur les attributs continus

• Nb FINI d’exemples d’apprentissage idem pour le nb de valeurs effectivement atteintes par chaque attribut continu En pratique, tri des exemples par valeur croissante de l’attribut continu et examen d’au maximum N-1 seuils

(typiquement les médianes entre valeurs successives croissantes :par exemple si valeurs de A atteintes sur exemples d’apprentissage sont 1;3;6;10;12, on considérera les tests A>1.5;A>4.5;A>8;A>11)

Brève introduction aux arbres de décision

Fabien Moutarde, CAOR, MINES ParisTech

21/05/2008

10

Critères d’arrêt et élagage

• Règles « évidentes » : - tous les exemples du nœud sont de même classe - tous exemples du nœud ont mêmes valeurs de variables - l’hétérogénéité des nœuds ne diminue plus - nb d’exemples dans le nœud < seuil minimal • Contrôle des performances de généralisation (sur base de validation indépendante) • Elagage a posteriori : supprimer des branches peu représentatives et nuisant à généralisation (parcours bottomup en « remontant » d’un niveau tant que cela diminue erreur en généralisation)

Brève introduction aux arbres de décision

Fabien Moutarde, CAOR, MINES ParisTech

21/05/2008

11

Critère pour l’élagage a posteriori

Soit l’arbre T, et v un de ses nœuds, et :

• MC(T,v) = nb d’exemples Mal Classés par v dans T • MCela(T,v) = nb d’exemples Mal Classés par v dans l’arbre T élagué à v • n(T) = nb de feuilles de T • nt(T,v) = nb de feuilles du sous-arbre de T sous nœud v

ALORS on prend comme critère à minimiser :

w(T,v) = (MCela(T,v)-MC(T,v))/(n(T)*(nt(T,v)-1))

Prise en compte simultanée de l’erreur et de la complexité de l’arbre

Brève introduction aux arbres de décision Fabien Moutarde, CAOR, MINES ParisTech 21/05/2008 12

Algorithme d’élagage

Elaguer(Tmax) : K←0 ← Tk←Tmax TANT QUE Tk a plus d’un nœud FAIRE POUR chaque nœud v de Tk FAIRE calculer w(Tk,v) sur exemples appr. ou valid. FIN_POUR choisir vm = tel que w(Tk,v) soit minimum Tk+1: Tk où vm a été remplacé par une feuille k←k+1 ← FIN_TANT_QUE Pour finir, on choisit parmi {Tmax, T1, … Tn} l’arbre qui a la plus petite erreur de classification sur l’ensemble de validation

Brève introduction aux arbres de décision Fabien Moutarde, CAOR, MINES ParisTech 21/05/2008 13

Synthèses des divers algos d’induction

• ID3 (Inductive Decision Tree, Quinlan 1979) :

– arbres « de discrimination » (ie variables uniquement qualitatives) – critère d’hétérogénéité = entropie

• C4.5 (Quinlan 1993) :

– Amélioration ID3, permettant notamment arbres « de régression » (gestion des variables continues) et valeurs manquantes

• CART (Classification And Regression Tree, Breiman et al. 1984)