Clustering par
kmeans
L. Macaire -
M1 IVI - RDF
- Cours 8
Introduction
Principes
Algorithme
Clustering par kmeans
Exemples
L. Macaire - M1 IVI - RDF - Cours 8
11 mars 2014
1/14
Motivations et objectifs du cours
Clustering par
kmeans Classification des données sans connaissance a priori
L. Macaire - Mise en oeuvre de la méthode K-means
M1 IVI - RDF
- Cours 8 Segmentation d’une image multi-variée
Introduction
Principes
Algorithme
Exemples
Niveaux de gris rdf-2-classes- Niveaux de texture rdf-2-
[Link] [Link]
2/14
Motivations et objectifs du cours
Clustering par
kmeans
Projection des pixels dans l’espace des attributs
L. Macaire -
M1 IVI - RDF
- Cours 8
Mise en oeuvre de la méthode K-means
Introduction
Principes
Algorithme
Exemples
Espace d’atributs Observations classées en 2
classes
3/14
Motivations et objectifs du cours
Clustering par
kmeans Classification des pixels par comparaison des distances
L. Macaire -
M1 IVI - RDF
observations-centres de gravité
- Cours 8
Introduction
Principes
Algorithme
Exemples
Observations classées en 2 Image segmentée en 2 classes
classes
4/14
Matrice des données discrètes X
Clustering par
kmeans
L. Macaire -
M1 IVI - RDF
- Cours 8
Soient N observations pour chacune des D attributs
Xi , i = 1, ..., D.
Introduction
Principes On peut donc représenter les N observations de l’attribut
Algorithme
Exemples xi sous la forme d’un vecteur
xi = (xi,1 , ..., xi, j, ..., xi,N )T
On peut alors rassembler les D vecteurs d’attributs xi dans
une matrice X de dimension D × N.
xi,j est donc le ieme attribut de la jeme observation.
x est une observation quelconque de dimension D.
5/14
Clustering par kmeans - Principes
Clustering par
kmeans
L. Macaire -
M1 IVI - RDF
- Cours 8 Soit K le nombre de classes Ck à retrouver, donné par
l’utilisateur.
Introduction
Principes
Algorithme
L’algorithme kmeans va identifier les K centres de gravité
Exemples µk des classes.
µ̂
Ils minimisent la distance entre les points assignés à
chaque classe et les centre de gravité associés :
1 X
(x − µ ω̂(x) )T .(x − µ ω̂(x) )
N x
où ω̂(x) est la classe d’assignation de la donnée x.
6/14
Clustering par kmeans -Principes
Clustering par
kmeans
L. Macaire -
M1 IVI - RDF
- Cours 8 Minimisation de la distance entre le centre de gravité et
les points assignés à chaque classe :
Introduction
Principes
Algorithme 1 X
Exemples (x − µ ω̂(x) )T .(x − µ ω̂(x) )
N x
où ω̂(x) est la classe d’assignation de la donnée x.
ω̂(x) est la classe dont le centre de gravité est le plus
proche de x :
ω̂(x) = argmink (x − µ k )T .(x − µ k )
7/14
Clustering par kmeans - Algorithme
Clustering par
kmeans
L. Macaire -
M1 IVI - RDF
Données d’entrée : K et X.
- Cours 8
Soient les positions initiales des centres de gravité des
Introduction µ(0)
classes µ̂ k , k = 1, .., K .
Principes
Algorithme
Exemples
t=1
Tant que critère d’arrêt non satisfait
Assignation des points aux K classes
(t−1) T (t−1)
ω̂(x)(t) = argmink (x − µ k ) .(x − µ k )
(t)
Soit Sk l’ensemble des points assignés à la classe k
(t)
Sk = {[Link].ω̂(x)(t) = k}
Mise à jour des
Pcentres de gravité des K classes
µ k (t) = 1(t) x∈S
(t) x
|Sk | k
t =t +1
8/14
Kmeans- Exemple 1
Clustering par
kmeans
L. Macaire -
M1 IVI - RDF
- Cours 8
Introduction
Principes
Algorithme
Exemples
Espace d’atributs µ(0)
µ̂ k
9/14
Kmeans- Exemple 1
Clustering par
kmeans
L. Macaire -
M1 IVI - RDF
- Cours 8
Introduction
Principes
Algorithme
Exemples
(1)
Assignation µk
Mise à jour des centres µ̂
10/14
Kmeans- Exemple 2
Clustering par
kmeans
L. Macaire -
M1 IVI - RDF
- Cours 8
Introduction
Principes
Algorithme
Exemples
(0)
µk
Espace d’atributs et µ̂ t=1
11/14
Kmeans- Exemple 2
Clustering par
kmeans
L. Macaire -
M1 IVI - RDF
- Cours 8
Introduction
Principes
Algorithme
Exemples
t=2 t=3
12/14
Limites de la méthode kmeans
Clustering par
kmeans
L. Macaire -
M1 IVI - RDF
- Cours 8
Introduction
Principes
Sensible aux positions initiales des centres de gravité
Algorithme
Exemples
Nécessite de préciser le nombre K des classes
Critères d’arrêt :
Nombre max d’itérationsP
µ(t)
seuil entre 2 itérations : k (µ
(t−1) T
k − µk µk(t) − µ (t−1)
) (µ k )
Adaptée aux nuages sphériques
13/14
