K-MEANS-TYPE ALGORITHMS - A GENERALIZED CONVERGENCE THEOREM AND CHARACTERIZATION OF LOCAL OPTIMALITY
K-MEANS-TYPE ALGORITHMS - A GENERALIZED CONVERGENCE THEOREM AND CHARACTERIZATION OF LOCAL OPTIMALITY
复制标题
DOI：
10.1109/tpami.1984.4767478
复制
发表时间：
1984-01-01
影响因子：
23.6
通讯作者：
ISMAIL, MA
中科院分区：
文献类型：
--
作者：
SELIM, SZ;ISMAIL, MA
K-均值算法是聚类分析中常用的一种技术。本文对该算法的几个问题进行了讨论。首先将聚类问题归结为一个非凸数学规划。然后，给出了K-均值算法对任意度量的有限收敛的严格证明。证明了该算法在一定条件下不能收敛到局部极小值，在可微条件下收敛到Kuhn-Tucker点。最后给出了一种求局部极小解的方法。
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.