View
104
Download
0
Category
Preview:
Citation preview
Classification supervisée
Marine Campedel
www.tsi.enst.fr/~campedel
avril 2005
Plan du cours Introduction
Généralités
Approche probabiliste
Notion d’apprentissage
Méthodes courantes
Classificateur de Bayes
Analyse discriminante et classificateur de Fisher
kppv
Arbres de décision
Réseaux de neurones
Séparateurs à vaste marge (SVM)
Stratégies multi-classes
Introduction
Objectif de la classification : identifier les classes auxquelles appartiennent des objets à partir de traits descriptifs (attributs, caractéristiques, features).
Supervisé : les classes sont connues et l’on dispose d’exemples de chaque classe.
Applications :
Reconnaissance des formes ;
Contrôle de processus ;
Jeux
Introduction Buffon, 1749 « Le seul moyen de faire une méthode
instructive et naturelle, est de mettre ensemble des choses
qui se ressemblent et de séparer celles qui diffèrent les
unes des autres »
1ère taxonomie scientifique : Andrea Cesalpino, 1853
Classification = thème majeur de l’histoire naturelle puis
de la biologie
Fin 19ème, théorie statistique apparaît.
20ème : analyse de données + optimisation,
apprentissage
Généralités
P population
D ensemble de descripteurs
{1,…,K} ensemble de classes
X : P -> D, fonction qui associe une description à tout élément de P (extraction d’attributs)
Y : P -> {1,…,K}, associe une classe à chaque élément de P
C : D -> {1,…,K}, fonction de classement ou procédure de classification
Généralités
Objectif : apprendre C
Déterminer C de façon que C(X) approche au
mieux Y
Les attributs peuvent être : logiques, symboliques, numériques,…
Décrire la population : attribuer une valeur à chacun des attributs
Généralités
Moyen : l’apprentissage (machine learning)
« Apprendre consiste à construire et à modifier des représentations ou des modèles à partir d’une série d’expériences. » Michalski (1986)
Difficulté actuelle ne réside pas dans l’accès à l’information mais dans son filtrage -> intérêt de la classification.
A ensemble d’apprentissage constitué d’exemples x à valeurs dans D, associés à une classe y
Généralités
Stratégies pour apprendre C
Règle majoritaire : à tout d de D, on associe la
classe k telle que P(k) est maximale.
Règle du maximum de vraisemblance : à tout d
on associe k telle que P(d/k) maximale.
Règle de Bayes : à tout d on associe k telle que
P(k/d) maximale.
Généralités
Erreur pour un attribut d = probabilité qu’un élément P de description d soit mal classe par C
E(d) = P( Y != C / X = d )
E(C)= ∑ E(d)P(X=d)
Théorème : La règle de Bayes est celle qui minimise l’erreur de classification
Généralités
Exercice
Population d’individus ouvriers (O), médecins (M) ou employés des
télécoms (FT) (donc 3 classes).
1 attribut binaire : possède un répondeur / n’en possède pas
Calculer l’erreur associée aux procédures de classement obtenues
par la règle majoritaire, la règle du maximum de vraisemblance
et la règle de Bayes.
0.450.91.0P(répondeur/k)
0.50.30.2P(k)
OMFTk
Généralités
Exercice
Population de champignons.
2 classes : vénéneux ou comestible
1- Je ramasse les champignons que la règle de Bayes me donne
comme comestibles. Est-ce que je ramasse les champignons à volve ?
Appliqueriez-vous cette règle en pratique ?
2- On définit un coût pour tout couple de classes (k,i) et un coût moyen
par :
On prend la règle qui minimise ce coût moyen.
Sachant coût(1,1)=coût(2,2)=0 ; coût(1,2)=2 et coût(2,1)=infini
Est-ce que je ramasse les champignons à volve ?
0.20.9P(volve/k)
0.950.05P(k)
Comestible(2)Vénéneux(1)k
coûtMoyen k di
coût k , i P i d
Généralités
Problème 1 : toutes les erreurs ne se valent pas -> Nécessité de pondérer les erreurs.
Problème 2 : les procédures de classification doivent avoir un pouvoir prédictif
Sous problème : le langage de description doit
être suffisamment riche
Généralités
Erreur apparente
A est le nombre d’exemples d’apprentissage et err le
nombre d’erreurs effectuées par la procédure C
En général A trop petit -> nécessité de prédire l’erreur de
classification. L’erreur apparente est souvent trop optimiste.
E app C1Aerr
l imA
Eapp C E C
Généralités
Limitation de l’espace des fonctions C car impossible à explorer.
Pb : Sélectionner C, parmi un ensemble réduit, de façon que l’erreur apparente (d’apprentissage) soit petite en s’assurant que l’erreur réelle soit petite aussi.
Sélectionner C et juger de sa qualité sur le même ensemble A pose problème.
Généralités
Soit C l’ensemble des hypothèses (ou modèles) pour C
Capacité de C = card(C) ; pour les ensembles infinis la capacité est égale à la dimension de Vapnik Chervonenskis (VC-dimension)
Si capacité trop petite, résultat potentiellement inintéressant
Si capacité trop grande, risque de trop minimiser l’erreur apparente au détriment de l’erreur réelle (sur-apprentissage) -> complexification néfaste
Généralités Plus l’on a de degrés de libertés (architecture
d’un réseau, taille des arbres de décision,…), plus la capacité est grande.
Solution : minimiser le risque structurel i.e. choisir conjointement le bon compromis entre erreur réelle et capacité de l’espace des hypothèses.
Estimation de l’erreur réelle : sur un ensemble T
E
CerrTT
Généralités
Attention à la taille de T
Parfois 3 ensembles (A, T) + Validation
Techniques de rééchantillonnage
Validation croisée (partitionnement)
Bootstrap (tirage avec remise)
Généralités : conclusion
La classification supervisée consiste à inférer, à partir d’un
échantillon de données classées, une procédure de
classification
La recherche se fait sur un espace de modèles basés sur
Des hypothèses probabilistes (Classif de Bayes)
Des notions de proximité (kPPV)
Recherche de structure (arbres de décision, réseaux
de neurones)
Trouver 1 bon compromis entre la minimisation de l’erreur
apparente et la complexité du modèle.
Classificateur naïf de Bayes
Règle de Bayes
Naïf -> hypothèse que les attributs sont indépendants
donc
Estimations de P(k) par la proportion des éléments de k
dans A, idem pour P(d/k)
Généralement bons résultats malgré hypothèse
d’indépendance souvent fausse
C Bayes d argmaxk
P k d
argmaxk
P d 1 , . .. , d n k P k
argmaxk i
P d i k P k
argmaxk i
P
di
k Pk
Analyse discriminante de Fisher
Objectif : trouver l’hyperplan <w,x>+b =0 qui sépare au mieux les classes des données x.
Fonction discriminante : sign( y = <w,x>+b ) ou bien comparaison de y = <w,x> à un seuil
Matrice de dispersion inter-classes SB
Matrice de dispersion intra-classe SW
Critère de Fisher
maxw
J w maxw
w t S Bw
w t SW w
K plus proches voisins
Approche très simple
Pas d’apprentissage simplement stockage des données d’apprentissage :
Une donnée de classe inconnue est comparée à
toutes les données stockées. On choisit pour la
nouvelle donnée la classe majoritaire parmi ses
K plus proches voisins.
Lourdeur de la procédure -> pb d’accélération.
Objectif : produire une procédure de classification interprétable par l’utilisateur
Exemple :
Nœuds : repérés par leur position p ;
Nœuds internes = nœuds de décision (étiqueté par un test) – les arcs issus d’un nœud sont étiquetés par les résultats du test ;
Feuille étiquetée par une classe.
Les arbres de décision
oui
oui
non
non
malade
malade Bien portant
Température < 37.5
Gorge irritée
Les arbres de décision
Représentation graphique d’une procédure de
classification
Pour une description complète, on aboutit à une seule
feuille
Règles de décision : l’arbre définit un système de règles
avec un ordre d’examen fixé pour les attributs + règles
exclusives
SI température < 37.5 ET gorge irritée ALORS malade
SI température < 37.5 ET NON gorge irritée ALORS sain
SI NON température < 37.5 ALORS malade
Les arbres de décision Notations
Echantillon S, Classes {1,…,K}
p position d’un nœud
N(p) cardinal de l’ensemble des exemples
associés à p
N(k/p) cardinal de l’ensemble des exemples
associés à p ayant la classe k
P(k/p) = N(k/p) / N(p)
Les arbres de décision
Exercice : calcul de N et P pour un échantillon de 100
malades (M) et 100 patients sains (S)
oui
oui
non
non
malade
malade Bien portant
Température < 37.5
Gorge irritée
1S ; 41M2S ; 21MTempérature >= 37.5
91S ; 1M6S ; 37MTempérature < 37.5
Non irritéeGorge irritée
Les arbres de décision
Exercice :
Comment construire l’arbre de décision associé ?
nonnonvillagemoyenfaible8
nonouivilleâgémoyen7
nonouivilleâgéélevé6
ouiouivillejeunemoyen5
ouiouibourgmoyenfaible4
nonnonbourgâgéfaible3
nonnonbourgmoyenélevé2
ouiouivillagemoyenmoyen1
I
(classe)
ERAMClient
Les arbres de décision
Comparaison des différents tests possibles : choix d’une
fonction permettant de mesurer le degré de mélange des
exemples dans les différentes classes.
Minimale lorsque tous les exemples appartiennent à
la même classe
Maximale lorsque les exemples sont équirépartis
Entropie
Gini
Exercice : calculer Entropie et Gini sur l’exemple
précédent
Entropie pk
P k p log P k p
Gini p 1 k
P k p 2 2 k k '
P k p P k ' p
Les arbres de décision
Choix de la fonction de gain (i la fonction précédente)
p position dans l’arbre
test : choisi parmi tous les tests possibles pour le nœud
courant, d’arité n
P(j) proportion d’éléments de S, en p, qui passent en pj
Exercice : appliquer le calcul du gain sur l’exemple
précédent.
gain p , test i pj 1
n
P j i p j
Les arbres de décision
NVr
ai
827
3
plui
e
14
PFa
ux
708
5
nua
ges
13
PVr
ai
777
0
nua
ges
12
PVr
ai
697
5
sole
il
11
PFa
ux
747
1
plui
e
10
PFa
ux
726
8
sole
il
9
NFa
ux
837
2
sole
il
8
PVr
ai
656
5
nua
ges
7
NVr
ai
706
4
plui
e
6
PFa
ux
756
9
plui
e
5
PFa
ux
967
5
plui
e
4
PFa
ux
808
3
nua
ges
3
NVr
ai
908
0
sole
il
2
NFa
ux
788
1
sole
il
1
Cla
sse
Ve
nt
é
Humi
dité
T
°
Tem
ps
Exercice
T1=P
T2=Humidité(N,P)
T3=Temps( Humidité(N,P), P,
Venté(N,P) ), avec étiquetage des
arcs dans l’ordre (gauche à droite)
pour le temps: soleil, nuages et pluie
pour l’humidité: >75 et <= 75
pour venté: vrai ou faux
Montrer que T3 est parfait
Calculer l’erreur apparente de
chaque arbre.
Les arbres de décision
Construction : diviser successivement et le plus efficacement possible les exemples de l’ensemble d’apprentissage, par des tests définis à l’aide des attributs.
Opérateurs nécessaires :
Décider si un nœud est terminal
Sélectionner un test à associer à un nœud
Affecter une classe à une feuille
Les arbres de décision Etapes
Initialisation à l’arbre vide
Répéter• Décider si le nœud courant est terminal• Si terminal alors affecter une classe• Sinon sélectionner un test et créer le sous-arbre• Passer au nœud inexploré suivant s’il en existe
Jusqu’à obtenir un arbre de décision
Construction d’un arbre qui classe parfaitement les exemples d’apprentissage -> pb
Algorithme classique de construction = non optimal (algorithme descendant)
Les arbres de décision
CART (Breiman et al.)
Arbre de décision binaire
Attributs binaires, qualitatifs ou continus (mais quantifiés)
Exploite la fonction de Gini
Utilise deux ensembles A et T
Deux phases : expansion puis élagage (sur T)
Les arbres de décision
Expansion :
Nœud terminal si Gini(p) <= seuil ou
N(p) <= seuil
Sélection d’un test : gain à maximiser
Feuille : choix de la classe majoritaire
gain p , test gini p Pg gini p g P d gini pd
P g proportion des éléments en p qui passe en p g
P d proportion des éléments en p qui passe en p d
Les arbres de décision Élagage
Construction de la suite des arbres T0,…TM
T0 = arbre issu de l’expansion et Ti+1 est un élagué de
Ti (un sous-arbre de Ti est remplacé par une feuille)
Choix de la position où élaguer par minimisation de
Calcul de l’erreur apparente sur T de chaque Ti
g p app p
taille u p 1u p sous arbre en position p
app pMalClasse p MalClasse u p
N p
Les réseaux de neurones
Intelligence artificielle
Cognitivisme
Connexionnisme• Étude et modélisation des phénomènes naturels• Boîte noire
Physiologie du cerveau
Cellule
Celluleaxone
axone
dendrites
synapses
Les réseaux de neurones
Formalisation par Mc Culloch et Pitts (1943)
Loi de Hebb (renforcement des neurones actifs simultanément)
1958 Perceptron de Rosenblatt
1969 Minski et Papert critiquent le perceptron
80’s Rumelhart et Mc Clelland et Le Cun introduisent le MLP (rétropropagation)
Les réseaux de neurones
Paramètres d’un réseau
Choix du type de cellule élémentaire (à seuil ou
non)
Architecture du réseau (nombre de couches,
nombre de neurones par couche)
Dynamique du réseau (synchrone ou séquentiel)
Les réseaux de neurones
Perceptron linéaire à seuil
Potentiel post-synaptique
Fonction d’activation iw i xi
1 si x 0 0 sinon
f x
x1
xn
o
w1
wn
x1
xn
ow1
wn
w0
X0=1
1 si iw i xi
0 sinon
o
Les réseaux de neurones Exercices
Que modélise ce réseau ?
Peut-on modéliser la fonction XOR logique ?
x1
x2
oW1=1
W2=1
W0=-0.5
X0=1
Les réseaux de neurones
Théorème : un perceptron linéaire à seuil à n entrées divise l’espace des entrées en deux sous-espaces délimités par un hyperplan.
Réciproquement : tout ensemble linéairement séparable peut être discriminé par perceptron linéaire à seuil.
Les réseaux de neurones
Apprentissage par correction d’erreurs
A ensemble d’apprentissage de Rnx{0,1}
Objectif : trouver un algo qui infère un perceptron qui classifie au mieux les éléments de A
Initialisation des poids wi
Répéter :• Prendre une donnée (x, y) de A• Calculer la sortie o pour la donnée courante• %Mise à jour des poids
Pour i = 1 : n, wi <- wi + (c-o)xi
Sortie : perceptron défini par w0,…wn
Les réseaux de neurones
Exemple :
Appliquer l’algorithme par correction d’erreurs à l’apprentissage du OU logique pour deux variables binaires x1 et x2
(initialisation w0=0, w1=1 et w2=-1)
Les réseaux de neurones
Si l’espace n’est pas linéairement séparable, l’algorithme par correction d’erreur ne converge pas et il n’y a aucun moyen de le savoir.
Aucune tolérance au bruit.
Les réseaux de neurones
Apprentissage par descente de gradient
Sortie o réelle
Mesure de l’erreur
sur tout
l’échantillon
oi
w i xi
E w12 s A
y s os2
Les réseaux de neurones
Algorithme par descente de gradient
Initialisation
Répéter• Pour tout (xs,ys) de A
– Calculer os ;
– Pour tout i
• Pour tout i
Sortie : perceptron défini par w0, …wn
i 0
i i cs os xis
wi w i i
Les réseaux de neurones
Fonction d’erreur quadratique donc ne possède qu’un minimum -> assurer de converger même si l’espace est non strictement linéairement séparable.
Paramètre ξ (learning rate) doit être bien choisi ; on peut décroître sa valeur en fonction du nombre d’itérations.
Défaut de l’algo : convergence peut être lente.
Les réseaux de neurones
Algorithme de Widrow-Hoff (règle delta)
Initialisation des poids wi
Répéter• Prendre une donnée (xs,ys) de A• Calculer os
• Pour i = 1 : n
Sortie : Perceptron défini par w0,…wn
wi w i cs os xis
Les réseaux de neurones
Parcourt des exemples
Critère d’arrêt : après un passage complet, les modification de poids sont sous un seuil prédéfini.
Pas loin de l’algo par correction d’erreur mais sorties réelles (et non binaires) et utilisation du paramètre ξ.
Empiriquement : convergence non assurée mais en pratique ok et plus rapide que le précédent.
Les réseaux de neurones
Perceptron multi-couches
1 à plusieurs couches intermédiaires
Connections uniquement entre couches
successives
Exemple : XOR (à vérifier en exercice)
x1
x2
o
-0.5X0=1
1
-1.51
11
1
-2
11
Les réseaux de neurones Couches C0 (entrée),C1…Cq-1(couches cachées),
Cq(sortie)
Entrées de la couche Ci = cellules de la couche Ci-1.
Si les cellules = perceptron linéaire à seuil alors le réseau est appelé perceptron multi-couches linéaire à seuil.
On peut démontrer (Hornik 1989) que la plupart des fonctions numériques peuvent être approximées par des réseaux à une seule couche cachée -> pb de complexité
Pb du PMC : déterminer l’architecture du réseau.
Les réseaux de neurones
Cellule élémentaire = perceptron linéaire
Erreur :
(P cellules de sortie)
Erreur (delta) :
o x1
1 e y avec yi
wi x i
E w12
xs , cs A k
P
cks ok
s 2
E x ,c w12 k
P
ck ok2
Les réseaux de neurones
Notations
wij poids associé au lien entre cellule j vers cellule
i ; xij entrée associée
yi entrée totale de la cellule i
oi sortie de la cellule i
Exercice : calculer en distinguant les cellules
de la couche de sortie des autres.
yij Pred i
w ij x ij
Ew ij
Les réseaux de neurones
Algorithme de rétropropagation (1980’s)
N cellules réparties sur les couches C0,C1…Cq-1, Cq
Initialisation des poids sur [-0.5, 0.5]
Répéter :• Prendre une donnée (x,c) et calculer o• %calcul par rétropropagation
– Pour les cellules de sortie :
– Pour q-1 à 1, pour chaque cellule
• %Mise à jour des poids
i oi 1 oi ci o i
i oi 1 oik Succ i
k wki
wij w ij i xij
Les réseaux de neurones
Algorithmes puissants : peuvent résoudre des pbs non linéaires
Les algorithmes reposent plus sur des heuristiques que sur des théorèmes solides
Les machines à vecteurs de support
Apparut au début des 90’s
Grand succès sur nombre d’applications
Potentiel énorme grâce au « truc des noyaux »
Même problème que les arbres et réseaux neuronaux : déterminer les bons paramètres !
Cours de 3h !
Stratégies multi-classes
Optimisation globale
UCU
UCT
Conclusion
Classification supervisée
Nombreux outils et nombreuses applications
Quels sont les outils les plus adaptés à tel ou tel
problème ? La réponse dépend des attentes de
l’utilisateur…
Autres cours :
SVM + TP sur SVM
Classification non supervisée : plus difficile à
évaluer ! + TP
Exercices supplémentaires
Exercice
Population de patients appartenant à deux classes : S (sains) ou M
(malades). On utilise deux attributs logiques indépendants T (tension
anormale) et C (taux de cholestérol anormal).
1- Donner la procédure de classification selon Bayes sous la forme d’un arbre
de décision T
2- T1=S et T2=T(M,S) -> calcul de l’erreur associée à chaque arbre
0.70.4P(C/k)
0.70.25P(T/k)
0.30.7P(k)
MSk
Recommended