基于麻雀搜索算法改进的密度峰值聚类算法

Improved Density Peak Clustering Algorithm Based on Sparrow Search Algorithm

摘要: 针对密度峰值聚类算法(Density Peaks Clustering Algorithm, DPC)用传统距离度量方式不能很好地反映数据分布，人为选取截断距离参数主观性较强等问题，设计了一种基于麻雀搜索算法改进的密度峰值聚类算法(Improved Density Peak Clustering Algorithm Based on Sparrow Search Algorithm, SSA-DPC)。该算法从两个方面进行改进：改变数据间的距离度量方式，用标准欧氏距离替代原算法中的欧氏距离；利用麻雀搜索算法(Sparrow Search Algorithm, SSA)较强的全局寻优能力，搜寻最佳截断距离值。通过对7个数据集进行仿真测试，证明SSA-DPC算法在3个评价指标上均优于其他聚类算法，提升了聚类性能，说明了算法的有效性。

Abstract: Aiming at the problems that density peaks clustering algorithm (DPC) cannot well reflect the data distribution with traditional distance measurement, and the artificial selection of truncation dis-tance parameters is highly subjective, an improved density peak based on sparrow search algo-rithm was designed—Clustering algorithm (Improved Density Peak Clustering Algorithm Based on Sparrow Search Algorithm, SSA-DPC). The algorithm is improved from two aspects: change the distance measurement method between data, and replace the Euclidean distance in the original algorithm with the standard Euclidean distance; using the strong global optimization ability of the Sparrow Search Algorithm (SSA), the best cutoff distance value was searched. Through the simula-tion test of 7 data sets, it is proved that the SSA-DPC algorithm is superior to other clustering algo-rithms in 3 evaluation indicators, and the clustering performance is improved, which shows the effectiveness of the algorithm.

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)类簇中心点与比其密度更高的点之间的距离相对较远。

假设有数据集合 $S=\left\{x_1,x_2,\cdots ,x_n\right\}$， $d_{ij}=dist\left(x_i,x_j\right)$ 是数据点 $x_i$ 与 $x_j$ 之间的欧氏距离。定义局部密度 ${\rho }_i$ 为：

$\begin{array}{l}{\rho }_i={\displaystyle \underset{j\ne i}{\sum }\chi \left(d_{ij}-d_c\right)}\\ \chi \left(x\right)=\{\begin{array}{c}1,x<0\\ 0,x\ge 0\end{array}\end{array}$, (1)

其中， $d_c$ 是截断距离，需要人为指定，一般选取整个数据集的1%~2%作为截断阈值， $\chi \left(x\right)$ 是指示函数。定义相对距离 ${\delta }_i$ 为：

${\delta }_i=\underset{j:{\rho }_j>{\rho }_i}{\min }\left(d_{ij}\right)$, (2)

当数据点 $x_i$ 的局部密度达到最大时，相对距离变为： ${\delta }_i=\underset{j}{\max }\left(d_{ij}\right)$。

局部密度和相对距离确定完成后，通过绘制决策图选取聚类中心，一般选择决策图右上方的点，这些点既有较高的局部密度，也有较大的相对距离。最后采用一步分配策略进行非聚类中心点的分配：若数据点 $x_j$ 不是中心点，则将其归入密度比 $x_j$ 大且距离 $x_j$ 最近的数据点 $x_i$ 所在的类，该过程只执行一次，不用进行迭代更新 [11]。

2.2. 麻雀搜索算法(SSA)

根据麻雀种群的生物特性，将其行为理想化，制定相应规则，建立数学模型，从而得到新颖且有潜力的算法——麻雀搜索算法。SSA将麻雀种群分为两大类：发现者和加入者，发现者拥有较高的能量，它们的职责是搜索食物并提供相应的觅食区域和方向，这类群体占总种群的20%；加入者相对来说能量较少，它们利用发现者来获取食物，占总种群的80%。当麻雀意识到危险时，会即刻表现出反捕食状态 [12]。

假设麻雀种群为： $X={\left(x_{i1},x_{i2},\cdots ,x_{id}\right)}^{\text{T}},i=1,2,\cdots ,n$，n为麻雀总数，d为变量维数，麻雀个体对应的适应度值为： $F_X=\left[f\left(\left[x_{i1},x_{i2},\cdots ,x_{id}\right]\right)\right]$。在SSA中，有较高适应度值的发现者会优先获得食物，故发现者的位置更新公式为：

$X_{i,j}^{t+1}=\{\begin{array}{l}{X}_{i,j}^t\cdot \exp \left(-\frac{i}{\alpha \cdot ite{r}_{\max }}\right),R_2<ST\\ X_{i,j}^t+Q\cdot L,R_2\ge ST\end{array}$, (3)

其中， $X_{i,j}^t$ 表示第i个麻雀在第j维的位置，t为当前迭代次数， $\alpha \in (0,1]$ 是随机数， $R_2\in \left[0,1\right]$ 是预警值， $ST\in \left[0.5,1\right]$ 是安全阈值，Q是服从正态分布的随机数，L是元素全部为1的 $1\times d$ 矩阵。当 $R_2<ST$ 时，说明觅食环境周围是安全的，发现者可以大范围搜索食物；当 $R_2\ge ST$ 时，说明麻雀感应到了捕食者，需要撤往安全地带 [12]。

对加入者来说，它们会优先选择和发现者争夺食物资源，公式如下：

$X_{i,j}^{t+1}=\{\begin{array}{l}Q\cdot \exp \left(\frac{X_{worst}-X_{i,j}^t}{i^2}\right),i>\frac{n}{2}\\ X_P^{t+1}+\left|X_{i,j}^t-X_P^{t+1}\right|\cdot A^{\text{T}}{\left(A{A}^{-1}\right)}^{\text{T}}\cdot L,i\le \frac{n}{2}\end{array}$, (4)

其中， $X_{worst}$ 为当前全局最差位置， $X_P$ 为发现者所占最佳位置，A中每个元素被随机赋值为1或−1。当 $i>\frac{n}{2}$ 时，表示第i个加入者的适应度值较低，因未获得食物而处于饥饿状态，所以将飞往其他可以觅食的地方；当 $i\le \frac{n}{2}$ 时，表示第i个加入者将在当前最优位置附近寻找食物 [12]。

为保证其整个觅食过程的安全性，选取麻雀种群的10%~20%作为可以感知危险的麻雀，其位置更新表达式为：

$X_{i,j}^{t+1}=\{\begin{array}{l}{X}_{best}^t+\beta \left|X_{i,j}^t-X_{best}^t\right|,f_i>f_g\\ X_{i,j}^t+K\left(\frac{\left|X_{i,j}^t-X_{worst}^t\right|}{\left(f_i-f_w\right)+\epsilon }\right),f_i=f_g\end{array}$, (5)

其中， $X_{best}$ 为当前全局最优位置， $\beta$ 为控制参数的步长，是一个服从标准正态分布的随机数， $K\in \left[-1,1\right]$ 是调整移动方向的随机数， $f_i$ 是当前麻雀的适应度值， $f_g$ 与 $f_w$ 分别表示当前全局最佳与最差适应度值， $\epsilon$ 为最小常数。当 $f_i>f$ 时，表示麻雀处于种群边缘，易被捕食者袭击；当 $f_i=f_g$ 时，表示麻雀处于种群中间且感知到了危险，为了免受攻击需要向其他麻雀靠近 [12]。

3. 基于麻雀搜索算法的密度峰值聚类(SSA-DPC)

本文主要从以下两个方面进行改进：首先更改数据间的距离度量函数来更新距离矩阵；其次，利用麻雀搜索算法较强的全局寻优能力对DPC算法中的截断距离d_c进行优化。

3.1. 距离度量函数的改进

密度峰值聚类中，局部密度和相对距离的计算与所采用的距离度量方式有着密切联系，距离矩阵构造的好坏很大程度上影响着聚类的性能。传统DPC算法采用欧氏距离进行聚类，但在处理一些较为复杂的数据集，比如数据各维度的分量不一致时，欧氏距离不能准确地反映数据分布情况，不能很好地表现出数据间的特征。因此，考虑将数据间的距离度量方式改用标准欧氏距离来替代。

标准欧氏距离是对传统欧氏距离的缺点而做的一种改进方案，可将其看成一种加权欧氏距离。他利用数据样本的标准差，综合各维度的差异程度，使得各个维度都满足标准正态分布，这种处理方式更能体现数据间的分布情况，且能很好地反映数据间的特征，其计算公式为：

$d_{ij}=\sqrt{{\displaystyle \underset{k=1}{\overset{d}{\sum }}{\left(\frac{x_{1k}-x_{2k}}{s_k^2}\right)}^2}}$, (6)

其中，d为维度，s_k为标准差。

3.2. 截断距离d_c的优化

密度峰值聚类中有且只有一个参数——截断距离d_c，但该参数的确定方式是人们根据经验来估计，主观性很强，因此利用麻雀搜索算法较强的全局寻优能力对参数进行自适应选取。

本文提出的SSA-DPC算法将聚类结果的标准互信息(Normalized Mutual Information, NMI) [13] 指标进行变形作为适应度值目标函数，即d_c求解的收敛条件。NMI指标利用互信息来评价聚类质量，取值范围为 $\left[0,1\right]$，其值越接近1，说明聚类结果越接近于真实结果。假设U为真实标签向量，V为预测标签向量，MI为互信息，H为信息熵，那么NMI指标的数学表达式为：

$\text{NMI}=\frac{MI\left(U,V\right)}{\sqrt{H\left(U\right)H\left(V\right)}}$, (7)

取NMI指标的倒数作为SSA中的适应度值函数，表达式如下：

$f_i=\frac{1}{\text{NMI}\left(X_{i,j}\right)}$, (8)

在优化过程中，通过SSA算法进行多次迭代寻优，找出使DPC算法中NMI指标最大的d_c作为当前数据集最优的d_c，从而实现算法的聚类。

3.3. SSA-DPC算法描述

SSA-DPC算法将数据间的距离度量方式用标准欧氏距离来表示，把密度峰值聚类算法和麻雀搜索算法通过NMI指标函数有效地结合在一起，优化了截断参数d_c。记采用标准欧氏距离改进后的DPC为DPC^*。算法具体步骤如下：

输入：数据集 $S=\left\{x_1,x_2,\cdots ,x_n\right\}$。

输出：聚类结果 $C=\left\{c_1,c_2,\cdots ,c_k\right\}$，k为类簇数目。

步骤1. 计算数据点间的距离，构造距离矩阵，确定d_c取值范围。

步骤2. 运行DPC算法，根据聚类结果得到NMI指标的值。

步骤3. 根据数据集大小设置种群大小为S，最大迭代次数为T。

步骤4. 初始化种群位置，得到初始d_c值。

步骤5. 根据式(8)运行SSA算法，迭代更新d_c的值。

步骤6. 判断算法是否满足终止条件，若是，则结束迭代转至下一步；若否，则继续迭代。

步骤7. 将最优的d_c值代入DPC^*算法，得到聚类结果，完成聚类。

4. 仿真实验及分析

4.1. 实验数据集

为了验证SSA-DPC算法的有效性，本文采用4个人工数据集和3个真实数据集对该算法进行验证，7个数据集的具体描述如表1所示：

Table 1. Dataset description

表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指标的数学表达式为：

$\text{AMI}\left(U,V\right)=\frac{MI\left(U,V\right)-E\left[MI\left(U,V\right)\right]}{\max \left[H\left(U\right),H\left(V\right)\right]-E\left[MI\left(U,V\right)\right]}$, (9)

定义2 调整兰德系数(ARI) [15]：设a为同属于U与V的数据对个数；b为在U中属在同类，在V中属不同类的数据对个数；c为在U中属不同类，在V中属同类的数据对个数；d为在U与V中都属不同类的数据对个数 [11]，则有：

$\text{ARI}=\frac{2\left(ad-bc\right)}{\left(a+b\right)\left(b+d\right)+\left(a+c\right)\left(c+d\right)}$, (10)

定义3 FM指数(FMI) [16]：FMI是平衡了精确度和召回率的调和平均值，表达式为：

$\text{FMI}=\frac{a}{\sqrt{\left(a+b\right)\left(a+c\right)}}$, (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算法的三个

Figure 1. The renderings of the four algorithms in the Spiral dataset

图1. 四种算法在Spiral数据集的效果图

Figure 2. The renderings of the four algorithms in the Jain dataset

图2. 四种算法在Jain数据集的效果图

Figure 3. The renderings of the four algorithms in the Flame dataset

图3. 四种算法在Flame数据集的效果图

Figure 4. The effect of the four algorithms in the Aggregation dataset

图4. 四种算法在Aggregation数据集的效果图

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

^*通讯作者。