Refining Initial Points for K-Means Clustering
Refining Initial Points for K-Means Clustering
复制标题
DOI：
--
复制
发表时间：
1998-07
期刊：
影响因子：
--
通讯作者：
P. Bradley;U. Fayyad
中科院分区：
文献类型：
--
作者：
P. Bradley;U. Fayyad
聚类的实际方法使用迭代过程（例如K-Means，EM），其收敛于众多局部最小值之一。已知这些迭代技术对初始起始条件特别敏感。我们提出了一个程序，从一个给定的初始条件，是基于一个有效的技术，用于估计分布的模式计算一个细化的起始条件。改进的初始起始条件允许迭代算法收敛到“更好”的局部极小值。该程序适用于广泛的一类离散和连续数据的聚类算法。我们证明了这种方法的流行的K-Means聚类算法的应用，并表明，细化的初始起点确实会导致改进的解决方案。优化运行时间大大低于集群整个数据库所需的时间。该方法是可扩展的，可以耦合到一个可扩展的聚类算法，以解决数据挖掘中的大规模聚类问题。
Practical approaches to clustering use an iterative procedure (e.g. K-Means, EM) which converges to one of numerous local minima. It is known that these iterative techniques are especially sensitive to initial starting conditions. We present a procedure for computing a refined starting condition from a given initial one that is based on an efficient technique for estimating the modes of a distribution. The refined initial starting condition allows the iterative algorithm to converge to a “better” local minimum. The procedure is applicable to a wide class of clustering algorithms for both discrete and continuous data. We demonstrate the application of this method to the popular K-Means clustering algorithm and show that refined initial starting points indeed lead to improved solutions. Refinement run time is considerably lower than the time required to cluster the full database. The method is scalable and can be coupled with a scalable clustering algorithm to address the large-scale clustering problems in data mining.