k-means–: A unified approach to clustering and outlier detection

We present a unified approach for simultaneously clustering and discovering outliers in data. Our approach is formalized as a generalization of the k-MEANS problem. We prove that the problem is NP-hard and then present a practical polynomial time algorithm, which is guaranteed to converge to a local optimum. Furthermore we extend our approach to all distance measures that can be expressed in the form of a Bregman divergence. Experiments on...