arXiv:2604.23628cs.DScs.LG2026-04

提出可衡量层次聚类质量的新目标函数,让算法结果更可信。

Characterizing Admissible Objective Functions for Hierarchical Clustering

  • 用对称多项式定义聚类目标函数,给出可实现的数学条件。
  • 证明递归稀疏割算法在特定条件下能达到近似最优解。
  • 新方法适合追求理论严谨性的研究者或数据科学家。

层次聚类是数据分析的基础任务,但传统方法长期缺乏合理的优化目标。Dasgupta(STOC 2016)首次提出一个有动机的目标函数。Cohen-Addad 等人(JACM 2019)引入了‘可接受性’概念:若输入相似度矩阵存在生成树,则目标函数的最小化结果恰好为这些生成树。他们给出了基于聚合簇间相似度的一类目标函数的可接受性充要条件,称为 sum-type 目标函数。然而除 Dasgupta 原始函数外,该类中未提供其他显式可接受函数。本文从两方面推进:针对 sum-type 函数,当缩放函数为次数 ≤2 的对称多项式时,给出完整可接受性刻画;对次数为3的多项式,给出充分条件;并证明递归稀疏割算法对这类目标函数可达 $O( ho)$ 近似比,其中 $ ho$ 是稀疏割子程序的近似因子。此外,引入 max-type 目标函数,以最大簇间相似度代替聚合相似度,并对任意对称缩放函数及次数 ≤2 的对称多项式情形,完成可接受性完全刻画。

原文摘要 · Abstract (English)

Hierarchical clustering is a fundamental task in data analysis, but classical methods have long lacked a principled objective function. Dasgupta [STOC 2016] took an important step toward addressing this gap by proposing a well-motivated objective function for cluster trees. Cohen-Addad et al. [J. ACM 2019] subsequently introduced the notion of admissibility: an objective function is admissible if, whenever the input similarity matrix admits generating trees, its minimizers are precisely those generating trees. They also gave a necessary and sufficient condition for admissibility within a family of objective functions based on aggregate intercluster similarity. We refer to this family as sum-type objective functions. However, apart from Dasgupta's original objective function, no explicit admissible objective functions in this family were provided. In this paper, we study admissible objective functions for hierarchical clustering in two directions. For sum-type objective functions, we give a complete characterization when the scaling function is a symmetric polynomial of degree at most two, and we derive sufficient conditions for degree-three polynomials. We also show that the recursive sparsest cut algorithm achieves an O$(ϕ)$-approximation ratio for the admissible objective functions covered by our characterization, where $ϕ$ is the approximation factor of the sparsest cut subroutine. We then introduce max-type objective functions, where cluster interaction is measured by maximum, rather than aggregate, intercluster similarity. For this class, we characterize which objective functions are admissible for arbitrary symmetric scaling functions and give a complete characterization when the scaling function is a symmetric polynomial of degree at most two.

聚类优化理论分析

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。