Clustering Semi-Random Mixtures of Gaussians
Clustering Semi-Random Mixtures of Gaussians
复制标题
DOI：
--
复制
发表时间：
2017-11
期刊：
影响因子：
--
通讯作者：
Pranjal Awasthi;Aravindan Vijayaraghavan
中科院分区：
文献类型：
--
作者：
Pranjal Awasthi;Aravindan Vijayaraghavan
高斯混合模型（GMM）是$ k $ - 均值聚类问题最广泛使用的统计模型，并形成了用于机器学习和数据分析中聚类的流行框架。在本文中，我们提出了一个天然的半随机模型，用于$ k $ - 均值聚类，该模型概括了高斯混合模型，并且我们认为这将有助于识别可靠的算法。在我们的模型中，允许半随机对手对高斯混合模型产生的数据进行任意“单调”或有用的更改。我们的第一个贡献是一种多项式时间算法，该算法可证明将基础真相恢复到小分类误差W.H.P.，假设组件之间有一定的分离。也许令人惊讶的是，我们分析的算法是流行的劳埃德（Lloyd）的算法，用于$ k $ - 均值聚类，这是实践中选择方法。我们的第二个结果通过在半随机模型上给出任何$ k $ - 均值聚类算法所产生的错误分类点的数量来提供几乎匹配的信息理论下限。
Gaussian mixture models (GMM) are the most widely used statistical model for the $k$-means clustering problem and form a popular framework for clustering in machine learning and data analysis. In this paper, we propose a natural semi-random model for $k$-means clustering that generalizes the Gaussian mixture model, and that we believe will be useful in identifying robust algorithms. In our model, a semi-random adversary is allowed to make arbitrary "monotone" or helpful changes to the data generated from the Gaussian mixture model. Our first contribution is a polynomial time algorithm that provably recovers the ground-truth up to small classification error w.h.p., assuming certain separation between the components. Perhaps surprisingly, the algorithm we analyze is the popular Lloyd's algorithm for $k$-means clustering that is the method-of-choice in practice. Our second result complements the upper bound by giving a nearly matching information-theoretic lower bound on the number of misclassified points incurred by any $k$-means clustering algorithm on the semi-random model.