Licence CC BY-SA

Les arbres de décisions

Quand c'est l'ordinateur qui prend des décisions

Dernière mise à jour :

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

  1. Les origines
  2. État des lieux

Une première version : ID3

  1. L'algorithme ID3
  2. Une implémentation

Une amélioration : C 4.5

  1. L'algorithme C 4.5
  2. Manipuler les données manquantes
  3. Élagage de l'arbre


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 :

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 :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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


  1. La bible dans le domaine ! 

6 commentaires

Ouais il est là !

Un bon gros milliard de mercis à coma qui avait débuté la valid' a long long time ago et artagis qui s'en est occupé pour la seconde tentative. <3

PS : poupou ? nan jamais entendu parler :-°

Le hasard n'est que le nom donné à notre ignorance et n'existerait pas pour un être ominscient., Émile Borel

+0 -0

Mais non, boude pas le loup, merci énormément à Arius, à Aabu et à Vayel pour l'aide pendant la bêta ! (keur aussi <3)

Le hasard n'est que le nom donné à notre ignorance et n'existerait pas pour un être ominscient., Émile Borel

+1 -0
Vous devez être connecté pour pouvoir poster un message.
Connexion

Pas encore inscrit ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte