K-mean++ initialization algorithm alternative

Question

I got this question as an exercise, and I frankly don't know where to begin:

Consider the deterministic variant of the k−means++ algorithm where the set of initial centroids are selected in the following way. Let $X$ be a set of points in $\mathbb R^d$ given in input. The first centroid is chosen arbitrarily in $X$. Then at step $t$, given the set of centroids $C_t = \{ c_1, \dots, c_t \}$, $(1 ≤ t ≤ k − 1)$ selected up to step t, we select the point at maximum distance from the centroids in $C_t$. Formally, we choose the point $p \in X$ such that $\min_{c \in C_t} d(c, p)$ is maximum (if there are multiple choices we pick one of them arbitrarily). Give an example where such a variant of k-means++ does not perform well, i.e. it computes a set of centroids with SSE much larger than the optimum solution. Compare the performance of such a variant of k-means++ with the original k-means++ algorithm.

Answer 1

This assignment (?) is nonsense.

First of all, the "deterministic variant of k-means++" is not deterministic, lol: the first center is chosen at random. Then, it is not desirable to be deterministic (because you want to run k-means multiple times, and get different results). Secondly this is not k-means++ anymore. Instead, it is the "farthest points" heuristic. The whole idea of k-means++ is to be likely to choose a point from a far-away-cluster, and k-means++ avoids always choosing the farthest point, but tries to choose from far-away clusters.! So whoever wrote that assignment did not understand the theory of k-means++. He also did not understand that you want randomness to play a role with k-means.

Let me clarify this last bit a bit more. First of all, let's assumdße the data contains clusters (otherwise, we would not be clustering, would we?). Thus we assume there is a set of points (= cluster) that is approximately at the same distance of the cluster. But we have many of these points. If these n points each have weight approximately a, and there is an outlier farther away with weight b, then k-means will because of n*a>>b still be much more likely to choose one of the clusters point (= a good starting point) rather than the outlier (= a bad starting point).

With this suggested "deterministic" variant, the key mechanism of k-means++ is destroyed. Instead, it now tends to choose outliers, i.e. bad starting points.

Answer 2

It'll pretty much underperform classical k means in any dataset. By the sound of it if you start with two clusters of points, then your first centroid is a random point that'll define the first cluster and the second point will be somewhere on the very edge of the other cluster. Clearly centroids are better when they are chosen somewhere inside the two clusters