Clustering in High Dimensions
Mihai Bâdoiu · 2003
In this thesis we show that, for several clustering problems, we can extract a small set of points, so that, using these core-sets, we can approximate clustering efficiently. The cardinality of these core-sets is independent of the dimension. Using these sets, we develop a (1 + ε)-approximation algorithm for the k-center clustering problem (with or without outliers)and the k-median clustering problem in Euclidean space. The running time of our algorithm has linear dependency on the number of points and in the dimension, and exponential dependency on 1/ε and k. Our algorithm runs substantially faster than the previously known algorithms. We present a (1 + ε)-approximation algorithm for the 1-cylinder clustering problem. We show how to quickly construct small core-sets and the existence of optimal core-sets. We also present experimental results showing that in practice these core-sets are smaller than in the