Bermudes
Les arbres de d cisions
12 ao t 2019
0
Table des mati res
1. Comprendre le concept
1.1. Les origines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2. tat des lieux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2
2
5
2. Une premi re version : ID3
9
2.1. Lalgorithme ID3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9
2.2. Une impl mentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
Contenu masqu
3. Une am lioration : C 4.5
44
3.1. Lalgorithme C 4.5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
3.2. lagage de larbre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
Contenu masqu
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 laide dun
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.
((cid:80)), les logarithmes
Pour comprendre les points de th orie trait s, il est n cessaire de savoir manipuler lindice
sommatoire
). Il faut galement tre laise
avec la notion densembles et de sous-ensembles et bien s r la notion darbre informatique
(commencer par les arbres binaires, puis les arbres n-aires puis les arbres quelconques pour ceux
ne connaissant pas cette notion).
(et exponentielles
Si vous arrivez la fin, vous aurez un moyen infaillible de gagner au Qui est-ce ?
, cest 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 sapplique tr s bien ce que nous allons accomplir.
1
1. Comprendre le concept
Dans cette partie, nous allons voir la th orie r sidant derri re le machine learning et plus
pr cis ment les arbres de d cisions. Restez bien attentifs et nh sitez pas relire les passages
qui vous semblent compliqu s car il est videmment important de bien saisir ce qui est expliqu
ici pour pouvoir comprendre la suite.
1.1. Les origines
Je vais commencer par introduire tous les termes un peu compliqu s et les concepts qui vont
revenir tout au long de ce tutoriel.
###1. Mise en situation
Mettons-nous tout alors en situation, et laissez-moi vous exposer en quoi ce que je vous propose
est int ressant. Figurez-vous que jai un ami qui sappelle Ren et qui me demande sil peut
sinscrire au MIT. Alors comme vous pouvez vous en douter, ce nest pas moi qui d cide de qui
peut ou ne peut pas sinscrire dans cet tablissement r put . Je lui ai donc dit de se r f rer aux
responsables des inscriptions. Jusque l , vous vous demandez pourquoi je vous parle de notre
cher Ren et vous avez tout fait raison. Mais une petite minute, jy arrive.
Le MIT avait des probl mes financiers parce quil n cessitait des dizaines de personnes pr pos es
aux d cisions dinscriptions car ces derniers taient extr mement sollicit s et quil fallait les
payer, mais cest maintenant une p riode r volue : tout a t informatis ! Bien entendu, il faut
trouver une mani re de savoir comment expliquer lordinateur comment choisir... nouveau,
a ne va pas vous surprendre, lordinateur va lapprendre tout seul ! Quoi ? Si, a vous surprend ?
Tiens donc... Lordinateur va se cr er une structure interne pour r ussir prendre des d cisions.
Cest justement ce que nous allons faire nous aussi (quelle co ncidence !).
Il y a bien entendu plusieurs mani res pour faire un arbre de d cision : on peut gentiment
expliquer lordinateur en le programmant tape par tape comment il doit faire pour prendre
une d cision (cest la m thode facile) ou alors on peut lui demander de trouver tout seul comment
le g n rer (cest la m thode compliqu e). Je vous laisse deviner laquelle nous allons d velopper
ici.
Ne perdez pas de vue notre ami Ren , je vais en reparler dans un instant pour vous expliquer le
fonctionnement plus pr cis dun arbre de d cision. Mais avant a, je vais devoir vous parler de
lapprentissage automatique !
###2. Apprentissage automatique Commen ons par lapprentissage automatique, plus connu
sous son nom anglais : Machine Learning. Cest une branche de lIA qui consiste trouver
des m thodes qui permettraient la r solution de probl mes compliqu s r soudre avec des
algorithmes triviaux. Bon quest-ce quun algorithme trivial ? Il faudrait d j commencer par
2
1. Comprendre le concept
d finir ce quest un algorithme. Si a vous int resse vraiment fort, nh sitez pas aller lire le
tutoriel sur ce site (ici
).
?
Bon, quest-ce quun algorithme ?
Un algorithme, cest une suite finie dinstructions non ambig es exprimant la r solution dun
probl me. Voil , vous tes contents ? Quest-ce que a veut dire tout a ? Bon, allons-y tape par
tape. Une suite finie dinstructions est une liste dinstructions qui est tr s clairement d finie et
pour laquelle le nombre d tapes (instructions) est fini (fini ici est le contraire dinfini). Passons
la caract ristique de non-ambig it . a veut tout simplement dire que chaque instruction de
la liste est tr s claire sur ce quelle fait et ne peut pas tre confondue avec une autre.
?
Et trivial, a veut dire quoi ?
On va consid rer ici quun algorithme trivial cest un algorithme (forc ment ) qui est tr s simple
et surtout qui sex cute en un temps plus quacceptable. On parle de complexit polynomiale
pour les int ress s.
De mani re g n rale, lapprentissage automatique, cest apprendre faire mieux dans le
futur sur base de ce qui a t exp riment dans le pass .
source
Les chercheurs tentent donc de d couvrir lalgorithme (ou plus justement la succession dalgo-
rithmes) le plus ecace pour permettre au programme dapprendre de ce qui lui est donn . Cet
algorithme se veut le plus g n ral possible :
Nous cherchons des algorithmes qui peuvent tre facilement applicables une large classe de
probl mes dapprentissage.
source
Le fondement m me de cette branche de lIA est de trouver une m thode de r solution de
probl mes sans que des programmeurs ne doivent adapter lalgorithme en fonction du probl me
pos . Vous pouvez voir sur la figure suivante le fonctionnement g n ral de lapprentissage
automatique. Les notions et le vocabulaire qui y sont relatifs sont expliqu s juste apr s.
3
1. Comprendre le concept
Figure 1.1. fonctionnement dun probl me typique dapprentissage automatique (Fig. 1)
Lapprentissage automatique a un jargon bien particulier que lon va d tailler ici.
!
Attention, le vocabulaire expliqu ici est un vocabulaire relatif une branche pr cise de
lapprentissage automatique : lapprentissage automatique supervis . Cest uniquement de
celui-ci quil sera question ici. Plus dinformations sur le sujet viendront plus tard dans
des cours/articles d di s.
Ce que lon va faire, cest classer (ou classifier) des objets. Cest le principe des algorithmes que
je vais vous d tailler dans ce cours. Ces objets vont avoir plusieurs caract ristiques (que lon
peut galement appeler attributs). En fonction de ces attributs que lon va explorer et tester,
on va finir par attribuer une classe chaque objet. Chacun de ces objets est appel exemple.
On va donc manipuler des exemples compos s dattributs pour leur attribuer une classe.
Il existe deux types dexemples : les exemples tiquet s et les exemples non tiquet s.
Leur diff rence est tr s simple. Les exemples tiquet s sont ceux qui sont pr -class s et qui
donc vont tre utilis s pour que le programme sache comment classer les exemples suivants. Les
exemples suivants, vous laurez devin , sont eux les exemples non tiquet s. La m thode qui va
tre utilis e pour d terminer comment tiqueter les exemples non tiquet s sur base des exemples
tiquet s sappelle lalgorithme dapprentissage. Nous allons en voir deux ici : lalgorithme
ID3 et son successeur, lalgorithme C4.5. Cet algorithme dapprentissage (peu importe duquel il
est question) va nous permettre dextraire une r gle que lon appelle concept qui va nous dire
comment on fait pour tiqueter un exemple.
R capitulons :
nous allons cr er un programme compos dun algorithme dapprentissage qui va nous
permettre danalyser des exemples tiquet s (eux-m mes compos s dattributs) pour pouvoir
classer dautres exemples mais cette fois-ci des exemples non tiquet s, et ce laide dun
concept.
4
1. Comprendre le concept
Pour rendre les choses aussi simples que possible, nous allons consid rer quil ny a que deux
classes possibles que nous pouvons appeler 0 et 1. Nous allons galement supposer quil y a
toujours moyen de lier lexemple son tiquette. En r alit , il est possible que a ne soit pas
le cas, mais cest tout de m me plus simple de vous expliquer comment a marche si tout se
d roule bien !
i
Notez que lhistoire du nombre d tiquettes r duit 2 nest pas tout le temps dapplication.
Forc ment, par soucis doptimisation, on cherche toujours limiter le nombre de possibilit s
et de tournures que peut prendre un probl me. On tente donc de r duire le nombre
d tiquettes autant que possible. Mais on peut tr s bien tre confront un probl me de
classification 3, 4 ou encore 150 classes !
Rassurez-moi, tout le monde est encore vivant la fin de cette premi re partie un peu ardue ?
Revenons-en au d roulement g n ral dun probl me dapprentissage automatique. Le fonction-
nement est le suivant : lalgorithme central est le premier l ment de limage, il est impl ment
avant de faire fonctionner le programme. Cest dailleurs deux de ces algorithmes que nous allons
tudier ici. L tape suivante est de fournir un set dexemples tiquet s pour que le programme
puisse comprendre (gr ce lalgorithme central) par quel concept (quelle r gle) les exemples
ont t tiquet s. Une fois le concept extrait, on ny touche plus, et on soumet de nouveaux
exemples, cette fois-ci non tiquet s !, ce concept afin que le programme fasse une analyse
syst matique et r ussisse tiqueter lui-m me les nouveaux exemples fournis. Donc si vous
regardez de plus pr s la figure 1, vous vous apercevrez quil y a pr sence de deux axes : un axe
horizontal qui est le premier exp riment , et qui nest exp riment quune seule fois, et puis il y
a laxe vertical qui, quant lui, ne peut tre op r quapr s avoir op r laxe horizontal, et est
utilis plus dune fois (sinon quel en serait lint r t ?).
1.2. tat des lieux
###1. Les arbres de d cisions En anglais decision trees, les arbres de d cisions sont utilis s
entre autres dans lapprentissage automatique. Mais attention, cest loin d tre leur seul domaine
dapplication ! Ce mod le est appel arbre car il est compos de nSuds ayant chacun un certain
nombre (variable) de fils. Le principe est de partir den haut de larbre (du nSud p re de tous
les autres, que lon appelle racine) et de tester lattribut en question et de suivre le chemin.
Juste avant den voir un exemple, il serait int ressant de donner une d finition dun arbre de
d cision.
i
Un arbre de d cision est un arbre^arbre
dont les nSuds repr sentent un choix sur un
attribut, les arcs repr sentent les possibilit s pour lattribut test et les feuilles repr sentent
les d cisions en fonction des compositions dattributs.
Voici un exemple darbre de d cision :
1. Donc un graphe connexe acyclique.
5
1. Comprendre le concept
Figure 1.2. exemple darbre de d cision r pondant Le patient est-il malade ? (Fig. 2)
Laissez-moi vous expliquer la m thodologie pour parcourir un arbre de d cision en machine
learning. Pour ce, il faut d j savoir quoi il sert.
Consid rons que cet arbre-ci est une m thode syst matique pour traiter les cas dinscriptions au
MIT. Vous souvenez-vous de Ren , mon bon ami ? Cest ici quil r intervient : nous allons donc
suivre tape par tape le traitement de sa demande dinscription au MIT.
On commence tout en haut, donc par la question
est dipl m du lyc e (ou de lenseignement secondaire) ?
Ordinateur du MIT en charge des inscriptions
Publicité
Ici, deux choix soffrent nous comme on peut le voir sur limage. Deux branches partent de
la premi re case. Ces deux branches sont NON et OUI. Ren a donc deux possibilit s : soit
il a un dipl me d tudes sup rieures, soit il nen a pas. Jusque-l , tout le monde est daccord
avec moi, non ? Fort heureusement pour nous (et surtout pour Ren !), ce dernier a bien fini ses
tudes. On suit donc la branche OUI (celle de droite) et on laisse tomber tout ce qui suit la
branche de gauche.
On continue de descendre et on arrive la question
a plus de 18 ans ?
nouveau, deux choix soffrent nous : soit Ren a plus de 18 ans, soit il na pas plus de 18
ans.
Toujours le m me ordinateur
i
Et pour ceux qui rousp teraient parce quon ne laisse pas Ren la possibilit davoir 18
ans pile, je leur r pondrai quil attendra le lendemain pour venir sinscrire si cest le cas,
na !
6
1. Comprendre le concept
Cest le jour de chance de notre ami Ren : il a eu 18 ans la semaine pass e. Il peut donc passer
sur la branche OUI (la branche de gauche). nouveau, on oublie le reste des branches (donc
uniquement la branche de droite).
On continue de descendre... Et lordinateur nous harc le de questions : il nous demande
maintenant
a des parents riches ?
Encore et toujours cet ordinateur
Euh... Bah Ren vient dune famille relativement ais e mais mine de rien, on ne peut pas les
qualifier de riches. Donc regardons ce que larbre nous propose : OUI, MOYEN, ou NON.
Choisissons MOYEN parce que sa famille nest ni pauvre ni riche. Alors on fait encore et
toujours le m me proc d , on suit la branche MOYEN et on oublie les deux autres. Lordinateur
en redemande :
a droit une bourse ?
si si... Cest toujours le m me, pourquoi il aurait chang ?
Cest l que a coince. Ren est un pauvre tudiant fran ais qui na pas droit avoir une bourse
aux tats-Unis dAm rique. On est alors contraints de suivre la branche NON de larbre et
nouveau doublier le reste.
Maintenant, lordinateur ne nous demande plus rien. Mais il nous ache ceci :
Non
Je vais le r p ter chaque fois ?
Pourquoi ? Cest assez simple : on a continu sur la branche, mais on ne rencontre plus de nSud.
On a rencontr une feuille. Cest le nom que lon donne une extr mit dun arbre. Le fait de
tomber sur une feuille nous fait arr ter de chercher vu que lon vient de recevoir la r ponse du
MIT. Et cette r ponse est non. Je vous laisse r essayer avec dautres personnes que Ren qui
ont dautres caract ristiques ou plut t dautres attributs. Si ce mot ne vous dit rien, je vous
recommande vivement de remonter dun chapitre et de relire le ( 1.1.).
###2. ID3 ID3 est un des nombreux algorithmes possibles pour g n rer un arbre de d cision,
et cest galement celui qui va tre d velopp dans la premi re partie de ce cours. Cet algorithme
t d velopp en 1986 par Ross Quinlan. Il la publi dans le magazine Machine Learning
parmi dautres articles.
###3. C4.5 C4.5 est en quelque sorte le petit fr re dID3. C4.5 a galement t d velopp par
Ross Quinlan dans les ann es 1990 et a aussi t publi dans Machine Learning.
Je nai pas vraiment d taill ces deux derniers chapitres car cest ce que nous allons faire dans
toute la suite de ce cours donc ne soyez pas impatients !
Il est donc n cessaire que vous ayez bien compris les notions abord es ici car vous en aurez
besoin pour suivre la suite de ce cours ! Si vous navez pas retenu tout le vocabulaire expos au
point 2, ce nest pas tr s grave, vous pourrez y retourner en cas de trou de m moire. Cependant,
si vous navez pas saisi ce qu tait un arbre de d cision et comment a sutilise ce machin l , il
est pr f rable pour vous de relire ce chapitre car la suite sera beaucoup plus ardue sinon.
7
1. Comprendre le concept
Quoi quil en soit, pr parez-vous entrer dans le vif du sujet avec lexposition de lalgorithme
ID3 !
Maintenant que vous savez ce quest un arbre de d cision, nous allons pouvoir nous lancer dans
la construction dune telle structure.
2.
source
8
2. Une premi re version : ID3
Dans cette partie, nous allons voir le principe de lalgorithme ID3 laide dun exemple. Ensuite
je vous donnerai le pseudo-code afin de nous lancer dans une impl mentation en Python3.
2.1. Lalgorithme ID3
Cest, pour commencer, cet algorithme qui va tre expliqu . ID3 veut dire Iterative Dichotomiser
3. Il va tre expliqu laide dun premier exemple, puis lalgorithme sera explicit , et enfin
quelques am liorations possibles seront expliqu es.
###1. Exemple de playTennis Voici lexemple utilis par Quinlan en personne pour expliquer
son algorithme dans le magazine Machine Learning. Lalgorithme ID3 part dun tableau (de
mani re plus g n rale, dun set, ensemble en anglais) dexemples tiquet s duquel va d couler
un arbre qui pourra pr dire les tiquettes de nouveaux exemples non tiquet s donn s par apr s.
Comme vous pouvez le voir, ID3 est bien un algorithme dapprentissage automatique vu quil
est bien question dexemples, d tiquettes, dattributs, de classification, etc. et cest bien un
arbre de d cision parce que... parce que cest un arbre pardi !
####1.1. Tableau de valeurs
Voici le tableau contenant les informations n cessaires lexplication de lalgorithme tel quex-
pliqu par Ross Quinlan.
Jour
Attributs des exemples
Classe
Pr visions
Temp rature
Humidit
Vent
1
Ensoleill
Chaud
lev e
Faible
Non
2
3
4
5
6
7
8
9
Ensoleill
Nuageux
Pluvieux
Pluvieux
Pluvieux
Nuageux
Ensoleill
Ensoleill
Chaud
Chaud
Moyen
Frais
Frais
Frais
Moyen
Frais
9
lev e
lev e
lev e
Normale
Normale
Normale
lev e
Normale
Fort
Faible
Faible
Faible
Fort
Fort
Faible
Faible
Non
Oui
Oui
Oui
Non
Oui
Non
Oui
2. Une premi re version : ID3
10
11
12
13
14
Pluvieux
Ensoleill
Nuageux
Nuageux
Pluvieux
Moyen
Moyen
Moyen
Chaud
Moyen
Normale
Normale
lev e
Normale
lev e
Faible
Fort
Fort
Faible
Fort
Oui
Oui
Oui
Oui
Non
Table : Ensemble dexemples pour playTennis
Pr visions, Temp rature, Humidit et Vent sont les quatre attributs qui d terminent
chacun des exemples qui vont tre fournis. On peut voir quil existe uniquement 36 exemples
diff rents pour cette configuration dattributs :
= 3 3 2 2 = 9 4 = 36
1.2. Arbre complet et optimis g n r par lalgorithme
Voici ce quoi on devrait arriver la fin de ce chapitre : un arbre tout beau tout propre
g n r sur base du tableau que je viens de vous donner. Si vous testez chaque branche avec la
m thodologie expliqu e au-dessus ( 1.2.), vous vous apercevrez que larbre classe tous les
exemples sans faute.
! (/media/galleries/4955/8108f502-
02e8-4f08-aab9-a0b4abda6c94.gif)
2. Explication de lalgorithme Lalgorithme ID3 se base sur le concept dattributs et de classe de
Publicité
lapprentissage automatique (sur classification discr te ).Cetalgorithmerecherchel(cid:48)attributlepluspertinenttesterpourquel(cid:48)arbresoitlepluscourtetoptimispossible.
Pour trouver lattribut tester, Quinlan parle dentropie. Pour d finir lentropie, il faut
dabord rappeler que la quantit minimale de donn es redondantes ajouter pour quun message
ayant une probabilit p darriver sans tre corrompu est log2(p). Une telle n cessit de stocker
des donn es redondantes est assez vidente dans le cas de codes correcteurs derreurs par
exemple .N evouslaissezpasavoirparle devantlelog : le logarithme dun nombre
compris entre 0 et 1 est toujours n gatif. Il faut donc prendre son oppos avec le
-. Rappelons galement que lentropie est la longueur minimale n cessaire pour coder la
classe dun membre pris au hasard dans le set dexemples S. Cest en r alit de l**entropie
de Shannon** quil est question. On lappelle ainsi car cest une notion trouv e par ling nieur
am ricain Claude Shannon.
: P ourplusd(cid:48)inf ormations, c(cid:48)est (https : //f r.wikipedia.org/wiki/Codecorrecteur)etpluslargement (https :
//f r.wikipedia.org/wiki/T h : P lusdedtails : (http : //www.yannollivier.org/entropie/entropie1).
Tel que pc est la proportion dexemples de S ayant pour classe r sultante c. Dans lexemple
dau-dessus, les seules classes possibles sont Oui et Non. donc lentropie vaut
pOui log2(pOui) pNon log2(pNon)
10
2. Une premi re version : ID3
Dailleurs voici quoi ressemble la fonction dentropie pour un ensemble deux classes possibles
(Fig. 4)
Figure 2.1. le graphique dentropie de Shannon pour un ensemble nayant que deux tiquettes
(Fig. 4)
Remarquons quelque chose dint ressant : cette fonction est parfaitement sym trique en prenant
laxe x = 1
2. Et pour cause : la fonction dentropie repr sente le d sordre au sein du set (dans
notre cas, ou du message dans le cas du code correcteur derreurs). Donc quil y ait 5 l ments
dune classe et 3 dune autre ou inversement, le d sordre reste le m me car les proportions
restent inchang es. On peut galement voir trois points int ressants sur ce graphique (il y a en
r alit une infinit de points int ressants pour ceux comme moi qui ce graphe parle mais bon
mon but est de ne pas vous effrayer donc nous allons nous int resser qu ces trois l maintenant
). Ces trois points sont les points dabscisse 0, 0.5 et 1. Vous voyez o je veux en venir ? Si
lentropie repr sente le d sordre du set, cest logique que le set ait lentropie la plus lev e
quand il est le plus d sordonn . Et quand est-ce quil est le plus d sordonn ? Quand il a autant
dobjets de la premi re classe que dobjets de la deuxi me classe. Logique non ? Et inversement :
quand le set a une entropie nulle (qui vaut 0), cest parce que cest ce moment que le d sordre
est le moins lev . Et quand est-ce que le d sordre est le moins lev ? Quand tous les objets
sont de la m me classe. Donc quand la probabilit est soit minimum (0) soit maximum (1).
11
2. Une premi re version : ID3
Initialement, lalgorithme prend tout le set S = {J1, J2, J3, ..., J14}. Et comme 9 des 14 exemples
donnent la r ponse (ou classe) Oui et 5 sur 14 donnent la r ponse (ou classe) Non,
pNon =
5
14
On peut donc calculer que
Il faut savoir que, comme on peut le voir sur la Fig. 4,
S : 0 d Entropie(S) d 1
Ce qui veut dire que pour tout ensemble S, le d sordre de S est toujours compris entre 0 et 1.
Maintenant que nous savons que lentropie initiale du set est de 0.94, il nous faut savoir quel
attribut tester en premier, puis en second, ..., puis en n-i me.
Pour savoir quel attribut tester, il faut conna tre la notion de gain dentropie. Le gain est d fini
par un set dexemples et par un attribut. Cette formule va donc servir calculer ce que cet
attribut apporte au d sordre du set. Plus un attribut contribue au d sordre, plus il est important
de le tester pour s parer le set en plus petits sets ayant une entropie moins lev e.
Gain(S, A) = Entropie(S)
(cid:88)
v valeurs(A)
|Sv|
|S|
Entropie(Sv)
Lattribut qui va tre test ce nSud de larbre est le nSud qui va le plus r duire lentropie.
Cest logique : quand lentropie vaut z ro, cest quil ny a quune seule classe repr sent e :
1 log2(1) n (0 log2(0)) = 0 n 0 = 0
i
Ici, jai mis un n en vidence pour dire quil peut y avoir autant de classes que lon veut.
Mais si la probabilit dune classe est 1, on a beau avoir 150 classes, leur probabilit sera
nulle chaque fois. On peut donc mettre le nombre de classes en vidence. Mais attention,
si je mets n en vidence, cest parce quil y a n classes de probabilit nulle, mais il y a
aussi une classe de probabilit 1. Il y a donc n+1 classes diff rentes.
Toujours dans notre exemple du point 2, en consid rant S comme le set initial, pour d terminer
lattribut tester, il faut calculer le gain de tous les attributs :
####2.1. Calcul de gain dentropie
#####2.1.1. Pr visions Lattribut Pr visions a trois valeurs possibles : {Ensoleill , Nuageux, Pluvieux}.
12
2. Une premi re version : ID3
Gain(S, Pr visions) = Entropie(S)
= 0.94
5
14
4
14
5
14
5
14
4
14
5
14
Entropie(SEnsoleill )
Entropie(SNuageux)
Entropie(SPluvieux)
(cid:19)
(cid:18)
(cid:18)
(cid:18)
3
5
0
4
3
5
log2
log2
log2
(cid:18)3
5
(cid:18)0
4
(cid:18)3
5
(cid:19)
(cid:19)
2
5
4
4
2
5
log2
log2
log2
(cid:19)(cid:19)
(cid:19)(cid:19)
(cid:19)(cid:19)
(cid:18) 2
5
(cid:18) 4
4
(cid:18) 2
5
= 0.94
= 0.24742
0.357 (0.97)
0.286 (0)
0.357 (0.97)
#####2.1.2. Vent Lattribut Vent a quant lui deux valeurs possibles : {Faible, Fort}.
Gain(S, Vent) = Entropie(S)
8
14
6
14
(cid:18)
(cid:18)
6
8
3
6
log2
log2
(cid:19)
(cid:19)
(cid:18)6
8
(cid:18)3
6
2
8
3
6
log2
log2
(cid:19)(cid:19)
(cid:19)(cid:19)
(cid:18) 2
8
(cid:18) 3
Publicité
6
= 0.94
= 0.048
0.571 (0.811)
0.428 1
#####2.1.3. Humidit Humidit a galement deux valeurs possibles : { lev e, Normale}.
Gain(S, Humidit ) = Entropie(S)
(cid:18)
(cid:18)
4
7
6
7
log2
log2
(cid:19)
(cid:19)
(cid:18) 4
7
(cid:18) 6
7
3
7
1
7
log2
log2
(cid:19)(cid:19)
(cid:19)(cid:19)
(cid:18)3
7
(cid:18)1
7
7
14
7
14
0.49
0.296
= 0.94
= 0.153
#####2.1.4. Temp rature Temp rature a trois valeurs diff rentes possibles : {Chaud, Chaud, Frais}.
13
2. Une premi re version : ID3
Gain(S, Temp rature) = Entropie(S)
(cid:18)
(cid:18)
(cid:18)
2
4
4
6
3
4
log2
log2
log2
(cid:19)
(cid:19)
(cid:19)
(cid:18) 2
4
(cid:18) 4
6
(cid:18) 3
4
2
4
2
6
1
4
log2
log2
log2
(cid:19)(cid:19)
(cid:19)(cid:19)
(cid:19)(cid:19)
(cid:18) 2
4
(cid:18) 2
6
(cid:18) 1
4
4
14
6
14
4
14
0.286
0.394
0.232
= 0.94
= 0.028
R capitulons : Gain(S, Temp rature) < Gain(S, Vent) < Gain(S, Humidit ) < Gain(S, Pr visions).
On peut voir que le plus grand gain est pour Pr visions. Cest donc Pr visions qui est le
premier attribut test dans larbre. Si on regarde chaque nSud fils, on remarque que pour le
nSud Nuageux, tous les r sultats sont positifs. Il ny a donc pas dattribut tester ici, on peut
directement tiqueter Oui. Voici quoi ressemble notre arbre.
/media/galleries/822/a9a95fc2-33c6-4a0b-8586-721fffb94d77.png.960x960_q85.jpg
Figure 2.2. arbre la premi re it ration de sa r alisation (Fig. 5)
Image perdue
!
i
Jai utilis une notation entre crochets de la forme . Cette notation veut dire
que dans lensemble ayant n+m l ments, n sont positifs et m sont n gatifs. Dans notre
cas, les positifs sont les exemples tiquet s Oui et les n gatifs sont ceux tiquet s Non
bien entendu.
Il faut maintenant continuer mettre des nSuds apr s Ensoleill et Pluvieux car tous les
exemples ne donnent pas le m me r sultat. D terminons donc pour Ensoleill quel est le
meilleur attribut tester en utilisant nouveau le gain. Cependant il nest plus utile de tester
le gain de Pr visions tant donn quil vient d tre utilis . Je vous donne juste les r sultats, je
vous laisse faire les calculs vous-m me pour vous entrainer.
Rappel : pour ceux nayant pas de fonctionnalit log2 sur leur calculatrice :
log2(f (x)) =
log(f (x))
log(2)
Voici donc ce que vous devez normalement obtenir :
14
2. Une premi re version : ID3
Gain(SEnsoleill , Temp rature) = 0.571
Gain(SEnsoleill , Humidit ) = 0.971
Gain(SEnsoleill , Vent) = 0.019
Donc r capitulons nouveau :
Le plus grand gain est pour Humidit . Dailleurs on peut voir que le gain est gal lentropie
de SEnsoleill . a veut dire que tous les fils de Humidit donneront une tiquette. Voil notre
arbre jusqu pr sent. Il nous reste continuer larbre du c t de Pluvieux. Voici les gains
pour les diff rents attributs ( nouveau, il nest pas n cessaire de tester Pr visions qui vient
de l tre mais il faut tester Humidit qui na pas t test de ce c t -l de la branche) :
Gain(SPluvieux, Temp rature) = 0.019
Gain(SPluvieux, Humidit ) = 0.019
Gain(SPluvieux, Vent) = 0.971
R capitulons une fois de plus :
Le plus grand gain est nouveau de 0.971 et est pour Vent. Il nous faut donc tester Vent et
vu que le gain est gal lentropie de SPluvieux, chaque nSud fils de Vent sera une tiquette.
Voici donc notre arbre. Il ny a plus rien faire tant donn quil ne reste aucun nSud qui nest
pas tiquet . Le travail est donc accompli et voil larbre que nous avons g n r .
Figure 2.3. larbre g n r par ID3 de lexemple playTennis (Fig. 6)
15
2. Une premi re version : ID3
Si vous comparez larbre que nous venons de g n rer avec larbre que je vous ai donn en d but
de tutoriel, vous pouvez constater que cest exactement le m me. Larbre est optimis car il
donne une tiquette en maximum deux tests alors quil y a 4 attributs diff rents.
Vous ne voyez peut- tre pas lutilit de cet arbre parce quici il y a maximum 36 combinaisons
des attributs et 14 nous sont d j donn es. Mais imaginez maintenant que vous voulez faire
un arbre qui va d terminer un diagnostic pour des malades. Comme il existe des milliers de
maladies et encore plus de sympt mes, larbre sera plus dicile faire la main. Ceci dit, tant
que tous les exemples possibles nont pas t donn s il est possible que larbre contienne des
erreurs. Mais nous y reviendrons plus tard.
###3. Algorithme et pseudo-code de lalgorithme ID3 Voici lalgorithme de g n ration dun
arbre de d cision selon ID3 sous forme de pseudo-code. Ce chapitre est pour les programmeurs.
Si vous tes uniquement venus pour les maths, ce chapitre ne vous concerne pas directement et
vous n tes pas oblig s de lire ce qui suit.
Je ne vais pas d tailler le pseudo-code, a devrait sembler relativement clair. Et si vous avez
tout de m me besoin daide la compr hension, regardez dans les commentaires, peut- tre
trouverez-vous votre r ponse. Et si vous ne ly trouvez pas, posez votre question sur les forums,
cest a quils servent.
1 FONCTION ID3
2
3
4
Entr e :
- exemples = liste d'exemples tiquet s
- questions = liste des attributs non utilis s
5
6
7 DEBUT
8
9
10
Publicité
11
12
13
14
15
16
17
18
19
20
21
22
23
24
jusqu' pr sent
Retour :
- un nSud
SI exemples est vide, alors
Finir la fonction sans construire de nSud
FIN SI
SI tous les exemples sont la m me classe, alors
Retourner une feuille ayant cette classe
FIN SI
SI questions est vide, alors
Retourner une feuille avec la classe la plus
fr quente
FIN SI
q = attribut optimal (avec le plus grand gain d'entropie)
n = nouveau nSud cr qui testera l'attribut q
POUR CHAQUE v = valeur possible de q, FAIRE
e = l'ensemble des l ments de exemples ayant v
comme valeur l'attribut q
16
2. Une premi re version : ID3
25
26
27
28 FIN
chaque nSud fils de n est cr par ID3(e,
questions\{q})
FIN POUR CHAQUE
Retourner n
Notez que si la condition SI questions est vide est remplie, a veut dire que deux exemples
identiques mais tiquet s diff remment ont t mis dans le set dexemples de test.
###4. Am liorations Ici sont pr sent es dabord les am liorations que lon peut apporter aux
notions vues au ( 2.).5
Commen ons par la fonction dEntropie. Une petite tude math matique nous montre que la
probabilit dune classe dans un set nest autre que la longueur du sous-set de cette classe divis e
par la longueur du set initial. Donc
Entropie(S) =
(cid:88)
pc log2(pc)
c classes(S)
(cid:88)
=
c classes(S)
|c|
|S|
log2
(cid:19)
(cid:18) |c|
|S|
(cid:18) |c|
|S|
(cid:19)
|c| log2
(cid:88)
c classes(S)
(cid:88)
c classes(S)
=
=
=
=
=
=
1
|S|
1
|S|
1
|S|
1
|S|
1
|S|
1
|S|
|c| (log2 |c| log2 |S|)
(cid:88)
|c| log2 |c|
(cid:88)
|c| log2 |S|
c classes(S)
c classes(S)
|c| log2 |c| log2 |S|
(cid:88)
|c|
c classes(S)
|c| log2 |c| |S| log2 |S|
(cid:88)
c classes(S)
(cid:88)
c classes(S)
(cid:88)
c classes(S)
|c| log2 |c| +
|S|
|S|
log2 |S|
= 1 log2 |S|
(cid:80)
= log2 |S|
1
|S|
(cid:88)
|c| log2 |c|
c classes(S)
c classes(S) |c| log2 |c|
|S|
Alors cette petite d monstration peut vous para tre rude, mais elle est tr s bien car elle nous
permet de faire beaucoup moins de calculs. Cest tr s pratique tant pour programmer (car le
programme sera plus rapide) que pour faire les calculs de t te (vous risquez beaucoup moins
17
2. Une premi re version : ID3
de faire des erreurs). On a donc simplifi notre splendide fonction dentropie et on a gard un
indice sommatoire tout de m me. Ouf !
?
Quid de la fonction de Gain(S, A) ?
Cette fonction varie entre 0 et Entropie(S) vu que :
0 <
(cid:88)
v valeurs(A)
|Sv|
|S|
Entropie(Sv) < Entropie(S)
Quand la somme vaut 0, Gain(S, A) vaut Entropie(S) ce qui est son maximum. Cest donc cet
attribut qui va tre choisi. Alors que si la somme vaut Entropie(S), gain vaut 0 et donc cet
attribut nest pas int ressant tester ce moment vu quil ne r duit pas lentropie (qui est,
rappelons-le, le d sordre des classifications du set). La seule chose qui nous int resse dans cette
fonction est donc la somme qui doit tre la plus petite possible (il nous faut avoir le moins de
d sordre). On peut donc changer la fonction comme ceci :
Perte(S, A) =
(cid:88)
v valeurs(A)
|Sv|
|S|
Entropie(Sv) =
1
|S|
(cid:88)
v valeurs(A)
|Sv| Entropie(Sv)
Sauf que je viens de vous montrer comment am liorer la fonction dentropie. On peut donc
encore simplifier la fonction de gain !
Perte(S, A) =
1
|S|
=
1
|S|
(cid:88)
v valeurs(A)
(cid:88)
v valeurs(A)
|Sv| Entropie(Sv)
|Sv|
log2 |Sv|
(cid:8...