Proportionally Representative Clustering

技术摘要：比例代表性聚类

问题陈述
本文探讨了质心聚类（centroid clustering）中的公平性问题。质心聚类是无监督机器学习中的一项基本任务，其目标是从度量空间中选择 $k$ 个中心（质心）子集，以服务于 $n$ 个数据点（代理人）。虽然 $k$-means、$k$-medians 和 $k$-center 等标准目标优化的是全局福利，但它们往往无法捕捉到比例代表性的公平性。现有的聚类公平性概念（如比例公平性 PF 和核心公平性 Core Fairness）存在局限性：它们可能无法在每个实例中实现，且未能满足一个被称为“一致比例性”（unanimous proportionality，即位于同一位置的一组代理人有权获得与其规模成比例数量的中心）的最小直觉要求。此外，现有的公平聚类算法通常依赖于预先指定的受保护属性，而本研究寻求的是适用于由数据分布内生确定的任意定义的群体的公平属性。

方法论
作者采用公理化方法，提出了一种新的公平性概念，称为比例代表性公平（Proportionally Representative Fairness, PRF）。该概念设计用于连续（无约束）和离散聚类场景。

1. 公理化定义 (PRF)：

   • 无约束场景： 若对于任何规模至少为 $\ell n/k$ 且最大两两距离为 $y$ 的代理人集合 $S$，在 $X$ 中至少有 $\ell$ 个中心位于距离 $S$ 中至少一个代理人距离 $y$ 之内，则结果 $X$ 满足 PRF。
   • 离散场景： 该定义经过调整以适应候选集 $M$ 的粗糙性。如果存在 $\ell'$ 个候选人在距离 $y$ 内覆盖了所有属于集合 $S$（其中 $|S| \ge \ell n/k$）的代理人，那么结果中必须有至少 $\ell'$ 个中心位于距离 $S$ 中某些代理人距离 $y$ 之内。

2. 算法设计 (SEAR)：
   作者引入了 SEAR（空间扩张批准规则），这是一种受多赢选举中扩张批准规则（Expanding Approvals Rule, EAR）启发并针对空间数据进行适配的多项式时间算法。

   • 机制： 该算法基于代理人与候选人之间的排序距离，迭代地扩张邻域半径。代理人被分配初始权重。当选中的候选中心覆盖了一组总权重至少为 $n/k$ 的代理人时，该中心被添加到解集中，且所覆盖代理人的权重减少 $n/k$。
   • 实现：
     • 算法 1（无约束）： 候选人被限制在代理人的位置。运行复杂度为 $O(n^2 \log n + kn^2)$。
     • 算法 2（离散）： 候选人选自有限集 $M$。运行复杂度为 $O(|M|n \log n + k|M|n)$。

主要贡献与结果

• PRF 的存在性与性质： 本文证明了在无约束和离散场景下均保证存在 PRF 结果。PRF 满足若干理想性质：它隐含了一致比例性，对离群值具有鲁棒性，具有尺度不变性，且不需要预先指定的受保护群体。
• 比例公平性 (PF) 的逼近：
  • 无约束场景： 用于无约束场景的 SEAR 算法提供了比例公平性 (PF) 的 3-近似。这是已知第一个在一般度量空间中针对 PF 的多项式时间近似算法。论文还确定了在一般存在性方面，关于 PF 的紧确界 $\frac{3+\sqrt{17}}{2} \approx 3.56$。
  • 离散场景： 用于离散场景的 SEAR 算法提供了 PF 的 $(1+\sqrt{2})$-近似，在匹配已知最优 PF 近似因子的同时，还满足了更强的 PRF 公理。
• 不可能结果：
  • 本文证明了标准聚类算法（$k$-means、$k$-median、$k$-center）和之前的公平聚类算法（如 Greedy Capture）并不满足 PRF。
  • 策略性（Strategyproofness）： 作者证明了 PRF 与策略性之间存在不兼容性。具体而言，不存在既满足顺序统计策略性（order-statistic strategyproof）又满足 PRF 的算法，即使是在离散场景下 $k=2$ 的情况也是如此。这是通过从基于批准的委员会投票进行归约来证明的，将 PRF 与已知与策略性不兼容的比例正当代表（PJR）公理联系起来。

意义
该论文声称其在以下三个主要领域具有重要意义：

1. 概念演进： 它引入了 PRF，作为一种鲁棒的、公理化的公平性概念，克服了现有比例公平性定义的缺陷，特别是未能保证一致比例性的问题。
2. 算法突破： 它提供了第一个在一般度量空间中针对比例公平性的多项式时间近似算法（无约束场景），并在满足更强 PRF 公理的同时，匹配了离散场景下的已知最优界限。
3. 理论极限： 它严格建立了公平性（特别是 PRF）与激励相容性（策略性）之间的权衡，表明满足比例代表性公理本质上与防止质心选择中的操纵行为相冲突。

这项工作将社会选择理论（特别是多赢投票）与无监督机器学习联系起来，利用空间信息来实现传统投票规则或标准聚类目标无法实现的同步决策。