SyntaxPilot
Courses/Machine Learning/Lesson 43
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

Machine Learning · Lesson 43 of 90

k-means from scratch

clusteringcentroidcluster assignmentLloyd's algorithminertia (within-cluster sum of squares)k-means++ initialisationelbow methodsilhouette scoremini-batch k-means

Machine Learning Full Course · Episode 43. Every code sample below was run with Python 3.13, NumPy 2.5.3, pandas 3.0.5 and scikit-learn 1.9.1; the output shown is the real output (the timings in seconds change from run to run). Riya's customers, their spending and the two million delivery points are all made up for teaching. Because we made the data ourselves, we know the "true" groups, which lets us check whether clustering found them.

The big idea: until now every dataset came with answers (labels). Today there are none: just rows. Clustering puts similar rows into the same group, where "similar" means "close together". k-means does it with two tiny steps repeated: give every row to its nearest centre (assignment), then move every centre to the average of its rows (update, the centre is the centroid). Repeating them is Lloyd's algorithm. Inertia (the sum of squared distances to the own centroid) measures how tight the groups are and can only go down. Bad starts can leave k-means stuck in a local minimum (inertia 3,531 instead of 1,253); the k-means++ start and several restarts (n_init) fix that. Inertia always falls as you add clusters (k = 1,000 gives 0), so choose k with the elbow method and the silhouette score. Scale your columns first, and use mini-batch k-means when the rows run into millions.

Sources: S. P. Lloyd, "Least squares quantization in PCM", IEEE Transactions on Information Theory, 1982, doi:10.1109/TIT.1982.1056489 (knowledge-base page); D. Arthur and S. Vassilvitskii, "k-means++: the advantages of careful seeding", SODA 2007, pp. 1027-1035 (bibbase: randomized seeding, Θ(log k)-competitive, improves both speed and accuracy); P. J. Rousseeuw, "Silhouettes: a graphical aid to the interpretation and validation of cluster analysis", Journal of Computational and Applied Mathematics 20:53-65, 1987 (math.utah.edu); D. Sculley, "Web-scale k-means clustering", WWW 2010, pp. 1177-1178 (webis anthology); the docstrings of the installed scikit-learn 1.9.1 (KMeans: init="k-means++" is the default, n_init, inertia_; MiniBatchKMeans).

Words you need first

  • Supervised vs unsupervised learning (Episode 1): in supervised learning every row has a label (the answer: late or on time, a price) and the model learns to predict it. In unsupervised learning there are no labels, only rows, and the job is to find structure in them.
  • Vector, distance (Episode 3): a customer at x = 2.85 km, y = 8.32 km is the vector (2.85, 8.32). The (Euclidean) distance between two points is the straight-line distance, √((x₁ − x₂)² + (y₁ − y₂)²). np.linalg.norm(v) computes the length of a vector v; the length of a difference is a distance.
  • Broadcasting (Episode 2): NumPy automatically stretches arrays of different shapes so they can be combined. X[:, None] has shape (1000, 1, 2) and the hubs c have shape (5, 2); X[:, None] - c becomes shape (1000, 5, 2): every customer minus every hub, without a loop.
  • axis: which direction an operation runs along. On a (1000, 5) table, axis=1 works across each row (one result per customer).
  • argmin: the position of the smallest value, not the value itself. np.array([3.1, 0.4, 2.0]).argmin() is 1.
  • Mean: the average. The mean of 1, 3, 2 is (1 + 3 + 2) / 3 = 2.
  • Random generator: np.random.default_rng(1) makes random numbers that are the same every run (seed 1), so you get exactly the outputs shown here. r.normal(m, s, (n, 2)) draws n points around the centre m with spread s.
  • Local minimum (Episode 8): a spot where no small move improves things, but which is not the best answer overall.
  • Standardising, StandardScaler (Episode 16): rescale each column to mean 0 and standard deviation 1, so every column speaks in the same units.
  • k-nearest neighbours and scaling (Episode 27): distance listens most to the column with the biggest numbers.
  • Mini-batch gradient descent (Episode 18): update a model using a small random batch of rows at a time instead of all rows.

The real-life hook: Riya's five delivery hubs

Riya runs a quick grocery delivery service in her city. She has 1,000 customers, and for each one she knows where they live, as x and y in kilometres on a 10 km × 10 km city map. She has money for 5 small hubs (little warehouses); every rider starts each trip from a hub. Where should the hubs go so that trips are as short as possible?

Nobody gives her the answer. There is no column saying "this customer belongs to hub 3". There are no labels. This is a clustering problem:

  • Clustering: putting similar rows into the same group. Like sorting a pile of mixed laundry into whites, darks and colours without anyone telling you the names of the piles.
  • Cluster: one such group (all the customers served by one hub).
  • Similar here means close together, measured by the distance between vectors.

The made-up customers live in 5 neighbourhoods: a big one (500 people) in the top left around (2.5, 7.5), and four smaller ones around (7.5, 8), (5, 4.5), (2, 2) and (8, 2). The two lines that create them (we will reuse them in every program) are called HDR below.

The obvious attempt: five equal strips

Cut the map into 5 equal vertical strips (x from 0-2, 2-4, ...) and put a hub in the middle of each strip, at (1, 5), (3, 5), (5, 5), (7, 5), (9, 5). Then measure every customer's distance to the nearest hub.

import numpy as np
r = np.random.default_rng(1)                                             # Riya's 1,000 customers (made up)
X = np.vstack([r.normal(m, s, (n, 2)) for m, s, n in [([2.5, 7.5], 1, 500), ([7.5, 8], .6, 120),
               ([5, 4.5], .5, 100), ([2, 2], .6, 140), ([8, 2], .6, 140)]])  # 5 neighbourhoods, (x, y) in km
print("customers:", X.shape, "  first:", X[0].round(2))
hubs = np.array([[x, 5] for x in (1, 3, 5, 7, 9)])                      # obvious: 5 equal strips, hub in each middle
d = np.linalg.norm(X[:, None] - hubs, axis=2)                           # every customer to every hub: (1000, 5)
print("average distance to nearest hub:", d.min(axis=1).mean().round(2), "km")
print("customers per hub:", np.bincount(d.argmin(axis=1)))

Output:

customers: (1000, 2)   first: [2.85 8.32]
average distance to nearest hub: 2.57 km
customers per hub: [242 372 121 171  94]

Line by line:

  • X.shape is (1000, 2): 1,000 rows (customers), 2 columns (x, y). The first customer lives at (2.85, 8.32).
  • np.vstack([...]) stacks the five neighbourhoods on top of each other into one table.
  • d is a (1000, 5) table: row i, column j is customer i's distance to hub j (broadcasting, see above).
  • d.min(axis=1) is each customer's distance to the nearest hub; .mean() averages them: 2.57 km.
  • d.argmin(axis=1) is the number of each customer's nearest hub; np.bincount counts how many times each number appears: the loads are 372 for one hub and only 94 for another.

Why is it bad? People don't live in strips. Every strip hub sits on the middle line y = 5 of the map, while most people live near the top or the bottom; only the middle hub at (5, 5) lands on a neighbourhood. A strip can cut a neighbourhood in half or land in an empty field. The hubs must follow the people.

Lloyd's algorithm: assign, update, repeat

Put 5 hubs anywhere. Then:

  1. Assignment step: every customer picks the nearest hub. In ML words, each row gets the label (cluster number) of its nearest centre. This label is the cluster assignment.
  2. Update step: every hub moves to the middle of its own customers: the average x and the average y. That average point is the centroid, the centre of a cluster. Example: customers at (1, 2), (3, 2) and (2, 5) have centroid ((1 + 3 + 2)/3, (2 + 2 + 5)/3) = (2, 3).
  3. Repeat: after the hubs move, some customers have a nearer hub, so assign again, then move again. Stop when nothing moves. That is convergence: the assignments (and therefore the centroids) stop changing.

These two steps, repeated, are Lloyd's algorithm, from S. P. Lloyd's paper "Least squares quantization in PCM" (IEEE Transactions on Information Theory, 1982). It is what everyone calls k-means: k groups, each one represented by a mean.

Inertia measures how good a set of hubs is: square each customer's distance to its own centroid and add them all up. It is also called the within-cluster sum of squares (WCSS). Smaller means tighter clusters. Example: for the cluster (1, 2), (3, 2), (2, 5) with centroid (2, 3), the squared distances are 1² + 1² = 2, 1² + 1² = 2 and 0² + 2² = 4, so its inertia is 8 (checked in Practice 4).

Why it always settles: assigning every row to its nearest centre cannot increase inertia (each squared distance can only get smaller or stay the same), and moving a centre to the mean of its rows cannot increase it either (the mean is the point with the smallest sum of squared distances to a set of points). So inertia only goes down, until it stops.

In NumPy, the whole algorithm is a short function (called KM below):

def kmeans(X, start, steps=12, show=True):
    c = start.copy()
    for step in range(steps):
        d = np.linalg.norm(X[:, None] - c, axis=2)                      # distance to every centroid
        lab = d.argmin(axis=1)                                          # 1) assign: nearest centroid
        inertia = (d.min(axis=1) ** 2).sum()                            # sum of squared distances
        if show: print(f"step {step}: inertia {inertia:7.1f}   sizes {np.bincount(lab, minlength=len(c))}")
        new = np.array([X[lab == j].mean(axis=0) for j in range(len(c))])   # 2) update: move to the mean
        if np.allclose(new, c): break                                   # nothing moved: converged
        c = new
    return c, lab, inertia
  • X[lab == j] picks the rows whose label is j (a boolean mask); .mean(axis=0) averages them column by column, giving the new centroid.
  • np.bincount(lab, minlength=len(c)) counts customers per cluster and also shows clusters with 0 customers.
  • np.allclose(new, c) is True when the new centroids are (almost exactly) the old ones: converged.

First try: start at 5 random spots on the map

import numpy as np
r = np.random.default_rng(1)                                             # Riya's 1,000 customers (made up)
X = np.vstack([r.normal(m, s, (n, 2)) for m, s, n in [([2.5, 7.5], 1, 500), ([7.5, 8], .6, 120),
               ([5, 4.5], .5, 100), ([2, 2], .6, 140), ([8, 2], .6, 140)]])  # 5 neighbourhoods, (x, y) in km
def kmeans(X, start, steps=12, show=True):
    c = start.copy()
    for step in range(steps):
        d = np.linalg.norm(X[:, None] - c, axis=2)                      # distance to every centroid
        lab = d.argmin(axis=1)                                          # 1) assign: nearest centroid
        inertia = (d.min(axis=1) ** 2).sum()                            # sum of squared distances
        if show: print(f"step {step}: inertia {inertia:7.1f}   sizes {np.bincount(lab, minlength=len(c))}")
        new = np.array([X[lab == j].mean(axis=0) for j in range(len(c))])   # 2) update: move to the mean
        if np.allclose(new, c): break                                   # nothing moved: converged
        c = new
    return c, lab, inertia
start = np.random.default_rng(13).uniform(0, 10, (5, 2))                # start: 5 random spots on the map
c, lab, inertia = kmeans(X, start, steps=4)

Output (stderr included):

step 0: inertia  9010.2   sizes [128 241 490 141   0]
main.py:12: RuntimeWarning: Mean of empty slice
  new = np.array([X[lab == j].mean(axis=0) for j in range(len(c))])   # 2) update: move to the mean
.../numpy/_core/_methods.py:134: RuntimeWarning: invalid value encountered in divide
  ret = um.true_divide(
step 1: inertia     nan   sizes [   0    0    0    0 1000]
step 2: inertia     nan   sizes [1000    0    0    0    0]
step 3: inertia     nan   sizes [   0 1000    0    0    0]
  • Step 0 looks fine (inertia 9,010.2), but the last size is 0: one hub landed in an empty field and no customer chose it.
  • RuntimeWarning: Mean of empty slice. A RuntimeWarning is Python's way of saying "something suspicious happened while running, but I did not stop". The mean of zero customers is 0 / 0, which is undefined (the second warning: invalid value encountered in divide).
  • The result is nan ("not a number"), a special float value for an undefined result. nan spreads: any arithmetic with nan gives nan, so every distance to that hub is nan, inertia becomes nan, and argmin over a row with nan in it returns the position of the nan, so all 1,000 customers pile onto one hub.

The fix: start the hubs at 5 randomly chosen customers. Each starting hub has at least one customer (itself, at distance 0), so no cluster is empty at the start.

Second try: start at 5 random customers

import numpy as np
r = np.random.default_rng(1)                                             # Riya's 1,000 customers (made up)
X = np.vstack([r.normal(m, s, (n, 2)) for m, s, n in [([2.5, 7.5], 1, 500), ([7.5, 8], .6, 120),
               ([5, 4.5], .5, 100), ([2, 2], .6, 140), ([8, 2], .6, 140)]])  # 5 neighbourhoods, (x, y) in km
def kmeans(X, start, steps=12, show=True):
    c = start.copy()
    for step in range(steps):
        d = np.linalg.norm(X[:, None] - c, axis=2)                      # distance to every centroid
        lab = d.argmin(axis=1)                                          # 1) assign: nearest centroid
        inertia = (d.min(axis=1) ** 2).sum()                            # sum of squared distances
        if show: print(f"step {step}: inertia {inertia:7.1f}   sizes {np.bincount(lab, minlength=len(c))}")
        new = np.array([X[lab == j].mean(axis=0) for j in range(len(c))])   # 2) update: move to the mean
        if np.allclose(new, c): break                                   # nothing moved: converged
        c = new
    return c, lab, inertia
pick = np.random.default_rng(9).choice(len(X), 5, replace=False)        # start: 5 random CUSTOMERS
c, lab, inertia = kmeans(X, X[pick])
print("hubs:", *[tuple(h) for h in c.round(1).tolist()])
print("average distance:", np.linalg.norm(X - c[lab], axis=1).mean().round(2), "km")

Output:

step 0: inertia  8035.7   sizes [273  88 265  93 281]
step 1: inertia  3350.0   sizes [454 111 181  84 170]
step 2: inertia  1656.7   sizes [488 137 143 102 130]
step 3: inertia  1268.8   sizes [483 139 140 116 122]
step 4: inertia  1253.5   sizes [480 140 140 118 122]
step 5: inertia  1252.8   sizes [480 140 140 118 122]
hubs: (2.3, 7.6) (8.1, 2.1) (2.0, 2.0) (4.9, 4.7) (7.5, 7.9)
average distance: 0.97 km
  • choice(len(X), 5, replace=False) picks 5 different row numbers; X[pick] are those customers.
  • Inertia: 8,035.7 → 3,350.0 → 1,656.7 → 1,268.8 → 1,253.5 → 1,252.8. It only went down, as promised, and settled after 5 steps (at step 5 the hubs no longer moved).
  • The sizes end at 480, 140, 140, 118, 122: close to the real neighbourhoods (500, 140, 140, 100, 120; a few customers at the edges of the big neighbourhood are nearer another hub).
  • The hubs sit at (2.3, 7.6), (8.1, 2.1), (2.0, 2.0), (4.9, 4.7), (7.5, 7.9): one in each neighbourhood.
  • c[lab] gives every customer its own hub, so the average trip is 0.97 km, down from 2.57 km with strips.

You just invented k-means.

Hub placement Average distance Inertia
5 equal strips 2.57 km not computed
Random map spots nan (a hub got 0 customers) nan
Random customers, Lloyd's algorithm 0.97 km 1,252.8

Bad starts get stuck, and k-means++

That start (seed 9) was lucky. With some other random starts, two hubs land in the big top-left neighbourhood and split it, while one hub sits on the empty road between two bottom towns, serving both. Neither step can fix it: every customer already uses its nearest hub, and every hub already sits at the mean of its customers. Inertia 3,531, nearly three times worse. This is a local minimum: no small move helps, but it is not the best answer.

Two fixes:

  1. Restarts: run k-means several times from different random starts and keep the run with the lowest inertia. In scikit-learn this is n_init (number of initialisations).
  2. Start better: k-means++ (Arthur and Vassilvitskii, 2007). Think of placing water coolers in a big school: after the first one, you wouldn't put the second right next to it; you'd go somewhere far away. - Pick the first centre as a random customer. - For every next centre, each customer's chance of being picked is proportional to its squared distance from the nearest centre chosen so far ("proportional" means twice the squared distance gives twice the chance). - Far away means much more likely, but it is still random, so one odd outlier (an unusual far-off point) doesn't always win.

The paper calls this randomized seeding, shows it is Θ(log k)-competitive (its expected inertia is guaranteed to be within a factor that grows like log k of the best possible inertia), and reports that it improves both the speed and the accuracy of k-means.

import numpy as np
r = np.random.default_rng(1)                                             # Riya's 1,000 customers (made up)
X = np.vstack([r.normal(m, s, (n, 2)) for m, s, n in [([2.5, 7.5], 1, 500), ([7.5, 8], .6, 120),
               ([5, 4.5], .5, 100), ([2, 2], .6, 140), ([8, 2], .6, 140)]])  # 5 neighbourhoods, (x, y) in km
def kmeans(X, c):                                                       # same two steps, no printing
    for _ in range(100):
        lab = np.linalg.norm(X[:, None] - c, axis=2).argmin(axis=1)
        c, old = np.array([X[lab == j].mean(axis=0) for j in range(len(c))]), c
        if np.allclose(c, old): return ((X - c[lab]) ** 2).sum()        # converged: return inertia
def plus_plus(X, k, rng):                                               # k-means++ start
    c = [X[rng.integers(len(X))]]                                       # first: one random customer
    while len(c) < k:
        d2 = np.linalg.norm(X[:, None] - np.array(c), axis=2).min(axis=1) ** 2   # squared distance to nearest
        c.append(X[rng.choice(len(X), p=d2 / d2.sum())])                # far away = more likely
    return np.array(c)
rand = [kmeans(X, X[np.random.default_rng(s).choice(len(X), 5, replace=False)]) for s in range(20)]
pp = [kmeans(X, plus_plus(X, 5, np.random.default_rng(s))) for s in range(20)]
print("random 0-9 :", *np.round(rand[:10]).astype(int))
print("k-means++  :", *np.round(pp[:10]).astype(int))
print("stuck (> 1300) in 20 runs:  random", sum(i > 1300 for i in rand), "  k-means++", sum(i > 1300 for i in pp))

Output:

random 0-9 : 1253 1253 1253 3531 1253 3167 3531 1253 1253 1253
k-means++  : 1253 1253 1253 1253 1253 1253 1253 1253 1253 1253
stuck (> 1300) in 20 runs:  random 3   k-means++ 0
  • This kmeans is a shorter version: c, old = new_centroids, c keeps the previous centroids in old, and as soon as nothing moved (np.allclose(c, old)) it returns the inertia.
  • rand and pp are list comprehensions: a one-line loop that builds a list, [f(s) for s in range(20)]. Seed s gives run s for both starts; the first two lines print seeds 0-9, the last line counts all 20 runs.
  • p=d2 / d2.sum() turns the squared distances into probabilities that add up to 1; rng.choice(..., p=...) picks one row with those chances. Customers already sitting on a centre have d2 = 0, so they can never be picked twice.
  • Random-customer starts: 3 of 20 got stuck (seeds 3, 5 and 6: 3,531, 3,167, 3,531).
  • k-means++ starts: 0 of 20 stuck; seeds 0-9 all found 1,253.

k-means in scikit-learn

import numpy as np
r = np.random.default_rng(1)                                             # Riya's 1,000 customers (made up)
X = np.vstack([r.normal(m, s, (n, 2)) for m, s, n in [([2.5, 7.5], 1, 500), ([7.5, 8], .6, 120),
               ([5, 4.5], .5, 100), ([2, 2], .6, 140), ([8, 2], .6, 140)]])  # 5 neighbourhoods, (x, y) in km
from sklearn.cluster import KMeans
km = KMeans(n_clusters=5, init="k-means++", n_init=10, random_state=0).fit(X)   # 10 starts, keep the best
print("hubs:", *[tuple(h) for h in km.cluster_centers_.round(1).tolist()])
print("inertia:", round(km.inertia_, 1), "  sizes:", np.bincount(km.labels_))
print("new customer at (6, 7.5) -> hub", km.predict([[6, 7.5]]))
for k in range(1, 10):                                                  # inertia for k = 1 ... 9
    print(f"k={k}  inertia {KMeans(k, n_init=10, random_state=0).fit(X).inertia_:7.0f}")
print(f"k=1000 inertia {KMeans(1000, n_init=1, random_state=0).fit(X).inertia_:7.0f}   <- one hub per customer")

Output:

hubs: (7.5, 7.9) (2.0, 2.0) (2.3, 7.6) (8.1, 2.1) (4.9, 4.7)
inertia: 1252.8   sizes: [122 140 480 140 118]
new customer at (6, 7.5) -> hub [0]
k=1  inertia   13186
k=2  inertia    6920
k=3  inertia    4071
k=4  inertia    2145
k=5  inertia    1253
k=6  inertia     953
k=7  inertia     773
k=8  inertia     681
k=9  inertia     642
k=1000 inertia       0   <- one hub per customer

What each piece means:

  • n_clusters=5: k, the number of clusters.
  • init="k-means++": the k-means++ start. It is the default in scikit-learn 1.9.1.
  • n_init=10: 10 runs from 10 different starts; the one with the lowest inertia is kept. (The default, n_init="auto", means 1 run with k-means++ and 10 runs with init="random".)
  • random_state=0: fixes the randomness so the result is the same every run.
  • .fit(X): runs the algorithm. Note there is no y: unsupervised.
  • cluster_centers_: the centroids (the same 5 hubs as our version, in a different order: cluster numbers are just names and can come out in any order).
  • labels_: each training row's cluster. inertia_: 1,252.8, the same as ours.
  • predict(new_rows): assigns new rows to the nearest centroid without moving the centroids. A new customer at (6, 7.5) goes to hub 0, the top-right one at (7.5, 7.9).
  • fit_predict(X) (used later) is fit(X) then returns labels_.

Choosing k: the elbow method

Riya guessed 5. What is the right k? The obvious attempt, "pick the k with the smallest inertia", fails: inertia keeps falling (13,186 → 6,920 → ... → 642), and with k = 1,000, one hub per customer, inertia is 0. Perfect, and useless. Adding a cluster can never make inertia worse, so its smallest value cannot choose k.

Instead, look at how much each new cluster helps:

k Inertia Drop from k − 1
1 13,186
2 6,920 6,266
3 4,071 2,849
4 2,145 1,926
5 1,253 892
6 953 300
7 773 180
8 681 92
9 642 39

From 1 to 5, every extra hub cuts inertia a lot. After 5 the curve flattens: each new hub barely helps. Plotted, the curve looks like a bent arm, and the bend is the elbow. The elbow method: plot inertia against k and pick k at the bend. Here, 5.

The trouble: on real data the bend is often soft, and two people will point at different elbows. We need a number with a clear best.

Choosing k: the silhouette score

Think of a student sitting with a friend group in the canteen. Ask two questions:

  • a: on average, how far am I from the others in my own group?
  • b: on average, how far am I from the people in the nearest other group?

The silhouette of that student (one row) is

s = (b - a) / max(a, b)          # always between -1 and +1
  • near +1: snug in my group and far from the next one (a much smaller than b).
  • near 0: I'm sitting on the border between two groups (a ≈ b).
  • negative: I'm closer to another group than to my own, so I'm probably in the wrong one.

Averaging s over every row gives the silhouette score (P. J. Rousseeuw, 1987). Higher is better; unlike inertia it does not just keep rising with k, so its highest value can choose k.

import numpy as np
r = np.random.default_rng(1)                                             # Riya's 1,000 customers (made up)
X = np.vstack([r.normal(m, s, (n, 2)) for m, s, n in [([2.5, 7.5], 1, 500), ([7.5, 8], .6, 120),
               ([5, 4.5], .5, 100), ([2, 2], .6, 140), ([8, 2], .6, 140)]])  # 5 neighbourhoods, (x, y) in km
from sklearn.cluster import KMeans; from sklearn.metrics import silhouette_score, silhouette_samples
lab = KMeans(5, n_init=10, random_state=0).fit_predict(X)
d = np.linalg.norm(X[:, None] - X, axis=2)                              # all customer-to-customer distances
i = 0; a = d[i, lab == lab[i]].sum() / ((lab == lab[i]).sum() - 1)      # a: average distance inside own cluster
b = min(d[i, lab == j].mean() for j in range(5) if j != lab[i])         # b: average distance, NEAREST other
print(f"customer 0:  a={a:.2f}  b={b:.2f}  s=(b-a)/max(a,b)={(b - a) / max(a, b):.3f}")
print("sklearn says:", silhouette_samples(X, lab)[0].round(3))
for k in range(2, 9):
    lab = KMeans(k, n_init=10, random_state=0).fit_predict(X)
    print(f"k={k}  silhouette {silhouette_score(X, lab):.3f}")         # mean s over all customers

Output:

customer 0:  a=1.43  b=4.24  s=(b-a)/max(a,b)=0.662
sklearn says: 0.662
k=2  silhouette 0.480
k=3  silhouette 0.548
k=4  silhouette 0.625
k=5  silhouette 0.638
k=6  silhouette 0.522
k=7  silhouette 0.524
k=8  silhouette 0.517
  • d is a (1000, 1000) table of every customer-to-customer distance (pairwise distances).
  • For a, we divide the sum by (cluster size − 1): customer 0's distance to itself is 0 and must not count as "another member".
  • For b, we take the mean distance to each other cluster and keep the smallest (the nearest other cluster).
  • Customer 0: a = 1.43 km, b = 4.24 km, s = (4.24 − 1.43) / 4.24 = 0.662. silhouette_samples (one s per row) agrees exactly.
  • silhouette_score (the mean of all s): highest at k = 5, 0.638. A clear winner, matching the elbow.

One cost to know: the silhouette needs every pairwise distance: 1,000 rows means 1,000,000 distances; a million rows would mean a million million. On big data, score a random sample (silhouette_score(X, lab, sample_size=...), Practice 3).

Scale before you cluster

Riya now wants groups of customers for offers, using two columns: spend_rs (rupees spent per month) and orders (orders per month). She suspects three kinds: daily small orders (₹1,500, 25 orders), one big basket a month (₹6,000, 4 orders), and occasional buyers (₹2,500, 4 orders). We made the data, so we know the true groups.

The catch: spend differs between people by thousands of rupees, while orders differ by ten or twenty. Distance is ruled by the column with the biggest numbers (Episode 27), so orders barely count. Feature scaling (here standardising with StandardScaler, Episode 16) puts both columns on the same footing.

import numpy as np, pandas as pd
from sklearn.cluster import KMeans; from sklearn.preprocessing import StandardScaler
r = np.random.default_rng(5)                                    # Riya's customers: spend and orders (made up)
groups = [(1500, 25, 300), (6000, 4, 300), (2500, 4, 400)]      # daily small · monthly big basket · occasional
C = pd.DataFrame(np.vstack([np.c_[r.normal(s, 900, n), r.normal(o, 2, n)] for s, o, n in groups]),
                 columns=["spend_rs", "orders"]).round()
C["true_group"] = np.repeat(["daily", "big basket", "occasional"], [300, 300, 400])
raw = C[["spend_rs", "orders"]]
for name, data in [("raw", raw), ("scaled", StandardScaler().fit_transform(raw))]:   # same data, scaled
    C["cluster"] = KMeans(3, n_init=10, random_state=0).fit_predict(data)
    print(name); print(pd.crosstab(C.true_group, C.cluster))

Output:

raw
cluster       0    1    2
true_group               
big basket  287    0   13
daily         0  220   80
occasional    4  110  286
scaled
cluster       0    1    2
true_group               
big basket  292    0    8
daily         0  300    0
occasional    8    0  392
  • np.c_[a, b] puts two arrays side by side as columns; np.repeat writes each group name 300, 300 and 400 times.
  • pd.crosstab(rows, columns) is a cross-tabulation: a count table. Row "daily", column 1 = how many daily customers landed in cluster 1.
  • Raw: the daily customers are split, 220 in cluster 1 and 80 in cluster 2, and 110 occasional buyers are mixed in with them. The clusters basically cut by spend alone. Counting everyone outside their group's main cluster: 13 + 80 + 4 + 110 = 207 mistakes.
  • Scaled: all 300 daily customers together, and only 8 + 8 = 16 mistakes in total. Same algorithm; the only change was the units. Scale before you cluster.

Mini-batch k-means for millions of rows

Riya expands across the state: 2,000,000 delivery points and 30 hubs. Every step of k-means reads all 2 million rows, which gets slow.

You don't drink the whole pot to check the chai: one spoon tells you enough. Mini-batch k-means updates the centroids using a small random batch of rows each step, nudging them a little toward that batch, just like mini-batch gradient descent (Episode 18). The idea is from D. Sculley's 2010 paper "Web-scale k-means clustering". In scikit-learn it is MiniBatchKMeans; batch_size is the number of rows per step (default 1,024).

import numpy as np, time
from sklearn.cluster import KMeans, MiniBatchKMeans
r = np.random.default_rng(2)
centres = r.uniform(0, 100, (30, 2))                                    # 30 towns across the state (made up)
X = centres[r.integers(0, 30, 2_000_000)] + r.normal(0, 3, (2_000_000, 2))   # 2,000,000 delivery points
for model in [KMeans(30, n_init=3, random_state=0), MiniBatchKMeans(30, batch_size=2048, n_init=3, random_state=0)]:
    t = time.time(); model.fit(X)
    print(f"{type(model).__name__:16} {time.time() - t:5.1f} s   inertia {model.inertia_ / 1e6:.2f} million")

Output (the seconds change from run to run and from machine to machine):

KMeans             7.6 s   inertia 30.15 million
MiniBatchKMeans    0.7 s   inertia 33.85 million
  • time.time() reads the clock; the difference is the training time.
  • Full k-means: about 7.6 s. Mini-batch: 0.7 s, about 10 times faster.
  • Inertia: 30.15 million versus 33.85 million, about 12% worse (33.85 / 30.15 ≈ 1.12): the answer is a bit rougher.
  • Rule of thumb: full k-means when the data fits in memory and you can wait; mini-batch when the rows run into millions, or keep arriving.

Two errors you will meet

import numpy as np
r = np.random.default_rng(1)                                             # Riya's 1,000 customers (made up)
X = np.vstack([r.normal(m, s, (n, 2)) for m, s, n in [([2.5, 7.5], 1, 500), ([7.5, 8], .6, 120),
               ([5, 4.5], .5, 100), ([2, 2], .6, 140), ([8, 2], .6, 140)]])  # 5 neighbourhoods, (x, y) in km
from sklearn.cluster import KMeans
try: KMeans(5).fit(X[:3])                                               # MISTAKE: 3 customers, 5 clusters
except ValueError as e: print("ValueError:", e)
km = KMeans(5, n_init=10, random_state=0).fit(X)
try: km.predict([[6, 7.5, 1200]])                                       # MISTAKE: a 3rd column the model never saw
except ValueError as e: print("ValueError:", e)

Output:

ValueError: n_samples=3 should be >= n_clusters=5.
ValueError: X has 3 features, but KMeans is expecting 2 features as input.
  • ValueError: n_samples=3 should be >= n_clusters=5. n_samples is the number of rows, n_clusters is k. You can't make 5 groups out of 3 rows.
  • ValueError: X has 3 features, but KMeans is expecting 2 features as input. A feature is a column. New rows passed to predict must have exactly the columns used in fit, in the same order, and with the same scaling.

Common mistakes

Mistake Exact message / symptom Why Fix
Start hubs at random map spots RuntimeWarning: Mean of empty slice, then inertia nan A hub with no customers; mean of 0 rows = 0 / 0 Start at data points, or k-means++
One run from one random start inertia 3,531 instead of 1,253 Stuck in a local minimum k-means++ and n_init restarts
Pick k with the lowest inertia k=1000 inertia 0 Inertia always falls as k grows Elbow method + silhouette score
Cluster raw columns in different units daily customers split 220 / 80 The biggest units rule the distance StandardScaler first (16 mistakes instead of 207)
More clusters than rows ValueError: n_samples=3 should be >= n_clusters=5. Can't fill the groups k ≤ number of rows
Predict with different columns ValueError: X has 3 features, but KMeans is expecting 2 features as input. The model knows only the fitted columns Same columns, same order, same scaling (a pipeline)
Treating cluster numbers as meaningful sklearn's hubs came out in a different order from ours Cluster numbers are arbitrary names Describe clusters by their centroids / averages
Silhouette on millions of rows very slow, huge memory Needs every pairwise distance sample_size= a random sample

Mini project: customer groups for offers, with scaling and the silhouette

A new shop's made-up customers come in four kinds (₹800 with 20 orders, ₹5,000 with 3, ₹2,000 with 8, ₹9,000 with 15). Pretend you don't know that: scale, choose k by the silhouette score, then fit a pipeline (Episode 17: a scaler and a model joined into one object, so new rows are scaled the same way automatically), describe each cluster in real units, and place a new customer.

import numpy as np, pandas as pd
from sklearn.cluster import KMeans; from sklearn.preprocessing import StandardScaler
from sklearn.pipeline import make_pipeline; from sklearn.metrics import silhouette_score
r = np.random.default_rng(11)                                   # a new shop's customers (made up)
groups = [(800, 20, 250), (5000, 3, 250), (2000, 8, 250), (9000, 15, 100)]   # spend_rs, orders, how many
C = pd.DataFrame(np.vstack([np.c_[r.normal(s, 600, n), r.normal(o, 2, n)] for s, o, n in groups]),
                 columns=["spend_rs", "orders"]).clip(lower=0).round()
Z = StandardScaler().fit_transform(C)                          # scale once, then compare k
scores = {}
for k in range(2, 8):
    scores[k] = silhouette_score(Z, KMeans(k, n_init=10, random_state=0).fit_predict(Z))
    print(f"k={k}  silhouette {scores[k]:.3f}")
best = max(scores, key=scores.get)
model = make_pipeline(StandardScaler(), KMeans(best, n_init=10, random_state=0)).fit(C)   # scaler + k-means together
C["cluster"] = model.predict(C)
print("best k:", best)
print(C.groupby("cluster").agg(customers=("orders", "size"), spend_rs=("spend_rs", "mean"),
                               orders=("orders", "mean")).round(0))
new = pd.DataFrame([[4800, 2]], columns=["spend_rs", "orders"])
print("new customer (4800 rs, 2 orders) -> cluster", model.predict(new))

Output:

k=2  silhouette 0.537
k=3  silhouette 0.644
k=4  silhouette 0.702
k=5  silhouette 0.602
k=6  silhouette 0.522
k=7  silhouette 0.420
best k: 4
         customers  spend_rs  orders
cluster                             
0              248    5015.0     3.0
1              250     823.0    20.0
2              252    1999.0     8.0
3              100    8967.0    15.0
new customer (4800 rs, 2 orders) -> cluster [0]
  • .clip(lower=0) replaces any negative made-up spend or orders by 0.
  • The silhouette peaks at k = 4 (0.702): the four true kinds.
  • groupby("cluster").agg(...) gives each cluster's size and average spend and orders, in original units: this is how you turn cluster numbers into names. Cluster 0 (₹5,015, 3 orders) is "monthly big basket"; cluster 1 (₹823, 20 orders) is "daily small"; cluster 2 (₹1,999, 8 orders) is "regular"; cluster 3 (₹8,967, 15 orders) is "VIP".
  • The new customer (₹4,800, 2 orders) goes to cluster 0, the big-basket group. Because the scaler is inside the pipeline, the raw ₹ and orders are scaled exactly as in training.

Extend it: add a third column (say avg_items), compare the clusters with and without scaling using pd.crosstab, and write a one-line offer for each cluster.

Practice

1. Run the from-scratch k-means with k = 4, 5 and 6 (starting at k random customers). How does inertia change?

Solution
import numpy as np
r = np.random.default_rng(1)                                             # Riya's 1,000 customers (made up)
X = np.vstack([r.normal(m, s, (n, 2)) for m, s, n in [([2.5, 7.5], 1, 500), ([7.5, 8], .6, 120),
               ([5, 4.5], .5, 100), ([2, 2], .6, 140), ([8, 2], .6, 140)]])  # 5 neighbourhoods, (x, y) in km
def kmeans(X, start, steps=12, show=True):
    c = start.copy()
    for step in range(steps):
        d = np.linalg.norm(X[:, None] - c, axis=2)                      # distance to every centroid
        lab = d.argmin(axis=1)                                          # 1) assign: nearest centroid
        inertia = (d.min(axis=1) ** 2).sum()                            # sum of squared distances
        if show: print(f"step {step}: inertia {inertia:7.1f}   sizes {np.bincount(lab, minlength=len(c))}")
        new = np.array([X[lab == j].mean(axis=0) for j in range(len(c))])   # 2) update: move to the mean
        if np.allclose(new, c): break                                   # nothing moved: converged
        c = new
    return c, lab, inertia
for k in (4, 5, 6):
    pick = np.random.default_rng(9).choice(len(X), k, replace=False)        # k random customers
    c, lab, inertia = kmeans(X, X[pick], steps=100, show=False)
    print(f"k={k}  inertia {inertia:7.1f}   sizes {np.bincount(lab)}")

Output:

k=4  inertia  2172.7   sizes [131 148 228 493]
k=5  inertia  1252.8   sizes [480 140 140 118 122]
k=6  inertia   952.8   sizes [220 115 122 140 264 139]

With k = 4, two neighbourhoods must share a hub (one cluster of 228). With k = 6, the big top-left neighbourhood is cut in two (220 and 264). Inertia falls each time (2,172.7 → 1,252.8 → 952.8), but the fall from 5 to 6 is much smaller than from 4 to 5: the elbow again.

2. Count stuck runs over 100 random-customer seeds instead of 20.

Solution
import numpy as np
r = np.random.default_rng(1)                                             # Riya's 1,000 customers (made up)
X = np.vstack([r.normal(m, s, (n, 2)) for m, s, n in [([2.5, 7.5], 1, 500), ([7.5, 8], .6, 120),
               ([5, 4.5], .5, 100), ([2, 2], .6, 140), ([8, 2], .6, 140)]])  # 5 neighbourhoods, (x, y) in km
def kmeans(X, c):
    for _ in range(100):
        lab = np.linalg.norm(X[:, None] - c, axis=2).argmin(axis=1)
        new = np.array([X[lab == j].mean(axis=0) for j in range(len(c))])
        if np.allclose(new, c): break
        c = new
    return ((X - c[lab]) ** 2).sum()                                    # inertia
res = np.array([kmeans(X, X[np.random.default_rng(s).choice(len(X), 5, replace=False)]) for s in range(100)])
print("stuck (> 1300):", (res > 1300).sum(), "of 100")
print("worst:", res.max().round(1), "  best:", res.min().round(1))

Output:

stuck (> 1300): 10 of 100
worst: 3531.4   best: 1252.8

10% of single random starts get stuck, the worst at 3,531.4. If each run is stuck with chance 0.1 independently, 10 restarts are all stuck with chance 0.1¹⁰: that is why n_init restarts work.

3. Silhouette for k = 2..12, on all rows and on a random sample of 300 rows.

Solution
import numpy as np
r = np.random.default_rng(1)                                             # Riya's 1,000 customers (made up)
X = np.vstack([r.normal(m, s, (n, 2)) for m, s, n in [([2.5, 7.5], 1, 500), ([7.5, 8], .6, 120),
               ([5, 4.5], .5, 100), ([2, 2], .6, 140), ([8, 2], .6, 140)]])  # 5 neighbourhoods, (x, y) in km
from sklearn.cluster import KMeans; from sklearn.metrics import silhouette_score
for k in range(2, 13):
    lab = KMeans(k, n_init=10, random_state=0).fit_predict(X)
    full = silhouette_score(X, lab)
    samp = silhouette_score(X, lab, sample_size=300, random_state=0)   # score a random sample of 300 rows
    print(f"k={k:2}  silhouette {full:.3f}   on a 300-row sample {samp:.3f}")

Output:

k= 2  silhouette 0.480   on a 300-row sample 0.476
k= 3  silhouette 0.548   on a 300-row sample 0.534
k= 4  silhouette 0.625   on a 300-row sample 0.617
k= 5  silhouette 0.638   on a 300-row sample 0.633
k= 6  silhouette 0.522   on a 300-row sample 0.530
k= 7  silhouette 0.524   on a 300-row sample 0.527
k= 8  silhouette 0.517   on a 300-row sample 0.525
k= 9  silhouette 0.463   on a 300-row sample 0.466
k=10  silhouette 0.452   on a 300-row sample 0.446
k=11  silhouette 0.468   on a 300-row sample 0.452
k=12  silhouette 0.410   on a 300-row sample 0.399

k = 5 is the best both ways (0.638 on all rows, 0.633 on the sample). The sample needs only 300 × 300 = 90,000 distances instead of 1,000,000 and still picks the same k.

4. Check the quiz cluster with NumPy: its centroid, its inertia, and the sum of squares around another point.

Solution
import numpy as np
P = np.array([[1, 2], [3, 2], [2, 5]])                                  # the quiz cluster
c = P.mean(axis=0)
print("centroid:", c)
print("squared distances:", ((P - c) ** 2).sum(axis=1))
print("inertia of this cluster:", ((P - c) ** 2).sum())
print("sum of squares around (2, 2):", ((P - [2, 2]) ** 2).sum())       # any other point gives more

Output:

centroid: [2. 3.]
squared distances: [2. 2. 4.]
inertia of this cluster: 8.0
sum of squares around (2, 2): 11

The centroid (2, 3) gives a sum of squared distances of 8; moving the centre to (2, 2) makes it 11. The mean is the point with the smallest sum of squares, which is why the update step can never increase inertia.

5. What does predict really do? Compare it with the distance to every hub (transform).

Solution
import numpy as np
r = np.random.default_rng(1)                                             # Riya's 1,000 customers (made up)
X = np.vstack([r.normal(m, s, (n, 2)) for m, s, n in [([2.5, 7.5], 1, 500), ([7.5, 8], .6, 120),
               ([5, 4.5], .5, 100), ([2, 2], .6, 140), ([8, 2], .6, 140)]])  # 5 neighbourhoods, (x, y) in km
from sklearn.cluster import KMeans
km = KMeans(5, n_init=10, random_state=0).fit(X)
new = np.array([[6, 7.5], [2, 2.5], [5, 5]])
print("predict:", km.predict(new))
print("distance to each hub:"); print(km.transform(new).round(2))      # transform = distance to every centroid
print("argmin of each row:", km.transform(new).argmin(axis=1))

Output:

predict: [0 1 4]
distance to each hub:
[[1.57 6.81 3.67 5.8  3.05]
 [7.72 0.48 5.07 6.08 3.61]
 [3.84 4.26 3.69 4.23 0.35]]
argmin of each row: [0 1 4]

transform gives each new row's distance to every centroid; predict is exactly the argmin of that table: the assignment step, with the centroids frozen.

Quick quiz

1. A cluster has three customers: (1, 2), (3, 2) and (2, 5). Where does its centroid go after the update step? Options: (2, 2) · (2, 3) · (3, 5) · (6, 9).

Answer

(2, 3). The update step moves the centroid to the mean: x = (1 + 3 + 2) / 3 = 2, y = (2 + 2 + 5) / 3 = 3. ((6, 9) is the sum, not the mean.)

2. Inertia for k = 5 is 1,253 and for k = 6 is 953. Does that mean k = 6 is better?

Answer

No. Inertia always falls when you add a cluster (k = 1,000 gives 0). Compare the size of the drops (elbow) or use the silhouette score, which is higher for k = 5 (0.638) than k = 6 (0.522).

3. A row has a = 2 and b = 1. What is its silhouette, and what does it mean?

Answer

s = (1 − 2) / max(2, 1) = −0.5. Negative: the row is closer to another cluster than to its own, so it is probably in the wrong cluster.

4. Why can't a k-means++ start pick the same customer twice?

Answer

A customer already chosen as a centre has distance 0 to the nearest centre, so its chance, proportional to 0², is 0.

5. You cluster columns income_rs (thousands) and age (tens) without scaling. What happens?

Answer

The distance is ruled almost entirely by income_rs, so the clusters cut by income alone and ignore age (like the raw crosstab, where daily customers were split 220 / 80). Standardise first.

Interview questions

  1. What is clustering, and why is it unsupervised? Grouping similar rows together; there are no labels to learn from, only the rows themselves.
  2. Describe the k-means (Lloyd's) algorithm. Choose k starting centres; assign every row to its nearest centre; move each centre to the mean of its rows; repeat until assignments stop changing.
  3. What does k-means minimise? Inertia, the within-cluster sum of squares: the sum of squared distances from each row to its own centroid.
  4. Why does k-means always converge? Both steps can only lower (or keep) inertia, and there are only finitely many ways to assign rows to clusters, so it must stop; but it stops at a local minimum, not necessarily the best one.
  5. What can go wrong with random initialisation? An empty cluster (mean of no rows gives nan) if starts are random spots, and getting stuck in a local minimum (3 of 20 runs at 3,167 or more vs 1,253).
  6. Explain k-means++. First centre: a random row. Each next centre: a row chosen with probability proportional to its squared distance to the nearest chosen centre. Arthur and Vassilvitskii (2007) show it is Θ(log k)-competitive and that it improves speed and accuracy. It is scikit-learn's default init.
  7. What is n_init? How many times k-means runs from different starts; the lowest-inertia run is kept.
  8. How do you choose k? Not by the lowest inertia (it always falls). Use the elbow method (where the inertia curve bends) and the silhouette score (pick the highest), plus what makes sense for the business (Riya can only afford so many hubs).
  9. Define the silhouette. For one row, s = (b − a) / max(a, b), where a is the mean distance to its own cluster and b the mean distance to the nearest other cluster; from −1 to +1. The silhouette score is the mean over all rows (Rousseeuw, 1987).
  10. Why scale features before k-means? It uses distances, which are dominated by the column with the largest numbers; unscaled, spend split the daily customers (207 mistakes), scaled only 16.
  11. When would you use MiniBatchKMeans? Millions of rows or streaming data: it updates centroids from small random batches (Sculley, 2010). Here about 10× faster (7.6 s vs 0.7 s) for about 12% higher inertia.
  12. What shapes of clusters does k-means handle badly? Since every row goes to its nearest centroid, it assumes round, similar-sized blobs; long, curved or very uneven clusters need other methods (next episode).
  13. Is the cluster number meaningful? No; it is an arbitrary name (scikit-learn returned our 5 hubs in a different order). Interpret clusters by their centroids or by group averages.

Glossary

Term Meaning (plain words + example)
Label The answer column in supervised learning: late / on time. Clustering has none
Supervised learning Learning from rows with labels to predict the label
Unsupervised learning Learning from rows without labels: finding structure, such as groups
Clustering Putting similar (close) rows into the same group: sorting laundry without names
Cluster One group found by clustering: all customers served by one hub
k The number of clusters you ask for: Riya's 5 hubs
Distance (Euclidean) Straight-line distance: from (0, 0) to (3, 4) is 5
Vector A row of numbers as a point: a customer at (2.85, 8.32)
Broadcasting NumPy stretching shapes to combine arrays: X[:, None] - c gives (1000, 5, 2)
axis The direction an operation runs: axis=1 gives one result per row
argmin Position of the smallest value: [3.1, 0.4, 2.0].argmin() is 1
np.bincount Counts how often each whole number appears: cluster sizes [480 140 140 118 122]
np.allclose True if two arrays are equal up to tiny rounding: used to detect convergence
Boolean mask X[lab == j]: keep only the rows where the condition is True
Centroid The centre of a cluster: the mean of its rows. (1, 2), (3, 2), (2, 5) → (2, 3)
Cluster assignment The cluster number given to a row: its nearest centroid
Assignment step Every row picks its nearest centroid
Update step Every centroid moves to the mean of its rows
Lloyd's algorithm Assign, update, repeat until nothing changes (S. P. Lloyd, 1982); what everyone calls k-means
k-means Clustering into k groups, each represented by a mean
Convergence The point where assignments stop changing: here after 5 steps
Inertia / within-cluster sum of squares (WCSS) Sum of squared distances from each row to its own centroid: 1,252.8 for Riya's 5 hubs
Empty cluster A centroid no row chose: happens with random map spots
nan (not a number) Float value for an undefined result such as 0 / 0; spreads through every calculation
RuntimeWarning A warning while the program runs that something is suspicious, without stopping it: Mean of empty slice
Local minimum A spot no small move improves, but not the best: inertia 3,531 instead of 1,253
Initialisation (init) How the starting centroids are chosen
Random-customer start Use k random rows as starting centroids: no empty cluster at step 0
k-means++ Smart start: next centre picked with chance ∝ squared distance to the nearest centre (Arthur and Vassilvitskii, 2007)
Proportional (∝) Twice as big gives twice the chance
Outlier A row far from all others: a lone farmhouse outside the city
Θ(log k)-competitive k-means++ guarantee: expected inertia within a factor growing like log k of the best possible
Restarts, n_init Run k-means several times from different starts, keep the lowest inertia
random_state Fixes the randomness so every run gives the same result
KMeans scikit-learn's k-means: KMeans(n_clusters=5, n_init=10, random_state=0)
fit, fit_predict Run the algorithm; fit_predict also returns each row's cluster
cluster_centers_, labels_, inertia_ The centroids, each training row's cluster, and the inertia after fit
predict Assign new rows to the nearest centroid without moving centroids: (6, 7.5) → hub 0
transform Each row's distance to every centroid
Elbow method Plot inertia vs k; pick k where the curve bends and extra clusters stop helping: k = 5
a (silhouette) A row's mean distance to the other rows of its own cluster: 1.43 km for customer 0
b (silhouette) A row's mean distance to the rows of the nearest other cluster: 4.24 km
Silhouette (one row) s = (b − a) / max(a, b), from −1 (wrong cluster) through 0 (border) to +1 (snug): 0.662
Silhouette score Mean silhouette over all rows (Rousseeuw, 1987); highest picks k: 0.638 at k = 5
silhouette_samples scikit-learn: one silhouette value per row
Pairwise distances Every row's distance to every other row: 1,000 rows → 1,000,000 distances
sample_size Compute the silhouette on a random sample of rows, for big data
Feature One column: spend_rs, orders
Feature scaling Putting columns on comparable scales so no column rules the distance
StandardScaler Rescales each column to mean 0, standard deviation 1
Cross-tabulation (pd.crosstab) A count table of one column against another: true group vs cluster
Pipeline (make_pipeline) Scaler + model as one object, so new rows are scaled the same way
Mini-batch A small random subset of rows used for one update step: 2,048 rows
Mini-batch k-means (MiniBatchKMeans) k-means updating centroids from small batches (Sculley, 2010): 0.7 s vs 7.6 s, slightly higher inertia
batch_size Rows per mini-batch (default 1,024)
n_samples, n_clusters Number of rows; number of clusters (k). Need n_samples ≥ n_clusters
ValueError Python error for a bad value: X has 3 features, but KMeans is expecting 2 features as input.

Summary

  • Clustering finds groups in rows without labels; "similar" means close together.
  • k-means (Lloyd's algorithm) repeats two steps: assign each row to its nearest centroid, move each centroid to the mean of its rows. Riya's average trip fell from 2.57 km (strips) to 0.97 km.
  • Inertia (within-cluster sum of squares) only goes down during k-means: 8,035.7 → 1,252.8 in 5 steps.
  • Starting at random map spots can leave a cluster empty (Mean of empty slice, nan); start at data points.
  • Random starts can get stuck in a local minimum (3 of 20 runs); k-means++ (0 of 20) and n_init restarts fix it.
  • Inertia always falls with k (k = 1,000 gives 0): choose k with the elbow method and the silhouette score (best k = 5, 0.638).
  • Scale your columns before clustering (207 mistakes raw, 16 scaled).
  • Use MiniBatchKMeans for millions of rows: about 10× faster, about 12% higher inertia.
  • k-means assumes round, similar-sized blobs and makes you choose k.

Next episode: Hierarchical clustering and DBSCAN: dendrograms, linkage, and clusters of any shape, with noise.