k-means++ algorithm and outliers

Question

It is well known that k-means algorithm suffers in the presence of outliers. k-means++ is one effective method for cluster center initalization. I was going through the PPT by the founders of the method, Sergei Vassilvitskii and David Arthur http://theory.stanford.edu/~sergei/slides/BATS-Means.pdf (slide 28) which shows that the cluster center initialization is not affected by outlier as seen below.

As per the k-means++ method, the farthermost points are more likely to be the initial centers. In this way the outlier point (the rightmost point) must also be an initial cluster centroid. What is the explanation for the figure?

Answer 1

In K-Means++ method, the first centroid (let's call C1) can be among any of the points. In other words, all points have an equal chance of getting selected as first centroid in the initialization stage. Now, once the first centroid is selected, the second centroid is selected in such as manner that, a probability of any point in the dataset (barring C1 of course) to get selected as second centroid is proportional to its squared-distance from the first centroid. Likewise, this logic extends for selecting the rest of the centroids among the data points in the initialization stage. In general, the probability that a point gets selected as centroid is proportional to its distance from the nearest centroid. In this way, the probabilistic approach in K-means++ as opposed to the random selection in K-Means ensures that the centroids selected in the initialization stage are as far as possible.

Now coming to your question, K-means++ is still sensitive to the outliers. One workaround could be removing outliers using techniques like LOF, RANSAC, simple univariate box-plots, etc. before clustering. The other I think could be reinitialize the Centroids in case you are getting sub-optimal performance in the first attempt.

Answer 2

Yes, the outlier os more likely to be picked. But there are also many more inliers, the chance of choosing one of them is also substantial. Say you have one outlier that is 10x farther, then it is 100x more likely to be picket than one inlier. If you have 100 inliers, the chances are about 50%, and if you have 1000 inliers, the chance of picking the outlier is about 10%.

But all in all I'd say k-means++ is probably more likely to pick outliers as initial centers (in above example, random would pick it at 1% resp. 0.1%), and thus probably more sensitive to outliers (and in fact, many people report little improvement with k-means++). Yet it does not make much of a difference: any k-means method is affected, because they all optimize the same objective. And sum-of-squares is an objective sensitive to outliers, independently of how you optimize. Because of the problem being in the objective, picking the outlier as center may yield a "better" result. The global optimum may look like this!

Answer 3

This seems to be explained on slide 27.

They propose choosing the first cluster centroid randomly, as per classic k-means. But the second is chosen differently. We look at each point x and assign it a weight equal to the distance between x and the first chosen centroid, raised to a power alpha. Alpha can take several interesting values.

If alpha is 0, we have the classic k-means algorithm, because all points have weight 1, so they're all equally likely to be chosen.

If alpha is infinity (or, in practice, a very large number) we have the Furthest point method, where the furthest point has a very large weight, that makes it very likely to be picked. As seen on slides 24-26, this makes it sensitive to outliers.

They propose setting alpha to 2. This gives a nice probability of picking points farther away from the first picked centroid, but not automatically picking the furthest. This gives their method, k-means++, the nice property of being less sensitive to outliers.