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. L’algorithme ID3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.2. Une implémentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 Contenu masqué
3. Une amélioration : C 4.5
44 3.1. L’algorithme C 4.5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 3.2. Élagage de l’arbre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 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é à 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.
((cid:80)), les logarithmes
Pour comprendre les points de théorie traités, il est nécessaire de savoir manipuler l’indice sommatoire ). 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).
(et exponentielles
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.
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 n’hé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 j’ai un ami qui s’appelle René et qui me demande s’il peut s’inscrire au MIT. Alors comme vous pouvez vous en douter, ce n’est pas moi qui décide de qui peut ou ne peut pas s’inscrire 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, j’y arrive.
Le MIT avait des problèmes financiers parce qu’il nécessitait des dizaines de personnes préposées aux décisions d’inscriptions car ces derniers étaient extrêmement sollicités et qu’il fallait les payer, mais c’est maintenant une période révolue : tout a été informatisé ! Bien entendu, il faut trouver une manière de savoir comment expliquer à l’ordinateur comment choisir... À nouveau, ça ne va pas vous surprendre, l’ordinateur va l’apprendre tout seul ! Quoi ? Si, ça vous surprend ? Tiens donc... L’ordinateur va se créer une structure interne pour réussir à prendre des décisions. C’est 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 à l’ordinateur en le programmant étape par étape comment il doit faire pour prendre une décision (c’est la méthode facile) ou alors on peut lui demander de trouver tout seul comment le générer (c’est 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 d’un arbre de décision. Mais avant ça, je vais devoir vous parler de l’apprentissage automatique !
###2. Apprentissage automatique Commençons par l’apprentissage automatique, plus connu sous son nom anglais : Machine Learning. C’est une branche de l’IA qui consiste à trouver des méthodes qui permettraient la résolution de problèmes compliqués à résoudre avec des algorithmes triviaux. Bon qu’est-ce qu’un algorithme trivial ? Il faudrait déjà commencer par
2
1. Comprendre le concept
définir ce qu’est un algorithme. Si ça vous intéresse vraiment fort, n’hésitez pas à aller lire le tutoriel sur ce site (ici
).
?
Bon, qu’est-ce qu’un algorithme ?
Un algorithme, c’est une suite finie d’instructions non ambigües exprimant la résolution d’un problème. Voilà, vous êtes contents ? Qu’est-ce que ça veut dire tout ça ? Bon, allons-y étape par étape. Une suite finie d’instructions est une liste d’instructions qui est très clairement définie et pour laquelle le nombre d’étapes (instructions) est fini (fini ici est le contraire d’infini). 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 qu’elle fait et ne peut pas être confondue avec une autre.
?
Et trivial, ça veut dire quoi ?
On va considérer ici qu’un algorithme trivial c’est un algorithme (forcément ) qui est très simple et surtout qui s’exécute en un temps plus qu’acceptable. On parle de complexité polynomiale pour les intéressés.
De manière générale, l’apprentissage automatique, c’est 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 l’algorithme (ou plus justement la succession d’algo- rithmes) le plus efficace pour permettre au programme d’apprendre 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 d’apprentissage.
source Le fondement même de cette branche de l’IA est de trouver une méthode de résolution de problèmes sans que des programmeurs ne doivent adapter l’algorithme en fonction du problème posé. Vous pouvez voir sur la figure suivante le fonctionnement général de l’apprentissage 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 d’un problème typique d’apprentissage automatique (Fig. 1)
L’apprentissage automatique a un jargon bien particulier que l’on va détailler ici.
!
Attention, le vocabulaire expliqué ici est un vocabulaire relatif à une branche précise de l’apprentissage automatique : l’apprentissage automatique supervisé. C’est uniquement de celui-ci qu’il sera question ici. Plus d’informations sur le sujet viendront plus tard dans des cours/articles dédiés.
Ce que l’on va faire, c’est classer (ou classifier) des objets. C’est le principe des algorithmes que je vais vous détailler dans ce cours. Ces objets vont avoir plusieurs caractéristiques (que l’on peut également appeler attributs). En fonction de ces attributs que l’on 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 d’attributs pour leur attribuer une classe.
Il existe deux types d’exemples : 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 l’aurez 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 s’appelle l’algorithme d’apprentissage. Nous allons en voir deux ici : l’algorithme ID3 et son successeur, l’algorithme C4.5. Cet algorithme d’apprentissage (peu importe duquel il est question) va nous permettre d’extraire une règle que l’on appelle concept qui va nous dire comment on fait pour étiqueter un exemple.
Récapitulons :
nous allons créer un programme composé d’un algorithme d’apprentissage qui va nous permettre d’analyser des exemples étiquetés (eux-mêmes composés d’attributs) pour pouvoir classer d’autres exemples mais cette fois-ci des exemples non étiquetés, et ce à l’aide d’un concept.
4
1. Comprendre le concept
Pour rendre les choses aussi simples que possible, nous allons considérer qu’il n’y a que deux classes possibles que nous pouvons appeler 0 et 1. Nous allons également supposer qu’il y a toujours moyen de lier l’exemple à son étiquette. En réalité, il est possible que ça ne soit pas le cas, mais c’est tout de même plus simple de vous expliquer comment ça marche si tout se déroule bien !
i
Notez que l’histoire du nombre d’étiquettes réduit à 2 n’est pas tout le temps d’application. Forcément, par soucis d’optimisation, 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 d’un problème d’apprentissage automatique. Le fonction- nement est le suivant : l’algorithme central est le premier élément de l’image, il est implémenté avant de faire fonctionner le programme. C’est d’ailleurs deux de ces algorithmes que nous allons étudier ici. L’étape suivante est de fournir un set d’exemples étiquetés pour que le programme puisse comprendre (grâce à l’algorithme central) par quel concept (quelle règle) les exemples ont été étiquetés. Une fois le concept extrait, on n’y 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 qu’il y a présence de deux axes : un axe horizontal qui est le premier expérimenté, et qui n’est expérimenté qu’une seule fois, et puis il y a l’axe vertical qui, quant à lui, ne peut être opéré qu’après avoir opéré l’axe horizontal, et est utilisé plus d’une fois (sinon quel en serait l’inté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 l’apprentissage automatique. Mais attention, c’est loin d’être leur seul domaine d’application ! Ce modèle est appelé arbre car il est composé de nœuds ayant chacun un certain nombre (variable) de fils. Le principe est de partir d’en haut de l’arbre (du nœud père de tous les autres, que l’on appelle racine) et de tester l’attribut en question et de suivre le chemin.
Juste avant d’en voir un exemple, il serait intéressant de donner une définition d’un arbre de décision.
i
Un arbre de décision est un arbre^arbre dont les nœuds représentent un choix sur un attribut, les arcs représentent les possibilités pour l’attribut testé et les feuilles représentent les décisions en fonction des compositions d’attributs.
Voici un exemple d’arbre de décision :
1. Donc un graphe connexe acyclique.
5
1. Comprendre le concept
Figure 1.2. – exemple d’arbre 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 d’inscriptions au MIT. Vous souvenez-vous de René, mon bon ami ? C’est ici qu’il réintervient : nous allons donc suivre étape par étape le traitement de sa demande d’inscription au MIT.
On commence tout en haut, donc par la question
est diplômé du lycée (ou de l’enseignement secondaire) ?
Ordinateur du MIT en charge des inscriptions
Ici, deux choix s’offrent à nous comme on peut le voir sur l’image. 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 n’en a pas. Jusque-là, tout le monde est d’accord 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 s’offrent à nous : soit René a plus de 18 ans, soit il n’a pas plus de 18 ans.
Toujours le même ordinateur
i
Et pour ceux qui rouspéteraient parce qu’on ne laisse pas à René la possibilité d’avoir 18 ans pile, je leur répondrai qu’il attendra le lendemain pour venir s’inscrire si c’est le cas, na !
6
1. Comprendre le concept
C’est 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 l’ordinateur nous harcèle de questions : il nous demande maintenant
a des parents riches ?
Encore et toujours cet ordinateur
Euh... Bah René vient d’une famille relativement aisée mais mine de rien, on ne peut pas les qualifier de riches. Donc regardons ce que l’arbre nous propose : OUI, MOYEN, ou NON. Choisissons MOYEN parce que sa famille n’est 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. L’ordinateur en redemande :
a droit à une bourse ?
si si... C’est toujours le même, pourquoi il aurait changé ?
C’est là que ça coince. René est un pauvre étudiant français qui n’a pas droit à avoir une bourse aux États-Unis d’Amérique. On est alors contraints de suivre la branche NON de l’arbre et à nouveau d’oublier le reste.
Maintenant, l’ordinateur ne nous demande plus rien. Mais il nous affiche ceci :
Non
Je vais le répéter à chaque fois ?
Pourquoi ? C’est assez simple : on a continué sur la branche, mais on ne rencontre plus de nœud. On a rencontré une feuille. C’est le nom que l’on donne à une extrémité d’un arbre. Le fait de tomber sur une feuille nous fait arrêter de chercher vu que l’on vient de recevoir la réponse du MIT. Et cette réponse est non. Je vous laisse réessayer avec d’autres personnes que René qui ont d’autres caractéristiques ou plutôt d’autres attributs. Si ce mot ne vous dit rien, je vous recommande vivement de remonter d’un 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 c’est é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 l’a publié dans le magazine Machine Learning parmi d’autres articles.
###3. C4.5 C4.5 est en quelque sorte le petit frère d’ID3. C4.5 a également été développé par Ross Quinlan dans les années 1990 et a aussi été publié dans Machine Learning.
Je n’ai pas vraiment détaillé ces deux derniers chapitres car c’est 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 n’avez pas retenu tout le vocabulaire exposé au point 2, ce n’est pas très grave, vous pourrez y retourner en cas de trou de mémoire. Cependant, si vous n’avez pas saisi ce qu’était un arbre de décision et comment ça s’utilise 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 qu’il en soit, préparez-vous à entrer dans le vif du sujet avec l’exposition de l’algorithme ID3 !
Maintenant que vous savez ce qu’est un arbre de décision, nous allons pouvoir nous lancer dans la construction d’une telle structure.
2.
source
8
2. Une première version : ID3
Dans cette partie, nous allons voir le principe de l’algorithme ID3 à l’aide d’un exemple. Ensuite je vous donnerai le pseudo-code afin de nous lancer dans une implémentation en Python3.
2.1. L’algorithme ID3
C’est, pour commencer, cet algorithme qui va être expliqué. ID3 veut dire Iterative Dichotomiser 3. Il va être expliqué à l’aide d’un premier exemple, puis l’algorithme sera explicité, et enfin quelques améliorations possibles seront expliquées.
###1. Exemple de playTennis Voici l’exemple utilisé par Quinlan en personne pour expliquer son algorithme dans le magazine Machine Learning. L’algorithme ID3 part d’un tableau (de manière plus générale, d’un set, ensemble en anglais) d’exemples é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 d’apprentissage automatique vu qu’il est bien question d’exemples, d’étiquettes, d’attributs, de classification, etc. et c’est bien un arbre de décision parce que... parce que c’est un arbre pardi !
####1.1. Tableau de valeurs
Voici le tableau contenant les informations nécessaires à l’explication de l’algorithme tel qu’ex- 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
Publicité
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 d’exemples 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 qu’il existe uniquement 36 exemples différents pour cette configuration d’attributs :
= 3 × 3 × 2 × 2 = 9 × 4 = 36
1.2. Arbre complet et optimisé généré par l’algorithme
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 l’arbre classe tous les exemples sans faute.
2. Explication de l’algorithme L’algorithme ID3 se base sur le concept d’attributs et de classe de l’apprentissage automatique (sur classification discrète[discrte]).Cetalgorithmerecherchel(cid:48)attributlepluspertinenttesterpourquel(cid:48)arbresoitlepluscourtetoptimispossible.
Pour trouver l’attribut à tester, Quinlan parle d’**entropie**. Pour définir l’entropie, il faut d’abord rappeler que la quantité minimale de données redondantes à ajouter pour qu’un message ayant une probabilité p d’arriver 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 d’erreurs par exemple[CCE].N evouslaissezpasavoirparle ∗ ∗ − ∗ ∗ devantlelog : le logarithme d’un nombre compris entre **0** et **1** est toujours négatif. Il faut donc prendre son opposé avec le **-**. Rappelons également que l’entropie est la longueur minimale nécessaire pour coder la classe d’un membre pris au hasard dans le set d’exemples S. C’est en réalité de l’**entropie de Shannon** qu’il est question. On l’appelle ainsi car c’est une notion trouvée par l’ingénieur américain Claude Shannon.[ES]
[CCE] : P ourplusd(cid:48)inf ormations, c(cid:48)est[ici](https : //f r.wikipedia.org/wiki/Codecorrecteur)etpluslargement[ici](https : //f r.wikipedia.org/wiki/T h[ES] : P lusdedtails : [ici](http : //www.yann−ollivier.org/entropie/entropie1).
Tel que pc est la proportion d’exemples de S ayant pour classe résultante c. Dans l’exemple d’au-dessus, les seules classes possibles sont Oui et Non. donc l’entropie vaut
−pOui × log2(pOui) − pNon × log2(pNon)
10
2. Une première version : ID3
D’ailleurs voici à quoi ressemble la fonction d’entropie pour un ensemble à deux classes possibles (Fig. 4)
Figure 2.1. – le graphique d’entropie de Shannon pour un ensemble n’ayant que deux étiquettes
(Fig. 4)
Remarquons quelque chose d’intéressant : cette fonction est parfaitement symétrique en prenant l’axe x = 1 2. Et pour cause : la fonction d’entropie représente le ”désordre” au sein du set (dans notre cas, ou du message dans le cas du code correcteur d’erreurs). Donc qu’il y ait 5 éléments d’une classe et 3 d’une 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 d’abscisse 0, 0.5 et 1. Vous voyez où je veux en venir ? Si l’entropie représente le désordre du set, c’est logique que le set ait l’entropie la plus élevée quand il est le plus désordonné. Et quand est-ce qu’il est le plus désordonné ? Quand il a autant d’objets de la première classe que d’objets de la deuxième classe. Logique non ? Et inversement : quand le set a une entropie nulle (qui vaut 0), c’est parce que c’est à 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, l’algorithme 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[approx]que
Il faut savoir que, comme on peut le voir sur la Fig. 4,
∀S : 0 ≤ Entropie(S) ≤ 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 l’entropie 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 d’entropie. Le gain est défini par un set d’exemples 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)
L’attribut qui va être testé à ce nœud de l’arbre est le nœud qui va le plus réduire l’entropie. C’est logique : quand l’entropie vaut zéro, c’est qu’il n’y a qu’une seule classe représentée :
−1 × log2(1) − n × (0 × log2(0)) = 0 − n × 0 = 0
i
Ici, j’ai mis un n en évidence pour dire qu’il peut y avoir autant de classes que l’on veut. Mais si la probabilité d’une 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, c’est parce qu’il 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 l’attribut à tester, il faut calculer le gain de tous les attributs :
####2.1. Calcul de gain d’entropie
#####2.1.1. Prévisions L’attribut 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 L’attribut 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
Publicité
× 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 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. C’est donc Prévisions qui est le premier attribut testé dans l’arbre. Si on regarde chaque nœud fils, on remarque que pour le nœud Nuageux, tous les résultats sont positifs. Il n’y a donc pas d’attribut à 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
J’ai utilisé une notation entre crochets de la forme [n+, m-]. Cette notation veut dire que dans l’ensemble 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 nœuds 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 n’est plus utile de tester le gain de Prévisions étant donné qu’il 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 n’ayant 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é. D’ailleurs on peut voir que le gain est égal à l’entropie de SEnsoleillé. Ça veut dire que tous les fils de Humidité donneront une étiquette. Voilà notre arbre jusqu’à présent. Il nous reste à continuer l’arbre du côté de Pluvieux. Voici les gains pour les différents attributs (à nouveau, il n’est pas nécessaire de tester Prévisions qui vient de l’être mais il faut tester Humidité qui n’a 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 à l’entropie de SPluvieux, chaque nœud fils de Vent sera une étiquette.
Voici donc notre arbre. Il n’y a plus rien à faire étant donné qu’il ne reste aucun nœud qui n’est pas étiqueté. Le travail est donc accompli et voilà l’arbre que nous avons généré.
Figure 2.3. – l’arbre généré par ID3 de l’exemple playTennis (Fig. 6)
15
2. Une première version : ID3
Si vous comparez l’arbre que nous venons de générer avec l’arbre que je vous ai donné en début de tutoriel, vous pouvez constater que c’est exactement le même. L’arbre est optimisé car il donne une étiquette en maximum deux tests alors qu’il y a 4 attributs différents.
Vous ne voyez peut-être pas l’utilité de cet arbre parce qu’ici 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, l’arbre sera plus difficile à faire à la main. Ceci dit, tant que tous les exemples possibles n’ont pas été donnés il est possible que l’arbre contienne des erreurs. Mais nous y reviendrons plus tard.
###3. Algorithme et pseudo-code de l’algorithme ID3 Voici l’algorithme de génération d’un 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 d’aide à la compréhension, regardez dans les commentaires, peut-être trouverez-vous votre réponse. Et si vous ne l’y trouvez pas, posez votre question sur les forums, c’est à ça qu’ils 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 11 12 13 14 15 16 17
18 19 20 21 22 23 24
jusqu'à présent
Retour :
- un nœud
SI exemples est vide, alors
Finir la fonction sans construire de nœud
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 nœud 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 nœud 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 d’exemples de test.
###4. Améliorations Ici sont présentées d’abord les améliorations que l’on peut apporter aux notions vues au (§2.).5
Commençons par la fonction d’Entropie. Une petite étude mathématique nous montre que la probabilité d’une classe dans un set n’est 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)
Publicité
(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. C’est 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 d’entropie 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. C’est donc cet attribut qui va être choisi. Alors que si la somme vaut Entropie(S), gain vaut 0 et donc cet attribut n’est pas intéressant à tester à ce moment vu qu’il ne réduit pas l’entropie (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 d’entropie. 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:88)
|c| × log2 |c|
c ∈ classes(Sv)
1 |Sv|
×
(cid:88)
|Sv| |Sv|
×
(cid:88)
|c| × log2 |c|
c ∈ classes(Sv)
(cid:88)
|Sv| × log2 |Sv| −
v ∈ valeurs(A)
v ∈ valeurs(A)
=
=
1 |S|
1 |S|
×
×
(cid:88)
|Sv| × log2 |Sv| −
(cid:88)
(cid:88)
|c| × log2 |c|
v ∈ valeurs(A)
v∈valeurs(A)
c ∈ classes(Sv)
Je ne pense pas que cette amélioration-ci ait réellement une influence en termes de performances lors d’un programme mais c’est plus facile de faire les calculs à la main avec cette formule. La double somme peut faire un petit peu peur, mais ce n’est pas bien compliqué : ça veut dire qu’on fait la somme sur tous les v, et que pour chaque v, on ajoute la somme sur tous les c.
PS : faites bien attention, ici c’est bien un indice sommatoire sur c dans les classes de Sv et plus juste dans S. La raison est bien simple, c’est ce qui est expliqué juste au-dessus, c’est lié à la double somme.
18
2. Une première version : ID3
Ces améliorations ne changent rien à l’algorithme. Ce sont juste de légères optimisations pour éviter de trop calculer. C’est pour ceux qui programment leur algorithme mais également pour ceux qui font leurs calculs sur papier et à la calculette (ou pour les plus balèzes, qui font les calculs de logarithmes avec leurs tables) et qui ne veulent pas tout le temps calculer les mêmes choses ce qui augmente la probabilité d’erreurs.
2.2. Une implémentation
###5. Implémentation
Je vais vous proposer une implémentation détaillée en python3. Je vas vous guider étape par étape dans la réalisation de ce programme. Et pour ceux qui ne savent pas vraiment programmer ce n’est pas grave, le code complet sera mis à la fin.
!
Le code que je vous propose est une implémentation que j’ai choisie et que j’ai développée. Elle n’est pas la plus performante mais les choix sont avant tout pédagogiques. Le code qui suit est pseudo-orienté objet (dans la mesures de ce que Python permet), il vous faut être relativement à l’aise avec cette notion pour pouvoir le comprendre !
####5.1. Les types de données nécessaires
Commençons par déterminer de quelles structures de données nous allons avoir besoin. Voici ce que je propose, je vous laisse le lire, puis j’expliquerai.
* enfants: dict * attribut_testé: str
1 classe Nœud: 2 3 4 5 classe Feuille: 6 7 8 classe Exemple: 9 10 11
* étiquette: str * attributs: dict
* étiquette: str
3.
Publicité
ici, la classification discrète s’oppose à la classification continue. Les mathématiques discrètes concernent les opérations sur des ensembles finis (ex : les possibilités d’un jet de dé : {1, 2, 3, 4, 5, 6}) alors que les mathéma- tiques continues concernent les opérations sur des ensem