Master 2 Recherche en InformatiqueEcole Normale Superieure de Cachan

Etude de criteres de separationpour les arbres de decision

stage realise au sein de l’equipe-projet Texmex de l’INRIA Bretagne-Atlantique

sous la direction d’Annie Morin

2 fevrier 2009 – 30 juin 2009

Olivier Schwander

ENS Cachan INRIA Bretagne-Atlantique

Introduction

Les arbres de decision sont l’une des plus anciennes techniques utilisees en apprentissageautomatique. A ce jour plusieurs techniques de construction de ces arbres coexistent sans qu’au-cune n’offre des performances significativement meilleures que les autres.

Il existe des etudes experimentales qui montrent que les differentes techniques de construc-tion offrent des performances equivalentes, mais peu de travaux s’interessent aux differencesentre les arbres obtenus. L’objectif du stage est d’etudier une etape precise de la construction,la facon de choisir la variable qui permettra de separer un nœud en plusieurs branches, et decomprendre dans quelle mesure les differentes techniques font des choix similaires ou differents.

1

Table des matieres

1 Arbres de decisions 31.1 Presentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31.2 Decision . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31.3 Construction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31.4 Algorithmes classiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

2 Points de depart 82.1 Informaticiens et statisticiens . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82.2 Etudes experimentales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82.3 Critere du χ2 et indice de Gini . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92.4 Critere du χ2 et gain d’information . . . . . . . . . . . . . . . . . . . . . . . . . . 9

3 Comparaison entre χ2 et et gain d’information 113.1 Cadre des simulations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113.2 Desaccords entre criteres . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123.3 Cas discret . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 263.4 Modelisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

Bibliographie 35

2

Chapitre 1

Arbres de decisions

1.1 Presentation

Les arbres de decisions sont l’une des plus anciennes methodes utilisees en apprentissage parordinateur et en statistique inferentielle : d’apres [Rakotomalala, 2005], la premiere utilisationremonterait a [Morgan et Sonquist, 1963].

Cette methode a eu un tel succes grace a plusieurs avantages :– les processus de construction et de decision sont assez simple,– il est possible pour un expert de comprendre l’arbre produit,– c’est une methode non-parametrique,– elle est rapide pour des bases qui tiennent en memoire.Les arbres de decisions sont encore largement utilises de nos jours, notamment au sein de

methodes recentes, comme les forets aleatoires [Breiman, 2001].

1.2 Decision

Un arbre de decision est un arbre dont les nœuds contiennent des tests. Chaque test portesur les variables (en general une seule a la fois) qui decrivent les donnees. En fonction du resultatdu test, la donnee inconnue est orientee dans l’un des sous-arbres.

Chaque feuille de l’arbre est etiquetee par l’une des classes. Quand la donnee inconnue atteintl’une des feuilles, elle se voit attribuer la classe associee a cette feuille.

Exemple TODOexemple de decision sur un petit arbre

1.3 Construction

1.3.1 Etapes de l’algorithme

Les arbres sont construits en utilisant un algorithme recursif. Initialement, l’arbre est formed’un seul nœud, contenant toutes les donnees d’apprentissage. A chaque etape, l’ensemblecontenu dans le nœud est separe en plusieurs branches, selon une condition de separation oulaisse intact pour former un nœud terminal.

Il y a donc deux parties importantes dans cet algorithme ([Rakotomala, 2008]) :– le critere d’arret, pour decider si un nœud est terminal ou pas,– le critere de separation, pour creer le test qui va realiser la separation.

3

CHAPITRE 1. ARBRES DE DECISIONS

Le critere d’arret a pour but de limiter la taille de l’arbre, a la fois pour des problemes dememoire et pour assurer la generalisation en evitant une specialisation trop grande de l’arbre.On peut se baser sur un critere de precision (quand une certaine proportion d’une certaine classeest atteinte dans un nœud) ou d’effectif (on n’essaye plus de separer au dessous d’un certainnombre d’instances dans le nœud).

Le role du critere de separation est de separer un ensemble de donnees en plusieurs sous-ensembles, de facon interessante pour la classification. Le principe est de selectionner la variablela plus discriminante pour la grandeur a predire et d’effectuer un test sur celle-ci pour construireles sous-ensembles.

Exemple : On dispose d’informations sur des animaux, et on veut savoir si ce sont des oiseaux.Les donnees correspondantes sont donnees dans le tableau 1.1.

Numero Rouge Ailes Oiseau1 oui oui oui2 oui oui oui3 non oui oui4 oui non non5 non non non6 oui non non

Tab. 1.1 – Exemple de donnees

On voit immediatement que le fait de posseder des ailes est plus parlant pour identifier unoiseau que sa couleur. On peut donc faire une premiere separation sur cette variable, ce quidonne l’abre de la figure 1.1.

Ailes ?

3 oiseaux1 autres

oui

0 oiseaux2 autres

non

Fig. 1.1 – Exemple d’arbre

Bien sur, le but est d’effectuer ce choix de facon automatique, en attribuant a chaque variableun score decrivant sa pertinence vis-a-vis de la variable a predire.

4

CHAPITRE 1. ARBRES DE DECISIONS

1.3.2 Criteres de choix de la variable de separation

Presentation

Dans la suite, on notera Y la variable a predire et Xi les variables decrivant les donnees. Leprobleme est de trouver une variable sur laquelle realiser la separation. La methode de selectionest assez simple : pour chaque variable possible, le partitionnement va etre realise et evalue parun indicateur de qualite [Rakotomalala, 2005]. C’est de cet indicateur de qualite que nous allonsdiscuter par la suite.

Pour chaque variable de separation possible, nous definissons un tableau de contingencecroisant la variable a predire et la variable candidate. En reprenant l’exemple du tableau 1.1,on obtient le tableau 1.2.

Rouge ?Oiseau ? Oui Non

Oui 2 1Non 1 2

Tab. 1.2 – Exemple de tableau de contingence

Pour le tableau de contingence d’une variable X a L modalites et pour L classes possibles,on utilisera la notation du tableau 1.3.

x1 xl xL

y1...

yk · · · nkl · · · nj...

yK

nk n

Tab. 1.3 – Tableau de contingence quelconque

Liaison statistique

Une mesure de liaison statistique cherche a quantifier dans quelle mesure la connaissance deXi nous renseigne sur celle de Y .

On va utiliser le test d’independance du χ2 pour determiner si les valeurs observees concordentavec l’hypothese d’independance, obtenue quand la variable observee n’apprend rien sur la va-riable a predire. Voici donc la formule utilisee :

χ2 =K∑

k=1

L∑l=1

(nkl − nknl

n

)2nknl

n

Remarquons que la valeur du χ2 varie donc entre 0 (independance) et +∞ (tres fort lien)et que cette formule tend a avantager les variables avec beaucoup de normalites.

On utilisera donc en general la normalisation suivante, dite t de Tschuprow (evoquee dans[Rakotomalala, 2005]) :

5

CHAPITRE 1. ARBRES DE DECISIONS

t =χ2

n√

(K − 1)(L− 1)

La meilleure variable pour realiser la separation est celle qui a obtenu le score le plus eleve,c’est a dire celle pour laquelle le lien avec la variable a predire est le plus eleve.

Information

Une autre notion naturelle pour evaluer l’utilite d’une variable pour en predire une autreest l’information [Rakotomala, 2008] : on va chercher quelle variable nous apporte le plus d’in-formation sur la variable a predire.

Commencons par definir l’entropie de Shannon associee a la variable Y :

E(Y ) =K∑

k=1

nk

nlog

nk

n

Une premiere mesure de qualite de la separation peut etre l’entropie conditionnelle :

E(Y |X) =L∑

l=1

K∑k=1

nl

n

nkl

nllog

nkl

nl

Cette grandeur est nulle si les deux variables sont independantes et augmente avec l’infor-mation apportee par X sur Y .

On peut aussi utiliser le gain d’entropie :

G(Y |X) = E(Y )− E(Y |X)

ou sa version normalisee qui tient compte de la distribution marginale de X :

GR(Y |X) =G(Y |X)E(X)

Indice de concentration

La troisieme famille de conditions de separation est l’indice de concentration, ou indice deGini ([Rakotomala, 2008]. Celui-ci mesure le degre d’impurete au sein d’un ensemble de donnees.

Definissons l’indice de Gini de la variable Y :

I(Y ) = 1−K∑

k=1

(nk

n

)2

De facon analogue a l’entropie ([Mingers, 1989]), on peut definir l’indice de Gini conditionnelet l’amelioration de la concentration :

I(Y |X) =L∑

l=1

nl

n

(1−

K∑k=1

(nkl

nl

)2)

et

D(Y |X) = I(Y )− I(Y |X)

6

CHAPITRE 1. ARBRES DE DECISIONS

1.4 Algorithmes classiques

Algorithmes classiques

Cette partie a pour but de lister quelques uns des algorithmes de construction d’arbres dedecision parmi les plus connus. Il ne s’agit pas de donner une description exhaustive de ceux-ci,mais seulement d’exposer brievement les solutions retenues.

ID3 et C4.5 Introduits respectivement dans [Quinlan, 1986] et [Quinlan, 1993], l’algorithmeID3 et son amelioration C4.5 utilisent l’entropie pour realiser la separation des nœuds. Chaquemodalite possible pour la variable de separation choisie conduit a une nouvelle branche differente.

Cet algorithme est bien adapte aux petits effectifs et est peu sensible au parametrage.Cependant, la phase d’elagage est moins efficace sur de grosses bases.

CART La methode de [Breiman, 1984], CART (pour Classification and Regression Tree),utilise l’indice de Gini comme condition de separation. Les differentes modalites sont regroupeesen deux groupes de facon a obtenir des arbres binaires [Rakotomala, 2008].

Cette methode offre de bonnes performances en general, sans parametres a regler. Par contre,la binarisation n’est pas toujours appropriee et conduit a des arbres plus profonds.

CHAID L’algorithme CHAID (CHi-squared Automatic Interaction Detector) de [Kass, 1980]se sert du critere du χ2. Il utilise une solution intermediaire pour la creation des branches : enregroupant les modalites conduisant a des branches proches, il obtient un arbre a mi-cheminentre un arbre binaire et un arbre qui aurait exactement une branche par modalite.

C’est une methode interessante sur de grosses bases de donnees mais pour laquelle il estdifficile de trouver les bons parametres pour le regroupement des branches.

7

Chapitre 2

Points de depart

2.1 Informaticiens et statisticiens

La question du choix entre les χ2 et l’information n’est pas tant un probleme de qualitequ’une question de parcours des gens qui elaborent l’algorithme de construction : les statisti-ciens ont plus tendance a preferer le χ2 tandis que les informaticiens se tourneront plutot versl’information. Il est cependant generalement admis que ces deux approches sont equivalentes(voir par exemple [Chauchat et Rakotomalala, 1999]).

Le premier argument quant au lien entre ces deux approches provient de [Benzecri, 1982](et n’a rien de specifique aux arbres de decision). Ces deux approches servent toutes deux acomparer deux lois de probabilite : pIJ et la loi produit pIpJ . Etudions la distance entre cesdeux distributions a l’aide du χ2.

||pIJ − pIpJ ||2 =∑i∈I

∑j∈J

pij − pipj

pipj

=∑i∈I

∑j∈J

pipj

(pij

pipj

2− 1)

car∑pipj = 1 =

∑pij .

Comparons l’expression obtenue avec celle de l’information mutuelle :

H(pij |pipj) =∑i∈I

∑j∈J

pij logpij

pipj

=∑i∈I

∑j∈J

pipjφ1

(pij

pipj

)en posant φ1(x) = x log x.

Si on pose φ2(x) = x2 − 1 dans l’expression obtenue pour le χ2, on remarque que les deuxformules ne varient que par la fonction φ utilisee.

De plus, les fonctions φ1 et φ2 sont osculatrices (meme derivees premieres et secondes) auvoisinage du point x = 1.

2.2 Etudes experimentales

Un autre argument pour l’equivalence entre le χ2 et l’information provient de l’etude experimentalede [Mingers, 1989]. Apres une presentation exhaustive et detaillee des differentes conditions de

8

CHAPITRE 2. POINTS DE DEPART

separation existantes, il etudie l’influence de ces criteres sur le taux d’erreur et la taille desarbres generes. Voici un bref resume de ses conclusions :

– le critere n’influe pas significativement sur le taux d’erreur,– la taille des arbres produits varie fortement,– apres elagage, on retrouve des arbres de taille comparable.Le resultat le plus surprenant est que si la variable de separation est choisie aleatoirement —

ce qui conduit a des arbres tres grands — le taux d’erreur reste sensiblement le meme qu’avecd’autres methodes.

En fait, cette affirmation est contredite par [Buntine et Niblett, 1992] : le partitionnementaleatoire conduit a de tres mauvaises performances. Buntime explique que Mingers a utilise lememe ensemble de donnees pour elaguer les arbres et pour evaluer les performances, ce quiconduit a un taux d’erreur sous-evalue.

2.3 Critere du χ2 et indice de Gini

La comparaison entre le critere du χ2 et l’indice de Gini a ete traitee dans [Grabmeier et Lambe, 2007].Le resultat principal est que le χ2 et Gini conduisent a des arbres identiques, pour des problemesde classification binaire : quel que soit le critere utilise, les variables seront classees dans le memeordre lor de la construction de l’arbre.

Ce resultat ne s’applique qu’au cas de la classification binaire, un contre-exemple est donneepour le cas ou les donnees sont separees en trois classes.

[Grabmeier et Lambe, 2007] s’interesse egalement rapidement a la comparaison enter le χ2

et le gain d’information, mais sans obtenir de resultat probant.TODO

Detailler plus ?

2.4 Critere du χ2 et gain d’information

Le seul article presentant des resultats a priori interessants sur le sujet de la comparai-son entre le χ2 et le gain d’information est [Raileanu et Stoffel, 2004]. Cet article, completepar la these de Raileanu ([Raileanu, 2002]) affirme que, pour toutes les bases entre 50 et 200echantillons, il n’y a jamais plus de 2% de cas ou les deux criteres classent les variables dansun ordre different (pour un probleme de classification binaire, ou chaque donnee est decrite pardeux variables binaires).

Ces deux articles restent cependant peu satisfaisant :– l’etude commence par une gigantesque disjonction de cas pour determiner quels sont les

cas ou les criteres sont en desaccord, dans le but d’eviter d’avoir a calculer explicitementles valeurs des criteres, mais sans expliquer pour cette disjonction est plus simple ou plusinteressant qu’un calcul direct (voir la figure ) ;

– l’article dit clairement «toutes les bases entre 50 et 200 echantillons», alors qu’un calculelementaire de combinatoire montre qu’il n’est pas realiste de faire une etude exhaustive.Il y a donc eu un echantillonnage a un moment donne, mais aucune information n’est surce sujet ;

– des bases de seulement 50 a 200 echantillons sont vraiment tres petites. Certaines basesutilisees avec des arbres de decision contiennent plusieurs milliers ou dizaines de milliersd’individus.

9

CHAPITRE 2. POINTS DE DEPART

0

1 2 3 4 5 6

1a 1b 1c 1d 1e 3a 3b 3c 4 a 4b 4 c 4d 4 e 5a 5b 5c 6a 6b 6c

1bi 1bii 1ci 1cii 1di 1dii

Fig. 2.1 – La disjonction de cas de [Raileanu, 2002]

10

Chapitre 3

Comparaison entre χ2 et et gaind’information

3.1 Cadre des simulations

3.1.1 Presentation

Nous n’utiliserons pas de donnees reelles de facon a pouvoir manipuler tous les parametresen fonction des besoins de nos experiences. Nous nous limiterons au cas le plus simple (et aussile seul etudie dans la litterature pour l’instant) : un probleme de classification binaire, sur desdonnees decrites par deux variables, elles-memes binaires.

Comme notre objectif est de determiner si les deux criteres classent les deux variables dansle meme ordre, il est possible d’«oublier» completement la partie «arbre» et de se concentrerseulement sur les valeurs des criteres de decisions.

Dans un premier temps, nous considererons que tous les parametres prennent leurs valeursdans R au lieu d’evoluer dans un ensemble discret, dont la taille est determine par le nombrereel d’echantillons. Tout se passe comme si on disposait d’un nombre infini d’echantillons. Nousverrons dans la partie 3.3 que cette approximation est valide pour des bases d’une taille dequelques milliers d’individus, ce qui correspond a beaucoup de bases reelles.

La distribution des donnees simulees sera decrite par les tableaux de contingence detaillesdans la partie 3.1.2. Dans un premier temps, nous etudierons la repartition des cas de desaccorda l’interieur de l’espace des parametres (partie 3.2.1), puis nous nous interesserons a la surfacede la zone de desaccord (partie 3.2.2). La derniere serie d’experience examine le cas ou le nombred’echantillons est fini (partie 3.3).

En plus de ces experiences, nous allons etudier formellement la forme de la surface dedesaccord (3.2.3) puis modeliser l’echantillonage d’une population pour evaluer la probabilited’un desaccord entre critere.

3.1.2 Donnees

On s’interesse a des donnees reparties en deux classes (notee Y ). Chaque instance est decritepar deux variables binaires X1 et X2. La distribution de ces donnees est decrite par les deuxtableaux de contingence suivant, utilisant des frequence relative (puisque nous n’avons pas denotion de nombre d’individus) :

11

CHAPITRE 3. COMPARAISON ENTRE χ2 ET ET GAIN D’INFORMATION

– Pour X1

X1

0 1

Y0 x1 b− x1 b1 a1 − x1 1− a1 − b+ x1 1− b

a1 1− a1 1

– Pour X2

X2

0 1

Y0 x2 b− x2 b1 a2 − x2 1− a2 − b+ x2 1− b

a2 1− a2 1

3.1.3 Critere de separation

Le choix de separer le jeu de donnees suivant X1 ou X2 sera determinee en utilisant les deuxcriteres suivants (exprimes ici dans le cas de deux variables binaires) :

– le χ2

χ2(X) = (x− ab) 1 + ab

ab(1− a)(1− b)– et le gain d’information

IG(X) = x log2

( xab

)+ (b− x) log2

(b− xb(1− a)

)+ (a− x) log2

(a− x

(1− b)a

)+(x− a− b+ 1) log2

(x− a− b+ 1(1− a)(1− b)

)Le critere du χ2 (respectivement du gain d’information) choisit la variable X1 si χ2(X1) >

χ2(X2) (respectivement si IG(X1) > IG(X2)).Pour determiner si les deux criteres choisissent la meme variable, il suffit donc d’etudier le

signe du produit :

(χ2(X1)− χ2(X2))(IG(X1)− IG(X2))

Les deux criteres seront en desaccord si cette quantite est negative.

3.2 Desaccords entre criteres

3.2.1 Zone de desaccord

On va etudier la zone de desaccord en fonction des parametres x1 et x2, avec des margesdonnees (a1, a2 et b fixes).

Le trace correspond a la fonction :

f : (x1, x2)→ (χ2(X1)− χ2(X2))(IG(X1)− IG(X2))

Cette fonction est evaluee sur une grille reguliere de 1000×1000 points pris dans [0,min(a1, b)]×[0,min(a2, b)] et la zone d’equation f(x1, x2) ≤ 0 est affichee (en blanc) sur le trace de la surface.

L’aire de la zone de desaccord (l’ensemble des couples (x1, x2) tels que f(x1, x2) < 0) estevaluee en comptant le nombre de points ou la fonction f prend des valeurs negatives. Elle esttracee en blanc sur les graphes suivants et sa valeur est indiquee en pourcentage.

12

CHAPITRE 3. COMPARAISON ENTRE χ2 ET ET GAIN D’INFORMATION

Cas a1 = a2

Premiere serie d’experiences pour a1 = a2 = 0.1 et b compris entre 0.1 et 0.5 (par pas de0.01) : figures 3.2 et 3.5.

Observations : Tous les points de desaccord sont regroupe dans une zone delimitee en baspar une droite et en haut par une courbe (les equations de ces courbes sont etudiees en 3.2.3).Lorsque b augmente, la zone de desaccord se rapproche de la diagonale x2 = a1 − x1. Lors dece deplacement, l’aire de la zone commence par augmenter pour atteindre un maximum versb = 0.35 puis diminue quand b devient tres proche de 0.5.

Les deux courbes qui limitent la zone de desaccord se rejoignent au point d’independance(x1 = x2 = aib, illustre sur la figure 3.6).

Remarque Les courbes precedentes sont assez reguliere (la forme de la zone de desaccordest toujours la meme, seule sa position et sa surface change). On peut donc les resumer seulementpar la surface de la zone de desaccord sans perdre trop d’information.

Fig. 3.1 – Independance pour a1 = a2

Cas a1 6= a2

Premiere serie d’experiences pour a1 = 0.15 et a2 = 0.45 et b toujours compris entre 0.1 et0.5 (par pas de 0.01) : figures 3.7 et 3.10.

13

CHAPITRE 3. COMPARAISON ENTRE χ2 ET ET GAIN D’INFORMATION

Fig. 3.2 – Zone de desaccord pour a1 = a2 = 0.1 (partie 1)

14

CHAPITRE 3. COMPARAISON ENTRE χ2 ET ET GAIN D’INFORMATION

Fig. 3.3 – Zone de desaccord pour a1 = a2 = 0.1 (partie 2)

15

CHAPITRE 3. COMPARAISON ENTRE χ2 ET ET GAIN D’INFORMATION

Fig. 3.4 – Zone de desaccord pour a1 = a2 = 0.1 (partie 3)

16

CHAPITRE 3. COMPARAISON ENTRE χ2 ET ET GAIN D’INFORMATION

Fig. 3.5 – Zone de desaccord pour a1 = a2 = 0.1 (partie 4)

17

CHAPITRE 3. COMPARAISON ENTRE χ2 ET ET GAIN D’INFORMATION

Observations : Ici les points de desaccord sont repartis en deux zones, une qui correspond acelle du cas precedent, et une autre orientee perpendiculairement a la premiere. Ces deux zonesse croisent encore au point d’independance (xi = aib, illustre sur la figure ??).

Les valeurs sont deux fois plus elevees que dans le cas a1 = a2 : on se rend compteimmediatement que l’on depasse largement la limite des 2% annonces par [Raileanu et Stoffel, 2004],jusqu’a atteindre 5%.

Fig. 3.6 – Independance pour a1 6= a2

3.2.2 Aire de la zone de desaccord

Les experiences precedentes se sont faites pour a1, a2 et b fixes. Pour faciliter l’explorationde cet espace de parametres, on va s’interesser uniquement a l’aire de la zone de desaccord, defacon a s’abstraire des variations de x1 et de x2. La remarque faite plus haut sur la regularitedes courbes justifie ce choix : connaıtre seulement la valeur de l’aire nous donne une idee assezbonne de la courbe de depart.

On trace donc la surface :

g : (a1, a2)→ aire{(x1, x2)|f(x1, x2) < 0}

Cette fonction est evaluee sur une grille reguliere de 100× 100 points de [0.1, 0.5]× [0.1, 0.5]avec b compris entre 0.1 et 0.5, par pas de 0.01.

L’aire est estimee en comptant de le nombre de points ou la courbe prend des valeursnegatives sur la surface [0.1,min(a1, b)]× [0.1,min(a2, b)] (toujours echantillonnee sur une grillereguliere de 1000× 1000 points) et est donnee en pourcentage de cette surface.

18

CHAPITRE 3. COMPARAISON ENTRE χ2 ET ET GAIN D’INFORMATION

Fig. 3.7 – Zone de desaccord pour a1 = 0.15 et a2 = 0.35 (partie 1)

19

CHAPITRE 3. COMPARAISON ENTRE χ2 ET ET GAIN D’INFORMATION

Fig. 3.8 – Zone de desaccord pour a1 = 0.15 et a2 = 0.35 (partie 2)

20

CHAPITRE 3. COMPARAISON ENTRE χ2 ET ET GAIN D’INFORMATION

Fig. 3.9 – Zone de desaccord pour a1 = 0.15 et a2 = 0.35 (partie 3)

21

CHAPITRE 3. COMPARAISON ENTRE χ2 ET ET GAIN D’INFORMATION

Fig. 3.10 – Zone de desaccord pour a1 = 0.15 et a2 = 0.35 (partie 4)

22

CHAPITRE 3. COMPARAISON ENTRE χ2 ET ET GAIN D’INFORMATION

Puisque [Raileanu et Stoffel, 2004] affirme qu’il n’y a jamais plus de 2% de cas de divergence,on ne devrait observer aucune valeur superieure a 2% dans les graphiques qui suivent. Pourmieux voir ce qui se passe, la courbe d’equation aire(a1, a2) est tracee en blanc.TODO

enlever les Narea et les Ndiff

Observations : Les points ou l’aire depasse 2% ne sont pas du tout isoles, en fait seule la zoneproche de la diagonale a1 = a2 possede des valeurs inferieures a 2%. Quand on se rapprochede b = 0.5, toutes les aires tendent vers des valeurs faibles (inferieurs a 2%), ce qui rejointl’observation faite en 3.2.1.

3.2.3 Etude formelle

On s’interesse a la frontiere de la zone de desaccord, c’est a dire, aux points (x1, x2) telsque :

(χ2(X1)− χ2(X1))(IG(X1)− IG(X2)) = 0

Il faut donc resoudre les deux equations suivantes :

χ2(X1)− χ2(X1) = 0 (3.1)

et

IG(X1)− IG(X2) = 0 (3.2)

Equation 3.1

C’est une equation facile, et Maple nous donne directement les solutions suivantes :

Cas a1 = a2 = a

x2 = 2 ab− x1

⇔ x1 − ab = − (x2 − ab)

et

x2 = x1

La premiere equation correspond a la droite qui apparaıt sur les figures. Les deux variabless’eloignent de l’independance de la meme maniere, mais en sens oppose.

La deuxieme, a la zone ou les deux variables sont strictement equivalentes : croisees avec Y,elles donnent les memes tableaux de contingence.

Cas a1 6= a2

x2 =

−a22b2a1 − a1ba2 + a2ba1

2 + a12b2a2

2 +√a2 (−1 + a2) a1 (a1 − 1) (b2a1a2 + a1b+ a2b+ 1) (−x1 + a1b)

2

a1 (−a2b− 1 + a1 + a1ba2)

x2 =

23

CHAPITRE 3. COMPARAISON ENTRE χ2 ET ET GAIN D’INFORMATION

Fig. 3.11 – Aire de la zone de desaccord en fonction de a1 et a2 (partie 1)

24

CHAPITRE 3. COMPARAISON ENTRE χ2 ET ET GAIN D’INFORMATION

Fig. 3.12 – Aire de la zone de desaccord en fonction de a1 et a2 (partie 2)

25

CHAPITRE 3. COMPARAISON ENTRE χ2 ET ET GAIN D’INFORMATION

−a22b2a1 − a1ba2 + a2ba1

2 + a12b2a2

2 −√a2 (−1 + a2) a1 (a1 − 1) (b2a1a2 + a1b+ a2b+ 1) (−x1 + a1b)

2

a1 (−a2b− 1 + a1 + a1ba2)

Ici, les deux solutions sont des frontieres des deux zones d’inversion qu’on remarque sur lesfigures

Equation 3.2

Ce cas est beaucoup plus complique a resoudre de facon exacte, Maple n’obtient rien d’ex-ploitable.

Une possibilite est d’utiliser un developpement limite et de chercher une approximation dela solution.

On va faire le developpement limite au point d’independance : xind = ab (figure 3.6).A l’ordre 3, on obtient les solutions suivantes.

x2 = x1

On retrouve la droite x2 = x1 : une annulation, mais sans zone d’inversion.L’autre solution est inexploitable car trop compliquee et manquant de precision (c’est une

droite).Des l’ordre 4, on obtient une formule extremement longue, totalement inexploitable et dont

l’enonce ici prendrait plusieurs pages.

3.3 Cas discret

TODOrajouter des titres sur les axes

3.3.1 Presentation

Toutes les experiences precedentes supposent qu’on dispose d’une quantite infinie d’echantillonset que donc les grandeurs etudiees varient continuement. Pour etudier la validite de cette hy-

26

CHAPITRE 3. COMPARAISON ENTRE χ2 ET ET GAIN D’INFORMATION

pothese, nous avons traces la courbe de l’aire de la zone de desaccord (exprimee en pourcentagede la surface totale) en fonction du nombre d’echantillons de la base (pour a1, a2 et b fixes).TODO

dessin courbes de desaccord avec grille pour montrer qu’on peut ne pas tomber dans la zoneblanche

Remarque Les valeurs representees sur les courbes correspondent a l’aire des zones traceesen blanc sur les courbes des parties 3.2.1 et 3.2.2.

Il y a eu trois series d’experiences, pour des plages de nombre d’echantillons differentes :– l’etude la plus large : des bases de 1000 a 10000 echantillons (par pas de 100). On part de

bases assez petites a des bases tres grosses ;– une etude plus fine pour de petites bases : entre 100 et 1000 echantillons (par pas de 10) ;– enfin, une etude sur les memes tailles de bases sur Raileanu : entre 50 et 200 echantillons.

Ce qui correspond a des bases vraiment tres petites.

Parametres Puisqu’on manipule desormais des nombres d’echantillons plutot que des frequencesrelatives, les parametres devraient etre des nombres d’echantillons. Cependant, comme nousallons faire varier le nombre d’echantillons total, il est necessaire de continuer a utiliser desfrequences relatives qui seront ensuite multipliees par le nombre d’echantillon.

Pour chacune des series d’experiences, les valeurs utilisees sont les suivantes :– b varie entre 0.1 et 0.4 par pas de 0.1,– a1 varie entre 0.1 et 0.4 par pas de 0.05,– a2 varie entre 0.1 et 0.4 par pas de 0.05.

3.3.2 Observations

Entre 1000 et 10000 echantillons

La figure 3.14 est un exemple assez representatif des courbes qu’on obtient : la plupart ontune allure en 1−e−x (figure 3.15). La courbe converge assez rapidement vers une asymptote quicorrespond a la valeur obtenue avec l’approximation continue. Dans les pires cas, l’asymptoteest pratiquement atteinte a partir de 4000 echantillons mais en general, celle-ci est atteinte des2000 echantillons.

En fait, de rares courbes nous indiquent que l’allure en 1 − e−x est trompeuse et n’est duqu’au pas choisi pour l’echantillonnage (100 echantillons ici) : on voit nettement des oscillationssur la figure 3.16. La serie d’experience, concentree sur la fenetre [100, 1000] avec un pas de 10echantillons va nous permettre de confirmer cette observation.

Comme on l’avait vu lors des experiences 3.2.1, l’ordonnee de l’asymptote n’est absolumentpas bornee par 2%.

Entre 100 et 1000 echantillons

On voit maintenant que les courbes de cette serie d’experiences (par exemple 3.17) ont uneallure en e−x sin(x) (figure ??). De plus la periode est tres inferieure aux 100 echantillons choisisprecedemment, ce qui explique ce que ce phenomene soit passe pratiquement inapercu dans lesexperiences precedentes.

Non seulement, l’asymptote ne passe pas aux 2%, mais les oscillations observees contredisentl’idee qu’il n’y jamais plus de 2% de desaccord.

27

CHAPITRE 3. COMPARAISON ENTRE χ2 ET ET GAIN D’INFORMATION

Fig. 3.13 – Aire de la zone de desaccord en fonction de a1 et a2 (partie 3)

Fig. 3.14 – Entre 1000 et 10000 echantillons, pour b = 0.4, a1 = 0.15, a2 = 0.3

28

CHAPITRE 3. COMPARAISON ENTRE χ2 ET ET GAIN D’INFORMATION

Fig. 3.15 – Allure des courbes entre 1000 et 10000 echantillons

Entre 50 et 200 echantillons

C’est la serie d’experiences la plus interessantes pour realiser une comparaison avec lesresultats de [Raileanu et Stoffel, 2004] et [Raileanu, 2002] (pas plus de 2% de desaccord surtoutes les bases entre 50 et 200 echantillons). Ici, nous n’avons bien sur pas explore de facon ex-haustive toutes les bases possibles, mais nous avons realise un echantillonnage assez representatifde la situation. La figure [?] nous montre un exemple de cas ou la fameuse valeur des 2% n’in-tervient pas du tout : des oscillations centrees autour de 4% et qui semblent confinees sur unebande entre 3 et 4%. Toutes les courbes ne sont pas centrees sur la meme valeur mais nous nevoyons toujours pas de justification a cette borne des 2% evoquee par Raileanu.

3.3.3 Conclusion

Encore une fois, nous n’avons trouve aucun argument qui permette d’etayer la these deRaileanu. Par contre, le phenomene des oscillations est une decouverte inedite. Meme si lesetudes experimentales de [Mingers, 1989] et [Buntine et Niblett, 1992] ont montrees que le choixdu critere etait en pratique peu important, il est possible que ce choix est une influence dansles systeme d’apprentissage ou l’on reduit la quantite de donnees utilisees pour la constructionde l’arbre, de facon a accelerer la phase d’apprentissage ([Chauchat et Rakotomalala, 1999].En pratique, on passe de quelques milliers d’individus a quelques centaines (3.20), soit unetransition entre le regime stationnaire vu sur la courbe 3.14 et le regime transitoire avec lesoscillations vues sur la courbe de la courbe 3.17.

3.4 Modelisation

3.4.1 Presentation

L’echantillonnage est une etape qui intervient systematiquement en apprentissage : que cesoit au moment de passer de la distribution reelle a la distribution observee, utilisable pour l’ap-prentissage, au moment de passer des donnees observees aux donnees utilisees pour apprendrele modele (puisque qu’on en retire une partie pour la phase de validation) ou au moment depasser de la base d’apprentissage complete a une base de petite taille (pour reduire la dureede l’apprentissage, en esperant que la qualite du modele ainsi construit sera la meme que celleobtenue avec le modele complet).

29

CHAPITRE 3. COMPARAISON ENTRE χ2 ET ET GAIN D’INFORMATION

Fig. 3.16 – Entre 1000 et 10000 echantillons, pour b = 0.1, a1 = 0.15, a2 = 0.3

Fig. 3.17 – Entre 10 et 1000 echantillons, pour b = 0.4, a1 = 0.35, a2 = 0.25

30

CHAPITRE 3. COMPARAISON ENTRE χ2 ET ET GAIN D’INFORMATION

Fig. 3.18 – Allure des courbes entre 100 et 1000 echantillons

L’etude suivante peut s’appliquer a tous ces cas : on dispose d’une distribution de depart pourlaquelle on fait l’hypothese que les deux variables sont equivalente et on aimerait determiner laprobabilite que les deux criteres ne choisissent pas la meme variable.

3.4.2 Observations

On suppose que la distribution complete est decrite par les tables de contingence suivantes :– Pour X1

X1

0 1

Y0 X1 B −X1 B1 A1 −X1 N −A1 −B +X1 N −B

A1 N −A1 N

– et pour X2

X2

0 1

Y0 X2 B −X2 B1 A2 −X2 N −A2 −B +X2 N −B

A2 N −A2 N

Parmi ces N elements, on fait un tirage aleatoire de n observations, on obtient alors ladistribution decrite en 3.1.2.

3.4.3 Loi hypergeometrique

La probabilite d’avoir b echantillons avec Y = 0 suit une loi hypergeometrique de parametres(n,B/N, N) (en effet, on tire sans remise n echantillons, parmi N au total, et une fraction B

Nd’entre eux est telle que Y = 0).

Celle d’avoir a1 (respectivement a2) echantillons avec X1 = 0 (respectivement X2 = 0) suitune loi HG de parametres (n,A1/N, N) (respectivement (n,A2/N, N)).

Enfin celle d’avoir x1 (respectivement x2) echantillons avec X1 = 0 et Y = 0 (respectivementX2 = 0 et Y = 0) suit une loi HG de parametres (n,X1/N, N) (respectivement (n,X2/N, N)).

31

CHAPITRE 3. COMPARAISON ENTRE χ2 ET ET GAIN D’INFORMATION

On suppose que les deux variables X1 et X2 sont equivalentes (donc que X1 = X2 et queA1 = A2). On se demande quelle est alors la probabilite d’avoir une inversion lors du calcul duχ2 et du gain d’informations sur les observations.

3.4.4 Calcul

En se limitant au cas le plus simple, on va supposer dans un premier temps que les margesdes distributions echantillonnees sont egales pour les deux variables et donc que a1 = a2.Une condition suffisante pour que les deux criteres choisissent la meme variable est donc quex1 = x2. Dans ce cas, la probabilite de ne pas obtenir d’inversion est la probabilite que les deuxlois hyper-geometriques decrivant x1 et x2 prennent la meme valeur.

C’est un calcul que nous n’avons pas realise pour le moment et qui est probablement delicatpuisque nous n’avons pas trouve de reference a ce sujet.

32

CHAPITRE 3. COMPARAISON ENTRE χ2 ET ET GAIN D’INFORMATION

Fig. 3.19 – Entre 50 et 200, pour b = 0.4, a1 = 0.1, a2 = 0.4

Données réelles Données observées

10 000 éch.

Données d’apprentissage

~10 000 éch.

Données échantillonnées

~100 éch.

Fig. 3.20 – Processus d’echantillonnage des donnees

33

Conclusion

Surprises– Deux zones de desaccord si a1 6= a2

– L’article de Raileanu n’est pas tres interessant meme s’il est beaucoup cite– Oscillations dans le cas discret

Perspectives– Cas discret et echantillonnage– Probabilite d’etre en desaccord sachant que les deux variables sont equivalentes

TODOrediger

Remerciements :

34

Bibliographie

[Benzecri, 1982] Benzecri, J.-P. (1982). L’analyse des donnees.

[Breiman, 1984] Breiman, L. (1984). Classification and Regression Trees. Chapman &Hall/CRC.

[Breiman, 2001] Breiman, L. (2001). Random forests. In Machine Learning, pages 5–32.

[Buntine et Niblett, 1992] Buntine, W. et Niblett, T. (1992). A further comparison of split-ting rules for decision-tree induction. Machine Learning, 8(1):75–85.

[Chauchat et Rakotomalala, 1999] Chauchat, J. et Rakotomalala, R. (1999). Elementsstatistiques pour determiner la taille des echantillons dans la construction des graphes d’in-duction. In SFC99 Nancy.

[Grabmeier et Lambe, 2007] Grabmeier, J. et Lambe, L. (2007). Decision trees for binaryclassification variables grow equally with the Gini impurity measure and Pearson’s chi-squaretest. International Journal of Business Intelligence and Data Mining, 2(2):213–226.

[Kass, 1980] Kass, G. V. (1980). An exploratory technique for investigating large quantities ofcategorical data. Journal of Applied Statistics, 29(2):119–127.

[Mingers, 1989] Mingers, J. (1989). An empirical comparison of selection measures fordecision-tree induction. Machine Learning, 3(4):319–342.

[Morgan et Sonquist, 1963] Morgan, J. et Sonquist, J. (1963). Problems in the analysis ofsurvey data, and a proposal. Journal of the American Statistical Association.

[Quinlan, 1986] Quinlan, J. R. (1986). Induction of decision trees. Mach. Learn., 1(1):81–106.

[Quinlan, 1993] Quinlan, J. R. (1993). C4.5 : programs for machine learning. Morgan Kauf-mann Publishers Inc., San Francisco, CA, USA.

[Raileanu, 2002] Raileanu, L. (2002). Formalization and comparison of split criteria for deci-sion trees. Neuchatel.

[Raileanu et Stoffel, 2004] Raileanu, L. et Stoffel, K. (2004). Theoretical comparison bet-ween the gini index and information gain criteria. Annals of Mathematics and ArtificialIntelligence, 41(1):77–93.

[Rakotomala, 2008] Rakotomala, R. (2008). Arbres de decisions - introduction. UniversiteLyon 2 — Cours de Data Mining.

[Rakotomalala, 2005] Rakotomalala, R. (2005). Arbres de decision. MODULAD.

35

Table des figures

1.1 Exemple d’arbre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

2.1 La disjonction de cas de [Raileanu, 2002] . . . . . . . . . . . . . . . . . . . . . . . 10

3.1 Independance pour a1 = a2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133.2 Zone de desaccord pour a1 = a2 = 0.1 (partie 1) . . . . . . . . . . . . . . . . . . . 143.3 Zone de desaccord pour a1 = a2 = 0.1 (partie 2) . . . . . . . . . . . . . . . . . . . 153.4 Zone de desaccord pour a1 = a2 = 0.1 (partie 3) . . . . . . . . . . . . . . . . . . . 163.5 Zone de desaccord pour a1 = a2 = 0.1 (partie 4) . . . . . . . . . . . . . . . . . . . 173.6 Independance pour a1 6= a2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183.7 Zone de desaccord pour a1 = 0.15 et a2 = 0.35 (partie 1) . . . . . . . . . . . . . . 193.8 Zone de desaccord pour a1 = 0.15 et a2 = 0.35 (partie 2) . . . . . . . . . . . . . . 203.9 Zone de desaccord pour a1 = 0.15 et a2 = 0.35 (partie 3) . . . . . . . . . . . . . . 213.10 Zone de desaccord pour a1 = 0.15 et a2 = 0.35 (partie 4) . . . . . . . . . . . . . . 223.11 Aire de la zone de desaccord en fonction de a1 et a2 (partie 1) . . . . . . . . . . . 243.12 Aire de la zone de desaccord en fonction de a1 et a2 (partie 2) . . . . . . . . . . . 253.13 Aire de la zone de desaccord en fonction de a1 et a2 (partie 3) . . . . . . . . . . . 283.14 Entre 1000 et 10000 echantillons, pour b = 0.4, a1 = 0.15, a2 = 0.3 . . . . . . . . 283.15 Allure des courbes entre 1000 et 10000 echantillons . . . . . . . . . . . . . . . . . 293.16 Entre 1000 et 10000 echantillons, pour b = 0.1, a1 = 0.15, a2 = 0.3 . . . . . . . . 303.17 Entre 10 et 1000 echantillons, pour b = 0.4, a1 = 0.35, a2 = 0.25 . . . . . . . . . 303.18 Allure des courbes entre 100 et 1000 echantillons . . . . . . . . . . . . . . . . . . 313.19 Entre 50 et 200, pour b = 0.4, a1 = 0.1, a2 = 0.4 . . . . . . . . . . . . . . . . . . 333.20 Processus d’echantillonnage des donnees . . . . . . . . . . . . . . . . . . . . . . . 33

36