立夏 | 如何让聚类具有可解释性

机器学习的可解释性历来是学术界与工业界共同关注的重要议题。尽管目前许多关注都集中在最新机器学习模型的可解释性挑战上，然而，一些传统机器学习问题，如聚类问题，似乎同样存在一些可解释性方面的问题。

假设我们手头有 $n$ 位同学的身高数据 $\{h_i \}_i$ 和体重数据 $\{w_i \}_i$ ，我们想将这些同学按照体型相似度分成 $k$ 类。这个问题，实际上可以转化为一个欧氏空间中的 $k$ -means 聚类问题。具体来说，我们可以将每位同学视为二维欧氏空间上的一个数据点，其中横坐标代表身高，纵坐标代表体重。我们的目标是将这个数据集 $X = \{x_i \}_i$ 划分为 $k$ 个类 $\mathcal{C}=\{C_1,…,C_k\}$ ，使得如下目标函数最小化： $\operatorname{cost}(\mathcal{C})=\sum_{i=1}^{k} \sum_{x \in C_{i}}\left\|x-\mu_{i}\right\|^{2}$ 其中 $\mu_i$ 是 $C_i$ 中所有点的均值， $\left\| \cdot \right\|$ 表示向量的模长。我们用 $\mathcal{C}^*$ 表示最优聚类。

聚类问题，作为无监督机器学习领域的一个经典课题，虽然求取最优解是一个 NP-hard 问题，但随着技术的发展，我们已经拥有了许多高效的近似算法来得到近似最优解，比如广为人知的 $k$ -means++ 算法^[1]。

然而，传统的 $k$ -means 算法存在一个问题：它的聚类结果往往难以直观地解释。原因在于，传统 $k$ -means 聚类的结果通常呈现为一个沃罗诺伊图（Voronoi Diagram），如图1中的左图，其中各个聚类之间由复杂的超平面分割，而这些超平面可能是由所有特征维度（如身高和体重）的任意线性组合决定的。这导致我们很难直观地理解一个聚类中的数据点与其他聚类中的数据点在特征上的差异。想象一下，如果我们尝试根据诸如“身高×1.5+体重×0.2”或“体重×3-身高×5”这样的复杂数学公式来进行分类，听起来麻烦且怪异。相比之下，我们更期望有一种直观且易于解释的方式来对同学们的体型进行分类。

图1. 最优 $k$ -means 聚类与可解释 $k$ -means 聚类的对比，以及可解释 $k$ -means 聚类的决策树。以 k=5 以及身高体重数据集为例。图来源于^[2]。

为了解决这一问题，Moshkovitz 等人^[2]提出了可解释聚类问题（Explainable Clustering），尝试利用决策树来构建聚类，从而大大提高了聚类的可解释性。以体型分类为例，我们可以考虑这样一种聚类方式：初始时，我们只有一个类，即整个数据集，然后选择一个特征维度（如身高）和一个合适的阈值 $T$ 。根据这个阈值，我们可以轻松地将数据集分为两类：一类是身高不超过 $T$ 的同学，另一类是身高超过 $T$ 的同学。接下来，我们递归地对子数据集进行相同的操作。也就是说，对于每一个子数据集，我们可以再选择一个特征维度（这次可以是体重或依然是身高）和一个新的阈值，然后再次进行划分。这样，我们不断地将数据集细分成更小的类，直到最终划分为 $k$ 类为止。在图1的中间图和右图，我们展示了一种可解释聚类的结果及其决策过程。借助决策树的分类方法，我们成功将聚类结果呈现得直观且易于理解。

不过，我们自然会提出一个问题：这样的聚类方法其效果如何呢？Moshkovitz 等人^[2]在提出可解释聚类问题的同时，也设计了一种构造可解释聚类的算法，其输出的聚类 $\mathcal{C}$ 的目标函数值不会超过最优聚类（不一定可解释）目标函数的 $O(k^2 )$ 倍，即 $\operatorname{cost} (\mathcal{C})\le O(k^2 )\cdot \operatorname{cost}(\mathcal{C}^*)$ 。同时，他们证明，在最坏情况下，任何可解释聚类的目标函数与最优聚类的目标函数的比值不小于 $\Omega(\log k)$ 。换句话说，如果我们追求聚类的可解释性，即通过决策树来构建聚类，我们可能在聚类质量上损失一个 $\Omega(\log k)$ 倍的代价。这个比值 $\frac{\operatorname{cost}(\mathcal{C})}{\operatorname{cost}(\mathcal{C}^*)}$ 被称为聚类的可解释性代价。

随后，研究者们不断努力，试图改进聚类的可解释性代价的上下界。随着研究的深入，一个简洁而高效的算法被提出：在每次分割一个类时，我们只需随机选择一个特征维度和阈值即可。Gupta 等人^[3]证明，这种随机分割策略可以将 $k$ -means 聚类的可解释性代价降低到 $O(k \log \log k)$ 。另一方面，Gamlath 等人^[4]通过构造困难实例，成功地将可解释性代价的下界提升至 $\Omega(k)$ 。这些突破使得 $k$ -means 聚类的可解释性代价的上下界差距大大缩小，现在仅仅相差一个 $\log \log k$ 因子。

聚类的可解释性代价概念自2020年被提出以来，便受到了计算机理论研究者们广泛的关注。在这里我们简要梳理了欧氏空间中 $k$ -means 聚类的可解释性代价的演进历程，回顾了其从最初较为粗略的 $O(k^2 )$ 上界与 $\Omega(\log ⁡k )$ 下界，到如今达到几乎精确的 $O(k\log \log k)$ 上界与 $\Omega(k)$ 下界。同时，其他聚类问题的可解释性代价也在持续研究中，例如欧氏空间中 $k$ -median 问题。Makarychev 和 Shan^[5]针对这一问题，给出了目前最优的上界 $O(\log^{3/2}⁡k)$ 和下界 $\Omega(\log ⁡k)$ ，然而，这一问题仍然存在着进一步改进和优化的空间。此外，还有一些研究从其他角度探索了可解释性代价，例如尝试通过删除少量数据点的方式，实现完全可解释的聚类，从而避免了产生额外的可解释代价^[6]。

参考文献

[1] Arthur, David, and Sergei Vassilvitskii. "k-means++: The advantages of careful seeding." SODA. Vol. 7. 2007.

[2] Moshkovitz, Michal, et al. "Explainable k-means and k-medians clustering." ICML 2020: 7055-7065.

[3] Gupta, Anupam, et al. "The price of explainability for clustering." FOCS 2023: 1131-1148.

[4] Gamlath, Buddhima, et al. "Nearly-tight and oblivious algorithms for explainable clustering." NeurIPS 2021: 28929-28939.

[5] Makarychev, Konstantin, and Liren Shan. "Near-optimal algorithms for explainable k-medians and k-means." ICML 2021: 7358-7367.

[6] Bandyapadhyay, Sayan, et al. "How to find a good explanation for clustering?" Artificial Intelligence 322 (2023): 103948.

文 | 楼家宁

图 | 朱成轩

本微信公众号所有内容，由北京大学前沿计算研究中心微信自身创作、收集的文字、图片和音视频资料，版权属北京大学前沿计算研究中心微信所有；从公开渠道收集、整理及授权转载的文字、图片和音视频资料，版权属原作者。本公众号内容原作者如不愿意在本号刊登内容，请及时通知本号，予以删除。

内容中包含的图片若涉及版权问题，请及时与我们联系删除

立夏 | 如何让聚类具有可解释性

评论