基于核函数动态分配聚类中心的DGK-Kmeans算法
来源:用户上传
作者:
摘 要：Kmeans算法存在两个主要缺陷，导致聚类结果准确率较低。为改善聚类效果，提出一种DGK-Kmeans算法。该算法选用核密度估计处理数据，得到备选聚类中心，依据平均类间相似度动态增加初始聚类中心个数，直至平均类间相似度大于前次计算值时，选取平均类内相似度最小时对应的聚类中心为初始聚类中心，进行Kmeans聚类计算。采用UCI标准数据集进行实验，证明改进后的DGK-Kmeans算法在聚类准确率和稳定性方面有很大提高。
关键词：Kmeans算法;高斯核函数;动态聚类中心
DOI：10. 11907/rjdk. 182140
中图分类号：TP312 文献标识码：A 文章编号：1672-7800（2019）002-0042-03
Abstract：There are two main defects in the Kmeans algorithm which lead to lower accuracy of clustering results.In order to improve the clustering effect， a DGK-Kmeans algorithm is proposed.The algorithm uses the kernel density estimation to process the data to obtain the candidate cluster center， and dynamically increases the number of initial cluster centers according to the average inter-class similarity until the average inter-class similarity is greater than the previous calculated value， and the average intra-class similarity is selected. The cluster center corresponding to the minimum degree is Kmeans clustering calculation for the initial cluster center.The experiment uses the UCI standard data set to verify that the improved DGK-Kmeans algorithm and greatly improves the accuracy and stability of clustering.
Key Words：Kmeans clustering;Gaussian kernel function;dynamic clustering center
0 引言
Kmeans算法是一種适用于大规模数据集[1]的简单聚类算法，但算法迭代次数受初始聚类中心和实际聚类中心偏差的影响很大，所以选择合适的初始聚类中心是很有必要的[2]。Kmeans算法有两个主要缺点：一是需要人工输入聚类K值;二是随机选择K个初始中心[3]。
为提高Kmeans算法的性能，许多学者从不同方面对算法进行改进[4]。ALSABTI[5]选择利用K-D树结构对Kmeans算法进行改进。赖玉霞等[6]根据聚类对象分布密度，从K个处于高密度区域的点中选取相互距离值最远的样本点作为初始聚类中心。王玲等[7]提出一种基于密度敏感的相似度度量方法。程艳云等[8]提出通过定义的平均类间最大相似度指标值确定最佳K值，进而动态分配聚类中心的聚类算法。韩凌波等[9]提出按照密度大小选择K个聚类中心的算法。马帅等[10]选择根据密度和参考点提高聚类算法，基本满足聚类以适应数据集分布的特征。袁方等[11]提出一种基于样本距离相似度及通过合适的权值初始化聚类的方法，对特定的数据集选择合适权值进行聚类，达到了良好的效果。周涓等[12]提出基于距离大小的算法，初始聚类中心选择的是相互之间距离最远的K个样本点。周世兵等[13]从样本几何结构的角度定义样本聚类距离和样本聚类离差距离，设计一种新的聚类有效指标，从而提出一种自动确定最佳聚类数量的方法。刘凤芹等[14]提出一种基于最大距离实现K值自动生成的算法。翟东海等[15]提出基于最大距离选取初始簇中心的算法。
以上研究通过密度、权值及距离对算法进行改进，但都存在聚类精度不高、时间复杂度高等情况。因此本文提出一种基于高斯核密度、动态确定初始聚类中心的DGK-Kmeans算法（Gaussian Kernel Kmeans Algorithm）。通过实验证明，本文算法在UCI数据集中的聚类精度高于传统K-means算法，并且在误差平方和方面也有很大优势。
1 高斯核密度估计
核密度估计方法对于数据分布特征的研究从数据样本集合本身出发，不需要利用数据分布的先验知识或对数据样本服从何种分布作出任何假设[16]。核函数的作用是在高维空间对输入的空间进行特征映射后，直接在高维数据空间进行数据处理。核函数映射是非线性变换的，可确保映射出各种不同的高维特征空间[17]。
使用高斯核函数作为核平滑函数的密度估计，是一种用来估计概率密度函数的非参数方法，假定[x1，x2，？，xn]为独立分布[F]的[n]个数据点，数据点服从的分布密度函数为[f]，函数定义为：
本文采用高斯核函数为核平滑函数，公式为：
[h]的取值公式为：
2 DGK-Kmeans算法
由于Kmeans算法聚类数需事先确定，且初始聚类中心的选取具有随机性，因此本文提出基于高斯核密度的动态确定初始聚类中心的算法（DGK-Kmeans算法）。 2.1 相关概念及公式定义
本文采用欧氏距离定义数据之间的距离度量。
定义1 类内距离表示类中每个点到其聚类中心之间距离的均值。
其中，[ci]为类[i]聚类中心。
定义2 类间距离表示某个聚类中心到另一类聚类中心的距离。
定义3 平均类内最大相似度（AMS）表示一个类与其它类存在相似度的大小，由最大相似度取均值得到。
AMS越小则聚类效果越好，所以当AMS取得最小值时聚类效果最好，此时可获取最佳聚类个数。
2.2 DGK-Kmeans算法
根据数据样本位置属性，首先进行核密度估计，从而得到一个高密度区域，然后将高密度区域通过空间分析（焦点统计，栅格计算等）提取在特定区域内密度值最高的点，得到一个极大密度点的集合，将该极大密度点集作为备选聚类中心，从备选点中选取距离最远的两个点作为初始聚类中心，进行初步聚类并计算平均类间最大相似度。当计算得到的平均类间最大相似度现值小于前次计算值时，则依据相对距离原则从备选点中动态选择下一个聚类中心; 否则，将当前聚类中心当作最佳初始聚类中心后进行Kmeans聚类。
DGK-Kmeans算法执行步骤如下所示。
输入：一个数据集中包含N个数据对象。AMS初始值、算法终止条件。
输出：K个簇、评价函数值、算法聚类时间。
（1）使用核密度估计算法计算每个数据点，再使用焦点统计得到一个极大密度点集作为备选初始聚类点集D。
（2）从D中选择密度最大的一个点作为第一个初始聚类中心，D中距其最远的点作为第二个聚类中心，将选出的两个聚类中心放入初始聚类中心集合I中，并且将其从集合D中删除。
（3）根据已选择的聚类中心将N个数据点进行迭代划分，然后计算此时AMS值。
（4）若步骤（3）得出的AMS值小于前次AMS值或者备选聚类中心集合D不为空，则转步骤（5）继续执行算法;否则，选择AMS处于最小值时的集合I，即从Kmeans聚类的初始聚类中心进入步骤（6）。
（5）从D中选择一个到已选初始聚类中心距离的各自乘积最大的样本点，添加至集合I，并将其从D中删除。转步骤（3）。
（6）进行Kmeans聚类。
3 实验部分
3.1 实验描述
为了验证DGK-Kmeans算法的有效性，本文采用UCI数据库的4组数据集作为测试数据集。UCI数据集是对机器学习和数据挖掘的相关算法进行测试的标准数据集[18]。从数据总量、类别数和数据维度等方面选择的4组数据集分别是Iris数据集、Wine数据集、Glass数据集和Yeast數据集，这样可以更好地检测改进算法的有效性。现今对算法聚类效果的评价标准有很多种，本文采用以下3种度量指标：准确率、误差平方和、时间性能[19-20]。
3.2 实验结果
本文利用DGK-Kmeans算法、传统K-means算法、文献[8]中的动态分配聚类中心的改进K均值算法、文献[9]中基于密度的K-means初始聚类中心选取算法，使用选取的4组测试数据集进行对比实验。为尽量避免传统算法容易陷入局部最优的缺陷，聚类结果取10次实验数据的平均值。表1是4种聚类算法在4组数据集中聚类准确率比较结果。表2是4种不同聚类算法误差平方和的比较结果。
由表1可以看出DGK-Kmeans算法在Iris数据集上的准确率比文献[8]中的算法准确率低，在Wine和Glass数据集上，DGK-Kmeans算法准确率略高于其它3个算法，从Yeast数据集来看，DGK-Kmeans算法准确率远远高于其它3个算法。
由表2可以看出，与传统算法、文献[8]算法和文献[9]算法相比，本文DGK-Kmeans算法误差平方和有所降低。
图1为4种聚类算法使用4个标准数据集时的聚类时间折线变化。
由图1可以看出，传统Kmeans算法和文献[8]的算法在数据量小时，运行时间较短，但是当数据量增大时，运行时间呈指数增长。文献[9]的算法及本文DGK-Kmeans算法在Iris、Wine和Glass数据集运行时间高于其它两个算法，但是在数据量大的Yeast数据集中，运行时聚类时间并不像前两个算法那样呈指数增长。在数据总量增大的情况下与其它3个算法相比，本文DGK-Kmeans算法运行时间增长最为缓慢，在Yeast数据集下的聚类时间最短。所以在数据总量增大时，DGK-Kmeans运行时间具有很大优势。
3.3 实验分析
结合上面3种实验结果可以看出，与其它3个算法相比，虽然DGK-Kmeans在数据量小、聚类数小及数据维度低时，聚类准确率没有明显改善，而且在Iris数据集中低于文献[8]的算法，但是在数据量大时聚类准确率改善很明显，在误差平方和方面也有所改善。在运行时间方面，虽然DGK-Kmeans算法在数据量小的情况下比传统Kmeans算法和动态分配聚类中心的算法所需时间多，但是在数据量大的情况下其聚类时间优于其它3个算法，而且DGK-Kmeans算法聚类结果十分稳定。因此DGK-Kmeans算法在准确率、误差平方和及运行时间等方面有很大提高。
4 结语
本文提出的DGK-Kmeans算法使用核密度估计对初始聚类中心进行选取，所以经过本文算法选取得到的初始聚类中心保持不变，故该算法聚类结果较稳定。DGK-Kmeans算法可以自动获取K值，不需要人工输入，在准确率、误差平方和及运行时间方面较其它算法都有很大改进，在数据量大的情况下，大幅缩短了运行时间。但是在数据量小的情况下，本文算法运行时间较其它算法略长，所以在数据量小的情况下如何降低时间复杂度，是下一步需要解决的问题。 参考文献：
[1] 戴涛. 聚类分析算法研究[D]. 北京：清华大学， 2005.
[2] 柯良文， 王靖. 基于用户相似度迁移的协同过滤推荐算法[J]. 微型机与应用， 2014（14）：71-74.
[3] 倪志伟. 动态数据挖掘[M]. 北京：科学出版社， 2010.
[4] 莫锦萍，陈琴，马琳，等. 一种新的K-Means蚁群聚类算法[J]. 广西科学院学报，2008，24（4）：284-286
[5] ALSABTI K，RANKA S，SINGH V. An efficient K-means clustering algorithm[C]. Proceedings of IPPS/SPDP Workshop on High Performance Data Mining， 1997.
[6] 赖玉霞， 刘建平. K-means算法的初始聚类中心的优化[J]. 计算机工程与应用， 2008， 44（10）：147-149.
[7] 王玲， 薄列峰， 焦李成. 密度敏感的谱聚类[J]. 电子学报，2007， 35（8）：1577-1581.
[8] 程艳云，周鹏. 动态分配聚类中心的改进K均值聚类算法[J]. 计算机技术与发展，2017， 27（2）：33-36.
[9] 韩凌波，王强，蒋正锋，等. 一种改进的K-means初始聚类中心选取算法[J]. 计算机工程与应用， 2010， 46（17）：150-152.
[10] 马帅，王腾蛟，唐世渭，等. 一种基于参考点和密度的快速聚类算法[J]. 软件学报，2003， 14（6）：1089-1095.
[11] 袁方，孟增辉，于戈. 对k-means聚类算法的改进[J]. 计算机工程与应用， 2004， 40（36）：177-178.
[12] 周涓， 熊忠阳，张玉芳，等. 基于最大最小距离法的多中心聚类算法[J]. 计算机应用，2006，26（6）：1425-1427.
[13] 周世兵，徐振源，唐旭清. K-means算法最佳聚类数确定方法[J]. 计算机应用，2010，30（8）：1995-1998.
[14] 刘凤芹. K-means聚类算法改进研究[D]. 济南：山东师范大学， 2013.
[15] 翟东海，鱼江，高飞，等. 最大距离法选取初始簇中心的K-means文本聚类算法的研究[J]. 计算机应用研究，2014，31（3）：713-715.
[16] 熊开玲， 彭俊杰， 杨晓飞，等. 基于核密度估计的K-means聚类优化[J]. 计算机技术与发展， 2017， 27（2）：1-5.
[17] 赵明明， 张桂芸， 潘冬宁，等. 基于高斯核函数的K-means聚类在分布式下的優化[J]. 软件导刊， 2018，17（4）：64-66.
[18] 毛国君， 段立娟， 王实. 数据挖掘原理与算法[M].北京：清华大学出版社，2016.
[19] 周炜奔， 石跃祥. 基于密度的K-means聚类中心选取的优化算法[J]. 计算机应用研究， 2012， 29（5）：1726-1728.
[20] 王晓燕. K-均值算法与自组织神经网络算法的改进研究及应用[D]. 太原：中北大学， 2017.
（责任编辑：江 艳）
转载注明来源:https://www.xzbu.com/8/view-14803820.htm
