Comment créer un arbre de décision avec les algorithmes ID3 et CART...

Les arbres de décision nous questionnent afin de déterminer une action à réaliser ou une catégorie d’appartenance d’un objet que nous interrogeons. Lors d’un précédent article, nous avons vu comment ils étaient composés et dans quel domaine, nous pouvions les utiliser. Dans cet article, nous allons nous intéresser à la conception d’un arbre de décision. Plus précisément, nous verrons les algorithmes qui nous permette de réaliser un arbre de décision.

Algorithme ID3 (Iterative Dichotomiser 3)

Nous avons à notre disposition un ensemble d’éléments contenant plusieurs caractéristiques. Notre objectif va être de déterminer nos questions à partir de ces caractéristiques. Ainsi, nous allons dans un premier temps déterminer la première question à poser. Pour ce faire, nous allons chercher à déterminer l’attribut qui sépare le mieux nos données. Une fois cette question obtenue, nous allons avoir un ensemble de réponses. Il nous suffira de répéter cette opération afin d’arrivée dans un état final. Ce type d’approche est une approche du haut vers le bas (Top-Down). En effet, nous partons de l’ensemble de nos données afin d’arrivée à un ensemble de sous-ensemble.

Afin de déterminer le meilleur attribut pour pouvoir poser notre question, nous allons utiliser, avec l’algorithme ID3, l’attribut ayant le gain d’information basé sur l’entropie le plus élevé. Pour cela, nous allons, à partir de nos données, calculer l’entropie qui caractérise le degré de désorganisation de nos données. Pour visualiser cela, on peut imaginer une chambre d’un étudiant qui est mal ranger. Ainsi, cette chambre aura une entropie élevée. Le calcul de l’entropie va nous permettre de savoir quel attribut nous allons sélectionner afin de poser notre question dans le nœud de notre arbre. Ainsi, nous sélectionnerons l’attribut ayant une entropie la plus importante, car cela signifie que l’attribut en question possède différentes catégories. En revanche, un attribut avec une entropie faible signifie qu’il y a peu d’éléments différents. Enfin, une entropie nulle signifie que tous les éléments sont de la même catégorie.

Calcul de l’entropie - Entropie de Shannon

Nous avons :

S : L’ensemble des données actuelles, où nous souhaitons calculer l’entropie.
C : l’ensemble des classes de S. Ici : {“oui”, “non”}
p(c) : La proportion du nombre d’éléments appartenant à une classe c par rapport à l’ensemble des éléments présents dans S.

Note : Quand nous avons H(S) = 0, cela signifie que tous nos éléments appartiennent à la même catégorie.

Calcul du gain d’information

Le gain d’information (Information Gain - IG), mesure la différence d’entropie entre ce que nous avions de base et par rapport à ce que nous avons obtenus lorsque nous avons séparé notre ensemble par l’attribut A. En d’autres termes, nous cherchons à savoir de combien le gain d’information a-t-il était réduit dans S lorsque nous avons séparé nos données avec l’attribut A.

Avec :

H(S) : L’entropie de notre ensemble de données S.
T : Le sous ensemble crée à partir de S que nous avons séparé avec l’attribut A. Ainsi, si nous faisons l’union de tous les sous-ensembles créer, nous obtenons S. Mathématiquement, nous avons :

p(t) : La proportion d’un nombre d’éléments dans t par rapport au nombre d’éléments dans l’ensemble S.
H(t) : L’entropie du sous-ensemble t.

Fonctionnement de l’algorithme ID3

Calculer l’entropie pour chaque ensemble de données.
Pour chaque attribut :
- Calculer l’entropie pour toutes les catégories.
- Prendre la moyenne de l’information de l’entropie pour l’actuel attribut.
- Calculer le gain pour l’attribut courant.
Prendre le plus grand gain d’attribut .
Répéter cela dans les sous-arbres jusqu’à ce que l’on obtienne l’arbre désiré.

Un peu de pratique

Nous avons vu tous les principes nécessaires afin de fabriquer notre arbre de décision. Afin d’illustrer tous cela, nous allons réaliser un exemple d’application qui nous permettra d’avoir une meilleure compréhension du fonctionnement de notre algorithme. Dans notre exemple, nous avons créé un tableau nous indiquant si un enfant joue dehors ou non en fonction de différents paramètre.

Temps	Température	Vent	Jouer dehors
soleil	chaud	faux	oui
soleil	chaud	vrai	oui
pluit	froid	vrai	non
pluit	chaud	faux	oui
nuageux	froid	vrai	non

L’objectif va être de créer un arbre de décision à partir de ces informations. Pour cela, la première étape consiste à calculer l’entropie de notre ensemble de départs. Nous appliquons donc l’entropie de Shannon que nous avons vu précédemment pour chacune des résultats de jouer. Nous avons donc deux catégories : oui et non.

Maintenant, nous allons devoir, pour chaque attribut, calculer l’entropie et le gain d’information.

Calcul pour le Temps

Calcul pour la Température

Calcul pour le Vent

Calcul du gain par rapport à nos données

Ici, nous allons sélectionner le gain le plus important. Nous pouvons constater que c’est la température.

Temps	Température	Vent	Jouer dehors
soleil	chaud	faux	oui
soleil	chaud	vrai	oui
pluit	froid	vrai	non
pluit	chaud	faux	oui
nuageux	froid	vrai	non

Comme nous pouvons le constater, l’ensemble de nos données sont bien séparer. En effet, dans les deux sous-arbres que nous obtenons, nous avons bien nos éléments appartenant à la même catégorie. Bien entendu, un œil averti aurait remarqué dès le début que nous pouvions séparer nos données en se basant sur l’attribut température. Cependant, cet exemple nous permet de mettre en pratique cet algorithme. Bien entendu, il se peut que vous construisiez des arbres de décision bien plus complexe. Ainsi, vous devrez renouveler cette étape, pour chaque sous-arbre que vous obtenez jusqu’à obtenir un arbre satisfaisait.

Algorithme CART (Classification And Regression Trees)

Afin de construire des arbres de décision, différents algorithmes existent. Nous allons maintenant nous pencher sur le cas de l’algorithme CART. Ce dernier utilise l’indice de Gini contrairement à l’algorithme ID3 qui utilise l’entropie.

Indice de Gini

Avec :

C : Ensemble des sous-ensembles. Dans notre cas, nous l’avons obtenu en séparant notre ensemble de bases par rapport à un attribut. Mathématiquement, nous avons :

p(c) : Proportion d’élément dans c par rapport au nombre d’éléments dans l’ensemble C.

Fonctionnement de l’algorithme Gini

Calcul de l’indice de Gini pour nos ensembles de données
Pour chaque attribut
- Calculer l’indice de Gini pour chaque catégorie
- Calculer le gain d’information en utilisant l’indice de Gini
Prendre l’attribut qui possède le meilleur gain d’information
Répéter cela dans les sous-arbres jusqu’à ce que l’on obtienne l’arbre désiré.

Cas d’application

Afin de pouvoir comprendre le fonctionnement de cet algorithme, nous allons réaliser cet algorithme sur un exemple comme nous l’avons fait pour l’algorithme ID3. Nous allons nous baser sur le même problème que précédemment, à savoir :

Temps	Température	Vent	Jouer dehors
soleil	chaud	faux	oui
soleil	chaud	vrai	oui
pluit	froid	vrai	non
pluit	chaud	faux	oui
nuageux	froid	vrai	non

La première étape consiste à calculer l’indice de Gini pour notre ensemble de données de base. Ainsi, nous allons avoir :

Nous allons, maintenant, pour chaque catégorie calculer le gain d’information en utilisant toujours l’indice de GINI.

Pour le temps

Pour la température

Pour le vent

Une fois que nous avons calculé pour chacun des attributs le gain d’information, nous allons sélectionner celui qui a la valeur la plus importante. Dans notre cas, c’est l’attribut pour la température. Et nous répétons cette opération jusqu’à obtenir un état final de notre arbre. Ici, c’est déjà le cas.

Élagage de l’arbre

L’arbre que nous venons de créer, à partir de nos données d’entraînements, correspond à un arbre qui a appris par cœur. Le problème, que nous pouvons rencontrer avec ce genre d’arbre, est qu’il a du mal à généraliser. De plus, il est fort probable que notre arbre contienne des branches complexes. C’est-à-dire, des branches qui nécessitent énormément de questions, qui ont été créer à cause d’une instance particulière. Or, il se peut que cette instance soit un cas particulier. Ainsi, notre objectif est d’obtenir un arbre qui généralise le plus possible. Nous voulons donc que notre arbre soit à la fois simple et concis.

Nous allons devoir modifier notre arbre afin de le simplifier. Pour ce faire, nous allons réaliser un élagage (prunning). Cela consiste à retirer des feuilles, voir des branches peu représentatives tous en cherchant à garder un arbre performant. L’une des premières possibilités serait de stopper la construction de l’arbre à partir d’un certain stade. En effet, on pourrait se dire qu’à partir d’un certain seuil, nous arrêtons la construction de notre arbre. Cependant, avec cette méthode, nous n’explorons pas l’ensemble des possibilités. De ce fait, il se peut que nous manquions des cas majeurs lors de la construction de notre arbre.

Sélectionner le meilleur sous-arbre

Une autre méthode d’élagage consiste à créer un ensemble d’arbres qui sont des sous-arbres de l’arbre final que nous avons. Puis, nous allons chercher à obtenir le meilleur arbre parmi notre ensemble d’arbres. Pour ce faire, nous allons tester notre arbre sur notre base de validation. L’arbre obtenant le meilleur score sera l’arbre que nous garderons. Cette approche est intéressante, cependant si notre arbre est conséquent, alors nous aurons du mal a tester toutes les possibilités possibles.

Supprimer certaines feuilles

Enfin, une autre possibilité serait de supprimer certaines feuilles et de mettre la classe majoritaire au nœud supérieur. Cela permet de simplifier notre arbre. Cependant, cette simplification ne doit pas se faire à l’extrême. En effet, il est préférable de le faire lorsque nous avons 100 instances identiques dans la sous-branche de gauche et 1 instance différente dans la sous-branche de droit. De plus, à trop vouloir généraliser, il se peut que nous omettons des cas particulier qui existent réellement. Cependant, c’est un compromis à faire permettant de rendre notre arbre plus simple et pus rapide.

Conclusion

Lors de cet article, nous avons vu deux algorithmes afin de créer des arbres de décision. Le premier est l’algorithme ID3 utilisant l’entropie. Le second est l’algorithme CART utilisant l’indice de GINI. Ces deux méthodes nous permettent de créer un arbre basé sur notre base d’apprentissage. Cet arbre peut parfois être complexe de part les cas parfois particuliers qui peuvent le composer. Afin d’éviter ce sur-apprentissage, nous pouvons élaguer notre arbre en le simplifiant. Cependant, nous devons faire des compromis et parfois perdre des questions qui peuvent être pertinente pour la réalisation d’une classification.