Initializations methods for lloyds algorithm (Kmeans++ vs Gonzalez)

Question

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?

Answer 1

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)$.