周爱武，潘 勇，崔丹丹，肖 云

(安徽大学 计算机科学与技术学院，安徽 合肥 230039)

K-means算法是基于划分的经典聚类算法，该算法简单、快速，得到了广泛应用，但是该算法对孤立点是敏感的，其次该算法要求用户必须事先给出簇数k值，该算法聚类结果受初始聚类中心随机性选择影响比较大，聚类中心选择不当，容易导致聚类准确度下降，甚至无法得到聚类结果。针对以上缺点，国内外许多专家和学者提出很多对K-means算法的改进，比如参考文献[1]~参考文献[3]是基于密度的对K-means算法进行改进来找到密度比较高的代表点作为初始聚类中心，参考文献[4]是把遗传算法应用到K-means算法中来确定k个初始聚类中心，这种结合能够进行一种全局优化，可提高算法的准确率，将智能算法与K-means算法的结合也是近年来研究的热点。K-means算法以及其改进的算法已经应用到了各个领域，取得了很好的效果，比如参考文献[3]是改进的K-means算法在客户划分中的应用，参考文献[5]是在图像标注和检索的应用，参考文献[6]是在存在异常孤立点大数据集中进行聚类发现簇的应用。由此可见，K-means算法的效率高、时间复杂度低，应用前景宽广。

本文针对初始聚类中心随机选择这个缺陷，提出将凝聚层次聚类算法AGNES应用到改进的算法中，得到k个密度比较高的初始聚类中心，并将其应用到K-means中去进行聚类。实验表明，改进的算法运行效率高，并能获得比较高的准确率。

1 算法的基本思想

1.1 K-means算法

算法接收输入量k，然后将n个数据对象划分为k个聚类以便使得所获得的聚类满足：同一聚类中的对象相似度较高；……