23 0 2MB
Arbre de décision pour la classification Sofia Ben Jebara & Amel Ben Azza Avril 2020
1
1
Introduction • Une des techniques de classification les plus utilisées • Suite de règles à arbre • Méthode récursive basée sur ‘diviser-pour-régner’ • Précision de classification: concurrente avec d'autres méthodes, et très efficace • C4.5 et CART: parmi ‘top 10’
2
2
Structure d’un arbre de décision sur un exemple (1) Aide au diagnostic d’une maladie selon des symptômes • SymptômesàAttributs: – Douleur ∈ {abdomen, gorge, poitrine, aucune}ànominale – Fièvre ∈ {oui, non} à booléenne – Toux ∈ {oui, non} àbooléenne
• Classes: {appendicite, rhume, mal de gorge, refroidissement, rien} • Données: attributs et classes de plusieurs personnes 3
3
Structure d’un arbre de décision sur un exemple (2)
• • • •
Nœud = Test sur un attribut Branche pour chaque valeur possible de l’attribut testé Feuilles: classe de l’objetàterminaison des chemins Chaque chemin de la racine à une feuille est une règle 4
4
Avantages et intérêts d’un arbre de décision • Intérêts – Facilement interprétable – Adapté aux attriburs qualitatifs et nominaux – Possibilité d’exploitation des attributs quantitatifs – Bon fonctionnement (pour un nombre gérable d’attributs
• Inconvénients – Parfois non interprétable – Lent et instable pendant l’apprentissage 5
5
Arbre de décision converti en règles
6
6
Résultat unique (1)? • Non • Exemple: obtenir un crédit bancaire selon les
attributs: -âge, -avoir un travail, -avoir une maison, -solde bancaire
Age
Travail
Maison Solde
Crédit
Jeune
Non
Non
Moyen
Non
Jeune
Non
Non
Excellent Non
Jeune
Oui
Non
Bon
Oui
Jeune
Oui
Oui
Bon
Oui
Jeune
Non
Non
Moyen
Non
Moyen Non
Non
Moyen
Non
Moyen Non
Non
Bon
Non
Moyen Oui
Oui
Bon
Oui
Moyen Non
Oui
Excellent Oui
Moyen Non
Oui
Excellent Oui
Vieux
Non
Oui
Excellent Oui
Vieux
Non
Oui
Bon
Oui
Vieux
Oui
Non
Bon
Oui
Vieux
Oui
Non
Excellent 7 Oui
Vieux
Non
Non
Moyen
Non
7
Résultat unique (2)? Age moyen
• Résultat 1:
Travail
Solde bon
Maison
•
Résultat 2:
Maison
Travail
Nous voulons un arbre plus petit et un arbre précis facile à comprendre et à améliorer 8
8
Méthode ID3 (Iterative Dichotomiser 3): utilisation de la théorie de l’information • Idée: A chaque étape, à chaque point de choix dans l’arbre, on va calculer une fonction objective de coût • Fonction coût: gain d’information L’attribut avec le plus grand gain d’information est sélectionné • Finalité: – Tous les attributs sont considérés – Il n’est plus possible d’obtenir de gain d’information plus grand – Le maximum de pureté a été atteint – L’arbre a atteint une hauteur maximum 9
9
Entropie pour la classification • Entropie élevée – Cas où l’information provient d'une distribution uniforme – Histogramme plat – Chaque valeur de l’information est peu prévisible • Entropie faible – Cas où l’information est issu d'une distribution variée (sommets et vallées) – Histogramme a de nombreux hauts et bas – Certaines valeurs sont plus prévisibles que d’autres 10
10
Définition importante: entropie de la sortie pour une jeu de données
• Probabilités Pr(cj) : probabilité de la classe j = nombre d’occurrences de j / nombre total d’occurrences • Entropie de la sortie D entropie(D) = −
card (C )
∑
card (C )
Pr(c j )log 2 Pr(c j ),
j=1
∑
Pr(c j ) = 1
j=1
• Cas simple: 2 classes positif et négatif entropie(D) = − Pr( positif )log 2 Pr( positif ) − Pr(négatif )log 2 Pr(négatif ) Pr( positif ) + Pr(négatif ) = 1 11
11
Notion de pureté vs entropie • D contient 50% de données de la classe 1 et 50% de la classe 2 entropie(D) = −0.5 log 2 (0.5) − 0.5 log 2 (0.5) = 1
Histogramme plat à données impuresàentropie=1 • D contient 20% de données de la classe 1 et 80% de la classe 2 entropie(D) = −0.2 log 2 (0.2) − 0.8 log 2 (0.8) = 0.722
• D contient 100% de données de la classe 1 et 0% de la classe 2 entropie(D) = −1.log 2 (1) − 0 log 2 (0) = 0
Un seul pic dans l’histogrammeà données pures àentropie=0
• Interprétation: À mesure que les données deviennent de plus en plus pures (appartiennent à la même classe), la valeur d'entropie devient de plus en plus petite 12
12
Définition importante: entropie de la sortie pour un attribut • Un attribut Ai prend k valeurs possibles • Pour chaque valeur de k , La sortie D est partitionné en v=card(C) sous partitions D1 (k), D2(k),…Dv(k) • On calcule entropyA (D j ) à partir des i probabilités de chaque sous partition • Entropie de la sortie pour un attribut Ai: k
entropyAi (D) = ∑ Pr(D j ) × entropyAi (D j ) j=1 • Gain d’information d’un attribut Ai
gain(D, Ai ) = entropie(D) − entropieAi (D) 13
13
Exemple: obtenir un crédit (1) Age
Travail
Maison Solde
Crédit
Jeune
Non
Non
Moyen
Non
Jeune
Non
Non
Excellent Non
Jeune
Oui
Non
Bon
Oui
Jeune
Oui
Oui
Bon
Oui
Jeune
Non
Non
Moyen
Non
Moyen Non
Non
Moyen
Non
Moyen Non
Non
Bon
Non
Moyen Oui
Oui
Bon
Oui
Moyen Non
Oui
Excellent Oui
Moyen Non
Oui
Excellent Oui
Vieux
Non
Oui
Excellent Oui
Vieux
Non
Oui
Bon
Oui
Vieux
Oui
Non
Bon
Oui
Vieux
Oui
Non
Excellent Oui
Vieux
Non
Non
Moyen
Non
14
14
Exemple: obtenir un crédit (2) • Probabilités des attributs Attributs Age
Travail
Maison
Moyenne solde
Pr(jeune)=5/15
Pr(oui)=5/15
Pr(oui)=6/15
Pr(moyen)=4/15
Pr(moyen)=5/15
Pr(non)=10/15
Pr(non)=9/15
Pr(bon)=6/15
Pr(vieux)=5/15
Pr(excellent)=5/15
15
15
Exemple: obtenir un crédit (3) • Entropies • EntropieAi(Dj) pour Ai=Age et Dj {jeune, moyen, vieux} Sortie
EntropieAi (Dj)
Oui No n Jeune
Age
Crédit
Jeune
Non
Jeune
Non
Jeune
Oui
Jeune
Oui
Jeune
Non
2
3
EntropieAge(jeune)=-2/5log2(2/5)-3/5log2(3/5) =0.971
Moyen 3
2
EntropieAge(moyen)=-3/5log2(3/5)-2/5log2(2/5) =0.971
Moyen Non
EntropieAge(vieux)=-4/5log2(4/5)-4/5log2(4/5) =0.722
Moyen Oui
Vieux
4
1
EntropieAge(D)
Moyen Non Moyen Oui Moyen Oui
entropyAge (D) = Pr( jeune) × entropyAge (D jeune ) + Pr(moyen) × entropyAge (Dmoyen ) + Pr(vieux) × entropy Vieux Oui Age (Dvieux ) =
5 5 5 × 0.971+ × 0.971+ × 0.722 = 0.888 15 15 15
Vieux 16 Vieux
Oui
Vieux
Oui
Oui16
Exemple: obtenir un crédit (4): choix du sommet de l’arbre Maison Crédit • Un autre attribut: maison entropieMaison (D) =
6 9 × entropie(Doui ) + × entropie(Dnon ) 15 15 6 9 = ×0+ × 0.918 = 0.551 15 15
• Gain Gain(D, age) = 0.971 − 0.888 = 0.083 Gain(D, maison) = 0.971 − 0.551 = 0.420 Gain(D, travail ) = 0.971 − 0.647 = 0.324 Gain(D, solde) = 0.971 − 0.608 = 0.363
• Maison est l’attribut ayant le plus grand gainàsommet
Non
Non
Non
Non
Non
Oui
Oui
Oui
Non
Non
Non
Non
Non
Non
Oui
Oui
Oui
Oui
Oui
Oui
Oui
Oui
Oui
Oui
Non
Oui
Non 17 Non
Oui
17
Non
Exemple: obtenir un crédit (4) : Arborescence Maison
Décision? Décision? 06/06 qui ont une maison 03/09 qui n’ont pas de maison ont pu obtenir un crédit ont pu obtenir un crédit Arrêt On continue avec les autres 18 18 attributs
Exemple: obtenir un crédit (5): (Nouvelles données Age
Travail
Solde
Crédit
Age
Travail Maison Solde
Crédit
Jeune
Non
Non
Moyen
Non
Jeune
Non
Moyen
Non
Jeune
Non
Non
Excellent
Non
Jeune
Non
Excellent
Non
Jeune
Oui
Non
Bon
Oui
Jeune
Oui
Oui
Bon
Oui
Jeune
Oui
Bon
Oui
Jeune
Non
Non
Moyen
Non
Jeune
Non
Moyen
Non
Moyen
Non
Non
Moyen
Non
Moyen Non
Moyen
Non
Moyen
Non
Non
Bon
Non
Moyen
Oui
Oui
Bon
Oui
Moyen Non
Bon
Non
Moyen
Non
Oui
Excellent
Oui
Moyen
Non
Oui
Excellent
Oui
Vieux
Oui
Bon
Oui
Vieux
Non
Oui
Excellent
Oui
Vieux
Oui
Excellent
Oui
Vieux
Non
Oui
Bon
Oui
Vieux
Non
19 Moyen
Non 19
Vieux
Oui
Non
Bon
Oui
Exemple: obtenir un crédit (6): Suite des étapes • On considère un nœud • On sélectionne un attribut pour ce nœud • On crée une branche pour chaque valeur de cet attribut • Pour chaque branche, on regarde la pureté de la classe obtenue • On décide si on termine la branche ou non • Si on ne termine pas, le processus est répété
20
20
Exemple: obtenir un crédit (7): Suite de l’arborescence
• Même démarche avec les nouvelles données (en nombre de 9 et 3 attributs) • Résultat final Maison
Travail
• Remarque: les attributs d’âge et de moyenne de soldes sont inutiles pour la méthode basée sur l’entropie 21
21
Problèmes de ID3 • Solution globale non garantie (optimum local) • Risque d’Over-fitting: bonnes performances avec les données utilisées pour créer l’arbre mais mauvaise généralisation avec d’autres données • Pas efficace pour des données numériques continues 22
22
Algorithme C4.5 • 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 maximisent le gain d’information • Étape d’élagage (couper certaines branches) après création pour remplacer des branches inutiles par des feuilles 23
23
CART: Classification And Regression Trees • Fonctionne aussi pour des attributs aux valeurs continues • cherche tous les attributs et tous les seuils pour trouver celui qui donne la meilleure homogénéité du découpage • Se base sur l’indice GINI= GINI = 1 −
card (C )
∑
Pr(c j )2
j=1
24
24
Extension aux données numériques • Il est possible de traiter les numériques en les transformant en nominaux (ou ordinaux) par discrétisation • Possibilité d’utilisation du seuillage
25
25
Exercice Reprendre l’exemple précédent en utilisant l’approche CART • Restructuration des données Age
Maison
Sortie Oui
Non
Jeune
2
3
Moyen
3
2
Vieux
4
1
Sortie Oui
Non
Oui
6
0
Non
3
6
Solde
Travail
Sortie Oui
Non
Oui
5
0
Non
4
6
Sortie Oui
Non
Moyen
0
4
Bon
5
1
Excellent
4
1
26
26
Autres exemples Désabonnement à un opérateur téléphonique Client
Facture moyenne (DT)
Genre
std
Sortie: quitter le service
1
>70
1
0
1
2
>70
1
1
1
3
60-70
1
0
0
4
partition ou répartition des individus en Nc classes homogènes ou catégories •Donc, affecter tout individu X (vecteur de p variables) à une des Nc classes • Formellement, définir une fonction C d’étiquettage/classification C:
p
X
[1,Nc]
Règle de décision
Y étiquette, label 5
5
La classification en général (2) • Règle de décision frontières de séparation entre les n donnés d’apprentissage • Plusieurs frontières possibles => plusieurs méthodes possibles • Une fois frontière déterminée, phase test classer une nouvelle donnée
Individu-test X (hors de l’ensemble d’apprentissage) à classer 6
6
La classification supervisée • Une règle de décision en partant de quoi ? Mode supervisé : un ensemble de n vecteurs X1,…,Xn déjà étiquetés => données d’apprentissage annotées (ou vérité-terrain, ground truth) •Formellement, ensemble de couples ={(X1, Y1),…,(Xn, Yn)} où – Xi vecteur de variables de dimension p (exemples ou instances) – Yi vrai label de Xi de étiquette d’appartenance à une classe de l’instance Xi
7
7
Méthodes de classifications supervisées
• k-plus proches voisins (ou k-nearest neighbors ou k-NN) • Classifieur bayésien naïf (naive Bayesian classifier) • Séparateurs à Vastes Marges (Support Vector Margin ou SVM) • Classification par réseaux de neurones (Artificial Neural Networks) • Classification par réseaux profonds de neurone (Deep Neural Networks)
8
8
Algorithme k-NN Phase d’apprentissage Stockage des individus et de leurs étiquettes pour l’ensemble d’apprentissage => Apprentissage paresseux (lazy training) ! 1. 2. 3. 4. 5. 6.
Phase de test d’un individu test X Choix d’un entier k Choix d’une distance d entre les individus Calcul les n distances d(Xi, X) pour i=1, …, n Retenir les k vecteurs d’apprentissage X(1) , …, X(k) les plus proches selon d Affecter à X l'étiquette qui est la plus fréquente parmi les k observations les plus proches (vote majoritaire) Si régression, affecter en sortie la moyenne des k observations les plus proches 9 9
Illustration p=2 , Nc =2
k=3 => majorité des 3-plus proches voisins dans B =>classe B k=6 => classe A Résultats dépendent de la structure des données d’apprentissage et de k
10
10
Sec.14.3
Propriétés (1) • Distance : – Si variables continues, distance de Mahanalobis – Si variables discrètes, distance de Hamming – … • Facile à implementer • Coût calculatoire élevé pendant le test (calcul de n distances/requête) – o(p) calcul d’une distance – o(np) pour trouver un plus proche voisin – o(knp) pour trouver k plus proche voisin
• Pas d’apprentissage à proprement parler pour trouver un modèle • S’adapte facilement quand le nombre Nc de classes augmente 11
11
Sec.14.3
Propriétés (2) • Robuste au bruit dans les données d’apprentissage :
Si k=1 => affectation à la classe de l’observation la plus proche de X mais pb si plus proche voisin bruité Vecteur à classer
Tous les vecteurs de la zone ombrée en bleu affectés incorrectement à la classe bleue
Tous les vecteurs de la zone ombrée en bleu affectés correctement à 12 la classe rouge
12
Sec.14.3
Propriétés (3) Une autre illustration Observations aberrantes
13
13
Sec.14.3
Choix du paramètre k
• k impair pour éviter les ambigüités (souvent, 3 ou 5) • Règle empirique k=sqrt(n) • Augmenter k positif mais si k trop élevé perte de la localisation de l’information
14
14
Ajustement de k par validation croisée (1)
Sec.14.3
• Possibilité d’ajuster k par validation croisée (cross-validation) Pour chaque valeur de k candidate – Diviser aléatoirement les observations d’entraînement en L sousensembles – Premier sous-ensemble pour le test et les L -1 autres à l’entraînement – Calculer l’erreur de classification (ou régression) – Répéter la procédure sur le 2ème, .., L-ème sous-ensemble – Moyenne les erreurs de classification (ou régression) pour la valeur courante de k – Recommencer pour la valeur suivante de k Retenir la valeur de k donnant la classification (regression) la plus précise 15 15
Sec.14.3
Ajustement de k par validation croisée (1) Illustration de la validation croisée (L=5)
16
16