Skip to content
Tutorials Center
My learning

Topics

Lesson 27 of 39 ยท Clustering

k-Means and Its Variants

Implement k-means from scratch, then learn k-means++ initialization, choosing k with the elbow and silhouette, k-medoids (PAM) for robustness and MiniBatch k-means for big data.

k-means is the most widely used clustering algorithm. You pick the number of clusters k; the algorithm finds k centers (centroids) and assigns each record to its nearest one, so that the total squared distance from records to their centroids, called inertia or SSE, is as small as it can get.

It works by repeating two steps (Lloyd's algorithm) until nothing changes:

  1. Assign: put every record in the cluster of its closest centroid.
  2. Update: move each centroid to the mean of its records.

Each round can only decrease the SSE, so the process always converges, but only to a local minimum: a bad starting point can give a bad answer.

k-means from scratch

Python Lloyd's algorithm in NumPy

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.

Initialization matters

Random starts can place two centroids inside one blob and leave another blob uncovered. k-means++ spreads the starting centers: the first is random, and each next one is chosen with probability proportional to its squared distance from the closest center picked so far. scikit-learn uses it by default and also runs the algorithm n_init times, keeping the best SSE.

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.

Choosing k

The data does not announce k. Two common guides:

  • Elbow method: plot SSE against k. SSE always falls as k grows (at k = n it is 0), so look for the bend where extra clusters stop paying off.
  • Silhouette score: for each record compare the distance to its own cluster (a) with the distance to the nearest other cluster (b): s = (b - a) / max(a, b). It runs from -1 to 1; the average over all records is highest when clusters are tight and well separated.
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 generator made four blobs, but two of them overlap: SSE bends at k = 3 and the silhouette peaks there too, so the data itself suggests three groups. Real data is just as untidy, so also ask whether the clusters make business sense. More tools are in evaluating clusters.

Limits of k-means

  • Prefers round, similarly sized clusters (see the moons example in Clustering Basics).
  • Sensitive to outliers, because the mean is pulled by extreme values.
  • Needs k in advance and numeric features (categories need a different method, below).
  • Every record is forced into a cluster, even noise.

k-medoids (PAM)

k-medoids replaces the mean with a medoid: an actual record that is the most central point of its cluster. Because medoids are real records and the criterion uses distances (not squared), the method is robust to outliers and works with any distance measure, including ones for categorical data. The classic algorithm is PAM (Partitioning Around Medoids): start with k medoids, try swapping each medoid with a non-medoid, and keep any swap that lowers total distance. The cost is higher, so the variants CLARA and CLARANS work on samples.

Python Mean versus medoid with an outlier

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 outlier claims a k-means cluster of its own and the other center (4.46, 4.44) falls between the two real groups, while the medoids stay on genuine records of the two real groups. For truly categorical data, k-modes uses the most frequent category as the cluster center and counts mismatches as the distance.

Scaling to big data and soft versions

  • MiniBatch k-means updates centroids from small random batches, trading a little accuracy for large speed gains on millions of records.
  • Gaussian mixture models (EM) are a soft generalization: clusters can be ellipses with different sizes, and every record gets a probability per cluster.
  • Fuzzy c-means gives each record a membership degree in every cluster.
Python MiniBatch 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.

The SSE values are similar; the mini-batch version is usually faster (exact timings vary by machine).

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What are the two repeated steps of k-means?

    Assignment and update alternate until the centroids stop moving.
  2. 2. Why does k-means++ help?

    Spreading the initial centers reduces the chance of a poor local minimum.
  3. 3. How does a medoid differ from a centroid?

    A medoid is an existing record that is most central in its cluster, which makes k-medoids robust to outliers.
  4. 4. The SSE always decreases as k grows. How is k then chosen with the elbow method?

    The bend in the SSE curve marks the point where more clusters bring little extra benefit.

Summary

  • k-means alternates assignment and centroid update to minimize SSE; it finds a local minimum.
  • Use k-means++ and several restarts; choose k with the elbow, the silhouette and common sense.
  • k-medoids (PAM, CLARA) uses real records as centers and resists outliers; k-modes handles categories.
  • MiniBatch k-means scales to large data; Gaussian mixtures give soft assignments.

Next: Hierarchical Clustering