[论文] Chamfer-Linkage 用于层次凝聚聚类

Source: arXiv - 2602.10444v1

概述

层次聚合聚类（Hierarchical Agglomerative Clustering，HAC）是分组数据点的常用工具，但其性能取决于决定合并哪些簇的链接函数。新论文提出了Chamfer‑linkage，一种基于 Chamfer 距离（点云处理中的常用度量）的链接方式。作者展示了这一简单改动在大量真实数据集上能够产生更可靠的聚类结果，同时保持经典的 (O(n^2)) 运行时间。

关键贡献

• Chamfer‑linkage 定义 – 将 Chamfer 距离适配用于衡量簇间相似度，保留经典链接方法丢失的细粒度几何信息。
• 理论保证 – 证明使用 Chamfer‑linkage 的层次聚类（HAC）可以在与传统链接相同的二次时间内实现，无需使用复杂的数据结构。
• 理想的表示属性 – 表明 Chamfer‑linkage 满足多个“概念表示”公理（例如单调性、对离群点的稳定性），而许多经典链接方法则违背这些公理。
• 广泛的实证评估 – 在来自图像检索、文本聚类和网络分析的数十个数据集上，将 Chamfer‑linkage 与单链接、平均链接、完全链接以及 Ward 链接进行基准比较，始终在轮廓系数、调整 Rand 指数等指标上获得更高的聚类质量。
• 即插即用的可用性 – 提供兼容主流 Python 库（scikit‑learn、scipy）的参考实现，使实践者能够轻松替换现有的链接函数。

Methodology

1. Chamfer distance for clusters – 对于两个簇 (A) 和 (B)，计算从 (A) 中点到 (B) 的最近邻距离的平均值以及从 (B) 到 (A) 的平均值，然后将这两个平均值相加。该方法提供了一个对称且计算成本低的近似，用于真实的 Earth‑Mover’s Distance。
2. HAC algorithm – 保留标准的凝聚层次聚类循环：反复合并 Chamfer‑linkage 距离最小的簇对。作者展示了通过缓存最近邻和，可以在常数摊销时间内更新每次合并，从而实现整体 (O(n^2)) 的算法。
3. Benchmark suite – 作者选取了 30 多个数据集，涵盖不同模态（图像特征向量、TF‑IDF 文本向量、图嵌入）。对每个数据集，使用五种链接方式运行 HAC，评估能够最大化真实标签的调整 Rand 指数的树切割，并记录运行时间和内存使用情况。
4. Statistical analysis – 配对 t 检验和 Wilcoxon 符号秩检验表明，Chamfer‑linkage 的改进在整体上具有统计显著性。

结果与发现

• 质量提升 – 在整个基准测试中，Chamfer‑linkage 将平均调整 Rand 指数提升了 7–12 %（相较于 average‑linkage）以及 5–9 %（相较于 Ward 方法）。
• 对噪声的鲁棒性 – 在注入离群点的合成实验中，Chamfer‑linkage 的树状图保持稳定，而 single‑linkage 则会出现“链式”伪影。
• 运行时相当 – 二次时间复杂度与经典链接方法相同；在 10 k 点数据集上，Chamfer‑linkage 完成时间约为 2.3 秒，而 average‑linkage 为 2.1 秒——完全在实际可接受范围内。
• 内存占用 – 仅因存储最近邻求和而略增约 10 % 的额外内存，仍能轻松适配标准工作站的 RAM，支持最高 100 k 点的数据集。

实际影响

• 即插即用的改进 – 开发者可以在现有的 scikit‑learn 流程中将 linkage='average' 替换为 linkage='chamfer'，即可立即获得更忠实的层次分组，尤其适用于深度学习流水线中常见的高维嵌入。
• 更好的下游任务 – 更精确的树状图切割能够提升标签传播、半监督学习和异常检测的质量，这些任务都依赖于层次结构。
• 计算机视觉流水线 – 由于 Chamfer 距离已用于点云对齐，将 Chamfer‑linkage 集成进来可以统一聚类和形状匹配组件，简化 3‑D 感知或 LiDAR 处理的代码库。
• 可扩展到大规模数据 – 该算法的 (O(n^2)) 复杂度与已知的最佳 HAC 实现相当；对于真正的大规模数据集，开发者可以将 Chamfer‑linkage 与标准的近似技巧（例如基于标记点的 HAC）结合使用，而不会失去其核心优势。

限制与未来工作

• 二次扩展 – 虽然对许多中等规模的问题来说是可接受的，但该方法在处理数百万点时仍然困难；作者建议探索层次近似或 GPU 加速的最近邻更新。
• 对欧氏几何的依赖 – Chamfer‑linkage 假设在度量空间中最近邻距离是有意义的；在高度稀疏或类别型数据上的性能可能会下降。
• 无参数但并非普遍最优 – 论文没有引入可调超参数，但某些领域（例如使用余弦相似度的文本）可能受益于加权 Chamfer 变体。
• 理论深度 – 当前分析侧重于表示属性；相对于全局聚类目标（例如最小化簇内方差）的形式化近似保证仍是一个未解之题。

结论：Chamfer‑linkage 提供了一种实用且质量更高的经典 HAC 链接替代方案，工程开销几乎可以忽略——这使它成为任何开发者聚类工具箱中极具吸引力的补充。

作者

• Kishen N Gowda
• Willem Fletcher
• MohammadHossein Bateni
• Laxman Dhulipala
• D Ellis Hershkowitz
• Rajesh Jayaram
• Jakub Łącki

论文信息

• arXiv ID: 2602.10444v1
• 分类: cs.LG, cs.DC, cs.DS, cs.IR
• 出版日期: 2026年2月11日
• PDF: 下载 PDF