Korea Academic Institute of Science and Technology

We study the classic kk-means/median clustering, which are fundamentalproblems in unsupervised learning, in the setting where data are partitionedacross multiple sites, and where we are allowed to discard a small portion ofthe data by labeling them as outliers. We propose a simple approach based onconstructing small summary for the original dataset. The proposed method istime and communication efficient, has good approximation guarantees, and canidentify the global outliers effectively. To the best of our knowledge, this isthe first practical algorithm with theoretical guarantees for distributedclustering with outliers. Our experiments on both real and synthetic data havedemonstrated the clear superiority of our algorithm against all the baselinealgorithms in almost all metrics.