摘 要：K-means 算法从样本集随机选取初始聚类中心导致聚类结果不稳定，且聚类性能易受奇异点影响。针对以上缺陷，文章定义基于相异度矩阵的邻域半径概念，依次选取最小邻域半径对应的样本作为初始聚类中心，直到邻域半径达到样本集的平均邻域半径；若选取的聚类中心数量不足 K 个，逐步缩小邻域参数探索，直到选出 K 个。随后给出基于实验的剔除奇异点公式，得到最终的聚类结果。实验结果表明，算法在准确度和迭代次数两方面均有所改进。
关键词：K-means 聚类；相异度；邻域半径；初始聚类中心；奇异点
DOI:10.19850/j.cnki.2096-4706.2021.07.017
基金项目：国家自然科学基金青年项目（117 01189）；广东省大学生创新创业项目（S20201056 4034）；华南农业大学微达安产业学院项目
中图分类号：TP273.4 文献标识码：A 文章编号：2096-4706（2021）07-0067-04
Improved K-means Algorithm Based on Dissimilarity Neighborhood
LI Hanbo，WEI Fuyi，ZHANG Jialong，LIU Zhiwei
（South China Agricultural University，Guangzhou 510642，China）
Abstract：The K-means algorithm selects the initial clustering centers from the sample set at random，which leads to unstable clustering results，and the clustering performance is easily affected by singularity. In view of above defects，the paper defines the concept of neighborhood radius based on the dissimilarity matrix，and successively selects the samples corresponding to the minimum neighborhood radius as the initial clustering centers，until the neighborhood radius reaches the average neighborhood radius of the sample set；if the number of selected clustering centers is less than K，the neighborhood parameter is gradually reduced to explore，until K initial clustering centers are selected. Then the formula of eliminating singular points based on experiment is given，and the final clustering result is obtained. Experimental results show that the algorithm is improved in accuracy and iteration times.
Keywords：K-means clustering；dissimilarity；neighborhood radius；initial cluster center；singularity
参考文献：
[1] MACQUEEN J B. Some Methods for Classification and Analysis of Multivariate Observations [C]//Proc. of 5th Berkeley Symposium on Mathematical Statistics and Probability.Berkeley：Univ. California Press，1967：281-297.
[2] 赵庆 . 基于 Hadoop 平台下的 Canopy-Kmeans 高效算法 [J]. 电子科技，2014，27（2）：29-31.
[3] 高国琴，李明 . 基于 K-means 算法的温室移动机器人导 航路径识别 [J]. 农业工程学报，2014，30（7）：25-33.
[4] 彭育辉，杨辉宝，李孟良，等 . 基于 K- 均值聚类分析的 城市道路汽车行驶工况构建方法研究 [J]. 汽车技术，2017（11）： 13-18.
[5] 韩凌波，王强，蒋正锋，等 . 一种改进的 K-means 初始 聚类中心选取算法 [J]. 计算机工程与应用，2010，46（17）：150- 152.
[6] 孟子健，马江洪 . 一种可选初始聚类中心的改进 K 均值算 法 [J]. 统计与决策，2014（12）：12-14.
[7] 唐东凯，王红梅，胡明.优化初始聚类中心的改进K-means 算法 [J]. 小型微型计算机系统，2018，39（8）：1819-1823.
[8] 李武，赵娇燕，严太山 . 基于平均差异度优选聚类中心 的改进 K- 均值聚类算法 [J]. 控制与决策，2017，32（4）：759- 762.
[9] 杨华晖，孟晨，王成，等 . 基于目标特征选择和去除的改 进 K-means 聚类算法 [J]. 控制与决策，2019，34（6）：1219- 1226.
[10] 刘美玲，黄名选，汤卫东 . 基于离散量优化初始聚类 中心的 K-means 算法 [J]. 计算机工程与科学，2017，39（6）： 1164-1170.
[11] 王世其，张文斌，蔡潮森，等 . 最小局部方差优化初始聚 类中心的 K-means 算法 [J]. 软件导刊，2020，19（6）：196-200.
[12] 董秋仙，朱赞生 . 一种新的选取初始聚类中心的 K-means 算法 [J]. 统计与决策，2020，36（16）：32-35.
[13] 蒋丽，薛善良.优化初始聚类中心及确定K值的K-means 算法 [J]. 计算机与数字工程，2018，46（1）：21-24+113.
[14] 左进，陈泽茂 . 基于改进 K 均值聚类的异常检测算法 [J]. 计算机科学，2016，43（8）：258-261.
[15] 张硕，金鑫，李兆峰，等.基于网络LOF和自适应K-means 的离群点检测算法 [J]. 指挥信息系统与技术，2019，10（1）：90- 94.
[16] ASUNCION A，NEWMAN D.UCI Machine Learning Respository [EB/OL].[2015-06-01].http://archive.ics.uci.edu.
[17] 曹端喜，唐加山，陈香 . 一种优化初始聚类中心的自适 应聚类算法 [J]. 软件导刊，2020，19（7）：28-31.
作者简介：李汉波（1999—），男，汉族，广东茂名人，本科 在读，研究方向：数据挖掘；通讯作者：魏福义（1964—），男， 汉族，山西阳泉人，教授，硕士，研究方向：组合矩阵论、人工 智能；张嘉龙（2000—），男，汉族，广东梅州人，本科在读，研 究方向：人工智能；刘志伟（2001—），男，汉族，广东茂名人， 本科在读，研究方向：人工智能。