Arbre de décision (Apprentissage Automatique)

Source

Dans le domaine de l'apprentissage automatique, de nombreuses méthodes existent afin de pouvoir réaliser de la classification de données. Une des méthodes consiste à questionner notre donnée et à partir des réponses obtenues déterminer sa catégorie d'appartenance. Ainsi, dans cet article, nous allons voir le fonctionnement d'un arbre de décision.

Un arbre de décision est un arbre qui est composé d'un ensemble d'états. Chaque état est composé de branches qui mènent à d'autres états. L'objectif dans notre arbre de recherche est d'arriver à un état final, c'est-à-dire à un état qui ne possède plus de branches. Afin de choisir l'état que nous devons prendre, nous allons questionner notre donnée. En fonction de la réponse obtenue, nous prendrons la branche correspondant à notre réponse. Au final, nous allons obtenir un chemin nous indiquant au final la catégorie d'appartenance de notre donnée.

Illustration d’un arbre de décision.

Pour illustrer ce système, nous pouvons, par exemple, réaliser un système-expert de panne de voiture. Ainsi, lorsque nous aurons une voiture en panne, nous allons avoir une série de questions qui vont chercher à déterminer la panne de notre voiture. On pourrait imaginer une question du type "Est-ce que la voiture arrive à démarrer ?". En fonction de la réponse, deux cas de figure sont possibles. Un cas pour une réponse positive et un autre pour le cas d’une réponse négative. Puis, en fonction de la réponse, de nouvelles questions sont posées jusqu'à arrivée à l'étape finale nous indiquant le type de panne.

Composition d’un arbre de décision

Un arbre est constitué d'un ensemble d'états où chacun possède une question. Chaque état possède un ensemble de branches représentant les réponses possibles par rapport à la question. Le cas le plus fréquent est l'arbre binaire dans lequel seulement deux branches sont possibles pour chaque état. Nous appelons une feuille un état final de notre arbre, c'est-à-dire un état qui ne possédant pas de sous branche. Il nous indique l'élément recherché. Cela peut-être, par exemple, la catégorie d'appartenance ou bien l'action à prendre en fonction de notre donnée d'entrée.

Lors de la réalisation de notre arbre, nous devrons faire attention à la réalisation de nos questions. En effet, nous devons être suffisamment claires et simples afin de pouvoir répondre à cette dernière. En effet, une question trop abstraite ne pourra être répondue et on se retrouvera dans l'incapacité de continuer notre arbre de décision. De ce fait, on privilégiera les questions ayant comme réponse oui/non. Bien entendue, nous pouvons réaliser des intervalles prenant en compte tous les cas possibles. Cela peut-être le cas lorsque nous souhaitons avoir plusieurs cas pour, par exemple, la taille d’une personne. Nous pouvons donc avoir plusieurs réponses possibles comme une taille inférieure à 100 cm, une comprise entre 100 et 150 cm et une supérieure à 150 cm.

Problème d'apprentissage

Quand nous allons vouloir entraîner notre système, nous allons séparer nos données et avoir deux grandes bases. Une base d'entraînement et une base de validation. Concernant la base d'entraînement, c'est sur celle-ci que notre modèle va apprendre, c'est sur celle-ci que nous allons déterminer les questions de notre arbre. La base de validation va nous permettre, comme son nom l'indique, de valider notre système. Nous faisons cette séparation afin de vérifier que notre système a bien appris. L'objectif final pour nous va être d'obtenir un système qui est à la fois performant sur notre base d'entraînement et notre base de validation.

L'une des erreurs récurrentes avec les arbres de décision est d'obtenir un arbre très performant sur notre base d'entraînement, mais très mauvais sur notre base de validation. On appelle ce phénomène le sur-apprentissage. On définit cela par le fait que notre système a appris par cœur nos données d'entraînement. Cependant, avec cette méthode, notre système est performant uniquement sur les cas qu'il connaît. Lorsque notre système sera confronté à un nouveau cas, un cas qu'il n'a jamais vu, il ne pourra pas nous donner une réponse pertinente.

Cas d'application

Un arbre de décision peut être utilisé dans plusieurs domaines que ce soit pour de la prise de décision ou bien de la classification. Par exemple, nous pouvons utiliser notre arbre de décision afin de déterminer le salaire d'une personne en se basant sur de multiples informations comme son âge, son sexe, ses études... Ainsi, lorsque nous aurons une nouvelle personne, il nous suffira de parcourir notre arbre et nous pourrons avoir une idée de son salaire.

On retrouve aussi les arbres de décision dans des systèmes-experts comme pour le cas des voitures que nous avons illustré au tout début de notre article. Ce genre de système peut nous indiquer le type de panne, mais aussi les étapes pour la résolution de ce problème. Ainsi, nous pouvons utiliser les arbres de décision pour de la classification, mais aussi pour interagir avec notre environnement. De ce fait, nous pouvons déterminer des actions à réaliser en fonction des données présentes dans notre environnement.

Conclusion

Les arbres de décision sont une méthode d'apprentissage qui permettent de décomposer notre donnée en posant un ensemble de questions. En fonction des réponses obtenues, nous allons obtenir un chemin nous guidant vers la catégorie d'appartenance de notre donnée ou vers un choix. L'utilisation d'un arbre de décision est très intéressante, car il est facile à mettre en place et compréhensible. Il faudra seulement faire attention au problème de sur-apprentissage qui peut survenir.

Aller plus loin

http://fr.wikipedia.org/w/index.php?title=Arbre_de_d%C3%A9cision&oldid=153703146
https://www.rocq.inria.fr/axis/modulad/archives/numero-33/tutorial-rakotomalala-33/rakotomalala-33-tutorial.pdf
https://hackernoon.com/what-is-a-decision-tree-in-machine-learning-15ce51dc445d

Pour les programmer

https://scikit-learn.org/stable/modules/tree.html