Hierarchical Clustering Can Jointly Satisfy Richness, Consistency, and Scale Invariance

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

问题陈述
聚类缺乏一个公认的“簇”的定义，这一困难由 Kleinberg 的不可能定理（Kleinberg, 2002）进行了形式化。该定理证明，没有任何扁平聚类方法（将差异度映射为单一划分）能同时满足三个自然公理：尺度不变性（与测量单位无关）、丰富性（能够根据适当的输入产生任何可能的划分）以及一致性（即增强簇内相似性和削弱簇间相似性不应改变输出划分的性质）。这种紧张关系源于一致性允许在簇内创建新的子结构，而扁平划分无法在不违反该公理的情况下表达这些子结构。

本文研究了当输出是一个层次结构（一个嵌套的簇族）而非扁平划分时，这种不可能现象是否仍然存在。作者探讨了层次聚类的公理化版本是否可以被同时满足。

方法论与定义
作者将层次聚类方法定义为一个从差异函数集 $D(X)$ 到层次结构集 $T(X)$ 的映射，其中层次结构是一个包含全集 $X$ 和所有单元素集合的层级簇族。他们为层次聚类制定了四个公理：

1. 尺度不变性： 对于任何缩放因子 $\beta > 0$，有 $T(\beta d) = T(d)$。
2. 划分丰富性： 对于 $X$ 的每一个划分 $\mathcal{C}$，存在一个差异度 $d$，使得 $\mathcal{C} \subseteq T(d)$。（注：层次结构必须将该划分作为其簇的子集）。
3. 划分一致性： 若划分 $\mathcal{C}$ 包含在 $T(d)$ 中，且 $d'$ 是 $d$ 的 $\mathcal{C}$-增强（簇内距离减小，簇间距离增加），则 $\mathcal{C} \subseteq T(d')$。
4. 置换不变性： 输出仅取决于差异结构，而不取决于点的标记。

满足所有这四个条件的被称为可容许的（admissible）。作者还考虑了一个更强的条件，即在超度量上的精确性，要求如果输入是超度量，该方法需恢复与该超度量相关的规范层次结构。

核心贡献与结果

1. 可容许性的实现
与扁平划分的设定不同，作者证明了可容许的层次聚类方法是存在的。事实上，存在不可数个这样的方法。

• 显式构造： 论文构造了几种可容许的方法：
  • 非二元单链接法 ($T_{SL}$)： 与标准的二元单链接不同，这种非二元变体（同时合并所有并列的簇）是可容许的。
  • 分离方法： 两类基于全局和局部分离边际的方法 $T_{glob}^\eta$ 和 $T_{loc}^\eta$。它们定义的簇在内部差异相对于外部差异足够小时成立。
  • Bryant-Berry 稳定簇 ($T_{stable}$)： 一种基于组合稳定性准则的方法，以及其幂变换变体 $T_{stable}^{(p)}$。
• 其他连接法的不可行性： 研究表明，完全连接法（complete linkage）、平均连接法（average linkage）、Ward 法、重心连接法（centroid）和中位数连接法（median）的非二元变体至少违反了一个公理。

2. 可容许方法的结构分析
作者在**细化序（refinement order）**下对可容许方法集（记作 $H_{\alpha_{adm}}(X)$）进行了分析（若对于所有 $d$ 都有 $T_1(d) \subseteq T_2(d)$，则称 $T_1 \sqsubseteq T_2$）。

• 多样性： 该集合是一个具有不可数高度、宽度和细胞性的偏序集。
• 不存在最大元： 不存在一个能细化所有其他方法的单一“最精细”的可容许方法。
• 不相容性： 存在不可数多个两两不相容的最大元（即无法被任何其他可容许方法共同细化的方法）。具体而言，族 $\{T_{stable}^{(p)} : p > 0\}$ 构成了一个强上升反链。
• 共同骨干： 尽管存在这种多样性，公理仍强制执行了一种非平凡的共同结构。每个可容许方法都细化了一个由足够分离的簇组成的层次结构（即对于某个边际序列 $\eta$ 的 $T_{glob}^\eta$）。此外，任何有限个可容许方法的交集都共享一个共同的骨干。
• 不存在最小元： 仅返回单元素和根节点的平凡方法是所有层次方法中的下确界，但它因无法满足划分丰富性而不具备可容许性。因此，可容许类没有最小元。

3. 强可容许性与超度量
当加入在超度量上的精确性公理时，该类变为强可容许的（strongly admissible）（$H_{\alpha_{adm}^+}(X)$）。

• 该类依然是不可数的，并保留了最大元的多样性。
• 至关重要的是，与规范的可容许类不同，强可容许类有一个最小元：$T_{glob}$（边际序列 $\eta = \mathbf{1}$ 的方法）。这提供了一个最粗的强可容许方法。

4. 预处理与组合
论文研究了在聚类前应用的预处理变换 $\mu: D(X) \to D(X)$。

• 保持条件： 作者推导了使变换保持公理的一般条件（例如，缩放与 $\mu$ 交换，增强映射为增强）。
• 示例：
  • 极小极大路径（次优超度量）： 将差异度映射为其次优超度量的变换 $B^*$ 保持了尺度不变性、置换不变性和超度量精确性。这导致了分解关系 $T_{SL} = T_{glob} \circ B^*$，表明单链接法是超度量变换与分离方法的组合。
  • PCA 与 HDBSCAN： 论文分析了 PCA 和互达性（mutual-reachability）预处理，显示它们保持了尺度和置换不变性，但通常无法保持丰富性或一致性。

意义
本文表明，满足 Kleinberg 公理的基本不可能现象是由于将输出限制为扁平划分而产生的产物。通过转向层次化输出，这些公理可以被共同满足，从而开启了一个广阔的可容许方法图景。

这项工作揭示了虽然可容许方法空间极其多样（缺乏唯一的优化解），但它并非无序的。公理强制执行了一个所有可容许方法都必须遵守的“保守”骨干（即足够分离的簇），同时允许在如何解析更精细结构方面拥有自由度。这为理解层次聚类中的权衡提供了一个原则性的框架，并表明在可容许类中选择特定方法，取决于对噪声敏感度与输出粒度之间平衡的期望，而非违反基本的公理原则。

作者指出，该框架与 Carlsson 和 Mémoli (2010) 以及 Ackerman 和 Ben-David (2016) 的工作相关联，但不同之处在于它侧重于无权重层次结构，并保留了 Kleinberg 一致性公理的完整强度，从而得到一个更广泛、更多样化的类别，而非仅仅刻画单一算法。