Upload
others
View
2
Download
0
Embed Size (px)
Citation preview
1
Classification, Apprentissage,Décision
● MCC :– (CC+Exam)/2
– CC : pas de projet, notes sur les rendus de TP (etplus si affinités)
● Eléments du cours sur la page :
http://pageperso.lif.univ-mrs.fr/~remi.eyraud/CAD/
2
Arbres de Décision &
Forêts aléatoires
3
Les arbres de décision
Un arbre de décision est un arbre orienté dont :
Les noeuds internes sont étiquetés par un test applicable àtout individu, généralement sur un attribut de description.
Les arcs contiennent les résultats du test.
Les feuilles sont étiquetés par une classe par défaut.
4
Les arbres de décision (2)
Une feuille est repérable par sa position : la liste (unique)des valeur des arcs qui permettent d'y accéder.
Un arbre de décision est donc un classifieur organisé demanière arborescente.
Ce classifieur a une traduction immédiate en terme derègles de décision, mutuellement exclusives etordonnées (si ... alors ... sinon ...).
2 qualités principales :
Facilement interprétables
Classification rapide
5
Classification supervisée par arbrede décision
Problème : Construire un arbre de décision à partir d'unéchantillon de données
Caractéristiques des données :
Apprentissage supervisé : nécessite un expert
Attributs à valeurs discrètes (vs continus)
Question : quel attribut choisir en premier ? Ensecond ? ...
6
Classification avec des arbres dedécision exemple : formalisation
Exemple : Evaluation du risque cardiaque à partir d'unetable Individu contenant les attributs :
Age (entier positif)
Fumeur (O ou N)
Taille (entier positif)
Poids (entier positif)
Sexe (H ou F)
On demande à un cardiologue d'étiqueter une partie de labase (disons 5%) en 2 classes : individu à risque ounon.
6
7
Classification avec des arbres dedécision exemple : discrètisation
Ces attributs doivent être discrètisés :
Age (entier positif)
Taille (entier positif)
Poids (entier positif)
Proposition :
Age en trois catégories : jeune (<20 ans), actif (entre 21 et 50),senior (>50)
On applique une formule liant taille et poids et on obtient unattribut Corpulence prenant trois valeurs : faible, moyenne,forte.
7
8
Classification avec des arbres dedécision exemple : échantillon
Voici les données étiquetées par le cardiologue :
8
CorpulenceF O NF O forte OF O OF N forte OH O OH N NH N forte NF N OH N forte OF N O
Sexe Fumeur Risquefaible
faible
faiblemoyenne
moyenne
moyenne
9
Fouille avec des arbres de décisionexemple (apprentissage)
Choix de la racine de l'arbre : le pivot qui “disperse” lemieux les 2 classes
<20
Age ?
>20 <
50
>50
1N, 1O 2N, 3O 0N, 3O
faibl
e
Corp. ?
Moyenne
forte
1N, 2O 1N, 2O 1N, 3O
F
Sexe ?
H
1N, 5O 2N, 2O
O
Fum. ?
N
1N, 3O 2N, 4O
10
Fouille avec des arbres de décisionexemple (apprentissage)
Choix de la racine de l'arbre : le pivot qui “disperse” lemieux les 2 classes
<20
Age ?
>20 <
50
>50
1N, 1O 2N, 3O 0N, 3O
faibl
e
Corp. ?
Moyenne
forte
1N, 2O 1N, 2O 1N, 3O
F
Sexe ?
H
1N, 5O 2N, 2O
O
Fum. ?
N
1N, 3O 2N, 4O
11
Fouille avec des arbres de décisionexemple (apprentissage)
On continue récursivement sur chacune des branches àpartir de :
On a (première branche à gauche) : <20
Age ?
>20 <
50
>50
1N, 1O 2N, 3O
faibl
e
Corp. ?
Moyenne
forte
1N, 0O 0N, 0O 0N, 1O
F
Sexe ?
H
1N, 1O 0N, 0O
O
Fum. ?
N
1N, 1O 0N, 0O
O
12
Fouille avec des arbres de décisionexemple (apprentissage)
L'arbre courant à ce moment :
Après calcul, en testant sur l'attribut Sexe (puiscorpulence) dans la branche restant à déterminer ondisperse entièrement les classes.
<20
Age ?
>20 <
50
>50
2N, 3Ofai
ble
Corp. ?
Moyenne
forte
N ? O
O
13
Fouille avec des arbres de décisionexemple (apprentissage)
Résultat final :
On peut alors classer toutes les données d'apprentissage.
<20
Age ?
>20 <
50
>50
faibl
e
Corp. ?
Moyenne
forte
N ? O
O
F
Sexe ?
H
O
faibl
e
Corp. ?
Moyenne
forte
O N N
14
Arbre de décision de risqueempirique minimal
Il est toujours possible de trouver un arbre de décisionminimisant le risque empirique (= erreur surl'échantillon) sur un jeu de données. Mais cet arbreest bien souvent un mauvais classifieur. Pourquoi ?
Le plus petit arbre de décision compatible avec lesdonnées est l'hypothèse la meilleure engénéralisation. Pourquoi ?
La théorie de l'apprentissage statistique de Vapnickpermet de répondre formellement à ces questions.
Trouver le plus petit arbre de décision compatible avecun échantillon est un problème NP-complet :-(
15
Qu'est-ce qu'on peut faire ?
Construire un petit arbre de décision compatible avec lemaximum de données.
Conforme à 2 principes :Le rasoir d'Occam (XIV siècle) : “Les multiples ne doivent pas être utilisés sans nécessité”
(pluralitas non est ponenda sine necessitate)Autrement dit : entre deux représentations équivalentes, ilfaut choisir la moins complexe.
Le principe MDL (Minimum Description Length) :Soit D l'échantillon. Apprendre c'est trouver l'hypothèseH minimisant ||H|| + ||D|H||, c'est à dire un compromisentre la taille de l'hypothèse et celle du codage desdonnées par cette hypothèse.
16
Algorithmes d'apprentissaged'arbres de décision
Plusieurs algorithmes : CART [Breiman84],C4.5[Quinlan94].
Algorithmes en deux étapes :Construction d'un petit arbre de décision compatible Elagage de l'arbre
Première étape :
Idée principale : Diviser récursivement et le pluseffcacement possible l'échantillon d'apprentissage pardes tests défnis à l'aide des attributs jusqu'à obtenirdes sous-échantillons ne contenant (presque) que desexemples appartenant à une même classe.
Méthodes de construction Top-Down, gloutonnes etrécursives.
17
Algorithmes d'apprentissaged'arbres de décision
On a besoin de trois opérateurs permettant de :Décider si un noeud est terminalSi un noeud n'est pas terminal, lui associer un testSi un noeud est terminal, lui affecter une classe
Algorithme générique :arbre ← arbre vide ; noeud_courant ← racineRépéter
Décider si le noeud courant est terminalSi le noeud est terminal alors lui affecter une classeSinon sélectionner un test et créer autant de noeuds fils qu'il
y a de réponses au testPasser au noeud suivant (si il existe)
Jusqu'à obtenir un arbre de décision consistant
18
Les trois opérateurs (en général)
Un noeud est terminal lorsque :Soit (presque) tous les exemples correspondant à ce noeud
sont dans la même classe, Soit il n'y a plus d'attribut non utilisé dans la branche
correspondante,
On attribue à un noeud terminal la classe majoritaire (encas de conflit, on peut choisir la classe majoritaire dansl'échantillon, ou en choisir une au hasard),
On sélectionne le test qui fait le plus progresser laclassification des données d'apprentissage. Commentmesurer cette progression ? CART utilise l'indice deGini et C4.5 utilise le calcul d'entropie.
19
Indice de Gini
Soit S l'échantillon et S1, S2, ... Sk sa partition suivant lesclasses (S1 sont les données de S de la classe 1, etc.)
Gini(S) = ∑i |Si|/|S|*(1-|Si|/|S|) = ∑
i≠j |Si|/|S|*|Sj|/|S|
Supposons qu'on a un problème à 2 classes (k=2), etposons x = |S1|/|S|. Alors |S2|/|S| = 1-x. On a donc :Gini(S) = 2x(1-x)
Cette fonction (idem pour k quelconque) :a des valeurs dans [0,1]S'annule pour x = 0 et x= 1 (tous éléments d'une seule classes)Sont maximales pour x = 1/2 (autant d'éléments de chaque
classe)
20
Gain et sélection du test avec Gini
Soit p la position courante de l'arbre en construction et Tun test. On définit :
Gainf (p,T) = Gini(Sp) - ∑j Pj * Gini(Spj
)
où Sp est l'échantillon associé à p et Pj est la proportiondes éléments de Sp qui satisfont la j-ème branche de T.
Maximiser le gain revient à minimiser ∑j Pj * f(Spj
)
Gain maximal : l'attribut permet de classer correctement toutes lesdonnées
Gain nul : données sont aussi mal classées après le test qu'avantSélectionner l'attribut dont le gain est maximal correspond à une
stratégie gloutonne : rechercher le test faisant le plus progresserla classification localement.
21
Exemple d'utilisation de l'algo de CART avec Gini
Résultat
GGGGP
P
P
P
22
Sur l'exemple des matchs
DOM ?
V F
R
Avec le critère de Gini et en désignant les attributsdescriptifs Dom, Bal, MCC et MPG nous avons :
<4G,4P>
<3G,2P> <1G,2P>
Gain(ε,Dom) = Gini(S)-(5/8Gini(S1) + 3/8 Gini(S2))= Gini(S) - 5/8*2*3/5*2/5 – 3/8*2*1/3*2/3 = Gini(S) - 7/15
23
Sur l'exemple des matchs
Avec le critère de Gini et en désignant les attributsdescriptifs Dom, Bal, MCC et MPG nous avons :
<4,4>
<3,1> <1,3>
Gain(ε,Dom) = Gini(S)-(4/8Gini(S1) + 4/8 Gini(S2))= Gini(S) - 4/8*2*3/4*1/4 – 4/8*2*1/4*3/4 = Gini(S) - 3/8
Bal ?
V F
24
Sur l'exemple des matchs
Avec le critère de Gini et en désignant les attributsdescriptifs Dom, Bal, MCC et MPG nous avons :
<4,4>
<2,3> <2,1>
Gain(ε,Dom) = Gini(S)-(5/8Gini(S1) + 3/8 Gini(S2))= Gini(S) - 5/8*2*2/5*3/5 – 3/8*2*2/3*1/3 = Gini(S) - 7/15
MCC ?
V F
25
Sur l'exemple des matchs
Avec le critère de Gini et en désignant les attributsdescriptifs Dom, Bal, MCC et MPG nous avons :
<4,4>
<2,2> <2,2>
Gain(ε,Dom) = Gini(S)-(4/8Gini(S1) + 4/8 Gini(S2))= Gini(S) - 4/8*2*2/4*2/4 – 4/8*2*2/4*2/4 = Gini(S) - 1/2
MPG ?
V F
26
Sur l'exemple des matchs
Avec le critère de Gini et en désignant les attributsdescriptifs Dom, Bal, MCC et MPG nous avons :
Gain(ε,Dom) = Gini(S) - 7/15
Gain(ε,Bal) = Gini(S) - 3/8
Gain(ε,MCC) = Gini(S) - 7/15
Gain(ε,MPG) = Gini(S) - 1/2
Le gain maximal est obtenu pour le test sur les attributsBalance positive et Mauvaises conditionsclimatiques. Il faut alors faire un choix (aléatoire)entre ces deux attributs.
27
Sur l'exemple des matchs
Supposons que l'on choisisse l'attribut “balancepositive” à la racine. L'arbre courant est alors :
<4,4>
<3,1> <1,3>
Il faut alors recommencer récursivement (etindépendamment) le calcul du gain en position 1et en position 2 pour choisir les tests à cesniveaux.
21
Bal ?
V F
28
Sur l'exemple des matchs (résultat)
29
Autre fonction de test : l'entropie
● Il y a d'autres indices que Gini pour tester ladispersion des classes. Le plus utilisé estl'entropie :
Soit S l'échantillon et S1, S2, ... Sk sa partitionsuivant les classes (S1 sont les données de S dela classe 1, etc.). L'entropie de l'échantillonest :
Entropy(S) = ∑i |Si|/|S|* log(|Si|/|S|)
30
Problème des arbres de décision
Un arbre peut avoir une erreur apparente nulle maisune erreur réelle importante, c'est-à-dire être bienadapté à l'échantillon mais avoir un pouvoir deprédictionfaible.
Problème de
surapprentissage
31
Eviter le sur-apprentissage
On peut utiliser un ensemble de validation pour arrêter la construction de l'arbre quand l'estimation del'erreur ne diminue plus.
On peut construire l'arbre en entier, puis l'élaguer
32
Elagage d'arbre de décision (CART)
Supposons qu'on a construit un arbre T0.
α = ∆Remp(S) / Tp|-1 où ∆Remp(S) est le nombre d'erreurssupplémentaires que commet l'arbre de décision sur Slorsqu'on l'élague à la position p et où |T
p|-1 mesure le
nombre de feuilles supprimées.
Ti+1 est obtenu en élaguant Ti en un nœud en lequel α estminimal. Soit T0, ... , Ti, ... , Tt la suite obtenue, Tt étant réduit à une feuille. On sélectionne l'arbre Ti dontle nombre d'erreurs calculé sur un ensemble devalidation Sval est minimal.
33
Retours à l'exemple
On dispose de l'ensemble de validation suivant :
L'arbre T0 est l'arbre construit précédemment. T1 est l'arbre obtenu en élaguant à partir de la position 2T2 est obtenu en élaguant à partir de la position 1. T3 est réduit à une feuille, portant la classe gagné. L'algorithme d'élagage retournera alors l'arbre T2.
34
Résultat de CART sur l'exemple
35
Elagage d'arbre de décision (C4.5)
L'idée est d'élaguer en estimant l'erreur : si la somme(pondérée) des erreurs des fils est supérieure à celle dupère, alors on élague.
On peut aussi tenir compte de l'intervalle de confiance :[e-u√(e(1-e)/n); e+u√(e(1-e)/n)] pour un u donné.
C4.5 compare les bornes sup. de l'intervalle de confianceExemple sur un nœud binaire p ayant deux fils p1 et p2
C4.5 élague si|Sp1
|/|S|*(e(p1)-u√(e(p1)(1-e(p1))/|Sp1|) +
|Sp2|/|S|*(e(p2)-u√(e(p2)(1-e(p2))/|Sp2
|)
est supérieur à |Sp|/|S|*(e(p)-u√(e(p)(1-e(p))/|Sp|)
36
Complément sur les attributs
Les propriétés vues sur les attributs binaires s'étendentaux attributs n-aires
Attributs discrets : il est possible (si on veut des arbresbinaire par exemple) de regrouper a priori desvaleurs des attributs.
Attribut continus : processus de discrétisation (souventà l'aide d'inégalités).
Attributs à valeurs manquantes :
En classement : prendre la branche majoritaire
En apprentissage : donner un valeur suivant la distribution(locale ou globale sur l'échantillon)
37
Pour être complet
On peut facilement introduire une matrice de coût de prédictions erronées : cela permet de pénaliserun type d'erreur plus qu'un autre.
Des attributs n-aires peuvent prendre un grandnombre de valeurs : il est possible de lespénaliser pour retarder leur apparition dansl'arbre.
38
Forêts aléatoires (Random forests)
Instabilité des arbres de décision: Un desinconvénients principaux des méthodesd'apprentissage par arbres de décision est leurinstabilité. Sur des données réelles, un attribut estchoisi plutôt qu'un autre se joue à peu de chose.Or le choix d'un attribut-test, surtout s'il est prèsde la racine, influence grandement le reste de laconstruction. Ces algorithmes ont une varianceimportante.
➔ Une solution est d'apprendre plusieurs arbres sur l'échantillon d'apprentissage et de faire unvote sur les nouvelles données
39
Forêts aléatoires : algorithme
Entrée : un ensemble S de n données
1) Créer K ensemble de données en réalisant un tirageavec remise
2) Apprendre K arbres de décision, un par ensemble dedonnées
3) Retourner la forêt
Quand une nouvelle donnée doit être classée, onregarde la classe que donne chacun des K arbres : laforêt retourne la classe majoritaire (décision par votemajoritaire)
40
k-plus proches voisins(aka k-ppv ou k-nn)
41
k-plus proches voisins
● Objectif : pouvoir prédire la classe d'un nouvel exempleen utilisant les exemples déjà connus
● Principe : – regarder la classe des k exemples les plus proches (k=1, 3,
…)– Affecter la classe majoritaire dans le voisinage au nouvel
exempleExemple : 2 classes, dimension 2, k=1
A
B
42
Algorithme
● Soit S ={(x,y) | x ∈ X ⊆ Rd, y∈ Y}
● Soit x' l'exemple à classer
k-ppv(S, x') :
pour chaque exemple (x,y) dans S :
Calculer la distance D(x,x')
pour chaque x'' dans k-voisinage(x') :
Ajouter 1 au nombre d'occurrences de y''
Attribuer à x' la classe la plus fréquente
43
Cas d'égalité
● Que faire en cas d'égalité ?– Augmenter k de 1
– Tirer au hasard la classe parmi les ambiguës
– Pondération des exemples par leur distance à x'
44
Pour aller plus loin
● Complexité : O(d|S|)
● On peut :– Réduire l'ensemble d'apprentissage a priori
– Organiser les données dans des structurespermettant d'accélérer la décision