本栏目责任编辑：梁书
计算机工程应用技术
融合了K 近邻与密度峰值算法的K-means 算法 王炜唯，周云才
(长江大学计算机科学与技术学院，湖北荆州4340200)
摘要：初始聚类中心的随机选择，根据主观经验确定类簇数等问题时常伴随着原始K -means 算法。为了攻克以上问题， 改进算法采用峰值法以及融合了K 近邻算法的密度峰值算法逐一调整。通过在UCI 数据集上测试及与原始K -means 算法、最大最小距离距离算法在准确率、稳定性和处理数据速率方面的比较，其中最为突出的是，改进算法的准确率达到了96%以上。 关键词：K-means 算法；PCA 降维；峰值法；KDPC 算法中图分类号：TP301.6
文献标识码：A
文章编号：1009-3044(2021)08-0182-03
开放科学（资源服务）标识码（OSID ）：
K-means Algorithm Combined with K-nearest Neighbor and Density Peak Algorithm WANG Wei-wei,ZHOU Yun-cai
(School of Computer Science,Yangtze University,Jingzhou 434020,China)
Abstract:The random selection of the initial clustering centers,and the determination of the number of clustering based on subjec⁃tive experience often accompany the original K-means algorithm.In order to overcome the problems,the algorithm used Peak meth⁃od and the fusion of the density peak algorithm and K-nearest neighbor algorithm to adjusted K-means algorithm.The most promi⁃nent of these is that the accuracy of the improved algorithm has reached more than 96%through testing on the UCI dataset and comparing with the original K-meaning algorithm,the maximum and minimum distance algorithm in terms of accuracy,stability and processing data rate.
Key words:K-means algorithm;shannon entropy;improved DPC algorithm
1引言
近年来，数据大爆炸引发了人们对数据分析的需求，数据挖掘技术应运而生。而K-means 算法在数据挖掘中处于重要地位。因其具有简单易懂、容易实现、时间复杂度低，处理庞大数据集效率更高等优点，所以在工作中常常成为首要的选择。然而在该算法也会产生不容忽略的问题[1-4]：①类簇数需要根据经验人工确定；②初始类中心的选择是随机的。
针对上述的不足，本文对算法做了以下改进：首先利用香农熵改进欧式距离计算公式，提高样本点相似度计算的精度；其次同时使用峰值法、融合了K 近邻算法的密度峰值算法(简称KDPC 算法)自动确定类簇数及精准的初始类心。论文的实验数据显示，改进后的算法(简称KDPCK-means 算法)聚类结果十分贴近真实数据分布，算法性能较高。
2原始K-means 算法
2.1原始K-means 算法原理
K-means 算法是经典的无监督聚类算法
功能梯度材料[5-7]
，在对数据处理
前无须知道数据真实类别，直接以数据相似度判断函数来估量
数据间的相似度，将整体未知类别的数据集划分成不同的数据簇。K-means 算法的执行过程是：
1)根据对数据集X 的先验知识，确定数据集X 的类簇数k ；2)在X 中随机选取k 个数据点作首次聚类的k 个类簇的类心c i (i =1,2,...,k)，同样地，每个聚类中心也有d 维属性即c ij (j =1,2,...,d)；
3)计算除类心点以外的剩余数据对象与这k 个类心的相似度，根据计算结果，将这些剩余数据对象分配给最相似的那个类心所属类别，最终形成k 个类簇C i 。相似度计算一般使用欧式距离计算公式：
d pi (x p ,c i )=
∑j =1
d (x
pj
-c ij )2(1)
4)重新计算各个新得到的类簇C i 中所有数据对象d 个维度的均值，将计算结果赋值给聚类中心。然后
重复步骤c 、d 直至聚类目标函数收敛。目标函数的定义如下：
SSE =∑i =1k
∑x ∈C d (x ,c i )
2
(2)
收稿日期：2020-12-20
基金项目：2019年中央引导地方科技发展中的油田数据智能分析研究资金项目（2019ZYYD016）作者简介：王炜唯（1994-），女（土家族），湖北荆州人，硕士研究生，主要研究方向为数据挖掘；周云才（1961-），男，湖北荆州人，教
授，硕导，硕士，主要研究方向为计算理论、软件设计与开发、科学计算可视化等。
182
计算机工程应用技术
本栏目责任编辑：梁
书
Computer Knowledge and Technology 电脑知识与技术
第17卷第8期(2021年3月)
式中的x 代表属于簇C i 的所有数据对象。
2.2原始K-means 算法缺陷分析及改进
根据2.1节中的算法思想可知，原始K-means 算法存在诸多如下缺陷。
1)数据集的最佳聚类数k 根据对数据的先验知识确定，缺乏客观科学性。针对该问题，本文提出峰值法来决此问题。
2)本文利用原始K-means 算法对10维以上数据集聚类时发现，该算法对10维以上的数据集聚类效果很差，因此本文在面对高维数据集时，先对其降维处理，以便得到较好的聚类效果。
3)当初始聚类中心选到含有相同类簇的数据对象时，聚类结果将会偏离真实数据分布情况，生成局部
最优解。针对该问题，本文利用融合了K 近邻算法的密度峰值算法加以解决。
3原始K-means 算法的改进
3.1峰值法确定数据集的最佳类别
实验证实，最佳聚类数范围为[2,Int(n )][8]。本文经过大量实验发现以Calinski-Harabasz 系数(CH)为指标，得到各数据集的最佳聚类数最准确。同时，由于K-means 算法对高维数据集聚类效果差，本文在对高维数据集聚类前采用能最大保留数据信息的PCA 降维。峰值法选取最佳聚类数的过程如下：
1）判断数据集维数，若数据集超过10维，先对数据集采用PCA 降维，然后计算数据集的最佳聚类数范围；
2)在该范围内取不同的整数k 值，对每个确定的k 值用原始K-means 算法对该数据集聚类10次，得到不同k 值对应的最佳CH 值。CH 系数定义如下：
CH (k )=
∑i =1
k n i d 2(c i ,c M )/(k -1)
∑i =1k ∑x ∈c d
2
(x ,c i )/(n -k )
(3)
C i 表示簇C i 的类心，n i 表示簇C i 拥有的数据总数，c M 表示整个数据集的中心即均值，n 表示整体数据集的数据数，即CH 值越大，聚类效果越好。
3)根据b 步骤，以k 为横坐标，CH 系数为纵坐标，画出对应的折线图，选择图中的峰值点对应的k 值即为该数据集的最佳类别数。3.2KDPC 算法
根据大多数据集中样本点的分布可知，类心常被其他样本点环绕，且各个类心之间相隔较远。而这一特点正好符合DPC 算法应用的前提条件。因此该算法可以很好地解决原始K-means 算法中首次聚类类心随意选择的问题。然而该算法在计算样本点局部密度值时未考虑邻近样本点的分布且在选取初始聚类中心时，仍依赖人工选择，因此本文提出KDPC 算法，具体过程如下：
1)样本点局部密度的计算：
乙免(1)引入参数K 结合赋权欧式距离来计算截断距离d c ：
δK i =max j ≤KNN d w (a i ,a j )
(4)μK =
1N ∑i =1
N δK
i
(5)
d c =μK +
(6)
(2)ρi =
∑j ≤KNN exp(-
d 2w (a i ,a j )d 2c
)(7)
上式中的N 代表样本点总数，(4)式表示距离样本点i 最邻
近的第K 个样本点间的赋权欧氏距离，(6)式等号右边的第二项是每个样本点的第K 最邻近赋权欧氏距离与所有样本点的第K 最邻近赋权欧氏距离的均值的标准差。
2)样本点i 的距离计算：
{δi =min j :ρj >pi
(d (ai ,aj )),i ≥1
δj =max j (d (ai ,aj )),ρi 最大
(8)3)画出决策图：
γi =ρi *δi
(9)
中国新诗派
根据上式结果，将其降序排列，然后以γ为纵轴，点的标号
为横轴，建立平面直角坐标系。靠近近横轴、更平滑密集是非类簇中心，而类簇中心远离横轴，且相对分散，类簇中心点与非类簇中心间界限较明显。在自动选取初始类心前需要结合3.1节的峰值法选择排在前k 位的点作为初始类心。
4实验
4.1实验概述
本文在下图所示的数据集上，通过与原始K-means 算法、最大最小距离聚类算法的准确度、稳定性和收敛速度的比较来检验KDPCK-means 算法的改进是否有效。
表1实验数据
数据Iris
Wine
样本量150178
属性数413
类别数33
类簇划分50,50,5059,71,48
4.2实验展示与分析
由于文本篇幅限制，下文主要展示本文算法在Iris 数据集上的运行效果。
图1KDPC 算法决策图
由图1可知：Iris 数据集有3个γ值凸出的间断点，最佳聚类数为3，将前3个最大的γ值点作为Iris 数据集的初始类心。表2KDPCK-means 算法得到的类心与Iris 数据集真实类心
对比
KDPCK-means 算法的
初始类心(5.0,3.4,1.5,0.2)(6.5,2.8,4.6,1.5)(6.1,3.0,4.9,1.8)
KDPCK-means 算法的最终
类心
(5.006,3.428,1.462,0.246)(5.900,2.741,4.237,1.314)(6.610,2.998,5.549,2.024)
Iris 数据集真实类心(5.006,3.428,1.462,0.246)(5.936,2.770,4.260,1.326)(6.588,2.974,5.552,2.026)
183
本栏目责任编辑：梁书
计算机工程应用技术Computer Knowledge and Technology 电脑知识与技术第17卷第8期(2021年3月)
由表2可知，KDPCK-means 算法得到的初始类心、最终类
心与Iris 数据集真实类心十分接近。
絮凝剂>江新蓉表3各个算法的精确度(单位：%)及迭代次数的对比
数据
Iris Wine
K-means
精确度
54.8050.34
迭代次数
67
最大最小距离聚类算法
精确度
88.9368.65
迭代次数
山莨菪碱
811
KDPCK-means 算法
精确度
96.6797.19
迭代次数
23
在这两种数据集中，KDPCK-means 算法的精确度显优于前两种算法，其迭代次数也明显少于前两种算法。通过以上实验数据可知，KDPCK-means 算法在一举解决了原始K-means 算法中问题的同时，在准确率、稳定性及运行效率上都得到了有效的提升。
参考文献：
[1]Al Hasib A,Cebrian J M,Natvig L.A vectorized k-means algo⁃rithm for compressed datasets:design and experimental analysis [J].The Journal of Supercomputing,2018,74(6):2705-2728.
[2]Douzas G,Bacao F,Last F.Improving imbalanced learning through a heuristic oversampling method based on k-means and SMOTE[J].Information Sciences,2018,465:1-20.
[3]García J,Crawford B,Soto R,et al.A k-means binarization framework applied to multidimensional knapsack problem[J].Applied Intelligence,2018,48(2):357-380.
[4]Manju V N,Lenin Fred A.AC coefficient and K-means cuckoo optimisation algorithm-based segmentation and compression of compound images[J].IET Image Processing,2018,12(2):218-225.
[5]陈思敏.基于位置指纹识别的WiFi 室内定位算法研究与实现[D].南京：南京邮电大学,2016.
[6]韩雅雯.kmeans 聚类算法的改进及其在信息检索系统中的应用[D].昆明：云南大学,2016.
[7]孔超.基于分布式平台的高校网络舆情分析系统研究与实现[D].成都：电子科技大学,2017.
[8]郭靖.K-means 聚类算法改进研究[D].北京：中国人民公安大学,2018.
【通联编辑：李雅琪】
（上接第179页）增加，并且GA 的加速比在任何时刻都是小于PS-ABC 的加速比的，并且PS-ABC 的
加速比的图像近似符合线性函数的图像。对于PS-ABC 而言，在逻辑的层面上，其可以把整个搜索空间划分为多个独立的子空间。同时，这些子空间分别对应着自己的搜索程序，并且执行者自己的搜索工作，接着，雇佣蜂共享大量的信息资源。GA 的机制比较适合集中处理，而PS-ABC 可以进行并行处理，从这些特点就可以看出来，PS-ABC 的测试性能要比GA 的性能好得多。此外，PS-ABC 的工作性能将会在处理大数据的时候充分地体现出来。
4结语
PS-ABC 可以减少系统的能源损耗以及提高服务性能的稳
定程度，除此之外，PS-ABC 还能够确保虚拟机动态迁移的性能良好。最终，各项结果都证明了PS-ABC 有能力配合虚拟机的动态迁移，从而提高大数据的分析处理水平。
参考文献：
[1]姚金玲，李莉.浅谈大数据背景下虚拟化与云计算的优势及应用[J].电脑知识与技术,2020,16(21):44-45.
[2]江璜.基于VMware vSphere 的虚拟化资源池应用研究[J].软件工程,2020,23(3):32-34.
[3]甘云志.虚拟化技术在新一代云计算数据中心的应用研究[J].数字技术与应用,2020,38(1):70,72.
【通联编辑：光文玲】
184
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议