Machine Learning Full Course · Episode 45. Every code sample below was run with Python 3.13, NumPy 2.5.3, pandas 3.0.5, SciPy 1.18.1 and scikit-learn 1.9.1; the output shown is the real output. Riya's 1,000 trips are made up for teaching. Because we made the data ourselves, we secretly know which vehicle made every trip, which lets us check whether the clustering recovered it.
The big idea: k-means (Episode 43), hierarchical clustering and DBSCAN give hard answers: "this trip is in cluster 2, full stop". A Gaussian mixture model (GMM) gives soft answers: "this trip is 49% bicycle, 51% scooter". It explains the data as a few bell-shaped ovals (components), each with a weight (its share of the rows), a mean (its centre) and a covariance (its spread and tilt). It is trained with the EM algorithm: the E-step computes how much each component is responsible for each row (responsibilities, from Bayes' theorem), the M-step refits each oval using those responsibilities as weights, and the log-likelihood never goes down (-4828 → -3954 on Riya's trips). On two stretched, tilted ovals, k-means splits the bicycles 196 / 204 (a coin toss), while a GMM with covariance_type="full" puts only 26 of 1,000 trips with the wrong vehicle. The likelihood alone always wants more components, so choose the number with AIC or BIC, which add a price for every learned number (both lowest at 2). Judge clusters with the adjusted Rand index (0.898), never accuracy (the same clusters scored 0.974 and 0.026), and treat internal scores like Davies-Bouldin and silhouette with care: here they wrongly preferred k-means.
Sources: A. P. Dempster, N. M. Laird and D. B. Rubin, "Maximum Likelihood from Incomplete Data via the EM Algorithm", Journal of the Royal Statistical Society, Series B, 39(1):1-38, 1977 (PDF at cs.brown.edu); the docstrings of the installed scikit-learn 1.9.1: GaussianMixture (covariance_type is one of full, tied, diag, spherical, default full; attributes weights_, means_, covariances_, n_iter_; methods predict_proba, aic, bic, and score, which returns the per-sample average log-likelihood), adjusted_rand_score and davies_bouldin_score. The formulas AIC = 2p − 2 log L and BIC = p ln(n) − 2 log L were checked against the printed numbers (p = 11 for 2 full components in 2-D gives 7929 and 7983).
Words you need first
- Clustering, cluster, unsupervised learning (Episodes 1 and 43): putting similar rows into groups when there are no labels (no answer column). A cluster is one such group.
- k-means, centroid, inertia,
n_init, silhouette (Episode 43): k-means gives every row to its nearest centre (the centroid) and moves each centre to the mean of its rows; inertia is the total squared distance to the own centroid;n_initis how many different starts to try (the best is kept); the silhouette score measures how snug each row is in its cluster compared with the nearest other one, from −1 to +1. - Hierarchical clustering and DBSCAN (Episode 44): other clustering methods; both also give hard labels (DBSCAN can also say "noise", label −1).
- Normal distribution (Episode 10): the bell curve. Described by a mean (where the bell's peak sits) and a standard deviation (how wide it is). Example: bicycle trip distances with mean 2.2 km and standard deviation 0.7 km: most trips are between 1.5 and 2.9 km.
- Variance and covariance (Episode 11): variance is the standard deviation squared (spread of one column). Covariance says whether two columns rise together: positive covariance between km and minutes means longer trips take more minutes.
- Probability, conditional probability, Bayes' theorem (Episode 9): P(A | B) is "the probability of A given that B happened". Bayes' theorem turns "how likely is this data if the cause were X" into "how likely is cause X given this data".
- Likelihood (Episode 12): how probable the observed data is under a model; a better model makes the data more probable.
- Standardising,
StandardScaler(Episode 16): rescale every column to mean 0 and standard deviation 1. - Cross-tabulation (
pd.crosstab): a count table of one column against another, here true vehicle against cluster. - Random generator:
np.random.default_rng(7)makes the same "random" numbers every run, so you get exactly the outputs printed here.
The real-life hook: which trips were by bicycle?
Riya's riders use two kinds of vehicle:
- Bicycle riders take short trips, and every extra kilometre costs them about 5.5 minutes.
- Scooter riders take longer trips, and every extra kilometre costs only about 2 minutes.
She has an old log of 1,000 trips: distance (km) and time (minutes). The vehicle was never written down. She wants to recover it, to plan how many bicycles and scooters to buy. We made the data, so we secretly know the truth: 400 bicycle trips and 600 scooter trips. These four lines create it; every program below starts with them (we call them HDR):
import numpy as np, pandas as pd
r = np.random.default_rng(7) # 1,000 trips, vehicle NOT recorded (made up)
km = np.r_[r.normal(2.2, .7, 400), r.normal(4.5, 1.6, 600)].clip(.3) # 400 bicycle trips, 600 scooter trips
minutes = np.r_[5 + 5.5 * km[:400], 7 + 2.0 * km[400:]] + r.normal(0, 1.5, 1000)
X = np.c_[km, minutes]; vehicle = np.repeat(["bicycle", "scooter"], [400, 600]) # the truth, hidden from the model
r.normal(2.2, .7, 400): 400 bicycle distances around 2.2 km;r.normal(4.5, 1.6, 600): 600 scooter distances around 4.5 km;.clip(.3)makes every trip at least 0.3 km.- Minutes: bicycle trips take 5 + 5.5 × km, scooter trips 7 + 2 × km, plus random noise of about 1.5 minutes.
np.c_[km, minutes]puts the two columns side by side:Xhas shape (1000, 2), one row per trip.vehicleholds the truth, which the model never sees.
Picture the data: a steep, narrow oval of bicycle trips (time rises fast with distance) and a flatter, longer oval of scooter trips. They overlap at the bottom left, where short trips live.
The obvious attempt: k-means
k-means with two clusters, once on the raw columns and once scaled (Episode 43 taught us to scale). The table compares the truth with the clusters:
import numpy as np, pandas as pd
r = np.random.default_rng(7) # 1,000 trips, vehicle NOT recorded (made up)
km = np.r_[r.normal(2.2, .7, 400), r.normal(4.5, 1.6, 600)].clip(.3) # 400 bicycle trips, 600 scooter trips
minutes = np.r_[5 + 5.5 * km[:400], 7 + 2.0 * km[400:]] + r.normal(0, 1.5, 1000)
X = np.c_[km, minutes]; vehicle = np.repeat(["bicycle", "scooter"], [400, 600]) # the truth, hidden from the model
from sklearn.cluster import KMeans; from sklearn.preprocessing import StandardScaler
print("first trips (km, min):", X[:3].round(1).tolist())
for name, data in [("k-means, raw", X), ("k-means, scaled", StandardScaler().fit_transform(X))]:
lab = KMeans(2, n_init=10, random_state=0).fit_predict(data)
print(name); print(pd.crosstab(vehicle, lab, rownames=["truth"], colnames=["cluster"]))
Output:
first trips (km, min): [[2.2, 17.6], [2.4, 18.8], [2.0, 15.4]]
k-means, raw
cluster 0 1
truth
bicycle 196 204
scooter 325 275
k-means, scaled
cluster 0 1
truth
bicycle 107 293
scooter 323 277
- Raw: the bicycle trips split 196 / 204 between the clusters. That is a coin toss.
- Scaled: 107 / 293, with scooters spread over both clusters (323 / 277). Scaling did not save it.
Why? k-means only knows round blobs around a centre: every row goes to the nearest centroid, so the border between two clusters is always a straight line halfway between the centres. It cuts straight across both ovals. Two things are missing:
- Clusters with their own shape: stretched and tilted ovals.
- Honesty about the overlap: a short trip near the bottom left could really be either vehicle.
Hard vs soft clustering
- Hard clustering: each row gets exactly one cluster. Example: trip 17 → cluster 1.
- Soft clustering: each row gets a probability for every cluster. Example: trip 17 → bicycle 0.70, scooter 0.30.
- For every row the probabilities add up to 1.
Like a doctor saying "70% this is a cold, 30% the flu" instead of pretending to be sure. You can always turn soft labels into hard ones (pick the biggest probability), but not the other way round. Where would those probabilities come from? From a model of what each group's data looks like.
Gaussian mixtures: bell curves, added up
Look first at only the distances. Their histogram has two humps. Suppose each vehicle's distances follow their own bell curve (a Gaussian, another name for the normal distribution):
- Each bell curve is called a component (a mixture component).
- Each component has a mixture weight: the fraction of rows that come from it. The weights add up to 1. Example: 0.4 for bicycles, 0.6 for scooters.
- Multiply each bell curve by its weight and add them: you get one curve with two humps that matches the histogram.
A distribution made by adding weighted Gaussians is a Gaussian mixture. Fitted on distance alone:
import numpy as np, pandas as pd
r = np.random.default_rng(7) # 1,000 trips, vehicle NOT recorded (made up)
km = np.r_[r.normal(2.2, .7, 400), r.normal(4.5, 1.6, 600)].clip(.3) # 400 bicycle trips, 600 scooter trips
minutes = np.r_[5 + 5.5 * km[:400], 7 + 2.0 * km[400:]] + r.normal(0, 1.5, 1000)
X = np.c_[km, minutes]; vehicle = np.repeat(["bicycle", "scooter"], [400, 600]) # the truth, hidden from the model
from sklearn.mixture import GaussianMixture # distance alone: a 1-D mixture
gm = GaussianMixture(2, random_state=0).fit(km.reshape(-1, 1))
order = gm.means_.ravel().argsort() # smaller mean first (bicycles)
print("weights:", gm.weights_[order].round(2), " means (km):", gm.means_.ravel()[order].round(2))
print("spreads (std, km):", np.sqrt(gm.covariances_.ravel()[order]).round(2), " truth: weights [0.4 0.6]")
Output:
weights: [0.55 0.45] means (km): [2.32 4.97]
spreads (std, km): [0.8 1.27] truth: weights [0.4 0.6]
With distance alone the weights come out 0.55 / 0.45, but the truth is 0.4 / 0.6: on distance alone the two vehicles overlap a lot (a 3 km trip could be either), so the fit cannot separate them well. Using both columns does much better.
Density
A density (probability density) is the height of the curve at a point: how crowded the data is around that value. It is not a probability itself (it can be bigger than 1), but a higher density means "values near here are more common". Example: under the bicycle curve, the density at 2.2 km (its mean) is high, at 7 km almost zero. In two columns, a Gaussian is an oval of points (a hill seen from above), and its density is highest at the centre and falls off towards the edges.
A Gaussian mixture model (GMM)
A Gaussian mixture model says: the data comes from k ovals. Each component j has three things:
| Part | Meaning | Riya's bicycle component |
|---|---|---|
| Weight w_j | Share of rows from this component | about 0.40 |
| Mean μ_j | Centre of the oval (one number per column) | about (2.1 km, 16.7 min) |
| Covariance Σ_j | Shape of the oval: spread of each column, and tilt | steep: minutes rise ~5.4 per km |
The covariance of a component is a small table (a matrix). In 2-D it holds the variance of km, the variance of minutes, and the covariance of km with minutes. The first two stretch the oval along the axes; the third tilts it. Positive covariance = the oval leans up to the right.
Soft labels from Bayes' theorem
The probability that a row x came from component j:
P(component j | x) = w_j · density_j(x) / Σ_k w_k · density_k(x)
In words: weight times how dense that oval is at this row, divided by the total over all components so the probabilities add up to 1. The weight is the prior (how common the component is before looking at the row); the density is how well the row fits that oval. Checked by hand for the trip "3 km in 17 minutes":
import numpy as np, pandas as pd
r = np.random.default_rng(7) # 1,000 trips, vehicle NOT recorded (made up)
km = np.r_[r.normal(2.2, .7, 400), r.normal(4.5, 1.6, 600)].clip(.3) # 400 bicycle trips, 600 scooter trips
minutes = np.r_[5 + 5.5 * km[:400], 7 + 2.0 * km[400:]] + r.normal(0, 1.5, 1000)
X = np.c_[km, minutes]; vehicle = np.repeat(["bicycle", "scooter"], [400, 600]) # the truth, hidden from the model
from sklearn.mixture import GaussianMixture; from scipy.stats import multivariate_normal as mvn
gm = GaussianMixture(2, random_state=0).fit(X); t = [3.0, 17.0] # Bayes by hand for one trip
top = [gm.weights_[j] * mvn.pdf(t, gm.means_[j], gm.covariances_[j]) for j in range(2)]
print("weight x density:", np.round(top, 5), " sum", round(sum(top), 5))
print("by hand:", np.round(np.array(top) / sum(top), 3), " predict_proba:", gm.predict_proba([t]).round(3)[0])
print("same trip typed as integers [[3, 17]]:", gm.predict_proba([[3, 17]]).round(3)[0])
Output:
weight x density: [0.00056 0.00059] sum 0.00115
by hand: [0.488 0.512] predict_proba: [0.488 0.512]
same trip typed as integers [[3, 17]]: [0.477 0.523]
Weight × density is 0.00056 for component 0 and 0.00059 for component 1; divided by their sum 0.00115 that gives 0.488 / 0.512, exactly what scikit-learn's predict_proba returns. (When we typed the same trip as integers, [[3, 17]], this install printed 0.477 / 0.523; we did not dig into why, so pass decimals such as 3.0 when you want the exact numbers.)
The EM algorithm: a chicken-and-egg problem
- If we knew each trip's vehicle, measuring each vehicle's oval would be easy: its share of trips (weight), its average (mean), its covariance.
- If we knew the two ovals, guessing each trip's vehicle would be easy: Bayes, as above.
- We know neither. Chicken and egg.
So start with a rough guess of the ovals and alternate:
- E-step (expectation): compute every row's soft membership in every component. These are called responsibilities:
resp[i, j]is how much component j is responsible for row i. Each row's responsibilities add up to 1. - M-step (maximisation): refit each oval using the responsibilities as weights. A row with responsibility 0.9 counts as 0.9 of a row for that component.
This is the expectation-maximisation (EM) algorithm, described by Dempster, Laird and Rubin in 1977 for "maximum likelihood from incomplete data": here the incomplete part is the missing vehicle column. Each round, the likelihood never goes down.
Likelihood and log-likelihood
- The likelihood L of the model is the probability density of all the data under it: the mixture's density at row 1 × density at row 2 × ... × density at row 1,000. A bigger L means the model explains the data better.
- Multiplying 1,000 small numbers gives an absurdly tiny number, so we take the log: the log-likelihood log L = sum over rows of log(mixture density at that row). Logs of numbers below 1 are negative, so log L is negative; closer to zero is better (−3954 beats −4828).
One round of EM, in code
dens[i, j] = w[j] · N(x_i | mu[j], cov[j]) # weight times Gaussian density
resp = dens / row sums # E-step
w = resp.sum(0) / n # M-step: new weights
mu, cov = responsibility-weighted mean and covariance
N(x | mu, cov) is the Gaussian density with that mean and covariance; SciPy computes it with multivariate_normal.pdf. Notice it is k-means again, assign then update, except no row is forced into one group: every row is shared softly.
EM from scratch
Start with weights 50 / 50, means at two random trips, and both covariances equal to the whole data's covariance (np.cov(X.T)), then 30 rounds:
import numpy as np, pandas as pd
r = np.random.default_rng(7) # 1,000 trips, vehicle NOT recorded (made up)
km = np.r_[r.normal(2.2, .7, 400), r.normal(4.5, 1.6, 600)].clip(.3) # 400 bicycle trips, 600 scooter trips
minutes = np.r_[5 + 5.5 * km[:400], 7 + 2.0 * km[400:]] + r.normal(0, 1.5, 1000)
X = np.c_[km, minutes]; vehicle = np.repeat(["bicycle", "scooter"], [400, 600]) # the truth, hidden from the model
from scipy.stats import multivariate_normal as mvn
k = 2; w = np.full(k, 1 / k) # mixture weights (start: 50 / 50)
mu = X[np.random.default_rng(1).choice(len(X), k, replace=False)] # means: 2 random trips
cov = np.array([np.cov(X.T)] * k) # covariances: the whole data's
for it in range(30):
dens = np.column_stack([w[j] * mvn.pdf(X, mu[j], cov[j]) for j in range(k)])
loglik = np.log(dens.sum(axis=1)).sum() # how well the mixture explains X
resp = dens / dens.sum(axis=1, keepdims=True) # E-step: soft membership, rows sum to 1
n = resp.sum(axis=0) # M-step: weighted counts ...
w = n / len(X); mu = resp.T @ X / n[:, None] # ... weights and means
cov = np.array([(resp[:, j, None] * (X - mu[j])).T @ (X - mu[j]) / n[j] for j in range(k)])
if it % 5 == 0 or it == 29: print(f"iter {it:2}: log-likelihood {loglik:8.1f} weights {w.round(3)}")
print("means (km, min):", mu.round(1).tolist())
print(pd.crosstab(vehicle, resp.argmax(axis=1), rownames=["truth"], colnames=["component"]))
Output:
iter 0: log-likelihood -4828.4 weights [0.371 0.629]
iter 5: log-likelihood -4210.7 weights [0.516 0.484]
iter 10: log-likelihood -3956.4 weights [0.586 0.414]
iter 15: log-likelihood -3953.6 weights [0.596 0.404]
iter 20: log-likelihood -3953.6 weights [0.597 0.403]
iter 25: log-likelihood -3953.6 weights [0.598 0.402]
iter 29: log-likelihood -3953.6 weights [0.598 0.402]
means (km, min): [[4.4, 15.8], [2.1, 16.7]]
component 0 1
truth
bicycle 7 393
scooter 581 19
resp.sum(axis=0)is each component's total responsibility, an "effective number of rows". New weight = that / 1,000.resp.T @ X / n[:, None]is the responsibility-weighted mean of every column (@is matrix multiplication).- The covariance line averages (x − μ)(x − μ)ᵀ with each row counted by its responsibility.
Read the output:
- Log-likelihood: −4828.4 → −4210.7 → −3956.4 → settles at −3953.6 by round 15. It only went up.
- Weights: 0.598 / 0.402: the 600 scooters and 400 bicycles we hid.
- Means: (4.4 km, 15.8 min) for scooters and (2.1 km, 16.7 min) for bicycles.
- Table: only 7 + 19 = 26 of 1,000 trips on the wrong side (
resp.argmax(axis=1)turns soft labels into hard ones).
You just invented Gaussian mixture models trained with EM.
Convergence and local optima
- Convergence: EM stops changing; here from round 15 on the log-likelihood stays at −3953.6. scikit-learn stops when the improvement falls below a small tolerance (
tol) or aftermax_iterrounds. - Local optimum: like k-means, EM only climbs uphill from where it starts, so a bad start can stop on a lower hill (a solution that no small change improves, but not the best one). Practice 6 started 20 runs from random trips (
init_params="random_from_data"): 3 of 20 got stuck near −4460 instead of −3953.6. Withn_init=10(10 starts, keep the best) every run reached −3953.6. - scikit-learn's default start (
init_params="kmeans") runs k-means first; on these trips it always reached the best answer.
GaussianMixture in scikit-learn
import numpy as np, pandas as pd
r = np.random.default_rng(7) # 1,000 trips, vehicle NOT recorded (made up)
km = np.r_[r.normal(2.2, .7, 400), r.normal(4.5, 1.6, 600)].clip(.3) # 400 bicycle trips, 600 scooter trips
minutes = np.r_[5 + 5.5 * km[:400], 7 + 2.0 * km[400:]] + r.normal(0, 1.5, 1000)
X = np.c_[km, minutes]; vehicle = np.repeat(["bicycle", "scooter"], [400, 600]) # the truth, hidden from the model
from sklearn.mixture import GaussianMixture
gm = GaussianMixture(n_components=2, covariance_type="full", random_state=0).fit(X)
print("weights:", gm.weights_.round(3), " iterations:", gm.n_iter_)
print("means (km, min):", gm.means_.round(1).tolist())
print(pd.crosstab(vehicle, gm.predict(X), rownames=["truth"], colnames=["component"]))
trips = [[3, 22], [5, 17], [2.5, 15], [3, 17]] # (km, minutes)
for t, p in zip(trips, gm.predict_proba(trips)): # soft labels: a probability each
print(f"{t[0]} km in {t[1]} min -> component 0: {p[0]:.2f} component 1: {p[1]:.2f}")
Output:
weights: [0.403 0.597] iterations: 23
means (km, min): [[2.1, 16.7], [4.4, 15.8]]
component 0 1
truth
bicycle 393 7
scooter 19 581
3 km in 22 min -> component 0: 1.00 component 1: 0.00
5 km in 17 min -> component 0: 0.00 component 1: 1.00
2.5 km in 15 min -> component 0: 0.65 component 1: 0.35
3 km in 17 min -> component 0: 0.49 component 1: 0.51
GaussianMixture(n_components=2, covariance_type="full"): 2 components, each with its own tilted oval.weights_,means_: the same answer as our scratch EM (0.403 / 0.597, (2.1, 16.7) and (4.4, 15.8)).n_iter_: 23 EM rounds until convergence.predict(X): hard labels (the most probable component). The same 26 mistakes (7 + 19).- Component 0 is the bicycles this time; in the scratch version it was component 1. Component numbers are arbitrary names.
predict_proba(trips): soft labels, one row per trip, one column per component, each row adds up to 1:- 3 km in 22 min: 1.00 component 0: certainly a bicycle (slow per km).
- 5 km in 17 min: 1.00 component 1: certainly a scooter.
- 2.5 km in 15 min: 0.65 / 0.35: leaning bicycle.
- 3 km in 17 min: 0.49 / 0.51: the model honestly says "I can't tell". k-means would just have picked one.
Covariance types: how free is each oval?
scikit-learn's covariance_type:
| Type | Shape of each component | Learned covariance numbers in 2-D (2 components) |
|---|---|---|
spherical |
A circle: one spread per component | 1 per component → 2 |
diag (diagonal) |
An oval stretched only along the axes, never tilted | 2 per component → 4 |
tied |
Any tilt, but all components share one shape | 3, shared → 3 |
full (default) |
Each component its own tilted oval | 3 per component → 6 |
More freedom means more numbers to learn. A full covariance in d columns has d(d + 1) / 2 numbers per component (d variances plus d(d − 1)/2 covariances): 3 for d = 2, but 100 × 101 / 2 = 5,050 for d = 100. Simpler types exist for when rows are few compared with columns.
import numpy as np, pandas as pd
r = np.random.default_rng(7) # 1,000 trips, vehicle NOT recorded (made up)
km = np.r_[r.normal(2.2, .7, 400), r.normal(4.5, 1.6, 600)].clip(.3) # 400 bicycle trips, 600 scooter trips
minutes = np.r_[5 + 5.5 * km[:400], 7 + 2.0 * km[400:]] + r.normal(0, 1.5, 1000)
X = np.c_[km, minutes]; vehicle = np.repeat(["bicycle", "scooter"], [400, 600]) # the truth, hidden from the model
from sklearn.mixture import GaussianMixture
for ct in ["spherical", "diag", "tied", "full"]: # what shape may each component take?
lab = GaussianMixture(2, covariance_type=ct, random_state=0).fit_predict(X)
t = pd.crosstab(vehicle, lab).values; wrong = min(t[0, 1] + t[1, 0], t[0, 0] + t[1, 1])
print(f"{ct:9} trips put with the wrong vehicle: {wrong:3} of 1000")
Output:
spherical trips put with the wrong vehicle: 471 of 1000
diag trips put with the wrong vehicle: 355 of 1000
tied trips put with the wrong vehicle: 445 of 1000
full trips put with the wrong vehicle: 26 of 1000
spherical: 471 wrong (almost a coin toss).diag: 355.tied: 445.full: 26.wrong = min(...): since component numbers are arbitrary, count the mistakes both ways round and keep the smaller.
Why? The two vehicles' ovals tilt at different angles: time rises fast with distance on a bicycle, slowly on a scooter. Circles and axis-aligned ovals cannot tilt, and tied forces one tilt on both. Only full can draw both shapes. The shape you allow decides what you can find.
How many components? AIC and BIC
Riya assumed two vehicles. What if there were three? Fit 1 to 6 components:
import numpy as np, pandas as pd
r = np.random.default_rng(7) # 1,000 trips, vehicle NOT recorded (made up)
km = np.r_[r.normal(2.2, .7, 400), r.normal(4.5, 1.6, 600)].clip(.3) # 400 bicycle trips, 600 scooter trips
minutes = np.r_[5 + 5.5 * km[:400], 7 + 2.0 * km[400:]] + r.normal(0, 1.5, 1000)
X = np.c_[km, minutes]; vehicle = np.repeat(["bicycle", "scooter"], [400, 600]) # the truth, hidden from the model
from sklearn.mixture import GaussianMixture
for n in range(1, 7): # how many components?
gm = GaussianMixture(n, random_state=0).fit(X)
loglik = gm.score(X) * len(X) # score = average log-likelihood per row
print(f"{n} components: log-likelihood {loglik:7.1f} AIC {gm.aic(X):6.0f} BIC {gm.bic(X):6.0f}")
Output:
1 components: log-likelihood -4480.5 AIC 8971 BIC 8996
2 components: log-likelihood -3953.6 AIC 7929 BIC 7983
3 components: log-likelihood -3954.2 AIC 7942 BIC 8026
4 components: log-likelihood -3952.3 AIC 7951 BIC 8064
5 components: log-likelihood -3949.2 AIC 7956 BIC 8099
6 components: log-likelihood -3950.3 AIC 7971 BIC 8142
gm.score(X)is the average log-likelihood per row, so × 1,000 gives the total log L.- The obvious way, the highest likelihood, fails: from 1 to 2 components it jumps a lot (−4480.5 → −3953.6), then barely moves (−3954.2, −3952.3, −3949.2, −3950.3). More components can almost always squeeze out a tiny bit more, the same trap as inertia in Episode 43. (3 and 6 components are even slightly below their smaller neighbours: EM stopped on a local optimum from its single start.)
- AIC and BIC are both lowest at 2 components: 7929 and 7983.
AIC and BIC: fit minus a price
AIC = 2p − 2 log L
BIC = p · ln(n) − 2 log L
- p = number of learned numbers (parameters), n = number of rows, ln = natural log.
- Both start from −2 log L, so a better fit lowers them; then they add a price for every number the model learns. Lower is better.
- Like a tailor who charges for every extra measurement: a better fit is worth it only if it is much better.
- AIC (Akaike information criterion) charges 2 per number. BIC (Bayesian information criterion) charges ln(n) per number: ln(1000) = 6.908, so BIC punishes size harder and prefers smaller models. BIC is the usual choice for picking the number of components.
Worked example, p = 11 (2 full components in 2-D):
- Weights: 2 weights, but they must add up to 1, so only 1 is free.
- Means: 2 components × 2 columns = 4.
- Covariances: 2 components × 3 = 6.
- p = 1 + 4 + 6 = 11.
- log L = −3953.6, so −2 log L = 7907.2. AIC = 2 × 11 + 7907.2 = 7929.2 (printed 7929). BIC = 11 × 6.908 + 7907.2 = 7983.2 (printed 7983).
Practice 5 counts p for every covariance type and recomputes AIC and BIC by hand: spherical 7, diag 9, tied 8, full 11, and the formulas match scikit-learn to the decimal.
Judging clusters
How do you know whether a clustering is any good? Two families of metrics:
- External metrics compare the clusters with true labels, when you happen to have some: our hidden vehicles, or a small hand-labelled sample.
- Internal metrics use only the data and the clusters, like the silhouette from Episode 43.
The obvious external metric is accuracy. Fit the same GMM twice with two random states:
import numpy as np, pandas as pd
r = np.random.default_rng(7) # 1,000 trips, vehicle NOT recorded (made up)
km = np.r_[r.normal(2.2, .7, 400), r.normal(4.5, 1.6, 600)].clip(.3) # 400 bicycle trips, 600 scooter trips
minutes = np.r_[5 + 5.5 * km[:400], 7 + 2.0 * km[400:]] + r.normal(0, 1.5, 1000)
X = np.c_[km, minutes]; vehicle = np.repeat(["bicycle", "scooter"], [400, 600]) # the truth, hidden from the model
from sklearn.mixture import GaussianMixture; from sklearn.cluster import KMeans
from sklearn.metrics import accuracy_score, adjusted_rand_score, davies_bouldin_score, silhouette_score
y = (vehicle == "scooter").astype(int) # 0 = bicycle, 1 = scooter
a = GaussianMixture(2, random_state=0).fit_predict(X)
b = GaussianMixture(2, random_state=1).fit_predict(X) # same model, different start
print("same clusters?", (a == 1 - b).all(), " accuracy a:", accuracy_score(y, a), " b:", accuracy_score(y, b))
print("ARI a:", round(adjusted_rand_score(y, a), 3), " b:", round(adjusted_rand_score(y, b), 3))
kml = KMeans(2, n_init=10, random_state=0).fit_predict(X)
rnd = np.random.default_rng(0).integers(0, 2, 1000) # coin-flip clusters
print("ARI k-means:", round(adjusted_rand_score(y, kml), 3), " coin flips:", round(adjusted_rand_score(y, rnd), 3))
for name, lab in [("GMM", a), ("k-means", kml)]: # internal scores: no truth needed
print(f"{name:8} Davies-Bouldin {davies_bouldin_score(X, lab):.2f} silhouette {silhouette_score(X, lab):.2f}")
Output:
same clusters? True accuracy a: 0.974 b: 0.026
ARI a: 0.898 b: 0.898
ARI k-means: 0.002 coin flips: -0.001
GMM Davies-Bouldin 2.52 silhouette 0.18
k-means Davies-Bouldin 0.79 silhouette 0.46
- Same clusters? True, just numbered the other way round (
a == 1 - beverywhere). - Yet accuracy is 0.974 for one and 0.026 for the other. Accuracy compares the numbers, and cluster numbers mean nothing. This is label switching: the same clustering with the labels swapped.
- Adjusted Rand index: 0.898 for both. k-means gets 0.002, coin-flip clusters −0.001 (about zero).
- Internal scores: Davies-Bouldin (lower is better) 2.52 for the GMM vs 0.79 for k-means; silhouette (higher is better) 0.18 vs 0.46. Both say k-means is better. They are wrong here.
Rand index and adjusted Rand index
- The Rand index looks at pairs of rows, not label numbers. For every pair of trips: did both clusterings put them together, or both keep them apart? The Rand index is the fraction of pairs where they agree. Renaming clusters changes nothing.
- Its weakness: random labels already score about 0.5, because many pairs agree by luck.
- Adjusted means corrected for chance: random labels score about 0, a perfect match 1 (it can dip slightly below 0 for worse-than-random). That is the adjusted Rand index (ARI),
adjusted_rand_score(truth, labels).
The plain and the adjusted index on our trips:
import numpy as np, pandas as pd
r = np.random.default_rng(7) # 1,000 trips, vehicle NOT recorded (made up)
km = np.r_[r.normal(2.2, .7, 400), r.normal(4.5, 1.6, 600)].clip(.3) # 400 bicycle trips, 600 scooter trips
minutes = np.r_[5 + 5.5 * km[:400], 7 + 2.0 * km[400:]] + r.normal(0, 1.5, 1000)
X = np.c_[km, minutes]; vehicle = np.repeat(["bicycle", "scooter"], [400, 600]) # the truth, hidden from the model
from sklearn.metrics import rand_score, adjusted_rand_score
y = (vehicle == "scooter").astype(int); rnd = np.random.default_rng(0).integers(0, 2, 1000)
for name, lab in [("perfect", y), ("renamed", 1 - y), ("coin flips", rnd), ("all one cluster", np.zeros(1000, int))]:
print(f"{name:15} Rand {rand_score(y, lab):.3f} ARI {adjusted_rand_score(y, lab):.3f}")
Output:
perfect Rand 1.000 ARI 1.000
renamed Rand 1.000 ARI 1.000
coin flips Rand 0.500 ARI -0.001
all one cluster Rand 0.520 ARI 0.000
Renaming the clusters keeps both at 1.000. Coin flips get a Rand index of 0.500 and "everyone in one cluster" 0.520, which look half good; the ARI correctly says about 0 for both.
Davies-Bouldin index
An internal score. For each cluster i, find its most similar neighbour j, where similarity = (spread of i + spread of j) / distance between their centres (spread = average distance of the cluster's rows to its centre). Average that worst value over all clusters. Lower is better: tight clusters, far apart. davies_bouldin_score(X, labels).
Silhouette recap
From Episode 43: for each row, a = mean distance to its own cluster, b = mean distance to the nearest other cluster, s = (b − a) / max(a, b); the score is the mean over rows. Higher is better.
Why the internal scores were fooled
Riya's ovals are long, and their centres are close (2.1 vs 4.4 km). Both internal scores reward round, tight, far-apart blobs, so they dislike the true ovals and like k-means' round chunks. Internal metrics have their own idea of a good cluster. Use them to compare similar models, and always check that the clusters make sense.
Two errors you will meet
import numpy as np, pandas as pd
r = np.random.default_rng(7) # 1,000 trips, vehicle NOT recorded (made up)
km = np.r_[r.normal(2.2, .7, 400), r.normal(4.5, 1.6, 600)].clip(.3) # 400 bicycle trips, 600 scooter trips
minutes = np.r_[5 + 5.5 * km[:400], 7 + 2.0 * km[400:]] + r.normal(0, 1.5, 1000)
X = np.c_[km, minutes]; vehicle = np.repeat(["bicycle", "scooter"], [400, 600]) # the truth, hidden from the model
from sklearn.mixture import GaussianMixture; import textwrap
gm = GaussianMixture(2, random_state=0)
try: gm.predict_proba([[3, 17]]) # MISTAKE: ask before fit
except Exception as e: print(*textwrap.wrap(type(e).__name__ + ": " + str(e), 62), sep="\n") # wrap long lines
try: gm.fit(km) # MISTAKE: one column as a 1-D array
except ValueError as e: m = str(e).split("\n"); print("ValueError:", m[0]); print(m[-1][:51], "...")
gm.fit(km.reshape(-1, 1)) # fix: a column, shape (1000, 1)
print("works on km alone:", gm.means_.ravel().round(2), " shape was", km.reshape(-1, 1).shape)
Output:
NotFittedError: This GaussianMixture instance is not fitted
yet. Call 'fit' with appropriate arguments before using this
estimator.
ValueError: Expected 2D array, got 1D array instead:
Reshape your data either using array.reshape(-1, 1) ...
works on km alone: [4.97 2.32] shape was (1000, 1)
NotFittedError: This GaussianMixture instance is not fitted yet. Call 'fit' with appropriate arguments before using this estimator.You asked for probabilities before the model had learned anything. Callfitfirst. (NotFittedErroris scikit-learn's error class for "used before fit".textwrap.wrap(text, 62)only splits the long message into lines of at most 62 characters so it fits the screen.)ValueError: Expected 2D array, got 1D array instead:followed by the hintReshape your data either using array.reshape(-1, 1) ...(the program prints only its first 51 characters). scikit-learn always wants a table: rows × columns.kmhas shape (1000,), a flat list.km.reshape(-1, 1)makes it one column, shape (1000, 1):-1means "work out this size yourself".- After the fix, the 1-D model's means are 4.97 and 2.32 km (the same 1-D mixture as in the Gaussian mixtures section, where the weights came out 0.55 / 0.45).
Common mistakes
| Mistake | Exact message / symptom | Why | Fix |
|---|---|---|---|
| k-means on stretched, tilted groups | bicycles split 196 / 204 | Round blobs only, hard labels | GaussianMixture(covariance_type="full") |
Too simple covariance_type |
spherical: 471 of 1000 wrong |
Circles cannot tilt | full (if there are enough rows) |
| Picking components by likelihood | −3953.6, −3954.2, −3952.3, −3949.2 ... keeps creeping | No price for size | Lowest BIC |
| Accuracy for clusters | same clusters: 0.974 vs 0.026 | Label switching | adjusted_rand_score |
| Trusting internal scores blindly | Davies-Bouldin 0.79 / silhouette 0.46 prefer k-means | They favour round blobs | Check with ARI on a labelled sample, or by eye |
| One run of EM from a random start | 3 of 20 runs stuck near −4460 | Local optimum | n_init=10 |
| Predict before fit | NotFittedError: This GaussianMixture instance is not fitted yet. ... |
Nothing learned yet | fit first |
| One column as a flat array | ValueError: Expected 2D array, got 1D array instead: |
Needs rows × columns | .reshape(-1, 1) |
Mini project: Riya's fleet report
Choose the covariance type and the number of components by BIC, name the components by their minutes-per-km slope (covariance of km and minutes ÷ variance of km), estimate the bicycle share from the soft labels, list the borderline trips, and score new trips. score_samples gives each row's log-density under the whole mixture.
import numpy as np, pandas as pd
r = np.random.default_rng(7) # 1,000 trips, vehicle NOT recorded (made up)
km = np.r_[r.normal(2.2, .7, 400), r.normal(4.5, 1.6, 600)].clip(.3) # 400 bicycle trips, 600 scooter trips
minutes = np.r_[5 + 5.5 * km[:400], 7 + 2.0 * km[400:]] + r.normal(0, 1.5, 1000)
X = np.c_[km, minutes]; vehicle = np.repeat(["bicycle", "scooter"], [400, 600]) # the truth, hidden from the model
from sklearn.mixture import GaussianMixture; from sklearn.metrics import adjusted_rand_score
best = None # 1) choose shape and size by BIC
for ct in ["spherical", "diag", "tied", "full"]:
for n in range(1, 5):
gm = GaussianMixture(n, covariance_type=ct, n_init=3, random_state=0).fit(X)
if best is None or gm.bic(X) < best[0]: best = (gm.bic(X), ct, n, gm)
bic, ct, n, gm = best
print(f"chosen: {n} components, covariance_type={ct}, BIC {bic:.0f}")
slope = [gm.covariances_[j][0, 1] / gm.covariances_[j][0, 0] for j in range(n)]
bike = int(np.argmax(slope)); print("minutes per extra km:", np.round(slope, 1), "-> bicycle = component", bike)
P = gm.predict_proba(X)[:, bike] # 3) soft fleet estimate
print(f"estimated bicycle share: {P.mean():.3f} (expected trips {P.sum():.0f}), hard count {(P > .5).sum()}")
print("trips to check by hand (0.4 < P < 0.6):", ((P > .4) & (P < .6)).sum())
print("ARI against the hidden truth:", round(adjusted_rand_score(vehicle, gm.predict(X)), 3))
new = np.array([[3, 17], [1.5, 14], [9, 26], [2, 60]]) # 4) new trips; the last is strange
for t, pb, ll in zip(new, gm.predict_proba(new)[:, bike], gm.score_samples(new)):
print(f"{t[0]:>4} km {t[1]:>3.0f} min: P(bicycle) {pb:.2f} log-density {ll:7.1f}")
Output:
chosen: 2 components, covariance_type=full, BIC 7983
minutes per extra km: [2.1 5.4] -> bicycle = component 1
estimated bicycle share: 0.402 (expected trips 402), hard count 412
trips to check by hand (0.4 < P < 0.6): 16
ARI against the hidden truth: 0.898
3.0 km 17 min: P(bicycle) 0.49 log-density -6.8
1.5 km 14 min: P(bicycle) 1.00 log-density -3.4
9.0 km 26 min: P(bicycle) 0.00 log-density -7.8
2.0 km 60 min: P(bicycle) 1.00 log-density -382.9
- BIC chose 2 full components (BIC 7983) out of 16 candidates.
- The slopes 2.1 and 5.4 minutes per km identify the bicycle component without looking at the truth.
- Soft fleet estimate: 0.402 (402 expected bicycle trips; the truth is 400). Counting hard labels gives 412: the soft average uses the uncertainty instead of rounding every trip.
- 16 trips have P(bicycle) between 0.4 and 0.6: those are the ones worth checking by hand.
- ARI against the hidden truth: 0.898.
- New trips: 2 km in 60 minutes has log-density −382.9, far below the others (−3.4 to −7.8): no component explains it. That is the idea of the next episode.
Practice
1. Run the scratch EM from five different starting seeds (100 rounds each). Do they agree?
Solution
import numpy as np, pandas as pd
r = np.random.default_rng(7) # 1,000 trips, vehicle NOT recorded (made up)
km = np.r_[r.normal(2.2, .7, 400), r.normal(4.5, 1.6, 600)].clip(.3) # 400 bicycle trips, 600 scooter trips
minutes = np.r_[5 + 5.5 * km[:400], 7 + 2.0 * km[400:]] + r.normal(0, 1.5, 1000)
X = np.c_[km, minutes]; vehicle = np.repeat(["bicycle", "scooter"], [400, 600]) # the truth, hidden from the model
from scipy.stats import multivariate_normal as mvn
for seed in [1, 2, 3, 4, 5]: # scratch EM, different starting trips
k = 2; w = np.full(k, 1 / k)
mu = X[np.random.default_rng(seed).choice(len(X), k, replace=False)]
cov = np.array([np.cov(X.T)] * k)
for it in range(100):
dens = np.column_stack([w[j] * mvn.pdf(X, mu[j], cov[j]) for j in range(k)])
loglik = np.log(dens.sum(axis=1)).sum(); resp = dens / dens.sum(axis=1, keepdims=True)
n = resp.sum(axis=0); w = n / len(X); mu = resp.T @ X / n[:, None]
cov = np.array([(resp[:, j, None] * (X - mu[j])).T @ (X - mu[j]) / n[j] for j in range(k)])
print(f"seed {seed}: log-likelihood {loglik:8.1f} weights {np.sort(w).round(3)} start trips {np.round(X[np.random.default_rng(seed).choice(len(X), k, replace=False)], 1).tolist()}")
Output:
seed 1: log-likelihood -3953.6 weights [0.402 0.598] start trips [[5.4, 16.0], [4.3, 18.2]]
seed 2: log-likelihood -3953.6 weights [0.402 0.598] start trips [[2.8, 20.8], [2.9, 13.8]]
seed 3: log-likelihood -3953.6 weights [0.402 0.598] start trips [[1.4, 12.5], [2.2, 10.2]]
seed 4: log-likelihood -3953.6 weights [0.402 0.598] start trips [[6.3, 19.4], [5.1, 17.0]]
seed 5: log-likelihood -3953.6 weights [0.402 0.598] start trips [[4.6, 16.5], [2.9, 12.3]]
All five starts reach log-likelihood −3953.6 and weights 0.402 / 0.598, even from two very similar starting trips (seed 3). On this data the scratch EM, starting with the whole data's covariance, is robust; Practice 6 shows starts that do get stuck.
2. How many trips is the model unsure about (top probability below 0.6)? Where are they, and how many are wrong?
Solution
import numpy as np, pandas as pd
r = np.random.default_rng(7) # 1,000 trips, vehicle NOT recorded (made up)
km = np.r_[r.normal(2.2, .7, 400), r.normal(4.5, 1.6, 600)].clip(.3) # 400 bicycle trips, 600 scooter trips
minutes = np.r_[5 + 5.5 * km[:400], 7 + 2.0 * km[400:]] + r.normal(0, 1.5, 1000)
X = np.c_[km, minutes]; vehicle = np.repeat(["bicycle", "scooter"], [400, 600]) # the truth, hidden from the model
from sklearn.mixture import GaussianMixture
gm = GaussianMixture(2, random_state=0).fit(X)
p = gm.predict_proba(X).max(axis=1) # how sure is the model about each trip?
unsure = (p < 0.6) # the top probability is between 0.5 and 0.6
print("unsure trips (top probability < 0.6):", unsure.sum(), " of", len(X))
print("their km range:", X[unsure, 0].min().round(1), "to", X[unsure, 0].max().round(1))
print("sure trips (top probability > 0.99):", (p > 0.99).sum())
hard = gm.predict(X); bike = np.bincount(hard[vehicle == "bicycle"]).argmax() # the component most bicycles got
wrong = (hard == bike) != (vehicle == "bicycle")
print("wrong among unsure:", wrong[unsure].sum(), " wrong among all:", wrong.sum())
Output:
unsure trips (top probability < 0.6): 15 of 1000
their km range: 0.3 to 2.1
sure trips (top probability > 0.99): 847
wrong among unsure: 4 wrong among all: 26
15 unsure trips, all short (0.3 to 2.1 km), in the overlap at the bottom left; 4 of the 26 mistakes are among them. 847 trips are above 0.99. The soft labels tell Riya exactly where to doubt.
3. Add a third vehicle (200 made-up walks, about 15 minutes per km). Does BIC find 3 components?
Solution
import numpy as np, pandas as pd
r = np.random.default_rng(7) # 1,000 trips, vehicle NOT recorded (made up)
km = np.r_[r.normal(2.2, .7, 400), r.normal(4.5, 1.6, 600)].clip(.3) # 400 bicycle trips, 600 scooter trips
minutes = np.r_[5 + 5.5 * km[:400], 7 + 2.0 * km[400:]] + r.normal(0, 1.5, 1000)
X = np.c_[km, minutes]; vehicle = np.repeat(["bicycle", "scooter"], [400, 600]) # the truth, hidden from the model
from sklearn.mixture import GaussianMixture # add a third vehicle: walking (made up)
r2 = np.random.default_rng(11); wk = r2.normal(1.2, .3, 200).clip(.2) # 200 short walks
X3 = np.r_[X, np.c_[wk, 15 * wk + r2.normal(0, 1.5, 200)]] # about 15 minutes per km on foot
for n in range(1, 6):
gm = GaussianMixture(n, n_init=5, random_state=0).fit(X3) # 5 starts each, keep the best
print(f"{n} components: BIC {gm.bic(X3):6.0f} weights {np.sort(gm.weights_).round(2)}")
Output:
1 components: BIC 11317 weights [1.]
2 components: BIC 11209 weights [0.45 0.55]
3 components: BIC 9820 weights [0.17 0.33 0.5 ]
4 components: BIC 10483 weights [0.07 0.13 0.36 0.44]
5 components: BIC 9896 weights [0.08 0.15 0.17 0.28 0.32]
BIC is lowest at 3 (9820), and the weights 0.17 / 0.33 / 0.50 match the truth 200 / 400 / 600 of 1,200. The jump at 4 components (10483) is a fit that stopped on a poor local optimum even with 5 starts; when BIC looks bumpy, use more n_init.
4. What adjusted Rand index does DBSCAN (Episode 44) get on the scaled trips?
Solution
import numpy as np, pandas as pd
r = np.random.default_rng(7) # 1,000 trips, vehicle NOT recorded (made up)
km = np.r_[r.normal(2.2, .7, 400), r.normal(4.5, 1.6, 600)].clip(.3) # 400 bicycle trips, 600 scooter trips
minutes = np.r_[5 + 5.5 * km[:400], 7 + 2.0 * km[400:]] + r.normal(0, 1.5, 1000)
X = np.c_[km, minutes]; vehicle = np.repeat(["bicycle", "scooter"], [400, 600]) # the truth, hidden from the model
from sklearn.cluster import DBSCAN; from sklearn.preprocessing import StandardScaler
from sklearn.metrics import adjusted_rand_score
y = (vehicle == "scooter").astype(int); Xs = StandardScaler().fit_transform(X)
for eps in [0.1, 0.2, 0.3, 0.5]:
lab = DBSCAN(eps=eps, min_samples=10).fit_predict(Xs) # -1 = noise
print(f"eps {eps}: clusters {len(set(lab) - {-1})} noise {(lab == -1).sum():3} ARI {adjusted_rand_score(y, lab):.3f}")
Output:
eps 0.1: clusters 18 noise 668 ARI 0.110
eps 0.2: clusters 2 noise 125 ARI 0.593
eps 0.3: clusters 2 noise 23 ARI -0.011
eps 0.5: clusters 1 noise 2 ARI 0.000
The best here is eps 0.2: 2 clusters and 125 noise trips, ARI 0.593, still below the GMM's 0.898. DBSCAN joins dense regions, and the two ovals touch in their densest part (short trips), so a slightly larger eps (0.3) merges them (ARI −0.011). Noise trips (label −1) count as one more "cluster" in the ARI.
5. Count p for each covariance type and recompute AIC and BIC by hand.
Solution
import numpy as np, pandas as pd
r = np.random.default_rng(7) # 1,000 trips, vehicle NOT recorded (made up)
km = np.r_[r.normal(2.2, .7, 400), r.normal(4.5, 1.6, 600)].clip(.3) # 400 bicycle trips, 600 scooter trips
minutes = np.r_[5 + 5.5 * km[:400], 7 + 2.0 * km[400:]] + r.normal(0, 1.5, 1000)
X = np.c_[km, minutes]; vehicle = np.repeat(["bicycle", "scooter"], [400, 600]) # the truth, hidden from the model
from sklearn.mixture import GaussianMixture
n = len(X)
for ct in ["spherical", "diag", "tied", "full"]: # count the learned numbers p
gm = GaussianMixture(2, covariance_type=ct, random_state=0).fit(X)
p = gm._n_parameters(); logL = gm.score(X) * n
print(f"{ct:9} p={p:2} AIC {gm.aic(X):7.1f} = {2*p - 2*logL:7.1f} BIC {gm.bic(X):7.1f} = {p*np.log(n) - 2*logL:7.1f}")
print("ln(1000) =", round(np.log(1000), 3))
Output:
spherical p= 7 AIC 9361.3 = 9361.3 BIC 9395.6 = 9395.6
diag p= 9 AIC 8996.0 = 8996.0 BIC 9040.1 = 9040.1
tied p= 8 AIC 8979.9 = 8979.9 BIC 9019.1 = 9019.1
full p=11 AIC 7929.1 = 7929.1 BIC 7983.1 = 7983.1
ln(1000) = 6.908
spherical 7 = 1 + 4 + 2, diag 9 = 1 + 4 + 4, tied 8 = 1 + 4 + 3, full 11 = 1 + 4 + 6. The hand formulas match scikit-learn exactly. (_n_parameters starts with an underscore: a private helper, fine for checking, not for production code.) BIC also picks full here: 7983 is far below the rest, because the better fit is worth much more than the extra parameters.
6. Start EM from random trips 20 times. How often does it get stuck, and does n_init fix it?
Solution
import numpy as np, pandas as pd
r = np.random.default_rng(7) # 1,000 trips, vehicle NOT recorded (made up)
km = np.r_[r.normal(2.2, .7, 400), r.normal(4.5, 1.6, 600)].clip(.3) # 400 bicycle trips, 600 scooter trips
minutes = np.r_[5 + 5.5 * km[:400], 7 + 2.0 * km[400:]] + r.normal(0, 1.5, 1000)
X = np.c_[km, minutes]; vehicle = np.repeat(["bicycle", "scooter"], [400, 600]) # the truth, hidden from the model
from sklearn.mixture import GaussianMixture # local optima and n_init
lls = [GaussianMixture(2, init_params="random_from_data", random_state=s).fit(X).score(X) * len(X) for s in range(20)]
print("20 single starts from random trips: best", round(max(lls), 1), " worst", round(min(lls), 1),
" stuck (below -4000):", sum(l < -4000 for l in lls))
for s in range(3): # n_init=10: keep the best of 10 starts
gm = GaussianMixture(2, init_params="random_from_data", n_init=10, random_state=s).fit(X)
print(f"n_init=10, random_state={s}: log-likelihood {gm.score(X) * len(X):.1f}")
Output:
20 single starts from random trips: best -3953.6 worst -4460.1 stuck (below -4000): 3
n_init=10, random_state=0: log-likelihood -3953.6
n_init=10, random_state=1: log-likelihood -3953.6
n_init=10, random_state=2: log-likelihood -3953.6
3 of 20 single starts stopped on a local optimum (as low as −4460.1). With n_init=10, three different random states all reached −3953.6.
Quick quiz
1. Which model does BIC choose? n = 1000 rows, ln(1000) ≈ 6.9. Model A: p = 11, log L = −3954. Model B: p = 17, log L = −3954. Options: A, B, a tie, can't tell.
Answer
A. Same log-likelihood, so the fit part is equal: −2 log L = 2 × 3954 = 7908 for both. A pays 11 × 6.9 ≈ 76, B pays 17 × 6.9 ≈ 117. A has the lower BIC (about 7984 vs 8025). Same fit, fewer numbers: A wins.
2. Two clusterings of the same rows give accuracy 0.974 and 0.026 against the truth. Can they be the same clustering?
Answer
Yes: with two clusters, swapping the labels turns accuracy a into 1 − a. That is label switching (our two GMMs). Their ARI is identical (0.898).
3. How many covariance numbers does one full component have with 4 columns?
Answer
d(d + 1)/2 = 4 × 5 / 2 = 10 (4 variances + 6 covariances).
4. During EM, can the log-likelihood go down from one round to the next?
Answer
No. Each round never decreases it (our run: −4828.4 → −4210.7 → −3956.4 → −3953.6). It can, however, stop at a local optimum.
5. A row's responsibilities are 0.2, 0.5 and something. What is the something?
Answer
0.3: a row's responsibilities always add up to 1.
Interview questions
- Hard vs soft clustering? Hard gives each row one cluster; soft gives a probability per cluster that sums to 1 per row. A GMM gives soft labels (
predict_proba) and hard ones (predict). - What is a Gaussian mixture model? A density made of k weighted Gaussian components, each with a weight, a mean and a covariance; the weights sum to 1.
- Explain EM. Start with a guess; E-step: responsibilities from Bayes' theorem (weight × density, normalised per row); M-step: refit weights, means and covariances with responsibility-weighted averages; repeat. The likelihood never decreases (Dempster, Laird and Rubin, 1977).
- How is k-means related to a GMM? k-means is like EM with hard assignments and round, equal-sized clusters: assign, then update. A GMM shares rows softly and lets each component have its own shape and weight.
- Does EM find the global optimum? No, it can stop at a local optimum; use several starts (
n_init) and a good initialisation (k-means, the scikit-learn default). - Covariance types?
spherical(circles),diag(axis-aligned ovals),tied(one shared shape),full(own tilted oval each, default). Fewer parameters = more stable with few rows;fullneeds d(d + 1)/2 per component. - How do you choose the number of components? Not by likelihood (it keeps creeping up); use the lowest BIC (or AIC). BIC = p ln(n) − 2 log L charges more per parameter than AIC = 2p − 2 log L.
- Count the parameters of 2 full components in 2-D. 1 free weight + 4 mean values + 6 covariance values = 11.
- Why not use accuracy to evaluate clusters? Cluster numbers are arbitrary (label switching): the same clusters scored 0.974 and 0.026. Use a permutation-free external metric such as the adjusted Rand index.
- What does "adjusted" mean in ARI? Corrected for chance: random labels score about 0 (the plain Rand index gives them about 0.5), a perfect match 1.
- External vs internal metrics? External needs true labels (ARI); internal uses only data and clusters (silhouette, Davies-Bouldin). Internal ones favour compact round blobs and can prefer a worse clustering, as here (k-means DB 0.79 vs GMM 2.52).
- How would you flag strange rows with a GMM? Rows with a very low density under the whole mixture (
score_samples), like 2 km in 60 minutes at −382.9. That leads to anomaly detection.
Glossary
| Term | Meaning (plain words + example) |
|---|---|
| Clustering | Grouping similar rows without labels: Riya's trips by unknown vehicle |
| Cluster | One group found by clustering |
| Unsupervised learning | Learning from rows with no answer column |
| Label | The answer column; here the hidden vehicle |
| Hard clustering | Each row gets exactly one cluster: trip 17 → cluster 1 |
| Soft clustering | Each row gets a probability per cluster: bicycle 0.70, scooter 0.30 |
| k-means | Assign each row to the nearest centroid, move centroids to the mean (Episode 43); round blobs only |
| Centroid | The centre (mean) of a k-means cluster |
| Gaussian (normal) distribution | The bell curve, set by a mean and a standard deviation: bicycle km around 2.2 ± 0.7 |
| Mean | The average; the centre of a bell or oval: (2.1 km, 16.7 min) |
| Standard deviation | Typical distance from the mean: the bell's width |
| Variance | Standard deviation squared: spread of one column |
| Covariance | Whether two columns rise together; tilts the oval |
| Covariance matrix | The table of variances and covariances of all columns: 2 × 2 for (km, minutes) |
| Density (probability density) | Height of the distribution at a point: how crowded the data is there |
| Gaussian mixture | A distribution made by adding weighted Gaussians: two bells → two humps |
| Gaussian mixture model (GMM) | A model saying the data comes from k Gaussian ovals |
| Mixture component | One of the Gaussians in the mixture: the bicycle oval |
| Mixture weight | A component's share of the rows; the weights sum to 1: 0.402 / 0.598 |
| Prior | How common a component is before looking at the row (its weight) |
| Bayes' theorem | Posterior ∝ prior × density: P(component | trip) = weight × density / total |
| Soft label (posterior probability) | P(component | row): 0.49 / 0.51 for 3 km in 17 min |
| Likelihood | How probable (dense) the data is under the model; bigger = better fit |
| Log-likelihood (log L) | Sum of log densities over rows; closer to 0 is better: −3953.6 beats −4828.4 |
| Maximum likelihood | Choosing the parameters that make the data most probable |
| Expectation-maximisation (EM) | Alternate E-step and M-step until convergence (Dempster, Laird, Rubin, 1977) |
| E-step | Compute every row's responsibilities from the current ovals |
| M-step | Refit weights, means and covariances using responsibilities as row weights |
| Responsibility | How much component j owns row i; each row's responsibilities sum to 1 |
| Effective number of rows | A component's total responsibility: about 402 for the bicycles |
| Incomplete data | Data with a missing column; for EM here, the vehicle |
| Convergence | EM stops changing: log L stays at −3953.6 from round 15 |
tol, max_iter |
Stop when the improvement is below tol, or after max_iter rounds |
n_iter_ |
How many EM rounds the fit took: 23 |
| Local optimum | A solution no small change improves, but not the best: −4460.1 vs −3953.6 |
n_init |
Number of starts; the best is kept: n_init=10 |
init_params |
How EM starts: "kmeans" (default), "random_from_data", ... |
GaussianMixture |
scikit-learn's GMM class |
n_components |
Number of components (k) |
weights_, means_, covariances_ |
The fitted weights, means and covariances |
predict |
Hard labels: the most probable component per row |
predict_proba |
Soft labels: one probability per component per row |
score |
Average log-likelihood per row (× n gives log L) |
score_samples |
Log-density of each row under the whole mixture: −382.9 for 2 km in 60 min |
covariance_type |
How free each component's shape is: spherical, diag, tied, full |
| Spherical | Every component a circle with one spread: 471 wrong |
| Diag (diagonal) | Ovals along the axes, no tilt: 355 wrong |
| Tied | All components share one oval shape: 445 wrong |
| Full | Each component its own tilted oval (default): 26 wrong |
| d(d + 1)/2 | Covariance numbers in one full component with d columns: 3 for d = 2, 5,050 for d = 100 |
| Parameter (p) | A number the model learns; 11 for 2 full components in 2-D |
| Free parameter | One that is not fixed by the others: only 1 of the 2 weights |
| AIC (Akaike information criterion) | 2p − 2 log L; lower is better: 7929 at 2 components |
| BIC (Bayesian information criterion) | p ln(n) − 2 log L; lower is better, punishes size harder: 7983 at 2 |
| ln (natural log) | Log base e: ln(1000) = 6.908 |
| External metric | Compares clusters with true labels: ARI |
| Internal metric | Uses only data and clusters: silhouette, Davies-Bouldin |
| Accuracy | Fraction of rows whose label equals the truth; meaningless for cluster numbers |
| Label switching | The same clusters with swapped numbers: accuracy 0.974 vs 0.026 |
| Rand index | Fraction of row pairs both clusterings treat alike (together in both, or apart in both) |
| Adjusted Rand index (ARI) | Rand index corrected for chance: random ≈ 0, perfect = 1; GMM 0.898, k-means 0.002 |
| Davies-Bouldin index | Average over clusters of the worst (spread i + spread j) / centre distance; lower is better |
| Silhouette score | Mean of (b − a) / max(a, b) over rows; higher is better (Episode 43) |
| DBSCAN | Density-based clustering with noise (Episode 44): ARI 0.593 at best here |
StandardScaler |
Rescales columns to mean 0, standard deviation 1 |
pd.crosstab |
Count table of truth against cluster |
multivariate_normal.pdf |
SciPy: Gaussian density of rows for a given mean and covariance |
@ (matrix multiplication) |
resp.T @ X: responsibility-weighted column sums |
reshape(-1, 1) |
Turn a flat array into one column: (1000,) → (1000, 1) |
NotFittedError |
Error when a model is used before fit |
ValueError |
Python error for a bad value: Expected 2D array, got 1D array instead: |
| Anomaly | A strange row that no component explains well (next episode) |
Summary
- k-means assumes round blobs and gives hard labels; on Riya's tilted ovals it split the bicycles 196 / 204.
- A Gaussian mixture model explains the data as weighted Gaussian components (weight, mean, covariance) and gives soft labels via Bayes' theorem: 3 km in 17 minutes is 0.49 / 0.51.
- EM alternates the E-step (responsibilities) and M-step (responsibility-weighted refits); the log-likelihood never decreases (−4828.4 → −3953.6) and recovered the hidden 0.4 / 0.6 split with 26 mistakes.
- EM can stop at a local optimum; use
n_init. covariance_typedecides which shapes are possible: onlyfull(26 wrong) could fit the two different tilts.- Choose the number of components with BIC (or AIC), not likelihood: AIC = 2p − 2 log L, BIC = p ln(n) − 2 log L, p = 11 for 2 full components in 2-D.
- Judge clusters with the adjusted Rand index (0.898), not accuracy (0.974 vs 0.026 for the same clusters); internal scores (Davies-Bouldin, silhouette) favour round blobs and can mislead.
Next episode: Anomaly detection: finding the strange rows (fraud, faults and glitches) with isolation forest, local outlier factor and one-class SVM.