On the k-Means/Median Cost Function

Abstract

In this work, we study the $k$-means cost function. Given a dataset $X\subseteq {\mathbb{R}}^d$ and an integer $k$, the goal of the Euclidean $k$-means problem is to find a set of $k$ centers $C\subseteq {\mathbb{R}}^d$ such that $\hat{I}¦(C,X)\equiv {\sum }_{x\in X}{\min }_{c\in C}||x-c|{|}^2$ is minimized. Let $\hat{I}”(X,k)\equiv {\min }_{C\subseteq {\mathbb{R}}^d}\hat{I}¦(C,X)$ denote the cost of the optimal $k$-means solution. For any dataset $X$, $\hat{I}”(X,k)$ decreases as $k$ increases. In this work, we try to understand this behaviour more precisely. For any dataset $X\subseteq {\mathbb{R}}^d$, integer $k\ge 1$, and a precision parameter $\epsilon >0$, let $L(X,k,\epsilon )$ denote the smallest integer such that $\hat{I}”(X,L(X,k,\epsilon ))\le \epsilon \cdot \hat{I}”(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,\epsilon /c)\right)$ using $D^2$-sampling such that $\hat{I}¦(S,X)\le \epsilon \cdot \hat{I}”(X,k)$ for some fixed constant $c$. We also discuss some applications of our bounds.

This update includes minor improvements and a new section on Dimension Estimation