On the k-Means/Median Cost Function

In this work, we study the k-means cost function. Given a dataset X subseteq ℝd and an integer k, the goal of the Euclidean k-means problem is to find a set of k centers C subseteq ℝd such that Phi(C, X) equiv sumx ∈ X minc ∈ C ||x - c||2 is minimized. Let Delta(X,k) equiv minC subseteq ℝd Phi(C, X) denote the cost of the optimal k-means solution. For any dataset X, Delta(X,k) decreases as k increases. In this work, we try to understand this behaviour more precisely. For any dataset X subseteq ℝd, integer k ≥ 1, and a precision parameter varepsilon > 0, let L(X, k, varepsilon) denote the smallest integer such that Delta(X, L(X, k, varepsilon)) ≤ varepsilon · Delta(X,k). We show upper and lower bounds on this quantity. Our techniques generalize for the metric k-median problem in arbitrary metric spaces and we give bounds in terms of the doubling dimension of the metric. Finally, we observe that for any dataset X, we can compute a set S of size O left(L(X, k, varepsilon/c) right) using D2-sampling such that Phi(S,X) ≤ varepsilon · Delta(X,k) for some fixed constant c. We also discuss some applications of our bounds.