孙　佳，　胡　明，　赵　佳

(长春工业大学 计算机科学与工程学院， 吉林 长春　130012)



K-means初始聚类中心选取优化算法

孙佳，胡明*，赵佳

(长春工业大学 计算机科学与工程学院， 吉林 长春130012)

摘要：提出了一种利用重心优化初始聚类中心的算法BKM(Barycenter K-Means)。首先将每个候选点临域内所有数据点的重心作为初始聚类中心，然后引入MapReduce进行并行处理计算。结果表明，BKM算法选取的初始聚类中心更为合理，取得了较好的聚类效果。

关键词：聚类; K-means算法; 初始聚类中心; 算法优化

0引言

随着数据时代的到来，数据挖掘技术已经成为当前的研究热点之一[1-4]。聚类分析[5]是数据挖掘领域中一个重要的研究方向，它是将数据集划分成若干个子集，使得每个子集内部的对象相似度较高，而不同子集之间差异性较大。聚类算法大致可分为五类[6]：基于划分的方法、基于层次的方法、基于密度的方法、基于网格的方法和基于模型的方法。其中，K-means算法是基于划分的经典聚类算法之一[7-8]，由于其操作简单、收敛速度快等特点，得到了广泛的应用。但是传统的K-means算法也存在着一些不足之处，首先算法对初始的k个聚类中心有较大依赖性，不同的初始聚类中心得到的聚类结果也不一样，使得初始聚类中心的选取成为影响聚类结果的质量的重要因素之一，传统的K-means算法的初始聚类中心是随机选取的，容易陷入局部最优；再者算法对噪音和离群点敏感；另外，从K-means 算法框架可以看出，该算法需要不断地根据计算后的聚类中心进行分类调整，因此当数据量非常大时，算法有较大的时间开销。……