1. 引言
当前世界正处在一个科学技术飞速发展,信息量指数型增加的状态,与之而来的是繁多且复杂的数据,这些数据包括人们的日常活动信息,比如文字数据,视频数据,语音数据等,如何处理分析这些数据成为当下研究的热点。聚类作为数据挖掘的核心技术之一,其目的是将待处理的数据按照相似性规则聚成几组各异的簇,这些簇的特征是簇内相似度高但簇间相似度低。根据原理的不同可将聚类分为五类 [1] [2] [3] [4] [5]:划分聚类(division-based clustering)、层次聚类(hierarchical clustering)、网格聚类(grid-based clustering)、密度聚类(density-based clustering)和模型聚类(model-based clustering)。
密度峰值聚类算法于2014年被意大利学者Rodriguez等人 [6] 首次提出,相比于其他聚类算法,该算法原理简单,参数唯一且聚类高效,这些优势让DPC算法成功应用到各个领域,包括人工智能、模式识别、图像处理 [7] 等多个方面。自此算法提出至今,诸多国内外学者对其进行了改进:蒋礼青等人 [8] 针对截断参数人为确定,一个簇中存在多密度峰值数据等问题,利用近邻距离曲线的变化和类合并优化的方法,实现了参数自适应确定和多密度峰值数据的正确聚类。Jian等人 [9] 利用K近邻思想重新定义了局部密度的计算,并分析了DPC算法中核密度估计方法对聚类结果的影响,通过使用距离归一化原理设计了新的聚类中心选择标准。这些改进算法在一定程度上解决了DPC算法的部分问题。
麻雀搜索算法是2020年由Xue等人 [10] 提出的一种新型群智能优化算法,此算法被提出的契机来自于麻雀群体的觅食与反捕食行为。SSA的数学模型可看作是发现者–加入者模型,并且加入了预警机制。此算法不仅具备良好的鲁棒性和收敛速度,而且有着较强的全局探索能力和局部开发能力,这使得麻雀群体会自发向全局最优值移动,有效避免了早熟现象。
本文对于人工选取截断距离参数主观性强这一问题,考虑将密度峰值聚类算法与麻雀搜索算法相结合,提出基于麻雀搜索算法改进的密度峰值聚类算法:首先更改数据间距离度量方式,用标准欧氏距离代替传统的欧氏距离来计算数据样本间的相似性,其次选择经过变形的聚类评价指标作为SSA算法的适应度函数对DPC算法中的截断距离参数进行迭代寻优,最后对所提算法进行仿真实验,分别选取人工数据集和真实数据集对其进行算法有效性评价。第二部分对DPC算法和SSA算法进行简要介绍,第三部分详细阐述所提出的SSA-DPC算法,第四部分对新算法进行实验分析,第五部分为总结。
2. 相关算法简述
2.1. 密度峰值聚类算法(DPC)
密度峰值聚类算法建立在两个基本假设上:1) 类簇中心点的局部密度相较于周围点的密度要高;2)类簇中心点与比其密度更高的点之间的距离相对较远。
假设有数据集合
,
是数据点
与
之间的欧氏距离。定义局部密度
为:
, (1)
其中,
是截断距离,需要人为指定,一般选取整个数据集的1%~2%作为截断阈值,
是指示函数。定义相对距离
为:
, (2)
当数据点
的局部密度达到最大时,相对距离变为:
。
局部密度和相对距离确定完成后,通过绘制决策图选取聚类中心,一般选择决策图右上方的点,这些点既有较高的局部密度,也有较大的相对距离。最后采用一步分配策略进行非聚类中心点的分配:若数据点
不是中心点,则将其归入密度比
大且距离
最近的数据点
所在的类,该过程只执行一次,不用进行迭代更新 [11]。
2.2. 麻雀搜索算法(SSA)
根据麻雀种群的生物特性,将其行为理想化,制定相应规则,建立数学模型,从而得到新颖且有潜力的算法——麻雀搜索算法。SSA将麻雀种群分为两大类:发现者和加入者,发现者拥有较高的能量,它们的职责是搜索食物并提供相应的觅食区域和方向,这类群体占总种群的20%;加入者相对来说能量较少,它们利用发现者来获取食物,占总种群的80%。当麻雀意识到危险时,会即刻表现出反捕食状态 [12]。
假设麻雀种群为:
,n为麻雀总数,d为变量维数,麻雀个体对应的适应度值为:
。在SSA中,有较高适应度值的发现者会优先获得食物,故发现者的位置更新公式为:
, (3)
其中,
表示第i个麻雀在第j维的位置,t为当前迭代次数,
是随机数,
是预警值,
是安全阈值,Q是服从正态分布的随机数,L是元素全部为1的
矩阵。当
时,说明觅食环境周围是安全的,发现者可以大范围搜索食物;当
时,说明麻雀感应到了捕食者,需要撤往安全地带 [12]。
对加入者来说,它们会优先选择和发现者争夺食物资源,公式如下:
, (4)
其中,
为当前全局最差位置,
为发现者所占最佳位置,A中每个元素被随机赋值为1或−1。当
时,表示第i个加入者的适应度值较低,因未获得食物而处于饥饿状态,所以将飞往其他可以觅食的地方;当
时,表示第i个加入者将在当前最优位置附近寻找食物 [12]。
为保证其整个觅食过程的安全性,选取麻雀种群的10%~20%作为可以感知危险的麻雀,其位置更新表达式为:
, (5)
其中,
为当前全局最优位置,
为控制参数的步长,是一个服从标准正态分布的随机数,
是调整移动方向的随机数,
是当前麻雀的适应度值,
与
分别表示当前全局最佳与最差适应度值,
为最小常数。当
时,表示麻雀处于种群边缘,易被捕食者袭击;当
时,表示麻雀处于种群中间且感知到了危险,为了免受攻击需要向其他麻雀靠近 [12]。
3. 基于麻雀搜索算法的密度峰值聚类(SSA-DPC)
本文主要从以下两个方面进行改进:首先更改数据间的距离度量函数来更新距离矩阵;其次,利用麻雀搜索算法较强的全局寻优能力对DPC算法中的截断距离dc进行优化。
3.1. 距离度量函数的改进
密度峰值聚类中,局部密度和相对距离的计算与所采用的距离度量方式有着密切联系,距离矩阵构造的好坏很大程度上影响着聚类的性能。传统DPC算法采用欧氏距离进行聚类,但在处理一些较为复杂的数据集,比如数据各维度的分量不一致时,欧氏距离不能准确地反映数据分布情况,不能很好地表现出数据间的特征。因此,考虑将数据间的距离度量方式改用标准欧氏距离来替代。
标准欧氏距离是对传统欧氏距离的缺点而做的一种改进方案,可将其看成一种加权欧氏距离。他利用数据样本的标准差,综合各维度的差异程度,使得各个维度都满足标准正态分布,这种处理方式更能体现数据间的分布情况,且能很好地反映数据间的特征,其计算公式为:
, (6)
其中,d为维度,sk为标准差。
3.2. 截断距离dc的优化
密度峰值聚类中有且只有一个参数——截断距离dc,但该参数的确定方式是人们根据经验来估计,主观性很强,因此利用麻雀搜索算法较强的全局寻优能力对参数进行自适应选取。
本文提出的SSA-DPC算法将聚类结果的标准互信息(Normalized Mutual Information, NMI) [13] 指标进行变形作为适应度值目标函数,即dc求解的收敛条件。NMI指标利用互信息来评价聚类质量,取值范围为
,其值越接近1,说明聚类结果越接近于真实结果。假设U为真实标签向量,V为预测标签向量,MI为互信息,H为信息熵,那么NMI指标的数学表达式为:
, (7)
取NMI指标的倒数作为SSA中的适应度值函数,表达式如下:
, (8)
在优化过程中,通过SSA算法进行多次迭代寻优,找出使DPC算法中NMI指标最大的dc作为当前数据集最优的dc,从而实现算法的聚类。
3.3. SSA-DPC算法描述
SSA-DPC算法将数据间的距离度量方式用标准欧氏距离来表示,把密度峰值聚类算法和麻雀搜索算法通过NMI指标函数有效地结合在一起,优化了截断参数dc。记采用标准欧氏距离改进后的DPC为DPC*。算法具体步骤如下:
输入:数据集
。
输出:聚类结果
,k为类簇数目。
步骤1. 计算数据点间的距离,构造距离矩阵,确定dc取值范围。
步骤2. 运行DPC算法,根据聚类结果得到NMI指标的值。
步骤3. 根据数据集大小设置种群大小为S,最大迭代次数为T。
步骤4. 初始化种群位置,得到初始dc值。
步骤5. 根据式(8)运行SSA算法,迭代更新dc的值。
步骤6. 判断算法是否满足终止条件,若是,则结束迭代转至下一步;若否,则继续迭代。
步骤7. 将最优的dc值代入DPC*算法,得到聚类结果,完成聚类。
4. 仿真实验及分析
4.1. 实验数据集
为了验证SSA-DPC算法的有效性,本文采用4个人工数据集和3个真实数据集对该算法进行验证,7个数据集的具体描述如表1所示:
4.2. 性能评估指标
本文采用调整互信息(Adjusted Mutual Information, AMI) [14]、调整兰德系数(Adjusted Rand Index, ARI) [15] 和FM指数(Fowlkes and Mallows Index, FMI) [16] 三个评价指标对算法进行性能评估,定义如下:
定义1 调整互信息(AMI) [14]:假设U为真实标签向量,V为预测标签向量,MI为互信息,E为期望,H为信息熵,那么AMI指标的数学表达式为:
, (9)
定义2 调整兰德系数(ARI) [15]:设a为同属于U与V的数据对个数;b为在U中属在同类,在V中属不同类的数据对个数;c为在U中属不同类,在V中属同类的数据对个数;d为在U与V中都属不同类的数据对个数 [11],则有:
, (10)
定义3 FM指数(FMI) [16]:FMI是平衡了精确度和召回率的调和平均值,表达式为:
, (11)
4.3. 实验结果及分析
使用SSA-DPC算法、DPC算法、DBSCAN算法以及K-Means算法对表1中的四个人工数据集Spiral、Jain、Flame以及Aggregation进行聚类,这四个数据集的总体分布情况各不相同,因而可以更清晰直观地反映出四种算法的聚类效果和性能。图1 为四种算法在Spiral数据集上的聚类效果图。
从图中可以看出,Spiral数据集是由三条螺旋线组成,DPC算法和K-Means算法的聚类效果不是很好,它们错误地将一个类簇的数据点划分到三个类簇,而SSA-DPC算法和DBSCAN算法可以正确地将数据聚集在一起,聚类效果很好。
图2为四种算法在Jain数据集上的聚类效果图。
从图中可以看出,Jain数据集由两个月牙型的数据簇组成,DPC算法、DBSCAN算法以及K-Means算法在此数据集上的表现效果很差,尤其是DBSCAN算法,未能将第二个数据簇的数据表现出来,只有SSA-DPC算法能够准确确定类簇的个数,同时聚类效果十分优秀。
图3为四种算法在Flame数据集上的聚类效果图。
从图中可以看出,Flame数据集由两个形状不同的数据簇组成,SSA-DPC算法、DPC算法以及DBSCAN算法的聚类效果都很好,只存在细微差别,而K-Means算法将火焰型的数据集用直线割裂成了两部分,错误地将一个类簇的数据点划分到两个类簇。
图4为四种算法在Aggregation数据集上的聚类效果图。
从图中可以明显看出,四种算法都未能精准地将七个类簇识别,但相对来说,SSA-DPC算法将数据集下方难以分辨的三个球形类簇很好地分离开来,聚类效果较好,其他三种算法要么错误的将不同类簇的数据聚集到了一起,要么不能准确识别类簇数目。
为了更好地对比四种算法的聚类效果,表2给出了各算法7个数据集上的聚类评价指标值:
对比表中数据指标值可以发现:SSA-DPC算法对七个种数据集进行聚类所得的AMI、ARI和FMI指标值均得到了更好的结果,聚类性能也有了很大的提升。在四个人工数据集中,SSA-DPC算法的三个
![](//html.hanspub.org/file/15-1251694x58_hanspub.png?20140114005507871)
Figure 1. The renderings of the four algorithms in the Spiral dataset
图1. 四种算法在Spiral数据集的效果图
![](//html.hanspub.org/file/15-1251694x59_hanspub.png?20140114005507871)
Figure 2. The renderings of the four algorithms in the Jain dataset
图2. 四种算法在Jain数据集的效果图
![](//html.hanspub.org/file/15-1251694x60_hanspub.png?20140114005507871)
Figure 3. The renderings of the four algorithms in the Flame dataset
图3. 四种算法在Flame数据集的效果图
![](//html.hanspub.org/file/15-1251694x61_hanspub.png?20140114005507871)
Figure 4. The effect of the four algorithms in the Aggregation dataset
图4. 四种算法在Aggregation数据集的效果图
![](Images/Table_Tmp.jpg)
Table 2. Experimental results of the four algorithms on 7 datasets
表2. 四种算法在7个数据集上的实验结果
指标值几乎都等于或者接近于1,这表示此算法在类似数据集中都有较好的聚类效果。在Iris和Seeds数据集中,SSA-DPC的聚类效果略差于K-Means算法,但仍高于DPC算法和DBSCAN算法。
5. 结语
为了更好地体现密度峰值聚类算法的数据分布,减弱手动确定截断距离的主观性,本文结合群智能优化算法中的麻雀搜索算法,提出一种基于麻雀搜索算法改进的密度峰值聚类算法。该算法用标准欧氏距离取代传统的欧式距离,更改数据间距离度量方式;将NMI指标作为适应度值目标函数,设定取值范围,对截断距离进行寻优。通过在人工数据集和真实数据集上的实验验证,可以得出结论:本文所提出的SSA-DPC算法可以有效反映数据分布,能自动确定截断参数,是一种有效的自适应聚类算法,并且对任意形状的类簇都有着较好的聚类效果。下一步的研究目标是对剩余点的分配策略进行改进,尝试将DPC算法应用于实际问题。
基金项目
国家自然科学基金(11461039)。
NOTES
*通讯作者。