机器学习模型常因其 黑箱 特性而饱受诟病。我们输入数据,它输出结果,但其决策背后的逻辑却不透明。在医疗诊断或贷款审批等高风险领域,这种缺乏透明性的状况是不可接受的,因为在这些场景下,理解 为什么 与知道 是什么 同样重要。聚类——即将相似的数据点分组的任务——也不例外。如果无法理解模型创建簇的逻辑,我们又怎能信任它的聚类结果呢?

于是,可解释 AI 应运而生。目标是设计既准确又易于人类理解的模型。对于聚类,Dasgupta 等人 (2020) 提出了一个简单而强大的想法——用 阈值决策树 来定义簇。取代复杂、不规则的边界,簇由简单的轴对齐切割界定,比如“年龄 > 30”或“收入 ≤ 50000 美元”。这样的边界让聚类的逻辑一目了然。

当然,这种简洁性是有代价的: 强制限制簇在整齐的矩形框中,可能会扭曲数据的自然分组并增加聚类成本。这种权衡被称为 可解释性的代价。关键问题是: 这个代价有多高? 我们能否找到一种算法,让这个代价尽可能低?

近期一篇论文《随机切割是可解释 k-中值聚类的最优方法》给出了肯定答案。作者分析了一种极其简单的算法 RANDOMCOORDINATECUT,并证明其竞争比达到最优。这项研究不仅提出了一个优秀算法,还弥合了理论缺口,将复杂的几何问题重构为一个简洁的概率博弈。


什么是可解释聚类?

在深入探讨论文核心贡献之前,先直观感受一下这个问题。

标准的 k-中值聚类 会将数据集 \(X\) 划分为 \(k\) 个簇,选取 \(k\) 个中心点,使得每个数据点到其分配中心的距离总和最小化。这里我们关注的是 \(\ell_1\)-范数,即 曼哈顿距离,公式为:

\[ \|x - c\|_1 = \sum_j |x_j - c_j| \]

在标准 k-中值聚类中,簇由 Voronoi 分割 定义: 每个点属于离它最近的中心。如 **图 1 **(左) 所示,这可能形成复杂的非矩形边界——尤其在 \(\ell_1\) 距离下——使得解释一个点为何属于某个簇变得困难。

图 1: 左图是标准的 k-中值聚类,其沃罗诺伊边界较为复杂。中图和右图是一个可解释的聚类,其轴对齐的简单切割由一棵决策树定义。

图 1: 左: 无约束 k-中值聚类在 \(\ell_1\) 距离下的 Voronoi 分割。中: 具有矩形区域的可解释分割。右: 对应的决策树。

可解释 k-中值聚类 中,簇边界必须轴对齐。我们构建一棵决策树,每个分裂由简单的阈值切割 \(x_j \le \theta\) 定义,从而得到 \(k\) 个矩形簇 \(P_1,\dots,P_k\)。k-中值的成本通过这些矩形簇的最优中值计算:

可解释聚类 T 对于数据集 X 的成本。

图 2: 可解释 k-中值聚类的目标,是计算每个点到其矩形簇中值的 \(\ell_1\) 距离之和。

主要衡量指标是 竞争比——可解释聚类的成本除以最优无约束聚类的成本。Dasgupta 等人证明,没有算法能优于 \(\Omega(\log k)\),而现有对 RANDOMCOORDINATECUT 的分析给出了 \(\mathcal{O}(\log k \log \log k)\) 的上界。那么,这个算法是次优的,还是分析不够紧?


算法: RANDOMCOORDINATECUT

RANDOMCOORDINATECUT 接收由标准 k-中值算法计算得到的 \(k\) 个参考中心点,并构建阈值决策树将它们逐一分离。

步骤:

  1. 初始化: 从一个表示整个空间的根节点开始;将所有 \(k\) 个参考中心点分配给它。
  2. 递归分割: 当某个叶节点包含多于一个中心点时:
    • 随机选择一个坐标 \(j\) (例如 \(x\)-轴或 \(y\)-轴) ;
    • 在该坐标上随机选择一个阈值 \(\theta\);
    • 对每个叶节点 \(u\),如果切割 \((j,\theta)\) 能将其中心点分成两个非空子集,则将 \(u\) 分裂为:
      • 左子节点: 所有满足 \(x_j \le \theta\) 的点;
      • 右子节点: 所有满足 \(x_j > \theta\) 的点。
  3. 停止: 当每个叶节点恰好包含一个中心点时结束。此时的树定义了 \(k\) 个矩形簇。

根据随机切割在节点 u 处分割中心点的规则。

图 3: 随机坐标切割 \((j, \theta)\) 将一个叶节点的中心点分成左右子节点,前提是两侧均非空。

早期分析表明,该算法的期望竞争比为 \(\mathcal{O}(\log k \log \log k)\)。

先前对 RANDOMCOORDINATECUT 竞争比的界定。

图 4: 先前分析给出的竞争比上界为 \(\mathcal{O}(\log k \log \log k)\)。


分析: 将聚类问题转化为博弈

这篇论文的关键洞见是将算法的行为转化为一个 **集合消除博弈 **(Set Elimination Game) ,剥离几何因素,专注于一个纯粹的随机过程。

思路: 设数据点 \(x\) 最终分配给中心 \(c^i\),其成本为 \(\|x - c^i\|_1\)。我们通过博弈过程来计算它的期望成本。

  1. 切割作为元素: 令 \(\Omega\) 为有界数据空间中所有可能的切割 \((j,\theta)\) 的集合。
  2. 距离作为集合: 对每个中心 \(c^i\),定义 \(S_i \subset \Omega\) 为能将 \(x\) 与 \(c^i\) 分开的切割的集合。

集合 S_i 的定义,它包含所有将数据点 x 与中心点 c^i 分开的切割。

图 5: \(S_i = \{(j,\theta) \in \Omega : \mathrm{sign}(x_j - \theta) \neq \mathrm{sign}(c_j^i - \theta)\}\)。

关键联系: 集合 \(S_i\) 的测度 \(\mu(S_i)\) 等于 \(\|x - c^i\|_1\),因为每个坐标的贡献是分离区间长度 \(|x_j - c_j^i|\),对所有 \(j\) 求和即可。

集合消除博弈规则:

  • 玩家: \(S_1, \dots, S_k\);
  • 回合: 随机抽取 \(\omega \in \Omega\);
  • 消除: 移除所有包含 \(\omega\) 的集合,除非所有剩下集合均包含 \(\omega\),此时不消除任何集合。

集合消除博弈的核心规则。

图 6: 切割会消除它所分离的集合,除非它分离了所有剩余集合。

博弈以出现一个 获胜者 结束,成本即该获胜集合的 \(\mu\)。数据点 \(x\) 最终分配的中心对应于获胜集合;期望聚类成本即期望博弈成本。

作者证明:

主要定理,限定了集合消除博弈的期望成本。

图 7: \(\mathbb{E}[\mu(\mathrm{winner})] \le (2\ln k + 2) \cdot \min_i \mu(S_i)\)。

在聚类中,\(\min_i \mu(S_i)\) 是 \(x\) 到最近中心的距离。对所有 \(x\) 求和可得 RANDOMCOORDINATECUT 的竞争比至多为 \(2\ln k + 2\):

可解释 k-中值聚类竞争比的最终紧凑界。

图 8: 紧凑界与 \(\Omega(\log k)\) 下限相符——实现最优。


证明过程一瞥

证明中引入了 指数时钟 的概念: 设每个切割 \(\omega\) 有一个独立的速率为 \(\mu(\omega)\) 的指数时钟;命中时间 \(h(\omega)\) 即时钟响起的时刻。
对于集合 \(S\),\(h(S) = \min_{\omega \in S} h(\omega)\) 是速率为 \(\mu(S)\) 的指数随机变量。

切割集合 X 的命中时间 h(X) 的定义。

图 9: 命中时间 \(h(X)\) 是集合 \(X\) 中第一个切割出现的时间。

不相交集合的命中时间相互独立,这一性质非常强大。

作者假设 \(S_1\) 最小 (即 \(\mu(S_1) \le \mu(S_i)\) 对所有 \(i\) 成立) ,并将期望成本拆分为:

  1. 获胜者是 \(S_1\);
  2. 获胜者是 **意外集 **(集合很大但存活时间异常长: \(h(S_i) \ge (\ln k)/\mu(S_i)\)) ;
  3. 获胜者是除 \(S_1\) 外的 非意外集

一个集合成为意外集的概率很小。

图 10: 意外集很少见;其概率 \(\le \frac{1}{k} \cdot \frac{\mu(S_1)}{\mu(S_i)}\)。

第 (1) 项 \(\le \mu(S_1)\)。由于意外获胜者的概率极低,第 (2) 项同样 \(\le \mu(S_1)\)。

第 (3) 项需更细致处理: 非意外获胜者的命中时间较短,使得作者可将其贡献限制在 \(2L\mu(S_1)\) 内,其中 \(L = \ln k\)。

期望成本被分解为三种情况。

图 11: 按获胜集合类型分解成本。

将三部分相加,得出:

通过将三个部分相加,得出最终的界。

图 12: \(\mathbb{E}[\mu(\mathrm{winner})] \le (2\ln k + 2)\mu(S_1)\)。


结论与启示

这篇论文是理论解决实际问题的典范: 它回答了我们能否兼顾 聚类质量可解释性

核心要点:

  1. 可实现最优性: RANDOMCOORDINATECUT 被证明是可解释 k-中值聚类的最优算法;可解释性的代价为 \(\Theta(\log k)\)。
  2. 弥合理论差距: 竞争比从 \(\mathcal{O}(\log k \log \log k)\) 改进为紧凑的 \(\mathcal{O}(\log k)\),与下限匹配。
  3. 优雅分析工具: 集合消除博弈与指数时钟技术为分析随机算法提供了可重复使用的方法。

在推动 AI 透明化的道路上,这项研究令人振奋: 有时我们能够在保持完全可解释性的同时,不失去太多效果——用简单的规则定义簇。仅靠随机坐标切割,我们即可构建出经过严格证明的最佳解释。