论文部分内容阅读
摘 要： 针对传统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]的实验结果，体现了本文算法的优越性。其中，文献[11]提出了一种自适应聚类算法，根据误差平方和（SSE）趋势自动确定簇数，在不增加迭代次数的情况下得到了准确聚类结果。文献[12]则是在文献[11]提出的算法上进行改进，并且最终实验结果在准确率上有所提升。而本文的算法对比于两种算法，在保持准确率的情况下，迭代次数大幅下降。对比于传统K-means算法，新算法同时具备准确率高和迭代次数少的优点。
1 算法综述
1.1 算法相关定义
1.2 算法思想描述
首先设需要聚类的类别数为K。
根据数据集X构造相异度矩阵R，然后建立初始化许可集合S，S包含X中每个样本点的下标，即第1个样本点对应S中的1。
对存在于集合S当中样本点的邻域U_i，计算样本点间的平均相异度，平均相异度最小的K个邻域对应的中心样本点即作为候选的初始聚类中心。此时，按平均相异度从小到大的趋势，依次判断其余中心样本点是否存在于第一个中心样本点的邻域当中，若不存在，则判断后续中心样本点是否存在于第二个中心样本点的邻域中，以此类推，找到首个存在于前者中心样本点邻域中的样本点，将该样本点对应的下标从集合S中删除，重新执行本段的算法;否则，若这K个样本点间互不存在于彼此的邻域当中，则将这K个样本点作为最终的初始聚类中心。 将得到的初始聚类中心作为参数，采用K-means算法进行聚类，即可得到K类样本点。对比于UCI数据集已划分的类别，判断每个样本点是否准确分到各类当中，由此计算分类的准确率。
1.3 算法步骤
⑴ 根据数据集X建立相异度矩阵R，同时构造初始许可集合S;
⑵ 对R中的每一行进行排序，并记录对应的索引下标，取前元素建立Rr_jki;
⑶ 对于样本点x_i，计算邻域内其余样本点与x_i的相异度平均值，记为mean_Rr_i，i∈1，2，…，n，若i?S，则令mean_Rr_i=∞;
⑷ 找到mean_Rr_i中最小的K个值，对应的下标逐个添加到集合idx中;
⑸ 按j从小到大的顺序判断x_（idx（j））是否存在于邻域U_（idx（i））中，j∈{2，3，…，K};i=min{j}-1，当找到第一个满足的样本点时，进入⑹，若不存在，删去集合j中的第一个元素，令i=i+1，继续按j从小到大的顺序判断x_（idx（j））是否存在于邻域U_（idx（i））中，按上述的方法循环判断，若出现j为空，则进入⑺;
⑹ 将该样本点从许可集合S中除去，重新从⑵开始执行;
⑺ 將集合idx中元素对应的样本点作为初始聚类中心;
⑻ 利用K-means算法得到聚类结果，并计算准确率。
2 实验
本文实验采用UCI数据集中的三种数据集进行实验，数据集分别为Iris，Wine，Seeds，对应的描述如表1。
对比的算法包括传统K-means算法、文献[11]和文献[12]的算法。其中，由于K-means的不稳定性，本文实验中将对其运行十次得到的结果取平均作为对比数据。
不同算法的实验结果如表2-表4所示。
根据表2-表4的结果可以看出，与传统的K-means算法对比，本文算法的运行结果在准确率和迭代次数上都有所优化。在Iris数据集中，平均迭代次数下降4.5次，平均准确率则是提高2.8%;在Wine数据集中，平均迭代次数下降3.2次，平均准确率提高约1.3%;而在Seeds数据集中，平均迭代次数下降最多，为5.1次，同时准确率提高约0.14%。
另一方面，与改进的两种算法进行比较，新算法在保持准确率几乎不变的情况下，迭代次数有较大幅度的下降。在Iris数据集中，新算法迭代次数比以往最优的算法还要少4次，准确率虽有所下降，但下降幅度可忽略;在Wine数据集中，新算法准确率与改进算法持平，而迭代次数却有下降至少1次;最后在Seeds数据集中，本文算法在保持准确率的前提下，迭代次数大幅度下降，由原来的12次和8次下降到3次，下降程度明显。
由图1可见，本文算法的迭代次数明显低于其余算法，在该方面有较大的改进。
3 结束语
针对传统K-means算法聚类不稳定以及两种改进算法迭代次数较多的缺陷，提出了一种新的具有稳定聚类效果且迭代次数较少的算法，该算法基于相异度和邻域，选取K个相互距离较远且邻域内样本点较密集的初始聚类中心。
实验结果表明，新算法不仅准确率较高，还弥补了迭代次数较多的缺陷，大幅度减少了K-means算法所需的迭代次数，具有更好的应用前景。
参考文献（References）：
[1] 陈欢，曹承富，张存岭，李玮，乔玉强，杜世州，赵竹.基于主成分-聚类分析评价长期施肥对砂姜黑土肥力的影响[J].土壤学报，2014.51（3）：609-617
[2] 唐利明，王洪珂，陈照辉，黄大荣.基于变分水平集的图像模糊聚类分割[J].软件学报，2014.25（7）：1570-1582
[3] 雍玉洁，顾华.基于空间聚类和边缘梯度的图像分割算法[J].计算机与现代化，2021.2）：13-17
[4] 陈磊，周丽苹，班茂盛，郑运鸿.基于聚类分析的中国低龄老年人力资源水平区域差异研究[J].人口学刊，2015.37（4）：55-65
[5] 杨俊闯，赵超.K-Means聚类算法研究综述[J].计算机工程与应用，2019.55（23）：7-14，63
[6] 李荟娆. K-means聚类方法的改进及其应用[D].东北农业大学，2014.
[7] 崔丹丹.K-Means聚类算法的研究与改进[D].安徽大学，2012.
[8] 孟子健，马江洪.一种可选初始聚类中心的改进k均值算法[J].统计与决策，2014.12：12-14
[9] 董秋仙，朱赞生.一种新的选取初始聚类中心的K-means算法[J].统计与决策，2020.36（16）：32-35
[10] 赵明清，蒋昌俊，陶树平.基于等价相异度矩阵的聚类[J].计算机科学，2004.7：183-184
[11] 成卫青，卢艳红.一种基于最大最小距离和SSE的自适应聚类算法[J].南京邮电大学学报（自然科学版），2015.35（2）：102-107
[12] 曹端喜，唐加山，陈香.一种优化初始聚类中心的自适应聚类算法[J].软件导刊，2020.19（7）：28-31
收稿日期：2021-03-29
作者简介：张嘉龙（2000-），男，广东梅州人，本科，主要研究方向：机器学习。
关键词： 相异度; 聚类; 初始聚类中心; 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]的实验结果，体现了本文算法的优越性。其中，文献[11]提出了一种自适应聚类算法，根据误差平方和（SSE）趋势自动确定簇数，在不增加迭代次数的情况下得到了准确聚类结果。文献[12]则是在文献[11]提出的算法上进行改进，并且最终实验结果在准确率上有所提升。而本文的算法对比于两种算法，在保持准确率的情况下，迭代次数大幅下降。对比于传统K-means算法，新算法同时具备准确率高和迭代次数少的优点。
1 算法综述
1.1 算法相关定义
1.2 算法思想描述
首先设需要聚类的类别数为K。
根据数据集X构造相异度矩阵R，然后建立初始化许可集合S，S包含X中每个样本点的下标，即第1个样本点对应S中的1。
对存在于集合S当中样本点的邻域U_i，计算样本点间的平均相异度，平均相异度最小的K个邻域对应的中心样本点即作为候选的初始聚类中心。此时，按平均相异度从小到大的趋势，依次判断其余中心样本点是否存在于第一个中心样本点的邻域当中，若不存在，则判断后续中心样本点是否存在于第二个中心样本点的邻域中，以此类推，找到首个存在于前者中心样本点邻域中的样本点，将该样本点对应的下标从集合S中删除，重新执行本段的算法;否则，若这K个样本点间互不存在于彼此的邻域当中，则将这K个样本点作为最终的初始聚类中心。 将得到的初始聚类中心作为参数，采用K-means算法进行聚类，即可得到K类样本点。对比于UCI数据集已划分的类别，判断每个样本点是否准确分到各类当中，由此计算分类的准确率。
1.3 算法步骤
⑴ 根据数据集X建立相异度矩阵R，同时构造初始许可集合S;
⑵ 对R中的每一行进行排序，并记录对应的索引下标，取前元素建立Rr_jki;
⑶ 对于样本点x_i，计算邻域内其余样本点与x_i的相异度平均值，记为mean_Rr_i，i∈1，2，…，n，若i?S，则令mean_Rr_i=∞;
⑷ 找到mean_Rr_i中最小的K个值，对应的下标逐个添加到集合idx中;
⑸ 按j从小到大的顺序判断x_（idx（j））是否存在于邻域U_（idx（i））中，j∈{2，3，…，K};i=min{j}-1，当找到第一个满足的样本点时，进入⑹，若不存在，删去集合j中的第一个元素，令i=i+1，继续按j从小到大的顺序判断x_（idx（j））是否存在于邻域U_（idx（i））中，按上述的方法循环判断，若出现j为空，则进入⑺;
⑹ 将该样本点从许可集合S中除去，重新从⑵开始执行;
⑺ 將集合idx中元素对应的样本点作为初始聚类中心;
⑻ 利用K-means算法得到聚类结果，并计算准确率。
2 实验
本文实验采用UCI数据集中的三种数据集进行实验，数据集分别为Iris，Wine，Seeds，对应的描述如表1。
对比的算法包括传统K-means算法、文献[11]和文献[12]的算法。其中，由于K-means的不稳定性，本文实验中将对其运行十次得到的结果取平均作为对比数据。
不同算法的实验结果如表2-表4所示。
根据表2-表4的结果可以看出，与传统的K-means算法对比，本文算法的运行结果在准确率和迭代次数上都有所优化。在Iris数据集中，平均迭代次数下降4.5次，平均准确率则是提高2.8%;在Wine数据集中，平均迭代次数下降3.2次，平均准确率提高约1.3%;而在Seeds数据集中，平均迭代次数下降最多，为5.1次，同时准确率提高约0.14%。
另一方面，与改进的两种算法进行比较，新算法在保持准确率几乎不变的情况下，迭代次数有较大幅度的下降。在Iris数据集中，新算法迭代次数比以往最优的算法还要少4次，准确率虽有所下降，但下降幅度可忽略;在Wine数据集中，新算法准确率与改进算法持平，而迭代次数却有下降至少1次;最后在Seeds数据集中，本文算法在保持准确率的前提下，迭代次数大幅度下降，由原来的12次和8次下降到3次，下降程度明显。
由图1可见，本文算法的迭代次数明显低于其余算法，在该方面有较大的改进。
3 结束语
针对传统K-means算法聚类不稳定以及两种改进算法迭代次数较多的缺陷，提出了一种新的具有稳定聚类效果且迭代次数较少的算法，该算法基于相异度和邻域，选取K个相互距离较远且邻域内样本点较密集的初始聚类中心。
实验结果表明，新算法不仅准确率较高，还弥补了迭代次数较多的缺陷，大幅度减少了K-means算法所需的迭代次数，具有更好的应用前景。
参考文献（References）：
[1] 陈欢，曹承富，张存岭，李玮，乔玉强，杜世州，赵竹.基于主成分-聚类分析评价长期施肥对砂姜黑土肥力的影响[J].土壤学报，2014.51（3）：609-617
[2] 唐利明，王洪珂，陈照辉，黄大荣.基于变分水平集的图像模糊聚类分割[J].软件学报，2014.25（7）：1570-1582
[3] 雍玉洁，顾华.基于空间聚类和边缘梯度的图像分割算法[J].计算机与现代化，2021.2）：13-17
[4] 陈磊，周丽苹，班茂盛，郑运鸿.基于聚类分析的中国低龄老年人力资源水平区域差异研究[J].人口学刊，2015.37（4）：55-65
[5] 杨俊闯，赵超.K-Means聚类算法研究综述[J].计算机工程与应用，2019.55（23）：7-14，63
[6] 李荟娆. K-means聚类方法的改进及其应用[D].东北农业大学，2014.
[7] 崔丹丹.K-Means聚类算法的研究与改进[D].安徽大学，2012.
[8] 孟子健，马江洪.一种可选初始聚类中心的改进k均值算法[J].统计与决策，2014.12：12-14
[9] 董秋仙，朱赞生.一种新的选取初始聚类中心的K-means算法[J].统计与决策，2020.36（16）：32-35
[10] 赵明清，蒋昌俊，陶树平.基于等价相异度矩阵的聚类[J].计算机科学，2004.7：183-184
[11] 成卫青，卢艳红.一种基于最大最小距离和SSE的自适应聚类算法[J].南京邮电大学学报（自然科学版），2015.35（2）：102-107
[12] 曹端喜，唐加山，陈香.一种优化初始聚类中心的自适应聚类算法[J].软件导刊，2020.19（7）：28-31
收稿日期：2021-03-29
作者简介：张嘉龙（2000-），男，广东梅州人，本科，主要研究方向：机器学习。