K-Means++ & K Selection

K-Means++ is an improved initialization for K-Means: the first centroid is chosen uniformly at random, then each subsequent centroid is sampled with probability proportional to the squared distance to the nearest already-chosen centroid, where $D(x) = \min_{k} \Vert x - \mu_k \Vert$: $P(x) = \frac{D(x)^2}{\sum_{x'} D(x')^2}$.Squared-distance sampling spreads the initial centroids apart: the expected objective satisfies $\mathbb{E}[J] \le 8(\ln K + 2) \, J_{\mathrm{OPT}}$, bounding the worst local optimum within $O(\log K)$ of the optimal — at the cost of just one extra $O(nKd)$ round of distance computation.Choosing K: the elbow method (WCSS inflection point) and the silhouette score $s = \frac{b - a}{\max(a, b)}$ ($a$ = mean intra-cluster distance, $b$ = mean distance to the nearest other cluster; closer to 1 is better); for outlier-robust clustering use K-Medoids (centroids restricted to actual data points).

the default initialization for any K-Means run (scikit-learn defaults to k-means++) and a common initialization for GMM EM; interviews often ask for the probability formula and why squared distance beats uniform sampling.

uniform random initialization can place all centroids in dense regions, trapping the algorithm in poor local optima; K-Means++ probabilistically spreads the initial centroids, achieving an $O(\log K)$ approximation in expectation for about the cost of one extra iteration — the classic time-quality tradeoff.

Write the K-Means++ sampling probability $P(x) = \frac{D(x)^2}{\sum_{x'} D(x')^2}$ and explain $D(x)$; why squared distance rather than plain distance?

How much does K-Means++ improve over random initialization in expectation? What does the $\mathbb{E}[J] \le 8(\ln K + 2) J_{\mathrm{OPT}}$ bound mean?

How do the elbow method and silhouette score choose K? Range and interpretation of $s = \frac{b - a}{\max(a, b)}$?

Why is K-Means outlier-sensitive? How does K-Medoids mitigate it? Complexity comparison with K-Means?

What extra time does K-Means++ cost? How is the first centroid chosen? vs multiple random restarts?