Marin FERECATU ([email protected])
http ://cedric.cnam.fr/vertigo/Cours/ml2/
Département Informatique Conservatoire National des Arts & Métiers, Paris, France
2 Objectifs et contenu de l’enseignement
3 Arbres de décision (motivation, définitions)
4 Apprentissage avec arbres de décision
5 Implémentation
6 Extensions
“La raison d’être des statistiques, c’est de vous donner raison.” - Abe Burrows
Arbres de décision : motivation, définition, exemples
Apprentissage avec de arbres de décision : classification, régression
Implémentation
ID3, C4.5, C5.0 CART
Extensions
Graphes de décision Bagging decision trees, Boosted trees Forets aléatoires (random forrests) - prochaine séance
2 Objectifs et contenu de l’enseignement
3 Arbres de décision (motivation, définitions)
4 Apprentissage avec arbres de décision
5 Implémentation
6 Extensions
Arbres de décision :
Outil utilisé dans l’exploration de données et informatique décisionnelle.
Représentation hiérarchique de la structure des données sous forme des séquences de décision (tests) en vue de la prédiction d’un résultat ou d’une classe.
Problème à résoudre : comment répartir une population d’individus (e.g. clients, produit, utilisateurs etc.) en groupes homogènes selon un ensemble de variables discriminantes (e.g. âge, temps passé sur un site Web, etc.) et en fonction d’un objectif fixé (variable de sortie ; par exemple : chiffre d’affaires, probabilité de cliquer sur une publicité, etc.)
Source : https ://maximilienandile.github.io
Source : http ://www.labortho.fr, https ://jeromechoain.files.wordpress.com
Survie de passagers sur le Titanic (https ://en.wikipedia.org).
2 Objectifs et contenu de l’enseignement
3 Arbres de décision (motivation, définitions)
4 Apprentissage avec arbres de décision
Publicité
5 Implémentation
6 Extensions
Représentation :
Chaque nœud interne correspond à un attribut
Chaque nœud teste l’attribut correspondant et génère plusieurs branches
Variable catégorielle : une branche par valeur de l’attribut Variable numérique : test sur valeur
Les feuilles spécifient les classes
Principe de la construction :
L’arbre est construit par partition récursive de la base d’apprentissage en fonction de la valeur de l’attribut testé à chaque itération (top-down induction).
Le processus s’arrête quand les éléments d’un nœud ont la même valeur pour la variable cible (homogénéité).
Gauche : division de l’espace impossible à obtenir par partition récursive sur les attributs. Milieu et droite : Partition récursive de l’espace et arbre obtenu. (source : wikimedia.org )
Gauche : séparation de classes par partition itérative des variables. Droite : séparation par combinaison linéaire de plusieurs variables.
Données d’entrée : points dans un ”feature space” spécifié par ses attributs
variables catégorielles ou numériques
Cible : classe (classification) ou valeur (régression)
2 Objectifs et contenu de l’enseignement
3 Arbres de décision (motivation, définitions)
4 Apprentissage avec arbres de décision
5 Implémentation
6 Extensions
Quinlan, J. R., Induction of Decision Trees. Mach. Learn. 1, (Mar. 1986), pp. 81-106
S un nœud interne :
Partitionner S sur les valeurs de la cible en n groupes : C 1 , . . ., Cm
pi : probabilité qu’un élément de S se retrouve dans Ci ( pi ≈|Ci | / |S| )
[ ]
H ( S ) = − [ ] 1=1 [(] [)]
H ( S ) = 0 si S est homogène (tous les éléments sont dans la même classe : un pi = 1, le reste à 0)
H ( S ) = max si tous les groupes Ci ont la même taille ( p 1 = · · · = pn = 1/ n )
Quinlan, J. R., Induction of Decision Trees. Mach. Learn. 1, (Mar. 1986), pp. 81-106
S un nœud interne :
Publicité
Partitionner S sur les valeurs de l’attribut a en n sous-groupes : S 1 , . . ., Sn
pi : la probabilité qu’un élément de S appartient à Si ( pi ≈|Si | / |S| )
[ ]
GI ( S ; a ) = H ( S ) − [ ] 1=1 [(] [)]
Algorithme :
Calculer l’entropie de chaque attribut pas encore utilisé
Choisir l’attribut de gain d’information maximal
Créer un nœud test (décision) sur cet attribut et les sous-nœuds correspondants
Récurrence sur les nœuds restants
Sortie de la récursivité :
Tous les éléments de S sont dans la même classe ( H ( S ) = 0) : S devient nœud feuille
Pas d’attributs non utilisés : nœud feuille sur le classe majoritaire
S = : nœud feuille sur le classe majoritaire du parent (ce cas est nécessaire pour la ∅ classification de nouveau échantillons)
Problèmes :
Solution globale non garantie (optimum local, amélioration : backtracking)
Over-fitting (pour éviter : préférer les arbres de taille réduite)
Pas efficace pour des données numériques continues
C4.5 : extension de ID3
Le critère de division est le gain d’information normalisé maximal (différence d’entropie avant et après la division)
Chaque attribut peut avoir un poids (coût)
Traitement de variables continues en cherchant des seuils qui maximise le gain d’information
Traitement de valeurs manquantes
Étape d’élagage après la création pour remplacer des branches inutiles par des feuilles
C5.0 : extension de ID4.5
Vitesse et utilisation mémoire
Arbres plus petits
Pondération des cas et erreurs de classification
Breiman, Friedman, Olshen, Stone, Classification and regression trees, Monterey, Brooks/Cole Advanced Books, 1984.
CART : Arbres de classification et régression
CART pose seulement de questions test binaires (arbres binaires)
Publicité
Fonctionne aussi pour des attributs aux valeurs continues
CART cherche tous les attributs et tous les seuils pour trouver celui qui donne la meilleure homogénéité du découpage
Un noeud interne S est coupé sur l’attribut j, seuil aj :
Sous-noeud gauche Sg ( pg ≈|Sg | / |S| ) et
Sous-noeud droit Sd ( pd ≈|Sd | / |S| )
Soit I ( S ) la fonction de l’impureté de S par rapport à la classe cible. CART étudie le changement de l’impureté par rapport au seuil et pour tous les attributs :
E [ I ( Sgd )] = pg I ( Sg ) + pd I ( Sd )
∆ I ( S ) = I ( S ) − E [ I ( Sgd ) = I ( S ) − pg I ( Sg ) − pd I ( Sd )
Problème d’optimisation :
arg max j ; aj ∆ I ( S )
Pb. de classification optimise l’ index (ou impureté) de Gini :
La vraisemblance qu’un élément du nœud sera incorrectement labellisé par un tirage aléatoire qui respecte la loi statistique de la cible estimé dans le nœud.
S un nœud interne :
Partitionner S sur les valeurs de la cible en n groupes : C 1 , . . ., Cm
pi : probabilité estimé qu’un élément de S se retrouve dans Ci ( pi ≈|Ci | / |S| )
[ ] [ ]
IG ( S ) = [ ] 1=1 [(1] [ −] [) =][ ] 1=1 [(] [−] i [2][) = 1] [ −] [ ] 1=1 i [2]
[ ]
IG ( S ) = [ ]
i = j
IG ( S ) = 0 si S est homogène (tous les éléments sont dans la même classe impureté du groupe nulle)
Classification : autres types de mesures d’ impureté :
H ( s ) = − [ ]
i [(] [)] [(entropie)]
E ( s ) = 1 max i pi (erreur de classification) −
Comparaison mesures d’impureté des noeuds.
Pb. de régression optimise le résidu quadratique moyen : minimise la variance moyenne des groupes.
arg min j ; aj pg Var ( Sg ) + pd Var ( Sd )
Classification de nouvelles données :
Parcours de l’arbre pour arriver dans une feuille
Publicité
La classe dominante (majoritaire) dans ce noeud donne la classification
Pour la régression : on considère les valeurs dominantes dans les feuilles
Avantages CART :
Forme non paramétrique
Pas de sélection de variables nécessaire
Invariable aux transformation monotones des attributs
Bonne gestion des ouliers
Sur-apprentissage :
Pour des pb. non-linéaires CART peut donner des arbres de grande tailles avec beaucoup de feuilles qui ont peu d’éléments (souvent un seul)
Les premiers splits sont généralement les plus importants et les moins dépendants de l’échantillon, tandis que les suivants décrivent des particularités plus subtiles, pouvant être propres à l’échantillon .
Il est donc souhaitable, afin de garder un niveau correct de généralité, d’élaguer l’arbre construit.
Un taux d’erreur de prédiction par validation croisée est calculé pour différentes tailles de l’arbre (i.e., différents nombres de feuilles terminales) : l’arbre est alors à élaguer au niveau offrant l’erreur minimale.
Taux d’erreurs : construction versus test.
Gestion des données manquantes :
Surrogate splits ou variables-substituts : l’opération continue sur un autre attribut qui, à l’apprentissage, a donné un split similaire
2 Objectifs et contenu de l’enseignement
3 Arbres de décision (motivation, définitions)
4 Apprentissage avec arbres de décision
5 Implémentation
6 Extensions
Bagging decision trees : construction plusieurs arbres par re-échantillonnage avec remise ; prise de décision par vote consensuel
Forêts d’arbres décisionnels (ou forêts aléatoires) : apprentissage sur de multiples arbres de décision entraînés sur des sous-ensembles de données légèrement différents.
Livres et articles :
Rokach, Lior ; Maimon,Data mining with decision trees : theory and applications. World Scientific Pub Co Inc., 2008
Quinlan, Induction of Decision Trees. Machine Learning 1 : 81-106, Kluwer Academic Publishers 1986
Hastie, Tibshirani, Friedman, The elements of statistical learning : Data mining, inference, and prediction. New York : Springer Verlag, 2006
Breiman, Friedman, Olshen, Stone, Classification and regression trees. Monterey, CA : Wadsworth and Brooks/Cole Advanced Books 1984
Roman Timofeev, Classification and Regression Trees (CART) Theory and Applications, Master Thesis, Université Humbold, Berlin, 2004