2
$\begingroup$

Consider the setup of the $k$-means problem and assume that the data points are confined to $k$ balls of radius $\varepsilon$ while the pairwise distances between the centers of the balls are $> 2 \varepsilon$, and each ball contains the same number of points. It seems to me that it should be possible to show that the solution of the $k$-means problem puts all the centers in these balls, exactly one per each ball (in which case it is clear that each center will be the mean of the points in the corresponding ball). I have trouble showing this, but I feel that this has to be known. Any reference? or am I missing some additional necessary condition?

More precise statement: Let $B_2$ be the unit $\ell_2$ ball in $\mathbb R^d$ and consider datapoints $\{x_i, i=1,\dots,n\} \subset \mathbb R^d$ and (true) centers $\{v_1,\dots,v_k\} \subset \mathbb R^d$ such that

  • for each $i$, $x_i \in v_j + \varepsilon B_2$ for some $j \in [k]$, and
  • $\|v_j - v_\ell\|_2 > 2\varepsilon$ for all $j \neq \ell$, and
  • $|\{i:\; x_i \in v_j + \varepsilon B_2\}|$ is the same for all $j \in [k]$.

Let $\{v^*_1,\dots,v^*_k\}$ be an optimal solution to the k-means problem. We would like to show that $v^*_j \in v_{\pi(j)} + \varepsilon B_2$ for all $j \in [k]$ and some permutation $\pi : [k] \to [k]$.

(It would be nice if this can be extended to constant-factor approximate solutions of the k-means problem.)

Alternative formulation in terms of measure approximation (see Pollard 82): Let $\mu$ be a measure on $\mathbb R^d$ supported on a collection $S_1,\dots,S_k$ of disjoint sets. Let $\mathcal P_k$ be the collection of discrete measures on $\mathbb R^d$ with at most $k$ atoms (objects of the form $\sum_{j=1}^k \pi_j \,\delta_{v_j}$).

Assume that

  • Diameter of $S_j < 2\varepsilon$, for all $j$.
  • $S_j$ and $S_\ell$ are suitably separated (?) relative to $\varepsilon$.
  • $\mu(S_j)$ are equal for all $j \in [k]$.

Let $\mu^*_k$ be a solution of $\min_{\nu \in \mathcal P_k} W_2(\mu,\nu)$ where $W_2$ is the $2$-Wasserstein distance. Then $\mu^*_k$ will have exactly $k$ atoms one within each $S_j, j \in [k]$.

Improve this question
$\endgroup$
1

1 Answer 1

Reset to default
1
$\begingroup$

There are counterexamples in $\mathbb{R}^2$ under these conditions.

For $(d,k,n) = (2,2,4)$, place the balls such that they fit (neighborhoods of) the corners of a square. Here's such a configuration, with the K-means solution $(\theta_1,\theta_2)$ outside of the balls: Image.

Similarly, placing two balls at (center) distance $2+\delta$ (wlog $\varepsilon=1$) with $M$ and $m$ points in each ball as close to the other ball as possible and the remaining $M-m$ diametrically opposite has two (plausible) K-means assignments, at total cost $\frac{\delta^2}{4}(m+M)$ vs $M$. The first assignment places a center between (outside) the two balls and is optimal for $\delta \leq 2$ and sufficiently large $M$.

More restrictive bounds on the center distances, e.g. $\|v_j - v_\ell\|_2>4$, might work. It dismisses my counterexamples and has had some success when proving correctness of algorithms for K-means.

$\|v_j - v_\ell\|_2>4$ mentioned here:

https://arxiv.org/abs/1408.4045

https ://arxiv.org/abs/1309.3256

A different approach to restricting ball proximity is used here:

https ://arxiv.org/abs/1004.1823

Improve this answer
$\endgroup$
4
  • $\begingroup$ This is great! Thanks for the counterexample and references. I started suspecting 2 was not enough. $\endgroup$
    – passerby51
    Commented Jan 14, 2017 at 17:39
  • $\begingroup$ I actually did care about the worst case. On the other hand, it seems that the missing condition is uniformity of the distribution within balls. If the points are uniformly distributed within balls, and there are large numbers of them, it seems 2-separation could be enough with high probability. $\endgroup$
    – passerby51
    Commented Jan 14, 2017 at 17:46
  • $\begingroup$ @passerby51 All I can find on the worst case: By Lemma 6 in this chapter there exists a 2-approximation taking data points as centers, thus placing them within the balls. Perhaps this, coupled with some separation assumption, can be massaged to get an approximation with one data point in each ball. $\endgroup$
    – Sam Zackrisson
    Commented Jan 14, 2017 at 20:43
  • $\begingroup$ thanks. That book is really interesting. They also talk about approximation stability which is in fact what I am after. $\endgroup$
    – passerby51
    Commented Jan 23, 2017 at 18:56

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .