Geodesic
How the initialization affects the stability of the k-means algorithm
ESAIM: Probability and Statistics, Tome 16 (2012), pp. 436-452 Cet article a éte moissonné depuis la source Numdam

Voir la notice de l'article

We investigate the role of the initialization for the stability of the қ-means clustering algorithm. As opposed to other papers, we consider the actual қ-means algorithm (also known as Lloyd algorithm). In particular we leverage on the property that this algorithm can get stuck in local optima of the қ-means objective function. We are interested in the actual clustering, not only in the costs of the solution. We analyze when different initializations lead to the same local optimum, and when they lead to different local optima. This enables us to prove that it is reasonable to select the number of clusters based on stability scores.

DOI : 10.1051/ps/2012013
Classification : 62F12
Keywords: clustering, қ-means, stability, model selection 
@article{PS_2012__16__436_0,
     author = {Bubeck, S\'ebastien and Meil\u{a}, Marina and von Luxburg, Ulrike},
     title = {How the initialization affects the stability of the $k$-means algorithm},
     journal = {ESAIM: Probability and Statistics},
     pages = {436--452},
     year = {2012},
     publisher = {EDP-Sciences},
     volume = {16},
     doi = {10.1051/ps/2012013},
     mrnumber = {2972502},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1051/ps/2012013/}
}
TY  - JOUR
AU  - Bubeck, Sébastien
AU  - Meilă, Marina
AU  - von Luxburg, Ulrike
TI  - How the initialization affects the stability of the $k$-means algorithm
JO  - ESAIM: Probability and Statistics
PY  - 2012
SP  - 436
EP  - 452
VL  - 16
PB  - EDP-Sciences
UR  - http://geodesic.mathdoc.fr/articles/10.1051/ps/2012013/
DO  - 10.1051/ps/2012013
LA  - en
ID  - PS_2012__16__436_0
ER  - 
%0 Journal Article
%A Bubeck, Sébastien
%A Meilă, Marina
%A von Luxburg, Ulrike
%T How the initialization affects the stability of the $k$-means algorithm
%J ESAIM: Probability and Statistics
%D 2012
%P 436-452
%V 16
%I EDP-Sciences
%U http://geodesic.mathdoc.fr/articles/10.1051/ps/2012013/
%R 10.1051/ps/2012013
%G en
%F PS_2012__16__436_0
Bubeck, Sébastien; Meilă, Marina; von Luxburg, Ulrike. How the initialization affects the stability of the $k$-means algorithm. ESAIM: Probability and Statistics, Tome 16 (2012), pp. 436-452. doi: 10.1051/ps/2012013

Cité par Sources :