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.

Test Your Knowledge: Practice Questions for "K-Means++ & K Selection"

Single choice pitfall questions with instant feedback and mistake tracking.