Méthodes de Classification
Pr. OUTTAJ
1
Introduction
• La grande variété des individus d’une population nécessite parfois de les
répartir en classes ou catégories.
Exemples :
•En médecine par exemple, il est intéressant de savoir les principaux
regroupements de malades ayant le même comportement vis à vis de
certaines maladies.
•Les méthodes de classification sont très utilisées en marketing. Les
entreprises les utilisent pour segmenter leurs marchés, selon des
critères quantitatifs.
Démarche algorithmique
La classification regroupe des techniques de synthèse des grands volumes de
données.
Technique intéressante avant l’apparition des bases de données
2 Pr. OUTTAJ Analyse des Données
Exemple
Besoin de répartir une population de personnes selon les
critères tel que sexe, activité, état matrimonial ....
La même population peut aussi être soumise, selon le besoin,
à une autre classification comme par exemple le sexe, la
nature du travail...
3 Pr. OUTTAJ Analyse des Données
Définitions
La classification est la construction de classes, de groupes ou de
catégories
Une classe est un groupe d’individus possédant des caractères
communs ou similaires (classe politique, sociale…)
Suivant le domaine d’application, elles s’appellent aussi :
Typologie,
Segmentation (marketing)
Ou classement.
2 types de classification
classification
Hiérarchique Partitionnement (centres
(arbre, CAH) mobiles, nuées dynamiques)
4
Pr. OUTTAJ Analyse des Données
Différence entre Clustering et
classification
Le but du Clustering (technique d’apprentissage non
supervisée) est de regrouper des individus pour déterminer
s'il existe une relation entre eux,
alors que tandis que la classification (technique
d’apprentissage supervisée) consiste à déterminer à quelle
classe un nouvel individu appartient parmi les classes
prédéfinies.
5
Exemples
Personne
Homme femme
Homme Homme Femme Femme
actif inactif active inactive
Non
marié mariée
marié
6
Pr. OUTTAJ Analyse des Données
Bases théoriques
Soit l’ensemble des individus
Partition
Une partition de l'ensemble des observations w est un
ensemble de parties non vides P =(P1,…,Pk) d'intersection
vides deux à deux et dont la réunion forme :
1. j{1,2…k} Pj
2. i,j{1,2…k} avec i j on a Pi Pj =
3. j=1k (Pj )=
7
Pr. OUTTAJ Analyse des Données
Partition : Exemple
Partition en trois classes:
P=(P1, P2, P3) représentée par P1 ={ w7}, P2={w5,w4,w6}
et P3 = { w1 , w2, w3}
8
Pr. OUTTAJ Analyse des Données
Bases théoriques
Recouvrement
Un recouvrement de est un ensemble de parties non vides
P =(P1, ... ,Pk)dont la réunion forme :
j 1,2,...k P j
k
Exemple : P j
j 1
Avec les sept individus précédents, on peut aussi construire un
recouvrement à trois classes P=(P1, P2, P3):
P1 ={ w7,w5,w4}; P2 ={ w5 , w4,w6}; et P3 ={ w1 , w2,w3}
9
Pr. OUTTAJ Analyse des Données
Recouvrement : Exemple
P1
P2
P3
Une partition est un cas particulier de recouvrement
10
Pr. OUTTAJ Analyse des Données
Bases théoriques
Hiérarchie
Une hiérarchie H de est une représentation de par un
ensemble de partitions emboîtées (appelées paliers) non vides
qui vérifient :
1) H (le palier le plus haut contient tous les individus)
2) w , w H (les points terminaux)
3) h, h' H on a h h' ou h h ' ou h' h
11
Pr. OUTTAJ Analyse des Données
Hiérarchie : Exemple
Avec les sept individus précédents W1,….W7
On a bien : H=Hi
avec hi={wi} pour i=1,…7
Et h11 = {w7} h10 et h12= h11h9…etc
12
Pr. OUTTAJ Analyse des Données
Classification Ascendante Hiérarchique CAH
Objectif : mettre en évidence des liens hiérarchiques entre individus
Tableau de données : Individus x variables quantitatives
p variables
xij est la valeur de la
n individus
variable j quand elle
xij est mesurée sur
l’individu i
13
Pr. OUTTAJ Analyse des Données
Distance entre individus et groupe d’individus
Chaque individu i est donc un élément de IRp
Pour mesurer la ressemblance entre individus, on utilise soit :
La distance euclidienne
La distance de Jaccard…
Et pour la distance entre deux groupes d’individus, on utilise
généralement l’un des critères d’agglomération suivants :
dmin : saut minimum (lien simple) ou plus petite distance
dmax : saut maximum (lien complet) ou plus grande distance
dGG’ : distance entre les barycentres des deux groupes d’individus
Etc.
dmin
dmax
14
Pr. OUTTAJ Analyse des Données
Dendrogramme
Représentation graphique lisible des groupements
15
Pr. OUTTAJ Analyse des Données
Exemple
V1 V2 V3 •Distance entre individus : distance euclidienne
I1 1 2 3 •Critère d’agglomération : saut minimum
I2 4 2 5
I3 4 3 7 Etape 0 : chaque individu représente une classe
I4 8 9 6
I5 4 2 3
Etape 1 : on regroupe I2 et I5 en N1 à hauteur de 2.00 et on construit le
dendrogramme
16
Pr. OUTTAJ Analyse des Données
Exemple
Etape 2 : on recalcule la nouvelle matrice des distances
Ensuite, on regroupe I3 et N1 en N2 à hauteur de 2,24
17
Pr. OUTTAJ Analyse des Données
Exemple
Etape 3 : on recalcule la nouvelle matrice des distances
Ensuite, on regroupe I1 et N2 en N3 à hauteur de 3
18
Pr. OUTTAJ Analyse des Données
Exemple
Etape 4 : on recalcule la nouvelle matrice des distances
Enfin, on regroupe enfin I4 et N3 en N4 à hauteur de 7,28
19
Pr. OUTTAJ Analyse des Données
Exemple
V1 V2 V3 •Distance entre individus : distance euclidienne
I1 1 2 3 •Critère d’agglomération : Méthode de Ward (la distance entre
I2 4 2 5 deux classes est celle de leurs barycentres au carré, pondérée par les
I3 4 3 7 effectifs des deux clusters) Dendrogramme
I4 8 9 6 60
I5 4 2 3
50
Dissimilarité 40
30
20
10
0
I4
I3
I1
I2
I5
20
Pr. OUTTAJ Analyse des Données
Choix du nombre de classes
Une fois l’arbre généré, il faut le découper en classes à
un certain niveau.
Quel est le bon niveau? : Une coupe pertinente si elle se
trouve entre 2 nœuds dont les hauteurs sont éloignées
2 critères :
Les individus d’une même classe doivent être proches
Les individus de 2 classes différentes doivent être éloignés
Ou encore :
La variabilité intra-classe doit être petite
La variabilité inter-classes doit être grande
21
Pr. OUTTAJ Analyse des Données
Théorème de Huygens
Si g est le centre de gravité du nuage N() on a :
n
Ig p
p 2
a R Ia i 1
i d M
( a,g )
Conséquence :
•Puisque I a I g alors le centre de gravité du nuage est le point qui
réalise la plus petite Inertie du Nuage
Ou encore
•le centre de gravité est le meilleur représentant du nuage
Remarque : En notation vectorielle, g est souvent confondu
avec l’origine O
22
Pr. OUTTAJ Analyse des Données
Théorème de Huygens
Inertie totale=inertie inetr_classes +inertie intra_classe
Puisque l’inertie totale est constante :
Minimiser l’inertie intra-classe
est équivalent à
Maximiser l’inertie inter-classes
23
Pr. OUTTAJ Analyse des Données
Méthode de Ward
On part de :
1 classe = 1 individu et donc inertie-inter=1
Si ma (resp. mb) est le nombre d’individus de la classe a (resp. b)
alors
Inertie( a ) Inertie(b) Inertie( a b) mm a b
d ²( a, b)
m m
a b
Ce qui revient à minimiser
mm a b
d ²(a, b)
m m a b
24
Pr. OUTTAJ Analyse des Données
Critère de Ward vs Saut minimum
Méthode de Ward Saut minimum
Effet de chaîne
25
Pr. OUTTAJ Analyse des Données
Application du logiciel R pour :
AFC
ACM
CAH
26
Qualité d’une partition
Exprimée par le rapport
inertie _ inter
0 1
inertie totale
La partition est d’autant plus bonne que ce rapport avoisine 1
Quand ce rapport =0 toutes les classes ont la même
moyenne (la partition ne sépare pas les classes)
Quand ce rapport est =1 inertie-intra=0 tous les
individus d’une classe sont identiques classification idéale
27
Nombre de classes
Règle 1 : procéder à plusieurs découpages et analyser les
changements observés lors de chaque découpage
Règle 2 : réaliser autant de découpages jusqu’à ce le rapport
inertie inter/inertie totale soit satisfaisant (pourcentage
d’inertie récupéré)
Attention :
Très peu de classes peut entrainer des classes non homogènes
Beaucoup de classes peut amener à des classes qui ne se
différencient pas beaucoup
28
Nombre de classes
Règle 3:
Des milliers d’individus => max 10 classes
Individus statistiques très différents => construire le maximum
de classes
Règle 4 (générale):
Construire des classes interprétables
29
Nombre de classes (groupes)
30
Méthode de partitionnement k-means
Appelée aussi méthode d’agrégation autour des centres
mobiles ou Nuées dynamiques ou K-Means Cluster Analysis
Si le nombre d’observations est supérieure à 100, il est
recommandé d’utiliser les nuées dynamiques.
Ne nécessite pas la construction d’arbre hiérarchique
31
L’algorithme k-means
L’algorithme s’effectue en 4 étapes :
1. Choisir k individus qui forment k classes C1, C2, …., Ck
2. Affecter (réaffecter) chaque individu O à la classe Ci de
centre Mi dont la distance d(O,Mi) est minimale
3. Recalculer le centre Mi de chaque classe Ci
4. Refaire l’étape 2 si on a effectué une affectation
32
K-means exemple
A={1,2,3,6,7,8,13,15,17}
Supposons qu’on opte pour 3 classes. On choisit donc trois
individus au hasard comme représentant de chaque classe.
Par exemple les individus 1, 2 et 3
Chaque objet est affecté au centre pour lequel la distance est
minimale :
C1={1} ; et M1=1
C2={2} ; et M2=2
C3={3,6,7,8,13,15,17} ; et M3=69/7=9,86
33
Exemple(suite)
On commence par l’affectation de l’individu 3 :
On a : d(3,M2)=1< d(3,M1)=2 <d(3,M3)=6,86 et on affecte
donc l’individu 3 à la classe C2 et on recalcule les nouveaux
centres de C2 et C3 (C1 n’a pas changé) :
C1={1} ; et M1=1
C2={2;3} ; et M2=2,5
C3={6;7;8;13;15;17} ; et M3=66/6=11
d(6,M2)=3,5< d(6,M3)=d(6,M1) =5 donc 6 passe à C2 et
C1={1} ; et M1=1
C2={2;3;6} ; et M2=11/3=3,67
C3={7;8;13;15;17} ; et M3=60/5=12
34
Exemple (suite)
d(2,M1)=1< d(2,M2)=1,67<d(2,M3) =10 donc 2 passe à C1 et
C1={1;2} ; et M1=1,5
C2={3;6} ; et M2=9/2=4,5
C3={7;8;13;15;17} ; et M3=60/5=12
Puis 7 passe à C2
Puis 3 passe à C1 :
C1={1;2;3} ; et M1=2
C2={6;7;8} ; et M2=7
C3={13;15;17} ; et M3=15
Puis les classes sont stables et aucun individu ne bouge
(barycentres bien placés au milieu)
35
Remarques
i. L'inconvénient de la méthode k-means :
a) Elle ne permet pas de déterminer le nombre optimal de
classes
b) Ne permet pas de visualiser la proximité entre les classes ou
les individus.
ii. Les méthodes k-means et la CAH sont complémentaires.
iii. Pour les variables qualitatives, on peut appliquer la
méthode k-means sur les coordonnées des variables sur les
axes factoriels après avoir exécuté une ACM
36
Bon courage
Pr. OUTTAJ
37