混合k-聚类：结合k-均值和k-中心算法

《ACM Transactions on Computation Theory》：Hybrid k-Clustering: Blending k-Median and k-Center

本文提出混合k-聚类模型，结合k-中心与k-中位数方法，通过放置k个半径为(1+ε)r的闭球最小化未被覆盖点的距离。当r=0时退化为k-中位数，完全覆盖时为k-中心。该双标准近似算法在O(k^d/ε^d × n)时间内实现，是目前该问题的最优解。

　　

摘要

我们提出了一种新的聚类模型，该模型结合了两种著名的聚类方法：k-中心聚类和k-中位数聚类。在混合k-聚类问题中，给定一组点集$R^d$、一个整数k以及一个非负实数r，我们的目标是将半径为r的k个闭球放置到适当的位置，以最小化未被这些球覆盖的点到最近球的距离之和。等价地，我们寻求在欧几里得空间中找到一个最优的L₁拟合，使得这k个半径为r的球能够最好地拟合这组点。当r = 0时，该模型对应于k-中位数聚类；当距离之和为零时，表示所有点都被完全覆盖，此时模型为k-中心聚类。

我们的主要成果是一种双标准近似算法，对于给定的ε > 0，该算法能够生成半径为(1 + ε)r的混合k-聚类结果。该算法的代价最多为最优解的1 + ε倍，并且其运行时间复杂度为$2^{(kd/\epsilon {)}^{O\left(1\right)}}?n^{O\left(1\right)}$。值得注意的是，考虑到已知的k-中心聚类和k-中位数聚类的下界，我们的双标准近似方法是混合k-聚类问题的最佳可能结果。