Les arbres de décisions

Ce cours a pour objectif de vous apprendre (ou de vous rappeler si vous connaissez déjà) comment générer un arbre de décision avec les algorithmes ID3 et C4.5 inventés par Ross Quinlan dans les années 1980 et 1990. Je vous montrerai le principe de ces algorithmes et leur utilité à l’aide d’un exemple (celui utilisé par Quinlan lui-même), et je vous montrerai également les pseudo-codes pour pouvoir vous laisser la possibilité de les implémenter, ce que je vous accompagnerai à faire en Python3.

Pour comprendre les points de théorie traités, il est nécessaire de savoir manipuler l’indice sommatoire ($\sum$), les logarithmes (et exponentielles). Il faut également être à l’aise avec la notion d’ensembles et de sous-ensembles et bien sûr la notion d’arbre informatique (commencer par les arbres binaires, puis les arbres n-aires puis les arbres quelconques pour ceux ne connaissant pas cette notion).

Si vous arrivez à la fin, vous aurez un moyen infaillible de gagner au Qui est-ce ?, c’est moi qui vous le dis ! Mais il vous faut bien entendu arriver jusqu’à la conclusion Vous verrez que le Qui est-ce ? est un exemple qui s’applique très bien à ce que nous allons accomplir.

Comprendre le concept

Une première version : ID3

Une amélioration : C 4.5

1. Sources :

[1] SCHAPIRE R, Theoretical Machine Learning [Document électronique], http://www.cs.princeton.edu/courses/archive/spr08/cos511/scribe_notes/0204.pdf

[2] QUINLAN R, Induction of Decision Trees, Machine Learning, 1986

[3] QUINLAN R, C4.5 programs for machine learning, Kaufmann, 1993

[4] Lecture slides for textbook Machine Learning, Tom M. Mitchell, McGraw Hill, 1997, http://www.cs.cmu.edu/afs/cs/project/theo-20/www/mlbook/ch3.pdf

2. Liens

Pour aller plus loin, voici quelques liens sur le machine learning et l’intelligence artificielle en général :

DE LESPINAY JP, Conscience artificielle et robotique : fin de l’évolution humaine ! [Document électronique], http://www.automatesintelligents.com/echanges/2009/mar/conscienceartificielle.pdf
GANASCIA JG, L’Intelligence Artificielle, Paris, Le Cavalier Bleu, 2007, coll. "idées reçues".
RUSSEL R, NORVIG P, Intelligence Artificielle, Paris, Pearson, 2010, coll. "Pearson Education"¹
POTTER S, What AI can get from neurosciences [Document électronique], https://neurolab.gatech.edu/wp/wp-content/uploads/potter/publications/Potter-NeuroscienceForAIchapter.pdf
POTTER S, Neuroingineering : Neuroscience – APPLIED [Vidéo d’un séminaire datant du 19 octobre 2012], www.youtube.com

Comme promis, voici le dataset qui vous permet de faire fonctionner l’arbre ID3 sur les données du Qui est-ce ?. Je vous le donne uniquement parce que je m’étais beaucoup amusé à tricher contre ma petite soeur qui ne comprenait pas comment je faisais pour gagner sans même regarder la plaque . Le voici donc :

sexe couleur_pilosite est_euro couleur_yeux lunettes chapeau chauve moustache barbe
g noir non brun non non non non non frank
f marron oui brun non non non non non holly
g blond oui brun non non non oui non hans
g roux oui bleu non non non oui non alfred
f roux oui brun oui oui non non non sarah
g marron oui brun non oui non non non bernard
g roux oui brun non non oui non non herman
f blanc oui bleu oui non non non non betty
g roux oui brun non non oui non oui bill
g roux oui brun non non non non non frederick
g blanc oui brun non non non non non victor
g blanc oui brun oui non oui oui non charles
g blanc oui brun oui non non non non paul
g blond oui brun non non non oui oui luk
g marron oui bleu non non non non non robert
g blond oui brun non oui non non non eric
f marron oui brun non oui non non non maria
g blanc oui brun non oui non non non joe
g noir oui bleu oui non oui non non albert
g noir non brun non non non non oui mario
g noir non brun non non non oui non max
f blond oui bleu non non non non non anita
f noir non brun oui non non non non sally
g marron oui brun non non oui oui oui roger