2012/01/20 by Jaiswal, Ragesh, Kumar, Amit, Sen, Sandeep · 1 citation
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #I.5.3
paper · doi:10.48550/arxiv.1201.4206
Given a set of points P ⊂ ℝd, the k-means clustering problem is to find a set of k \em centers C = \c1,...,ck\, ci ∈ ℝd, such that the objective function ∑x ∈ P d(x,C)2, where d(x,C) denotes the distance between x and the closest center in C, is minimized. This is one of the most prominent objective functions that have been studied with respect to clustering. D2-sampling \citeArthurV07 is a simple non-uniform sampling technique for choosing points from a set of points. It works as follows: given a set of points P ⊆ ℝd, the first point is chosen uniformly at random from P. Subsequently, a point from P is chosen as the next sample with probability proportional to the square of the distance of this point to the nearest previously sampled points. D2-sampling has been shown to have nice properties with respect to the k-means clustering problem. Arthur and Vassilvitskii \citeArthurV07 show that k points chosen as centers from P using D2-sampling gives an O(logk) approximation in expectation. Ailon et. al. \citeAJMonteleoni09 and Aggarwal et. al. \citeAggarwalDK09 extended results of \citeArthurV07 to show that O(k) points chosen as centers using D2-sampling give O(1) approximation to the k-means objective function with high probability. In this paper, we further demonstrate the power of D2-sampling by giving a simple randomized (1 + ε)-approximation algorithm that uses the D2-sampling in its core.