技术摘要：层次聚类中的个体公平性

1. 问题定义

本文探讨了经典层次聚类中的一个基本局限性：虽然这些方法通过超度量（ultrametrics）生成多分辨率表示（树状图/dendrograms），但它们往往缺乏关于处理特定个体数据的保证。标准方法通常优化全局目标或遵循贪婪的连接规则，这可能会以不成比例的方式扭曲局部相似性，从而对特定个体产生不利影响。由于层次结构是向上传播的，早期的局部邻域扭曲会影响所有更粗的分辨率层级。

作者将层次聚类中的个体公平性问题进行了形式化。其核心要求是：相似的个体（由度量 $d$ 定义）应当被相似地对待。具体而言，本文研究是否存在一个超度量表示 $u$，能够同时满足以下两个条件：

1. 支配性（Domination）： 对于所有点对，$u(i, j) \ge d(i, j)$（即距离不会被收缩）。
2. 局部公平性（Local Fairness）： 在任何点 $i$ 的 $k$-最近邻（$k$-NN）邻域内，超度量距离相对于原始度量满足乘性松弛因子 $\alpha$（以及加性松弛因子 $\beta$）的界限：对于所有 $j \in N_k(i)$，$u(i, j) \le \alpha d(i, j) + \beta$。

主要目标是刻画实现此类可行超度量所需的最小乘性松弛因子 $\alpha^\star(d, k)$。

2. 方法论与理论框架

可行性图景

作者分析了寻找满足局部 Lipschitz 约束且被支配的超度量的可行性。他们区分了相互邻域（其中 $j \in N_k(i)$ 且 $i \in N_k(j)$）和单向邻域。

关键理论结果

• 局部必要松弛度（定理 1）： 作者定义了一个局部异质性比率 $\alpha^{\text{mut}}_k(d)$，用于衡量相互 $k$-最近邻星形结构（stars）内的最大尺度分离。他们证明，任何可行的乘性松弛因子 $\alpha$ 必须满足 $\alpha \ge \alpha^{\text{mut}}_k(d)$。这建立了一个尖锐的局部阈值；如果松弛因子低于此值，公平性在数学上是不可能的。
• 稳定性（定理 2）： 研究表明，在度量受限 $\ell_\infty$ 扰动下（前提是 $k$-最近邻的身份保持不变，即 $\epsilon$-稳定邻域），最小松弛阈值具有 Lipschitz 稳定性。
• 构造充分性（定理 3）： 借鉴经典的树嵌入理论（特别是 [11] 的结果），作者证明对于任何 $n$ 点度量，始终存在一个具有松弛因子 $\alpha = O(\log n)$ 的支配超度量。这为所需的失真提供了全局上界。
• 内在局部-全局差距（命题 1）： 一个关键发现是局部结构与全局可实现性之间的分离。作者构建了基于扩展图（expander graphs）的度量族，在这些度量族中，局部异质性比率是平凡的（$\alpha^{\text{mut}}_k(d) = 1$），但任何支配超度量都需要 $\Theta(\log n)$ 的失真。这表明局部一致性并不保证全局可行性。
• 单调性（定理 4）： 最小可行松弛因子 $\alpha^\star(d, k)$ 随邻域大小 $k$ 的增加而呈非递减趋势。加强局部公平性约束（增加 $k$）绝不会降低所需的全局松弛因子。

算法方法：FCAC

为了构造可行的超度量，本文提出了公平约束凝聚聚类（Fairness Constrained Agglomerative Clustering, FCAC）。

• 机制： FCAC 通过在合并选择过程中强制执行公平性约束来修改标准的凝聚聚类。它将连接得分（决定合并顺序）与合并高度分配分离。
• 高度分配： 合并高度被设定为 $h(A, B) = \max(\ell(A, B), \max_{i \in A, j \in B} d(i, j))$，以确保满足支配条件（$u \ge d$）。
• 可行性检查： 在合并两个簇之前，算法会检查提议的高度是否违反了跨簇的任何邻居对的公平性约束（$h \le \alpha d(i, j) + \beta$）。
• 复杂度： 该算法在最坏情况下的运行时间为 $O(n^3 k)$。论文指出，确定底层可行性决策问题的确切计算复杂度仍是一个开放的研究方向。

3. 实验结果

作者在合成数据集和现实世界数据集（高斯混合模型、随机 3-正则图、UCI Census Income、German Credit Data 和 Iris）上验证了其理论主张。

• 可行性阈值： 在高斯混合模型上的实验显示了可行性的剧烈转变。最小可行松弛因子 $\alpha^\star$（17.46）显著高于局部相互阈值（5.08），证实了局部一致性低估了全局失真需求。
• 局部-全局差距： 在随机 3-正则图上，局部比率 $\alpha^{\text{mut}}_k(d)$ 保持为 1，而最小可行松弛因子 $\alpha^\star$ 随 $n$ 增长，经验性地证明了命题 1 所预测的 $\Theta(\log n)$ 差距。
• 缩放行为：
  • 在异质数据集（如 Adult）中，$\alpha^\star$ 随样本量 $n$ 的增加而显著增加，这表明稀有的局部几何违规会累积并放大全局失真。
  • 在更稳定的数据集（如 German Credit）中，尽管 $n$ 在增加，$\alpha^\star$ 仍保持相对稳定。
• 阻碍饱和（Obstruction Saturation）： 观察到最小松弛因子 $\alpha^\star$ 在较小的邻域规模（$k \approx 3$）下趋于饱和，这表明全局超度量阻碍是由小规模几何配置决定的。
• 算法对比： 在 Adult 数据集（$n=800$）上，FCAC (基于 MST 的变体) 实现的松弛因子为 1.00，而 FRT 嵌入（一种标准的树嵌入方法）尽管具有 $O(\log n)$ 的理论保证，其平均松弛因子却达到了 67.26。这表明，与通用的嵌入界限相比，感知几何结构的构造方法在实践中可以表现得更好。

4. 重要性与主张

本文声称提供了层次聚类中个体公平性的首次结构可行性分析。其意义在于：

1. 重构公平性： 将焦点从优化全局目标转向刻画在超度量这种僵化的几何结构下，局部公平性约束的可行性。
2. 量化内在代价： 明确了层次表示中的公平性成本本质上与度量失真相关，特别是识别出某些度量族中，局部相似性与全局超度量可实现性之间存在不可避免的 $\Theta(\log n)$ 分离。
3. 算法贡献： 提供了一种能够强制执行这些约束的构造性算法（FCAC），并经验性地证明了数据感知方法（特别是基于 MST 的变体）可以实现优于通用嵌入技术的近乎最优的松弛因子。

作者总结道，虽然局部条件是必要的，但不足以决定全局可实现性，且最小所需的松弛因子是数据几何结构的一个基本属性。未来的工作建议包括刻画可行性问题的计算复杂度，并将该框架扩展到其他多尺度表示。