Timezone: »

 
Oral
Clustering Semi-Random Mixtures of Gaussians
Aravindan Vijayaraghavan · Pranjal Awasthi

Wed Jul 11 02:50 AM -- 03:00 AM (PDT) @ K11
in Clustering 1 »

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 robust model for k-means clustering that generalizes the Gaussian mixture model, and that we believe will be useful in identifying robust algorithms. 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 lower bound on the number of misclassified points incurred by any k-means clustering algorithm on the semi-random model.

[ PDF]  [ PDF]  [ Video] 

Author Information

Aravindan Vijayaraghavan (Northwestern University)
Pranjal Awasthi (Rutgers University)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors