K-Means-Type Algorithms: A Generalized Convergence Theorem and Characterization of Local Optimality
- 1 January 1984
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. PAMI-6 (1) , 81-87
- https://doi.org/10.1109/tpami.1984.4767478
Abstract
The K-means algorithm is a commonly used technique in cluster analysis. In this paper, several questions about the algorithm are addressed. The clustering problem is first cast as a nonconvex mathematical program. Then, a rigorous proof of the finite convergence of the K-means-type algorithm is given for any metric. It is shown that under certain conditions the algorithm may fail to converge to a local minimum, and that it converges under differentiability conditions to a Kuhn-Tucker point. Finally, a method for obtaining a local-minimum solution is given.Keywords
This publication has 10 references indexed in Scilit:
- A new approach to clusteringPublished by Elsevier ,2004
- Technical Note—Further Results on the Minimization of a Nonseparable Objective Function Subject to Disjoint ConstraintsOperations Research, 1980
- Clustering Methodologies in Exploratory Data AnalysisPublished by Elsevier ,1980
- A Convergence Theorem for the Fuzzy ISODATA Clustering AlgorithmsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1980
- An Empirical Typology of Adjustment to AgingJournal of Gerontology, 1978
- Clustering techniques: The user's dilemmaPattern Recognition, 1976
- A Physical Interpretation of Fuzzy ISODATAIEEE Transactions on Systems, Man, and Cybernetics, 1976
- N‐DIMENSIONAL LOCATION MODELS: AN APPLICATION TO CLUSTER ANALYSISJournal of Regional Science, 1973
- New experimental results in fuzzy clusteringInformation Sciences, 1973
- Multidimensional group analysisAustralian Journal of Botany, 1966