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.

Initialize two centers0 and 10Assign nearest points{1, 2} to 0; {8, 9} to 10Move to group means1.5 and 8.5Assign againSame groups; centers stay put
On points 1, 2, 8 and 9, one center update reduces total squared distance from 10 to 1.

How it works

  1. Choose $k$ and initialize centers, preferably with spread-out seeds.
  2. Assign every point to its nearest center using squared Euclidean distance.
  3. Replace each center with the mean of its assigned points, handling empty clusters explicitly.
  4. Repeat until assignments stabilize or improvement is small.
  5. 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)

Learn it

Interview questions about k-means