Three Families of Clustering Algorithms
Three Families of Clustering Algorithms¶

Computer Science Dept, Ferdowsi University of Mashhad
Where this page sits¶
Sections 14.3.4 and 14.3.5 of Hastie et al. (2009) (pp. 507-509) are the bridge between the dissimilarity matrix and the algorithms. They do two things: they sort clustering methods into three families according to what each method assumes about the data, and then they write the combinatorial family down as an explicit optimisation problem, which is the formulation every method on the following pages is a special case of.
The optimisation has an exact solution - enumerate all partitions - which is uselessly expensive. What is left is descent, and descent explains both the strength and the weakness of K-means.
What you should be able to do at the end¶
say which of the three families a given algorithm belongs to, and what it therefore assumes;
write the within-cluster scatter and the between-cluster scatter and prove ;
state why minimising is the same as maximising ;
explain why every practical method is a greedy descent that can stop in a local minimum.
1. Three families¶
| family | what it assumes | what is estimated | examples |
|---|---|---|---|
| combinatorial | nothing beyond the dissimilarities | the assignment of every observation | K-means, K-medoids, hierarchical merging |
| mixture modelling | the data are an i.i.d. sample from a mixture of densities | the parameters of the component densities | Gaussian mixtures, model-based clustering |
| mode seeking | the density is unknown but has distinct modes | the modes, and then the points nearest each | PRIM (“bump hunting”), mean-shift, DBSCAN |
The division is about assumptions, not about quality. A combinatorial method never asks where the data came from; a mixture model states a probability model and estimates it by maximum likelihood; a mode seeker estimates the density nonparametrically and calls the neighbourhood of each mode a cluster. The first family is by far the largest in practice, and it is the one this course develops; mixture modelling is treated separately later in the course, and mode seeking appears only as the idea behind density-based methods.
2. The combinatorial formulation¶
Each observation is labelled by an integer and each cluster by with given in advance. A clustering is an encoder
a many-to-one map that sends every observation to one and only one cluster. The parameters of the problem are the labels themselves. There is no model to fit and nothing to differentiate; there is a finite set of candidate assignments and a loss that says how bad each one is.
The natural loss is the total dissimilarity within clusters,
the “within-cluster point scatter”: small when points assigned together are close. Splitting the total scatter into a within and a between part gives
depends on the data only, so minimising is exactly maximising . The two ways of saying it are useful in different places: “make the clusters tight” and “make the clusters far apart” are the same instruction.
The cell below checks the identity on a simulated data set and a random assignment.
import numpy as np
import matplotlib.pyplot as plt
rng = np.random.default_rng(0)
centres = [(-3.0, 0.0), (3.0, 0.0), (0.0, 4.0), (0.0, -4.0)] # four groups
X = np.vstack([rng.normal(c, 0.7, size=(15, 2)) for c in centres])
N = len(X)
dist = ((X[:, None, :] - X[None, :, :]) ** 2).sum(-1) # squared Euclidean
def W_of(C):
same = C[:, None] == C[None, :]
return 0.5 * dist[same].sum()
def B_of(C):
different = C[:, None] != C[None, :]
return 0.5 * dist[different].sum()
C_random = rng.integers(0, 3, size=N)
T = 0.5 * dist.sum()
print(f"W(C) = {W_of(C_random):9.2f}")
print(f"B(C) = {B_of(C_random):9.2f}")
print(f"W(C) + B = {W_of(C_random) + B_of(C_random):9.2f}")
print(f"T = {T:9.2f}")W(C) = 15566.41
B(C) = 33990.16
W(C) + B = 49556.56
T = 49556.56
A detail worth knowing: and the inertia of sklearn¶
With squared Euclidean distance, the pairwise form of (14.28) can be rewritten in terms of the cluster means, which is what makes K-means cheap:
The left side counts every pair once; the right side multiplies the cluster’s
own sum of squares by its size . So is not the number
KMeans.inertia_ reports - that is , without the - and the two need not have the same
minimiser. Both are within-cluster scatters, both decrease as clusters become
tighter, and the book uses (14.31) because it turns an sum into an sum.
Keep the factor in mind when you compare numbers from different sources.
def means_form(C):
total = 0.0
for k in np.unique(C):
members = X[C == k]
total += len(members) * ((members - members.mean(axis=0)) ** 2).sum()
return total
plain_ss = sum(((X[C_random == k] - X[C_random == k].mean(axis=0)) ** 2).sum()
for k in np.unique(C_random))
print("pairwise W(C) :", round(W_of(C_random), 2))
print("sum_k N_k * SS_k, form (14.31) :", round(means_form(C_random), 2))
print("sum_k SS_k, the sklearn inertia :", round(plain_ss, 2))pairwise W(C) : 15566.41
sum_k N_k * SS_k, form (14.31) : 15566.41
sum_k SS_k, the sklearn inertia : 759.35
3. Enumeration is exact and useless¶
The number of ways to split labelled observations into non-empty clusters is the Stirling number of the second kind,
For , this is , which a laptop can enumerate. For it is already 1010, and clustering problems start at hundreds of observations. The counting, the enumeration code, and the pruning that makes small instances tractable are worked out on the exhaustive clustering page; here only the consequence matters:
from math import comb, factorial
def stirling2(n, k):
return sum((-1) ** (k - j) * comb(k, j) * j ** n for j in range(k + 1)) // factorial(k)
for n, k in [(10, 4), (19, 4), (50, 3)]:
print(f"S({n:>2}, {k}) = {stirling2(n, k):.3e}")S(10, 4) = 3.410e+04
S(19, 4) = 1.126e+10
S(50, 3) = 1.196e+23
4. What is left: greedy descent¶
A practical method starts from an initial partition and changes labels as long as the change improves . When no single change improves it, the algorithm stops and returns the current assignment. That is a local minimum of a function defined on a finite but astronomically large set, and nothing about the procedure says the global one is near.
The code below does exactly this, with the crude move “move one point to another cluster if that lowers ”, evaluated on the full pairwise matrix. It is far too slow for real data - which is why K-means replaces it with the two-step move “means, then nearest mean” - but it shows the shape of every method in the chapter.
def wcss(X, C):
"""Sum over clusters of the sum of squared distances to the cluster mean."""
return sum(((X[C == k] - X[C == k].mean(axis=0)) ** 2).sum() for k in np.unique(C))
def wcss_moves(X, C, K):
cur = wcss(X, C)
for i in range(len(X)):
for k in range(K):
if k == C[i]:
continue
trial = C.copy()
trial[i] = k
if len(np.unique(trial)) < K: # keep K non-empty clusters
continue
if wcss(X, trial) < cur - 1e-9:
return i, k
return None
def greedy(X, K, seed, max_steps=400):
rng = np.random.default_rng(seed)
C = rng.integers(0, K, size=len(X))
history = [wcss(X, C)]
for _ in range(max_steps):
move = wcss_moves(X, C, K)
if move is None:
break
C[move[0]] = move[1]
history.append(wcss(X, C))
return C, history
for seed in range(5):
C, history = greedy(X, 3, seed)
print(f"start {seed}: steps {len(history) - 1:3d} "
f"W from {history[0]:8.2f} to {history[-1]:8.2f}")start 0: steps 36 W from 748.54 to 258.19
start 1: steps 47 W from 793.17 to 245.77
start 2: steps 49 W from 814.64 to 245.77
start 3: steps 33 W from 790.05 to 245.77
start 4: steps 54 W from 814.08 to 245.77
Every row decreases, and the rows do not all end at the same value: with four groups and , one start in five stopped on a clustering that no single move can improve and that is nevertheless worse than what the others found. That is a local minimum of a criterion with several basins, and it is the single most important practical fact about clustering: the starting point is part of the answer, which is why every implementation runs the algorithm from several starts and keeps the best - and why the number of starts belongs in what you report.
K-means is this scheme with squared Euclidean distance and a cleverer move: given
the current means, each point moves to its nearest mean, which needs only
distance computations instead of . The criterion it drives down is the same
within-cluster scatter of (14.31); the price of the cheaper move is that it
considers only a small subset of the possible relabellings, so it too can stop
early. Exhaustive
Summary¶
Clustering methods divide into combinatorial, mixture-modelling and mode-seeking families by what they assume; a combinatorial method assumes only the dissimilarities.
In the combinatorial family the parameters are the assignments themselves, and the loss is the within-cluster scatter of (14.28).
with fixed, so minimising and maximising are the same problem.
The exact solution costs evaluations, which is 1010 already at , .
Practical methods are greedy descents that stop at a local minimum, and the starting point decides which one.
Exercises¶
Prove from the definitions, and check it for and .
Verify (14.31) for a cluster of three points by hand, then with two lines of numpy.
Show that and the unweighted sum of squares have the same value when all clusters have the same size. When do they rank two partitions differently?
Compute from (14.30) and compare with Exhaustive
-Clustering. Modify
greedyto accept the first improving move it finds instead of the best one. Do the runs take fewer steps? Do they end lower or higher?Give an example of two data sets with the same for every partition but different answers to “which clustering is right”.
Sources¶
The three families, the encoder formulation, (14.28)-(14.31) and the sentence about convergence to local minima: §14.3.4-14.3.5 of Hastie et al. (2009), pp. 507-509.
The counting of partitions and the pruning that makes exhaustive search possible on small instances: Exhaustive
-Clustering. The identity behind (14.31) is Lemma 2 of Clustering-Part2.
- Hastie, T., Tibshirani, R., & Friedman, J. (2009). The Elements of Statistical Learning: Data Mining, Inference, and Prediction (2nd ed.). Springer. 10.1007/978-0-387-84858-7