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

摘要：

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

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