Méthodes de clustering

I méthodes par partitionnement

I méthodes hiérarchiques
I méthodes probabilistes : modèles de mélanges, estimation
des niveaux d’une densité par une méthode non
paramétrique ...
I méthodes spectrales
I Mode/Valley seeking : Mean/Medoid/Quick Shift,
graph-based hill climbing
I ...

7/41
I - Classification non supervisée par partitionnement

8/41
(Dis)similarité et distances entre individus
Définition : Dissimilarité
Une dissimilarité est une fonction d : X ⇥ X ! R+ telle que
I 8(xi , x` ) 2 X ⇥ X , d(xi , x` ) = d(x` , xi ) (symétrie)
I d(xi , x` ) = 0 , xi = x`

Définition : Similarité
Une similarité (normée) est une fonction s : X ⇥ X ! [0, 1] telle que
I 8(xi , x` ) 2 X ⇥ X , s(xi , x` ) = s(x` , xi ) (symétrie)
I s(xi , x` ) = 1 , xi = x`
Définition : Distance
Une distance est une dissimilarité d satisfaisant en plus l’inégalité tri-
angulaire

8(xi , x` , xm ) 2 X 3 , d(xi , xm )  d(xi , x` ) + d(x` , xm )

9/41
Attention à la standardisation
4
2

●
● ● ● ●● ● ●
● ●●
● ●
● ●● ●
● ●●
●● ●● ● ●
●● ●●●
0

● ●● ● ● ●
●● ● ●
●● ●
● ● ●
●
●
−2

●
−4

−4 −2 0 2 4 ●
3

●
● ●
2

●
● ● ● ●● ● ● ● ● ●● ●
● ● ●
● ● ●
● ● ● ●
● ● ●
1

● ● ● ● ●●
● ● ●
● ● ● ● ●
● ● ● ● ● ●
● ● ● ● ● ● ● ● ●●●
● ● ●
●● ● ●● ●
● ●
● ● ●
●
0

● ● ● ● ●
●●
● ●
●
−1

−1

●
●●
●
● ●
●
−2

−2

●
−3

−3

−3 −2 −1 0 1 2 3 −3 −2 −1 0 1 2 3

10/41
Exemples pour variables quantitatives

Distances définies comme des formes quadratiques

d 2 (xi , x` ) = (xi x` )0 M(xi x` )

I Norme euclidienne usuelle : M = Ip

⇣ ⌘
1 1
I M = diag 2 , . . . , 2 où j2 = Sjj
1 p

I Distance de Mahalanobis : M = S 1 où S est la matrice de

variance-covariance des données.

11/41
Exemple pour la distance de Mahalanobis
● ●
Y
2.5

●
2.0

●
●
●● ●
●●
1.5

● ●
●
● ●
●
● ● ●
● ●●
●● ● ●● ●●●●● ● ● ●●
● ●● ● ●● ● ●
●
●● ● ●● ●● ●●● ● ●
●● ●
● ● ● ●● ●●●●● ●
1.0

● ● ●
●●● ●●● ● ● ●● ●● ●
● ●●● ●● ● ● ●●
● ● ●● ●● ●●● ●●●●●● ●
●● ● ●● ● ●●● ●●
●
● ●
●●● ● ●●●●● ● ● ● ●●
● ● ●● ● ●
●●●
●●● ●●● ● ●●● ● ● ● ● Z
X ● ● ● ● ●
●
●● ●
●●
0.5

●
●
●●
●
●● ●
●
●
0.0

● ●
●
●
●

−5 0 5
kX Y k2 = 1, 78 kX Y k2,S 1 = 24, 94

kX Z k2 = 6, 25 kX Z k2,S 1 = 5, 92

12/41
Clustering et quantification

Pour une dissimilarité d et r > 0, on définit la “coût" de

quantification du “code" {c1 , . . . , cK } par
n
X
({c1 , . . . , cK }) = d r (xi , {c1 , . . . , cK })
i=1

où d(x, A) = mina2A d(x, a).

13/41
Inerties (cas euclidien)
Soit C = {C1 , . . . , CK } une partition des individus en K classes. On considère
le coût de clustering
n
X
(C) = ({m1 , . . . , mK }) = kxi {m1 , . . . , mK }k2
i=1

1
P
où mk = |Ck |
xi est le centre de gravité de la classe Ck .
i2Ck

n
P
I Inertie totale : IT = 1
n
kxi x̄k 2
i=1
n
P
1
où x̄ = n
xi est le centre de gravité du nuage de points
i=1

K
P
I Inertie interclasse : Iinter = 1
n
|Ck | ⇥ kmk x̄ k2
k =1
V variance des centres des classes

K
P P
I Inertie intra-classe : Iintra = 1
n
kxi mk k2 = 1
n
(C)
k =1 i2Ck
V variance des points d’une même classe

14/41
 Le critère d’inertie

nertie d’un nuage d’individus

Soit un ensemble G d’individus de centre de gravité g ⎛ Notion de variance
1 n ⎜
∑
n
IG = Dist (xi ,g)2 ( Dist ( x , y ) étant une distance quadratique) 1
⎜ sx = ∑ (xi − x )2
2
Inerties n i ⎝ n i

Théorème de König-Huygens : Itot = Iintra + Iinter

Propriété de Huygens
n Gc
∑ Dist (x i, g) =IT∑=∑Iinter + I,g
i c ) + ∑ Gc Dist(gc , g)
2 intra 2 2
Dist(x
i c i c

G1
g1
G3
g3
G2
g g
g4 G4
g2

Bisson (2001)

15/41
 Inerties
Objectif Classification et inertie
Minimiser l’inertie intra-classe
Obtenir des classes cohérentes et contrastées
()
Maximisation de l’inertie inter-classes
}
Maximiser l’inertie inter-classe
équivalent puisque Itot = I intra + I inter
Minimisation de l’inertie intra-classes
Forte inertie inter-classes Faible inertie inter-classes
Faible inertie intra-classes Forte inertie intra-classes

g3

g1 g2

g4

Bisson (2001)
pplication de ce critère
Valeur optimale obtenue pour la partition triviale : un individu par classe 16/41
!

• Fixer le nombre de classes sur lequel on travaille (nuées dynamiques)

• Mesurer la dégradation entraînée par la fusion de plusieurs classes (CAH)
Algorithmes des K-means (Algorithme de Lloyd)
Impossible de parcourir toutes les partitions de X . L’algorithmes des
K-means propose une approximation de la minimisation de .
Data: k , data set X , nombre d’iterations T .
Result: clustering C = {C1 . . . CK }.
Initialisation : choix de K noyaux initiaux c1 , . . . , cK ;
t = 0;
while clustering non stabilisé ou t < T do
t = t+1 ;
for x 2 X do
for k = 1 to K do
Calculer toutes les distances aux centres kx ck k;
end
Affecter x dans le groupe Ck pour lequel kx ck k est minimal
;
end
for k = 1 to K do
Mise à jour du barycentre dans Ck ;
end
end
Animation
17/41
Propriétés

I Avantages
I Relativement efficace : Complexité O(KnT ) où T est le
nombre d’itérations
I L’inertie intra-classe décroit avec les itérations de
l’algorithme
I Découvre les classes compactes, bien séparées

I Inconvénients
I (Spécification du nombre de classes K )
I Influence du choix des noyaux initiaux Animation

I Convergence vers un minimum local

I Peut produire des classes vides
I Influence des outliers Animation

18/41
Choix des noyaux initiaux

I Sélection fondée sur des connaissances complémentaires

I Etude préliminaire des données univariées (histogrammes,

...)

I Réduction de dimension pour initialisée sur une structure

plus robuste (k-means sur les premières composantes de
l’ACP)

I Répétition de la méthode N fois ) N classifications

Sélection de la classification ayant la plus faible inertie
intra-classe

19/41
Choix du nombre de classes

I Choix a priori à partir de connaissances complémentaires

I Pour chaque valeur de K 2 {2, . . . , Kmax }, on obtient une

classification et on sélectionne finalement celle où on
observe un saut important de l’inertie intra-classe : " règle
du coude".

I Choix par maximisation d’un indice. Exemple : silhouette.

20/41
Silhouette

I C(K ) = {C1 , . . . , CK } une classif. de X en K groupes.

Pour i 2 {1, . . . , n} soit Ck la classe de i :
1
P
I a(i) = |Ck | 1 d(xi , x` )
`2Ck
`6=i
1
P
I b(i) = min |C d(xi , x` )
0 k 6=k k0 |
`2Ck 0
b(i) a(i)
I s(i) = max(b(i),a(i)) 2 [ 1, 1]

1 P
I S(C(K )) = n i=1...n s(i)
I Pour une collection de clustering C(2), . . . , C(Kmax ), le
nombre de classes retenu est

K̂ = argmax S(C(K ))
1K Kmax

21/41
Exemple

Evolution Inertie Intra Critere Silhouette

● ● ●
●
●
8

0.42

●
6

0.40

●
●
Silhou

●
Iintra

●
●
●
4

0.38

● ●

●
2

0.36

● ●
●
●
● ● ● ● ● ● ●

2 4 6 8 10 12 14 2 4 6 8 10 12 14

22/41
Jeu simulé - Silhouette

n = 500 8 clusters Cj
j : nj | avei∈Cj si
0.4

1 : 80 | 0.47

2 : 71 | 0.43
average silhouette width

0.3

3 : 61 | 0.44

4 : 82 | 0.44
0.2

5 : 64 | 0.41

6 : 42 | 0.45
0.1

7 : 55 | 0.38

8 : 45 | 0.42
0.0

best
5 8 10 15 20 0.0 0.2 0.4 0.6 0.8 1.0
Silhouette width si
k (# clusters)
Average silhouette width : 0.43

23/41
Variantes des k-means

I Algorithme des k medoids :

Le medoid d’un groupe est le point du groupe le plus
proche de tous les autres (⇠ médiane pour la norme k · k1 ).

24/41
Variantes des k-means
I Algorithme des k medoids
I k-means ++ : Modification de l’initialisation de k-means.
Data: nombre de classes K , data set X
Result: clustering C = {C1 . . . CK }.
Choisir un premier centre c uniformément parmi les xi ;
Initialisation de la famille des centres C = {c} ;
for k = 2 to K do
for i 2 {1 . . . n} do
Calculer d(xi , C) la distance au plus proche centre ;
end
2
Choisir c̃ dans les xi selon les proba P d(xi ,C) 2 ;
x2X d(x,C)
C = C [ {c̃} ;
end
Effectuer k-means avec cette initialisation;

24/41