Improved algorithms for clustering with outliers

Qilong Feng, Zhen Zhang, Ziyun Huang, Jinhui Xu, Jianxin Wang

Research output: Chapter in Book/Report/Conference proceedingConference contribution

11 Scopus citations


Clustering is a fundamental problem in unsupervised learning. In many real-world applications, the to-be-clustered data often contains various types of noises and thus needs to be removed from the learning process. To address this issue, we consider in this paper two variants of such clustering problems, called k-median with m outliers and k-means with m outliers. Existing techniques for both problems either incur relatively large approximation ratios or can only efficiently deal with a small number of outliers. In this paper, we present improved solution to each of them for the case where k is a fixed number and m could be quite large. Particularly, we gave the first PTAS for the k-median problem with outliers in Euclidean space Rd for possibly high m and d. Our algorithm runs in O(nd(1 ε (k + m))(kε )O(1) ) time, which considerably improves the previous result (with running time O(nd(m + k)O(m+k) + (1 ε k log n)O(1))) given by [Feldman and Schulman, SODA 2012]. For the k-means with outliers problem, we introduce a (6 + ε)-approximation algorithm for general metric space with running time O(n(β 1 ε (k + m))k) for some constant β > 1. Our algorithm first uses the k-means++ technique to sample O(1 ε (k + m)) points from input and then select the k centers from them. Compared to the more involving existing techniques, our algorithms are much simpler, i.e., using only random sampling, and achieving better performance ratios.

Original languageEnglish (US)
Title of host publication30th International Symposium on Algorithms and Computation, ISAAC 2019
EditorsPinyan Lu, Guochuan Zhang
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959771306
StatePublished - Dec 2019
Event30th International Symposium on Algorithms and Computation, ISAAC 2019 - Shanghai, China
Duration: Dec 8 2019Dec 11 2019

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
ISSN (Print)1868-8969


Conference30th International Symposium on Algorithms and Computation, ISAAC 2019

All Science Journal Classification (ASJC) codes

  • Software


Dive into the research topics of 'Improved algorithms for clustering with outliers'. Together they form a unique fingerprint.

Cite this