How the initialization affects the stability of the k-means algorithm
ESAIM: Probability and Statistics, Tome 16 (2012), pp. 436-452.

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.

Classification : 62F12
Mots clés : clustering, қ-means, stability, model selection
     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},
     publisher = {EDP-Sciences},
     volume = {16},
     year = {2012},
     doi = {10.1051/ps/2012013},
     mrnumber = {2972502},
     language = {en},
     url = {}
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
DA  - 2012///
SP  - 436
EP  - 452
VL  - 16
PB  - EDP-Sciences
UR  -
UR  -
UR  -
DO  - 10.1051/ps/2012013
LA  - en
ID  - PS_2012__16__436_0
ER  - 
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.

[1] D. Arthur and S. Vassilvitskii, қ-means++ : the advantages of careful seeding, in Proc. of SODA (2007). | Zbl 1302.68273

[2] S. Ben-David and U. Von Luxburg, Relating clustering stability to properties of cluster boundaries, in Proc. of COLT (2008).

[3] S. Ben-David, U. Von Luxburg and D. Pál, A sober look on clustering stability, in Proc. of COLT (2006). | Zbl 1143.68520

[4] S. Ben-David, D. Pál and H.-U. Simon, Stability of қ-means clustering, in Proc. of COLT (2007). | Zbl 1203.68138

[5] L. Bottou and Y. Bengio, Convergence properties of the қ-means algorithm, in Proc. of NIPS (1995).

[6] S. Dasgupta and L. Schulman, A probabilistic analysis of EM for mixtures of separated, spherical Gaussians. J. Mach. Learn. Res. 8 (2007) 203-226. | MR 2320668 | Zbl 1222.62142

[7] S. Graf and H. Luschgy, Foundations of Quantization for Probability Distributions. Springer (2000). | MR 1764176 | Zbl 0951.60003

[8] D. Hochbaum and D. Shmoys, A best possible heuristic for the -center problem. Math. Operat. Res. 10 (1985) 180-184. | MR 793876 | Zbl 0565.90015

[9] T. Lange, V. Roth, M. Braun and J. Buhmann, Stability-based validation of clustering solutions. Neural Comput. 16 (2004) 1299-1323. | Zbl 1089.68100

[10] R. Ostrovsky, Y. Rabani, L.J. Schulman and C. Swamy, The effectiveness of Lloyd-type methods for the қ-means problem, in Proc. of FOCS (2006). | Zbl 1281.68229

[11] O. Shamir and N. Tishby, Cluster stability for finite samples, in Proc. of NIPS (2008).

[12] O. Shamir and N. Tishby, Model selection and stability in қ-means clustering, in Proc. of COLT (2008).

[13] O. Shamir and N. Tishby, On the reliability of clustering stability in the large sample regime, in Proc. of NIPS (2008).

[14] N. Srebro, G. Shakhnarovich and S. Roweis, An investigation of computational and informational limits in Gaussian mixture clustering, in Proc. of ICML (2006).

[15] Z. Zhang, B. Dai and A. Tung, Estimating local optimums in EM algorithm over Gaussian mixture model, in Proc. of ICML (2008).

Cité par Sources :