Module: intelligence artificielle

Chapter7: Les arbres de décision

Master Sciences des données et analytiques

Réalisé par: AGUERCHI SAIDA

BENAGUERRI Safaa

Département Informatique
École Supérieure de Technologie-Safi
 L'apprentissage automatique

L'apprentissage automatique (Machine Learning) est une branche de l'intelligence artificielle qui permet à une machine
d'apprendre à partir de données pour effectuer des prédictions ou prendre des décisions sans être explicitement
programmée.

Artificial Intelligence

Machine Learning

2
Les types d'apprentissage automatique

Apprentissage supervisé :Les données d'entraînement sont étiquetées, ce qui signifie qu'elles contiennent déjà les
réponses correctes. Le modèle apprend à associer des entrées à des sorties.

Exemples : Classification (spam ou non-spam), régression (prédire le prix d'une maison).

Apprentissage non supervisé :Les données ne sont pas étiquetées. Le modèle doit découvrir des structures ou des
relations dans les données.

Exemples : Clustering (groupement des clients en fonction de leurs comportements), réduction de dimensions.

3
Les types d'apprentissage automatique

4
 Applications principales de l’apprentissage supervisé

a. Classification: Utilisée pour prédire des catégories ou des classes discrètes.

Exemples : Spam/Non Spam, Jouer/Ne pas jouer, reconnaissance des chiffres.

b. Régression: Utilisée pour prédire des valeurs continues.

Exemples : Prédire le prix d'une maison, le revenu annuel.

c. Optimisation des décisions: Décider la meilleure action à entreprendre dans un contexte donné.

Exemples : Choix optimal d'une offre pour un client, ou d'une stratégie d'investissement.

d. Analyse prédictive: Utilisée pour prévoir des événements futurs en se basant sur des données historiques.

Exemples : Prévision des ventes.

5
LES ARBRES D E D É C I S I O N

◾ Les arbres de décision sont des méthodes d’apprentissage supervisés utilisées pour résoudre des problèmes de classification et
de régression.

◾ Ils sont été largement utilisés dans les années 1960-1980 pour la construction de systèmes [Link] règles sont introduites
manuellement,pour cette raison ce modèle a perdu sa popularité après les années 80.L’apparition des méthodes mathématiques
pour construire les arbres de décision fait revenir ce modèle à la bataille des algorithmes de l’apprentissage automatique.

◾ Une arbre de décision est essentiellement constitué :

• de nœuds non terminaux représentant les tests sur les variables explicatives,ou attributs.
• de branches portant les valeurs des attributs,nécessairement discrètes,.
• de nœuds terminaux représentant la classification résultante.

6
 Variables (attributs) Classe(groupe)
Individus (instances)

Les attributs

Les valeurs de l’attribut

Classe = feuille = nœud pur 7

AVANTAGES ET I N C O N V É N I E N T S

Avantages :
◾ Facile à comprendre et à interpréter.
◾ Fonctionne pour des données numériques et catégoriques.
◾ Peu de prétraitement nécessaire.
Inconvénients :
◾ Sensible au surapprentissage (overfitting).
◾ Nécessite parfois une méthode de pruning (élagage) pour simplifier l’arbre.
◾ Les arbres non optimisés peuvent être biaisés sur des classes avec un nombre disproportionné d’exemples.

8
APPLICATIONS PRATIQUES

 Classification en apprentissage automatique

 Système de recommandation
 Aide à la décision dans les affaires
 Diagnostic et traitement
 Analyse des données financières
 Contrôle qualité et diagnostique industriel
 Jeux vidéo et intelligence artificielle (IA)
 Sécurité informatique

9
C O N S T R U C T I O N D’UN ARBRE DE DÉCISION

Étapes :

1. Choisir un attribut de division :

• L'attribut qui maximise la séparation des données.
• Utilisation de mesures comme l’entropie,le gain d’information.
2. Créer des branches basées sur les valeurs possibles de l’attribut.
3. Réitérer récursivement jusqu’à ce qu’une condition d’arrêt soit atteinte :
• Les données sont parfaitement séparées.
• Un seuil de profondeur est atteint.

10
 C O N C E P T S MATHÉMATIQUES IMPORTANTS

1. L’entropie de Shannon:

Les théories de Shannon étant à la base de l’algorithme ID3 et donc de C4.5.

L’entropie de Shannon est la plus connue et la plus appliquée. Elle définit d’abord la quantité d’information apportée
par un événement.

En général, si on nous donne une distribution de probabilité P = (p1, p2, ..., pn) et un échantillon S alors l’Information
portée par cette distribution, aussi appelée l’Entropie de P, est : Entropie(P) = - (p1×log (p1) + p2×log (p2) + ... +
pn×log (pn))

L’entropie note l’incertitude sur la valeur de la variable. 11

L’entropie pondérée
Lorsque l’on travaille avec des sous-ensembles pondérés (comme dans les algorithmes de construction d’arbres de
décision), l’entropie pondérée est utilisée. Elle permet de tenir compte de la taille relative des sous-ensembles. Pour
un ensemble S divisé en mmm sous-ensembles S1,S2,...,Sm l’entropie pondérée est donnée par :

|Sj|
Entropie pondéré(S)= σ𝒎 × 𝑬𝒏𝒕𝒓𝒐𝒑𝒊𝒆(S𝒋)
𝒋=𝟏 |S|

|Sj|
où |S| représente le poids du sous-ensemble S𝒋 ​ par rapport à l’ensemble S, et Entropie(S𝒋) est l’entropie pour ce
sous-ensemble.

12
Exemple : Un ensemble S contient 10 exemples répartis en 6 "Oui" et 4 "Non"

6 6 4 4
Entropie(S)=− log 2 10 + 10 log 2
10 10

Entropie(S)=−(0.6 × (−0.737)+0.4 × (−1.321))=0.971

13
2. Le Gain d’information G (p, T)

Il mesure la réduction de l’entropie lorsqu'un attribut est utilisé pour diviser les données.

On définit le gain pour un test T et une position p

14
 Exemple : Considérons un attribut A=Visibilité, avec les valeurs possibles : {Soleil,
Nuageux, Pluie}. Les données initiales sont divisées ainsi :

Visibilité Non Oui total

Soleil 1 2 3
•Entropie(Soleil)=−((1/3) log2​(1/3)​+2/3 ​log2​(2/3))≈0.918
Nuage 0 1 1 •Entropie(Nuageux)= 0 (toutes les instances sont "Oui").
•Entropie(Pluie)=1.
Pluie 1 1 2

Entropie pondérée pour visibilité :

3 1 2
Entropie(Visibilité)= (6 × 0,918 + 6 × 0 + 6 × 1)=0.792

Gain d'information :

Gain(S,Visibilité)=Entropie(S)− Entropie(Visibilité)=0.971−0.792=0.179

15
 A L G O R I T H M E ID3 (ITERATIVE D I C H O T O M I S E R 3)

L'algorithme ID3 (Iterative Dichotomiser 3) est un algorithme de construction d'arbres de décision utilisé pour la classification
supervisée. Il a été proposé par Ross Quinlan en 1986 et il est l'un des algorithmes les plus connus pour la construction d'arbres de
décision.

16
PRINCIPE D E ID3

Le principe de l’algorithme ID3 pour déterminer la variable de segmentation est de prendre la variable du gain
d’information maximum.

Les principales idées sur lesquels repose ID3 sont les suivantes :

 Dans l’arbre de décision chaque nœud correspond à un attribut non cible et chaque arc à une valeur possible de cet
attribut. Une feuille de l’arbre donne la valeur attendue de l’attribut cible pour l’enregistrement testé décrit par le
chemin de la racine de l’arbre de décision jusqu’ à la feuille.

 Dans l’arbre de décision, chaque nœud doit être associé l’attribut non cible qui apporte le plus d’information par
rapport aux autres attributs non encore utilisés dans le chemin depuis la racine.

 L’entropie est utilisée pour mesurer la quantité d’information apportée par un nœud.

17
EXEMPLE:

Supposons qu'on veut utiliser l’algorithme ID3 pour décider si le temps se prête à jouer un match. Au cours des deux
semaines, les données sont collectées pour aider ID3 à construire un arbre de décision (voir tableau 1).

La classification de la cible est "devrions-nous jouer un match?" qui peut être oui ou non.

Les attributs météorologiques sont la visibilité, la température, l'humidité et la vitesse du vent.

Ils peuvent prendre les valeurs suivantes:

• Visibilité = {Soleil, Couvert, Pluie}

• Température = {Chaud, Doux, Froid}
• Humidité = {Elevé, normale}
• Vent = {Faible, Fort}

18
Des exemples de l'ensemble S sont les suivants:
Jour Visibilité Température Humidité Vent Jouer

D1 Soleil Chaud Elevé Faible Non

D2 Soleil Chaud Elevé Fort Non

D3 Couvert Chaud Elevé Faible Oui

D4 Pluie Doux Elevé Faible Oui

D5 Pluie Froid Normale Faible Oui

D6 Pluie Froid Normale Fort Non

D7 Couvert Froid Normale Fort Oui

D8 Soleil Doux Elevé Faible Non

D9 Soleil Froid Normale Faible Oui

D10 Pluie Doux Normale Faible Oui

D11 Soleil Doux Normale Fort Oui

D12 Couvert Doux Elevé Fort Oui
D13 Couvert Chaud Normale Faible Oui
D14 Pluie Doux Elevé Fort Non

Tableau 1: L'ensemble de données S 19

Nous devons trouver l'attribut qui sera le nœud racine dans notre arbre de décision. Le gain est calculé pour les
quatre attributs:

𝐸𝑛𝑡𝑟𝑜𝑝𝑖𝑒(𝑆) =-9/14×log2(9/14)-5/14×log2(5/14)=0.94

 le gain pour le premier attribut(Visibilité) :

Calcule des entropies:

Entropie(SSoleil)= -2/5×log2(2/5)-3/5×log2(3/5)=0.9710

Entropie(Scouvert)= -4/4×log2(4/4)-0×log2(0)=0

Entropie(Spluie)= -3/5×log2(3/5)-2/5×log2(2/5)=0.9710

Gain(S, Visibilité) = Entropie (S)-5/14×Entropie (Ssoleil)-4/14×Entropie (Scouvert) -5/14×Entropie (Spluie)

=0.94 – (5/14×0.9710) - (4/14×0) – (5/14×0.9710)

Gain(S, Visibilité) = 0 .246 20

 Le gain pour le deuxième attribut (Vent ):

Entropie(SFaible)= - (6/8)×log2 (6/8) - (2/8)×log2 (2/8) = 0.811

Entropie(SFort)= - (3/6)×log2 (3/6) - (3/6)×log2(3/6) = 1.00

Gain(S, Vent) =Entropie(S)-(8/14)×Entropie(SFaible)-(6/14)×Entropie(SFort)

= 0.940 - (8/14)×0.811 - (6/14)×1.00

Gain(S, Vent) = 0.048

 Le gain pour le troisième attribut (Températeure ):

Entropie(SChaud)= -2/4×log2 (2/4) - 2/4×log2 (2/4)= 1

Entropie(SDoux)= -4/6×log2 (4/6) - 2/6×log2 (2/6)= 0.9183

Entropie(SDoux)= -3/4×log2 (3/4) - 1/4×log2 (1/4)= 0.8113

Gain(S, Température)=Entropie(S)-4/14×Entropie (SChaud)-6/14× Entropie(SDoux)-4/14×Entropie (SFroid)
=0.94-(4/14×1)-(6/14×0.9183)-(4/14×0.8113)
Gain(S, Température) = 0.0289 21
 Calcul pour le premier attribut(Humidité) :

Entropie(SElevé)= -3/7×log2 (3/7) - 4/7×log2 (4/7)= 0.9852

Entropie(SNormale)= -6/7×log2 (6/7) - 1/7×log2 (1/7)= 0.1515

Gain(S, Humidité) = Entropie(S) -7/14×Entropie(SElevé) -7/14×Entropie(SNormale)

= 0.94-7/14×0.9852-7/14×0.5917

Gain(S, Humidité) = 0 .1515

 L’attribut Visibilité a le gain le plus élevé, il est donc utilisé comme attribut de décision
dans le nœud racine de notre arbre.

 Depuis Visibilité a trois valeurs possibles, le nœud racine a trois branches (Soleil, Couvert,
Pluie).

22
visibilité

23
 Ainsi, en utilisant les trois nouveaux ensembles, le gain d'information sera calculé pour la température, le vent et
l'humidité. Par exemple, si nous voulons calculer le gain d'information de la température contre Soleil alors :

Entropie (SSoleil)=-2/5×log2(2/5)-3/5×log2(3/5)=0.971

Entropie(SChaud)=-0/2×log2(0/2)-2/2×log2(2/2)=0

Entropie(SDoux)=-1/2×log2(1/2)-1/2×log2(1/2)=1

Entropie (SFroid) =-1/1×log2(1/1)-0/1×log2(0/1) =0

Gain (SSoleil, Température)= Entropie (SSoleil) -2/5×Entropie (SChaud) -2/5×Entropie (SDoux)-1/5×Entropie (SFroid)
=0,971-2/5×0-2/5×1-1/5×0

Gain (SSoleil, Température) =0.571

 De la même façon on calcule le gain pour l’Humidité et le Vent et on trouve :

Gain (SSoleil, Vent) = 0.019 Gain (SSoleil, Humidité) = 0.970

24
 Humidité a le gain le plus élevé et, par conséquent, il est utilisé comme le nœud de décision.

 Ce processus se poursuit jusqu'à ce que toutes les données sont parfaitement classées ou
Jusqu'à épuisement d'attributs.
 On va calculer le gain d'information de l'humidité, Température et vent contre Pluie alors :

Entropie (SPluie)=-3/5×log2(3/5)-2/5×log2(2/5)=0.971

Entropie(SDoux) = -2/3×log2(2/3)-1/3×log2(1/3)=0.918

Entropie (SFroid) = -0/2×log2(0/2)-2/2×log2(2/2) =0

Gain (SPluie, Température) = Entropie (SPluie) -3/5×Entropie (SDoux) - 2/5×Entropie (SFroid)

=0,971-3/5×0.918-2/5×0

Gain (SPluie, Température) =0.420

 De la même façon on calcule le gain pour l’Humidité et le Vent et on trouve :

Gain (SPluie, Vent) = 0.971 Gain (SSoleil, Humidité) = 0.021 25

 Visibilité

Soleil Couvert Pluie

Humidité Oui Vent

Faible Fort
Normale Elevé

Non Oui Non

Oui

26
L’arbre de décision final obtenue par ID3
L'arbre de décision peut aussi être exprimé sous forme de règles:

• Si Visibilité = Ensoleillé et humidité = Elevé ALORS, Jouer= Non

• Si Visibilité = Ensoleillé et humidité = Normale ALORS, Jouer= Oui

• Si Visibilité = Couvert ALORS Jouer = Oui

• Si Visibilité = Pluie et le Vent =Fort, Jouer= Non

• Si Visibilité = Pluie et le Vent = Faible ALORS Jouer= Oui

27
 A L G O R I T H M E C4.5

C4.5 est un algorithme de construction d'arbres de décision proposé par Ross Quinlan en [Link] est une version
améliorée de l'algorithme ID3 et est utilisé pour la classification supervisée. C4.5 est l'un des algorithmes les plus populaires
pour l'apprentissage supervisé, particulièrement dans le domaine de l'intelligence artificielle et de l'extraction de
connaissances à partir de données.

28
Algorithme simplifié
 Soit T l'ensemble des instances d'entraînement.

 Choisir un attribut qui différencie le mieux les instances contenues dans T (C4.5 utilise le Gain pour déterminer cet
attribut).

 Créer un nœud d'arbre dont la valeur est l'attribut choisi.

 Créer des liens enfants à partir de ce nœud, chaque lien représentant une valeur unique de l'attribut choisi.

 Utiliser les valeurs des liens enfants pour subdiviser davantage les instances en sous-classes.

29
Le gain ratio
L'algorithme C4.5 est un algorithme d'apprentissage supervisé utilisé pour construire des arbres de décision. Une
des étapes importantes dans cet algorithme est le choix de l'attribut à utiliser pour diviser les données à chaque
nœud. Pour ce faire, C4.5 utilise une mesure appelée gain ratio.

Voici les étapes pour calculer le gain ratio :

1. Entropie de l'ensemble S
2. Gain d'information (Information Gain)
3. Split Information (Information sur la division)
4. Gain Ratio

30
1. Entropie de l'ensemble S

L'entropie mesure la quantité d'incertitude ou de désordre dans un ensemble de données S. Elle est calculée comme
suit :
𝒌

E(S)= ෍ pi​⋅log2​(pi​)
𝒊=𝟏
où :

•pi est la proportion des exemples appartenant à la classe i

•k est le nombre total de classes.

31
2. Gain d'information (Information Gain)

Le gain d'information est une mesure qui indique combien l'attribut A réduit l'entropie de l'ensemble S après une
division

Gain(S,A)= E(S)− Entropie(S,A)

• Entropie(S,A): c’est l’entropie après avoir divise les données selon l’attribue A

32
3. Split Information (Information sur la division)
La Split-Info (S, A) est une mesure qui évalue comment les données sont divisées (ou réparties) lorsqu’on utilise un
attribut A pour créer des sous-groupes.

Elle indique la pureté ou le désordre introduit par la division.

•Si un attribut divise les données en beaucoup de petits groupes, la Split-Info sera élevée.

•Si les groupes sont plus équilibrés et grands, la Split-Info sera plus faible.

Elle est utilisée pour normaliser l’Info-Gain afin d'éviter qu’un attribut avec trop de valeurs uniques ne soit
systématiquement favorisé.

𝒌
Sv Sv
SplitInfo(S,A)= ෍ log2( )
S S
𝒗∈𝑽
où :
•∣S∣: est la taille totale des données.
•∣Sv| :est la taille du sous-groupe i créé par l'attribut A.
•k est le nombre de sous-groupes créés. 33
[Link] Ratio

Enfin, le gain ratio est le rapport entre le gain d'information et la split information :

Gain(S,A)
GainRatio(S,A)=
SplitInfo(S,A)

où :

•Gain(S,A) : Gain d'information obtenu en divisant S selon l'attribut A.

•SplitInfo(S,A) : Information sur la division, mesurant la diversité des sous-ensembles formés par A

34
Remarques importantes :

1.Éviter les divisions par zéro : Si la SplitInfo(S,A)=0, l'attribut A n'est pas choisi.

[Link] utiliser le gain ratio ? Contrairement au gain d'information seul, le gain ratio pénalise les attributs

ayant de nombreuses valeurs uniques, évitant ainsi des divisions biaisées.

[Link] de l'attribut : C4.5 choisit l'attribut avec le plus haut gain ratio.

35
Exemple :
Problème : Prédire si une personne achète un ordinateur
Nous disposons d'un petit ensemble de données décrivant des clients avec deux attributs : Âge et Revenu, ainsi
qu'une classe cible "Achète un ordinateur ?" (Oui ou Non).

Client Âge Revenu Achète un ordinateur ?

1 Jeune Élevé Non
2 Jeune Moyen Oui
3 Jeune Faible Oui
:
4 Moyen Élevé Oui
5 Moyen Moyen Oui
6 Moyen Faible Non
7 Âgé Élevé Oui
8 Âgé Moyen Non
9 Âgé Faible Non

36
Étape 1 : Calcul de l'entropie totale de l'ensemble

Fréquence des classes :

•Total : 9 exemples.
∣Oui∣=5, | Non| = 4

37
Étape 2 : Calcul du Gain d'information pour chaque attribut
Attribut : Âge
Les valeurs possibles de Âge : {Jeune, Moyen, Ageˊ}
Sous-ensemble "Jeune" :

1. 3 exemples : 2 Oui,1 Non

•Sous-ensemble "Moyen" :
3 exemples : 2 Oui,1 Non E(Moyen)=0.918 (identique aˋ "Jeune" car me proportions)

•Sous-ensemble "Âgé" :
•3 exemples : 1 Oui,2 Non

Gain d'information pour "Âge" :

38
Attribut : Revenu

Les valeurs possibles de Revenu : {Élevé, Moyen, Faible}

1. Sous-ensemble "Élevé" :

3 exemples : 2 Oui,1 Non E(Élevé)=0.918

2. Sous-ensemble "Moyen" :

3 exemples : 2 Oui,1 Non E(Moyen)=0.918.

3. Sous-ensemble "Faible" :

3 exemples : Oui, 2 , 1 Non E(Faible)=0.918

Gain d'information pour "Revenu" :

39
Étape 3 : Calcul de la Split Information
Pour Âge :

1. Formule de Split Information

𝒌
Sv Sv
Splitinfo(S,X)= ෍ log2​( )
S S
𝒗∈𝑽
2. Données :
3
Trois sous-ensembles égaux pour Âge : 9=0.333

3. Calcul de Split Information :

Substituons dans la formule :

SplitInfo(S, Âge)= −(3⋅0.333⋅log 2(0,333)) = 1.583

Pour Revenu :

SplitInfo(S,Revenu)=SplitInfo(S,Age)= 1,583 (mêmes proportions). 40

 Étape 4 : Calcul du Gain Ratio
Pour Âge :

•Gain(S, Âge) = 0.073

•SplitInfo(S, Âge) = 1.58

Calcul du Gain Ratio :

Substituons les valeurs :

Pour Revenu :

41
Étape 5 : Choix du meilleur attribut

Les deux attributs ont des Gain Ratios égaux. Si cela se produit, on peut choisir arbitrairement ou utiliser une autre

métrique comme le Gain d'information brut

Arbre de décision final :

Pour cet exemple simple, le choix initial peut diviser les données selon Âge ou Revenu, ce qui donnera des feuilles
correspondant aux différentes valeurs des classes cibles

42
Les extensions de l’algorithme C4.5
C4.5 introduit un certain nombre d’extensions à ID3.

1. Les attributs de valeur inconnue:

Lors de la construction de l’arbre de décision, il peut arriver que certaines données aient des valeurs manquantes pour un
ou plusieurs attributs. C4.5 propose une approche spécifique pour ces cas :

1.Évaluation du gain :

1. Le gain est calculé pour un attribut en tenant compte uniquement des enregistrements pour lesquels cet
attribut a une valeur connue.

2. Cela signifie que les enregistrements avec une valeur manquante pour cet attribut sont ignorés lorsqu'on
mesure son utilité pour le fractionnement de l'arbre.

Exemple : Si un attribut A a une valeur inconnue pour 10 exemples sur un total de 100, alors le gain est calculé
en utilisant uniquement les 90 exemples restants. Les 10 exemples sont temporairement exclus de ce calcul.
43
2. Critère de gain ajusté pour les valeurs inconnues :

Lorsque des valeurs manquantes existent, un facteur d’ajustement F est introduit pour refléter la proportion
d'exemples ayant une valeur connue pour un attribut donné. Le nouveau critère de gain est alors :

Gain(X)=F⋅(E(S)−E(S,X))

Où :
•E(S) :est l'entropie initiale de l'ensemble de données T

•E(S,X)est l'entropie après division sur X

nombre d’exemples avec une valeur connue

•F= 𝐧𝐨𝐦𝐛𝐫𝐞 𝐭𝐨𝐭𝐚𝐥 𝐝′ 𝐞𝐱𝐞𝐦𝐩𝐥𝐞

44
Exemple 2 (C4.5):
Supposons que vous avez un jeu de données décrivant si une personne achète un produit. Les attributs sont :

1.Âge (Jeune, Moyen, Senior),

[Link] (Élevé, Moyen, Bas),
3.Étudiant (Oui, Non),
[Link]édit (Bon, Moyen, Mauvais).

Le label cible est Achat (Oui, Non).

Une partie des données ressemble à ceci

45
Étape 1 : Calcul de l'entropie initiale

La classe Achat a deux valeurs possibles : Oui et Non. Dans l'ensemble initial :

•Nombre total d'exemples : 6

•Distribution des classes :
• Oui : 3 (ligne 2, 3, 4)
• Non : 3 (ligne 1, 5, 6)

L'entropie initiale est donnée par la formule :

Entropie(T)=−∑pi * log⁡
2pi)

3 3 3 3
Entropie(T)= −(6 . log2​(6​))−((6 .log2​(6​))

Entropie(T)= −(0.5×1)−(0.5×1)=1

46
Étape 2 : Calcul du gain pour l'attribut « Revenu »

L'attribut Revenu a trois valeurs possibles : Élevé, Moyen, Bas. Cependant, la 5ᵉ ligne contient une valeur inconnue (?) alors
l’algorithme ignore cette ligne pour le calcul du gain.

Distribution des exemples avec des valeurs connues :

•Pour Élevé : 1 exemple (ligne 1, classe Non),

•Pour Moyen : 3 exemples (ligne 2, 3, 6 ; classes Oui, Oui, Non),
•Pour Bas : 1 exemple (ligne 4, classe Oui).

Calcul de l'entropie après division :

Entropie pour "Élevé" :

• 1 exemple, 100 % Non Entropie(Élevé)=0
Entropie pour "Moyen" :
• 3 exemples : 2 Oui, 1 Non.
2 2 1 1
Entropie(Moyen)=−( 3 . log2(3 ) ​)−( 3 ​.(log2( 3) )
Entropie(Moyen)=−(0.666×0.585)−(0.333×1.585)

Entropie(Moyen)≈0.918 47
Entropie pour "Bas" :

1 exemple, 100 % Oui. Entropie(Bas)=0

Entropie totale après division :

En pondérant selon la proportion des exemples dans chaque catégorie :

𝟏 𝟑 𝟏
Entropie (Revenu)= 𝟓 ​Entropie(Élevéˊ) + 𝟓 . Entropie(Moyen)+ 𝟓 . Entropie(Bas)

𝟏 𝟑 𝟏
Entropie(Revenu)= 𝟓 × 0+ 𝟓 ×0, 𝟗𝟖𝟏 + 𝟓 ×0

Entropie(Revenu)≈0.551

48
Étape 3 : Ajustement avec le facteur F

Si un grand nombre d'exemples avaient une valeur inconnue pour Revenu, un facteur F serait appliqué pour réduire
l’importance de cet attribut. Dans cet exemple :

 Nombre d'exemples avec une valeur connue pour Revenu : 5

 Nombre total d'exemples : 6
𝟓
F= 𝟔 ​≈0.833

Le gain ajusté devient :

Entropie(T)−Entropie(Revenu)=1.0−0.551=0.449

Gain(Revenu)=F × (Entropie(T)−Entropie(Revenu))

Gain′(Revenu)=0.833*0.449≈0.374

49
 [Link] attributs à valeur sur intervalle continu
Lorsqu'un attribut dans un jeu de données prend des valeurs continues (par exemple, un attribut Revenu ou Âge),
C4.5 gère ce cas en cherchant à diviser les valeurs de cet attribut en plusieurs intervalles et à choisir la division qui
permet de maximiser le gain d'information (ou le gain ratio).

1. Identifiez l'attribut continu:

Supposons que l'attribut Ci soit continu, et que les valeurs possibles de cet attribut dans les données
d'entraînement soient dans un intervalle continu.

Les valeurs de cet attribut dans l'ensemble des données sont triées dans l'ordre croissant : A1,A2,…,Am

Exemple : Pour un attribut A=Age

A=Age({22, 25, 28, 30, 35}), les seuils possibles sont :

Seuils : {(22+25)/2,(25+28)/2,(28+30)/2,(30+35)/2

50
 2. Partitionner les enregistrements en fonction des valeurs de l'attribut:

Pour chaque valeur Aj (qui correspond à une valeur particulière de l'attribut Ci dans l'ensemble trié), on divise les données
en deux groupes :

• Groupe 1 : Les enregistrements dont la valeur de Ci est inférieure ou égale à Aj (c'est-à-dire Ci≤Aj).
• Groupe 2 : Les enregistrements dont la valeur de Ci est supérieure à Aj​ (c'est-à-dire Cj > Aj).

Exemple : Pour T=26,5 :

•Gauche (A≤26.5) : {22,25}
•Droit (A>26.5) : {28,30,35}

3. Calculer le gain d'information ou le gain ratio

Pour chaque partition, on calcule le gain d'information ou le gain ratio de cette division. Ces mesures permettent de
quantifier l'impact de la partition sur la réduction de l'entropie (incertitude) dans les données.

L'objectif est de choisir la division qui permet de mieux distinguer les classes cibles (par exemple, Oui/Non pour une
décision de crédit).
51
 4. Sélectionner la partition qui maximise le gain:

Parmi toutes les partitions possibles (en fonction des différentes valeurs (Aj​), on choisit celle qui maximise le
gain d'information ou le gain ratio. Cela signifie qu'on cherche la division qui offre la réduction la plus
importante de l'entropie (ou l'augmentation de la pureté des sous-ensembles).

52
 Exemple 3(C4.5):
On va travailler avec le même exemple utilisé précédemment mais cette fois on va prendre des valeurs continues pour
l’attribut Humidité.
 Traiter les valeurs numériques (attribue à valeur continue)

Jour Visibilité Température Humidité Vent Jouer

D1 Soleil Chaud 85 Faible Non
D2 Soleil Chaud 90 Fort Non
D3 Couvert Chaud 78 Faible Oui
D4 Pluie Doux 96 Faible Oui
D5 Pluie Froid 80 Faible Oui
D6 Pluie Froid 70 Fort Non
D7 Couvert Froid 65 Fort Oui
D8 Soleil Doux 95 Faible Non
D9 Soleil Froid 70 Faible Oui
D10 Pluie Doux 80 Faible Oui
D11 Soleil Doux 70 Fort Oui
D12 Couvert Doux 90 Fort Oui
D13 Couvert Chaud 75 Faible Oui
D14 Pluie Doux 80 Fort Non
53
Tableau 2: L'ensemble de données S
 Comme C4.5 est une amélioration de ID3, alors la première étape de calcul de gain est la même sauf pour
les attributs à valeurs continues pare ce que ID3 ne gère pas ce genre d’attributs.
Dans cet exemple on va détailler le calcul de gain d’information pour un attribut à valeur continue.

Les résultats qu’on a trouvés précédemment :

𝐸𝑛𝑡𝑟𝑜𝑝𝑖𝑒(𝑆) =-9/14×log2(9/14)-5/14×log2(5/14)=0.94

 Calcul pour le premier attribut:

Gain(S, Visibilité)= Entropie (S)-5/14×Entropie (SSoleil ) -4/14×Entropie (SPluie ) -5/14×Entropie (Scouvert)

Gain(S, Visibilité)= 0 .246

 Calcul pour le deuxième attribut:

Gain(S, Vent) =Entropie(S)-(8/14)×Entropie(SFaible)-(6/14)×Entropie(SFort)

Gain(S, Vent) = 0.048

54
 Calcul pour le troisième attribut:
Gain(S,Température)=Entropie(S)-4/14*Entropie(SChaud)-6/14*Entropie(SDoux)- 4/14*Entropie (SFroid)

Gain(S, Température) = 0.0289

 Calcul pour le Quatrième attribut:
Gain(S, Humidité)= ?
Il faut maintenant trier les valeurs de l’attribut en ordre croissant, l'ensemble de valeurs est la suivante:
{65, 70, 70, 70, 75, 78, 80, 80, 80, 85, 90, 90, 95, 96}
Alors on va travailler avec l’ensemble suivant :{65, 70, 75, 78, 80, 85, 90, 95, 96}
On cherche à trouver la meilleur partition qui maximise le gain tel que l’ensemble d’apprentissage va vérifier
pour une valeur seuil Sj, Si ≤ Sj et Si > Sj
65 70 75 78 80 85 90 95 96
intervalle ≤ > ≤ > ≤ > ≤ > ≤ > ≤ > ≤ > ≤ > ≤ >
Oui 1 8 3 6 4 5 5 4 7 2 7 2 8 1 8 1 9 0
Non 0 5 1 4 1 4 1 4 2 3 3 2 4 1 5 0 5 0
Entropie 0 0.961 0.811 0.971 0.721 0.991 0.65 1 0.764 0.971 0.881 1 0.918 1 0.961 0 0.94 0
Info(S, T) 0.892 0.925 0.8950 0.85 0.838 0.915 0.929 0.892 0.94
Gain 0.048 0.015 0.045 0.09 0.102 0.025 0.011 0.048 0

Tableau 3: Calcul de gain pour l'attribue continue humidité algorithme C4.5 55

D’ où le Gain(S, Humidité)= 0.102

Alors l’attribue Visibilité a la plus grande valeur du Gain d’Information est le nœud racine de l’arbre

Visibilité

Soleil
Pluie
Couvert

Jour Température Humidité Vent Jouer

Jour Jour Température Humidité Vent Jouer
Température Humidité Vent Jouer
D1 Chaud 85 Faible Non
D3 Chaud 78 Faible Oui D4 Doux 96 Faible Oui
D5 Froid 80 Faible Oui
D2 Chaud 90 Fort Non
D7 Froid 65 Fort Oui D6 Froid 70 Fort Non
D8 Doux 95 Faible Non D12 Doux 90 Fort Oui D10 Doux 80 Faible Oui
D9 Froid 70 Faible Oui D13 Chaud 75 Faible Oui D14 Doux 80 Fort Non
D11 Doux 70 Fort Oui
Jouer ???
???

56
Jour Température Humidité Vent Jouer

D1 Chaud 85 Faible Non

D2 Chaud 90 Fort Non

D8 Doux 95 Faible Non

D9 Froid 70 Faible Oui

D11 Doux 70 Fort Oui

???

57
Ici aussi on procède comme ID3 sauf pour l’attribue Humidité, on calcule de la même manière pour le nouvel
ensemble de données :

𝐸𝑛𝑡𝑟𝑜𝑝𝑖𝑒(𝑆) =-2/5×log2 (2/5)-3/5×log2 (3/5)= 0.9710

70 85 90 95
intervalle ≤ > ≤ > ≤ > ≤ >

Oui 2 0 2 0 2 0 2 0
Non 0 3 1 2 2 1 3 0
Entropie 0 0 0.918 0 1 0 0.97 0
1

Info(S, T) 0 0.55 0.8 0.9710

Gain 0.9710 0.042 0.171 0

D’où la valeur de séparation est 70 et le Gain(S, Humidité)= 0.97

58
 Visibilité

Soleil Couvert Pluie

Humidité Oui Vent

≤ 70 >70 Faible Fort

Non Oui Non

Oui

59
L’arbre de décision final obtenue par C4.5
Comparaison entre différentes algorithmes

ID3 (Iterative Dichotomiser 3) C4.5

◾ Utilise l’entropie et le gain d’information pour ◾ Amélioration d’ID3.
choisir les divisions.
◾ Supporte les attributs numériques et catégoriques.
◾ Fonctionne uniquement avec des attributs
◾ Gère pas les données manquantes.
catégoriques.
◾ Ne gère pas les données manquantes.

60
T D : Arbres de décision

61