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

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?

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

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