Skip to article frontmatterSkip to article content
Site not loading correctly?

This may be due to an incorrect BASE_URL configuration. See the MyST Documentation for reference.

Three Families of Clustering Algorithms

English · فارسی

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 W(C)W(C) and the between-cluster scatter B(C)B(C) and prove T=W+BT = W + B;

  • state why minimising WW is the same as maximising BB;

  • explain why every practical method is a greedy descent that can stop in a local minimum.

1. Three families

familywhat it assumeswhat is estimatedexamples
combinatorialnothing beyond the dissimilaritiesthe assignment C(i)C(i) of every observationK-means, K-medoids, hierarchical merging
mixture modellingthe data are an i.i.d. sample from a mixture of densitiesthe parameters of the component densitiesGaussian mixtures, model-based clustering
mode seekingthe density is unknown but has distinct modesthe modes, and then the points nearest eachPRIM (“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 i∈{1,…,N}i \in \{1,\dots,N\} and each cluster by k∈{1,…,K}k \in \{1,\dots,K\} with K<NK < N given in advance. A clustering is an encoder

k=C(i),k = C(i),

a many-to-one map that sends every observation to one and only one cluster. The parameters of the problem are the NN 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,

W(C)=12∑k=1K∑C(i)=k∑C(i′)=kd(xi,xi′),(14.28)W(C) = \frac{1}{2} \sum_{k=1}^{K} \sum_{C(i)=k} \sum_{C(i')=k} d(x_i, x_{i'}), \qquad \text{(14.28)}

the “within-cluster point scatter”: small when points assigned together are close. Splitting the total scatter into a within and a between part gives

T=12∑i=1N∑i′=1Ndii′=W(C)+B(C),B(C)=12∑k=1K∑C(i)=k∑C(i′)≠kdii′.(14.29)T = \frac{1}{2}\sum_{i=1}^{N}\sum_{i'=1}^{N} d_{ii'} = W(C) + B(C), \qquad B(C) = \frac{1}{2} \sum_{k=1}^{K} \sum_{C(i)=k} \sum_{C(i') \ne k} d_{ii'} . \qquad \text{(14.29)}

TT depends on the data only, so minimising WW is exactly maximising BB. 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.

W(C)      =  15566.41
B(C)      =  33990.16
W(C) + B  =  49556.56
T         =  49556.56

A detail worth knowing: WW 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:

12∑i∈Ck∑i′∈Ck∥xi−xi′∥2=Nk∑i∈Ck∥xi−xˉk∥2.(14.31)\frac{1}{2}\sum_{i \in C_k}\sum_{i' \in C_k} \lVert x_i - x_{i'} \rVert^2 = N_k \sum_{i \in C_k} \lVert x_i - \bar{x}_k \rVert^2 . \qquad \text{(14.31)}

The left side counts every pair once; the right side multiplies the cluster’s own sum of squares by its size NkN_k. So WW is not the number KMeans.inertia_ reports - that is ∑k∑i∈Ck∥xi−xˉk∥2\sum_k \sum_{i \in C_k}\lVert x_i - \bar x_k\rVert^2, without the NkN_k - 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 N2N^2 sum into an NN sum. Keep the factor in mind when you compare numbers from different sources.

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 NN labelled observations into KK non-empty clusters is the Stirling number of the second kind,

S(N,K)=1K!∑k=1K(−1)K−k(Kk)kN.(14.30)S(N,K) = \frac{1}{K!}\sum_{k=1}^{K}(-1)^{K-k}\binom{K}{k}k^{N} . \qquad \text{(14.30)}

For N=10N = 10, K=4K = 4 this is 34 10534\,105, which a laptop can enumerate. For N=19N = 19 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:

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 WW. 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 WW”, 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.

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 K=3K = 3, 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 NN distance computations instead of N2N^2. 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-Clustering compares the two on a problem small enough that the global optimum can be computed.

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 W(C)W(C) of (14.28).

  • T=W+BT = W + B with TT fixed, so minimising WW and maximising BB are the same problem.

  • The exact solution costs S(N,K)S(N,K) evaluations, which is 1010 already at N=19N = 19, K=4K = 4.

  • Practical methods are greedy descents that stop at a local minimum, and the starting point decides which one.

Exercises

  1. Prove T=W+BT = W + B from the definitions, and check it for K=1K = 1 and K=NK = N.

  2. Verify (14.31) for a cluster of three points by hand, then with two lines of numpy.

  3. Show that WW and the unweighted sum of squares have the same value when all clusters have the same size. When do they rank two partitions differently?

  4. Compute S(N,2)=2N−1−1S(N,2) = 2^{N-1} - 1 from (14.30) and compare with Exhaustive-Clustering.

  5. Modify greedy to accept the first improving move it finds instead of the best one. Do the runs take fewer steps? Do they end lower or higher?

  6. Give an example of two data sets with the same WW 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.

References
  1. 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