1
$\begingroup$

I'm learning the initialization methods for Lloyd's algorithm. And I have a hard thing finding examples where Kmeans++ works better than Gonzalez and where the reverse is true so Gonzalez works better than Kmeans++. Does anyone have an example input (Pointset and value k) for these two scenarios?

$\endgroup$
3
  • 1
    $\begingroup$ So in all examples you tried, both worked exactly as well? $\endgroup$ May 16, 2021 at 15:13
  • $\begingroup$ @InuyashaYagami imgur.com/k4wPiH3 Here is the Gonzalez algorithm $\endgroup$ May 16, 2021 at 16:54
  • $\begingroup$ @InuyashaYagami I mean which initializations results in better clustering(with lloyd's algorithm), so lower cost. $\endgroup$ May 16, 2021 at 16:56

1 Answer 1

2
$\begingroup$

Partial Answer:

Let us construct an instance where k-means++ initialization performs better than the Gonzalez initialization.

Consider the real line. Place $n$ points at the origin, i.e., position $0$. Place $n$ points at the position $1$. Lastly, place $1$ point at the position $n^{1/4}$. Let us cluster this pointset with $2$ clusters, i.e., $k = 2$.

In the optimal clustering, one center is placed at each of the two positions $0$ and $1$. The optimal k-means cost would be $\Theta(\sqrt{n})$ since the cost of $2n$ points at positions $0$ and $1$ is exactly $0$ and the cost of point at position $n^{1/4}$ is at most $\sqrt{n}$.

With the Gonzalez algorithm, only the following two center sets are possible (you can try this your own):

  1. Center set where one center is at position $0$ and the other at $n^{1/4}$
  2. Center set where one center is at position $1$ and the other at $n^{1/4}$

Without loss of generality, after this initialization, Lloyd's algorithm will cluster the points at positions $0$ and $1$ within the same cluster. And, the point at position $n^{1/4}$ would be clustered in a different cluster (singelton cluster). The $k$-means cost would be $\Theta(n)$.

With the k-means++ algorithm, the first center is chosen uniformly at random. With the high probability, the center would be chosen from positions $0$ or $1$. Without the loss of generality, suppose the first center is chosen from position $0$. Then, the probability that the second center will be chosen from position $1$ is $n/(n+\sqrt{n}) \geq 1/2$. And, the probability that the second center will be chosen from position $n^{1/4}$ is at most $\sqrt{n}/(n+\sqrt{n}) \leq 1/(2\sqrt{n})$. As you can see, the second center would be chosen from position $1$ with a high probability.

Therefore, with high probability, after this initialization, the $k$-means algorithm would open centers at positions $0$ and $1$. And, the $k$-means cost would be $\Theta(\sqrt{n})$. This cost is better than the cost with the Gonsalez algorithm that had cost $\Theta(n)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.