Apprentissage par arbre de

décision

Hicham BEHJA
Terminologie: Techniques de l’ECD
Auteurs Auteurs traduits et Analyse des données
anglo-saxon certains auteurs à la française
francophones

Clustering Segmentation Classification

Classification Classification Classement, analyse

discriminante

Decision trees Arbres de décision Segmentation

2
 Terminologie: Techniques de l’ECD

– Définition:
● Opération qui permet de placer chaque individu de la population étudiée dans une
classe, parmi plusieurs classes prédéfinies.

– Exemple:
● Client acheteur, non acheteur
● Client bon payeur, mauvais payeur
● Client fidèle, infidèle à l’entreprise

– Méthodes
● Arbres de décision
● Réseaux de neurones
● Analyse factorielle et analyse en composantes principales

3
 Terminologie: Techniques de l’ECD

– Définition:
● Regrouper les individus d’une population en un nombre limité de groupes, les
segments (ou cluster, ou partitions)
● Les clusters sont découverts automatiquement
● Les clusters regroupent des individus ayant des caractéristiques similaires et
séparent les individus ayant des caractéristiques différentes.
● La segmentation est utile:
– Pour avoir une compréhension d’ensemble de sa clientèle
– Pour constituer des panels représentatifs
– Méthodes
● Segmentation neuronale
● Segmentation hiérarchique ascendante
● Segmentation relationnelle

4
 Terminologie: types d’attributs
● Attribut qualitatif: si on ne peut pas faire une moyenne; sa valeur est d’un
type définie en extension (une couleur, marque d’une voiture,…).
● Attribut quantitative : un entier, un réel, ... ; il peut représenter un salaire,
une surface, un nombre d’habitants, ...
– On peut donc appliquer les opérateurs arithmétiques habituels sur les attributs
quantitatifs, ce qui n’est pas le cas des attributs qualitatifs.
● Un attribut peut également être un enregistrement (une date par exemple),
donc composé lui-même de sous-attributs (jour, mois, année dans le cas
d’une date), sur lequel on peut définir les opérateurs arithmétiques
habituels.

🡨 Quantitatif ne signifie pas forcément « numérique » et, réciproquement,

numérique ne signifie pas forcément quantitatif : un code postal est
numérique, mais pas quantitatif.

5
 Classification par
Arbre de décision
● On se donne un ensemble X de N exemples notés xi dont les P attributs sont
quantitatifs ou qualitatifs. Chaque exemple x est étiqueté, c’est-`a-dire qu’il lui est
associée une « classe » ou un « attribut cible » que l’on note y.

● A partir de ces exemples, on construit un arbre dit « de décision » tel que :

– chaque noeud correspond à un test sur la valeur d’un ou plusieurs attributs ;
– chaque branche partant d’un noeud correspond à une ou plusieurs valeurs de ce test ;
– à chaque feuille est associée une valeur de l’attribut cible.

● L’arbre de décision peut être ensuite exploité de différentes manières :

1. en y classant de nouvelles données ;
2. en faisant de l’estimation d’attribut ;
3. en en extrayant un jeu de règles de classification concernant l’attribut cible
4. en interprétant la pertinence des attributs

6
 Un exemple :
Détection de la grippe
● Apparition soudaine de fièvre élevée
● Le patient est fatigué
● Rhinorrhée (nez qui coule)
● Toux
● Douleurs à la gorge
● Enrouement, douleurs dorsales, des membres et céphalées

⇒Grippe

7
Représentation sous forme
d’arbre
fièvre

toux fatigue

Nez qui coule

angine Maux de gorge

Courbatures et
maux de tête

grippe

8
 Autre exemple :
la ballade du chien
● Attributs
– quel temps fait-il ? {pluvieux, ensoleillé, couvert}
– Température extérieure : attribut numérique
– Voisin parti avec son chat : attribut booléen

● Décision à prendre
– Sortir ou non le chien

9
 Arbre de décision
Quel temps fait-il ?

couvert Ensoleillé pluvieux

Température ? Voisin absent ? Je reste chez moi

non
> 10 degré ≤ 10 degré
oui
Je reste chez moi

Je sors le chien

Je sors le chien
Je reste chez moi

10
 Construction de l’arbre de
décision
Algorithme de base

A= MeilleurAttribut(Exemples)
Affecter A à la racine
Pour chaque valeur de A, créer un nouveau noeud fils
de la racine
Classer les exemples dans les noeuds fils
Si tous les exemples d’un noeud fils sont homogènes,
affecter leur classe au noeud,
sinon recommencer à partir de ce noeud

11
 Construction de l’arbre de
décision
Algorithme de base

A= MeilleurAttribut(Exemples)
Affecter A à la racine
Pour chaque valeur de A, créer un nouveau noeud fils
de la racine
Classer les exemples dans les noeuds fils
Si tous les exemples d’un noeud fils sont homogènes,
affecter leur classe au noeud,
sinon recommencer à partir de ce noeud

12
 Construction de l’arbre de
décision
Définition de l’entropie

Remarques:

13
 Construction de l’arbre de
décision
Généralisation de l’entropie

Gain d’information:

14
 Construction de l’arbre de
décision
● Plus ce gain est grand, plus le partitionnement
de la population selon cet attribut entraîne des
sous-ensembles homogènes.

15
Base d’exemples

16
 Construction de l’arbre de
décision
● Exemple : supposons que X soit constitué de 14
exemples, 9 positifs et 5 négatifs. Parmi ces
exemples, 6 positifs et 2 négatifs prennent la
valeur « oui » pour l’attribut a, tandis que les
autres exemples prennent la valeur « non » pour
cet attribut.

17
Construction de l’arbre de
décision

18
 Construction de l’arbre de
décision

1. Création d’une racine

2. Les exemples n’étant ni tous positifs, ni tous négatifs, l’ensemble des attributs n’étant
pas vide, on calcule les gains d’information pour chaque attribut :
Attribut Gain
Ciel 0.246
Humidité 0.151
Vent 0.048
Température 0.029

3. Donc, la racine de l’arbre de décision testera l’attribut « Ciel » ;

4. L’attribut « Ciel » peut prendre trois valeurs. Pour « Ensoleillé », ID3 est appelé
récursivement avec 5 exemples : {x1, x2, x8, x9, x11}). Les gains d’information des 3
attributs restants sont alors :
Attribut Gain
Humidité 0.970
Vent 0.570
Température 0.019

19
 Construction de l’arbre de
décision
(Rappel : le gain d’info est ici calculé uniquement sur les exemples
dont l’attribut « Ciel » vaut « Ensoleillé », soit XCiel=Ensoleillé
avec notre notation.)
L’attribut « Humidité » sera donc choisi ; on continue la construction
de l’arbre de décision récursivement ;

4. Pour la branche « Pluie » partant de la racine, ID3 est appelé

récursivement avec 5 exemples : {x4, x5, x6, x10, x14} ; on
continue la construction de l’arbre de décision récursivement ;
5. Pour la branche « Couvert » partant de la racine, ID3 est appelé
récursivement avec 4 exemples : {x3, x7, x12, x13} ; dans ce
dernier cas, tous les exemples sont positifs : on affecte donc tout de
suite la classe « oui » à cette feuille.

20
Construction de l’arbre de
décision

21
 Interprétation de l’arbre
● Remarquons que l’arbre de décision qui vient d’être
construit nous donne des informations sur la pertinence
des attributs vis-à-vis de la classe:
– l’attribut « Température » n’étant pas utilisé dans l’arbre ; ceci
indique que cet attribut n’est pas pertinent pour déterminer la
classe.
– si l’attribut « Ciel » vaut « Ensoleillé », l’attribut « Vent » n’est
pas pertinent ;
– si l’attribut « Ciel » vaut « Pluie », c’est l’attribut « Humidité »
qui ne l’est pas.

22
 Utilisation de l’arbre de décision
pour classer une donnée
Algorithme de Classification d’une donnée dans un arbre de décision

Nécessite: 2 paramètres : arbre de décision AD, exemple x

// on utilise une variable nc (noeud courant) pour parcourir l’arbre

nc 🡨 racine (AD)
tant-que nc # feuille faire
en fonction de l’attribut testé dans nc et de sa valeur dans x, suivre l’une
des branches de nc. Le noeud atteint devient nc
fin tant-que
retourner étiquette(nc)

23
 Utilisation de l’arbre de décision
pour classer une donnée

● Par exemple, on peut prédire la classe pour les

données suivantes :
– (Ensoleillé, Fraîche, Elevée, Fort) est classée comme
« non » ;
– (Ensoleillé, Fraîche, Normale, Fort) est classée comme
« oui » ;
– (Pluie, Chaude, Normale, Faible) est classée comme
« oui » ;
– (Pluie, Fraîche, Elevée, Fort) est classée comme « oui ».

24
 Exercice
● Une banque dispose des informations suivantes sur un ensemble de ses clients :

● L’attribut client indique le numéro du client ; l’attribut M indique la moyenne des crédits
sur le compte du client ; l’attribut A donne la tranche d’âge ; l’attribut R décrit la localité du
client ; l’attribut E possède la valeur oui si le client possède un niveau d’études supérieur au
bac ; l’attribut I (la classe) indique si le client effectue ses opérations de gestion de compte
via Internet.
● Question 1 : quelle est l’entropie de la population ?
● Question 2 : pour la construction de l’arbre de décision, utilisez-vous l’attribut numéro de
client ? Pourquoi ?
● Question 3 : lors de la construction de l’arbre de décision, quel est l’attribut à tester à la
racine de l’arbre ?
● Question 4 : construire l’arbre de décision complet.
25
 Construction d’un arbre de
décision en présence d’attributs
numériques
● ID3 ne prend pas en compte les attributs de type
numérique (que les attributs qualitatifs)
● Le successeur C4.5 de ID3 prend en compte les attributs de
type numérique, des attributs dont l’arité est élevée (voire
infinie).
● La construction d’un arbre de décision par C4.5 est
identique dans son principe à la construction par ID3
● Dans le cas de C4.5, un noeud de l’arbre de décision peut
contenir un test du fait que la valeur d’un attribut
numérique est inférieure à un certain seuil :
– cela correspond donc à un nouveau pseudo-attribut binaire.

26
 Test d’un attribut numérique
•Jeu de données « jouer au tennis ? » avec des attributs
quantitatifs et nominaux.

27
 Test d’un attribut numérique
Jour Température « Jouer au
● Considérons les tennis? »

exemples dont 1 27.5 Non

l’attribut «Ciel» vaut
« Ensoleillé », soit 2 25 Non

l’ensemble 8 21 Non
XCiel=Ensoleillé
d’exemples ayant un 9 19.5 Oui

seul attribut
11 22.5 Oui
numérique comme suit

28
 Test d’un attribut numérique
Température Jour « Jouer au
● On commence par trier tennis? »

les exemples sur la 19.5 9 Oui

valeur de leur attribut
numérique. A chaque 21 8 Non

attribut, on associe le 22.5 11 Oui

numéro de son
exemple associé ainsi 25 2 Non

que la valeur de
27.5 1 Non
l’attribut cible :

29
 Test d’un attribut numérique
● On détermine le seuil s pour partitionner cet ensemble d’exemples.
C4.5 utilise les règles suivantes :
– ne pas séparer deux exemples successifs ayant la même classe ; donc, on ne
peut couper qu’entre les exemples x9 et x8, x8 et x11, x11 et x2 ;
– si on coupe entre deux valeurs v et w (v < w) de l’attribut, le seuil s est fixé à
v (on aurait pu aussi utiliser (v+w)/2 ) ;
– choisir s de telle manière que le gain d’information soit maximal.
● Remarque :
– une fois le seuil s fixé et le noeud créé, chaque sous-arbre pourra à nouveau
tester la valeur de cet attribut ;
– contrairement au cas des attributs qualitatifs qui produisent des noeuds ayant
autant de branches que l’attribut prend de valeurs différentes, l’ensemble des
valeurs prises par un attribut numérique est coupé en deux : chaque partie
peut donc encore être raffinée jusqu’à ne contenir que des exemples ayant
même valeur cible.

30
 Test d’un attribut numérique
● Application : l’entropie de l’ensemble d’exemples est :

● Pour s = 21, le gain d’information est :

● Avec

● Et

● Soit

31
 Test d’un attribut numérique
● De la même manière, en fonction du seuil, le gain d’information est alors :

● C4.5 effectue ce traitement pour chaque attribut quantitatif et détermine

donc pour chacun un seuil produisant un gain d’information maximal.
● Le gain d’information associé à chacun des attributs quantitatifs est celui
pour lequel le seuil entraîne un maximum.
● Finalement, l’attribut choisi (parmi les quantitatifs et les nominaux pour
lesquels le principe est identique ID3) est celui qui produit un gain
d’information maximal.

32
 Test d’un attribut numérique
Arbre de décision obtenu pour des attributs numériques sur
le jeu de données « jouer au tennis ? ».

33
 Test d’un attribut numérique
● Extension de l’algorithme C4.5
● En présence d’attribut numérique ou d’attribut d’arité
élevée, ceux-ci sont automatiquement favorisés pour
être sélectionnés comme test dans les noeuds.
● Calcul de la fonction Rapport de gain

● Où

34
 Valeurs d’attributs
manquantes
● Plusieurs solutions peuvent être envisagées, les plus
générales étant :
– on laisse de côté les exemples ayant des valeurs manquantes ;
ennuyeux car le nombre d’exemples diminue ;
– le fait que la valeur de l’attribut soit manquante est une
information en soit : on ajoute alors une valeur possible à
l’ensemble des valeurs de cet attribut qui indique que la valeur est
inconnue ;
– la valeur la plus courante pour l’attribut en question parmi les
exemples classées dans ce noeud est affectée à la place de la
valeur manquante ;
– les différentes valeurs observées de cet attribut parmi les
exemples couverts par le même noeud sont affectées avec des
poids différents en fonction de la proportion d’exemples de
l’ensemble d’apprentissage couverts par ce noeud pour les
différentes valeurs de cet attribut.
35
 Valeurs d’attributs
manquantes
● Pour calculer le gain d’information, on ne
tient compte que des exemples dont
l’attribut est valué. Soit X l’ensemble
d’exemples couverts par le nœud courant
(dont on est en train de déterminer l’attribut
à tester) et les exemples dont
l’attribut est valué. On redéfinit :

36
 Valeurs d’attributs
manquantes
● Supposons que l’exemple x12 ait ? à la place
de Couvert comme valeur de son attribut «
Ciel ». Déterminons le test à placer en
racine de l’arbre de décision.
● L’entropie de l’ensemble d’apprentissage X
est maintenant :

37
 Valeurs d’attributs
manquantes
● Demeurant l’attribut fournissant un gain
maximal, « Ciel » est placé à la racine de
l’arbre.
● L’exemple 12 est affecté avec les poids 5/13 ,
3/13 et 5/13 à chacune des branches,
respectivement « Ensoleillé », « Couvert » et
«Pluie» ; les autres exemples sont affectés à leur
branche respective avec un poids 1 pour chacun.

38
Classification d’une donnée ayant
des attributs non valués
● On se place ici non plus dans la phase de construction de
l’arbre de décision, mais lors de son utilisation pour prédire la
classe d’une donnée.
● Lors de sa descente dans l’arbre, si un noeud teste un attribut
dont la valeur est inconnue, C4.5 estime la probabilité pour la
donnée de suivre chacune des branches en fonction de la
répartition des exemples du jeu d’apprentissage couverts par
ce noeud. Cela détermine une fraction de donnée qui poursuit
sa descente selon chacune des branches.
● Arrivé aux feuilles, C4.5 détermine la classe la plus probable à
partir de ces probabilités estimées.
● Pour chaque classe, il fait la somme des poids ; la classe
prédite est celle dont le poids est maximal.

39
Classification d’une donnée ayant
des attributs non valués
● Dans l’arbre de décision obtenu sur « jouer au
tennis ? » avec des attributs nominaux, classons la
donnée ( Ciel =?, Température =Tiède, Humidité
=?, Vent = Faible ).
● Le noeud racine testant l’attribut « Ciel », sa
valeur étant inconnue dans cette donnée à classer,
on calcule la proportion d’exemples correspondant
à chaque valeur :
– 5 « Ensoleillé » ;
– 4 « Couvert » ;
– 5 « Pluie ».

40
 Classification d’une donnée ayant
des attributs non valués
● Donc, on poursuit la classification en transmettant les poids 5/14 vers le noeud
testant l’attribut « Humidité », 4/14 le long de la branche « Couvert » vers l’étiquette
« oui » et 5/14 vers le noeud testant l’attribut « Vent ».
● La valeur de l’attribut « Humidité » est inconnue également. Parmi les exemples «
Ensoleillé », il y en a 3 dont l’attribut « Humidité » vaut « Elevée », 2 dont cet
attribut vaut « Normale », soit 3/5 et 2/5 respectivement. Puisque 5/14 exemple a
suivi cette branche depuis la racine, on obtient 5/14×3/5 = 3/14 exemple atteignant l’
étiquette « non » et 5/14 × 2/5 = 1/7 exemple atteignant l’étiquette « oui ».

● L’attribut « Vent » a la valeur « Faible » ; le 5/14 d’exemple qui ont suivi cette
branche depuis la racine est donc classé comme « oui ».

● En résumé, il y a 3/14 exemple qui atteint une étiquette « non » et 1/7 + 4/14 + 5/14
= 11/14 exemple qui atteint une étiquette « oui ».
● On en conclut que la classe la plus probable de cette donnée est « oui ».

41
 ID3 vs. C4.5
● ID3 construit un arbre de décision :
– les attributs doivent tous être qualitatifs et ils sont considérés comme
nominaux ;
– ne peut pas prendre en charge des exemples ou des données dans lesquels
il manque la valeur d’attributs ;
– utilise les notions d’entropie et de gain pour déterminer l’attribut à tester
dans chaque noeud.
● En ce qui concerne C4.5 :
– les attributs peuvent être qualitatifs ou quantitatifs ;
– peut utiliser des exemples dans lesquels la valeur de certains attributs est
inconnue lors de la construction de l’arbre de décision ;
– peut prédire la classe de donnée dont la valeur de certains attributs est
inconnue ;
– utilise le rapport de gain pour déterminer l’attribut à tester dans chaque
noeud.

42
 Exercice
● Récupérer le source de C4.5, y implanter et effectuer une
étude expérimentale.
● Construction incrémentale d’un arbre de décision
– On suppose que les exemples sont disponibles non plus tous à la
fois mais obtenus un par un (par exemple, un toutes les heures). On
veut construire un arbre de décision en utilisant les exemples
disponibles à un moment donné qui sera complété lorsqu’un
nouvel exemple sera obtenu.
– Imaginer un algorithme pour cela.

– Naturellement, l’algorithme commencera par construire un arbre

dès l’obtention du premier exemple. Cet arbre initial sera ensuite
modifié s’il le faut à la réception du deuxième exemple, ...

43