An Analysis of Dα seeding for k-means

One of the most popular clustering algorithms is the celebrated Dα seeding algorithm (also know as k-means++ when α=2) by Arthur and Vassilvitskii (2007), who showed that it guarantees in expectation an O(22α· log k)-approximate solution to the (k,α)-means cost (where euclidean distances are raised to the power α) for any α≥ 1. More recently, Balcan, Dick, and White (2018) observed experimentally that using Dα seeding with α>2 can lead to a better solution with respect to the standard k-means objective (i.e. the (k,2)-means cost). In this paper, we provide a rigorous understanding of this phenomenon. For any α>2, we show that Dα seeding guarantees in expectation an approximation factor of Oα left((gα)2/α· left(fracσmaxσminright)2-4/α· (minℓ,log k)2/αright) with respect to the standard k-means cost of any underlying clustering; where gα is a parameter capturing the concentration of the points in each cluster, σmax and σmin are the maximum and minimum standard deviation of the clusters around their means, and ℓ is the number of distinct mixing weights in the underlying clustering (after rounding them to the nearest power of 2). We complement these results by some lower bounds showing that the dependency on gα and σmax/σmin is tight. Finally, we provide an experimental confirmation of the effects of the aforementioned parameters when using Dα seeding. Further, we corroborate the observation that α>2 can indeed improve the k-means cost compared to D2 seeding, and that this advantage remains even if we run Lloyd's algorithm after the seeding.