Clustering Stable Instances of Euclidean k-means
Clustering Stable Instances of Euclidean k-means
复制标题
DOI：
--
复制
发表时间：
2017-12
期刊：
影响因子：
--
通讯作者：
Aravindan Vijayaraghavan;Abhratanu Dutta;Alex L. Wang
中科院分区：
文献类型：
--
作者：
Aravindan Vijayaraghavan;Abhratanu Dutta;Alex L. Wang
Euclidean K-均值问题可以说是机器学习中最广泛研究的聚类问题。尽管K-均值目标在最糟糕的情况下是NP的目标，但从业者在将劳埃德算法等启发式方法应用于此问题方面取得了巨大的成功。为了解决此断开连接，我们研究了以下问题：现实世界实例的哪些属性将使我们能够设计有效的算法并证明保证找到最佳聚类？我们认为一种天然概念称为加性扰动稳定性，我们认为捕获了许多实际实例。稳定的实例具有独特的最佳K均值解决方案，即使每个点都受到稍微扰动（在欧几里得距离）时也不会改变。这捕获了K-均值最佳解决方案应耐受测量错误和点不确定性的属性。我们设计了有效的算法，可证明，对于稳定的累加扰动的实例，可以恢复最佳聚类。当实例有一些额外的分离时，我们将显示一种有效的算法，并具有可证明的保证，这对离群值也很强。我们通过研究实际数据集中的稳定性量来补充这些结果，并证明我们的算法在这些基准数据集上的性能很好。
The Euclidean k-means problem is arguably the most widely-studied clustering problem in machine learning. While the k-means objective is NP-hard in the worst-case, practitioners have enjoyed remarkable success in applying heuristics like Lloyd's algorithm for this problem. To address this disconnect, we study the following question: what properties of real-world instances will enable us to design efficient algorithms and prove guarantees for finding the optimal clustering? We consider a natural notion called additive perturbation stability that we believe captures many practical instances. Stable instances have unique optimal k-means solutions that do not change even when each point is perturbed a little (in Euclidean distance). This captures the property that the k-means optimal solution should be tolerant to measurement errors and uncertainty in the points. We design efficient algorithms that provably recover the optimal clustering for instances that are additive perturbation stable. When the instance has some additional separation, we show an efficient algorithm with provable guarantees that is also robust to outliers. We complement these results by studying the amount of stability in real datasets and demonstrating that our algorithm performs well on these benchmark datasets.