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 vectorv; 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 hubschave shape (5, 2);X[:, None] - cbecomes 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=1works 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()is1.- 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.shapeis(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.dis 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.bincountcounts 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:
- 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.
- 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).
- 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.nanspreads: any arithmetic withnangivesnan, so every distance to that hub isnan, inertia becomesnan, andargminover a row withnanin it returns the position of thenan, 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:
- 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). - 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
kmeansis a shorter version:c, old = new_centroids, ckeeps the previous centroids inold, and as soon as nothing moved (np.allclose(c, old)) it returns the inertia. randandppare 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 withinit="random".)random_state=0: fixes the randomness so the result is the same every run..fit(X): runs the algorithm. Note there is noy: 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) isfit(X)then returnslabels_.
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
dis 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.repeatwrites 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 topredictmust have exactly the columns used infit, 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
- What is clustering, and why is it unsupervised? Grouping similar rows together; there are no labels to learn from, only the rows themselves.
- 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.
- What does k-means minimise? Inertia, the within-cluster sum of squares: the sum of squared distances from each row to its own centroid.
- 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.
- 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). - 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. - What is
n_init? How many times k-means runs from different starts; the lowest-inertia run is kept. - 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).
- 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).
- 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.
- 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.
- 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).
- 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_initrestarts 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
MiniBatchKMeansfor 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.