摘要—找到合适的密度函数对于基于密度的聚类算法（如 DBSCAN 和 DPC）至关重要。这些算法中通常使用与单位 d 维欧几里得球的指示函数相对应的朴素密度。这种密度会因在复杂数据集中捕获局部特征而受到影响。为了解决这个问题，我们提出了一种新的核扩散密度函数，它可以适应不同的局部分布特征和平滑度的数据。此外，我们开发了一个可以在线性时间和空间中有效计算的代理项，并证明它与核扩散密度函数渐近等效。在基准和大规模人脸图像数据集上进行的大量经验实验表明，所提出的方法不仅比经典的基于密度的聚类算法有了显着改进，而且大大优于最先进的人脸聚类方法。

1 简介

基于密度的聚类算法现在广泛用于各种应用，包括高能物理（Tramacere & Vecchio，2012；Rovere 等，2020）、材料科学（Marquis 等，2019；Reza 等， 2007)、社交网络分析 (Shi et al., 2014; Khatoon & Banu, 2019) 到分子生物学 (Cao et al., 2017; Ziegler et al., 2020)。在这些算法中，数据点被划分为集群，这些集群被认为是相对于潜在概率密度或类似参考函数而言足够高或局部高密度的区域。我们在整篇论文中都称它们为密度函数。这些技术对从业者很有吸引力，因为它们的非参数特征可以灵活地发现具有任意形状的集群，而经典方法如 k-means 和 k-medoids (Friedman et al., 2001) 只能检测凸（例如，球形）簇。在基于密度的聚类方面的开创性工作包括 DBSCAN (Ester et al., 1996) 和 DPC (Rodriguez & Laio, 2014)，以及许多其他 (Ankerst et al., 1999; Cuevas et al., 2001; Comaniciu & Meer，2002；Hinneburg 和 Gabriel，2007；Stuetzle，2003）。

大多数基于密度的聚类算法隐含地识别聚类中心，并通过与附近较高密度点的连接将剩余点分配给聚类。要继续使用这些方法，它需要一个密度函数，它通常是对潜在真实概率密度或其某些变体的估计。例如，一个流行的选择是朴素密度函数，它通过简单地计算每个 x 的 ε-邻域中覆盖的数据点的数量来执行。请注意，这样的密度不适用于不同的分布区域。具有挑战性的场景之一是数据中的集群具有不同的局部特征，例如大小、高度、分布和平滑度。因此，得到的密度函数倾向于使数据分布中的波峰和波谷变平，从而导致对聚类数量的低估（见图 1）。已经提出了 DBSCAN 和 DPC 的许多启发式变体来放大局部特征，从而使聚类任务更容易（Campello et al., 2013; Chen et al., 2018; Ertöz et al., 2003; Zhu et al., 2016 ）。这些方法中的大多数可以被视为对朴素密度函数的某些变换执行聚类。但是，如果朴素密度函数本身首先存在很大问题，那么这些方法将变得不那么有效。

此外，即使我们应用自适应替代方法来修改经典密度函数，通常使用的线性核密度估计器 (KDE) 也存在其他有争议的问题。它经常遭受严重的边界偏差（Marron & Ruppert, 1994），并且被认为计算成本很高。这些现象阻碍了经典密度函数的实用性和可靠性，特别是对于大规模和复杂的聚类任务。

为了克服基于密度的聚类算法中的这些问题，在本文中，我们提出了一种通用方法来构建所谓的核扩散密度函数来代替经典的密度函数。关键思想是从具有所需局部自适应特性的用户指定的二元核构建密度。我们没有使用朴素密度函数及其变体，而是利用二元核来推导转移概率。这种转移概率引发了扩散过程，该转移概率允许有限且平稳的分布。这种限制分布可作为一种似是而非的密度函数，用于减少误差的聚类。

为了克服基于密度的聚类算法中的这些问题，在本文中，我们提出了一种通用方法来构建所谓的核扩散密度函数来代替经典的密度函数。关键思想是从具有所需局部自适应特性的用户指定的二元核构建密度。我们没有使用朴素密度函数及其变体，而是利用二元核来推导转移概率。这种转移概率引发了扩散过程，该转移概率允许有限且平稳的分布。这种限制分布可作为一种似是而非的密度函数，用于减少误差的聚类。

在这个框架下，我们提供了对称和非对称二元核的例子来构建核扩散密度函数，它可以解决聚类复杂和局部变化的数据。我们将由此产生的适应 DBSCAN 和 DPC 算法应用于广泛不同的经验数据集，并在这些分析中显示出显着的改进。本文的主要贡献总结如下：

• 我们引入新的二元核函数并构建相关的核扩散过程。基于扩散过程，我们提出了一种核扩散密度函数来适应基于密度的聚类算法，如 DBSACN 和 DPC，在存在不同局部特征的情况下达到准确性。

• 我们推导出一个计算效率更高的替代物，并通过分析表明它与所提出的核扩散密度函数是渐近等效的。

• 通过大量实验，我们证明了核扩散密度函数在应用于 DBSCAN 和 DPC 时优于朴素密度函数及其变体，并表明它在人脸聚类任务上优于最先进的基于 GCN 的方法。

2 相关工作

基于密度的聚类 有大量关于采用基于密度的聚类算法来解决数据中不同聚类的巨大变化的文献。 DPC 本身就是 DBSCAN 的一种改进，因为它不仅通过最高密度值确定聚类中心，而且还考虑到它们之间的距离，因此在复杂的聚类任务中通常具有更好的性能。其他尝试包括重新调整数据以具有相对参考度量而不是 KDE (Zhu et al., 2016; Chen et al., 2018)，以及使用两点之间的共享最近邻数来代替几何距离 (Ertöz等人，2003）。

扩散图扩散图技术（Coifman et al., 2005; Coifman & Lafon, 2006）根据数据的基本几何结构对数据进行多尺度组织。它使用局部相似性度量来创建数据的扩散过程，该过程沿时间 t 整合不同尺度的局部几何。一般来说，diffusion会将数据分割成小t中的几个较小的簇，并将数据分组为大t的一个簇。在精心选择的时间 t 应用特征函数会导致数据的良好宏观表示，这在降维和谱聚类中很有用（Nadler 等人，2005 年）。

人脸聚类人脸聚类作为机器学习中的一个重要应用已经被广泛研究。传统算法包括 k-means、层次聚类 (Sibson, 1973) 和 ARO (Otto et al., 2017)。最近的许多工作都利用了监督信息和 GCN 模型，与传统算法相比取得了令人瞩目的改进。仅举几例，CDP (Zhan et al., 2018) 提出聚合不同模型提取的特征； L-GCN (Wang et al., 2019) 预测实例枢轴子图中的链接； LTC (Yang et al., 2019) 生成一系列子图作为提议，并在其上检测人脸簇；和 GCN(V+E) (Yang et al., 2020) 通过 GCN 学习置信度和连通性。在本文中，我们证明了所提出的具有核扩散的基于密度的聚类算法，作为一种通用的聚类方法，甚至优于专门为人脸聚类设计的这些最先进的方法。

3 预备知识 3.1 符号

让数据集 D = {x1, . . . , xn} ⊂ Rd 是从分布测量 F 中抽取的 n i.i.d 个样本，在 Rd 上具有密度 f。令 Fn 表示相对于 D 测量的相应经验分布，

即，Fn(A) = 1 􏰁n 1A(xi)，其中 1A(·) 表示集合 A 的指示函数。我们写为 ||u||当 n i=1 时，向量 u 的欧几里得范数。令 B(x, ε) 和 Vd 分别表示以 x 为中心的 d 维 ε 球和单位球 B(0, 1) 的体积。令 Nk(x) 表示数据集 D 中点 x 的 k 最近邻的集合。

3.2 密度函数

基于密度的算法通过在由 ρ 表示的密度函数中指定和分割高值区域来执行聚类。通常，我们计算每个 ρ(xi)，然后识别具有（局部）最高值的聚类中心。许多流行的算法，如 DBSCAN 和 DPC，采用以下朴素密度函数：

朴素密度函数 ρnaive 实际上是对精心选择的 ε 的 f 的经验估计。很容易观察到，为了聚类的目的，我们只关心 ρnaive(x) 直到一个归一化常数，这使得它简单地等同于计算 ε-ball 中围绕 x 的数据点的总数。

在实践中，数据分布可能非常复杂，并且包含难以检测的各种局部特征。对于所有 x 具有相同半径 ε 的 (1) 中的朴素密度通常遭受不令人满意的经验性能，例如，无法识别具有较少数据点的小集群。缓解此问题的一种可能方法是通过转换为以下局部对比度 (LC) 函数 (Chen et al., 2018)：

通过这种方式，ρLC 将每个数据点的密度与其 k 近邻进行比较。为了看到 LC 的好处，让我们将 x 视为一个聚类中心。经过局部对比后，无论该簇的大小如何，ρLC(x) 都可能达到 k 的值。

然而，像 ρLC 这样的密度函数仍然高度依赖于 ρnaive 的基础性能。这限制了它们在具有挑战性的局部特征的聚类数据中的应用。

4 方法论

在本节中，我们提出了一种基于核扩散密度函数概念的新型基于密度的聚类算法。为此，我们将引入一个核扩散密度函数，它考虑了局部适应性，非常适合聚类目的。我们提供了有关如何从由二元核引起的扩散过程中导出此密度函数的详细信息。我们还提供了一个计算效率更高的代理密度函数。

4.1 扩散过程和核扩散密度 考虑二元核函数 k : D × D → R+，这样：

• k(x, y) 是半正定的，即 k(x, y) ≥ 0。

• k(x, y) 是关于 x 和 y 的 Fn 可积的。

我们将 d(x) = n 􏰍 k(x, y)dFn(y) 定义为 x 处体积的局部度量并定义

容易看出 p(x, y) 满足守恒性质 n 􏰍

p(x, y) 可以看作是在数据集上从点 x 到点 y 的随机游走的概率，它在 D 上诱导出一条具有 n × n 转移矩阵 P = [p(x, y)] 的马尔可夫链。这种技术在各种应用中都是标准的，称为归一化图拉普拉斯构造。例如，我们可以将 D 视为一个图，将 L = I - P 视为归一化图拉普拉斯算子，将 d(x) 视为归一化因子。

对于 t ≥ 0，在 t 个时间步长内从 x 过渡到 y 的概率由 Pt 给出，即 P 的 t 次方。及时向前运行马尔可夫链，我们观察不同尺度的数据集，即扩散在 D 上处理 Xt。设 ρ(x, t): D × R+ → R+ 为相关概率密度，由以下具有初始条件的二阶微分方程控制：

其中 φ0(x) 是时间 t = 0 时的概率密度。在实践中，我们可以使用任何有效的 φ0(x) 选择，

例如密度均匀。

为了给出扩散过程的一个明确的例子，考虑一个 k 的子类，即各向同性核，其中 k(x, y) = K(||x − y||2/h) 对于某个函数 K : R → R+。在这里，我们可以将 h 双重解释为推断局部信息的尺度参数和随机游走跳跃的时间步长 h = Δt。然后我们可以将 forward Chapman-KolmogorovoperatorTF 定义为

注意，TF 是时间 t=h 时的数据分布，因此可以看作是左乘转移矩阵 P 的连续模拟。令 h → 0，随机游走收敛到一个连续扩散过程，概率密度在 t 中连续演化。在这种情况下，我们可以将（4）中的二阶微分方程明确写为：

∂ ρ(x,t) = lim ρ^(x,t+h)−ρ(x,t) = lim TF −Iρ(x,t), (5) ∂th h→0 h h→0 h

其中 Lh = limh→0 (TF − I)/h 是该过程的常规无穷小生成器。现在我们准备介绍我们的核扩散密度函数。

定义 1. (核扩散密度函数) 假设 P 诱导的马尔可夫链是遍历的，我们将核扩散密度函数定义为扩散过程 Xt 的极限概率密度，即

ρKD(x)= lim ρ(x,t)。 (6) t→∞

我们提供了一些直觉，说明为什么 ρKD 作为有效的聚类密度函数。随着 t 值的增加，扩散过程 Xt 在增加的尺度上揭示了数据分布 F 的几何结构（例如高密度区域）。要看到这一点，请注意转移概率 P 反映了数据点之间的连通性。我们可以将集群解释为在转换期间停留在该区域的概率很高的区域。由于所涉及的数据点密集且高度连接，因此沿着基础几何结构的路径的概率随着 t 的增加而增加。因此，路径与短而高概率的跳跃一起形成。而不遵循这种结构的路径会形成长而低概率的跳跃，这会降低路径的整体概率。

同时，为了防止所有数据的扩散过程在 t → ∞ 时将所有数据分组到一个大簇中，我们可以使用某些专注于局部自适应性的复杂形式的 k(x,y)。这将有助于减缓扩散并引导过程逐渐朝着正确的几何结构方向发展。因此，它们在放大几何结构和识别局部特征信号之间取得了平衡。

4.2 本地自适应内核

为了解决核扩散密度函数的局部适应性，我们提出了以下两个二元核。它们都是最常用的经典内核的非常简单的变体。

对称高斯核：

这里 h 和 k 是超参数。请注意，在这种情况下 k(x, y) 是不对称的，因为 y ∈ Nk (x) 并不意味着 x ∈ Nk(y)。

(7) 和 (8) 中定义的双变量内核分别只是经典高斯内核和 ε- 邻域或 k-最近邻内核的组合。通过这些简单的组合，我们在局部区域截断高斯核，每个点 y 对构建密度函数 ρKD(x) 的贡献不仅取决于距离 ||y - x||还有关于 x 周围的局部几何结构。因此，新内核在不同的 x 处具有自适应性，这有望导致针对局部特征的更好的聚类性能。我们注意到非对称高斯核考虑了每个 x 周围的变化邻域，因此与对称高斯核相比更具适应性。

虽然这里我们只提供了两个局部自适应内核的例子，但在这个框架下可以很容易地以类似的精神创建其他选项，例如，将高斯内核更改为其他内核或将 ε-neighbourhood (k-nearest neighbours) 内核更改为其他内核局部截断函数。一旦确定了 k(x, y)，我们就可以推导出相应的密度函数 ρKD。接下来，我们只需要简单地应用任何基于 ρKD 的密度聚类过程，如 DPC 或 DBSCAN，而不是简单的密度函数 ρnaive。

在第 5 节中，我们使用上述两个局部自适应内核评估了所提出的内核扩散密度函数的经验性能。它们优于现有的基于密度的算法和其他最先进的方法。

4.3 快速核扩散密度

核扩散密度函数 ρKD 可以计算为由转移矩阵 P 引起的马尔可夫链的平稳分布。在数值上，我们可以通过迭代右乘 P 与 ρ(x, t) 直到收敛，或者对 P 应用 QR 分解来解决它。这些方法在计算成本方面很昂贵，尤其是当样本量 n 很大时。

为了解决这个问题，我们提出了以下计算效率更高的 ρKD(x) 替代项。

定义 2. (快速核扩散密度函数) 设 p(y, x) 为从点 y 到点 x 的转移概率，如等式 (3) 中所定义。我们将快速核扩散密度函数定义为

很简单，ρFKD 可以在线性时间和内存空间中获得，因为我们只需要

计算矩阵 P 的列平均值。

在这里，我们表明 ρFKD 不仅计算效率高，而且适用于检测局部特征。这可以通过以下定理 1 来说明。考虑一个特殊情况，即 k(x,y) = 1B(x,ε)(y)。那么很容易验证

其中 Cd = nεdVd 是归一化常数。通过这种方式，我们在这个特殊示例中建立了 ρFKD 和朴素密度函数 ρnaive 之间的联系。

定理 1. 考虑上述特殊情况 k(x, y) = 1B(x,ε)(y)。此外，假设数据集 D = {x1 , ..., xn } 可以分成 m 个不相交的集群：即 X = D1 􏰎 ... Dm 并且对于每个 x ∈ D, B(x, ε)包含与 x 属于同一簇的数据点。将 ρ ̄j = 1 􏰁 ρFKD(x) 表示为簇 j 中的平均密度。我们有

定理 1 表明，无论集群大小和其他局部特征如何，每个集群中的平均 ρFKD 都是相同的。这表明 ρFKD 提高了小簇的密度，这对于找到小簇的密度峰值至关重要。

以前我们声称 ρFKD 是核扩散密度 ρKD 的替代物。接下来，我们想从渐近的角度揭示这两个密度函数之间的关系。为了继续，我们需要以下假设。

假设 1. 存在某个正常数 c < 1，使得 ρFKD(x) ≤ c 对于每个 x ∈ D 均成立。

这是一个非常温和的假设，因为它始终认为 ρFKD(x) < 1，并且数据集上的 ρFKD(x) 的平均值是 􏰍 提出以下定理来表征 ρFKD 和 ρKD 之间的一致接近性。

ρFKD(x)dFn(x) = 1/n，随着 n → ∞ 消失。现在我们准备好了

定理 2。假设假设 1 成立并且由核 k(x,y) 诱导的马尔可夫链是遍历的。我们有

定理 2 意味着当 n 足够大时，ρFKD 一致地逼近 ρKD。所以我们在实践中用它来代替 ρKD 是安全的。我们在第 5 节中的数值实验也验证了这一结果。

在本节中，我们根据 ρnaive 经验评估提出的核扩散密度函数

和 ρLC 在基于密度的聚类算法中，并将它们与其他最先进的方法进行比较。我们将 ρsym 和 ρsym 分别表示为具有对称高斯核的核扩散密度函数及其快速替代函数。类似地，我们将 ρKD 和 ρFKD 分别表示为具有非对称高斯核的两个密度函数。我们在广泛的数据集上检查它们的性能。聚类结果以 Pairwise F-score (Banerjee et al., 2005) 和 BCubed F-score (Amigó et al., 2009) 衡量。

参数 ε（球的半径，在 ρnaive、ρLC、ρsym 和 ρsym 中使用），k（最近的不对称 asym KD FKD 的数量ρLC、ρKD 和 ρFKD 中使用的邻居）通过在参数空间中的合适范围内搜索来调整，并且 h（用于 ρsym、ρsym、ρasym 和 ρasym 的高斯核的带宽）固定为 0.5。

5.1 基准数据集的性能

我们现在讨论来自 UCI 存储库的 13 个基准数据集（~100 到 5,000 个数据点）的性能。元数据总结在附录中。

如表 1 所示，就 KD KD 聚类精度而言，ρsym 和 ρasym 均优于 ρnaive 和 ρLC。所提出的具有非对称高斯核的核扩散密度函数 ρasym 在解析上具有更好的局部自适应性，在大多数 KD 数据集上取得了最佳结果，并且大大优于 ρnaive 和 ρLC。值得注意的是，两个快速替代物 ρsym 和 ρasym 与它们的原始对应物 ρsym 和 asym FKD FKD KD ρKD 取得了可比的结果。在附录中，对于应用于 DBSCAN 的同一组密度函数，观察到了类似的结果。

5.2 人脸图像数据集的性能

近年来，根据潜在身份对人脸图像进行聚类成为一项重要应用。从某种意义上说，人脸图像数据集通常包含数千个身份，对应于数千个集群，这是一个挑战。同时，每个身份（集群）的图像数量也有很大差异，对应于集群大小的变化。我们评估了该方法在两个流行的人脸图像数据集上的性能：emore_200k (Zhan et al., 2018) 和 MS1M (Guo et al., 2016)。

emore_200k。该数据集包含 2,577 个身份和 200,000 张图像，遵循 Zhan 等人的协议。 （2018 年）。结果总结在表 2 中。提出的扩散密度函数应用于 DPC，并与 k-means、HAC (Sibson, 1973)、ARO (Otto et al., 2017) 和 CDP (Zhan et al. , 2018)。同样，我们观察到提出的密度函数比 ρnaive 和 ρLC 有了显着改进。还值得指出的是，基于密度的聚类与提出的核扩散密度函数也大大优于 CDP 等最先进的方法。

MS1M。该数据集包含 8,573 个身份和大约 584,000 张图像，遵循 Yang 等人的协议。 （2020 年）。我们在表 3 中报告了聚类性能的结果。图 2 绘制了不同密度函数（应用于 DPC）的精度与召回曲线。在表 3 中，提出的核扩散密度函数优于 ρnaive 和 ρLC .请注意，基于 GCN 的方法，如 L-GCN (Wang et al., 2019)、LTC (Yang et al., 2019) 和 GCN (V+E) (Yang et al., 2020) 通常可以实现更好的聚类由于它们的监督性质，其性能优于无监督方法。然而，令人鼓舞的是，所提出的核扩散方法虽然也是无监督的聚类方法，但明显优于基于 GCN 的方法。

5.3 敏感性分析

接下来，我们检查所提出的核扩散密度函数对超参数的敏感性，并将其与 ρnaive 和 ρLC 进行比较。结果是通过在 emore_200k 和 MS1M 上进行的大量实验获得的，如图 3 所示。我们可以看到，当我们改变 ε 的值时，ρsym 的聚类性能比 ρnaive 和 ρLC 稳定得多。虽然 ρasym 对 KD sym asym KD 参数 k 是稳健的，但 ρKD 和 ρKD 对参数 h 都非常稳健。

5.4 计算成本

我们在 MS1M 上进行了一系列实验，以证明快速替代 ρFKD 在时间和空间方面的计算效率。通过从 MS1M 收集的不同百分位水平的子采样数据，我们运行核扩散密度 ρKD 和快速替代 ρFKD。从图 4 可以看出，ρKD 的运行时间和内存使用量随着样本量的增加而显着增加。而 ρFKD 保留了非常低的计算成本。这表明 ρFKD 实现了出色的计算效率，在实践中应该受到青睐。

六，结论

基于密度的聚类对机器学习和数据挖掘有着深远的影响。然而，基础朴素密度函数会检测到不同的局部特征，从而导致聚类中的额外错误。我们提出了一组基于核扩散过程的新密度函数来解决这个问题，它适应不同局部分布特征的密度区域。我们证明，与经典版本和其他最先进的方法相比，采用所提出方法的 DBSCAN 和 DPC 提高了聚类性能。