Ministère de l'Enseignement Supérieur et de la Recherche Scientifique

Institut Supérieur d’Informatique de Mahdia

Cours
Machine Learning

Dr. Mohamed Sofien Boutaib

2022-2023
 2

Partie II : Arbre
de décision
 3

Plan
•  Composants

•  Construction

•  Classification

•  Élagage

•  Attributs à valeurs continues

•  Attributs à valeurs manquantes

•  Bagging et boosting
 Introduction
Arbre de décision est une technique de classification en
apprentissage supervisé

Utilisation dans le domaine de l’intelligence artificielle

Diviser pour régner

 Traitement des problèmes complexes.

 Expression simple de la connaissance.
 Facilité dans la compréhension et l’interprétation des résultats.
 Participation des experts dans l’élaboration des règles.
 Applications

⚫ Gestion de crédits
⚫ Diagnostic médical
⚫ Analyse du marché
⚫ Contrôle de production
Composants
 Composants
Représente tout
l’ensemble
d’apprentissage
Racine
Représente des  Test sur les attributs
sous-ensembles
d’apprentissage

Nœuds de décision Nœuds feuilles

 Tests sur les attributs  Classes

Branches
 Valeurs de l’attribut
 Ensemble d’apprentissage
Attributs
Revenu Propriété Crédit non Classes
remboursé
Elevé Supérieur Non C1
Valeurs des attributs

Elevé Supérieur Oui C2

Elevé Supérieur Non C1
Elevé Inférieur Oui C2
Moyen Supérieur Non C1
Moyen Supérieur Oui C2
Moyen Inférieur Non C2
Moyen Inférieur Oui C2
Faible Inférieur Non C3
Faible Inférieur Oui C3
C1: Attribuer tout le crédit.
C2: Attribuer une partie crédit.
C3: Ne pas attribuer le crédit.
Arbre de décision
Propriété

Supérieur Inférieur

Crédit non
remboursé Revenu

Oui Non Elevé Moyen Faible

C2 C1 C2 C2 C3
Construction
 Construction d’un arbre de décision

Problème
⚫Apprendre un arbre de décision à partir d’un ensemble
d’apprentissage.

Objectif

⚫Être efficace en généralisation

Être capable de classer correctement un nouvel

objet (exemple).
 Un algorithme horrible!!

⚫ Générer tous les arbres de décision possibles.

⚫ Tester combien chaque arbre décrit l’ensemble d’apprentissage.

⚫ Choisir le meilleur arbre de décision.

Trop coûteux voire

impossible
 Un meilleur Algorithme

⚫Choisir le meilleur attribut.

⚫ Partitionner l’ensemble d’apprentissage.

⚫ Répéter jusqu’à ce que chaque élément de l’ensemble
d’apprentissage soit correctement classé.

Mais comment ?
 Algorithmes
Top Down Induction of Decision Trees (TDIDT)
Diviser pour régner (Induction descendante)

⚫ ID3 (Quinlan, 1979)

⚫ CART (Breiman et al., 1984)
⚫ ASSISTANT (Bratko, 1984)
⚫ C4.5 (Quinlan, 1993)
 Procédure de construction (1)
Processus récursif

⚫L'arbre commence à un nœud représentant toutes les données.

⚫ Si les objets sont de la même classe, alors le nœud devient une
feuille libellée par le nom de la classe.

⚫Sinon, sélectionner les attributs qui séparent le mieux les objets

en classes homogènes.

⚫ La récursion s'arrête quand au moins l’un des critères d’arrêt est

vérifié.
 Procédure de construction (2)
⚫Recherche à chaque niveau, l’attribut le plus discriminant.

⚫tPartition (données T)
⚫ Si tous les éléments de T sont dans la même classe alors retour;

⚫Pour chaque attribut A, évaluer la qualité du partitionnement sur A;

⚫ Utiliser le meilleur partitionnement pour diviser T en T1, T2, …Tk;

⚫Pour i = 1 à k faire Partition(Ti);

Paramètres
Mesure de sélection
d’attributs

Stratégie de partitionnement

Critères d’arrêt
 Comment choisir l’attribut ?
Pourquoi
?
⚫ Personne ne le sait !!

⚫ Plusieurs mesures ont été proposées.

⚫Gain d’information

⚫Indice de Gini

⚫Ratio de gain
 Mesure de l’information
⚫ L’entropie de Shannon exprime la quantité d’information.

Le nombre de bits nécessaires pour coder l’information.

6 3
La probabilité de tirer une boule bleue est
6 2 4
2 1
La probabilité de tirer une boule rouge est
62 4
 Apport de l’information
⚫Nombre de bits nécessaires pour distinguer chaque boule parmi N:
⚫P bits permettent de coder 2P informations.
⚫log2(N) bits permettent de coder N informations.
⚫Si je tire une boule (parmi N boules) et que je ne connais que sa couleur (par
exemple elle est rouge), l’information acquise sera:
log2(N) bits - log2(Nr) bits

C’est une Car je connais que

boule c’est une boule rouge

⚫Si je tire une boule au hasard et qu’on me donne sa couleur, l’information

acquise sera:
Prob(Bleue) (log2(N) - log2(Nb)) + Prob(Rouge)(log2(N)- log2(Nr))
3 (log 8 – log 6) + 1 (log2 8 – log2 2)
2 2
4 4
 Exemple
? ?

Prob(Bleue) (log2(N) - log2(Nb)) + Prob(Rouge)(log2(N)- log2(Nr))

Nb (log N ) Nr (log N ) Nb (log Nb) Nr (log Nr )

2 + 2 - 2 - 2
N Nb N Nr N N N N
- Prob(Bleue) log2(Prob(Bleue)) - Prob(Rouge)log 2(Prob(Rouge))
3 (log 3 ) 1 1 )
- 2 - (log2
4 4 4 4
C’est la quantité d’information apportée par la couleur.
 Mesure de l’information
Si on a n classes (C1, C2,.., Cn) de probabilités respectives p1, p2,.., pn,
la quantité d’information relative à la connaissance de la classe est
définie par l’entropie d’information:

I = -p log2 p
i = 1..n

I = 0 quand  i/ pi = 1 Une seule

classe

Classes
I est maximal quand  i/ pi = 1/n équiprobables
 Gain d’information (ID3)
⚫ freq(T, Cj): Nombre d’objets de T appartenant à la classe Cj.
⚫L’information relative à T est définie:
n
Quantité moyenne Info(T) = -  freq(T, Cj) log freq(T, Cj)
2
d’information nécessaire j=1
pour identifier la classe |T| |T|
d’un objet de T

⚫Une mesure similiaire de T après partition selon l’attribut A

(contenant n valeurs) est:
InfoA(T) =  |Ti| Info(Ti)
iD |T| A

DA =Domaine de valeurs de l’attribut A.

⚫Le gain d’information mesure le gain obtenu suite au partitionnement
selon l’attribut A.
Gain(T, A) = Info(T) – InfoA(T)
On sélectionne l’attribut offrant le plus de gain.
 Attributs multivalués
 Le Critère de gain d’information présente une limite.

Il favorise les attributs ayant

plusieurs valeurs

⚫ Lorsqu’un attribut a plusieurs valeurs possibles, son gain peut

être très élevé, car il classifie parfaitement les objets.

⚫ Par contre, ça peut générer un arbre de décision d'une

profondeur de 1 (ou faible) qui ne sera pas très bon pour les
instances futures.
 Ratio de Gain (C4.5)
⚫Une mesure de l’information contenue dans l’attribut A (mesure de
dispersion) est définie:
|Ti|
Split Info(T, A) = -  log2 |Ti|
iDA |T| |T|

⚫Le ratio de gain mesure le gain calibré par Split Info.

Gain(T, A)
Gain Ratio(T, A) =
Proportion d’information
Split Info(T, A)
génerée par T et utile
pour la classification

On sélectionne l’attribut offrant le plus de ratio de gain.

 Stratégie de partitionnement
⚫Pour chaque valeur de l’attribut, on va associer une branche dans
l’arbre.

⚫Problème avec les attributs continus.

Découper en sous-ensembles ordonnés

Quand s’arrêter ?
Si tous les objets appartiennent à la même classe.

S’il n’y a plus d’attributs à tester.

Feuille
vide
Il n'y a pas d'objets avec la valeur d'attribut.
Tous les ratios de
gain sont  0
Absence d’apport informationnel des attributs.
 Info
Revenu Propriété Crédit non Classe
remboursé
Elevé Supérieur Non C1
Elevé Supérieur Oui C2
Elevé Supérieur Non C1
Elevé Inférieur Oui C2
Moyen Supérieur Non C1
Moyen Supérieur Oui C2
Moyen Inférieur Non C2
Moyen Inférieur Oui C2
Faible Inférieur Non C3
Faible Inférieur Oui C3

3
Info(T) = -  freq(T, Cj) log freq(T, Cj)
2
j=1
|T| |T|

Info(T) = - 3/10 log2 3/10 - 5/10 log2 5/10 - 2/10 log2 2/10 = 1.485
 InfoRevenu(T)
InfoRevenu(T) =  |Ti| Info(T )
Revenu Propriété Crédit non Classe i
remboursé
iDRev enu |T|
Elevé Supérieur Non C1 DRevenu ={Elevé, Moyen, Faible}
Elevé Supérieur Oui C2 Revenu
Elevé Supérieur Non C1
Elevé Inférieur Oui C2
Elevé Moyen Faible
Moyen Supérieur Non C1
Moyen Supérieur Oui C2
Moyen Inférieur Non C2
Moyen Inférieur Oui C2 Info (T Elevé) Info(T Moyen) Info(T Faible)
Faible Inférieur Non C3
Faible Inférieur Oui C3

Info(TElevé) = - 2/4 log2 2/4 - 2/4 log2 2/4 = 1

Info(TMoyen) = - 1/4 log2 1/4 - 3/4 log2 3/4 = 0.812
Info(TFaible) = - 2/2 log2 2/2 = 0

InfoRevenu(T)= 4/10 Info (TElevé) + 4/10 Info (TMoyen) +2/10 Info (TFaible)
 Gain ratio(Revenu)
Revenu Propriété Crédit non Classe
remboursé
Elevé Supérieur Non C1
Elevé Supérieur Oui C2
Elevé Supérieur Non C1
Elevé Inférieur Oui C2
Gain(T, Revenu) = Info(T) – InfoRevenu(T)
Moyen Supérieur Non C1 = 0.761
Moyen Supérieur Oui C2
Moyen Inférieur Non C2
Moyen Inférieur Oui C2
Faible Inférieur Non C3
Faible Inférieur Oui C3

|Ti|
Split Info(T, Revenu) = -  log2 |Ti|
iDRev enu |T| |T|
Split Info(T, Revenu) = - 4/10 log2 4/10 - 4/10 log2 4/10 - 2/10 log2 2/10 = 1.522
0.761
Gain Ratio(T, Revenu) = = 0.5
 InfoPropriété(T)
Revenu Propriété Crédit non Classe |T|i
remboursé Info Propriété(T) =  Info(T)i
Elevé Supérieur Non C1
|T|
iDPropriété

Elevé Supérieur Oui C2 DPropriété ={Supérieur, Inférieur}

Elevé Supérieur Non C1
Elevé Inférieur Oui C2
Moyen Supérieur Non C1 Propriété
C2
Moyen Inférieur Non C2 Supérieur Inférieur
Moyen Inférieur Oui C2
Faible Inférieur Non C3
Faible Inférieur Oui C3 Info (T Inférieur)
Info(T Supérieur)

Info(TSupérieur) = - 3/5 log2 3/5 - 2/5 log2 2/5 = 0.971

Info(TInférieur) = - 3/5 log2 3/5 - 2/5 log2 2/5 = 0.971

InfoProrpiété(T)= 5/10 Info(TSupérieur) + 5/10 Info(TInférieur) = 0.971

Gain ratio(T, Crédit non remboursé)
Revenu Propriété Crédit non Classe
remboursé
Elevé Supérieur Non C1 Gain(T, Crédit non remboursé) =
Elevé Supérieur Oui C2 Info(T) – InfoCrédit non remboursé(T) = 0.439
Elevé Supérieur Non C1
Elevé Inférieur Oui C2
Moyen Supérieur Non C1
Moyen Supérieur Oui C2
Moyen Inférieur Non C2
Moyen Inférieur Oui C2
Faible Inférieur Non C3
Faible Inférieur Oui C3

|Ti| log |Ti|

Split Info(T, Crédit non remboursé) = -  2
|T|
iDCrédit non
remboursé
|T|
Split Info(T, Crédit non remboursé) = - 5/10 log2 5/10 - 5/10 log2 5/10 = 1
0.439
Gain Ratio(T, Crédit non remboursé) = = 0.439
1
 Arbre de décision: Niveau 1 Revenu Propriété Crédit non Classe
remboursé
Gain Ratio(T, Revenu) = 0.5 Elevé Supérieur Non C1
Elevé Supérieur Oui C2
Gain Ratio(T, Propriété) = 0.514 Elevé Supérieur Non C1
Elevé Inférieur Oui C2
Moyen Supérieur Non C1
Gain Ratio(T, Crédit non remboursé) = 0.439 Moyen Supérieur Oui C2
Moyen Inférieur Non C2
Propriété Moyen Inférieur Oui C2
Racine Faible Inférieur Non C3
Faible Inférieur Oui C3

Supérieur Inférieur

Revenu Propriété Crédit non Classe Revenu Propriété Crédit non Classe
rembours rembours
é é
Elevé Supérieur Non C1 Elevé Inférieur Oui C2
Elevé Supérieur Oui C2 Moyen Inférieur Non C2
Elevé Supérieur Non C1 Moyen Inférieur Oui C2
Moyen Supérieur Non C1 Faible Inférieur Non C3
Moyen Supérieur Oui C2 Faible Inférieur Oui C3
 Propriété = Supérieur (1)
Revenu Propriété Crédit non Classe
remboursé
Elevé Supérieur Non C1
Elevé Supérieur Oui C2
Elevé Supérieur Non C1
Moyen Supérieur Non C1
Moyen Supérieur Oui C2

Info(TSupérieur) = Info(S) = - 3/5 log2 3/5 - 2/5 log2 2/5 = 0.971

 Propriété = Supérieur (2)
Revenu Propriété Crédit non Classe
remboursé
Elevé Supérieur Non C1
Elevé Supérieur Oui C2
Elevé Supérieur Non C1
Moyen Supérieur Non C1
Moyen Supérieur Oui C2

InfoRevenu(SElevé)=- 2/3 log2 2/3 - 1/3 log2 1/3 = 0.918

InfoRevenu(SMoyen) = - 1/2 log2 1/2 - 1/2 log2 1/2 = 1

InfoRevenu(SFaible) = 0
InfoRvenu(S)= ((3/5) * 0.918) + ((2/5) * 1) + (0*0) = 0.951
Gain(S, Revenu) = 0.02
Split Info(S, Revenu) = - 3/5 log2 3/5 - 2/5 log2 2/5 - 0 = 0.971

Gain Ratio(S, Revenu) = 0.02

 Propriété = Supérieur (3)
Revenu Propriété Crédit non Classe
remboursé
Elevé Supérieur Non C1
Elevé Supérieur Oui C2
Elevé Supérieur Non C1
Moyen Supérieur Non C1
Moyen Supérieur Oui C2

InfoCrédit non remboursé(SOui)=- 2/2 log2 2/2 = 0

InfoCrédit non remboursé(SNon)=- 3/3 log2 3/3 = 0

InfoCrédit non remboursé(S)= ((3/5) * 0) + ((2/5) * 0) = 0

Gain(S, Crédit non remboursé) = 0.971

Split Info(S, Crédit non remboursé) = - 2/5 log2 2/5 - 3/5 log2 3/5 = 0.971
Gain Ratio(S, Crédit non remboursé) = 1
Arbre de décision: Niveau 2 (1)
Gain Ratio(S, Revenu) = 0.02
Gain Ratio(S, Crédit non remboursé) = 1
Revenu Propriété Crédit non Classe
remboursé
Propriété
Elevé Supérieur Non C1
Elevé Supérieur Oui C2
Elevé Supérieur Non C1
Supérieur Inférieur
Moyen Supérieur Non C1
Moyen Supérieur Oui C2

Crédit non
Revenu Propriété Crédit non Classe
remboursé remboursé
Elevé Inférieur Oui C2
Moyen Inférieur Non C2
Oui Non Moyen Inférieur Oui C2
Faible Inférieur Non C3
Faible Inférieur Oui C3
Revenu Propriété Crédit non Classe Revenu Propriété Crédit non Classe
remboursé remboursé
Elevé Supérieur Oui C2 Elevé Supérieur Non C1
Moyen Supérieur Oui C2 Elevé Supérieur Non C1
Moyen Supérieur Non C1
Arbre de décision: Niveau 2 (2)
Propriété

Supérieur Inférieur

Crédit non
Revenu Propriété Crédit non Classe
remboursé rembours
é
Elevé Inférieur Oui C2
Oui Non Moyen Inférieur Non C2
Moyen Inférieur Oui C2
Faible Inférieur Non C3
Faible Inférieur Oui C3
C2 C1
 Propriété = Inférieur (1)
Revenu Propriété Crédit non Classe
remboursé
Elevé Inférieur Oui C2
Moyen Inférieur Non C2
Moyen Inférieur Oui C2
Faible Inférieur Non C3
Faible Inférieur Oui C3

Info(TInférieur) = Info(I) = - 3/5 log2 3/5 - 2/5 log2 2/5 = 0.971

 Propriété = Inférieur (2)
Revenu Propriété Crédit non Classe
remboursé
Elevé Inférieur Oui C2
Moyen Inférieur Non C2
Moyen Inférieur Oui C2
Faible Inférieur Non C3
Faible Inférieur Oui C3

InfoRevenu(IElevé)=- 1/1 log2 1/1 = 0

InfoRevenu(IMoyen) = - 2/2 log2 2/2 = 0
InfoRevenu(IFaible) = - 2/2 log2 2/2 = 0
InfoRevenu(I)= ((1/5) * 0) + ((2/5) * 0) + ((2/5) * 0) = 0
Gain(I, Revenu) = 0.971
Split Info(I, Revenu) = - 1/5 log2 1/5 - 2/5 log2 2/5 - 2/5 log2 2/5 = 1.522
Gain Ratio(I, Revenu) = 0.638
Propriété = Inférieur (3)
Revenu Propriété Crédit non Classe
remboursé
Elevé Inférieur Oui C2
Moyen Inférieur Non C2
Moyen Inférieur Oui C2
Faible Inférieur Non C3
Faible Inférieur Oui C3

InfoCrédit non remboursé(IOui)=- 2/3 log2 2/3 - 1/3 log2 1/3 = 0.918

InfoCrédit non remboursé(INon)=- 1/2 log2 1/2 - 1/2 log2 1/2= 1

InfoCrédit non remboursé(I)= ((3/5) * 0.918) + ((2/5) * 1) = 0.951
Gain(I, Crédit non remboursé) = 0.02

Split Info(I, Crédit non remboursé) = - 3/5 log2 3/5 - 2/5 log2 2/5 = 0.971
Gain Ratio(I, Crédit non remboursé) = 0.02
Arbre de décision: Niveau 2 (3)
Gain Ratio(S, Revenu) = 0.638
Gain Ratio(S, Crédit non remboursé) = 0.02
Propriété Revenu Propriété Crédit non Classe
remboursé
Elevé Inférieur Oui C2
Moyen Inférieur Non C2
Supérieur Inférieur Moyen Inférieur Oui C2
Faible Inférieur Non C3
Faible Inférieur Oui C3
Crédit non
remboursé Revenu

Oui Non Elevé Faible

Moyen

Revenu Propriété Crédit non Classe Revenu Propriété Crédit non Classe
C2 C1 remboursé remboursé
Elevé Inférieur Oui C2 Faible Inférieur non C3
Faible Inférieur Oui C3

Revenu Propriété Crédit non Classe

remboursé
Moyen Inférieur non C2
Inférieur Oui C2
Moyen
Arbre de décision final
Propriété

Supérieur Inférieur

Crédit non
remboursé Revenu

Oui Non Elevé Moyen Faible

C2 C1 C2 C2 C3
 Travail à faire
1) Construire l’arbre de décision correspondant à l’ensemble d’apprentissage
suivant :
Age Concurrence Type Profit
Agé Non Software Baisse
Moyen Oui Software Baisse
Moyen Non Hardware Hausse
Agé Non Hardware Baisse
Récent Non Hardware Hausse
Récent Non Software Hausse
Moyen Non Software Hausse
Récent Oui Software Hausse
Moyen Oui Hardware Baisse
Agé Oui Software Baisse
 Algorithmes incrémentaux
⚫ Comment traiter des objets qui arrivent continûment
(dans l’ensemble d’apprentissage)?
L’ensemble d’apprentissage n’est pas complet.

⚫ ID4 (Schlimmer et Fisher, 1986)

⚫ ID5 (Utgoff, 1988)

⚫ ID5R (Utgoff, 1989)

L’ordre ne doit pas faire

varier le résultat
Classification
 Classification (1)
⚫ Classification basée sur une séquence de questions
portant sur un attribut.
⚫ La question est représentée par un nœud.

⚫ On prend la branche qui correspond à la réponse jusqu’à la

question suivante.

⚫ La feuille désigne la classe correspondant à l’objet à

classer.
Organiser les questions/réponses sous la forme d’un arbre.
Trouver le chemin relatif à l’objet à
classer menant de la racine à
l’une des feuilles de l’arbre
 Classification (2)
Propriété

Supérieur Inférieur

Crédit non
remboursé Revenu

Oui Non Elevé Moyen Faible

C2 C1 C2 C2 C3
À classer ?
Revenu Propriété Crédit non Classe
remboursé
Moyen Supérieur Non ?
Faible Inférieur Oui ?
 Convertir l’arbre en règles (1)

⚫ Représenter la connaissance sous la forme de Si….alors.

⚫ Une règle est créée pour chaque chemin de la racine

jusqu’à la feuille.

⚫ Les feuilles contiennent la classe à prédire.

⚫ Les règles sont plus faciles à comprendre et à interpréter.

 Convertir l’arbre en règles (2)
Propriété

Supérieur Inférieur

Crédit non
remboursé Revenu

Oui Non Elevé Moyen Faible

C2 C1 C2 C2 C3
Si (Propriété = Supérieur)  (Crédit non remboursé = Oui) alors C2
Si (Propriété = Supérieur)  (Crédit non remboursé = Non) alors C1
Si (Propriété = Inférieur)  (Revenu = Elevé) alors C2
Si (Propriété = Inférieur)  (Revenu = Moyen) alors C2
Si (Propriété = Inférieur)  (Revenu = Faible) alors C3
Elagage
 Pourquoi élaguer ?
Problème de sur-apprentissage (overfitting)
⚫Améliorer un modèle en le rendant meilleur sur l’ensemble
d’apprentissage mais il sera de plus en plus compliqué.

 Plusieurs branches. Il faut élaguer !!

 Arbre illisible.

 Faible résultat de classification.

⚫Réduire la taille de l’arbre. Rendre l’arbre plus

compréhensible.
⚫Améliorer la performance.
Mesurer la performance sur un ensemble différent de l’ensemble
d’apprentissage.
 Élagage d’un arbre
Objectif : minimiser la longueur de l’arbre

⚫ Cette méthode coupe des parties de l'arbre en choisissant un noeud

et en enlevant tout son sous-arbre.
Ce noeud devient une feuille et on lui attribue la valeur de
classification qui revient le plus souvent.

⚫ Des noeuds sont enlevés seulement si l'arbre résultant n'est pas pire
que l'arbre initial sur les exemples de validation.

⚫ On continue tant que l'arbre résultant offre de meilleurs résultats sur

les exemples de validation.

Réduire l'arbre en enlevant des branches qui auraient été

ajoutées par une erreur dans les objets d’apprentissage.
 Comment élaguer ?
Pré-élagage (pre-pruning)
⚫Arrêter le développement d’un noeud.
⚫Ne pas partitionner si le résultat va s’affaiblir
S’arrêter avant d’engendrer
Créer une feuille si la classe est
un nœud inutile
majoritairement représentée (seuil).
Post-élagage (post-pruning)
⚫ Élaguer après la construction de l’arbre en entier, en remplaçant les sous-
arbres satisfaisant le critère d’élgage par un noeud.
⚫ Pour chaque noeud de décision, voir si ça sera meilleur de le
remplacer par:
Générer l’arbre entier,
⚫Une feuille. puis élaguer
⚫Un de ses fils (le plus fréquent).
 Méthodes d’élagage
⚫ MCCP: Minimal Cost Complexity Pruning (Breiman, 1984)

⚫ MEP: Minimum Error Pruning (Niblett et Bratko, 1986)

⚫ CVP: Critical Value Pruning (Mingers, 1987)

⚫ PEP: Pessimistic Error Pruning (Quinlan, 1987)

⚫ REP: Reduced Error Pruning (Quinlan, 1987, 1993)

⚫ EBP: Error Based Pruning (Quinlan, 1993)

 Mesures de qualité de l’arbre
⚫ PCC: Pourcentage de Classifcation Correcte.

⚫Complexité
⚫Taille de l’arbre
⚫Nombre de feuilles

⚫Temps

⚫Trouver un arbre de décision minimal consistant avec

l’ensemble d’apprentissage est un problème NP-complet.
 Travail à faire
Expliquer la différence entre chacune des méthodes d’élagage suivantes
- MCCP
- MEP
- CVP
- PEP
- REP
- EBP

Solution :
Se baser sur J. Mingers, An empirical comparison of pruning methods for
decision tree induction, Machine Learning, 4, 227-243, 1989.
Attributs à valeurs
continues
Problème des attributs continus
⚫Seuils au lieu d’une infinité de valeurs.
⚫Certains attributs sont continus.
Découper en sous-ensembles ordonnés.

⚫Division en segments [a0,a1[, [a1,a2[, …., [an-1,an].

⚫Utiliser moyenne, médiane, …

⚫Investiguer différents cas et retenir le meilleur.

Attributs à valeurs continues
● On utilise un point de coupe pour obtenir une discrétisation des
variables continues.
 Ex: la variable Température est continue et on a les 6
exemples suivants.
Température 40 48 60 72 80 90
JouerTennis Non Non Oui Oui Oui No
n
 On met les valeurs en ordre croissant et on regarde les
endroits ou la classe change de valeur. À ces endroits, on
choisit la médiane comme valeur de coupe.

 On compare toutes les valeurs de coupe et on choisit celle qui

apporte le plus grand gain d'information.
 Travail à faire
Soient les valeurs de l’attribut Température:

Objet Température Jouer

O1 15 Oui
O2 20 Oui
O3 5 Non
O4 30 Non
O5 9 Non
O6 35 Non
Appliquer la procédure de traitement des attributs continus sur cet exemple.
 Solution (1)
Il faut tout d’abord ordonner selon la valeur de l’attribut (ordre croissant)
Objet Température Jouer
O3 5 Non
O5 9 Non
O1 15 Oui
O2 20 Oui
O4 30 Non
O6 35 Non
Il y a 2 coupures binaires possibles avec changement de classe, il faut voir
laquelle apporte le meilleur gain ?
Puisque la valeur de info est toujours la même, on se contente de trouver
quelle coupure présente une valeur d’infoTempérature minimale.
Les coupures sont 12 et 25 (où il y a changement de classe).
 Solution (2)
Info(T, 12) = 2/6 Info(T, <12) + 4/6 Info(T, >12)

Info(T, <12) = 0
Info(T, >12)= -2/4log 2/4 -2/4log 2/4 =1
Info(T, 12) = 0.666

Info(T, 25) = 4/6 Info(T, <25) + 2/6 Info(T, >25)

Info(T, <25) = -2/4 log 2/4 -2/4 log 2/4 =1
Info(T, >25) = 0
Info(T, 25) = 0.666
On peut aussi utiliser le ratio de gain donc calculer le split info.

Donc ici on peut choisir l’une des coupures 12 ou 25

Attributs à valeurs
manquantes
 Valeurs manquantes
d'attributs
 Attribuer la valeur la plus fréquente parmi les exemples du
noeud

 Attribuer la valeur la plus fréquente dans l’ensemble

d’apprentissage.

 Attribuer une probabilité pour chaque valeur de l’attribut.

Bagging et boosting
 Bagging
Bagging = Bootsrap aggregation

 Echantillon Bootstrap = Un sous-ensemble d’apprentissage.

 Génération de k échantillons à partir de l’ensemble d’apprentissage.

 Pour chaque échantillon, construire l’arbre de décision correspondant

 La décision finale pour la classe d’un nouvel objet est obtenue par
vote majoritaire.

Le bagging améliore la précision d’un classifieur instable.

 Boosting
 C’est une approche collaboratrice contrairement au bagging
(compétitive).

 Les sous classifieurs sont introduits un à la fois et travaillent sur

des sous-ensembles différents.

 Chaque nouveau sous-classifieur s’occupe des objets mal

classés.

L’intérêt d’appliquer le boosting quand les classifieurs présentent

de mauvais résultats.
 Les classifieurs peuvent être de types différents.
Conclusion et perspectives (1)
⚫Applicables à des variables quantitatives et qualitatives.

⚫Intelligibilité de la procédure de décision (traduction sous

forme de règles).

⚫Rapidité de décision.

⚫Très utilisés en data mining (recherche d’informations dans

de grandes bases de données hétérogènes).
Conclusion et perspectives (2)
 Arbres de décision et attributs continus (Fayyad, Irani, 1992;
Quinlan, 1993).

 Arbres de décision et élagage (Mingers, 1989).

 Arbres de décision et Bagging (Quinlan, 1997).
 Arbres de décision et Boosting (Quinlan, 1997).
 Arbres de décision multivariés (Brodley et Utgoff, 1995).
 Arbres de décision avec options (Kohavi et Kunz, 1997).
.
.
.
Conclusion et perspectives (3)
•  Arbres de décision et théories de
l’incertain.
•  Arbres de décision probabilistes (Quinlan, 1990).
•  Arbres de décision flous (Y. Yuan, M. J. Shaw, 1995;
Janikow, 1998).
•  Arbres de décision crédibilistes (Elouedi, Mellouli, Smets,
2000. Denoeux, M. Skarstein-Bjanger, 2000).

•  Arbres de décision possibilistes (Ben Amor, BenFerhat,

Elouedi, 2004, Jenhani et al. 2007).
•  Arbres de décision qualitatifs avec options (Jenhani,
Elouedi, Ben Amor, Mellouli, 2005).