When do birds of a feather flock together? k-Means, proximity, and conic programming
When do birds of a feather flock together? k-Means, proximity, and conic programming
复制标题
DOI：
10.1007/s10107-018-1333-x
复制
发表时间：
2017-10
影响因子：
2.7
通讯作者：
Xiaodong Li;Yang Li;Shuyang Ling;T. Strohmer;Ke Wei
中科院分区：
文献类型：
--
作者：
Xiaodong Li;Yang Li;Shuyang Ling;T. Strohmer;Ke Wei
给定一组数据，一个中心目标是根据各个对象之间的相似性将它们分组到集群中。最流行和广泛使用的方法之一是平均值，尽管计算困难，以找到其全局最小值。我们研究和比较不同的凸松弛的性质，将它们与相应的邻近条件，最初由库马尔和Kannan介绍的想法。利用锥对偶理论，我们提出了一个改进的邻近条件，在此条件下，Peng-Wei松弛的k-均值可以准确地恢复潜在的聚类。我们的邻近条件改善后，库马尔和Kannan和Awashti和Sheffet，接近条件建立projectivek手段。此外，我们还为Peng-Wei松弛的精确性提供了一个必要的邻近条件。对于相同的集群大小的特殊情况下，我们建立了一个不同的和完全本地化的邻近条件下，Amini-Levina松弛产生精确的聚类，从而解决了一个开放的问题Awasthi和Sheffet在平衡的情况下。我们的框架不仅是确定性的和无模型的，但也有一个明确的几何意义，允许进一步的分析和推广。此外，它可以方便地应用于分析各种数据生成模型，如随机球模型和高斯混合模型。利用该方法，我们改进了目前随机球模型的最小分离界，取得了高斯混合模型学习的最新成果。
Given a set of data, one central goal is to group them into clusters based on some notion of similarity between the individual objects. One of the most popular and widely-used approaches isk-means despite the computational hardness to find its global minimum. We study and compare the properties of different convex relaxations by relating them to corresponding proximity conditions, an idea originally introduced by Kumar and Kannan. Using conic duality theory, we present an improved proximity condition under which the Peng–Wei relaxation ofk-means recovers the underlying clusters exactly. Our proximity condition improves upon Kumar and Kannan and is comparable to that of Awashti and Sheffet, where proximity conditions are established for projectivek-means. In addition, we provide a necessary proximity condition for the exactness of the Peng–Wei relaxation. For the special case of equal cluster sizes, we establish a different and completely localized proximity condition under which the Amini–Levina relaxation yields exact clustering, thereby having addressed an open problem by Awasthi and Sheffet in the balanced case. Our framework is not only deterministic and model-free but also comes with a clear geometric meaning which allows for further analysis and generalization. Moreover, it can be conveniently applied to analyzing various data generative models such as the stochastic ball models and Gaussian mixture models. With this method, we improve the current minimum separation bound for the stochastic ball models and achieve the state-of-the-art results of learning Gaussian mixture models.