摘  要： 针对传统K-means算法的聚类不稳定性，提出一种基于相异度与邻域的初始聚类中心选择算法。该算法首先构造相异度矩阵，建立每个样本点的邻域，选取K个相互距离较远且邻域内样本点较密集的初始聚类中心。采用K-means算法思想，利用UCI中的三种数据集进行实验。结果表明，相比传统K-means算法，新算法有稳定的聚类结果，且对比于已经提出的两种改进算法，新的算法在保持准确率的前提下，迭代次数有较大程度的减少。

关键词： 相异度; 聚类; 初始聚类中心; K-means

中图分类号：TP31          文献标识码：A   文章编号：1006-8228（2021）08-57-03

K-means initial clustering center selection algorithm based on

dissimilarity and neighborhood

Zhang Jialong

（College of Mathematics and Information， South China Agricultural University， Guangzhou， Guangdong 510642， China）

Abstract： Aiming at the clustering instability of traditional K-means algorithm， an initial cluster center selection algorithm based on dissimilarity and neighborhood is proposed. The algorithm constructs a dissimilarity matrix， establishes the neighborhood of each sample point， and selects K initial cluster centers that are far apart from each other and the sample points are denser in the neighborhood. The idea of K-means algorithm is adopted， and three data sets in UCI are used for experiment. The results show that compared to the traditional K-means algorithm， the new algorithm has stable clustering results， and compared to the two improved algorithms that had been proposed， the new algorithm has a greater reduction in the number of iterations while maintaining accuracy.

Key words： dissimilarity; clustering; initial cluster centers; K-means

0 引言

機器学习是目前非常火热的一门学科，聚类作为机器学习的其中一种算法，广泛应用于农业[1]、图像处理[2-3]和社会调查[4]等领域。其中K-means聚类因算法易懂和容易实现的优点，使其受到众多研究人员的使用和关注。

K-means[5-7]算法最早由Macqueen提出，是一种基于划分的无监督学习算法。但最初的K-means算法在进行聚类时，不仅不能得到稳定的聚类结果，且容易陷入局部最优解的情况。因此，提出一种具有稳定聚类效果且快速的改进算法是非常必要的。

本文提出的新算法假设聚类个数为K，通过构造相异度矩阵[8-10]，建立每个样本点的邻域，根据不同类别的样本点距离不应靠近且邻域内点较密集的原则，选取K个合适的样本点作为初始聚类中心，随后采用K-means算法的思想对数据集进行聚类，得到稳定的聚类结果。

本文采用UCI数据集中的三种数据集进行实验。通过比较新算法与传统K-means算法和两种改进的算法[11-12]的实验结果，体现了本文算法的优越性。……