Arbre de Décision ET KNN PDF [PDF]

Zitiervorschau

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