Skip to content
Tutorials Center
My learning

Topics

Lesson 62 of 111 ยท Unsupervised Learning

k-Means Clustering

Understand the k-means algorithm step by step, build it in NumPy, pick k with the elbow method and silhouette score, and learn where k-means fails.

k-means is the workhorse of clustering. You tell it how many groups you want, k, and it returns k centroids (the average position of each group) and assigns every row to its nearest centroid. It is fast, simple and scales to millions of rows, which is why it appears in customer segmentation, image color reduction and as a preprocessing step for other models.

It also makes strong assumptions: groups are round, similar in size and spread, and you already know k. This lesson shows how the algorithm works, how to choose k when you do not know it, and how to recognize the situations where k-means gives confident but wrong answers. If you have not yet read the basics, start with Clustering Basics.

The algorithm in four steps

The standard algorithm is named after Stuart Lloyd. It alternates two simple moves until nothing changes:

  1. Initialize: pick k starting centroids.
  2. Assign: give each point to its nearest centroid.
  3. Update: move each centroid to the mean of the points assigned to it.
  4. Repeat steps 2 and 3 until the assignments stop changing.

The quantity k-means tries to make small is the inertia, also called the within-cluster sum of squares: the sum, over all points, of the squared distance to the centroid of their cluster. Each assign step and each update step can only lower the inertia or leave it unchanged, so the algorithm always converges. It converges to a local minimum, though, not necessarily the best one, and the starting centroids decide which one you reach.

One loop, repeated

Initialize Pick k starting centers.
Assign Each point joins its nearest center.
Update Move each center to its group mean.
Repeat Stop when nothing changes.

Inertia never goes up, so the loop always ends.

1 / 2

Here is the whole algorithm in about fifteen lines of NumPy, compared against scikit-learn's KMeans on the same data.

Python k-means from scratch

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Individual starts can end at very different inertia values: some get stuck in a poor local minimum. Keeping the best of ten, exactly what n_init does, gives the same clustering as scikit-learn (the centers match, only their order may differ). The next section shows how to make bad starts rarer.

Initialization and k-means++

Because k-means only finds a local minimum, a bad start can give a bad answer: two centroids land inside one real group and one centroid has to cover two groups. Two remedies are built into KMeans:

  • k-means++ (init="k-means++", the default) chooses the first centroid at random and each later centroid with probability proportional to its squared distance from the nearest centroid already chosen. Starting centroids tend to be spread out, which makes bad local minima much rarer.
  • Restarts (n_init) run the whole algorithm several times from different starts and keep the lowest inertia. The default n_init="auto" uses 1 run with k-means++ and 10 with random initialization.
Python Random starts versus k-means++

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Each run is a single start (n_init=1) so you can see the spread. With random starts 20 of the 30 runs end clearly worse than the best solution (inertia more than 20% above it); with k-means++ only 5 do, and its worst run is much better. In everyday use, keep the defaults and raise n_init if your results look unstable.

Choosing k

Often you do not know how many groups there are. Inertia alone cannot tell you, because it always decreases as k grows (with k equal to the number of rows it is zero). Two common tools:

  • The elbow method: plot inertia against k and look for the bend where adding another cluster stops helping much. It is a judgment call and some curves have no clear elbow.
  • The silhouette score: for each point, compare the average distance to its own cluster (a) with the average distance to the nearest other cluster (b). The silhouette is (b - a) / max(a, b), between -1 and 1. Higher is better, and you average it over all points. Pick the k where the average peaks.
Python Elbow and silhouette

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The data has four true groups. The inertia curve drops steeply until k=4 (from about 3,000 at k=3 to about 360) and then flattens, and the silhouette peaks at 4 (about 0.84). When the two methods agree you can be fairly confident; when they disagree, prefer the one that matches your purpose (for example, five marketing segments may be all your team can act on). Evaluating Clusters adds more scores.

Fit the scaler on the data you cluster and keep it. If you later assign new rows with predict, transform them with the same scaler first, exactly as you would in a pipeline.

Big data: MiniBatchKMeans

Standard k-means passes over all data on every iteration. MiniBatchKMeans updates the centroids using small random batches (default 1,024 rows), which is much faster on large data and also supports partial_fit for streams. The price is a slightly higher inertia.

Python MiniBatchKMeans versus KMeans

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

In our run the mini-batch inertia was about 9% higher than the full version, and it finished in well under half the time. Exact times depend on the machine, and the gap grows with the data size.

Where k-means fails

k-means assigns each point to the nearest centroid, so its cluster boundaries are always straight lines between centroids. This leads to predictable failures:

  • Non-round shapes: crescents, rings and long thin groups get cut apart.
  • Different spreads: a tight cluster next to a wide one gets part of the wide one stolen.
  • Different sizes: the objective splits big clusters and merges small ones.
  • Outliers: a few extreme points drag a centroid away, because it is a mean.
  • Wrong k: it always returns exactly k groups.
Python Four failure modes

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

In our run the ARI was about 0.24 on the moons, 0.72 with the unequal spread, and near 0.05 for both the unequal sizes and the outliers (one centroid is spent on just five outlier points, while the two real blobs share the other). None of these clusterings crashes or warns. Each one just returns a tidy-looking but wrong answer, which is why you should always look at the clusters (a plot, a profile table) and not trust a number alone. If these shapes match your data, try hierarchical clustering, DBSCAN or Gaussian mixtures.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does the update step of Lloyd's algorithm do?

    The assign step labels points by nearest centroid; the update step recomputes each centroid as the mean of its points. The two alternate until nothing changes.
  2. 2. Why does k-means++ usually give better results than purely random initialization?

    k-means++ picks each new starting centroid with probability proportional to its squared distance from existing ones. It is still heuristic and does not guarantee the global minimum.
  3. 3. Why can't you pick k by choosing the value with the lowest inertia?

    More centroids always fit the data at least as closely, so inertia alone rewards over-splitting. Use the elbow, the silhouette score or domain needs instead.
  4. 4. A dataset has one tight cluster, one wide cluster and a few extreme outliers. What is the most likely problem with k-means?

    A mean is sensitive to extreme values, and straight boundaries between centroids cannot adapt to different spreads. It still returns exactly k groups without any warning.

Summary

  • k-means alternates assigning points to the nearest centroid and moving each centroid to its group mean; it minimizes inertia and always converges to a local minimum.
  • Use the default k-means++ initialization and several restarts (n_init) to avoid poor local minima.
  • Choose k with the elbow plot and the silhouette score, and check that the groups make practical sense.
  • MiniBatchKMeans trades a little accuracy for large speedups and supports partial_fit.
  • k-means expects round, similar-size, similar-spread clusters, scaled features and few outliers; always inspect the result visually.

Next: when you do not want to fix the number of clusters in advance, see Hierarchical Clustering.