Apprentissage supervisée :
Validation de modèle
Dr. Mamadou Camara(1)
(1) ESP, Cheikh Anta Diop University, Dakar, Senegal
[Link]@[Link]
Module de Data Mining
Dr. Mamadou Camara. DM DIC 1 / 15
Élagage
▶ L’élagage consiste à simplifier un arbre de décision en coupant
des branches.
▶ Il possède deux objectifs :
▶ simplifier l’arbre de décision ;
▶ diminuer le sur-apprentissage (= augmenter la capacité de
généralisation) et, par la-même, diminuer le taux d’erreur.
Deux possibilités :
▶ élagage lors de la construction (prepruning ou forward
pruning).)
▶ et élagage après la construction (postpruning ou backward
pruning) (Ian and Eibe 2005).
▶ Cette seconde approche est celle utilisée dans C4.5.
Dr. Mamadou Camara. DM DIC 2 / 15
Élagage
prepruning
Le prepruning
▶ Principe : décider pendant la construction de l’arbre quand
arrêter le développement des sous-arbres.
▶ Avantage : évite de faire le travail consistant à développer des
sous-arbres pour les supprimer ensuite.
▶ Limite : non prise en compte des situations dans lesquelles
(Ian and Eibe 2005) :
▶ deux attributs pris individuellement peuvent sembler n’avoir
aucune contribution,
▶ mais sont des puissants prédicteurs quand ils sont combinés .
Dr. Mamadou Camara. DM DIC 3 / 15
Élagage
postpruning
Le postpruning
▶ Deux opérations assez différentes sont à envisager pour le
postpruning (Ian and Eibe 2005) :
▶ subtree replacement
▶ subtree raising
Dr. Mamadou Camara. DM DIC 4 / 15
Élagage
postpruning
Subtree replacement
▶ Dans la première opération il s’agit de couper toutes les
branches d’un nœud ().
Dr. Mamadou Camara. DM DIC 5 / 15
Élagage
postpruning
Subtree raising
▶ Consiste à remplacer un nœud par la racine d’un des
sous-arbres qui en descend.
▶ Les exemples classés dans les autres branches sont reclassés.
▶ Le subtree raising est plus complexe, et il n’est pas claire qu’il
soit nécessairement toujours intéressant (Ian and Eibe 2005).
Dr. Mamadou Camara. DM DIC 6 / 15
Cout de complexité et paramètre de complexité
Stratégies avec pénalisation
▶ Estimation avec pénalisation (e.g. Cout de complexité et
Élagage avec la méthode C4.5) est
1. l’estimation par resubstitution ou taux d’erreur apparent
2. plus une pénalité qui corrige le biais par abus d’optimisme.
Dr. Mamadou Camara. DM DIC 7 / 15
Cout de complexité et paramètre de complexité
▶ Le cout des erreurs de classement sur l’échantillon
d’apprentissage R(T)
▶ R(T) n’est pas toujours une bonne estimation du cout des
erreurs de classement sur la population R ∗ (T ).
▶ En outre, un compromis doit être fait entre la précision et la
complexité de l’arbre en partant de l’arbre le plus complexe à
celui le plus simple (arbre -racine).
Dr. Mamadou Camara. DM DIC 8 / 15
Cout de complexité et paramètre de complexité
Cout de complexité
▶ La mesure de cout de complexité est définie comme une
combinaison linéaire de l’erreur de classement normalisée 1 et
de la complexité de l’arbre.
▶ Pour chaque arbre T ayant la même racine que l’arbre
maximal Tmax (T ⪯ Tmax ) , la mesure de cout de complexité
se calcule comme suit [2, 1] :
∼
Rα (T ) = R(T ) + α|T | (1)
∼
▶ La complexité du sous-arbre |T | est le nombre de nœuds
terminaux dans T et le paramètre de complexité α ⪰ 0 est un
nombre réel.
1. rel error
Dr. Mamadou Camara. DM DIC 9 / 15
Cout de complexité et paramètre de complexité
Le paramètre de complexité
▶ Le paramètre de complexité est un cout de complexité par
nœud terminal et peut être considéré comme une cout de
pénalité pour la complexité de l’arbre.
▶ Si α = 0 le cout de complexité atteint son minimum avec
l’arbre de plus complexe.
▶ Si α devient suffisamment large l’arbre avec un seul nœud
terminal aura le cout de complexité le plus faible.
Dr. Mamadou Camara. DM DIC 10 / 15
Cout de complexité et paramètre de complexité
Double pénalisation
▶ Pour une valeur donnée de α, il s’agira de trouver le plus petit
sous arbre T (α) qui minimise Rα (T ) [3, 1]
Rα (T (α)) = min Rα (T ) (2)
T ⪯Tmax
▶ Si un autre arbre T atteint le minimum pour le même α, alors
cet autre arbre est assurément plus grand que T (α) (i.e. le
plus petit sous arbre minimisant Rα )
Si Rα (T ) = Rα (T (α)) alors T (α) ⪯ T (3)
Dr. Mamadou Camara. DM DIC 11 / 15
Cout de complexité et paramètre de complexité
Colonne CP : points de saut de α
▶ Lorsque la valeur de α augmente, il existe un nombre fini de
sous-arbres de Tmax .
▶ Ainsi, si T (α) est le sous-arbre minimisant pour un α donné,
il continuera de rester le sous-arbre minimisant jusqu’à ce que
′
le prochain point de saut α soit atteint lorsque α augmente.
′
▶ Le nouveau sous arbre minimisant devient T (α ) jusqu’au
prochain point de saut α” .
Dr. Mamadou Camara. DM DIC 12 / 15
Cout de complexité et paramètre de complexité
Dr. Mamadou Camara. DM DIC 13 / 15
Cout de complexité et paramètre de complexité
TP
▶ TP Cout de complexité et paramètre de complexité
▶ TP : minsplit, minbucket et cp
Dr. Mamadou Camara. DM DIC 14 / 15
Cout de complexité et paramètre de complexité
▶ Geurts, Contribution to Decision Tree Induction :
Biais/Variance Tradeoff and Time Series Classification, 2002
▶ (Geurts, Ensembles d’arbres extrêmement aléatoire :
Application à la classification d’images, 2004)
Dr. Mamadou Camara. DM DIC 15 / 15
References I
[1] Classification and regression trees. Wadsworth, 1984.
[2] Classification and Regression Trees, CART : A User Manual for Identifying Indicators of Vulnerability to
Famine and Chronic Food Insecurity. Intl Food Policy Res Inst, 1999.
[3] Modern Multivariate Statistical Techniques : Regression, Classification, and Manifold Learning. Springer
Science and Business Media, 2009.