One of the most popular clustering algorithms is the celebrated $D^\alpha$
seeding algorithm (also know as $k$-means++ when $\alpha=2$) by Arthur and
Vassilvitskii (2007), who showed that it guarantees in expectation an
$O(2^{2\alpha}\cdot \log k)$-approximate solution to the ($k$,$\alpha$)-means
cost (where euclidean distances are raised to the power $\alpha$) for any
$\alpha\ge 1$. More recently, Balcan, Dick, and White (2018) observed
experimentally that using $D^\alpha$ seeding with $\alpha>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 $\alpha>2$, we show that $D^\alpha$ seeding guarantees in expectation an
approximation factor of $$ O_\alpha \left((g_\alpha)^{2/\alpha}\cdot
\left(\frac{\sigma_{\mathrm{max}}}{\sigma_{\mathrm{min}}}\right)^{2-4/\alpha}\cdot
(\min\{\ell,\log k\})^{2/\alpha}\right)$$ with respect to the standard
$k$-means cost of any underlying clustering; where $g_\alpha$ is a parameter
capturing the concentration of the points in each cluster,
$\sigma_{\mathrm{max}}$ and $\sigma_{\mathrm{min}}$ are the maximum and minimum
standard deviation of the clusters around their means, and $\ell$ 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_\alpha$ and
$\sigma_{\mathrm{max}}/\sigma_{\mathrm{min}}$ is tight.
Finally, we provide an experimental confirmation of the effects of the
aforementioned parameters when using $D^\alpha$ seeding. Further, we
corroborate the observation that $\alpha>2$ can indeed improve the $k$-means
cost compared to $D^2$ seeding, and that this advantage remains even if we run
Lloyd's algorithm after the seeding.

研究论文通过对聚类算法和 $D^\alpha$ 种子算法的应用，证明了使用 $D^\alpha$ 种子算法在 $k$-means 目标函数方面具有更好的性能，并通过实验证实了这种优势即使在种子算法之后使用 Lloyd's 算法时依然存在。

关于 $k$-means 聚类中 $D^α$ 种子的分析

An Analysis of $D^α$ seeding for $k$-means

We study the problem of explainable clustering in the setting first
formalized by Dasgupta, Frost, Moshkovitz, and Rashtchian (ICML 2020). A
$k$-clustering is said to be explainable if it is given by a decision tree
where each internal node splits data points with a threshold cut in a single
dimension (feature), and each of the $k$ leaves corresponds to a cluster. We
give an algorithm that outputs an explainable clustering that loses at most a
factor of $O(\log^2 k)$ compared to an optimal (not necessarily explainable)
clustering for the $k$-medians objective, and a factor of $O(k \log^2 k)$ for
the $k$-means objective. This improves over the previous best upper bounds of
$O(k)$ and $O(k^2)$, respectively, and nearly matches the previous $\Omega(\log
k)$ lower bound for $k$-medians and our new $\Omega(k)$ lower bound for
$k$-means. The algorithm is remarkably simple. In particular, given an initial
not necessarily explainable clustering in $\mathbb{R}^d$, it is oblivious to
the data points and runs in time $O(dk \log^2 k)$, independent of the number of
data points $n$. Our upper and lower bounds also generalize to objectives given
by higher $\ell_p$-norms.

提出了一个算法，用于在 $k$-medians 目标和 $k$-means 目标下输出可解释的聚类，与最佳聚类最多相差 $O (\log^2 k)$ 和 $O (k\log^2 k)$ 的因子，算法时间为 $O (dk\log^2 k)$ 。