Les Arbres de Décision
UP: GL/BD
Réalisé par : Equipe ML Appliqué
Plan
• Introduction
• Concepts de base
• Algorithme
• Algorithme CART
• Exemple de construction de l’arbre (Annex)
• Avantages et inconvénients
Introduction
✓ Un arbre de décision est un modèle prédictif qui utilise une structure arborescente pour
prendre des décisions basées sur des règles.
✓ C’est une technique de classification hiérarchique descendante
Introduction
l'intuition derrière un arbre de
décision est de cartographier tous
les chemins de décision possibles
sous la forme d'un arbre
C’est quoi l’arbre de décision?
Comment est-elle construite?
Comment l’utiliser pour classification ?
Intuition
Problématique: On a collecté des données des patients qui souffrent de la même
maladie. On a constaté que durant le traitement, les patients répondent à un parmi
deux types de médicaments (Drug A et Drug B)
Construire un modèle pour prédire quel type de Drug est adéquat pour un futur
patient avec la même maladie ?
Intuition
L’arbre de décision, modèle prédictif
Construire l’arbre de décision
Construire l’arbre de décision
Noeud interne : un test
Branche: résultat de test
Feuille: une classe
Les étapes de construction de l’arbre de décision
1- Choisir un attribut de dataset
2- Calculer la signification de l’attribut dans le fractionnement de données (discrimination).
3- Fractionner les données en fonction de la valeur de meilleur attribut (le plus discriminant)
4- Allez vers chaque branche et répéter ces étapes pour le reste des attributs
5- Prédiction: Utiliser l’arbre pour la prédiction des nouveaux cas.
Conditions d'arrêt du partitionnement :
▪ Tous les enregistrements d'un nœud se trouvent dans la même classe.
▪ Il n'y a plus d'attributs pour faire le partitionnement, dans ce cas, le nœud est transformé en
feuille et la classe associée est la plus fréquente dans l'ensemble.
▪ Il n'y a plus d'enregistrements.
Problématique
Quel attribut est significatif
(discriminant) ?
Quel attribut est significative ?
Choisissons l’attribut “Cholesterol” pour le fractionnement:
=> On ne peut pas juger avec grande confiance si c’est le Drug B,
Un mauvais attribut pour fractionner les données
⇒ Essayons un autre attribut de trainingset.
Quel attribut est significative ?
Choisissons l’attribut “Sex”pour le fractionnement
▪ Prédiction mieux que celle de l’attribut “Cholesterol” => Noeud plus pur
▪ Un nœud est pur si dans 100% des cas le nœud tombe dans une catégorie spécifique de la
variable cible => L’attribut “Sex” est plus prédictif et significatif que l’attribut “Cholesterol”
Quel attribut est significative ?
Pour la branche “Male” on a
testé un autre attribut pour
diviser le sous arbre => résultat
de noeud pur,
Diviser un noeud est tout
un sujet de pureté
Quel attribut est significatif ?
▪ L’arbre de decision utilise un fractionnement récursif pour diviser le dataset en segments en
minimisant l'impureté à chaque étape.
Choix du nœud
On choisit l’attribut le plus pur:
• Celui où tous les exemples sont de la même classe
• Celui qui sépare le mieux les exemplespositifs et négatifs
• C’est l’attribut le plus discriminant
Mesure d’impureté :
✓ Entropie de Shannon
✓ Entropie de Boltzmann
✓ Index de Gini
C’est quoi l’Indice de gini ?
• L’indice de gini est la mesure de hasard dans les données.
• L’indice de gini dans un nœud dépend de la quantité de données aléatoires dans ce nœud et est
calculée pour chaque nœud => l'homogénéité des exemples dans un noeud
Indice de Gini
Indice de gini is Low Indice de gini
is High
The lower the Gini Index, the less uniform
the discribution, the purer the node,
Nous cherchons les arbres avec le faible indice de gini dans leurs nœuds.
Algorithmes d’apprentissage
CART [Briemen, 1984]
ID3 [Quinlan, 1986]
SIPINA [Zighed, 1992]
C4.5 [Quinlan, 1993]
..
Algorithmes d’apprentissage
CART [Briemen, 1984]
ID3 [Quinlan, 1986]
SIPINA [Zighed, 1992]
C4.5 [Quinlan, 1993]
..
Algorithme CART
Il utilise l’indice de Gini qu’on cherche à minimiser:
▪ fi fréquence de la classe ci dans le nœud
▪ N : nombre de classes à prédire
Plus l’indice de Gini est bas, plus le nœud est pur
Exemple de construction de l’arbre
Voir Annexe
Avantages et inconvénients
Avantages :
• Simple à comprendre et à interpréter.
• Non paramétrique : ne fait pas d’hypothèses sur la distribution des données.
• Fonctionne avec des données qualitatives et quantitatives.
Inconvénients :
• Peut devenir trop complexe, menant à du surapprentissage.
• Sensible aux petites variations dans les données.
