130
5 Segmentation
avec la moyenne la plus proche. Plus pr´ ecis´ ement si on note S l’ensemble de
toutes les partitions possibles des pixels en K ensembles S 1 , ¨ ¨ ¨ , S K on veut
minimiser sur S la fonctionnelle
EpS 1 , ¨ ¨ ¨ , S K q “
K
ÿ
i“1
ÿ
x j PS i
}x j ´ μ i }
2
o` u μ i est la moyenne des points de S i . L’algorithme est le suivant :
Algorithme 6 K-means
Initialisation. Ensemble de K moyennes m 1
1 , ¨ ¨ ¨ , m 1
K (par exemple g´ en´ er´ ees
al´ eatoirement) ; n “ 1.
Affectation : on affecte chaque pixel ` a la classe dont la moyenne est la plus proche
S
n
i “
x p :
›
› x p ´ m
n
i
›
› ď
›
› x p ´ m
n
j
›
› @ 1 ď j ď K
(
,
o` u chaque x p est affect´ e ` a exactement une classe de S n , mˆ eme s’il peut ˆ etre dans
plusieurs classes.
Actualisation : on calcule les nouvelles moyennes, qui sont les centres des nouvelles
classes
m
n`1
i
“
1
|S n
i |
ÿ
x j PS n
i
x j .
Arrˆ et quand les affectations ne changent plus.
Il y a un nombre fini de partitions possibles ` a K classes (qui peut ˆ etre
tr` es grand) et la fonctionnelle E n’est pas convexe. On ne peut donc obtenir
a priori qu’un minimum local. Chaque ´ etape de l’algorithme fait strictement
diminuer E et fait d´ ecouvrir une meilleure partition. Cela permet d’affirmer
que l’algorithme converge toujours en temps fini (vers un minimum local).
Toutefois, la convergence peut ˆ etre lente et on peut rajouter des limiteurs du
nombre d’it´ erations. De plus, la solution fournie par cet algorithme d´ epend
fortement de l’initialisation choisie. Les m´ ethodes d’initialisation les plus utilis´ ees sont des m´ ethodes Forgy et le partionnement al´ eatoire [51]. La m´ ethode
Forgy effectue un choix al´ eatoire de K observations des donn´ ees et les utilise comme moyennes (centres) initiales. Le partitionnement al´ eatoire assigne
al´ eatoirement une classe ` a chaque observation et effectue l’´ etape d’actualisation c’est-` a-dire le calcul des moyennes des ´ el´ ements des classes ainsi d´ efinies.
Selon [51] la m´ ethode Forgy est pr´ ef´ erable pour l’algorithme des K-means.
Enfin, le fait de devoir choisir a priori le param` etre K peut ˆ etre aussi un
inconv´ enient.
5 Segmentation
avec la moyenne la plus proche. Plus pr´ ecis´ ement si on note S l’ensemble de
toutes les partitions possibles des pixels en K ensembles S 1 , ¨ ¨ ¨ , S K on veut
minimiser sur S la fonctionnelle
EpS 1 , ¨ ¨ ¨ , S K q “
K
ÿ
i“1
ÿ
x j PS i
}x j ´ μ i }
2
o` u μ i est la moyenne des points de S i . L’algorithme est le suivant :
Algorithme 6 K-means
Initialisation. Ensemble de K moyennes m 1
1 , ¨ ¨ ¨ , m 1
K (par exemple g´ en´ er´ ees
al´ eatoirement) ; n “ 1.
Affectation : on affecte chaque pixel ` a la classe dont la moyenne est la plus proche
S
n
i “
x p :
›
› x p ´ m
n
i
›
› ď
›
› x p ´ m
n
j
›
› @ 1 ď j ď K
(
,
o` u chaque x p est affect´ e ` a exactement une classe de S n , mˆ eme s’il peut ˆ etre dans
plusieurs classes.
Actualisation : on calcule les nouvelles moyennes, qui sont les centres des nouvelles
classes
m
n`1
i
“
1
|S n
i |
ÿ
x j PS n
i
x j .
Arrˆ et quand les affectations ne changent plus.
Il y a un nombre fini de partitions possibles ` a K classes (qui peut ˆ etre
tr` es grand) et la fonctionnelle E n’est pas convexe. On ne peut donc obtenir
a priori qu’un minimum local. Chaque ´ etape de l’algorithme fait strictement
diminuer E et fait d´ ecouvrir une meilleure partition. Cela permet d’affirmer
que l’algorithme converge toujours en temps fini (vers un minimum local).
Toutefois, la convergence peut ˆ etre lente et on peut rajouter des limiteurs du
nombre d’it´ erations. De plus, la solution fournie par cet algorithme d´ epend
fortement de l’initialisation choisie. Les m´ ethodes d’initialisation les plus utilis´ ees sont des m´ ethodes Forgy et le partionnement al´ eatoire [51]. La m´ ethode
Forgy effectue un choix al´ eatoire de K observations des donn´ ees et les utilise comme moyennes (centres) initiales. Le partitionnement al´ eatoire assigne
al´ eatoirement une classe ` a chaque observation et effectue l’´ etape d’actualisation c’est-` a-dire le calcul des moyennes des ´ el´ ements des classes ainsi d´ efinies.
Selon [51] la m´ ethode Forgy est pr´ ef´ erable pour l’algorithme des K-means.
Enfin, le fait de devoir choisir a priori le param` etre K peut ˆ etre aussi un
inconv´ enient.