How does k-means++ initialization work?
mediumAnswer
- Pick the first centroid uniformly at random.
- For each subsequent centroid, sample point x with probability proportional to where D(x) is the distance to the nearest already-chosen centroid.
- Result: centroids spread out over the data → far better starting point than random.
- Expected O(log k) approximation to optimal SSE.
- Default in scikit-learn and Spark MLlib.
Check yourself — multiple choice
- Uniform random init
- Sample next centroid with probability ∝ → spread-out init; O(log k) approximation guarantee
- Same as random
- Only for GMM
k-means++: sampling for spread-out init; O(log k) approximation.
#clustering
Practise Unsupervised Learning
214 interview questions in this topic.