How the initialization affects the stability of the қ-means algorithm

Bubeck, S; Meila, M; von Luxburg, U

doi:10.1051/ps/2012013

Item

ITEM ACTIONSEXPORT

Add to Basket

Local TagsRelease HistoryDetailsSummary

Released

Journal Article

How the initialization affects the stability of the қ-means algorithm

MPS-Authors

/persons/resource/persons76237

von Luxburg, U
Max Planck Institute for Biological Cybernetics, Max Planck Society;
Department Empirical Inference, Max Planck Institute for Biological Cybernetics, Max Planck Society;

External Resource

https://www.esaim-ps.org/articles/ps/pdf/2012/01/ps120013.pdf
(Publisher version)

Fulltext (restricted access)

There are currently no full texts shared for your IP range.

Fulltext (public)

There are no public fulltexts stored in PuRe

Supplementary Material (public)

There is no public supplementary material available

Citation

Bubeck, S., Meila, M., & von Luxburg, U. (2012). How the initialization affects the stability of the қ-means algorithm. ESAIM: Probability and Statistics, 16, 436-452. doi:10.1051/ps/2012013.

Cite as: https://hdl.handle.net/21.11116/0000-000A-2C64-5

Abstract

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.