几种常用的基于密度的聚类算法

这里介绍的几种常用基于密度聚类算法包括：DBSCAN、OPTICS、DENCLUE。

1. DBSCAN

DBSCAN (Density Based Spatial Clustering of Application with Noise)[1] 算法的核心思想是，对于一个簇(cluster)内的点，要求在给定半径 ε 的邻域包含的点数——也称为基数(cardinality)——必须不小于一个最小值MInPts，这些满足要求点成为“核心点”(core points)。所以这里一个点的密度就是以其关于 ε 和 MInPts 的基数来代表的。而为了让每个簇中的那些“边缘点”(border points)——不满足最小值要求但在核心点的邻域范围内的点——不被忽略掉，算法递进地给出了"密度直达"(directly density-reachable)、“密度可达”(density-reachable)、“密度相连”(density-connected)的概念，所有彼此之间关于给定参数 ε 和 MInPts 密度相连的数据点组成一个簇，没有包含在任何一个簇内的点就属于噪声(noise)。其实在具体实现时时不必在意所谓“密度相连”的概念的，只需要迭代地将“核心点”邻域中的所有点——即密度直达的点——包含进来即可，这样最终形成的簇其内的所有点必定是密度相连的。

对于DBSCAN中的两个全局参数 ε 和 MInPts，可以通过一个参数 K 来启发式地得到它们。数据集中一个点的第 K 邻近点与它的距离称为 k_dist，当我们画出所有点排序后的 k_dist 图之后，可以确定一个”界限“(threshold)。在界限之下的所有点就是核心点，界限值就是所需的 ε 值，K 值就是 MInPts 值。界限一般在 k_dist 突然变化的地方，或者根据先验知识确定(事先知道数据集中噪声的比例)。

Tips

使用统计的方法，通过统计 k_dist 变化率 Δk_dist 可以形成一种自动找出 k_dist 突变处的方法。

2. OPTICS

OPTICS (Ordering Points To Identify the Clustering Structure)[2] 不直接提供数据集的聚类结果，而是产生一个关于数据集的“増广排序”(augmented ordering)，它反映了数据基于密度的聚类结构。原文中介绍说道OPTICS的工作原理就像是一种扩展的DBSCAN算法。在算法过程中会考虑在“生成距离”(generating distance) ε 之下的任何距离参数 ε_i，但这个过程不会生成点的所属簇，而是保存对象的处理顺序和重要信息。重要的信息包括两个：核心距离(core-distance)和可达距离(reachability-distance)。核心距离 core_distance_{ε,MinPts}(p) 就是，数据点 p 在给定的生成距离 ε 范围与一个临近点的距离，且是能让 p 成为核心点的最短距离 ε'（若 ε' 超过了 ε，p 不能称为核心点，那么 p 的核心距离就失去意义）。可达距离ReachDist_ε_MinPts(p,o) 是关于核心点来说的，数据点 p 在 ε 范围内与某一核心点 o 之间的距离，且它不能小于 o 的核心距离（若点 p 的 ε 范围没有核心点，则它不存在关于任何点的可达距离）。

在生成了数据集相对于 ε 和 MInPts 的增广聚类排序之后，我们可以从中提取关于 ε'<ε 和 MInPts 的任何基于密度的聚类结果，只需要根据核心距离和可达距离通过简单的“扫描”得到的排序序列来标记数据点的所属簇即可。

Tips

生成增广的聚类排序会保存两种信息——核心距离和可达距离。但对于从中提取类似 DBSCAN 的结果而言，通过对提取程序的一些调整，我们只需要可达距离这一种信息即可实现目的。

3. DENCLUE

DENCLUE (DENsity based CLUstEring)[3] 引入影响函数和密度函数(influence and density function)的概念用以进行基于密度的聚类。空间中的任一点密度是所有数据点在此点产生影响的叠加，一般采用高斯影响函数进行计算，这里需要给定算法的第一个参数 σ，一般称为平滑参数(smoothing parameter)。算法又定义了密度吸引点(density attractor)的概念用以进行聚类操作。密度吸引点就是密度函数中的那些局部最大值点，在算法中可以通过梯度爬山法(climb hill)来得到它们的近似位置，这里需要给定算法的第二个参数，步进长度 δ，也称为收敛速率(controlling convergence speed)。由这些吸引点可以给出从“中心限定簇”(center-defined cluster)到“任意形状簇”(arbitrary-shape cluster)的定义。中心限定簇针对每个吸引中心而言，指的是某吸引中心 x* 的密度大于给定的密度阈值 ξ，那么由 x* 所吸引的所有数据点构成一个中心限定簇。任意形状簇在前者的基础上延伸得到，只要两个吸引 x1* 、x2* 中心之间存在一条路径，该路径上的密度也大于 ξ，那么由x1* 、x2* 所定义的中心限定簇合并在同一簇内，这样构成的簇就可以任意形状的。这里的阈值 ξ 就是算法需要的第三个参数，也称为噪声阈值(noise threshold)。

算法实现过程中需要一些处理技巧。首先是计算密度函数，显然全局密度函数的计算量随着数据量的增加是巨大的(O(n^2))，所以我们可以根据高斯函数的 3σ 原则来计算局部密度函数值(local density function)，即数据空间中某点的局部密度等于它的 3σ 范围内数据点的影响叠加。然后为了提高搜索效率，我们可以对数据空间分块并建立索引，如B+树、R树等。

在缺少先验知识的情况下，设置算法的三个参数(σ/δ/ξ)是一件困难的事情，而且三个参数之间是互相牵制的，这无疑增大的参数调整的复杂度。另一个问题在于数据过滤操作，这一操作是DENCLUE算法中多出的一步操作。由于密度阈值 ξ 只针对密度吸引点，那么在原始数据集上的产生的聚类中不能避免地会包含噪声，这回造成聚类结果噪声率较低的假象，所以需要对数据提前过滤，去除明显的噪声数据。过滤实在数据分块的基础上进行的，设定一个过滤阈值 ξ_c ，视分块中数据量小于 ξ_c 的数据点为噪声，过滤即让该数据分块为空，之后使用过滤后的数据进行聚类。这里的ξ_c原文里的建议值是 ξ/2/ndims ， ndims 为数据维度。但是在实验中发现该建议值并不一定合适，实际上这里又产生了一个参数，需要我们针对数据集的特点进行设定。

DENCLUE在t7_10k.dat上的聚类结果如下，

有过滤操作

无有过滤操作

DENCLUE2.0 改进的地方在爬山法的方式。它不在采用原始的定步长爬山，而是给出了一种自适应的变步长爬山方式，可以更快的接近吸引点即山顶的位置，并且在理论可以上无限接近吸引点。正因为其会无限度地接近吸引点，所以我们需要给定其停止的条件。直白地说就是，当爬上过程中密度上升不十分明显时，可以停止继续爬山，表达式为 (f(x)l-f(x){l-1})/f(x)_l<=γ， γ 不需给太小，这样反而会让迭代步骤增加，加大计算量，同时也使爬山终点太过集中于各吸引点附近，不利于簇的合并，容易形成更多分离的簇，本次试验中的参数为 h=0.01985, γ=0.01, ξ=38, ξ_c=6，无过滤操作对应 ξ_c=0。

DENCLUE2.0在t7_10k.dat上的聚类结果如下，

有过滤操作(聚类数=9，噪声占比=7.410%)

无有过滤操作(聚类数=12,噪声占比=2.070%)

Tips

通过观察DENLCUE2.0中爬山终点的聚集过程得到启发，也许可以直接利用爬山终点提取聚类结果，由此节省许多时间与空间成本。

数据

实验数据 7_10k.dat 为 Chameleon 论文[5]中所给的DS3数据，数据密度分布图如下（h=0.01985）：

参考

1. Ester M, Kriegel H-P, Sander J, Xu X. A density based algorithm for discovering clusters in large spatial databases with noise[C]. Proceedings of the 2nd ACM In ternational Conference on Knowledge Discovery and Data Mining (KDD), 1996:226-231. https://dl.acm.org/doi/10.5555/3001460.3001507

2. Ankerst M, Breunig MM, Kriegel H-P, Sander J. OPTICS: ordering points to identify the clustering structure[C]. Proceedings of the ACM International Conference on Management of Data (SIGMOD), 1999:49–60. DOI:https://doi.org/10.1145/304181.304187

3. Hinneburg A, Keim DA. An efficient approach to clustering in large multimedia databases with noise[C]. Proceedings of the 4th ACM International Conference on Knowledge Discovery and Data Mining (KDD), 1998:58-65. https://dl.acm.org/doi/10.5555/3000292.3000302

4. Campello, RJGB, Kröger, P, Sander, J, Zimek, A. Density‐based clustering[J]. WIREs Data Mining Knowl Discov. 2020, 10(2):e1343. DOI:https://doi.org/10.1002/widm.1343

5. George Karypis, Eui-Hong (Sam) Han, and Vipin Kumar. 1999. Chameleon: Hierarchical Clustering Using Dynamic Modeling[J]. Computer, 1999, 32(8):68–75. DOI:https://doi.org/10.1109/2.781637