层次聚类可以同时满足丰富性、一致性和尺度不变性

# 层次聚类可联合满足丰富性、一致性与尺度不变性  
来源：https://arxiv.org/html/2609.11173  
Daichi Kuroda, Maximilien Dreveton, Matthias Grossglauser, and Patrick Thiran  

Daichi Kuroda daichi\.kuroda@epfl\.ch  
**隶属机构：** 计算机与通信科学学院  
**隶属机构：** 洛桑联邦理工学院（EPFL）  
**隶属机构：** 瑞士洛桑，1015  

Maximilien Dreveton maximilien\.dreveton@univ\-eiffel\.fr  
**隶属机构：** LAMA, UMR\-CNRS 8050  
**隶属机构：** 古斯塔夫·埃菲尔大学  
**隶属机构：** 法国马恩河谷，77454，笛卡尔大道5号  

Matthias Grossglauser matthias\.grossglauser@epfl\.ch  
**隶属机构：** 计算机与通信科学学院  
**隶属机构：** 洛桑联邦理工学院（EPFL）  
**隶属机构：** 瑞士洛桑，1015  

Patrick Thiran patrick\.thiran@epfl\.ch  
**隶属机构：** 计算机与通信科学学院  
**隶属机构：** 洛桑联邦理工学院（EPFL）  
**隶属机构：** 瑞士洛桑，1015  

###### 摘要  
尽管聚类无处不在，但对于“什么是簇”却缺乏一个普遍接受的定义。Kleinberg 不可能性定理通过证明没有平面聚类方法能同时满足三个自然公理——尺度不变性、丰富性和一致性——正式阐明了这一困难。本文探讨当输出为层次结构而非单一划分时，这种不可能性是否仍然存在。我们表明，与平面聚类设置相反，这些公理的层次类比可以**联合可满足**。事实上，存在不可数多个满足这些公理的层次聚类方法，我们称之为**可容许**方法。我们显式构造了几种可容许方法，包括基于良好分离簇的方法和单链接的非二元版本。对于某些可容许方法对，其中一种方法产生的层次结构总是对另一种方法产生的层次结构进行细化。这种细化关系在可容许方法类上定义了一个偏序。该偏序集没有最大元素，并包含不可数多个两两不相容的极大元素，揭示了可容许方法间的显著多样性。尽管如此，这种多样性受到约束：每个可容许方法都包含一个足够良好分离的簇层次结构，并且任意有限个可容许方法共享一个非平凡的共同骨架。  

††heading:23 2026 1\-1/21; Revised 5/22 9/22 21\-0000  
††shortheadings:公理化层次聚类 / Kuroda, Dreveton, Grossglauser, and Thiran  
††firstpage:1  
††editor:我的编辑  

###### 关键词  
聚类；层次聚类；公理化聚类；无监督学习；超度量。  

## 1 引言  
聚类是无监督学习中最基本的任务之一。给定数据点之间的成对差异度，聚类旨在无需标签或真实值的情况下发现有意义的群体结构。然而，这一任务本质上是欠定的：没有普遍接受的簇的定义。因此，公理框架为陈述和比较聚类方法的理想特性提供了一种有原则的方式。这一方向的一个核心结果是 **Kleinberg 不可能性定理**（Kleinberg, 2002 (https://arxiv.org/html/2609.11173#bib.bib8)），它表明没有一种将差异度映射到划分的平面聚类方法能同时满足三个自然公理：尺度不变性、丰富性和一致性。该定理对聚类理论产生了深远影响：它意味着在公理、问题表述和/或聚类输出之间的某种权衡是不可避免的。大量后续工作探索了通过弱化或修改公理，或修改输入或输出空间来规避这种不可能性（Ben\-David and Ackerman, 2008 (https://arxiv.org/html/2609.11173#bib.bib6); Zadeh and Ben\-David, 2009 (https://arxiv.org/html/2609.11173#bib.bib15); Strazzeri and Sánchez\-García, 2022 (https://arxiv.org/html/2609.11173#bib.bib14); Willson and Warnow, 2024 (https://arxiv.org/html/2609.11173#bib.bib7)）。相比之下，本文提出一个不同的问题：  

> *当输出是层次结构而非平面划分时，Kleinberg 的不可能性是否仍然存在？*  

在三个 Kleinberg 公理中，**一致性** 在平面聚类设置中可以说是争议最大的。它要求，如果减少所有簇内差异度（相对于输出划分）并增加所有簇间差异度，则输出聚类必须保持不变。这形式化了以下直觉：增强一个聚类的证据不应推翻它。然而，这种变换也可能在簇内创建任意强的**子结构**，从而揭示平面划分无法表达的更精细区分。这种张力是 Kleinberg 不可能性结果的核心。图1 (https://arxiv.org/html/2609.11173#S1.F1) 说明了这一现象：从单个簇 \(C_1 \cup C_2\) 开始，一次允许的强化可以使每个子簇 \(C_1\) 和 \(C_2\) 比它们的并集更紧密，从而揭示了两个新的簇，而尊重一致性公理的平面聚类方法将被迫忽略这两个新簇。  

图1：强化簇 \(C_1 \cup C_2\) 可以创建两个良好分离的子簇 \(C_1\) 和 \(C_2\)，而一个满足 Kleinberg 一致性的平面聚类方法却被迫忽略它们。相比之下，层次聚类方法可以同时包含 \(C_1 \cup C_2\) 以及 \(C_1\) 和 \(C_2\)，因为它们是适当嵌套的。  

这一观察提示我们通过考虑层次聚类方法来超越平面聚类。确实，层次聚类可以保留理想的簇 \(C_1 \cup C_2\)，同时纳入新出现的子簇 \(C_1\) 和 \(C_2\)：增强现有簇的证据不必阻止该方法表达该簇内更精细的结构。  

形式上，一种层次聚类方法是从差异度到层次结构的映射，表示为簇的层叠族。我们制定了尺度不变性、丰富性和一致性的层次类比，并额外施加置换不变性作为基本对称性要求。我们的第一个主要结果是积极的：与平面设置相反，这些公理在层次设置中是**联合可满足的**。事实上，存在不可数多个可容许方法。我们显式构造了几种可容许方法，包括基于良好分离簇的层次结构和单链接的非二元版本。相比之下，其他经典链接方法（如完全链接、平均链接、Ward链接、中心链接和中位数链接）的非二元变体未能满足这些公理。  

除了存在性，我们还在细化序下研究了可容许方法族的全局结构。该族形成了一个显著多样化的偏序集：它具有不可数的高度、宽度和胞腔度，并包含不可数多个两两不相容的极大元素。特别是，没有最大的可容许方法。尽管如此，公理施加了非平凡的共同结构。我们证明了一个**骨架性质**：每个可容许方法都细化一个足够良好分离的簇层次结构。此外，任意有限个可容许方法共享一个这样的共同骨架。因此，公理允许显著的多样性，同时仍强制对足够良好分离的簇结构达成一致。  

然后，我们考虑一个特定于层次聚类的更强要求。当输入差异度是一个超度量时，¹¹超度量是一种满足强三角不等式 \(u(x,y) \leq \max\{u(x,z), u(y,z)\}\) 的差异度，对所有 \(x,y,z\) 成立；这样的差异度通过其嵌套的距离球典范地编码一个层次结构。它已经编码了一个典范的层次结构。因此，自然要求一个层次聚类方法精确地恢复这个层次结构。我们称此性质为**在超度量上的精确性**。由此产生的强可容许方法类仍然是不可数的，并保留了上述骨架和极大性现象。然而，额外的要求锐化了序论结构：与典范可容许类不同，强可容许类在细化下具有最小元素。  

最后，受实际聚类流程的启发，我们研究了输入差异度的预处理变换。我们推导出在与这样的变换组合时保持每个公理的一般条件，并用几个常见的预处理操作来说明这些原则。  

我们的工作连接了聚类文献的几条脉络。它有助于理解 Kleinberg 不可能性定理并尝试绕过它，通过修改公理和/或聚类问题表述（Ben\-David and Ackerman, 2008 (https://arxiv.org/html/2609.11173#bib.bib6); Cohen\-Addad et al., 2018 (https://arxiv.org/html/2609.11173#bib.bib5); Willson and Warnow, 2024 (https://arxiv.org/html/2609.11173#bib.bib7)）。它也与层次聚类方法的公理化和结构性表征（Carlsson and Mémoli, 2010 (https://arxiv.org/html/2609.11173#bib.bib4); Ackerman et al., 2010 (https://arxiv.org/html/2609.11173#bib.bib10); Ackerman and Ben\-David, 2016 (https://arxiv.org/html/2609.11173#bib.bib13)）以及层次聚类的人口水平公理化（Thomann et al., 2015 (https://arxiv.org/html/2609.11173#bib.bib26); Arias\-Castro and Coda, 2025 (https://arxiv.org/html/2609.11173#bib.bib9)）相关。  

特别是，层次输出先前已被证明支持积极的公理结果：Carlsson and Mémoli (2010) (https://arxiv.org/html/2609.11173#bib.bib4) 使用与 Kleinberg 框架大不相同的公理系统刻画了单链接，而 Ackerman and Ben\-David (2016) (https://arxiv.org/html/2609.11173#bib.bib13) 使用局部性和一种仅考虑将已经良好分离的簇移动得更远的较弱一致性来刻画基于链接的层次方法。两项工作都保留了簇合并的数值尺度，因此它们的输出是带高度标签的层次结构（树状图），等效地由超度量表示。因此，它们研究的是从输入差异度到输出超度量的映射。相反，我们考虑返回无权重层次结构的方法，这些方法仅保留嵌套的簇结构。在这个结构较少的输出框架内，我们的公理更接近 Kleinberg 的原始要求，同时施加了较少的结构约束。因此，我们不是表征一个独特的方法或一个规定的算法族，而是研究满足这些公理的、更多样化的层次方法类。第6节 (https://arxiv.org/html/2609.11173#S6) 提供了详细比较。  

### 1.1 定义与符号  
在本文中，\(\mathcal{X}\) 是一个有限项目集，基数为 \(n\)。此外，由于项目 \(\mathcal{X}\) 的标记与聚类等无监督任务无关，我们隐含地假设 \(\mathcal{X} = [n]\)，其中 \(n = |\mathcal{X}|\) 是有限的且 \([n] = \{1,\dots,n\}\)。为避免平凡情况，我们始终假设 \(n \geq 4\)。²²对于 \(n \leq 2\)，层次结构只能包含根节点和单例叶节点，因此必然是星型层次结构。对于 \(n=3\)，在重标记意义下只有一个非星型层次结构。  

\(\mathcal{X}\) 上的**差异度函数**是一个映射 \(d: \mathcal{X} \times \mathcal{X} \to \mathbb{R}_{\geq 0}\)，使得对所有 \(x \in \mathcal{X}\) 有 \(d(x,x)=0\)，且对所有不同的 \(x,y \in \mathcal{X}\) 有 \(d(x,y)=d(y,x) > 0\)。我们不假设 \(d\) 满足三角不等式，因此 \(d\) 不一定是一个距离。我们用 \(\mathcal{D}(\mathcal{X})\) 表示 \(\mathcal{X}\) 上所有差异度函数的集合。我们采用约定 \(\min \emptyset = \infty\)。  

**簇** \(C\) 是 \(\mathcal{X}\) 的一个非空子集，\(\mathcal{X}\) 的一个**划分**是一组两两不相交的簇 \(\mathcal{C} = \{C_1,\dots,C_k\}\)，其并集为 \(\mathcal{X}\)。设 \(\bar{C} := \mathcal{X} \setminus C\) 表示簇 \(C\) 相对于 \(\mathcal{X}\) 的补集。我们用 \(\mathcal{P}(\mathcal{X})\) 表示 \(\mathcal{X}\) 的所有划分的集合。  

### 1.2 文章结构  
本文其余部分组织如下。第2节 (https://arxiv.org/html/2609.11173#S2) 陈述主要公理并建立相应的可实现性结果。第3节 (https://arxiv.org/html/2609.11173#S3) 介绍几种可容许的层次聚类方法。第4节 (https://arxiv.org/html/2609.11173#S4) 研究可容许方法集的结构性质。第5节 (https://arxiv.org/html/2609.11173#S5) 将超度量上的精确性添加到公理系统中，并刻画保持公理的预处理变换。第6节 (https://arxiv.org/html/2609.11173#S6) 讨论相关工作，第7节 (https://arxiv.org/html/2609.11173#S7) 总结全文。省略的证明和技术引理在附录中提供。  

### 1.3 大型语言模型（LLM）的使用  
虽然本文基础项目的概念化完全由作者完成，但我们还使用了 GPT\-5\.6 Sol 来改进清晰度、措辞和呈现方式，并帮助识别和纠正早期草稿中的小错误和笔误。然而，绝大部分数学内容和证明是由我们生成的。使用 LLM 来开发证明技术的数学结果只有命题13 (https://arxiv.org/html/2609.11173#Thmtheorem13)、引理16 (https://arxiv.org/html/2609.11173#Thmtheorem16) 和引理55 (https://arxiv.org/html/2609.11173#Thmtheorem55)，以及命题40 (https://arxiv.org/html/2609.11173#Thmtheorem40)(iv)。我们还使用该模型协助附录E (https://arxiv.org/html/2609.11173#A5) 中的数值模拟。LLM 提出的所有文本都经过作者的严格审查和编辑，我们对本文承担全部责任。  

## 2 从不可能性到可实现性  
在本节中，我们首先回顾平面聚类的 Kleinberg 不可能性定理，然后表明，与之相反，他的公理的层次类比是联合可满足的。  

### 2.1 平面聚类的 Kleinberg 不可能性定理  
我们首先回顾 Kleinberg (2002) (https://arxiv.org/html/2609.11173#bib.bib8) 引入的平面聚类公理框架。一种**平面聚类方法**是一个映射 \(f: \mathcal{D}(\mathcal{X}) \to \mathcal{P}(\mathcal{X})\)，使得对每个差异度 \(d \in \mathcal{D}(\mathcal{X})\)，\(f(d)\) 是 \(\mathcal{X}\) 的一个划分。我们首先引入一种差异度的变换，称为**强化**³³这种变换在 Kleinberg (2002) (https://arxiv.org/html/2609.11173#bib.bib8) 中称为 \(\Gamma\)-变换，其中 \(\Gamma\) 是一个划分。它增强一个给定的聚类。直观上，强化使同一簇内的点彼此靠近，不同簇间的点远离。  

###### 定义 1（\(\mathcal{C}\)-强化）  
设 \(\mathcal{C} \in \mathcal{P}(\mathcal{X})\) 且 \(d, d' \in \mathcal{D}(\mathcal{X})\) 是两个差异度函数。我们称 \(d' \in \mathcal{D}(\mathcal{X})\) 是 \(\mathcal{C}\)-强化的。