密度聚类方法研究*

2022-03-16赫德军武欣嵘

通信技术 2022年2期

赫德军，武欣嵘，俞璐

（陆军工程大学，江苏南京 210001）

0 引言

聚类是机器学习中一种重要的无监督学习方法[1]，可以在缺少先验知识和模型分布的前提下，探索数据点之间的关系，评估数据的内在结构，在数据挖掘、模式识别、图像分割、信息检索等方面应用广泛[2]。但是，在不同的研究领域，存在着海量的、类型各异的数据，难以找到一种普适的聚类方法[3]。迄今为止，针对不同的数据特性，研究人员提出了大量的聚类分析方法。基于不同的准则，经典聚类大致可以分为基于划分的聚类、基于层次的聚类、基于密度的聚类、基于网格的聚类、基于模型的聚类[4]几种。其中，基于密度的聚类是众多聚类算法中一类重要的聚类方法，它在多个研究领域有着广泛的应用，尤其是在以空间信息处理为代表的空间数据挖掘领域日趋活跃[5]。

本文将对密度聚类方法进行研究，旨在介绍密度聚类的基础理论、典型算法、发展现状、应用场景等。第1 节介绍聚类的定义、分类和评价指标，第2 节介绍密度聚类的几种典型代表算法，第3 节对密度聚类的发展现状、应用场景进行分析，并展望其未来的发展方向。

1 聚类概述

1.1 定义

聚类不是指某种具体的算法，而是一个分组任务。聚类根据主观选择的相似性度量准则，将无标签数据分组成多个簇或者类，并且最大化每个类内数据的同质性和不同类间数据的异质性[6]。简而言之，聚类即针对待处理的数据，根据它们特征的距离或者相似度，将模式相同的样本聚为一簇，从而划分出不同的类，使得类内样本的相似性最大，类间样本的差异性最大

1.2 聚类的分类

聚类及其改进方法层出不穷，其分类标准也大相径庭，有基于结果分类的，有基于方法分类的，也有基于数据规模分类的[7]。本文采用较为普遍的基于方法的分类，这种经典的方法将聚类分为基于划分的、基于层次的、基于密度的、基于网格的和基于模型的方法。

1.2.1 基于划分的聚类

基于划分方法的聚类，需要事先设定聚类中心或者聚类数目。这种聚类方法首先根据设定的聚类数目创建初始划分；其次通过反复迭代运算，将样本对象在划分聚类间来回移动，以此改进划分，逐步减小目标函数误差；最后目标函数收敛后得到最优划分聚类[8]。基于划分的聚类方法主要有K 均值（K-means）聚类算法[9]、K 中心点（K-medoids）聚类算法[10]、K 模式（K-modes）聚类算法[11]、近邻传播（Affinity Propagation，AP）算法[12]、围绕中心点的划分（Partitioning Around Medoid，PAM）聚类算法[13]、大型应用中的聚类（Clustering LARge Applications，CLARA）算法[14]等。

划分聚类算法的优点是简单易实现，但是该类算法也存在明显缺点：需要预先设定聚类中心和聚类数目；对初始化聚类中心敏感，易陷入局部最优解；算法基础基于欧式距离，对非凸数据效果不佳；对噪声和离群点敏感。

1.2.2 基于层次的聚类

基于层次的聚类是将数据对象组成层次结构或者关于簇的树，从而将数据划分成不同层次上的类。根据层次分解顺序的不同，可以将聚类分为凝聚的层次聚类和分裂的层次聚类。凝聚的层次聚类是自底向上进行合并，具体是一开始将每个样本单独成簇，然后在合并过程中，将两个最相似的簇合并为一个簇，如此迭代，将较多的小簇合并为较少的大簇，直至合并为一个簇。而分裂的层次聚类则相反，该算法是自上而下地进行分裂，从将所有样本归为一个簇开始，递归地将簇分裂成小簇，直至每个样本为一簇。层次聚类中比较著名的算法有基于代表对象的聚类（Cluster Using REpresentatives，CURE）算法[15]、利用层次结构的平衡迭代归约和聚类（Balanced Iterative Reducing and Clustering using Hierarchies，BIRCH）算法[16]、鲁棒的链接型聚类（RObust Clustering using linKs，ROCK）算法[17]。

层次聚类的优点在于能够根据用户的需求灵活控制聚类的进程，得到合适程度的聚类，其缺点有：只适合球形和相似差异小的数据；对孤立点敏感；算法的复杂度较高，不适合处理大规模数据。

1.2.3 基于密度的聚类

经典聚类算法大多是利用距离来评价数据间的相似性，尤其是基于欧氏距离的算法，擅长处理凸型数据，但对非凸集合聚类效果不佳。而基于密度的聚类是将样本密度作为相似度，簇是样本对象的密集区域。聚类的过程就是寻找被低密度区域分割开的高密度区域的过程。其核心思想是只要邻域的密度超过一定阈值，就基于可连接样本不断扩展可聚类簇，直至密度的边缘。因此，基于密度的聚类能够过滤噪声或者离群点，发现任意形状的簇。典型的密度聚类算法有基于密度的带噪声的空间聚类（Density-Based Spatial Clustering of Applications with Noise，DBSCAN）算法[18]、通过点排序识别聚类结构（Ordering Points To Identify the Clustering Structure，OPTICS）算法[19]、基于密度的聚类（DENsity-based CLUstEring，DENCLUE）算法[20]、密度峰值聚类（Clusterring by fast search and find of Density Peaks，DPC）算法[21]等。

密度聚类的优点在于不需要预先指定聚类数目，且对噪声数据的鲁棒性和非凸数据性能较好，缺点是大多数经典密度聚类需要设定超参数，并且对密度分布不均的数据聚类效果差。

1.2.4 基于网格的聚类

基于网格的聚类的核心思想是构建父级、子级的网格单元关系，形成多分辨率的网格数据结构，从而利用网格进行聚类。这种聚类首先将对象空间量化成有限数目的单元，从而形成网络结构；其次将数据对象集合映射到网格单元中，并计算每个网格单元的密度；最后根据数据对象数目阈值或者密度阈值判定每个单元是否是稠密单元，并将邻近的稠密单元聚类成簇。基于网格的聚类算法主要有统计信息网格（Statistical Information Grid，STING）算法[22]、小波聚类（Wave Cluster）算法[23]、CLIQUE（Clustering In QUEst）算法[24]、优化格（Optimal Grid-clustering，OptiGrid）算法[25]等。

由于网格聚类仅依赖于量化空间中每一维上的单元数目，其处理时间独立于样本对象的数目，因此网格聚类最大的优点就是处理速度快。但是网格聚类的缺点是精度取决于网格的大小，另外由于网格结构的局限性，网格聚类难以检测到数据的斜边界。

1.2.5 基于模型的聚类

基于模型的聚类其核心思想是事先给每一个聚类假定一个模型，然后寻找最能拟合该模型的数据集合。基于模型的方法既可以通过构建反映数据点空间分布的密度函数来实现聚类，也可以通过基于标准的统计量自动确定聚类数目，并考虑大数据噪声和离群点增强鲁棒性，从而实现聚类。基于模型的聚类主要分为统计学方法和神经网络方法两类[26]。统计学方法的模型聚类主要有COBWEB 算法[27]、期望最大化（Expectation-Maximum，EM）算法[28]等，神经网络方法的模型聚类主要有自组织映射（Self-organizing Maps，SOM）算法等。基于模型聚类的优缺点与选取的模型有关。

1.3 评价指标

聚类评价指标是指评判聚类结果有效性的质量评价方法。聚类有效性评价包括聚类质量、聚类算法与数据集的契合度以及划分的最佳聚类数目[29]。常用的聚类评价指标有外部指标、内部指标和相对指标[30]。

外部指标分为面向分类的指标和面向相似的指标：面向分类的指标包含精度、召回率、F度量三项；面向相似的指标包含蓝德（Rand）指数、杰卡德（Jaccard）指数、FM（Fowlkes and Mallows）指数3 项。内部指标有cophenetic 相关系数和Hubert’sΓ统计。相对指标有DB 指数、Dunn 指数两类[30]。

2 密度聚类方法

2.1 DBSCAN 算法

DBSCAN[18]算法最早在1996 年由Ester 等提出，是密度聚类的开创算法，也是最经典的密度聚类算法。该算法将具有足够高密度的区域划分为簇，并且可以在带有噪声的空间数据中发现任意形状的聚类。

DBSCAN 是基于一组邻域参数(ε,MinPts)来描述邻域的样本分布紧密程度。其中ε是某一样本的邻域距离阈值，描述了邻域的范围大小，MinPts是某一样本在距离为ε的邻域内样本对象个数的阈值，描述了样本邻域的密度大小。给定数据集D={x1,x2,…,xn}，有以下定义[18]：

（1）ε邻域：对于xj∈D，ε邻域包含了数据集D中与xj距离不大于ε的子样本集，即Nε={xi∈D|dist(xi,xj)≤ε}。

（2）核心对象：若|Ne(xj)|≥MinPts，那么xj就是核心对象。

（3）密度直达：若xj处于xi的邻域内，且xi是核心对象，那么xj由xi密度直达。

（4）密度可达：从核心对象xi出发，途径一系列核心对象，依次密度直达到xj，那么xj由xi密度可达。

（5）密度相连：若存在核心对象xk，使得xj和xi均由xk密度可达，就称xj和xi密度相连。

图1 给出了上述概念的示意图。给定MinPts=3，虚线范围是核心点的ε邻域，x1和x2是核心对象，x2由x1密度直达，x3由x1密度可达，x4与x3密度相连。

图1 DBSCAN 基本概念

基于以上概念，DBSCAN 将簇定义为密度相连的点的最大集合。簇内的所有样本密度相连，簇中核心对象的所有密度可达对象均在本簇内。因此DBSCAN 聚类的思想是，从任意一个核心对象开始，找到所有该核心对象密度可达的样本的集合，就形成了一个聚类簇，而不属于任何一簇的点则视为噪声点。具体算法如下：

该算法的优点：不用事先指定聚类个数；抗噪性能好；可识别任意形状的数据集。该算法的缺点：需主观选取全局参数(ε,MinPts)；对全局参数(ε,MinPts)初始化敏感；对多密度数据集处理效果不佳；难以区分不完全分离簇，会错误合并存在重叠的簇；运算量大，处理大规模数据集时收敛慢。

2.2 OPTICS 算法

虽然DBSCAN 能够根据全局参数(ε,MinPts)产生聚类，但是全局参数的选择依赖于用户的主观选择，类似超参数的设置通常依靠经验，往往无规律可循，而对于高维数据集的处理更是如此。并且，以DBSCAN 为代表的众多改进算法对全局参数值都极为敏感，聚类结果的好坏与参数的初始化息息相关。

OPTICS[19]是DBSCAN 的扩展，克服了使用全局参数的缺点，是一种参数次序结构上的密度聚类算法。该算法不直观地产生数据集聚类，而是输出簇排序。该排序是所有数据的线性表，代表了数据的聚类结构在密度上的次序，等价于从一个宽泛的参数设置范围得到的基于密度的聚类。该排序所对应的聚类结构包含了每个层级的聚类信息，因此可根据簇排序提取类似簇中心的聚类信息或者任意形状的聚类结构。

为了同时构建不同的聚类，需要按照特定的次序处理样本。这个次序选择的是关于最小ε值密度可达的样本，从而先完成高密度簇的聚类。因此，OPTICS 在DBSCAN 的基础上增加了两个新概念：

（1）核心距离ε′：对于xj∈D，xj的核心距离是使得xj邻域内至少包含MinPts个样本的最小ε值，即xj成为核心对象的最小邻域半径阈值。

（2）可达距离：从xj到xi的可达距离，是使xi从xj密度直达的最小半径值。其中xj必须是核心对象，因此xj到xi的可达距离为max{coredist(xj),dist(xi,xj)}。如果xj不是核心对象，那么xj到xi的可达距离没有定义。

图2 OPTICS 基本概念

xi可能由多个核心对象可达，对于不同的核心对象，就会有不同的可达距离。通常最小可达距离更有意义，它代表了连接到稠密簇的最短路径，并且可达距离越小，代表当前样本所处的空间密度越大。如果聚类时想朝着数据尽量稠密的空间进行扩张，那么就要选择可达距离尽量小的点。为此，OPTICS 用一个可达距离升序排列的有序种子队列（OrderSeeds）存储待扩张的点，以迅速定位稠密空间的数据。

OPTICS 算法分为两个阶段，第一阶段按照可达距离对样本进行排序，第二阶段提取聚类结构。

需注意OrderedFile 中第一个点的可达距离未定义，在此假设未定义的距离大于已定义的距离。

OPTICS 算法克服了密度聚类使用一组全局参数的缺点，不需要用户提供特定的密度阈值。但是OPTICS 算法不输出具体的簇信息，需要用户根据数据处理的需要从簇排序中提取聚类信息。另外，由于输出结果是簇排序，所以在处理稀疏点时具有一定的局限性。

2.3 DENCLUE 算法

DENCLUE[20]算法是一种基于密度分布函数的聚类算法，其理论基础是核密度估计。在DBSCAN和OPTICS 中，密度是通过计算核心对象的邻域范围内的数据点个数实现的。但是这种密度估计方式对邻域半径阈值ε极其敏感，尤其是在数据集密度分布变化大的情况下。

因此，DENCLUE 采用核密度估计的方法，对数据集的概率密度进行估计，以此规避ε带来的问题。设x1,…,xn是服从概率密度函数f的独立同分布样本，那么f的近似核函数密度为：

通常核函数使用标准高斯函数：

式中：ℎ为光滑参数的带宽，实际上是对数据集所处空间进行了网格单元划分。

在DENCLUE 中，簇中心由密度吸引点定义。若x*是密度函数的局部极大值，那么x*就被称作密度吸引点。为了排除平凡的局部极大值点，DENCLUE 设置了噪声阈值ξ，只有f^(x*)≥ξ的点才是有意义的密度吸引点，这些非平凡的密度吸引点就是簇中心。

确定簇中心后，其他数据点被密度吸引点吸引分配的过程就是聚类的过程，在此过程中DENCLUE 采用步进式爬山算法。DENCLUE 认为有意义的数据点x都是被密度吸引点x*吸引的，并且被估计的密度函数梯度所指导。如果存在一组点x0,x1,…,xn，使得x0=x，xk=x*，对于0＜i＜k，xi-1的梯度是在xi的方向上，那么点x就是被x*吸引的，那么就将x分配到以x*为中心的簇中。但是如果点x收敛于一个满足f^(x*)≤ξ的点，那么点x就是噪声点。

因此，DENCLUE 的一个簇代表一个密度吸引点的集合X和一个被吸引数据点的集合C，使得C中的每个对象都被分配到X中的一个密度吸引点，并且每对密度吸引点之间都存在一条密度不小于ξ的路径。通过被路径连接的多个密度吸引点，DENCLUE 可以发现任意形状的簇。

其主要原理归纳如下：

（1）每个数据点的影响可以用一个数学函数来形式化地模拟，它描述了样本点在邻域的影响。数据空间的全局密度函数即整体密度可以被模拟为所有数据点的影响函数总和。

（2）聚类可以通过密度吸引点得到，这里的密度吸引点是指全局密度函数的局部最大值。

（3）使用步进式爬山算法，将待分析的数据分配到密度吸引点代表的簇中。

主要算法步骤如下：

该算法有如下特点：

（1）核密度估计将噪声均匀分布到了输入数据，所以DENCLUE 对噪声有良好的鲁棒性；

（2）对高维数据任意形状的聚类给出了简洁的数学描述；

（3）使用了网格单元技术，并且使用了基于树的索引管理网格单元，使得该算法可以处理大规模数据集；

（4）相较于DBSCAN 等算法运算速度快，但是引入了参数ξ和ℎ。

2.4 DPC 算法

DPC[21]算法即密度峰值聚类算法，是2014 年在Science上提出的一种密度聚类算法，该算法基于两个基本假设：

（1）聚类中心被局部密度较低的近邻数据点包围；

（2）聚类中心与密度更高的数据点的距离足够远。

对于任意数据点xj∈D（D={x1,x2,…,xn}），需要计算它的局部密度ρj和与更高密度的最近点之间的距离δj。数据点xj的局部密度ρj定义为：

式中：χ为指示函数，当x＜0 时，χ(x)=1，否则χ(x)=0；dij为数据点xi和xj的距离；dc为截断距离。ρj本质上是xj截断邻域内数据点的个数，即邻域密度。δj的定义为：

图3 展示了数据点的分布，根据ρ和δ两个值，可以画出决策图如图4 所示。根据决策图中点的坐标不同，可以将数据点分为3 类：

图3 数据分布

图4 决策

（1）决策图右上部分的数据点ρ值大，δ值大，符合算法基本假设，属于簇中心；

（2）决策图左上部分数据点ρ值小，δ值大，该类数据局部密度小，距密度峰值点远，属于离群点；

（3）其他ρ值较大，δ值较小的点，属于普通簇内点。

定义γ=ρ*δ。用户可根据决策图直观得到密度峰值作为聚类中心，也可以选取前k个γ值最大的密度峰值作为簇中心，然后将剩余的点分配给最近的簇中心生成聚类[21]。

算法步骤可以归纳如下：

虽然DPC 算法简单，能够直观产生簇中心，自动发现剔除异常点，实现任意形状数据的高效聚类，但是也有较为明显的缺点：截断距离的选取依靠主观经验，另外在决策图上人为地选取聚类中心具有不可靠性，即使选取前k个γ值最大的密度峰值作为簇中心，也需要主观指定聚类中心个数。

3 应用与展望

现有文献对密度聚类的研究大多集中在算法改进性能提升等方面，而对算法的应用研究较少。目前密度聚类的应用主要集中在信号分选、文本挖掘、时空事件分析、图像聚类分割、异常值监测等方面。文献[31]利用DBSCAN 算法对出租车轨迹中的停靠点按时间段分块聚类，用于发现不同时间段的城市热点区域。文献[32]针对OPTICS 算法处理稀疏点上的局限性，提出一种结果重组织策略的OPTICSPlus 算法，在文本聚类上具有较好的效果。文献[33]利用DENCLUE 算法对事故多发点进行鉴别，可以在小样本情况下，凸显道路沿线的危险性。文献[34]提出了基于K 近邻算法（K-Nearest Neighbors，KNN）的快速密度峰值异常值检测算法，可实现对配电变压器的日常载荷数据异常检测。

随着大数据时代的发展，数据量爆炸式增长，样本更加高维、多元、复杂。现有的密度聚类算法计算量较高、密度参数选取依赖经验，难以处理大规模高维度数据。因此，实时高效、鲁棒性好、参数自适应且面向高维大数据的方向，是密度聚类算法未来的发展趋势。