1611-0483
自动确定聚类中心的密度峰值算法
王洋１，张桂珠2
WANG Yang 1 ,ZHANG Gui – zhu 2
江南大学物联网工程学院，江苏无锡 214122
School of Internet of Things Engineering, Jiangnan University, Wuxi 214122, China
Automatically determine the density of the cluster center of the peak algorithm
Abstract Density Peaks Clustering (DPC) is a density-based clustering algorithm, which has the advantage of not needing to specify clustering parameters and discovering non-spherical clusters. In this paper, an adaptive truncation method based on Gini index is proposed to solve the problem that the density peak algorithm can not effectively deal with each scene by calculating the cutoff distance dc, and the density peak algorithm manually selects the clustering center to get the actual clustering center. Distance dc and automatic clustering center method can effectively solve the traditional DPC algorithm can not handle the complex data set defects. The algorithm firstly cuts off the distance through Gini index, then calculates the cluster center weights of each point, and then uses the change of slope to find the critical point. This strategy effectively avoids the errors caused by manual selection of clustering centers by decision graph . Experiments show that the new algorithm not only can automatically determine the clustering center, but also has higher accuracy than the original algorithm.
.
Computer Engineering and Applications 计算机工程与应用1
Key words :density peak;clustering;cluster center point;Gini index
基金项目：江苏省自然科学基金(BK20140165)。
作者简介: 王洋（1990－),男,硕士研究生), 研究领域为数据挖掘,E-mail: wy3266039@163.com;张桂珠(1962－),女, 副教授，研究领域为计算机系统集成、云计算、数据挖掘。
摘 要 密度峰值聚类算法（Density Peaks Clustering，DPC），是一种基于密度的聚类算法，该算法具有不需要指定聚类参数，能够发现非球状簇等优点。针对密度峰值算法凭借经验计算截断距离无法有效的应对各个场景并且密度峰值算法人工选取聚类中心的方式难以准确获取实际聚类中心的缺陷，本文提出了一种基于基尼指数的自适应截断距离和自动获取聚类中心的方法，可以有效解决传统的DPC算法无法处理复杂数据集的缺点。该算法首先通过基尼指数自适应截断距离，然后计算各点的簇中心权值，再用斜率的变化找出临界点，这一策略有效避免了通过决策图人工选取聚类中心所带来的误差。实验表明，新算法不仅能够自动确定聚类中心，而且比原算法准确率更高。
关键词 密度峰值;聚类;簇中心点;基尼指数
文献标志码:A 中图分类号:TP18
1引言
聚类是把数据集划分成子集的过程，每一个子集是一个簇，满足簇中对象相似，但与其他簇中的对象不相似的条件。聚类分析是一种无监督的数据分析方法，是数据挖掘的重要研究方向之一[1]，已经广泛的应用于多个领域，包括图像模式识别，web搜索，生物学和安全等[2]。
目前已经有许多经典的聚类算法被提出，如基于划分方法的k-means、k-medoids等聚类算法，基于层次方法的BIRCH、Chameleon等聚类算法，基于密度方法的DBSCAN、OPTICS、DENCLUE等聚类算法，基于网格方法的CLIQUE等聚类算法，基于模型[3]的GMM等聚类方法。这些经典的聚类算法各有优缺点，如基于密度的DBSCAN算法相较与划分和层次方法有可以发现任意形状的簇类，并且不需要事先知道要形成的簇类的数量等优点。但DBSCAN算法具有不能很好反应高尺寸数据，不能很好的反应数据集变化的密度，对输入参数敏感，时间开销较大等问题。针对上述DBCAN问题，许多学者提出了不同的改进方法[4]~[7]。文献[4]和文献[5]分别通过贪心算法、网格与密度聚类算法间的等效规则自适应的寻找Eps（半径参数），一定程度上的解决了DBSCAN算法参数选择困难的缺陷，但对于输入参数MinPts（邻域密度阈值）依然采用经验方法选取，没有真正的实现自适应确定阈值。文献[6]提出了一种基于高斯分布的自适应DBSCAN算法，有效解决了传统DBSCAN算法选择参数困难和对于密度变化较大的的数据集聚类效果不明显的缺陷，但是该算法时间开销较大。文献[7]提出了基于网格单元的DBSCAN算法，该算法优化了传统DBSCAN算法中大量不必要的距离计算，提高了算法运行的效率，但是对于多维数据不能有效的处理。
2014年Alex Rodriguez等人在《Science》提出了一种基于密度的新的聚类算法，密度峰值聚类[8]（Density Peaks Clustering，DPC）算法。该算法提出一种新的选取聚类中心的方法。作者认为聚类中心具有本身局部密度大，与其他密度更大的点之间的相对距离更大的特点。基于上述聚类中心的特征，DPC算法计算点的局部密度和相对距离，画出决策图（以局部密度为X轴，以相对距离为Y轴的组成的图像），根据决策图人工选取聚类中心点，再对非聚类中心点进行合并，最终达到聚类的目的。
DPC算法原理简单效率较高，但须要凭借经验选取截断距离并且须要人工选取聚类中心。对一些较为复杂的数据集，决策图上点的分布也较复杂，人工很难准确的选取正确的聚类中心。针对DPC算法不能自适应截断距离和不能自动选取聚类中心的缺陷，本文提出了一种利用基尼指数自适应距离，利用斜率差的变化自动获取聚类中心的密度峰值算法（Automatically Density Peaks Clustering，ADPC）,ADPC算法能够根据决策图自动的选取聚类中心，并且具有更好的聚类效果和更高准确率。
2密度峰值聚类算法原理及其缺陷
2.1密度峰值算法思想
聚类中心具有以下两个特征: 一是数据点本身的局部密度大，即被密度小于它的邻居包围；二是局部密度大的点与其他局部密度大的点相对距离较远。DPC算法分别用和来刻画局部密度和相对距离这两个特征，选择和相对大的点作为聚类中心，然后归并其他非聚类中心点，剔除噪声点，从而实现聚类。
2.2密度峰值算法原理
对于数据点，其局部密度有两种计算方式分别为:
Cut-off kernel：
(1)
其中表示和的距离，为截断距离，函数定义如下：
(2)
其中截断距离。
Gaussian kernel：
(3)
由公式(1)和(3)可知，Cut-off kernel为离散值的计算方法，Gaussian kernel为连续值的计算方法，因此后者产生的冲突(即不同的数据点具有相同的局部密度)概率更小。
对于数据点，相对距离可定义为：
(4)
由公式(4)可知，当具有最大局部密度时，表示数据集中与距离最大的数据点与之间的距离。否则，表示在所有局部密度大于的数据点中，与距离最小的那个(或那些)数据点到之间的距离。
对于数据集中的每一个数据点，计算局部密度和相对距离。将数据集中的每个点以二元对（，）在平面上画出（以为横轴，为纵轴），称之为决策图。决策图是DPC算法选取聚类中心的关键。在决策图中选择相对右上区域的点作为聚类中心，这些点的和值相对较大，满足2.1节中描述的聚类中心的两个特征。
2.3密度峰值算法的缺陷
密度峰值算法有两方面的缺陷。一方面，密度峰值算法在选取截断距离时是基于若干数据集的经验值，文献[8]中提出，选取一个，使得每个数据点的平均邻居个数约为数据点总数的2%。截断距离的选取决定着DPC算法聚类效果的好坏，如果取得太大，极端情况下是取，这使得每个数据点的局部密度都一样，则所有数据点都归并到一个类之中。如果的取值过小，极端情况，则每个数据点都会成为一个单独的类。因此传统的DPC算法选取的方法并不适用于各个场景。实际上在一些具体问题中合理在数量级上可能存在很大差异，这导致DPC算法不能有效的处理结构复杂的数据集。
另一方面，DPC算法需要人工选取局部密度和相对距离较大的点作为聚类中心。对于决策图复杂的数据集，人工难以选择正确的聚类中心，并且DPC算法对非聚类中心点的一步归并策略也会造成连锁反应，一旦一个数据点分配错误可能会造成一系列的样本数据集类簇错误。
3自适应距离自动获取聚类中心的密度峰值算法（ADPC）
3.1基于基尼不纯度的自适应截断距离
在DPC算法中，截断距离的选取是计算局部密度的关键。局部密度的大小将直接影响最终的聚类效果。传统的密度峰值算法仅仅考虑每个数据点的局部密度，没有考虑整个数据集的分布情况。导致DPC算法不能够有效的应对复杂的数据集，为了改进DPC算法的这一缺陷，必须找到一种描述数据集整体分布情况的指标。文献[9]提出了一种用熵优化点势能的方法来找到最优截断距离。本文提出利用基尼不纯度求出最优截断距离，对比传统的DPC算法具有更好的聚类效果。
在文献[10]中提出了一种用高斯函数计算点势能的方法如公式(5)所示，在数据集中，势能较大的点位于密集区域，势能较小的点位稀疏区域，这说明数据域的势能和数据中的点局部密度具有类似的效果。因此，利用每个点的势能来估算整体数据集的势能，以此作为衡量数据集整体分布情况的指标。对于数据集，每一个点的势能计算公式为:
（5）
在数据域中，如果数据的势能分布较均匀，数据分布的不确定性较大，数据的不纯度较大。如果数据的势能分布不均匀，数据分布的不确定性较小，数据的不纯度较小。数据的不纯度可以由基尼指数表示，数据域中基尼指数的计算公式为：
（6）
其中表示数据域总的势能大小，表示每一点的势能。对比公式（5）和公式(3),发现计算点势能的方法与DPC算法中计算局部密度的方法相似，为了取得最优的截断距离，等价于取得最优的(称之为影响因子)。联合公式(5)和公式(6),可得当从0逐渐增大，基尼指数随着影响因子的变化而变化。当基尼指数值取最小值时,反映了数据的不纯度最小，不确定性最小，数据势能分布不均匀，数据的势能差别最大，更易于聚类，这是理想的结果。因此基尼指数值最小时取得最优影响因子的值。以最优的值作为截断距离的值，从而达到自适应截断距离的效果。
3.2自动选择聚类中心
定义1 为了综合考虑和的影响，定义,值越大，越有可能是聚类中心。对于进行降序排列，对排序后的点进行标号，用i来表示标号，然后绘制关于的函数图像，称之为“的排序图”。
定义2 临界点是的排序图中与前后整体变化最大的点。本文采用斜率k来表示变化程度，点满足条件：
（7)
（8）
（9）
其中表示第个点和第个点之间线段的斜率，表示在排序图中相邻两点之间斜率差的总和，表示在排序图中相邻点的斜率差的平均值，当是大于等于斜率差的平均值的点中，序号最大的点时，是临界点。
定义3 疑似聚类中心点的定义为：
（10）
疑似聚类中心包涵了实际的聚类中心，但也包含了其他非聚类中心点。如图一所示，图一是Aggreration数据集由于将疑似的聚类中心作为实际聚类中心，导致右下角本来属于一类的数据变成了两类。因此在用疑似聚类中心点得到聚类结果后，还需要判断是否一个簇被错误的分为多个子簇。
在DPC算法中,实际的聚类中心往往分布在相对高密度区域内,并且实际聚类中心间的相对距离较远。因此在一个高密度区域中，如果存在多个疑似聚类中心，则这些疑似聚类中心通常会比较接近。基于密度峰值算法的这种特点,把查找到属于某个簇的第一个疑似聚类中心（值最大），作为该簇的唯一实际聚类中心。进行聚类，依次判断剩余的点与第一个点的最短距离和截断距离的大小，如果小于，侧将该点作为错选的聚类中心点，当作簇成员处理，如果大于，侧该点作为其他簇的聚类中心。最终可以剔除多余的聚类中心，从而准确的选择出实际的聚类中心。
图一Aggreration错误的聚类结果
4实验结果与分析
为了验证ADPC算法的效果，分别在人工数据集和UCI数据集上进行测试，对比传统的密度峰值算法。实验环境为 Windows10 64位操作系统,Intel Core i7 @2.7GHz CPU,16G内存，使用MATLAB2014a进行仿真实验。
4.1人工数据集
仿真实验用到的人工数据集共有三个，如表一所示。使用表一的数据，分别运行DPC算法和ADPC算法，实验结果如图二至图九所示。
数据集
样本数
维数
类数
L3
312
2
3
R15
600
2
15
D31
3100
2
31
表一人工数据集
人工数据集L3的样本数、类别数最少，理论上聚类难度最低。但由于其数据集整体分布较为特殊（线性环状分布）增加了聚类难度。如图二所示，用传统的DPC算法并不能得到正确的聚类结果。利用本文提出的ADPC算法对人工数据集L3进行聚类，得到正确的聚类结果如图三所示。造成两种算法聚类结果差异的原因是该数据集分布特殊，DPC算法选取的截断距离不当，一步归并的策略造成连锁反应，没有考虑到数据集整体分布情况。
图二 DPC算法在L3上错误的聚类结果
图三 ADPC算法在L3上正确的聚类结果
人工数据集R15类簇间的间隔较大，有利于聚类，但是相对与L3，样本数量较大，类别数较多，增加了聚类难度。图四是DPC算法对人工数据集R15聚类后所得到的决策图，图五是DPC算法人工选取聚类中心之后所得到的聚类结果，如图五所示，中心部分的8个簇应该是属于不同的类，但由于DPC人工选取聚类中心有主观性，导致了错误的聚类结果。
图四DPC算法在R15上的决策图
图五DPC算法在R15上错误的聚类结果
图六是利用本文提出优化截断距离自动选取聚类中心的ADPC算法对人工数据集R15的聚类结果，如图六所示，ADPC算法准确的识别出了数据集R15的类别数，排除人工选取聚类中心的主观因素，得到正确的聚类结果。
图六ADPC算法在R15上正确的聚类结果
对于人工数据集D31,相对于L3和R15样本数和类别数最多，数据集整体分布最复杂，聚类难度最大。用DPC算法对其进行聚类时，生成的决策图比较复杂，人工选取聚类中心可能会导致错误的聚类结果。如图七所示，图七是DPC算法对数据集D31的决策图，人工选取聚类中心的十分困难，得到的错误结果如图八所示。
图七DPC算法在D31的决策图
图八ADPC算法在D31上错误的聚类结果
将ADPC算法用于人工数据集D31,得到图九所示的聚类结果，可以看到，ADPC算法准确的判断出数据集D31的31个类。
图九ADPC算法在D31上正确的聚类结果
DPC算法和ADPC算法在数据集D31上造成了不同的聚类结果。分析有三方面原因，其一：数据集D31较复杂（样本数较多），生成的决策图较复杂，如图七所示，人工选取难以准确选取聚类中心，因此导致图八错误的聚类结果。而ADPC算法根据斜率差的变化自动选取潜在聚类中心避免了对于复杂数据集人工难以准确选取聚类中心的问题。其二：DPC算法凭经验选取截断距离难以适应复杂数据集，对于数据集D31，不恰当的截断距离会导致决策图中聚类中心点分布不明显。而ADPC算法利用基尼指数自适应截断距离不仅仅考虑了点的局部密度，而且考虑了数据集整体的分布情况，计算出的截断距离更合理，合适的截断距离更有利于聚类。这是ADPC算法的另一个优势。其三：DPC算法一旦选取聚类中心错误，就会导致聚类结果的错误。如图七所示，决策图中人工选取的错误的聚类中心点，直接导致图八聚类结果错误。而ADPC算法剔除潜在聚类中心的方法，能有效避免DPC算法一步归并产生错误的连锁反应。因此对于数据集D31,ADPC算法有更好的聚类效果。
4.2 UCI数据集
实验采用的数据集是UCI机器学习数据库的Iris、Wine、Aggreration。详细信息如表二所示。
表二UCI数据集
数据集
样本数
维数
类数
Iris
150
4
3
Wine
178
13
3
Aggreration
788
2
7
将DPC算法和ADPC算法应用于上述数据集，并且比较聚类结果。本文采用Precision和F-measure作为聚类结果评判标准。数据所属的类可看作是集合中等待查询的项；由算法产生的簇可看作是集合中检索到的项；是簇中类i的数量。类和簇的精确率和召回率分别是：
精确率: (9)
召回率: (10)
(11)
由公式(11)可知，F-measure是精确率和召回率的加权调和平均值，其中是参数。
为了考察ADPC算法与传统的DPC算法的聚类效果，本文采用上述3类UCI数据集的进行测试，实验统计了准确率Precision和F-measure，实验结果如图十图十一所示。
图十F-measure
图十一准确率
ADPC算法在数据集Iris、Wine、Aggreration上的准确率与DPC算法有明显的提升。在F-measure方面，对于数据集Iris、Wine,APDC算法提升效果明显，对于数据集Aggreration，ADPC算法相对于DPC算法略有提升。通过分析可知，ADPC算法克服了传统DPC算法人工选取聚类中心的主观性和不确定性，同时改善了DPC算法选取截断距离无法应用于多个复杂场景这一缺陷，因此ADPC算法在大部分数据集中效果提升明显。
5结语
针对于传统的密度峰值算法(DPC算法)选取截断距离难以适应复杂的数据集，并且DPC算法人工难以准确的选取聚类中心的缺陷，本文提出了一种自动选择聚类中心的ADPC算法，该算法不仅保留了DPC算法简单高效的特点，克服了DPC算法的缺点。在人工数据集和UCI数据集的上的实验结果证明，ADPC算法具有更好的适应性，对于复杂的数据集，能够更好的计算出合适的截断距离和聚类中心点，并且对比DPC算法具有更高的准确率。
参考文献
Datta Souptik, Giannella Chris, Kargupta Hillol, et al. Approximate Distributed K-Means Clustering over a Peer-to-Peer Network[J]. IEEE Transactions on Knowledge and Data Engineering, 2009, 21(10): 1372-1388.
Zhou Tao, Lu Hui-ling, Clustering algorithm research advances on data mining[J]. Computer Engineering and Applications. 2012, 48(12): 100-111.
WANG Jun,WANG Shi-tong,DENG Zhao-hong, et al.Survey on challenges in clustering analysis research[J].Controland Decision.2012,27(3):321-328
冯振华,钱雪忠,赵娜娜. Greedy DBSCAN:一种针对多密度聚类的DBSCAN改进算法[J]. 计算机应用研究,2016,09:2693-2696+2700.
谭颖，胡瑞飞，殷国富. 多密度阈值的DBSCAN改进算法[J]. 计算机应用, 2008, 28(3): 745-748
陈刚，刘秉权，吴岩一种基于高斯分布的自适应DBSCAN算法[J]微电子学与计算机，2013,30 (3)27一0.
刘淑芬,孟冬雪,王晓燕. 基于网格单元的DBSCAN算法[J]. 吉林大学学报(工学版),2014,04:1135-1139.
Rodriguez, Alex, Alessandro Laio, Clustering by fast search and find of density peaks[J]. Science. 2014, 344(6191) : 1492-1496.
Wang S, Wang D, Li C, et al. Comment on “Clustering by fast search and find of density peaks”[J]. Computer Science, 2015.
Shuliang Wang, Wenyan Gan, Deyi Li, Deren Li, Data Field for Hierarchical Clustering, International Journal of Data Warehousing and Mining, 7(4), 43-63
蒋礼青,张明新,郑金龙,戴娇,尚赵伟. 快速搜索与发现密度峰值聚类算法的优化研究[J]. 计算机应用研究,2016,11:3251-3254.
谢娟英,鲁肖肖,屈亚楠,高红超. 粒计算优化初始聚类中心的K-medoids聚类算法[J]. 计算机科学与探索,2015,05:611-620
刘颖莹,刘培玉,王智昊,李情情,朱振方. 一种基于密度峰值发现的文本聚类算法[J]. 山东大学学报(理学版),2016,01:65-70.
马春来,单洪,马涛. 一种基于簇中心点自动选择策略的密度峰值聚类算法[J]. 计算机科学,2016,07:255-258+280.
谢娟英,高红超,谢维信. K近邻优化的密度峰值快速搜索聚类算法[J]. 中国科学:信息科学,2016,02:258-280.
1611-0483
修改说明;
1. 建议：作者已经按照6条审稿意见对论文进行了认真修改，建议再做以下修改： 建议作者结合改进方法原理，对ADPC算法用于人工数据集D31得到的结果进行分析，尤其是聚类结果原因分析。
1.
修改：已经增加 ADPC算法用于人工数据集D31得到的聚类结果原因分析。具体为“DPC算法和ADPC算法在数据集D31上造成了不同的聚类结果。分析有三方面原因，其一：数据集D31较复杂（样本数较多），生成的决策图较复杂，如图七所示，人工选取难以准确选取聚类中心，因此导致图八错误的聚类结果。而ADPC算法根据斜率差的变化自动选取潜在聚类中心避免了对于复杂数据集人工难以准确选取聚类中心的问题。其二：DPC算法凭经验选取截断距离难以适应复杂数据集，对于数据集D31，不恰当的截断距离会导致决策图中聚类中心点分布不明显。而ADPC算法利用基尼指数自适应截断距离不仅仅考虑了点的局部密度，而且考虑了数据集整体的分布情况，计算出的截断距离更合理，合适的截断距离更有利于聚类。这是ADPC算法的另一个优势。其三：DPC算法一旦选取聚类中心错误，就会导致聚类结果的错误。如图七所示，决策图中人工选取的错误的聚类中心点，直接导致图八聚类结果错误。而ADPC算法剔除潜在聚类中心的方法，能有效避免DPC算法一步归并产生错误的连锁反应。因此对于数据集D31,ADPC算法有更好的聚类效果。”
备注；文章已按照 论文模板格式 修改，并且斟酌了部分表述。谢谢各位专家的指导。
G
G
s
i
r
c
d
,
iiiS
iI
grd
=Î
i
g
1
{}
N
i
g
=
g
i
g
p
g
]
~
1
[
p
i
d
[
]
g
n
p
~
p
{
}
1
max|,1,,2
ii
piin
kk
b
+
=-³=-
L
(
)
=/2
jn
ba
–
(
)
2
1
1
n
jj
j
j
kk
a
–
+
=
=-
å
i
k
i
1
i
+
(
)
j
a
g
i
r
b
g
i
b
{
}
|,1,,
qqp
spqqp
gg
=³=
L
-20-15-10-505101520
-15
-10
-5
0
5
10
15
20
X
Y
i
g
c
d
c
d
c
d
i
d
-15-10-505101520
-15
-10
-5
0
5
10
15
20
X
Y
-15-10-505101520
-15
-10
-5
0
5
10
15
20
X
Y
100200300400500600700800
0
1
2
3
4
5
6
7
8
9
Decision Graph
-8-6-4-202468
-8
-6
-4
-2
0
2
4
6
8
X
Y
-8-6-4-202468
-8
-6
-4
-2
0
2
4
6
8
X
Y
i
i
N
k
C
k
N
ik
N
i
x
Pr(,)/
kikk
ecisioniCNN
=
Recall(,)/
kiki
iCNN
=
2
2
(1)Pr(,)*Recall(,)
(,)
Pr(,)Recall(,)
kk
k
kk
ecisioniCiC
FmeasureiC
ecisioniCiC
a
a
+
-=
+
a
IrisWineAggreration
0.5
0.55
0.6
0.65
0.7
0.75
0.8
0.85
0.9
0.95
1
F-measure
DPC
ADPC
IrisWineAggreration
0.5
0.55
0.6
0.65
0.7
0.75
0.8
0.85
0.9
0.95
1
准确率
DPC
ADPC
c
d
c
d
c
d
i
r
(
)
iijc
j
dd
rc
=-
å
(
)
,
ijij
ddistxx
=
i
x
j
x
c
d
(
)
x
c
(
)
1,0;
0,0,
x
x
x
c
<
ì
ï
=
í
³
ï
î
0
c
d
>
2
ij
c
d
d
i
j
e
r
æö
–
ç÷
ç÷
èø
=
å
i
d
{
}
{
}
min,;
max,,
i
S
S
i
ijS
jI
i
i
ijS
jI
dI
dI
f
d
f
Î
Î
ì
¹
ï
=
í
=
ï
î
i
r
c
d
c
d
max
c
dd
>
r
min
c
dd
<
c
d
c
d
i
r
{
}
12
,,,
n
xxx
L
(
)
2
1
i
xx
n
i
xe
s
d
æ-ö
-
ç÷
èø
=
æö
ç÷
=
ç÷
èø
å
2
1
1
n
i
i
G
Z
d
=
æö
=-
ç÷
èø
å
1
n
i
i
Z
d
=
=
å
i
d
c
d
s