Classification supervisée Marine Campedel campedel avril 2005

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


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)


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


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


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


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


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.


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)


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)


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


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)


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)


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


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.


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


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)


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.


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


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


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.


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


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.


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.


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


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


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


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

Documents

Classification supervisée Marine Campedel campedel avril 2005