K-Means-Type Algorithms: A Generalized Convergence Theorem and Characterization of Local Optimality

Shokri Z. Selim; M. A. Ismail

doi:10.1109/TPAMI.1984.4767478

K-Means-Type Algorithms: A Generalized Convergence Theorem and Characterization of Local Optimality

Shokri Z. Selim
, M. A. Ismail

King Fahd University of Petroleum & Minerals

Research output: Contribution to journal › Article › peer-review

1041 Scopus citations

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.

Original language	English
Pages (from-to)	81-87
Number of pages	7
Journal	IEEE Transactions on Pattern Analysis and Machine Intelligence
Volume	PAMI-6
Issue number	1
DOIs	https://doi.org/10.1109/TPAMI.1984.4767478
State	Published - Jan 1984

Keywords

Basic ISODATA
Index Terms
K-means algorithm
K-means convergence
cluster analysis
numerical taxonomy

ASJC Scopus subject areas

Software
Computer Vision and Pattern Recognition
Computational Theory and Mathematics
Artificial Intelligence
Applied Mathematics

Access to Document

10.1109/TPAMI.1984.4767478

Cite this

@article{2a85123209fe432aa6b73ef44f0f42f0,

title = "K-Means-Type Algorithms: A Generalized Convergence Theorem and Characterization of Local Optimality",

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 = "Basic ISODATA, Index Terms, K-means algorithm, K-means convergence, cluster analysis, numerical taxonomy",

author = "Selim, \{Shokri Z.\} and Ismail, \{M. A.\}",

year = "1984",

month = jan,

doi = "10.1109/TPAMI.1984.4767478",

language = "English",

volume = "PAMI-6",

pages = "81--87",

journal = "IEEE Transactions on Pattern Analysis and Machine Intelligence",

issn = "0162-8828",

number = "1",

}

TY - JOUR

T1 - K-Means-Type Algorithms

T2 - A Generalized Convergence Theorem and Characterization of Local Optimality

AU - Selim, Shokri Z.

AU - Ismail, M. A.

PY - 1984/1

Y1 - 1984/1

N2 - 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.

AB - 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.

KW - Basic ISODATA

KW - Index Terms

KW - K-means algorithm

KW - K-means convergence

KW - cluster analysis

KW - numerical taxonomy

UR - https://www.scopus.com/pages/publications/0021202650

U2 - 10.1109/TPAMI.1984.4767478

DO - 10.1109/TPAMI.1984.4767478

M3 - Article

AN - SCOPUS:0021202650

SN - 0162-8828

VL - PAMI-6

SP - 81

EP - 87

JO - IEEE Transactions on Pattern Analysis and Machine Intelligence

JF - IEEE Transactions on Pattern Analysis and Machine Intelligence

IS - 1

ER -

K-Means-Type Algorithms: A Generalized Convergence Theorem and Characterization of Local Optimality

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Fingerprint

Cite this