# An Analysis of Dα seeding for k-means

arXiv: https://arxiv.org/abs/2310.13474 · HTML: https://mlsanity.com/paper/2310.13474/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 6 of its 32 references that are in the map.
- First posted on arXiv 20 Oct 2023.

## Builds on (most cited first, 6 of 6)

- [Data-Driven Clustering via Parameterized Lloyd's Families](https://mlsanity.com/paper/1809.06987/) (2018)
- [k-means++: few more steps yield constant approximation](https://mlsanity.com/paper/2002.07784/) (2020)
- [Improved Guarantees for k-means++ and k-means++ Parallel](https://mlsanity.com/paper/2010.14487/) (2020)
- [Fast and Accurate k-means++ via Rejection Sampling](https://mlsanity.com/paper/2012.11891/) (2020)
- [A Constant-Factor Bi-Criteria Approximation Guarantee for k-means++](https://mlsanity.com/paper/1605.04986/) (2016)
- [A Nearly Tight Analysis of Greedy k-means++](https://mlsanity.com/paper/2207.07949/) (2022)

## Abstract (arXiv)

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.