💻 计算机科学

DISC: Dimension-Informed Clustering with Entropy Metric Warping and Attractor Basins

DISC 是一种基于图的新型聚类算法，它利用局部几何熵来扭曲亲和度度量并构建一个干净且破碎的图，随后通过深度引导流将该图划分为高纯度的吸引子盆地，并进行合并以在多种数据集上实现最先进的性能。

原作者： Qin Xu, Chenggang Xu, Hao Helen Zhang, Tian Xu

发布于 2026-10-21

📖 1 分钟阅读☕ 轻松阅读

原作者： Qin Xu, Chenggang Xu, Hao Helen Zhang, Tian Xu

原始论文采用 CC BY 4.0 许可（https://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

在现代数据科学的广袤版图中，研究人员经常面临这样一个问题：这感觉就像是在试图整理一个混乱的图书馆，书里没有标题，书架也是隐形的。他们处理的数据——图像、声音、传感器读数或文本——存在于一个高维空间中，这是一个比我们物理世界的三个维度拥有更多方向的数学领域。为了理解这些数据，科学家们依赖于一个被称为“流形假设”（manifold hypothesis）的概念，该假设表明，尽管数据点在高维空间中看起来是散乱的，但它们实际上沿着较低维度的形状（如线索或薄片）聚集在一起，隐藏在混沌之中。寻找这些隐藏群组的标准方法是构建一张连接图，将每个点与其最近的邻居联系起来。如果两个点距离很近，它们很可能属于同一个组。然而，这种传统方法将每个邻域视为同等对待，假设数据点周围的空间在各个方向上看起来都是一样的，就像一个平坦且均匀的地板。事实上，数据很少如此均匀；有些区域沿着单条线拉长，而另一些区域则向许多方向同时扩散。

Xgen AI 的一个研究团队开发了一种名为 DISC 的新方法，全称是“维度感知谱熵聚类”（Dimension-Informed Spectral-entropy Clustering），旨在通过让数据的局部形状来决定如何建立连接来解决这个问题。DISC 不再将每个邻域视为平坦、均匀的空间，而是测量数据在特定局部区域内向多少个方向扩散。他们将这种测量称为“局部谱熵”（local spectral entropy）。如果一个小邻域内的数据紧密排列在一条线上，其熵值就低；如果数据向许多方向扩散，其熵值就高。研究人员利用这种测量值来扭曲点与点之间的距离。当数据向许多方向扩散时，该方法会有效地缩短距离，使邻居感觉更近；当数据被限制在狭窄的路径中时，该方法会拉长距离，将点推开。这创造了一张更准确的数据结构图，其中只有当双方都强烈认同彼此属于同一组时，连接才会被信任。

该过程始于计算这些扭曲后的距离，然后应用一个被称为“互惠门”（reciprocity gate）的严格过滤器。这个门充当了一个双重检查系统：只有当两个点都认为彼此是强邻居时，它们之间的连接才会被保留。这一步移除了大量通常困扰聚类方法的“噪声”或错误连接，具体而言，与标准方法相比，它将不同组之间连接的权重削减了一半。然而，这种严格的过滤会导致地图变得破碎，分裂成许多小的、孤立的岛屿，而不是一个连续的网络。为了解决这个问题，研究人员并不试图寻求一个全局性的解决方案。相反，他们让每个点流向一个更深、更稳定的邻居，遵循最强的可用连接。这创造了被称为“吸引子盆地”（attractor basins）的小型、高度纯净的组，其中几乎每个点都属于同一个真实的类别。最后，研究人员使用一种精细的平均过程将这些小盆地合并在一起，以形成最终的簇。

这种方法在各种现实世界的数据集上都取得了惊人的结果。研究人员在十七个不同的数据集上测试了 DISC，涵盖了从手写数字和面部图像到语音录音、智能手机传感器数据以及文本文档的广泛范围。在这些测试中，新方法始终优于 K-Means、谱聚类和基于密度的方法等既有技术。在大多数数据集上，DISC 生成的簇与数据的真实类别匹配度显著提高。例如，在一个手写数字数据集中，该方法实现的纯度使得生成的组几乎能完美匹配实际的数字。更令人印象深刻的是，该方法在八个从未用于开发的数据库上也表现同样出色，证明了它不仅仅是在记忆训练数据，而是学习到了寻找结构的通用原则。该方法也非常高效，能够仅用 3.5 秒处理 70,000 个数据点，使其足以胜任大规模应用。

虽然该方法展现出了巨大的潜力，但研究人员也承认它并非适用于所有场景的完美方案。将这些小型、纯净的盆地合并为最终簇的过程有时会引入误差，特别是在处理具有复杂或不规则形状的数据集时，该方法偶尔会落后于其他先进技术。此外，该方法依赖于一个固定的邻域大小设置，如果该设置过小，方法可能会无法找到正确的结构。尽管存在这些局限性，其核心创新——即利用数据的局部几何结构来扭曲距离并创建更清晰、更可靠的地图——代表了向前迈出的重要一步。通过允许数据本身来定义连接的规则，而不是强加一个统一的结构，DISC 提供了一种更细致、更准确的方式来揭示组织我们复杂数字世界的隐藏模式。

技术摘要：DISC（基于熵度量变形与吸引子盆地的维度感知聚类）

问题陈述

基于图的聚类依赖于构建邻域图来划分数据，其运作基于流形假设，即高维数据集中在低维结构附近。然而，标准的构建方法通常对所有邻域进行统一处理，未能考虑到现实世界数据中变化的内在维度和局部几何结构。虽然某些方法能够适应局部密度，但它们经常忽略局部形状。因此，不同类别之间的边可能会合并簇，而类内缺失的边则可能分裂簇。挑战在于如何构建一个尊重局部几何（特别是数据在局部扩散的方向数量）的图，从而在不依赖联合表示学习的情况下，产生更清晰、更准确的划分。

方法论

所提出的方法 DISC（维度感知谱熵聚类）通过让局部几何决定边的可信度，通过四个阶段来解决这一问题：

1. 局部谱熵与度量变形

对于每个点 $x_i$ ，DISC 计算其 $k$ 个最近邻的局部协方差矩阵。这些协方差的特征值被归一化，形成一个概率向量，代表沿主方向的局部方差份额。局部谱熵 $H(x_i)$ 通过该向量的香农熵计算得出：
$H_i = -\sum_{t=1}^D q_{i,t} \ln q_{i,t}$
其中 $q_{i,t}$ 是归一化的特征值份额。该熵的指数 $\exp(H_i)$ 作为数据在局部占据的有效方向数。

该熵定义了一个共形度量变形 $g_i = H_i^{-2} I$ 。在此度量下，来自低熵（接近低维）邻域的距离会被拉长，而来自高熵（弥散）邻域的距离会被缩短。随后，利用这种变形后的距离，通过在邻域上进行高斯核归一化来计算方向亲和度 $p_{j|i}$ 。

2. 互惠门控 (Reciprocity Gate)

为了减少跨类噪声，DISC 应用了一个互惠门控。只有当两个端点都强烈支持一条边时，该边才会被保留。具体而言，仅当两个方向亲和度的最小值超过所有互为邻居的点对中此类最小值的中位数时，边权重才非零。这一过程实际上将跨类边权重减半（相对于标准的 $k$ -NN 图），但也导致了图变得稀疏且破碎。

3. 吸引子盆地划分 (Attractor Basin Partitioning)

由于经过门控处理后的图过于稀疏，无法进行全局谱划分，DISC 执行局部划分：

深度 (Depth)： 每个点的深度被定义为其经过门控后的度数除以其局部谱熵。
流 (Flow)： 每个点沿着其最强的门控边向具有更大深度的邻居移动。这个过程重复进行，直到到达一个吸引子（一个没有更深层门控邻居的点）。
盆地 (Basins)： 数据被划分为吸引子盆地，其中每个盆地都是以一个吸引子为根的树。观察表明，这些盆地具有极高的类纯度。
孤立点： 没有门控边的点被分配到其最近连接邻居的盆地中。

4. 盆地合并

最终的簇通过使用平均连锁法 (average linkage) 合并吸引子盆地来形成。盆地之间的亲和度是基于对称化的方向亲和度（包括被门控移除的对）计算的。算法迭代地合并具有最高平均亲和度的两两簇，直到达到所需的簇数 $c$ 。如果不再存在正向亲和度，则根据质心距离合并簇。

核心贡献

局部谱熵： 引入了一种度量，其中熵的指数代表了局部的有效方向数，用于对距离度量进行共形变形。
互惠门控： 一种通过仅保留相互认可的边来显著减少跨类边权重（约为标准 $k$ -NN 图的一半）的机制。
吸引子-盆地划分： 一种聚类策略，它避免了特征向量或模块度优化，而是利用门控图上的爬坡流来形成纯净的局部盆地，随后进行合并。
全面评估： 在涵盖图像、文本、语音和传感器数据的 17 个数据集（9 个基准数据集，8 个留出数据集）上进行了严格评估，证明了其在不针对开发数据过拟合情况下的鲁棒性。

结果

DISC 在 17 个数据集上与 K-Means、Ward 连锁法、谱聚类、DBSCAN、HDBSCAN 和 Leiden 社群检测进行了对比评估。

性能： 在调整兰德指数 (ARI) 上，DISC 在 14 个数据集上优于 K-Means；在准确率上，在 13 个数据集上优于 K-Means。在两个指标上，它在 15 个数据集上优于 Ward 连锁法和谱聚类。它在所有 17 个数据集上都优于 DBSCAN 和 HDBSCAN，且具有统计学显著性增益 ( $p \le 10^{-10}$ )。
泛化能力： 性能提升在 8 个留出数据集（从未用于开发）上保持一致，表明该方法并未过拟合。
与 Leiden 的比较： DISC 在统计上与 Leiden 社群检测处于同一水平，两者共享最佳的平均 ARI 排名。DISC 在具有小规模类别的数据集（如 Olivetti）和特定的留出集上表现出色，而 Leiden 在深度图像特征（CIFAR-10）和 Satimage 上表现更好。
可扩展性： DISC 扩展效率高，处理 70,000 个 MNIST 点仅需 3.5 秒，其运行时间缩放指数约为 1.5，与 Leiden 相当，且明显快于谱聚类。
内部指标： 虽然 DISC 实现了很高的外部准确率，但其轮廓系数 (Silhouette coefficients) 低于基于密度的算法（DBSCAN/HDBSCAN）。作者指出这是因为轮廓系数奖励紧凑、凸形的形状，而 DISC 捕捉的是弯曲或拉长的类别结构。

意义与主张

论文声称 DISC 提供了一种稳健且具备几何感知的传统图聚类替代方案。通过利用局部谱熵来变形度量并采用互惠门控，DISC 构建了一个“干净”的图，最大限度地减少了跨类连接。随后的吸引子-盆地方法允许在无需全局特征分解或学习表示的情况下实现有效的聚类。

作者强调，DISC 是为固定数据表示（例如 ResNet 特征）设计的，而非用于联合表示学习。该方法在未见数据集上的泛化能力以及与 Leiden 的统计等效性表明，它是一个强大的通用聚类工具，能有效利用局部维度来提高簇的纯度和分离度。主要提到的局限性是，最后的合并步骤（平均连锁法）可能会在特定数据集上引入误差，这表明改进合并标准可能是未来的一个研究方向。