Classic machine learning
K-means
Like choosing meeting spots and sending everyone to the closest one, K-means groups points around centers. It alternates between assigning points and moving each center to its group mean. It seeks to minimize squared distance within clusters, without using labels.
How it works
- Choose $k$ and initialize centers, preferably with spread-out seeds.
- Assign every point to its nearest center using squared Euclidean distance.
- Replace each center with the mean of its assigned points, handling empty clusters explicitly.
- Repeat until assignments stabilize or improvement is small.
- Run multiple initializations and compare the resulting objective values.
$$\min_{\mu_1,\ldots,\mu_k}\sum_{i=1}^{n}\min_j\|x_i-\mu_j\|_2^2$$
The knobs that matter
- n_clusters
- More centers reduce training inertia but may split meaningful groups.
- Initialization and restarts
- Different seeds can reach different local solutions.
- Feature scaling
- Large-scale features otherwise dominate Euclidean distance.
What interviewers ask
- How do the assignment and center-update steps work?
- How would you choose the number of clusters?
- Why can different initializations give different answers?
- How is K-means different from K-nearest neighbors?
Common mistakes
- Reading decreasing inertia as proof that a larger k is always better.
- Expecting spherical distance-based clusters to capture arbitrary shapes or ignore outliers.
When to use it
Use it for compact groups in a meaningful Euclidean feature space. Avoid relying on it for curved clusters, very unequal spreads, or data dominated by outliers.
Implement it (9 problems)
- K-Means ClusteringFreeMediumSolve
- K-Means Clustering From ScratchFreeMediumSolve
- K-Means++ InitializationProMediumSolve
- Mini-Batch K-MeansProMediumSolve
- Elbow Method for K-MeansProMediumSolve