Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Data Mining
Modélisation supervisée : Les arbres de décision

Cabrel FOSSO1 Dorine MAGNI2 Idriss NANGO3 David DIONMAYE4

Université de Dschang
Faculté des Sciences
Département de Mathématiques et Informatique
[Link]

8 juin 2025

Université de Dschang Les arbres de déciision 8 juin 2025 1 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

1 Introduction

2 La modélisation supervisée

3 Les arbres de décision

4 Validation des arbres de décision

5 Synthèse

6 Conclusion

Université de Dschang Les arbres de déciision 8 juin 2025 2 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Historique et contexte

• Â Prédire l’avenir : quête éternelle.

Université de Dschang Les arbres de déciision 8 juin 2025 3 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Historique et contexte

• Â Prédire l’avenir : quête éternelle.

• ø 1950 : ordinateurs et régression.

Université de Dschang Les arbres de déciision 8 juin 2025 3 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Historique et contexte

• Â Prédire l’avenir : quête éternelle.

• ø 1950 : ordinateurs et régression.
• . Limites : complexité non capturée.

Université de Dschang Les arbres de déciision 8 juin 2025 3 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Historique et contexte

• Â Prédire l’avenir : quête éternelle. • j Perceptron : inspiré du cerveau.

• ø 1950 : ordinateurs et régression.
• . Limites : complexité non capturée.

Université de Dschang Les arbres de déciision 8 juin 2025 3 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Historique et contexte

• Â Prédire l’avenir : quête éternelle. • j Perceptron : inspiré du cerveau.

• ø 1950 : ordinateurs et régression. • Ç Défi : simplicité et puissance.
• . Limites : complexité non capturée.

Université de Dschang Les arbres de déciision 8 juin 2025 3 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Historique et contexte

• Â Prédire l’avenir : quête éternelle. • j Perceptron : inspiré du cerveau.

• ø 1950 : ordinateurs et régression. • Ç Défi : simplicité et puissance.
• . Limites : complexité non capturée.

⋆ Prêt pour une révolution ?

Université de Dschang Les arbres de déciision 8 juin 2025 3 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Problématique

⋆ Révolution : mais à quel prix ?

Université de Dschang Les arbres de déciision 8 juin 2025 4 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Problématique

⋆ Révolution : mais à quel prix ?

•  Simplicité : facile à comprendre.

Université de Dschang Les arbres de déciision 8 juin 2025 4 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Problématique

⋆ Révolution : mais à quel prix ?

•  Simplicité : facile à comprendre.

• 4 Interprétabilité : décisions claires.

Université de Dschang Les arbres de déciision 8 juin 2025 4 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Problématique

⋆ Révolution : mais à quel prix ?

•  Simplicité : facile à comprendre. • W Efficacité : ressources limitées.

• 4 Interprétabilité : décisions claires.

Université de Dschang Les arbres de déciision 8 juin 2025 4 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Problématique

⋆ Révolution : mais à quel prix ?

•  Simplicité : facile à comprendre. • W Efficacité : ressources limitées.

• 4 Interprétabilité : décisions claires. • ? Comment tout concilier ?

Université de Dschang Les arbres de déciision 8 juin 2025 4 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Problématique

⋆ Révolution : mais à quel prix ?

•  Simplicité : facile à comprendre. • W Efficacité : ressources limitées.

• 4 Interprétabilité : décisions claires. • ? Comment tout concilier ?

Û Une révolution à relever !

Université de Dschang Les arbres de déciision 8 juin 2025 4 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Vers une solution : Les arbres de décision

• ‹ Structure hiérarchique simple.

Université de Dschang Les arbres de déciision 8 juin 2025 5 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Vers une solution : Les arbres de décision

• ‹ Structure hiérarchique simple.

• [ Décisions lisibles et claires.

Université de Dschang Les arbres de déciision 8 juin 2025 5 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Vers une solution : Les arbres de décision

• ‹ Structure hiérarchique simple. • Ó Efficace sur gros volumes.

• [ Décisions lisibles et claires.

Université de Dschang Les arbres de déciision 8 juin 2025 5 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Vers une solution : Les arbres de décision

• ‹ Structure hiérarchique simple. • Ó Efficace sur gros volumes.

• [ Décisions lisibles et claires. • ✓ Réponse aux défis modernes.

Université de Dschang Les arbres de déciision 8 juin 2025 5 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Vers une solution : Les arbres de décision

• ‹ Structure hiérarchique simple. • Ó Efficace sur gros volumes.

• [ Décisions lisibles et claires. • ✓ Réponse aux défis modernes.

Ç L’IA réinventée !

Université de Dschang Les arbres de déciision 8 juin 2025 5 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

1 Introduction

2 La modélisation supervisée

3 Les arbres de décision

4 Validation des arbres de décision

5 Synthèse

6 Conclusion

Université de Dschang Les arbres de déciision 8 juin 2025 6 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

1 Introduction

2 La modélisation supervisée

3 Les arbres de décision

4 Validation des arbres de décision

5 Synthèse

6 Conclusion

Université de Dschang Les arbres de déciision 8 juin 2025 7 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

La modélisation supervisée : Définition

• [ Apprentissage à partir de données étiquetées.

Université de Dschang Les arbres de déciision 8 juin 2025 8 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

La modélisation supervisée : Définition

• [ Apprentissage à partir de données étiquetées.

• $ Prédire des étiquettes pour de nouvelles données.

Université de Dschang Les arbres de déciision 8 juin 2025 8 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

La modélisation supervisée : Définition

• [ Apprentissage à partir de données étiquetées.

• $ Prédire des étiquettes pour de nouvelles données.
• Guidé par un "professeur" (étiquettes).

Université de Dschang Les arbres de déciision 8 juin 2025 8 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

La modélisation supervisée : Définition

• [ Apprentissage à partir de données étiquetées.

• $ Prédire des étiquettes pour de nouvelles données.
• Guidé par un "professeur" (étiquettes).

 La base de l’IA prédictive !

Université de Dschang Les arbres de déciision 8 juin 2025 8 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Types de problèmes

• U Classification :

Université de Dschang Les arbres de déciision 8 juin 2025 9 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Types de problèmes

• U Classification :
• ¥ Malade ou non ?

Université de Dschang Les arbres de déciision 8 juin 2025 9 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Types de problèmes

• U Classification :
• ¥ Malade ou non ?
• Espèce de fleur.

Université de Dschang Les arbres de déciision 8 juin 2025 9 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Types de problèmes

• U Classification : • ¢ Régression :
• ¥ Malade ou non ?
• Espèce de fleur.

Université de Dschang Les arbres de déciision 8 juin 2025 9 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Types de problèmes

• U Classification : • ¢ Régression :
• ¥ Malade ou non ? • d Température future.
• Espèce de fleur.

Université de Dschang Les arbres de déciision 8 juin 2025 9 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Types de problèmes

• U Classification : • ¢ Régression :
• ¥ Malade ou non ? • d Température future.
• Espèce de fleur. • Ñ Prix d’une maison.

Université de Dschang Les arbres de déciision 8 juin 2025 9 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Étapes principales

• õ Collecte : données étiquetées.

Université de Dschang Les arbres de déciision 8 juin 2025 10 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Étapes principales

• õ Collecte : données étiquetées.

• Ó Entraînement : ajuster le modèle.

Université de Dschang Les arbres de déciision 8 juin 2025 10 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Étapes principales

• õ Collecte : données étiquetées.

• Ó Entraînement : ajuster le modèle.
• ✓ Évaluation : tester la performance.

Université de Dschang Les arbres de déciision 8 juin 2025 10 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Étapes principales

• õ Collecte : données étiquetées.

• Ó Entraînement : ajuster le modèle.
• ✓ Évaluation : tester la performance.

Ç Un processus clé !

Université de Dschang Les arbres de déciision 8 juin 2025 10 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Importance

• È Médecine : diagnostics.

Université de Dschang Les arbres de déciision 8 juin 2025 11 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Importance

• È Médecine : diagnostics.
• Finance : tendances boursières.

Université de Dschang Les arbres de déciision 8 juin 2025 11 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Importance

• È Médecine : diagnostics. • s Marketing : ciblage clients.

• Finance : tendances boursières.

Université de Dschang Les arbres de déciision 8 juin 2025 11 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Importance

• È Médecine : diagnostics. • s Marketing : ciblage clients.

• Finance : tendances boursières. • € Données  Décisions !

Université de Dschang Les arbres de déciision 8 juin 2025 11 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Importance

• È Médecine : diagnostics. • s Marketing : ciblage clients.

• Finance : tendances boursières. • € Données  Décisions !

⋆ Au cœur de l’IA !

Université de Dschang Les arbres de déciision 8 juin 2025 11 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

La modélisation supervisée

j Apprentissage guidé pour prédire l’avenir !

Université de Dschang Les arbres de déciision 8 juin 2025 12 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

La modélisation supervisée

j Apprentissage guidé pour prédire l’avenir !

Définition Types Étapes Impact

Université de Dschang Les arbres de déciision 8 juin 2025 12 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

1 Introduction

2 La modélisation supervisée

3 Les arbres de décision

4 Validation des arbres de décision

5 Synthèse

6 Conclusion

Université de Dschang Les arbres de déciision 8 juin 2025 13 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Arbres de décision : Définition et structure

• ‹ Structure arborescente :

Université de Dschang Les arbres de déciision 8 juin 2025 14 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Arbres de décision : Définition et structure

• ‹ Structure arborescente :
• ○ Nœuds : tests sur attributs.

Université de Dschang Les arbres de déciision 8 juin 2025 14 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Arbres de décision : Définition et structure

• ‹ Structure arborescente :
• ○ Nœuds : tests sur attributs.
• $ Arêtes : résultats des tests.

Université de Dschang Les arbres de déciision 8 juin 2025 14 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Arbres de décision : Définition et structure

• ‹ Structure arborescente :
• ○ Nœuds : tests sur attributs.
• $ Arêtes : résultats des tests.
• Feuilles : prédictions finales.

Université de Dschang Les arbres de déciision 8 juin 2025 14 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Arbres de décision : Définition et structure

• ‹ Structure arborescente : • ⋆ Avantages :

• ○ Nœuds : tests sur attributs.
• $ Arêtes : résultats des tests.
• Feuilles : prédictions finales.

Université de Dschang Les arbres de déciision 8 juin 2025 14 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Arbres de décision : Définition et structure

• ‹ Structure arborescente : • ⋆ Avantages :

• ○ Nœuds : tests sur attributs. • 4 Interprétable, intuitif.
• $ Arêtes : résultats des tests.
• Feuilles : prédictions finales.

Université de Dschang Les arbres de déciision 8 juin 2025 14 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Arbres de décision : Définition et structure

• ‹ Structure arborescente : • ⋆ Avantages :

• ○ Nœuds : tests sur attributs. • 4 Interprétable, intuitif.
• $ Arêtes : résultats des tests. •  Robustesse : données manquantes.
• Feuilles : prédictions finales.

Université de Dschang Les arbres de déciision 8 juin 2025 14 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Arbres de décision : Définition et structure

• ‹ Structure arborescente : • ⋆ Avantages :

• ○ Nœuds : tests sur attributs. • 4 Interprétable, intuitif.
• $ Arêtes : résultats des tests. •  Robustesse : données manquantes.
• Feuilles : prédictions finales. • 8 Stable face aux outliers.

Université de Dschang Les arbres de déciision 8 juin 2025 14 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Arbres de décision : Définition et structure

• ‹ Structure arborescente : • ⋆ Avantages :

• ○ Nœuds : tests sur attributs. • 4 Interprétable, intuitif.
• $ Arêtes : résultats des tests. •  Robustesse : données manquantes.
• Feuilles : prédictions finales. • 8 Stable face aux outliers.

Ç Un modèle puissant !

Université de Dschang Les arbres de déciision 8 juin 2025 14 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Exemple d’arbre de décision

Humidité

Élevée Normale

Météo Oui
Nuageux
Pluvieux
Ensoleillé
Oui Température

Non Moyen Frais

Oui Non

Université de Dschang Les arbres de déciision 8 juin 2025 15 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Fonctionnement des arbres de décision

• Û Sélection : attribut optimal.

Université de Dschang Les arbres de déciision 8 juin 2025 16 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Fonctionnement des arbres de décision

• Û Sélection : attribut optimal.

• ô Partition : divise en sous-groupes.

Université de Dschang Les arbres de déciision 8 juin 2025 16 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Fonctionnement des arbres de décision

• Û Sélection : attribut optimal.

• ô Partition : divise en sous-groupes.
• 5 Arrêt :

Université de Dschang Les arbres de déciision 8 juin 2025 16 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Fonctionnement des arbres de décision

• Û Sélection : attribut optimal.

• ô Partition : divise en sous-groupes.
• 5 Arrêt :
• ¥ Pureté : classe unique.

Université de Dschang Les arbres de déciision 8 juin 2025 16 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Fonctionnement des arbres de décision

• Û Sélection : attribut optimal.

• ô Partition : divise en sous-groupes.
• 5 Arrêt :
• ¥ Pureté : classe unique.
• Ì Profondeur max : limite taille.

Université de Dschang Les arbres de déciision 8 juin 2025 16 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Fonctionnement des arbres de décision

• Û Sélection : attribut optimal.

• ô Partition : divise en sous-groupes.
• 5 Arrêt :
• ¥ Pureté : classe unique.
• Ì Profondeur max : limite taille.
• ² Échantillons min : seuil données.

Université de Dschang Les arbres de déciision 8 juin 2025 16 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Fonctionnement des arbres de décision

• Û Sélection : attribut optimal.

• ô Partition : divise en sous-groupes.
• 5 Arrêt :
• ¥ Pureté : classe unique.
• Ì Profondeur max : limite taille.
• ² Échantillons min : seuil données.

Ç Décision structurée !

Université de Dschang Les arbres de déciision 8 juin 2025 16 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Critères de division

• ? Entropie : mesure du désordre.

k
X
− pi log2 (pi )
i=1

Université de Dschang Les arbres de déciision 8 juin 2025 17 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Critères de division

• ? Entropie : mesure du désordre.

k
X
− pi log2 (pi )
i=1

• + Gain d’info : réduction d’entropie.

X |Sv |
Entropie(S) − Entropie(Sv )
v |S|

Université de Dschang Les arbres de déciision 8 juin 2025 17 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Critères de division

• ? Entropie : mesure du désordre. • ÷ Ratio d’info : gain normalisé.

k
X Gain(S, A)
− pi log2 (pi ) SplitInfo(A)
i=1

• + Gain d’info : réduction d’entropie.

X |Sv |
Entropie(S) − Entropie(Sv )
v |S|

Université de Dschang Les arbres de déciision 8 juin 2025 17 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Critères de division

• ? Entropie : mesure du désordre. • ÷ Ratio d’info : gain normalisé.

k
X Gain(S, A)
− pi log2 (pi ) SplitInfo(A)
i=1
• ¡ Gini : impureté des classes.
• + Gain d’info : réduction d’entropie.
k
X |Sv |
p2i
X
Entropie(S) − Entropie(Sv ) 1−
v |S| i=1

Université de Dschang Les arbres de déciision 8 juin 2025 17 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Critères de division

• ? Entropie : mesure du désordre. • ÷ Ratio d’info : gain normalisé.

k
X Gain(S, A)
− pi log2 (pi ) SplitInfo(A)
i=1
• ¡ Gini : impureté des classes.
• + Gain d’info : réduction d’entropie.
k
X |Sv |
p2i
X
Entropie(S) − Entropie(Sv ) 1−
v |S| i=1

Ó Base des algorithmes !

Université de Dschang Les arbres de déciision 8 juin 2025 17 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

ID3 : Iterative Dichotomiser 3

• + Principe : max gain d’info

X |Sv |
Gain(S, A) = Entropie(S) − Entropie(Sv )
v |S|

Université de Dschang Les arbres de déciision 8 juin 2025 18 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

ID3 : Iterative Dichotomiser 3

• + Principe : max gain d’info

X |Sv |
Gain(S, A) = Entropie(S) − Entropie(Sv )
v |S|

• . Limite : sur-apprentissage (catégoriel).

Université de Dschang Les arbres de déciision 8 juin 2025 18 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

ID3 : Iterative Dichotomiser 3

• + Principe : max gain d’info

X |Sv |
Gain(S, A) = Entropie(S) − Entropie(Sv )
v |S|

• . Limite : sur-apprentissage (catégoriel).

• Â Complexité :

Université de Dschang Les arbres de déciision 8 juin 2025 18 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

ID3 : Iterative Dichotomiser 3

• + Principe : max gain d’info

X |Sv |
Gain(S, A) = Entropie(S) − Entropie(Sv )
v |S|

• . Limite : sur-apprentissage (catégoriel).

• Â Complexité :
• Ó Moyenne : O (A × N log N)

Université de Dschang Les arbres de déciision 8 juin 2025 18 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

ID3 : Iterative Dichotomiser 3

• + Principe : max gain d’info

X |Sv |
Gain(S, A) = Entropie(S) − Entropie(Sv )
v |S|

• . Limite : sur-apprentissage (catégoriel).

• Â Complexité :
• Ó Moyenne : O (A × N log N)
• W Pire : O (A × N 2 )

Université de Dschang Les arbres de déciision 8 juin 2025 18 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

ID3 : Iterative Dichotomiser 3

• + Principe : max gain d’info

X |Sv |
Gain(S, A) = Entropie(S) − Entropie(Sv )
v |S|

• . Limite : sur-apprentissage (catégoriel).

• Â Complexité :
• Ó Moyenne : O (A × N log N)
• W Pire : O (A × N 2 )

Ç Pionnier des arbres !

Université de Dschang Les arbres de déciision 8 juin 2025 18 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Exemple : Construction de l’arbre avec ID3 - Jeu de données

Jour Météo Température Humidité Jouer

1 Ensoleillé Chaud Élevée Non
2 Ensoleillé Chaud Normale Oui
3 Nuageux Chaud Élevée Oui
4 Pluvieux Moyen Élevée Oui
5 Pluvieux Frais Normale Oui
6 Pluvieux Frais Élevée Non
7 Nuageux Frais Normale Oui
8 Ensoleillé Moyen Élevée Non
9 Ensoleillé Frais Normale Oui
10 Pluvieux Moyen Normale Oui
11 Ensoleillé Moyen Normale Oui
12 Nuageux Moyen Élevée Oui
13 Nuageux Chaud Normale Oui
14 Pluvieux Moyen Élevée Non

Université de Dschang Les arbres de déciision 8 juin 2025 19 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Calcul de l’entropie initiale

• Distribution des classes (14 exemples) :

Université de Dschang Les arbres de déciision 8 juin 2025 20 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Calcul de l’entropie initiale

• Distribution des classes (14 exemples) :
• Jouer = Oui : 10 cas ( 10 ≈ 0.7143)
14

Université de Dschang Les arbres de déciision 8 juin 2025 20 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Calcul de l’entropie initiale

• Distribution des classes (14 exemples) :
• Jouer = Oui : 10 cas ( 10 ≈ 0.7143)
14
• Jouer = Non : 4 cas ( 4 ≈ 0.2857)
14

Université de Dschang Les arbres de déciision 8 juin 2025 20 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Calcul de l’entropie initiale

• Distribution des classes (14 exemples) :
• Jouer = Oui : 10 cas ( 10 ≈ 0.7143)
14
• Jouer = Non : 4 cas ( 4 ≈ 0.2857)
14
• Formule de l’entropie :
n
X
H(S) = − pi log2 pi
i=1

Université de Dschang Les arbres de déciision 8 juin 2025 20 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Calcul de l’entropie initiale

• Distribution des classes (14 exemples) :
• Jouer = Oui : 10 cas ( 10 ≈ 0.7143)
14
• Jouer = Non : 4 cas ( 4 ≈ 0.2857)
14
• Formule de l’entropie :
n
X
H(S) = − pi log2 pi
i=1

a. Classe "Oui" :
−pOui log2 pOui = −0.7143 × log2 (0.7143) ≈ 0.3466

Université de Dschang Les arbres de déciision 8 juin 2025 20 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Calcul de l’entropie initiale

• Distribution des classes (14 exemples) :
• Jouer = Oui : 10 cas ( 10 ≈ 0.7143)
14
• Jouer = Non : 4 cas ( 4 ≈ 0.2857)
14
• Formule de l’entropie :
n
X
H(S) = − pi log2 pi
i=1

a. Classe "Oui" :
−pOui log2 pOui = −0.7143 × log2 (0.7143) ≈ 0.3466
b. Classe "Non" :

−pNon log2 pNon = −0.2857 × log2 (0.2857) ≈ 0.5163

Université de Dschang Les arbres de déciision 8 juin 2025 20 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Calcul de l’entropie initiale

• Distribution des classes (14 exemples) :
• Jouer = Oui : 10 cas ( 10 ≈ 0.7143)
14
• Jouer = Non : 4 cas ( 4 ≈ 0.2857)
14
• Formule de l’entropie :
n
X
H(S) = − pi log2 pi
i=1

a. Classe "Oui" :
−pOui log2 pOui = −0.7143 × log2 (0.7143) ≈ 0.3466
b. Classe "Non" :

−pNon log2 pNon = −0.2857 × log2 (0.2857) ≈ 0.5163

c. Total :
H(S) = 0.3466 + 0.5163 ≈ 0.8629 bits

Université de Dschang Les arbres de déciision 8 juin 2025 20 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Sélection de l’attribut racine

• Objectif : Réduire l’incertitude initiale (H(S) ≈ 0.863)

Université de Dschang Les arbres de déciision 8 juin 2025 21 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Sélection de l’attribut racine

• Objectif : Réduire l’incertitude initiale (H(S) ≈ 0.863)

• Calcul des gains d’information pour chaque attribut :

X |Sv |
Gain(A) = H(S) − H(Sv )
v∈Valeurs(A) |S|

Université de Dschang Les arbres de déciision 8 juin 2025 21 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Sélection de l’attribut racine

• Objectif : Réduire l’incertitude initiale (H(S) ≈ 0.863)

• Calcul des gains d’information pour chaque attribut :

X |Sv |
Gain(A) = H(S) − H(Sv )
v∈Valeurs(A) |S|

• Choix : Attribut avec le gain maximal

Université de Dschang Les arbres de déciision 8 juin 2025 21 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Gain d’information : Attribut "Météo"

• Ensoleillé (5 exemples) : Oui (3), Non (2)

µ ¶
3 3 2 2
H(Ensoleillé) = − log2 + log2 ≈ 0.971
5 5 5 5

Université de Dschang Les arbres de déciision 8 juin 2025 22 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Gain d’information : Attribut "Météo"

• Ensoleillé (5 exemples) : Oui (3), Non (2)

µ ¶
3 3 2 2
H(Ensoleillé) = − log2 + log2 ≈ 0.971
5 5 5 5
• Nuageux (4 exemples) : Oui (4), Non (0)
H(Nuageux) = 0 (pur)

Université de Dschang Les arbres de déciision 8 juin 2025 22 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Gain d’information : Attribut "Météo"

• Ensoleillé (5 exemples) : Oui (3), Non (2)

µ ¶
3 3 2 2
H(Ensoleillé) = − log2 + log2 ≈ 0.971
5 5 5 5
• Nuageux (4 exemples) : Oui (4), Non (0)
H(Nuageux) = 0 (pur)
• Pluvieux (5 exemples) : Oui (3), Non (2)
µ ¶
3 3 2 2
H(Pluvieux) = − log2 + log2 ≈ 0.971
5 5 5 5

Université de Dschang Les arbres de déciision 8 juin 2025 22 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Gain d’information : Attribut "Météo"

• Ensoleillé (5 exemples) : Oui (3), Non (2)

µ ¶
3 3 2 2
H(Ensoleillé) = − log2 + log2 ≈ 0.971
5 5 5 5
• Nuageux (4 exemples) : Oui (4), Non (0)
H(Nuageux) = 0 (pur)
• Pluvieux (5 exemples) : Oui (3), Non (2)
µ ¶
3 3 2 2
H(Pluvieux) = − log2 + log2 ≈ 0.971
5 5 5 5
• Gain total :
µ ¶
5 4 5
Gain(Météo) = 0.863 − × 0.971 + ×0+ × 0.971
14 14 14
≈ 0.169 bits

Université de Dschang Les arbres de déciision 8 juin 2025 22 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Gain d’information : Attribut "Température"

• Chaud (4 exemples) : Oui (3), Non (1)

µ ¶
3 3 1 1
H(Chaud) = − log2 + log2 ≈ 0.811
4 4 4 4

Université de Dschang Les arbres de déciision 8 juin 2025 23 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Gain d’information : Attribut "Température"

• Chaud (4 exemples) : Oui (3), Non (1)

µ ¶
3 3 1 1
H(Chaud) = − log2 + log2 ≈ 0.811
4 4 4 4
• Moyen (6 exemples) : Oui (4), Non (2)
µ ¶
4 4 2 2
H(Moyen) = − log2 + log2 ≈ 0.918
6 6 6 6

Université de Dschang Les arbres de déciision 8 juin 2025 23 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Gain d’information : Attribut "Température"

• Chaud (4 exemples) : Oui (3), Non (1)

µ ¶
3 3 1 1
H(Chaud) = − log2 + log2 ≈ 0.811
4 4 4 4
• Moyen (6 exemples) : Oui (4), Non (2)
µ ¶
4 4 2 2
H(Moyen) = − log2 + log2 ≈ 0.918
6 6 6 6
• Frais (4 exemples) : Oui (3), Non (1)
µ ¶
3 3 1 1
H(Frais) = − log2 + log2 ≈ 0.811
4 4 4 4

Université de Dschang Les arbres de déciision 8 juin 2025 23 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Gain d’information : Attribut "Température"

• Chaud (4 exemples) : Oui (3), Non (1)

µ ¶
3 3 1 1
H(Chaud) = − log2 + log2 ≈ 0.811
4 4 4 4
• Moyen (6 exemples) : Oui (4), Non (2)
µ ¶
4 4 2 2
H(Moyen) = − log2 + log2 ≈ 0.918
6 6 6 6
• Frais (4 exemples) : Oui (3), Non (1)
µ ¶
3 3 1 1
H(Frais) = − log2 + log2 ≈ 0.811
4 4 4 4
• Gain total :
µ ¶
4 6 4
Gain(Température) = 0.863 − × 0.811 + × 0.918 + × 0.811
14 14 14
≈ 0.006 bits
Université de Dschang Les arbres de déciision 8 juin 2025 23 / 64
Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Gain d’information : Attribut "Humidité"

• Élevée (7 exemples) : Oui (4), Non (3)

µ ¶
4 4 3 3
H(Élevée) = − log2 + log2 ≈ 0.985
7 7 7 7

Université de Dschang Les arbres de déciision 8 juin 2025 24 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Gain d’information : Attribut "Humidité"

• Élevée (7 exemples) : Oui (4), Non (3)

µ ¶
4 4 3 3
H(Élevée) = − log2 + log2 ≈ 0.985
7 7 7 7
• Normale (7 exemples) : Oui (7), Non (0)

H(Normale) = 0 (pur)

Université de Dschang Les arbres de déciision 8 juin 2025 24 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Gain d’information : Attribut "Humidité"

• Élevée (7 exemples) : Oui (4), Non (3)

µ ¶
4 4 3 3
H(Élevée) = − log2 + log2 ≈ 0.985
7 7 7 7
• Normale (7 exemples) : Oui (7), Non (0)

H(Normale) = 0 (pur)

• Gain total : µ ¶
7 7
Gain(Humidité) = 0.863 − × 0.985 + ×0
14 14
≈ 0.371 bits

Université de Dschang Les arbres de déciision 8 juin 2025 24 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Résumé des gains d’information

Attribut Gain d’information

Météo 0.169 bits
Température 0.006 bits
Humidité 0.371 bits

Université de Dschang Les arbres de déciision 8 juin 2025 25 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Résumé des gains d’information

Attribut Gain d’information

Météo 0.169 bits
Température 0.006 bits
Humidité 0.371 bits

Choix : Humidité comme racine

Université de Dschang Les arbres de déciision 8 juin 2025 25 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Division récursive : Humidité = Normale

Jour Météo Température Jouer

2 Ensoleillé Chaud Oui
5 Pluvieux Frais Oui
7 Nuageux Frais Oui
9 Ensoleillé Frais Oui
10 Pluvieux Moyen Oui
11 Ensoleillé Moyen Oui
13 Nuageux Chaud Oui

• Distribution : 7 Oui / 0 Non

Université de Dschang Les arbres de déciision 8 juin 2025 26 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Division récursive : Humidité = Normale

Jour Météo Température Jouer

2 Ensoleillé Chaud Oui
5 Pluvieux Frais Oui
7 Nuageux Frais Oui
9 Ensoleillé Frais Oui
10 Pluvieux Moyen Oui
11 Ensoleillé Moyen Oui
13 Nuageux Chaud Oui

• Distribution : 7 Oui / 0 Non

• Entropie : H = 0 bits (nœud pur)

Université de Dschang Les arbres de déciision 8 juin 2025 26 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Division récursive : Humidité = Normale

Jour Météo Température Jouer

2 Ensoleillé Chaud Oui
5 Pluvieux Frais Oui
7 Nuageux Frais Oui
9 Ensoleillé Frais Oui
10 Pluvieux Moyen Oui
11 Ensoleillé Moyen Oui
13 Nuageux Chaud Oui

• Distribution : 7 Oui / 0 Non

• Entropie : H = 0 bits (nœud pur)
• Décision : Oui

Université de Dschang Les arbres de déciision 8 juin 2025 26 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Division récursive : Humidité = Élevée

Jour Météo Température Jouer

1 Ensoleillé Chaud Non
3 Nuageux Chaud Oui
4 Pluvieux Moyen Oui
6 Pluvieux Frais Non
8 Ensoleillé Moyen Non
12 Nuageux Moyen Oui
14 Pluvieux Moyen Non

• Distribution : 3 Oui / 4 Non

Université de Dschang Les arbres de déciision 8 juin 2025 27 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Division récursive : Humidité = Élevée

Jour Météo Température Jouer

1 Ensoleillé Chaud Non
3 Nuageux Chaud Oui
4 Pluvieux Moyen Oui
6 Pluvieux Frais Non
8 Ensoleillé Moyen Non
12 Nuageux Moyen Oui
14 Pluvieux Moyen Non

• Distribution : 3 Oui / 4 Non

• Entropie : H ≈ 0.985 bits

Université de Dschang Les arbres de déciision 8 juin 2025 27 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Division récursive : Humidité = Élevée

Jour Météo Température Jouer

1 Ensoleillé Chaud Non
3 Nuageux Chaud Oui
4 Pluvieux Moyen Oui
6 Pluvieux Frais Non
8 Ensoleillé Moyen Non
12 Nuageux Moyen Oui
14 Pluvieux Moyen Non

• Distribution : 3 Oui / 4 Non

• Entropie : H ≈ 0.985 bits
• Nouvelle division nécessaire

Université de Dschang Les arbres de déciision 8 juin 2025 27 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Gain pour "Météo" (Humidité = Élevée)

• Ensoleillé (2 exemples) : 0 Oui / 2 Non

H(Ensoleillé) = 0 bits

Université de Dschang Les arbres de déciision 8 juin 2025 28 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Gain pour "Météo" (Humidité = Élevée)

• Ensoleillé (2 exemples) : 0 Oui / 2 Non

H(Ensoleillé) = 0 bits

• Nuageux (2 exemples) : 2 Oui / 0 Non

H(Nuageux) = 0 bits

Université de Dschang Les arbres de déciision 8 juin 2025 28 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Gain pour "Météo" (Humidité = Élevée)

• Ensoleillé (2 exemples) : 0 Oui / 2 Non

H(Ensoleillé) = 0 bits

• Nuageux (2 exemples) : 2 Oui / 0 Non

H(Nuageux) = 0 bits

• Pluvieux (3 exemples) : 1 Oui / 2 Non

µ ¶
1 1 2 2
H(Pluvieux) = − log2 + log2 ≈ 0.918
3 3 3 3

Université de Dschang Les arbres de déciision 8 juin 2025 28 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Gain pour "Météo" (Humidité = Élevée)

• Ensoleillé (2 exemples) : 0 Oui / 2 Non

H(Ensoleillé) = 0 bits

• Nuageux (2 exemples) : 2 Oui / 0 Non

H(Nuageux) = 0 bits

• Pluvieux (3 exemples) : 1 Oui / 2 Non

µ ¶
1 1 2 2
H(Pluvieux) = − log2 + log2 ≈ 0.918
3 3 3 3
• Gain : µ ¶
2 2 3
Gain(Météo) = 0.985 − × 0 + × 0 + × 0.918 ≈ 0.591
7 7 7

Université de Dschang Les arbres de déciision 8 juin 2025 28 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Gain pour "Température" (Humidité = Élevée)

• Chaud (2 exemples) : 1 Oui / 1 Non

H(Chaud) = 1 bit

Université de Dschang Les arbres de déciision 8 juin 2025 29 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Gain pour "Température" (Humidité = Élevée)

• Chaud (2 exemples) : 1 Oui / 1 Non

H(Chaud) = 1 bit

• Moyen (4 exemples) : 2 Oui / 2 Non

H(Moyen) = 1 bit

Université de Dschang Les arbres de déciision 8 juin 2025 29 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Gain pour "Température" (Humidité = Élevée)

• Chaud (2 exemples) : 1 Oui / 1 Non

H(Chaud) = 1 bit

• Moyen (4 exemples) : 2 Oui / 2 Non

H(Moyen) = 1 bit

• Frais (1 exemple) : 0 Oui / 1 Non

H(Frais) = 0 bits

Université de Dschang Les arbres de déciision 8 juin 2025 29 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Gain pour "Température" (Humidité = Élevée)

• Chaud (2 exemples) : 1 Oui / 1 Non

H(Chaud) = 1 bit

• Moyen (4 exemples) : 2 Oui / 2 Non

H(Moyen) = 1 bit

• Frais (1 exemple) : 0 Oui / 1 Non

H(Frais) = 0 bits

• Gain : µ¶
2 4 1
Gain(Température) = 0.985 − × 1 + × 1 + × 0 ≈ 0.129
7 7 7

Université de Dschang Les arbres de déciision 8 juin 2025 29 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Résultat des gains

Attribut Gain
Météo 0.591 bits
Température 0.129 bits

Université de Dschang Les arbres de déciision 8 juin 2025 30 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Résultat des gains

Attribut Gain
Météo 0.591 bits
Température 0.129 bits

Choix : Météo pour la division

Université de Dschang Les arbres de déciision 8 juin 2025 30 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Seconde division : Météo = Ensoleillé

Jour Température Jouer

1 Chaud Non
8 Moyen Non

• Distribution : 0 Oui / 2 Non

Université de Dschang Les arbres de déciision 8 juin 2025 31 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Seconde division : Météo = Ensoleillé

Jour Température Jouer

1 Chaud Non
8 Moyen Non

• Distribution : 0 Oui / 2 Non

• Entropie : H = 0 bits (nœud pur)

Université de Dschang Les arbres de déciision 8 juin 2025 31 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Seconde division : Météo = Ensoleillé

Jour Température Jouer

1 Chaud Non
8 Moyen Non

• Distribution : 0 Oui / 2 Non

• Entropie : H = 0 bits (nœud pur)
• Décision : Non

Université de Dschang Les arbres de déciision 8 juin 2025 31 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Seconde division : Météo = Nuageux

Jour Température Jouer

3 Chaud Oui
12 Moyen Oui

• Distribution : 2 Oui / 0 Non

Université de Dschang Les arbres de déciision 8 juin 2025 32 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Seconde division : Météo = Nuageux

Jour Température Jouer

3 Chaud Oui
12 Moyen Oui

• Distribution : 2 Oui / 0 Non

• Entropie : H = 0 bits (nœud pur)

Université de Dschang Les arbres de déciision 8 juin 2025 32 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Seconde division : Météo = Nuageux

Jour Température Jouer

3 Chaud Oui
12 Moyen Oui

• Distribution : 2 Oui / 0 Non

• Entropie : H = 0 bits (nœud pur)
• Décision : Oui

Université de Dschang Les arbres de déciision 8 juin 2025 32 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Seconde division : Météo = Pluvieux

Jour Température Jouer

4 Moyen Oui
6 Frais Non
14 Moyen Non

• Distribution : 1 Oui / 2 Non

Université de Dschang Les arbres de déciision 8 juin 2025 33 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Seconde division : Météo = Pluvieux

Jour Température Jouer

4 Moyen Oui
6 Frais Non
14 Moyen Non

• Distribution : 1 Oui / 2 Non

• Entropie : H ≈ 0.918 bits

Université de Dschang Les arbres de déciision 8 juin 2025 33 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Seconde division : Météo = Pluvieux

Jour Température Jouer

4 Moyen Oui
6 Frais Non
14 Moyen Non

• Distribution : 1 Oui / 2 Non

• Entropie : H ≈ 0.918 bits
• Division par "Température" :

Université de Dschang Les arbres de déciision 8 juin 2025 33 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Seconde division : Météo = Pluvieux

Jour Température Jouer

4 Moyen Oui
6 Frais Non
14 Moyen Non

• Distribution : 1 Oui / 2 Non

• Entropie : H ≈ 0.918 bits
• Division par "Température" :
• Moyen : 1 Oui / 1 Non (proportions équitables : On décide de choisir Oui)

Université de Dschang Les arbres de déciision 8 juin 2025 33 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Seconde division : Météo = Pluvieux

Jour Température Jouer

4 Moyen Oui
6 Frais Non
14 Moyen Non

• Distribution : 1 Oui / 2 Non

• Entropie : H ≈ 0.918 bits
• Division par "Température" :
• Moyen : 1 Oui / 1 Non (proportions équitables : On décide de choisir Oui)
• Frais : 0 Oui / 1 Non (Non, pur)

Université de Dschang Les arbres de déciision 8 juin 2025 33 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Arbre final obtenu

Humidité

Élevée Normale

Météo Oui
Nuageux
Pluvieux
Ensoleillé
Oui Température

Non Moyen Frais

Oui Non

Université de Dschang Les arbres de déciision 8 juin 2025 34 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

C4.5 : Amélioration d’ID3

• ⋆ Avancées :

Université de Dschang Les arbres de déciision 8 juin 2025 35 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

C4.5 : Amélioration d’ID3

• ⋆ Avancées :
• ¢ Discrétise attributs numériques.

Université de Dschang Les arbres de déciision 8 juin 2025 35 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

C4.5 : Amélioration d’ID3

• ⋆ Avancées :
• ¢ Discrétise attributs numériques.
•  Gère valeurs manquantes.

Université de Dschang Les arbres de déciision 8 juin 2025 35 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

C4.5 : Amélioration d’ID3

• ⋆ Avancées :
• ¢ Discrétise attributs numériques.
•  Gère valeurs manquantes.
• ÷ Ratio d’info (plus équilibré).

Université de Dschang Les arbres de déciision 8 juin 2025 35 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

C4.5 : Amélioration d’ID3

• ⋆ Avancées :
• ¢ Discrétise attributs numériques.
•  Gère valeurs manquantes.
• ÷ Ratio d’info (plus équilibré).
• ô Élagage : limite sur-apprentissage.

Université de Dschang Les arbres de déciision 8 juin 2025 35 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

C4.5 : Amélioration d’ID3

• ⋆ Avancées :
• ¢ Discrétise attributs numériques.
•  Gère valeurs manquantes.
• ÷ Ratio d’info (plus équilibré).
• ô Élagage : limite sur-apprentissage.
• Â Limite : complexité O (A · N 2 ).

Université de Dschang Les arbres de déciision 8 juin 2025 35 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

C4.5 : Amélioration d’ID3

• ⋆ Avancées :
• ¢ Discrétise attributs numériques.
•  Gère valeurs manquantes.
• ÷ Ratio d’info (plus équilibré).
• ô Élagage : limite sur-apprentissage.
• Â Limite : complexité O (A · N 2 ).

Ç Plus robuste !

Université de Dschang Les arbres de déciision 8 juin 2025 35 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Exemple : Construction de l’arbre avec C4.5 - Jeu de données

Jour Ciel Température Humidité Vent Jouer ?

1 Ensoleillé 27,5 80 Faible non
2 Ensoleillé 25 85 Faible non
3 Couvert 28 78 Faible oui
4 Pluie 22 90 Faible oui
5 Pluie 18 95 Fort non
6 Couvert 20 85 Fort oui
7 Ensoleillé 24 70 Faible non
8 Ensoleillé 21 75 Fort non
9 Couvert 19,5 65 Faible oui
10 Pluie 17 70 Fort non
11 Ensoleillé 22,5 75 Faible oui
12 Couvert 23 72 Fort oui
13 Pluie 20 80 Faible oui
14 Ensoleillé 26 82 Fort non

Université de Dschang Les arbres de déciision 8 juin 2025 36 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Calcul de l’entropie initiale

• Distribution des classes (14 exemples) :

Université de Dschang Les arbres de déciision 8 juin 2025 37 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Calcul de l’entropie initiale

• Distribution des classes (14 exemples) :

• Jouer = oui : 7 cas ( 7 = 0.5)
14

Université de Dschang Les arbres de déciision 8 juin 2025 37 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Calcul de l’entropie initiale

• Distribution des classes (14 exemples) :

• Jouer = oui : 7 cas ( 7 = 0.5)
14
• Jouer = non : 7 cas ( 7 = 0.5)
14

Université de Dschang Les arbres de déciision 8 juin 2025 37 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Calcul de l’entropie initiale

• Distribution des classes (14 exemples) :

• Jouer = oui : 7 cas ( 7 = 0.5)
14
• Jouer = non : 7 cas ( 7 = 0.5)
14
• Formule de l’entropie :
n
X
H(S) = − pi log2 pi
i=1

Université de Dschang Les arbres de déciision 8 juin 2025 37 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Calcul de l’entropie initiale

• Distribution des classes (14 exemples) :

• Jouer = oui : 7 cas ( 7 = 0.5)
14
• Jouer = non : 7 cas ( 7 = 0.5)
14
• Formule de l’entropie :
n
X
H(S) = − pi log2 pi
i=1
• Calcul :
H(S) = −(0.5 log2 0.5 + 0.5 log2 0.5) = 1 bit

Université de Dschang Les arbres de déciision 8 juin 2025 37 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Sélection de l’attribut racine

• Objectif : Réduire l’incertitude initiale (H(S) = 1)

Université de Dschang Les arbres de déciision 8 juin 2025 38 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Sélection de l’attribut racine

• Objectif : Réduire l’incertitude initiale (H(S) = 1)

• Calcul des Gain Ratios pour chaque attribut :

Gain(A)
Gain Ratio(A) =
SplitInfo(A)

Université de Dschang Les arbres de déciision 8 juin 2025 38 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Sélection de l’attribut racine

• Objectif : Réduire l’incertitude initiale (H(S) = 1)

• Calcul des Gain Ratios pour chaque attribut :

Gain(A)
Gain Ratio(A) =
SplitInfo(A)

• Choix : Attribut avec le Gain Ratio maximal

Université de Dschang Les arbres de déciision 8 juin 2025 38 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Gain Ratio : Attribut "Ciel"

• Ensoleillé (6 exemples) : oui (1), non (5)

H(Ensoleillé) = 0.650 bits

Université de Dschang Les arbres de déciision 8 juin 2025 39 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Gain Ratio : Attribut "Ciel"

• Ensoleillé (6 exemples) : oui (1), non (5)

H(Ensoleillé) = 0.650 bits
• Couvert (4 exemples) : oui (4), non (0)
H(Couvert) = 0 bits

Université de Dschang Les arbres de déciision 8 juin 2025 39 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Gain Ratio : Attribut "Ciel"

• Ensoleillé (6 exemples) : oui (1), non (5)

H(Ensoleillé) = 0.650 bits
• Couvert (4 exemples) : oui (4), non (0)
H(Couvert) = 0 bits
• Pluie (4 exemples) : oui (2), non (2)
H(Pluie) = 1 bit

Université de Dschang Les arbres de déciision 8 juin 2025 39 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Gain Ratio : Attribut "Ciel"

• Ensoleillé (6 exemples) : oui (1), non (5)

H(Ensoleillé) = 0.650 bits
• Couvert (4 exemples) : oui (4), non (0)
H(Couvert) = 0 bits
• Pluie (4 exemples) : oui (2), non (2)
H(Pluie) = 1 bit
• Gain : µ ¶
6 4 4
Gain(Ciel) = 1 − × 0.650 + ×0+ × 1 = 0.443 bits
14 14 14

Université de Dschang Les arbres de déciision 8 juin 2025 39 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Gain Ratio : Attribut "Ciel"

• Ensoleillé (6 exemples) : oui (1), non (5)

H(Ensoleillé) = 0.650 bits
• Couvert (4 exemples) : oui (4), non (0)
H(Couvert) = 0 bits
• Pluie (4 exemples) : oui (2), non (2)
H(Pluie) = 1 bit
• Gain : µ ¶
6 4 4
Gain(Ciel) = 1 − × 0.650 + ×0+ × 1 = 0.443 bits
14 14 14
• SplitInfo :
SplitInfo(Ciel) = 1.557 bits

Université de Dschang Les arbres de déciision 8 juin 2025 39 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Gain Ratio : Attribut "Ciel"

• Ensoleillé (6 exemples) : oui (1), non (5)

H(Ensoleillé) = 0.650 bits
• Couvert (4 exemples) : oui (4), non (0)
H(Couvert) = 0 bits
• Pluie (4 exemples) : oui (2), non (2)
H(Pluie) = 1 bit
• Gain : µ ¶
6 4 4
Gain(Ciel) = 1 − × 0.650 + ×0+ × 1 = 0.443 bits
14 14 14
• SplitInfo :
SplitInfo(Ciel) = 1.557 bits
• Gain Ratio :
0.443
Gain Ratio(Ciel) = ≈ 0.284
Université de Dschang Les arbres de déciision
1.557 8 juin 2025 39 / 64
Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Gain Ratio : Attribut "Température"

• Meilleur seuil : 23°C

Université de Dschang Les arbres de déciision 8 juin 2025 40 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Gain Ratio : Attribut "Température"

• Meilleur seuil : 23°C

• Partition ≤ 23◦ C (9 exemples) : oui (6), non (3)
H(≤ 23) = 0.918 bits

Université de Dschang Les arbres de déciision 8 juin 2025 40 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Gain Ratio : Attribut "Température"

• Meilleur seuil : 23°C

• Partition ≤ 23◦ C (9 exemples) : oui (6), non (3)
H(≤ 23) = 0.918 bits
◦
• Partition > 23 C (5 exemples) : oui (1), non (4)
H(> 23) = 0.722 bits

Université de Dschang Les arbres de déciision 8 juin 2025 40 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Gain Ratio : Attribut "Température"

• Meilleur seuil : 23°C

• Partition ≤ 23◦ C (9 exemples) : oui (6), non (3)
H(≤ 23) = 0.918 bits
◦
• Partition > 23 C (5 exemples) : oui (1), non (4)
H(> 23) = 0.722 bits
• Gain : µ ¶
9 5
Gain(Température) = 1 − × 0.918 + × 0.722 = 0.214 bits
14 14

Université de Dschang Les arbres de déciision 8 juin 2025 40 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Gain Ratio : Attribut "Température"

• Meilleur seuil : 23°C

• Partition ≤ 23◦ C (9 exemples) : oui (6), non (3)
H(≤ 23) = 0.918 bits
◦
• Partition > 23 C (5 exemples) : oui (1), non (4)
H(> 23) = 0.722 bits
• Gain : µ ¶
9 5
Gain(Température) = 1 − × 0.918 + × 0.722 = 0.214 bits
14 14
• SplitInfo :
SplitInfo(Température) = 0.940 bits

Université de Dschang Les arbres de déciision 8 juin 2025 40 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Gain Ratio : Attribut "Température"

• Meilleur seuil : 23°C

• Partition ≤ 23◦ C (9 exemples) : oui (6), non (3)
H(≤ 23) = 0.918 bits
◦
• Partition > 23 C (5 exemples) : oui (1), non (4)
H(> 23) = 0.722 bits
• Gain : µ ¶
9 5
Gain(Température) = 1 − × 0.918 + × 0.722 = 0.214 bits
14 14
• SplitInfo :
SplitInfo(Température) = 0.940 bits
• Gain Ratio :
0.214
Gain Ratio(Température) = ≈ 0.228
0.940

Université de Dschang Les arbres de déciision 8 juin 2025 40 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Gain Ratio : Attribut "Humidité"

• Seuils testés : 65, 70, 75, 78, 80, 90

Université de Dschang Les arbres de déciision 8 juin 2025 41 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Gain Ratio : Attribut "Humidité"

• Seuils testés : 65, 70, 75, 78, 80, 90

• Meilleur Gain : 0.075 bits (pour 65 et 90)

Université de Dschang Les arbres de déciision 8 juin 2025 41 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Gain Ratio : Attribut "Humidité"

• Seuils testés : 65, 70, 75, 78, 80, 90

• Meilleur Gain : 0.075 bits (pour 65 et 90)
• Gains faibles, donc "Humidité" est moins compétitif

Université de Dschang Les arbres de déciision 8 juin 2025 41 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Gain Ratio : Attribut "Vent"

• Faible (8 exemples) : oui (5), non (3)

H(Faible) = 0.954 bits

Université de Dschang Les arbres de déciision 8 juin 2025 42 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Gain Ratio : Attribut "Vent"

• Faible (8 exemples) : oui (5), non (3)

H(Faible) = 0.954 bits

• Fort (6 exemples) : oui (2), non (4)

H(Fort) = 0.918 bits

Université de Dschang Les arbres de déciision 8 juin 2025 42 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Gain Ratio : Attribut "Vent"

• Faible (8 exemples) : oui (5), non (3)

H(Faible) = 0.954 bits

• Fort (6 exemples) : oui (2), non (4)

H(Fort) = 0.918 bits

• Gain : µ ¶
8 6
Gain(Vent) = 1 − × 0.954 + × 0.918 = 0.061 bits
14 14

Université de Dschang Les arbres de déciision 8 juin 2025 42 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Gain Ratio : Attribut "Vent"

• Faible (8 exemples) : oui (5), non (3)

H(Faible) = 0.954 bits

• Fort (6 exemples) : oui (2), non (4)

H(Fort) = 0.918 bits

• Gain : µ ¶
8 6
Gain(Vent) = 1 − × 0.954 + × 0.918 = 0.061 bits
14 14
• SplitInfo :
SplitInfo(Vent) = 0.985 bits

Université de Dschang Les arbres de déciision 8 juin 2025 42 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Gain Ratio : Attribut "Vent"

• Faible (8 exemples) : oui (5), non (3)

H(Faible) = 0.954 bits

• Fort (6 exemples) : oui (2), non (4)

H(Fort) = 0.918 bits

• Gain : µ ¶
8 6
Gain(Vent) = 1 − × 0.954 + × 0.918 = 0.061 bits
14 14
• SplitInfo :
SplitInfo(Vent) = 0.985 bits
• Gain Ratio :
0.061
Gain Ratio(Vent) = ≈ 0.062
0.985

Université de Dschang Les arbres de déciision 8 juin 2025 42 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Résumé des Gain Ratios

Attribut Gain (bits) Gain Ratio

Ciel 0.443 0.284
Température (≤ 23◦ C) 0.214 0.228
Humidité (≤ 80%) 0.075 -
Vent 0.061 0.062

Université de Dschang Les arbres de déciision 8 juin 2025 43 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Résumé des Gain Ratios

Attribut Gain (bits) Gain Ratio

Ciel 0.443 0.284
Température (≤ 23◦ C) 0.214 0.228
Humidité (≤ 80%) 0.075 -
Vent 0.061 0.062

Choix : Ciel comme racine

Université de Dschang Les arbres de déciision 8 juin 2025 43 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Première division : Sous-ensembles

• Ciel = Ensoleillé (6 exemples) : 1 oui / 5 non

H = 0.650 bits

Université de Dschang Les arbres de déciision 8 juin 2025 44 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Première division : Sous-ensembles

• Ciel = Ensoleillé (6 exemples) : 1 oui / 5 non

H = 0.650 bits

• Ciel = Couvert (4 exemples) : 4 oui / 0 non

H = 0 bits (pur)

Université de Dschang Les arbres de déciision 8 juin 2025 44 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Première division : Sous-ensembles

• Ciel = Ensoleillé (6 exemples) : 1 oui / 5 non

H = 0.650 bits

• Ciel = Couvert (4 exemples) : 4 oui / 0 non

H = 0 bits (pur)

• Ciel = Pluie (4 exemples) : 2 oui / 2 non

H = 1 bit

Université de Dschang Les arbres de déciision 8 juin 2025 44 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Division récursive : "Ensoleillé"

Jour Température Humidité Vent Jouer

1 27,5 80 Faible non
2 25 85 Faible non
7 24 70 Faible non
8 21 75 Fort non
11 22,5 75 Faible oui
14 26 82 Fort non

• Entropie : H = 0.650 bits

Université de Dschang Les arbres de déciision 8 juin 2025 45 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Division récursive : "Ensoleillé"

Jour Température Humidité Vent Jouer

1 27,5 80 Faible non
2 25 85 Faible non
7 24 70 Faible non
8 21 75 Fort non
11 22,5 75 Faible oui
14 26 82 Fort non

• Entropie : H = 0.650 bits

• Gain Ratios :

Université de Dschang Les arbres de déciision 8 juin 2025 45 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Division récursive : "Ensoleillé"

Jour Température Humidité Vent Jouer

1 27,5 80 Faible non
2 25 85 Faible non
7 24 70 Faible non
8 21 75 Fort non
11 22,5 75 Faible oui
14 26 82 Fort non

• Entropie : H = 0.650 bits

• Gain Ratios :
• Température (≤ 22, 5◦ C) : 0.345

Université de Dschang Les arbres de déciision 8 juin 2025 45 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Division récursive : "Ensoleillé"

Jour Température Humidité Vent Jouer

1 27,5 80 Faible non
2 25 85 Faible non
7 24 70 Faible non
8 21 75 Fort non
11 22,5 75 Faible oui
14 26 82 Fort non

• Entropie : H = 0.650 bits

• Gain Ratios :
• Température (≤ 22, 5◦ C) : 0.345
• Humidité (≤ 75%) : 0.191

Université de Dschang Les arbres de déciision 8 juin 2025 45 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Division récursive : "Ensoleillé"

Jour Température Humidité Vent Jouer

1 27,5 80 Faible non
2 25 85 Faible non
7 24 70 Faible non
8 21 75 Fort non
11 22,5 75 Faible oui
14 26 82 Fort non

• Entropie : H = 0.650 bits

• Gain Ratios :
• Température (≤ 22, 5◦ C) : 0.345
• Humidité (≤ 75%) : 0.191
• Vent : 0.119

Université de Dschang Les arbres de déciision 8 juin 2025 45 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Division récursive : "Ensoleillé"

Jour Température Humidité Vent Jouer

1 27,5 80 Faible non
2 25 85 Faible non
7 24 70 Faible non
8 21 75 Fort non
11 22,5 75 Faible oui
14 26 82 Fort non

• Entropie : H = 0.650 bits

• Gain Ratios :
• Température (≤ 22, 5◦ C) : 0.345
• Humidité (≤ 75%) : 0.191
• Vent : 0.119
• Choix : Température (≤ 22, 5◦ C)

Université de Dschang Les arbres de déciision 8 juin 2025 45 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Division récursive : "Pluie"

Jour Température Humidité Vent Jouer

4 22 90 Faible oui
5 18 95 Fort non
10 17 70 Fort non
13 20 80 Faible oui

• Entropie : H = 1 bit

Université de Dschang Les arbres de déciision 8 juin 2025 46 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Division récursive : "Pluie"

Jour Température Humidité Vent Jouer

4 22 90 Faible oui
5 18 95 Fort non
10 17 70 Fort non
13 20 80 Faible oui

• Entropie : H = 1 bit
• Gain Ratios :

Université de Dschang Les arbres de déciision 8 juin 2025 46 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Division récursive : "Pluie"

Jour Température Humidité Vent Jouer

4 22 90 Faible oui
5 18 95 Fort non
10 17 70 Fort non
13 20 80 Faible oui

• Entropie : H = 1 bit
• Gain Ratios :
• Température (≤ 18◦ C) : 1

Université de Dschang Les arbres de déciision 8 juin 2025 46 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Division récursive : "Pluie"

Jour Température Humidité Vent Jouer

4 22 90 Faible oui
5 18 95 Fort non
10 17 70 Fort non
13 20 80 Faible oui

• Entropie : H = 1 bit
• Gain Ratios :
• Température (≤ 18◦ C) : 1
• Vent : 1

Université de Dschang Les arbres de déciision 8 juin 2025 46 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Division récursive : "Pluie"

Jour Température Humidité Vent Jouer

4 22 90 Faible oui
5 18 95 Fort non
10 17 70 Fort non
13 20 80 Faible oui

• Entropie : H = 1 bit
• Gain Ratios :
• Température (≤ 18◦ C) : 1
• Vent : 1
• Choix : Température (≤ 18◦ C)

Université de Dschang Les arbres de déciision 8 juin 2025 46 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Seconde division : "Ensoleillé" (Température ≤ 22, 5◦ C)

Jour Vent Jouer

8 Fort non
11 Faible oui

• Gain Ratio pour Vent : 1 (séparation parfaite)

Université de Dschang Les arbres de déciision 8 juin 2025 47 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Seconde division : "Ensoleillé" (Température ≤ 22, 5◦ C)

Jour Vent Jouer

8 Fort non
11 Faible oui

• Gain Ratio pour Vent : 1 (séparation parfaite)

• Choix : Vent

Université de Dschang Les arbres de déciision 8 juin 2025 47 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Arbre final obtenu

Ciel

Ensoleillé Pluie
Couvert
Température Température
Oui
≤ 22.5◦ C > 22.5◦ C > 18◦ C ≤ 18◦ C

Vent Non Oui Non

Faible Fort

Oui Non

Université de Dschang Les arbres de déciision 8 juin 2025 48 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

CART : Classification And Regression Trees

• ‹ Caractéristiques :

Université de Dschang Les arbres de déciision 8 juin 2025 49 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

CART : Classification And Regression Trees

• ‹ Caractéristiques :
• Ñ Arbres binaires : 2 branches/nœud.

Université de Dschang Les arbres de déciision 8 juin 2025 49 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

CART : Classification And Regression Trees

• ‹ Caractéristiques :
• Ñ Arbres binaires : 2 branches/nœud.
• ¡ Gini : impureté (classification).

Université de Dschang Les arbres de déciision 8 juin 2025 49 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

CART : Classification And Regression Trees

• ‹ Caractéristiques :
• Ñ Arbres binaires : 2 branches/nœud.
• ¡ Gini : impureté (classification).
• ¢ MSE : régression
1X n
MSE = (yi − ŷ)2
n i=1

Université de Dschang Les arbres de déciision 8 juin 2025 49 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

CART : Classification And Regression Trees

• ‹ Caractéristiques :
• Ñ Arbres binaires : 2 branches/nœud.
• ¡ Gini : impureté (classification).
• ¢ MSE : régression
1X n
MSE = (yi − ŷ)2
n i=1
• ô Élagage : coût-complexité.

Université de Dschang Les arbres de déciision 8 juin 2025 49 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

CART : Classification And Regression Trees

• ‹ Caractéristiques :
• Ñ Arbres binaires : 2 branches/nœud.
• ¡ Gini : impureté (classification).
• ¢ MSE : régression
1X n
MSE = (yi − ŷ)2
n i=1
• ô Élagage : coût-complexité.

Ç Flexible et simple !

Université de Dschang Les arbres de déciision 8 juin 2025 49 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Comparaison des algorithmes

Caractéristique ID3 C4.5 CART

Type d’attributs Catégoriels Mixte Mixte
Type d’arbre Multi Multi Binaire
Critère Gain d’info Ratio Gini/MSE
Valeurs manquantes Non Oui Oui

•  Applications :

Université de Dschang Les arbres de déciision 8 juin 2025 50 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Comparaison des algorithmes

Caractéristique ID3 C4.5 CART

Type d’attributs Catégoriels Mixte Mixte
Type d’arbre Multi Multi Binaire
Critère Gain d’info Ratio Gini/MSE
Valeurs manquantes Non Oui Oui

•  Applications :
• ê Détection de fraude.

Université de Dschang Les arbres de déciision 8 juin 2025 50 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Comparaison des algorithmes

Caractéristique ID3 C4.5 CART

Type d’attributs Catégoriels Mixte Mixte
Type d’arbre Multi Multi Binaire
Critère Gain d’info Ratio Gini/MSE
Valeurs manquantes Non Oui Oui

•  Applications :
• ê Détection de fraude.
• È Diagnostic médical.

Université de Dschang Les arbres de déciision 8 juin 2025 50 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Comparaison des algorithmes

Caractéristique ID3 C4.5 CART

Type d’attributs Catégoriels Mixte Mixte
Type d’arbre Multi Multi Binaire
Critère Gain d’info Ratio Gini/MSE
Valeurs manquantes Non Oui Oui

•  Applications :
• ê Détection de fraude.
• È Diagnostic médical.
• £ Analyse de risque.

Université de Dschang Les arbres de déciision 8 juin 2025 50 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Comparaison des algorithmes

Caractéristique ID3 C4.5 CART

Type d’attributs Catégoriels Mixte Mixte
Type d’arbre Multi Multi Binaire
Critère Gain d’info Ratio Gini/MSE
Valeurs manquantes Non Oui Oui

•  Applications :
• ê Détection de fraude.
• È Diagnostic médical.
• £ Analyse de risque.

Université de Dschang Les arbres de déciision 8 juin 2025 50 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Comparaison des algorithmes

Caractéristique ID3 C4.5 CART

Type d’attributs Catégoriels Mixte Mixte
Type d’arbre Multi Multi Binaire
Critère Gain d’info Ratio Gini/MSE
Valeurs manquantes Non Oui Oui

•  Applications :
• ê Détection de fraude.
• È Diagnostic médical.
• £ Analyse de risque.

Ç Polyvalence en action !

Université de Dschang Les arbres de déciision 8 juin 2025 50 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

1 Introduction

2 La modélisation supervisée

3 Les arbres de décision

4 Validation des arbres de décision

5 Synthèse

6 Conclusion

Université de Dschang Les arbres de déciision 8 juin 2025 51 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Validation des arbres de décision

• ◎ Erreur E : proba d’erreur (succès 1 − E).

Université de Dschang Les arbres de déciision 8 juin 2025 52 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Validation des arbres de décision

• ◎ Erreur E : proba d’erreur (succès 1 − E).

• 8 Mesures :

Université de Dschang Les arbres de déciision 8 juin 2025 52 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Validation des arbres de décision

• ◎ Erreur E : proba d’erreur (succès 1 − E).

• 8 Mesures :
• Eapp : sous-estime (apprentissage).

Université de Dschang Les arbres de déciision 8 juin 2025 52 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Validation des arbres de décision

• ◎ Erreur E : proba d’erreur (succès 1 − E).

• 8 Mesures :
• Eapp : sous-estime (apprentissage).
• Etest : réelle (test).

Université de Dschang Les arbres de déciision 8 juin 2025 52 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Validation des arbres de décision

• ◎ Erreur E : proba d’erreur (succès 1 − E).

• 8 Mesures :
• Eapp : sous-estime (apprentissage).
• Etest : réelle (test).
• { Méthodes :

Université de Dschang Les arbres de déciision 8 juin 2025 52 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Validation des arbres de décision

• ◎ Erreur E : proba d’erreur (succès 1 − E).

• 8 Mesures :
• Eapp : sous-estime (apprentissage).
• Etest : réelle (test).
• { Méthodes :
• ÷ Holdout : apprentissage/test.

Université de Dschang Les arbres de déciision 8 juin 2025 52 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Validation des arbres de décision

• ◎ Erreur E : proba d’erreur (succès 1 − E).

• 8 Mesures :
• Eapp : sous-estime (apprentissage).
• Etest : réelle (test).
• { Méthodes :
• ÷ Holdout : apprentissage/test.
• L Validation croisée : k-folds.

Université de Dschang Les arbres de déciision 8 juin 2025 52 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Validation des arbres de décision

• ◎ Erreur E : proba d’erreur (succès 1 − E).

• 8 Mesures :
• Eapp : sous-estime (apprentissage).
• Etest : réelle (test).
• { Méthodes :
• ÷ Holdout : apprentissage/test.
• L Validation croisée : k-folds.
• ® Leave-one-out : k = n.

Université de Dschang Les arbres de déciision 8 juin 2025 52 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Validation des arbres de décision

• ◎ Erreur E : proba d’erreur (succès 1 − E).

• 8 Mesures :
• Eapp : sous-estime (apprentissage).
• Etest : réelle (test).
• { Méthodes :
• ÷ Holdout : apprentissage/test.
• L Validation croisée : k-folds.
• ® Leave-one-out : k = n.
• ¶ Bootstrap : rééchantillonnage.

Université de Dschang Les arbres de déciision 8 juin 2025 52 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Validation des arbres de décision

• ◎ Erreur E : proba d’erreur (succès 1 − E).

• 8 Mesures :
• Eapp : sous-estime (apprentissage).
• Etest : réelle (test).
• { Méthodes :
• ÷ Holdout : apprentissage/test.
• L Validation croisée : k-folds.
• ® Leave-one-out : k = n.
• ¶ Bootstrap : rééchantillonnage.
• ✓ Objectifs : généralisation, sur-apprentissage, comparaison.

Université de Dschang Les arbres de déciision 8 juin 2025 52 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Validation des arbres de décision

• ◎ Erreur E : proba d’erreur (succès 1 − E).

• 8 Mesures :
• Eapp : sous-estime (apprentissage).
• Etest : réelle (test).
• { Méthodes :
• ÷ Holdout : apprentissage/test.
• L Validation croisée : k-folds.
• ® Leave-one-out : k = n.
• ¶ Bootstrap : rééchantillonnage.
• ✓ Objectifs : généralisation, sur-apprentissage, comparaison.

Ç Fiabilité assurée !

Université de Dschang Les arbres de déciision 8 juin 2025 52 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Métriques d’évaluation des classifieurs

• £ Métriques :
Prédit
Réel + -
+ VP FN
- FP VN

Université de Dschang Les arbres de déciision 8 juin 2025 53 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Métriques d’évaluation des classifieurs

• £ Métriques :
Prédit • Précision : VP .
Réel + - VP+FP
+ VP FN
- FP VN

Université de Dschang Les arbres de déciision 8 juin 2025 53 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Métriques d’évaluation des classifieurs

• £ Métriques :
Prédit • Précision : VP .
Réel + - VP+FP
• Rappel : VP .
+ VP FN VP+FN
- FP VN

Université de Dschang Les arbres de déciision 8 juin 2025 53 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Métriques d’évaluation des classifieurs

• £ Métriques :
Prédit • Précision : VP .
Réel + - VP+FP
• Rappel : VP .
+ VP FN VP+FN
- FP VN • Spécificité : VN .
VN+FP

Université de Dschang Les arbres de déciision 8 juin 2025 53 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Métriques d’évaluation des classifieurs

• £ Métriques :
Prédit • Précision : VP .
Réel + - VP+FP
• Rappel : VP .
+ VP FN VP+FN
- FP VN • Spécificité : VN .
VN+FP
• F1-Score : 2VP
2VP+FP+FN
.

Université de Dschang Les arbres de déciision 8 juin 2025 53 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Métriques d’évaluation des classifieurs

• £ Métriques :
Prédit • Précision : VP .
Réel + - VP+FP
• Rappel : VP .
+ VP FN VP+FN
- FP VN • Spécificité : VN .
VN+FP
• F1-Score : 2VP
2VP+FP+FN
.

Ç Forces et faiblesses révélées !

Université de Dschang Les arbres de déciision 8 juin 2025 53 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Calcul des métriques (ID3 et C4.5)

• O Matrice de confusion (4 derniers exemples) :

Classe prédite
Classe réelle Positif (Oui) Négatif (Non)
Positif (Oui) 2 (VP) 0 (FN)
Négatif (Non) 0 (FP) 2 (VN)

Université de Dschang Les arbres de déciision 8 juin 2025 54 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Calcul des métriques (ID3 et C4.5)

• O Matrice de confusion (4 derniers exemples) :

Classe prédite
Classe réelle Positif (Oui) Négatif (Non)
Positif (Oui) 2 (VP) 0 (FN)
Négatif (Non) 0 (FP) 2 (VN)
• y Métriques :

Université de Dschang Les arbres de déciision 8 juin 2025 54 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Calcul des métriques (ID3 et C4.5)

• O Matrice de confusion (4 derniers exemples) :

Classe prédite
Classe réelle Positif (Oui) Négatif (Non)
Positif (Oui) 2 (VP) 0 (FN)
Négatif (Non) 0 (FP) 2 (VN)
• y Métriques :
• Précision : VP 2
VP+FP = 2+0 = 1.0

Université de Dschang Les arbres de déciision 8 juin 2025 54 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Calcul des métriques (ID3 et C4.5)

• O Matrice de confusion (4 derniers exemples) :

Classe prédite
Classe réelle Positif (Oui) Négatif (Non)
Positif (Oui) 2 (VP) 0 (FN)
Négatif (Non) 0 (FP) 2 (VN)
• y Métriques :
• Précision : VP = 2 = 1.0
VP+FP 2+0
• Rappel : VP = 2 = 1.0
VP+FN 2+0

Université de Dschang Les arbres de déciision 8 juin 2025 54 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Calcul des métriques (ID3 et C4.5)

• O Matrice de confusion (4 derniers exemples) :

Classe prédite
Classe réelle Positif (Oui) Négatif (Non)
Positif (Oui) 2 (VP) 0 (FN)
Négatif (Non) 0 (FP) 2 (VN)
• y Métriques :
• Précision : VP = 2 = 1.0
VP+FP 2+0
• Rappel : VP = 2 = 1.0
VP+FN 2+0
• Spécificité : VN = 2 = 1.0
VN+FP 2+0

Université de Dschang Les arbres de déciision 8 juin 2025 54 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Calcul des métriques (ID3 et C4.5)

• O Matrice de confusion (4 derniers exemples) :

Classe prédite
Classe réelle Positif (Oui) Négatif (Non)
Positif (Oui) 2 (VP) 0 (FN)
Négatif (Non) 0 (FP) 2 (VN)
• y Métriques :
• VP 2
Précision : VP+FP = 2+0 = 1.0
• VP 2
Rappel : VP+FN = 2+0 = 1.0
• VN 2
Spécificité : VN+FP = 2+0 = 1.0
• 2VP 4
F1-score : 2VP+FP+FN = 4+0+0 = 1.0

Université de Dschang Les arbres de déciision 8 juin 2025 54 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Calcul des métriques (ID3 et C4.5)

• O Matrice de confusion (4 derniers exemples) :

Classe prédite
Classe réelle Positif (Oui) Négatif (Non)
Positif (Oui) 2 (VP) 0 (FN)
Négatif (Non) 0 (FP) 2 (VN)
• y Métriques :
• VP 2
Précision : VP+FP = 2+0 = 1.0
• VP 2
Rappel : VP+FN = 2+0 = 1.0
• VN 2
Spécificité : VN+FP = 2+0 = 1.0
• 2VP 4
F1-score : 2VP+FP+FN = 4+0+0 = 1.0
•  Interprétation :
• Performance parfaite (1.0 partout)
• Aucune erreur sur cet échantillon
• Nécessite validation sur un jeu plus large

Université de Dschang Les arbres de déciision 8 juin 2025 54 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Calcul des métriques (ID3 et C4.5)

• O Matrice de confusion (4 derniers exemples) :

Classe prédite
Classe réelle Positif (Oui) Négatif (Non)
Positif (Oui) 2 (VP) 0 (FN)
Négatif (Non) 0 (FP) 2 (VN)
• y Métriques :
• VP 2
Précision : VP+FP = 2+0 = 1.0
• VP 2
Rappel : VP+FN = 2+0 = 1.0
• VN 2
Spécificité : VN+FP = 2+0 = 1.0
• 2VP 4
F1-score : 2VP+FP+FN = 4+0+0 = 1.0
•  Interprétation :
• Performance parfaite (1.0 partout)
• Aucune erreur sur cet échantillon
• Nécessite validation sur un jeu plus large

⋆ Modèle idéal sur ce test !

Université de Dschang Les arbres de déciision 8 juin 2025 54 / 64
Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Validation croisée

• L Principe :

Université de Dschang Les arbres de déciision 8 juin 2025 55 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Validation croisée

• L Principe :
• ÷ n folds égaux.

Université de Dschang Les arbres de déciision 8 juin 2025 55 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Validation croisée

• L Principe :
• ÷ n folds égaux.
• 8 Stratification : classes équilibrées.

Université de Dschang Les arbres de déciision 8 juin 2025 55 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Validation croisée

• L Principe :
• ÷ n folds égaux.
• 8 Stratification : classes équilibrées.
• Ó Procédure : pour chaque fold i,

Université de Dschang Les arbres de déciision 8 juin 2025 55 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Validation croisée

• L Principe :
• ÷ n folds égaux.
• 8 Stratification : classes équilibrées.
• Ó Procédure : pour chaque fold i,
• Entraînement : n − 1 folds.

Université de Dschang Les arbres de déciision 8 juin 2025 55 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Validation croisée

• L Principe :
• ÷ n folds égaux.
• 8 Stratification : classes équilibrées.
• Ó Procédure : pour chaque fold i,
• Entraînement : n − 1 folds.
• Test : 1 fold (Ei ).

Université de Dschang Les arbres de déciision 8 juin 2025 55 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Validation croisée

• L Principe :
• ÷ n folds égaux.
• 8 Stratification : classes équilibrées.
• Ó Procédure : pour chaque fold i,
• Entraînement : n − 1 folds.
• Test : 1 fold (Ei ).
• y Erreur : 1 Pn
n i=1 Ei .

Université de Dschang Les arbres de déciision 8 juin 2025 55 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Validation croisée

• L Principe :
• ÷ n folds égaux.
• 8 Stratification : classes équilibrées.
• Ó Procédure : pour chaque fold i,
• Entraînement : n − 1 folds.
• Test : 1 fold (Ei ).
• y Erreur : 1 Pn
n i=1 Ei .
• ⋆ Config : 10-fold, stratifiée, répétée.

Université de Dschang Les arbres de déciision 8 juin 2025 55 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Validation croisée

• L Principe :
• ÷ n folds égaux.
• 8 Stratification : classes équilibrées.
• Ó Procédure : pour chaque fold i,
• Entraînement : n − 1 folds.
• Test : 1 fold (Ei ).
• y Erreur : 1 Pn
n i=1 Ei .
• ⋆ Config : 10-fold, stratifiée, répétée.

Ç Performance fiable !

Université de Dschang Les arbres de déciision 8 juin 2025 55 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Intervalle de confiance pour l’erreur

• ¡ Contexte : Ê = erreurs
N varie.
Confiance z
90% 1.645
95% 1.960
99% 2.576

Université de Dschang Les arbres de déciision 8 juin 2025 56 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Intervalle de confiance pour l’erreur

• ¡ Contexte : Ê = erreurs
N varie.
Confiance z
• û Binomiale : succès/échec.
90% 1.645
95% 1.960
99% 2.576

Université de Dschang Les arbres de déciision 8 juin 2025 56 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Intervalle de confiance pour l’erreur

• ¡ Contexte : Ê = erreurs
N varie.
Confiance z
• û Binomiale : succès/échec.
90% 1.645
• ✓ Idéal (jeu de test indépendant du jeu 95% 1.960
d’entrainement) : Wilson 99% 2.576
q
z 2 Ê(1−Ê)
Ê + 2N ±z N
Einf/sup = 2
1 + zN

Université de Dschang Les arbres de déciision 8 juin 2025 56 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Intervalle de confiance pour l’erreur

• ¡ Contexte : Ê = erreurs
N varie.
Confiance z
• û Binomiale : succès/échec.
90% 1.645
• ✓ Idéal (jeu de test indépendant du jeu 95% 1.960
d’entrainement) : Wilson 99% 2.576
q
z 2 Ê(1−Ê)
Ê + 2N ±z N
Einf/sup = 2
1 + zN

• . Problématique (jeu de test égal au jeu

d’entrainement) :
q
z 2 Eapp (1−Eapp )
Eapp + 2N +z N
Esup = 2
1 + zN

Université de Dschang Les arbres de déciision 8 juin 2025 56 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Intervalle de confiance pour l’erreur

• ¡ Contexte : Ê = erreurs
N varie.
Confiance z
• û Binomiale : succès/échec.
90% 1.645
• ✓ Idéal (jeu de test indépendant du jeu 95% 1.960
d’entrainement) : Wilson 99% 2.576
q
z 2 Ê(1−Ê)
Ê + 2N ±z N
Einf/sup = 2
1 + zN

• . Problématique (jeu de test égal au jeu

d’entrainement) :
q
z 2 Eapp (1−Eapp )
Eapp + 2N +z N
Esup = 2
1 + zN

Université de Dschang Ç arbres

Les demesurée
Fiabilité déciision
! 8 juin 2025 56 / 64
Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Sur-apprentissage
• . Définition : Modèle trop adapté aux données d’entraînement

Université de Dschang Les arbres de déciision 8 juin 2025 57 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Sur-apprentissage
• . Définition : Modèle trop adapté aux données d’entraînement
• Réduit la capacité à généraliser sur de nouvelles données

Université de Dschang Les arbres de déciision 8 juin 2025 57 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Sur-apprentissage
• . Définition : Modèle trop adapté aux données d’entraînement
• Réduit la capacité à généraliser sur de nouvelles données
• ¢ Dynamique :

Université de Dschang Les arbres de déciision 8 juin 2025 57 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Sur-apprentissage
• . Définition : Modèle trop adapté aux données d’entraînement
• Réduit la capacité à généraliser sur de nouvelles données
• ¢ Dynamique :
• Erreur d’entraînement ↓ continuellement

Université de Dschang Les arbres de déciision 8 juin 2025 57 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Sur-apprentissage
• . Définition : Modèle trop adapté aux données d’entraînement
• Réduit la capacité à généraliser sur de nouvelles données
• ¢ Dynamique :
• Erreur d’entraînement ↓ continuellement
• Erreur de généralisation ↓ puis stagne ou ↑

Université de Dschang Les arbres de déciision 8 juin 2025 57 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Sur-apprentissage
• . Définition : Modèle trop adapté aux données d’entraînement
• Réduit la capacité à généraliser sur de nouvelles données
• ¢ Dynamique :
• Erreur d’entraînement ↓ continuellement
• Erreur de généralisation ↓ puis stagne ou ↑
• 8 Conséquence : Sur-ajustement  complexité excessive

Perte de généralisation !

Université de Dschang Les arbres de déciision 8 juin 2025 57 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Élagage

• ô Définition : Simplification de l’arbre en coupant des branches

Université de Dschang Les arbres de déciision 8 juin 2025 58 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Élagage

• ô Définition : Simplification de l’arbre en coupant des branches

• ◎ Objectifs :

Université de Dschang Les arbres de déciision 8 juin 2025 58 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Élagage

• ô Définition : Simplification de l’arbre en coupant des branches

• ◎ Objectifs :
• Simplifier l’arbre

Université de Dschang Les arbres de déciision 8 juin 2025 58 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Élagage

• ô Définition : Simplification de l’arbre en coupant des branches

• ◎ Objectifs :
• Simplifier l’arbre
• Réduire le sur-apprentissage (↑ généralisation)

Université de Dschang Les arbres de déciision 8 juin 2025 58 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Élagage

• ô Définition : Simplification de l’arbre en coupant des branches

• ◎ Objectifs :
• Simplifier l’arbre
• Réduire le sur-apprentissage (↑ généralisation)
• Ó Approches dans C4.5 :

Université de Dschang Les arbres de déciision 8 juin 2025 58 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Élagage

• ô Définition : Simplification de l’arbre en coupant des branches

• ◎ Objectifs :
• Simplifier l’arbre
• Réduire le sur-apprentissage (↑ généralisation)
• Ó Approches dans C4.5 :
• Élagage post-construction

Université de Dschang Les arbres de déciision 8 juin 2025 58 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Élagage

• ô Définition : Simplification de l’arbre en coupant des branches

• ◎ Objectifs :
• Simplifier l’arbre
• Réduire le sur-apprentissage (↑ généralisation)
• Ó Approches dans C4.5 :
• Élagage post-construction
• Types :
• Remplacement : Sous-arbre 
feuille si ↓ erreur
• Promotion : Fusion de nœuds

Université de Dschang Les arbres de déciision 8 juin 2025 58 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Élagage

• ô Définition : Simplification de l’arbre en coupant des branches

• ◎ Objectifs :
• Simplifier l’arbre
• Réduire le sur-apprentissage (↑ généralisation)
• Ó Approches dans C4.5 :
• Élagage post-construction
• Types :
• Remplacement : Sous-arbre 
feuille si ↓ erreur
• Promotion : Fusion de nœuds

Ç Optimisation pour C4.5 !

Université de Dschang Les arbres de déciision 8 juin 2025 58 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

1 Introduction

2 La modélisation supervisée

3 Les arbres de décision

4 Validation des arbres de décision

5 Synthèse

6 Conclusion

Université de Dschang Les arbres de déciision 8 juin 2025 59 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Avantages et limites des arbres de décision

• – Avantages :

Université de Dschang Les arbres de déciision 8 juin 2025 60 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Avantages et limites des arbres de décision

• – Avantages :
• W Rapide, compétitif.

Université de Dschang Les arbres de déciision 8 juin 2025 60 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Avantages et limites des arbres de décision

• – Avantages :
• W Rapide, compétitif.
•  Robuste : valeurs manquantes.

Université de Dschang Les arbres de déciision 8 juin 2025 60 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Avantages et limites des arbres de décision

• – Avantages :
• W Rapide, compétitif.
•  Robuste : valeurs manquantes.
• 4 Interprétable, visuel.

Université de Dschang Les arbres de déciision 8 juin 2025 60 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Avantages et limites des arbres de décision

• – Avantages : • E Limites :
• W Rapide, compétitif.
•  Robuste : valeurs manquantes.
• 4 Interprétable, visuel.

Université de Dschang Les arbres de déciision 8 juin 2025 60 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Avantages et limites des arbres de décision

• – Avantages : • E Limites :
• W Rapide, compétitif. • . Sur-apprentissage.
•  Robuste : valeurs manquantes.
• 4 Interprétable, visuel.

Université de Dschang Les arbres de déciision 8 juin 2025 60 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Avantages et limites des arbres de décision

• – Avantages : • E Limites :
• W Rapide, compétitif. • . Sur-apprentissage.
•  Robuste : valeurs manquantes. • ¶ Sensible : variations données.
• 4 Interprétable, visuel.

Université de Dschang Les arbres de déciision 8 juin 2025 60 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Avantages et limites des arbres de décision

• – Avantages : • E Limites :
• W Rapide, compétitif. • . Sur-apprentissage.
•  Robuste : valeurs manquantes. • ¶ Sensible : variations données.
• 4 Interprétable, visuel. • ; Moins bon sur continues.

Ç Puissance et défis !

Université de Dschang Les arbres de déciision 8 juin 2025 60 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Applications typiques

•  Applications :
Critère Adapté ?
Catégoriel ✓
Interprétable ✓
Très grand volume (> 106 ex.) p
Relations non-linéaires complexes p

Université de Dschang Les arbres de déciision 8 juin 2025 61 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Applications typiques

•  Applications :
• È Médical : diagnostic. Critère Adapté ?
Catégoriel ✓
Interprétable ✓
Très grand volume (> 106 ex.) p
Relations non-linéaires complexes p

Université de Dschang Les arbres de déciision 8 juin 2025 61 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Applications typiques

•  Applications :
• È Médical : diagnostic. Critère Adapté ?
• Finance : scoring. Catégoriel ✓
Interprétable ✓
Très grand volume (> 106 ex.) p
Relations non-linéaires complexes p

Université de Dschang Les arbres de déciision 8 juin 2025 61 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Applications typiques

•  Applications :
• È Médical : diagnostic. Critère Adapté ?
• Finance : scoring. Catégoriel ✓
• s Marketing : segmentation. Interprétable ✓
Très grand volume (> 106 ex.) p
Relations non-linéaires complexes p

Université de Dschang Les arbres de déciision 8 juin 2025 61 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Applications typiques

•  Applications :
• È Médical : diagnostic. Critère Adapté ?
• Finance : scoring. Catégoriel ✓
• s Marketing : segmentation. Interprétable ✓
• Bioinfo : gènes. Très grand volume (> 106 ex.) p
Relations non-linéaires complexes p

Université de Dschang Les arbres de déciision 8 juin 2025 61 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Applications typiques

•  Applications :
• È Médical : diagnostic. Critère Adapté ?
• Finance : scoring. Catégoriel ✓
• s Marketing : segmentation. Interprétable ✓
• Bioinfo : gènes. Très grand volume (> 106 ex.) p
Relations non-linéaires complexes p

Ç Usage ciblé !

Université de Dschang Les arbres de déciision 8 juin 2025 61 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

1 Introduction

2 La modélisation supervisée

3 Les arbres de décision

4 Validation des arbres de décision

5 Synthèse

6 Conclusion

Université de Dschang Les arbres de déciision 8 juin 2025 62 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Conclusion

• [ Résumé :

Université de Dschang Les arbres de déciision 8 juin 2025 63 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Conclusion

• [ Résumé :
• ¡ Principes : entropie, Gini.

Université de Dschang Les arbres de déciision 8 juin 2025 63 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Conclusion

• [ Résumé :
• ¡ Principes : entropie, Gini.
• Ó Algos : ID3, C4.5, CART.

Université de Dschang Les arbres de déciision 8 juin 2025 63 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Conclusion

• [ Résumé :
• ¡ Principes : entropie, Gini.
• Ó Algos : ID3, C4.5, CART.
• ✓ Validation : Wilson,
sur-apprentissage.

Université de Dschang Les arbres de déciision 8 juin 2025 63 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Conclusion

• [ Résumé : • m Perspectives :
• ¡ Principes : entropie, Gini.
• Ó Algos : ID3, C4.5, CART.
• ✓ Validation : Wilson,
sur-apprentissage.

Université de Dschang Les arbres de déciision 8 juin 2025 63 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Conclusion

• [ Résumé : • m Perspectives :
• ¡ Principes : entropie, Gini. • ‹ Forêts aléatoires.
• Ó Algos : ID3, C4.5, CART.
• ✓ Validation : Wilson,
sur-apprentissage.

Université de Dschang Les arbres de déciision 8 juin 2025 63 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Conclusion

• [ Résumé : • m Perspectives :
• ¡ Principes : entropie, Gini. • ‹ Forêts aléatoires.
• Ó Algos : ID3, C4.5, CART. • j Deep learning hybride.
• ✓ Validation : Wilson,
sur-apprentissage.

Université de Dschang Les arbres de déciision 8 juin 2025 63 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Conclusion

• [ Résumé : • m Perspectives :
• ¡ Principes : entropie, Gini. • ‹ Forêts aléatoires.
• Ó Algos : ID3, C4.5, CART. • j Deep learning hybride.
• ✓ Validation : Wilson, •  Apps : médical, fraude.
sur-apprentissage.

Ç Interprétable et évolutif !

Université de Dschang Les arbres de déciision 8 juin 2025 63 / 64

Introduction La modélisation supervisée Les arbres de décision Validation des arbres de décision Synthèse Conclusion

Merci !

♥ Merci de votre attention !

® Des questions ?

Université de Dschang Les arbres de déciision 8 juin 2025 64 / 64