计算机工程与应用 ›› 2020, Vol. 56 ›› Issue (13): 63-71.DOI: 10.3778/j.issn.1002-8331.1906-0070

• 理论与研发 • 上一篇    下一篇

局部迭代的快速K-means聚类算法

李峰,李明祥,张宇敬   

  1. 1.河北金融学院 信息管理与工程系,河北 保定 071051
    2.河北省高校智慧金融应用技术研发中心,河北 保定 071051
  • 出版日期:2020-07-01 发布日期:2020-07-02

Partial Iterative Fast K-means Clustering Algorithm

LI Feng, LI Mingxiang, ZHANG Yujing   

  1. 1.Information Management and Engineering Department, Hebei Finance University, Baoding, Hebei 071051, China
    2.Applied Technology Research and Development Center Wisdom Finance in Hebei University, Baoding, Hebei 071051, China
  • Online:2020-07-01 Published:2020-07-02

摘要:

为了解决K-means算法在聚类数量增多的情况下,因选择了不合适的中心初值而影响到聚类效果这一问题,提出了一种局部迭代的快速K-means聚类算法(PIFKM+?)。该算法在K-means聚类的基础上,不断寻找能够被分割的聚类簇和能够被删除的聚类簇,并对受影响的局部数据进行重新聚类处理,降低了整个聚类更新的时间复杂度,提高了聚类的效果。PIFKM+?算法在面对聚类数量众多的情况下,具有能够快速更新聚类、对聚类中心初值不敏感、能够提高聚类精确度等优势。通过与K-means和K-means++两种算法的比较,在仿真数据集和真实数据集的综合实验下,验证了该算法的精确性、高效率性和可扩展性,同时实验结果的统计分析表明该算法在提高了聚类精确度的同时并没有损失太多的时间效率。

关键词: K-means算法, 聚类分割, 聚类删除, 局部迭代聚类, 聚类邻居

Abstract:

The K-means algorithm is one of the most popular and widely spread clustering methods. But it is not always possibly to find the appropriate initial value of the cluster centers, especially when the number of clusters is increased. If it can’t find suitable initial values, that will affect the clustering effect. This paper proposes an iterative approach to improve the quality of the clustering. This method called Partial Iterative Fast K-means plus-minus(PIFKM+?). Based on the K-means clustering, the algorithm divides a cluster and removes another one, then re-clusters the affected data, in each iteration. The algorithm reduces the time complexity and improves the effect of clustering. The proposed method has the advantages of being able to update clusters quickly, is insensitive to initial values of cluster centers, and can improve clustering accuracy in the face of a large number of clusters. By comparing with the K-means and K-means++, experimental results vividly demonstrate that the algorithm has better clustering effect, higher operating efficiency and scalability on the simulation data sets and the real data sets. Through the statistical analysis of the final experimental results, it is shown that the PIFKM+? algorithm does not lose too much time efficiency while improving clustering accuracy.

Key words: K-means algorithm, cluster segmentation, cluster removing, partial iterative clustering, cluster neighbor