基于贝叶斯优化的密度峰值聚类算法

摘要：针对人工经验设定密度峰值的聚类算法（clustering by fast search and find of density peaks， DPC）的截断距离[dc]有很大的主观性和随机性，进而导致密度峰值聚类算法的性能无法完全发挥的问题。提出贝叶斯算法（Bayesian Optimization，BO） 优化密度峰值的聚类算法以实现自适应聚类。并解决密度峰值的聚类算法簇间数据点识别错误问题。该方法建立在数据集Aggregation、Flame、Jain、Spiral上进行实验，分别通过内部指标Silhouette和外部指标F-measure对实验结果评估，性能均有提升。

关键词：密度峰值的聚类算法;截断距离;贝叶斯算法;自适应聚类;内部指标

中图分类号：TP391      文献标识码：A

文章编号：1009-3044（2022）22-0008-05

1 引言

21世纪随着互联网的快速普及，人们在形形色色的生活中产生了大量的数据，大数据的时代随之来临，怎样从这些数据中获得有用的信息成为当今研究热点。

聚类是数据挖掘、机器学习、图像识别等领域预处理数据的一种基本算法。聚类把一组没有标签定义的数据集或者样本集，依据样本的一组特征值，按照某种相似性度量手段将特征值相似度较高的数据点划分成同一个类簇，为后续处理提供了可贴标签的分类数据。

聚类是一种无监督学习，即在无任何人工干预的情况下对数据进行区分。相似度高的数据聚合成一类簇。不同簇之间的样本点相似性较低[1-2]。有监督学习主要任务是分类，通过很多已经标记过的数据来对新数据进行区分。相比监督学习，无监督学习则不需要大量人工标记的训练样本来作为区分数据的前提。在大数据信息共享时代，因为数据聚集模式复杂、多变，单一相似度标准难以适应多种模式，所以现有的聚类算法不能够满足已有种类繁多的数据集。面对以上现状，不断衍生出众多的聚类方法。目前常用的聚类算法大致可分为：基于模型的聚类，基于划分的聚类，基于层次的聚类，基于网格的聚类，基于密度的聚类。其中，基于模型的聚类算法一般假设要聚类的数据来源于某个混合的潜在概率分布模型，通过对该模型进行参数估计来完成聚类。基于划分的聚类算法需要一个最优化的目标函数来发现聚类数据中的类别信息，迭代的将数据集划分为几个部分，再验证划分过程是否科学合理。常见的划分聚类算法如K-means[3]，该算法简单并且高效，聚类效果主要受类簇中心点[k]值影响较大。一般情况下[k]值的确定具有很大的主观性，这对没有先验经验的测试下的取值会对聚类结果有很大的影响。面对高维的数据处理对象聚类效果不佳。基于网格的聚类算法对数据的处理比较粗糙，主要用于处理大量多维数据的聚类问题。基于层次的聚类算法分为自下而上的聚合层次聚类和自上而下的分裂层次聚类，其目的是让聚类过程不受参数的影响并且更加灵活。基于密度的聚类核心思想是先选定较高密度的数据点，再将周边与其相近的点聚为一类。常见的基于密度的聚类算法如DBSCAN[4]聚类算法虽然能够处理任意大小形状的簇，对噪声的容忍性较好，但当簇密度变化较大时聚类效果较差，并且当遇到大量高维的数据时会大量地消耗计算资源。

DPC算法[5]是近几年提出的一种基于密度划分的聚类算法，该算法依据密度峰值决策图选取合适的密度峰点;并将图中代表样本的其他数据点划分到最近或匹配的密度峰点类别中，从而得出簇的划分。DPC算法的优点之一是除了决策图中的密度峰值点需要人工干预选择外，整个算法仅需要预先给出一个输入参数（截断距离） ，不需要像多数其他聚类算法一般预先指定簇数目，提高了算法的可靠性与适应性。另一方面，DPC算法在初期决策图中选择的密度峰点即确定了簇的数目及分布，不需要通过反复迭代来获得最优结果，其效率相对于其他聚类算法有着显著优势。

随着对DPC算法的不断深入研究，越来越多的改进DPC算法相继出现。针对DPC算法的局部密度计算方式过于单一的问题，Liu等人[6]提出ADPC结合KNN的算法，该算法重新定义了局部密度的计算方法。针对DPC算法的一次性样本数据分配策略可能存在错误分配连带问题，即一旦一个数据点被错误分配，随后可能会有更多的点被错误分配，Seyed等人[7]提出了一种DPC-DLP的聚类算法，该算法统一确定簇中心，将簇中心联合起来构建新的KNN图，通过图的传播方法分配样本数据。Xie[8]等人提出了计算数据[ai]相对于[其K]近邻的局部密度度量方式和通过从聚类中心开始对点的K个最近邻进行广度优先搜索来分配数据点，从而对DPC聚类算法进行优化。

面对不同类型数据时，这些改进的DPC聚类算法虽然有较好的聚类结果，但是截断距离仍需要人为设定。当数据密度相差较大时，很难人为选择一个合适的截断距离，如果输入截断距离百分比过大时可能会出现所有数据点都被分到同一类，如果输入截断距离百分比过小时可能会出现聚类数目过多。所以截断距离[dc]是影响聚类效果好坏的重要参数，截断距离优化其实就是机器学习中超参数优化，目前主流的机器学习超参数优化方法有群体智能优化算法、网格搜索（即穷举法） 、随机搜索算法、贝叶斯优化算法。但是群体智能优化算法先要提供非常多的初始样本点，并且其优化效率一般。网格搜索算法是将所有涉及的超参数进行组合，对每个组合进行建模与评价，最后选择评价最高的组合作为模型最终的超参数，这种方法需要经过长时间的计算才能获得最优的超参数组合。而随机搜索则是在超参数的分布中随机搜索超参数进行建模，它的缺点是容易错过一些最优超参数。贝叶斯优化方法要优于群体智能优化算法、网格搜索算法和随机搜索算法，因为它在尝试下一组超参数时，会借鉴之前的评估结果，省去了很多无用功。因此本文选取贝叶斯算法[9-10]（Bayesian Optimization） 作为DPC聚类算法的优化手段，利用贝叶斯算法预测出的较优[dc]值，驱动DPC算法选择出合适的聚类中心，提高DPC聚类算法的性能。

2 相关研究

2.1 DPC算法

密度峰值的聚类算法[11-12]（clustering by fast search and find of density peaks， DPC），该算法能够自寻簇中心，对任意类型、大小的数据集能够进行准确高效的聚类。DPC算法具有两个前提：

1） 峰值密度点（簇中心） 局部密度大于近邻围绕的局部密度。

2） 要使得不同簇中心之间的距离相对较远。

为了能够准确找到同时满足以上两个条件的簇中心，DPC算法引入了局部密度的定义。局部密度的计算如公式（1） 所示：

[ ρi=j≠if（dij-dc）]               （1）

假设数据点[ai]的局部密度为[ρi]，[dij]为[ai]到[aj]的距离，[dc]为两点间的截断距离。[f（x）]为逻辑判断函数，当[x]值小于0时[f（x）]判定为1否则[f（x）]判断为0，该函数表示为满足一定距离阈值数目[ai]的多少，数目越多值越大，密度越高。

高密度最小值计算如公式（2） 所示：

[δi=minj：pj>pi（dij）]               （2）

[δi]表示为高密度的最小距离为[ai]到[aj]距离最近并且局部密度大于[ai]的局部密度的距离。当[ai]为数据集中密度最大的点时[δi]的计算如公式（3） 所示：

[δi=maxjϵc（dij）]             （3）

2.2 贝叶斯优化算法

贝叶斯优化算法（Bayesian Optimization，BO） 是一种基于黑盒的优化算法[13]，该算法的优化思路是首先生成初选解集合[x1，x2，x3，...xn]，也就是n个采样点，其次用目标函数[f（x）]分别计算以上样本点处的值，接着通过高斯回归过程来计算每一点处[fx]函数值的均值和方差，并且根据当前采样数据点集[D={（xn，f（xn）}]更新[pf（x）|D]的均值和方差计算采集函数[u（x）]，然后使用采集函数极大值[xn+1=argmaxxu（x）]确定下一个采样点。下一个采样点的函数值为[yn=f（xn+1）]，将该采样点加入原有集合中，不断重复直至迭代终止，最后从这些点集中找出[fx]函数值最大的点就是问题的最优解。

1） 采集函数的构建

构建采集函数[14]常用的方法有基于提升策略的PI，EI办法和置信边界策略方法。因为EI采集函数参数少，既整合提升的概率又体现不同的提升量，所以本文采用基于提升策略中的EI方法作为采集函数。已知对[n]个数据点进行探索，该点集中极大值函数按公式（4） 计算：

[f*n=max（f（x1），...，f（xn））]       （4）

现考虑下一搜索点[x]，如果下一搜索点[f（x）]值大于等于[f*n]，则该点处的极大值为[f（x）]否则为[f*n]。将加入新点后的改进值写成[f（x）-f*n+]（如果下一搜索点[f（x）]值大于等于[f*n]，则[f（x）-f*n+]等于正值[f（x）-f*n]，否则[f（x）-f*n+]为0），再计算所有[x]处的改进值的数学期望，并将数学期望最大的[x]点作为下一个探索点。期望改进函数如公式（5） 所示：

[EInx=Enf（x）-f*n+]           （5）

根据上述公式计算出[n]个采样点[x1，x2，x3，...xn]和函数值[y1，y2，y3，...yn].该期望采用高斯过程回归定义。假设在[xn]点的均值为[μ（x）]方差为[σ2（x）]，令[Z=f（x）]，根据期望定义能够得出公式（6） ：

[EIn（x）=-∞+∞Zf*n+12πσexp-（Z-μ）22σ2dZ]   （6）

化简为如公式（7） 所示：

[EIn（x）=-∞+∞（Z-f*n）12πσexp-（Z-μ）22σ2dZ] （7）

对公式（7） 进行换元可以得到公式（8） 如下所示：

[EIn（x）=μ-f*n（1-δf*n-μ/σ+σφf*n-μ/σ）]                            （8）

其中[δ（x）]为正态标准分布函数，若令[G（x）=μ-f*n]则有公式（9） ：

[EIn（x）=G（x）++σ（x）φG（x）σ（x）-G（x）δG（x）σ（x）]    （9）

因此由上述公式可以推导出[μ（x）]，[σ2（x）]均为[x]的函数，因此EI也是[x]的函数。为了能够优化目标函数[f（x）]因此通过最大化[EIn（x）]来得到新的评估点[xn+1]，计算如公式（10） 所示：

[xn+1=argmaxEIn（x）]               （10）

3 BO-DPC算法

3.1 主要思想

DPC在数据聚类方面具有很好的性能，但是截断距离[dc]值研究者凭借经验设定的，DPC算法不能完全发挥DPC算法的性能。因此本文选取贝叶斯算法来优化DPC聚类，利用贝叶斯算法预测出的较优[dc]值，驱动DPC算法选择出合适的聚类中心，提高DPC聚类算法的性能。获得最终的聚类结果。BO-DPC算法的流程图如图1所示。