结合鲸鱼优化算法的自适应密度峰值聚类算法

2021-02-04王芙银张德生

计算机工程与应用 2021年3期

王芙银，张德生，张晓

西安理工大学理学院，西安710054

随着互联网技术的飞速发展，随之产生的数据也以惊人的速度增加，这些海量的数据包含着丰富的信息。人们的日常活动都可以在一定形式上量化为数据的方式，但这些数据通常是毫无规律、杂乱无章的，随着时间的推移，这些数据的积累就更加庞大，大数据的时代也就应运而生。怎样从这些数据中获得有价值的信息就变成了当今时代研究的热点[1]。

聚类分析[2]在数据挖掘中扮演着重要的角色，它是无监督机器学习的一种，在不需要先验知识的情况下，根据数据的分布，计算数据间的相似性，将数据划分成不同的集合，成为类簇。同一类簇间的数据有着较高的相似性，不同类簇间的数据有着较低的相似性。按照数据分布方式以及算法原理，目前常见的聚类算法大体可分为：基于划分的聚类、基于层次的聚类、基于密度的聚类[3-4]、基于网格的聚类及基于模型的聚类等[3]。其中，基于密度的聚类算法可以在不同数据中发现各种形状及各种大小的簇，其思想是在选定较高密度点后，将周边与高密度点相近的点聚集为一类。

2014 年意大利学者Rodriguez 和Laio 在Science杂志上提出了一种快速搜索发现密度峰值聚类算法（Clustering by fast search and find of density peaks），这是一种基于密度的聚类算法，简称密度峰聚类算法（Density Peaks Clustering algorithm，DPC）[5]。该算法不需要事先确定类簇的个数，在各种复杂的数据集中能有效识别出类簇，对噪声点的识别也有一定的优越性，且对于任意形状的数据集都能达到很好的聚类效果，适用于大规模数据的聚类分析。基于这些优势，DPC算法目前越来越多地被应用于各个领域，其涉及的领域包括机器学习、模式识别、人工智能、图像处理等多个方面[6]。

鲸鱼优化算法（Whale Optimization Algorithm，WOA）[7]是Mirjalili等人于2016年所提出的一种新型元启发式算法，与其他智能算法相比具有多方面的优势。例如，文献[7]通过对29 个数值优化问题和6 个工程优化问题进行测试，验证了WOA 算法比模拟退火算法和差分进化算法等元启发式算法具有更强的竞争力。另外，如文献[8]所指出的那样，与典型的群智能优化算法相比，WOA 算法具有原理简单、调节参数少、寻优能力强等特点，且在收敛速度与收敛精度方面均明显优于引力搜索算法和粒子群优化算法等。除此之外，WOA 算法在求解优化问题时表现优异，且应用领域广泛。目前，国内外的研究学者将鲸鱼优化算法广泛应用于生产优化[8]、负载预测[9]、二次分配[10]、图像分割[11]、社团检测[12]等领域，在这些应用领域中，鲸鱼优化算法发挥了重要的作用，为各领域的优化问题寻求了较好的解。

针对DPC 算法自身所存在的问题，许多学者对其做了相应的改进以适应不同的应用领域。例如，丁志成等人[13]提出一种基于KL 散度的密度峰值算法，该算法提出一种自动选取聚类中心的方法，利用KL 散度的差异性度量准则对聚类中心和非聚类中心进行清晰的划分，以KL 排序图中的拐点作为分界点实现对聚类中心的自动选取；文献[14]在原算法确定类簇中心时，将模糊规则应用于其中，提出一种Fuzzy-CFSFDP算法，更有利于类簇中心的选择，同时提高了聚类结果的准确率；文献[15]提出将网格划分和圆划分的方法应用于DPC算法来筛选点，提出了GDPC 算法和CDPC 算法，都有效地降低了算法的复杂度，其中GDPC算法相比于DPC算法的计算时间更短，CDPC算法相对于DPC算法在大规模数据集上的准确度更高；杜沛等人[16]提出了基于K近邻的比较密度峰值聚类算法，该算法结合K近邻概念重新定义了截断距离和局部密度的度量方法，对任意数据集能自适应地生成截断距离，并使局部密度的计算结果更符合数据的真实分布，同时在决策图中引入距离比较量代替原距离参数，使类簇中心在决策图上更加明显；蒋礼青等人[17]提出基于近邻距离曲线和类合并优化的聚类算法，此算法利用近邻距离曲线变化情况自动确定截断距离，并利用计算值的方法指导类的合并，引入内聚程度衡量参数解决了类合并后不能撤销的难题，从而实现对多密度峰值数据的正确聚类；高诗莹等人[18]提出了基于密度比例峰值聚类算法，该算法将密度比例引入到密度峰值聚类算法中，通过计算样本数据的密度比峰值来提高数据中密度较小类簇的辨识度，进而提升整体聚类的准确率。

以上几种改进算法虽然较原DPC算法都具有较好的聚类表现，但也存在着一定的问题：（1）没有很好地克服原算法对截断距离的依赖性，人为设定截断距离使得最终的聚类结果具有很大的随机性和主观因素，不能保证截断距离选取的有效性[19-20]；（2）在决策图生成后，需手动选择聚类中心[19]，对于某些数据集而言，可能会导致聚类中心多选或漏选的情况，这将会直接影响聚类结果。针对以上问题，本文提出了一种结合鲸鱼优化算法的自适应密度峰值聚类算法（WOA-DPC）。该算法首先根据加权的局部密度和相对距离乘积的斜率变化趋势实现聚类中心的自动选择，再建立以ACC 指标为目标函数的优化问题，利用鲸鱼优化算法（WOA）有效地寻优能力对目标函数进行优化，寻找最佳的截断距离dc。

1 预备知识

1.1 密度峰值聚类算法（DPC）

密度峰值聚类算法（DPC）原理主要依据两个直观的假设：（1）聚类中心被一群密度较低的邻居点包围着；（2）聚类中心离比它密度更高的点的距离相对较大。该算法只需输入截断距离dc这一个参数，通过人工手动选取聚类中心点，然后根据一步分配策略完成对剩余点的聚类和分配。DPC算法中，局部密度的计算有两种方式，当数据集较大时，局部密度的计算如下：

当数据集较小时，局部密度的定义如下：

其中截断距离：

式中，di为所有数据点中任意两点间欧氏距离的升序排列。

定义相对距离为样本点与最近高密度样本点之间的距离，如式（5）所示：

DPC算法根据式（4）得出截断距离dc，再将其代入局部密度ρ和距离δ的计算公式，根据ρ和δ绘制出一个二维空间的决策图，通过决策图手动选取出ρ和δ相对较大的值作为聚类中心，最后，根据一步分配策略，将剩余点分配到密度比它高且距离其最近的类簇当中。

1.2 鲸鱼优化算法（WOA）

WOA算法是通过模拟鲸鱼捕食行为而提出的一种新型仿生算法，主要分为三个阶段：猎物包围阶段、气泡袭击阶段、猎物搜索阶段[7]。

1.2.1 猎物包围阶段

在这个阶段，鲸鱼能够识别猎物的位置并包围它们以捕获猎物。此阶段鲸鱼个体向当前最优解移动并更新其位置，该行为的数学模型[7]如下：

式中，t是当前迭代次数，X*(t) 是目前最优解位置，X(t)是当前鲸鱼位置，A、C是系数向量，r为[0,1]之间的随机数，a为从2到0的线性递减参数。

1.2.2 气泡袭击阶段

在此阶段，通过收缩环绕和螺旋形路径来设计鲸鱼捕食吐气泡的行为，其数学模型[7]为：

式中，b是定义对数螺旋线形状的常量，l是[-1,1]之间的随机数。

假设座头鲸收缩环绕和螺旋形位置更新的概率均为50%。建立如下位置更新模型[7]：

式中，变量p是[0,1]之间的随机数。

1.2.3 食物搜索阶段

当|A|≥1 时，种群个体随机选择鲸鱼个体作为参照更新其位置，强迫鲸鱼个体远离最优参考鲸鱼，这样可以有效增强算法的全局探索能力，数学模型[7]如下：

式中，Xrand(t)是从当前种群中随机选择鲸鱼个体。在具体问题优化过程中，鲸鱼个体根据不同的位置更新方式不断向最优解靠近。

WOA算法具体步骤如下：

步骤1在解空间中随机初始化S个鲸鱼个体位置，给出最大迭代次数T及当前迭代次数t。

步骤2通过目标函数计算每个个体适应度值，并保留最优个体为X*(t)。

步骤3更新系数向量A及随机数p，根据A及p的取值情况对所有个体进行相应的位置更新：

当|A|≥1，p ＜0.5 时，执行公式（12）进行位置更新；

当|A|＜1，p ＜0.5 时，执行公式（6）进行位置更新；

当p≥0.5 时，执行公式（9）进行位置更新。

步骤4计算更新后个体的适应度值，并更新保留最优个体位置及最优适应度值。

步骤5判断t ＜T是否成立，若成立，令t=t+1，转步骤2；否则，算法结束，输出最优解及最优值。

2 结合鲸鱼优化算法的自适应密度峰值聚类算法

本文主要从以下两个方面进行改进：首先通过加权的局部密度和相对距离乘积的斜率变化趋势实现聚类中心的自动选择；其次，利用鲸鱼优化算法较强的寻优能力对DPC算法中的截断距离dc进行优化。

2.1 聚类中心的自适应选取策略

原DPC 算法在选取聚类中心时，需要在决策图中手动截取那些局部密度ρ和相对距离δ大的点为聚类中心，而截取过程中带有一定的主观性，例如，图1所示类别数为7的Aggregation数据集的聚类决策图，但从图中看出同时具有较大的ρ和δ值的点并不容易确定，手动截取容易造成聚类中心个数选取不准确的问题，若选取聚类中心时出现了错误，那么在接下来的数据点分配类簇上会产生连锁反应，最终使得聚类效果不理想。

图1 Aggregation数据集的聚类决策图

在实际问题中，也可能存在一些具有较大ρ与较小δ或有较小ρ与较大δ的数据点也为聚类中心。因此，需综合考虑局部密度ρ和相对距离δ，定义如下度量：

其中N为数据集中样本点个数。

为避免不同量级间的相互影响，对ρ和δ进行归一化处理，得到新的γ定义如下：

将经归一化处理所得到的γi(i=1,2,…,N)进行降序排列，取前40个点。下文中，为了记号方便，仍用γ1,γ2,…,γ40表示由大到小排序后的前40 个γ值。根据γ降序排列图选取聚类中心，γ值越大的点越有可能是聚类中心，可以有效避免由于单独考虑ρ和δ所带来的误差。然而，对于一些数据集使用该方法也会存在聚类中心选取不准确的问题。以文献[5]中使用的类别为5 的GDP数据集为例，图2为该数据集的γ降序排列图。图中γ值呈现先快速下降，再趋于稳定变化的趋势，且图中存在多个拐点。直观来看γ7之后的值趋于稳定，会误以为聚类中心的个数为7个，而实际上聚类中心只有5个。因此，仅根据γ降序排列图有时也很难准确地选取出聚类中心。

图2 GDP数据集的γ 降序排列图

对此，本文将根据γ的斜率来选取聚类中心。一般地，对于归一化到[0,1] 上的斜率值最大的点可选作聚类中心和其他点的分界点，即将所对应的数据点选取为聚类中心。但考虑到的前几个值一般很大且呈现较强的跳跃性，仍不易准确选取聚类中心。如图2 所示，容易看出γ1到γ2差值最大，而将γ1所对应的数据点选作聚类中心显然是错误的。因此，这里引入加权的斜率度量如下：

其中，(i-1)可看作权值，随着i的增大而增大，这样可使γi值大的点拥有较小的权值，而γi值小的点拥有较大的权值，以降低前面一些过大值对聚类中心选取的影响，从而实现了聚类中心的自适应准确选取。综上，本文所提的聚类中心选取策略分为两步：

（2）将降序排列的前i0个γ值所对应的数据点选为聚类中心。

根据公式（15）得到的ki值描点作图，称其为加权γ斜率变化趋势图。图3 为GDP 数据集的加权γ斜率变化趋势图。由此易知k5最大，故聚类中心个数为5，且将前5个γ值所对应的数据点选为聚类中心，解决了利用公式（14）选取聚类中心的问题。类似地，图4、图5分别为Spiral数据集和D31数据集利用公式（14）和（15）选取聚类中心的效果对比图。由图4（b）易知聚类中心个数为3，这和Spiral数据集的类别数3是一致的，而由图4（a）在γi值趋于稳定前会误以为聚类中心的个数为5。虽然D31数据集的类别数较多，为31个，但由图5（b）亦可准确选取出聚类中心的个数。此外，通过大量模拟试验表明，利用公式（15）对大部分数据集均可客观选取出聚类中心的个数。

图3 GDP数据集的加权γ 斜率变化趋势图

图4 Spiral数据集的聚类中心选取效果对比图

图5 D31数据集的聚类中心选取效果对比图

2.2 截断距离dc 的优化选取策略

原DPC 算法中截断距离dc需要人为设定，且取值较为敏感。为了更直观地反映此问题，以图6中给出的R15数据集所得到的聚类结果图为例，可以得出，dc的细微不同所得到的聚类结果存在较大的差异。因此，对截断距离dc进行优化就变得很有必要。

图6 不同dc 所对应的聚类结果图

本文利用WOA 算法较强的寻优能力，来选取最佳的截断距离dc。ACC 指标[21-23]是广泛应用于统计学和信息检索领域的评价指标，对聚类结果能够产生准确的评判，假设Pj为已知人工标注的簇，Cj为经过聚类后的簇，则ACC指标的计算公式如下：

在优化过程中，以ACC指标作为WOA算法的目标函数，对DPC算法中的截断距离dc进行优化，所选取的目标函数ACC 指标是关于dc的一维函数，即给定一个dc便可得到一个ACC 指标值，ACC 指标的取值范围在[0,1]之间，其值越接近于1，说明聚类结果越好。

利用WOA算法多次迭代寻优，找出使DPC算法中ACC指标最大时的dc作为当前数据集最优的dc，从而实现算法的聚类。

2.3 WOA-DPC算法描述

本文所提出的WOA-DPC算法的基本思想：首先根据γ的斜率变化趋势图选取聚类中心，从而避免了聚类中心需要手动选择的缺陷；其次，将鲸鱼优化算法和聚类中心自适应的密度峰值聚类算法根据ACC指标函数有效地结合起来，对参数dc进行了优化，克服了DPC算法对参数选取敏感的缺陷。算法具体步骤如下，流程图如图7所示。

输入：实验数据集U(x)={x1,x2,…,xn}。

输出：聚类结果H={h1,h2,…,hm}，m为数据集聚类结果类别数。

步骤1设置WOA算法的种群规模为S，最大迭代次数T。

步骤2数据预处理，计算数据集中样本间的欧氏距离，确定dc的取值范围。

步骤3初始化WOA算法的种群位置，即dc的值。

步骤4将dc代入式（3）及式（5）中，分别计算出所有点的局部密度ρi与相对距离δi。

步骤5根据式（15）得到γ斜率变化趋势图，并自动选取聚类中心。

步骤6引入如式（16）所示的评价指标ACC 作为WOA 的目标函数，记ACC 指标最大时所对应的dc为。

步骤7利用WOA算法更新dc。

步骤8判断WOA算法是否满足迭代终止条件，若是，则结束迭代并转步骤9。若否，则跳转至步骤4继续优化寻优。

步骤9将最优截断距离dc所对应的聚类结果进行除噪，得到最终聚类结果，完成聚类。

图7 WOA-DPC算法流程图

2.4 算法复杂度分析

对于含有N个样本点的数据集，DPC 算法的时间复杂度主要来自计算样本点间的距离矩阵D的复杂度O(N2)，对欧氏距离进行快排的复杂度O(N2lbN)，计算局部密度ρ和最短距离δ的复杂度O(N2)组成。对于本文所提WOA-DPC 算法，算法复杂度主要体现在优化过程。假设鲸鱼群体规模为S，最大迭代系数为T，优化截断距离dc问题时维度为1，故优化dc的复杂度为O(S·T)。在优化过程中，由于dc的变化会导致局部密度ρ和相对距离δ的改变，故此过程的复杂度为O(N2·T)。综上，本文所提算法的时间复杂度为。

3 仿真实验结果及其分析

3.1 实验数据集

为了评估本文所提算法的可行性和有效性，采用如表1所示的9个数据集对其进行验证。

表1 人工合成数据集以及UCI数据集描述

3.2 评价指标

为避免重复使用ACC 指标，本实验采用FM 指数（FMI）、调整兰德系数（ARI）和调整互信息（AMI）[21-23]三个评价指标来对各算法的聚类结果进行评估。假设C代表样本真实标签，C*代表聚类产生的结果。

（1）FMI指标

FMI是成对精度与召回率的几何均值，定义式如下：

其中，a表示在C和C*中属于同一类数据点的对数，b表示在C中属于同一类但在C*中不属于同一类的数据点的对数，c表示在C*中属于不同类但在C中属于同一类的数据点的对数。FMI 指标的取值范围是[0,1]，其数值越大代表聚类效果越好。

（2）ARI指标

兰德指数（RI）的定义式为：

式中，a代表在C和C*中属于同一类数据点的对数，b代表在C*中属于不同类但在C中属于同一类的数据点的对数，代表数据集中可组成总元素的对数。使用RI指标时，不能保证类别标签在随即分配的情况下，其值接近0。故引入调整兰德指数（ARI）来解决这一问题，ARI指标的定义式为：

其中，E(RI) 表示RI 的数学期望，ARI 的取值范围为[-1,1]，值越大表示聚类结果越精准。

（3）AMI指标

与ARI 相似，AMI 也是一种常见的聚类评价指标，它的定义式为：

式中，H(A),H(B)表示两个类别标签的熵，AMI是基于互信息（MI）来衡量聚类效果的类别信息，E(MI)表示MI 的数学期望。AMI 的取值范围是[-1,1]，值越接近于1，表示聚类结果越好，即与真实结果越吻合。

3.3 实验结果及分析

对表1 所给出的数据集，使用WOA-DPC 算法与DPC 算法、DBSCAN 算法和K-Means 算法对其进行聚类，图8～10 分别为四种对比算法在Spiral、Aggregation和Flame三种人工数据集上聚类效果图，这三种数据集的总体分布情况和聚类的数目是截然不同的，它们可以更直观地反映出四种聚类算法的聚类性能。图中颜色不同的点被分配到不同的类簇中，其中，蓝色星形表示聚类中心点，叉形表示噪声点。

图8 四种算法在Spiral数据集上的聚类效果图

图9 四种算法在Aggregation数据集上的聚类效果图

图10 四种算法在Flame数据集上的聚类效果图

从图8 对Spiral 数据集的螺旋形聚类效果图中看出，除K-Means 算法外，其他三个算法均能够准确地对其进行聚类，K-Means 算法的聚类结果出现明显的错误，它将该数据集平均分为了三部分，且将每个部分的中心当作聚类中心。尽管K-Means 算法在该数据集上得到了正确的聚类数目，但无法进行正确的聚类，这表明K-Means 算法不能很好地对非凸分布的数据进行聚类。同时，其余三种算法均得到了正确的聚类结果，也可明显可看出WOA-DPC 算法比DPC 算法的聚类中心的识别更为准确。

在图9 的Aggregation 数据集聚类效果图中，WOADPC算法和DPC算法均得到了正确的类簇，WOA-DPC算法也更精准地识别了聚类中心点。DBSCAN 算法虽然能够识别出正确的聚类数目，但其中某些点被其标记为了噪声点，导致聚类效果略差。而K-Means算法在一个集群中出现了两个聚类中心，并出现了在三个蓝色类簇之间选择聚类中心的情况。从而使得聚类结果产生了较大的错误。因此，WOA-DPC算法能够准确地识别出聚类中心，并有效地优化了dc，从而得到了更加精准的聚类结果。

从图10 的Flame 数据集的流形聚类效果图可知，WOA-DPC 算法、DPC 算法和DBSCAN 算法都可正确地识别聚类数目，而DBSCAN 算法将左上边的两个点识别为了噪声点，导致聚类准确率降低。K-Means算法将本该属于红色类簇的点分配给了绿色类簇，以使整个数据集看起来像是从对角线斜率切开的，从而产生了错误的聚类结果。因此，可以看出WOA-DPC算法不仅能够得到正确的聚类数目，而且可以更精准地识别出聚类中心的位置，从而得到更佳的聚类效果图。

表2 给出了WOA-DPC 算法与其他对比算法在各数据集上的聚类评价指标值。图11～13 分别为四种算法在各种数据集上的指标对比图。从表2 所得的评价指标值可以看出，通过对聚类中心选取策略改进和利用鲸鱼优化算法对截断距离的优化，WOA-DPC算法对九种数据集进行聚类所得的FMI、ARI和AMI指标值均得到了更好的结果。在Spiral 数据集和Flame 数据集中，WOA-DPC 算法和DPC 算法的聚类指标值都为1，而在其他几个数据集上DPC 算法的聚类表现略差于WOADPC 算法，但优于K-Means 算法。尤其在Jain 数据集中，WOA-DPC算法相较于DPC算法的AMI指标值提高了大概40%。DBSCAN 算法在九种数据集的聚类表现中，Spiral 数据集的聚类指标为1，表明对其聚类效果良好，在Jain数据集上，DBSCAN算法表现优于DPC算法，而在另外七种数据集中，其聚类效果均差于WOA-DPC算法和DPC算法。K-Means算法在四种对比算法中，整体表现差于其他三种算法。同时，在维数比较大的Seeds和Waveform 数据集中，WOA-DPC 算法的准确率也较其他三种算法有了较大的提高，说明本文所提算法无论对于高维数据集还是低维数据集都有较好的聚类结果。