Skip to content

Chapter 13: Clustering and K-means

Hand somebody a pile of a thousand photographs of animals with no captions and ask them to sort it into groups. They will do it, and they will not need to be told what the groups are — but the groups they produce depend entirely on what they decided “similar” meant. Sort by species and you get one arrangement. Sort by colour, or by whether the photograph was taken indoors, and you get others. None of them is wrong.

That is clustering, and it is why this unit feels different from everything before it. In Units 3 and 4 there was a right answer and the only question was how close you got. Here you supply the definition of similarity — the distance metric, the scaling, the number of clusters — and the algorithm then finds the best arrangement under your definition. The output is a hypothesis about the data, to be judged by whether it is useful, not by whether it is correct.

Which means the choices you make before running anything — what to standardise, which distance, how many clusters — are not preliminaries. They are the model.

Learning outcomes of Unit 5

  • Explain what clustering is trying to achieve — high similarity within clusters, low similarity between them — and place any method in the partitional / hierarchical / density and hard / soft schemes.
  • Compute Euclidean, Manhattan, Chebyshev, Minkowski and cosine measures, and choose between them from the shape of the data.
  • Run k-means by hand, prove to yourself that it must terminate, and name each of its five failure modes with its remedy.
  • Choose \(k\) with the elbow method and the silhouette coefficient, and say why WCSS alone can never do it.
  • Build an agglomerative clustering under single, complete and average linkage, read a dendrogram, and cut it to get a clustering.
  • Evaluate a clustering with internal and external measures, and explain why evaluation here is genuinely harder than in Units 3 and 4.

13.1 What a cluster is, and the families of methods

Definition: The clustering objective

Partition the data so that intra-cluster similarity is high — points in the same cluster are close together — and inter-cluster similarity is low — points in different clusters are far apart. Every algorithm below is a different way of making that trade concrete.

Partitional Hierarchical Density-based
One flat split into \(k\) groups A nested tree of clusterings Clusters are dense regions separated by sparse ones
\(k\) must be given in advance \(k\) is chosen afterwards, by cutting the tree \(k\) is never given; the algorithm decides
k-means, k-medoids Agglomerative (bottom-up) or divisive (top-down) DBSCAN, OPTICS
Fast: roughly \(O(\text{mkni})\) per run Slow: \(O(m^{3})\) naïvely, \(O(m^{2}\) log \(m\)) with care Finds arbitrary shapes — crescents, rings, spirals
Finds convex, similar-sized blobs Shape depends entirely on the linkage Labels sparse points as noise, which the others cannot
Restarting can give a different answer Deterministic — the same data gives the same tree Needs two parameters: \(\varepsilon\) and minPts

There is a second, independent axis. Hard clustering assigns each point to exactly one cluster. Soft or fuzzy clustering gives each point a degree of membership in every cluster. Gaussian mixture models are the standard example, and they are the natural choice when the groups genuinely overlap.

13.2 Distance and similarity

“Similar” has to become arithmetic before an algorithm can use it. Every measure below is a different answer to the same question, and the answer changes the clustering.

Definition: The Minkowski family

\(d_{p}(a, b) =\) ( \(\sum |a_{i} - b_{i}|^{p} )^{1/p}\)

\(p = 1\) is Manhattan (city-block), \(p = 2\) is Euclidean, and \(p \to \infty\) gives Chebyshev, the largest single coordinate difference.

Two points A and B and three distances between them: Euclidean (the straight line), Manhattan (the staircase along the axes) and Chebyshev (the single longest coordinate gap).
Figure 13.1. Two points A and B and three distances between them: Euclidean (the straight line), Manhattan (the staircase along the axes) and Chebyshev (the single longest coordinate gap).

Always \(d_{\infty } \le d_{2} \le d_{1}\) — a useful check on any hand calculation.

Measure Use it for Because
Euclidean the default; k-means is built on it ordinary geometry, and the mean minimises it
Manhattan grid-like movement; robustness to one wild coordinate no squaring, so one large difference does not dominate
Cosine text, and any high-dimensional sparse count data measures direction, not magnitude — a long and a short document about the same topic count as similar
Jaccard sets: baskets, tags, binary presence \(\|A\cap B\|/\|A\cup B\|\) — shared items over total items
Hamming strings and categorical vectors counts positions that differ
Mahalanobis correlated features with different spreads divides by the covariance, so it measures distance in standard deviations

Scale first, always

Squared distance sums over features, so a feature measured in rupees swamps one measured in years and the clustering is effectively on income alone. Standardising is not a refinement here — without it you are not clustering the data you think you are clustering. The one exception is when every feature is already in the same unit and the differences in spread are themselves meaningful.

13.3 K-means

Definition: Lloyd's algorithm

  1. Choose \(k\) initial centroids.
  2. Assign: attach every point to its nearest centroid.
  3. Update: move each centroid to the mean of the points attached to it.
  4. Repeat 2–3 until no assignment changes.

It minimises the within-cluster sum of squares: \(\text{WCSS} = \sum _{j} \sum _{x \in C_{j}} \Vert x - \mu _{j}\Vert ^{2}\).

K-means in four frames. (a) Three centroids are placed. (b) Every point takes the colour of its nearest centroid. (c) Each centroid moves to the mean of its points. (d) The two moves are repeated until nothing changes.
Figure 13.2. K-means in four frames. (a) Three centroids are placed. (b) Every point takes the colour of its nearest centroid. (c) Each centroid moves to the mean of its points. (d) The two moves are repeated until nothing changes.

Why it always terminates

Both half-steps can only lower WCSS. Assignment moves each point to a nearer centroid or leaves it. Update moves each centroid to the mean — and the mean is exactly the point that minimises the sum of squared distances to a set, which is why k-means uses the mean rather than, say, the median. So WCSS never increases; and since there are only finitely many ways to partition \(m\) points into \(k\) groups, a quantity that never increases must eventually stop changing. Convergence is guaranteed. Convergence to the best partition is not.

Failure What you see Remedy
Local optimum different clusters each run many restarts, keep the lowest WCSS; k-means++ initialisation
\(k\) must be guessed no principled default elbow, silhouette, or domain knowledge
Non-convex shapes crescents and rings sliced in half DBSCAN, spectral clustering, single-linkage hierarchical
Unequal sizes or densities a big loose cluster is split; small tight ones merged Gaussian mixtures, or accept it
Outliers a cluster containing one point remove outliers first, or use k-medoids, whose centres are real data points
Unscaled features the clustering follows one feature standardise before clustering

k-means++ deserves a sentence of its own, because it is what every library now does by default. Rather than choosing the initial centroids uniformly at random, it picks the first at random and then chooses each subsequent one with probability proportional to its squared distance from the nearest centroid already chosen. The centroids therefore start spread out, which both reduces the chance of a poor local optimum and typically halves the number of iterations needed.

Example 13.1: Why the centroid is the mean, and why k-means must stop

Problem. The update step moves each centroid to the mean of its members. Why the mean and not, say, the median — and why does that choice guarantee the algorithm terminates?

Step 1 — what the update step is really solving

Hold the assignment fixed. For one cluster \(C\) with members \(x\), the contribution to the objective is

\(f(c) = \sum _{x \in C} \Vert x - c\Vert ^{2}\)

and we are free to choose \(c\). It is a smooth function of \(c\) and a sum of squares, so it has a minimum where its gradient vanishes.

Step 2 — differentiate

\(\nabla _{c} \Vert x - c\Vert ^{2} =\) −2(x \(- c\)), so

\(\nabla f(c) = -2 \sum _{x \in C} (x - c) = 0\)

Split the sum, using \(\sum c =\) |C|·c:

\(c = (1/|C|) \sum _{x \in C}\) x — the mean, and nothing else. It is a minimum because the second derivative is \(2|C| > 0\).

Step 3 — why this makes the algorithm stop

Write \(W\) for the within-cluster sum of squares. Each half-step can only lower it.

Assignment. Every point moves to a centroid at least as close as its current one, so no term of \(W\) increases.

Update. By step 2 the mean is the minimiser of that cluster's term, so replacing the old centroid by the mean cannot increase it either.

Step 4 — finish the argument

\(W\) never increases, and there are only finitely many ways to partition \(m\) points into \(k\) groups — at most \(k^{m}\). A sequence that never increases and can take only finitely many values must eventually stop changing. Hence k-means always converges, in finitely many iterations.

Answer. \(c =\) the mean of the cluster; \(W\) is non-increasing at every half-step over finitely many partitions, so the algorithm terminates

Comment. Notice what the proof does not say: nothing here promises that the partition it stops at is the best one. It promises a local optimum, reached from wherever the centroids started — which is exactly why you restart k-means and keep the run with the lowest \(W\). Change the objective to \(\sum \Vert x - c\Vert\) (absolute, not squared) and step 2 returns the median instead: that is k-medians, and it resists outliers for the same reason MAE does.

# k-means, the elbow and the silhouette in one pass
from sklearn.cluster import KMeans
from sklearn.metrics import silhouette_score
from sklearn.preprocessing import StandardScaler

Xs = StandardScaler().fit_transform(X)     # never skip this before a distance

for k in range(2, 9):
    km = KMeans(n_clusters=k, n_init=10, random_state=42).fit(Xs)
    print(k, round(km.inertia_, 1),                 # inertia IS the WCSS
          round(silhouette_score(Xs, km.labels_), 3))

km = KMeans(n_clusters=3, n_init=10, random_state=42).fit(Xs)
print(km.cluster_centers_)      # in scaled units — inverse_transform to read them
print(km.n_iter_)              # how many assign/update rounds it took

n_init=10 is the restart defence from the failure table: ten runs from different k-means++ starts, keeping the lowest inertia. Set it to 1 and the result becomes a lottery.

And the same algorithm written out — the two half-steps are two lines.

# Lloyd's algorithm from scratch
import numpy as np

def kmeans(X, k, iters=100, seed=0):
    rng = np.random.default_rng(seed)
    C = X[rng.choice(len(X), k, replace=False)]         # initial centroids
    for _ in range(iters):
        d = ((X[:, None, :] - C[None, :, :]) ** 2).sum(-1)   # squared distances (m, k)
        labels = d.argmin(axis=1)                         # ASSIGN — no square roots needed
        newC = np.array([X[labels == j].mean(axis=0)        # UPDATE — the mean, from the proof
                         if (labels == j).any() else C[j]
                         for j in range(k)])
        if np.allclose(newC, C): break                     # nothing moved: converged
        C = newC
    wcss = d[np.arange(len(X)), labels].sum()
    return C, labels, wcss

13.4 Choosing the number of clusters

Within-cluster sum of squares against k. WCSS falls at every k and is zero at k = m, so the lowest value is useless; the elbow, the last k that buys a large drop (here k = 3), is what to look for.
Figure 13.3. Within-cluster sum of squares against k. WCSS falls at every k and is zero at k = m, so the lowest value is useless; the elbow, the last k that buys a large drop (here k = 3), is what to look for.

Definition: The silhouette coefficient

For a point, let a be its mean distance to the other members of its own cluster and \(b\) its mean distance to the members of the nearest other cluster. Then

\(s = (b - a) / \max(a\), b)

\(s\) near +1: comfortably inside its cluster. \(s\) near 0: on a border. \(s\) negative: closer to another cluster than its own — probably misassigned. The average \(s\) over all points scores the whole clustering.

Unlike WCSS, the average silhouette has a genuine maximum over \(k\), so it can be optimised directly rather than eyeballed. It also gives per-point diagnostics: a cluster whose points mostly have low silhouettes is one you should look at again.

Other ways to fix \(k\), in rough order of how often they are right

Domain knowledge — the marketing team wants four segments because they have four campaigns, and no statistic overrules that. The elbow. The silhouette. The gap statistic, which compares your WCSS against what uniformly random data of the same extent would give. Or hierarchical clustering, which produces every \(k\) at once and lets you decide by looking.

13.5 Further topics

k-means++ initialisation in detail

The random start is the weak point of Lloyd's algorithm, since two initial centroids can fall inside one natural group and leave another group with none. k-means++ repairs this by choosing the starting centroids one at a time, in proportion to how badly each point is currently served.

  1. Choose the first centroid uniformly at random from the data.
  2. For every point \(x\) let \(D(x)\) be the distance to the nearest centroid chosen so far.
  3. Choose the next centroid from the data points, with \(P(x) = D(x)^{2} \Big/ \sum_{x'} D(x')^{2}\).
  4. Repeat steps 2 and 3 until \(k\) centroids are chosen, then run Lloyd's algorithm as usual.

A point already at a centroid has \(D = 0\) and so can never be chosen again, and a point far from every centroid has a large share of the probability. Squaring makes the preference sharp: a point twice as far away is four times as likely to be picked. The seeding is still random, so it does not remove the need for restarts, but it is a far better random start. Its expected WCSS is provably within a factor that grows only logarithmically with \(k\) of the best possible, and in practice it also saves iterations because the centroids begin near where they will end.

Convergence criteria and cost

"Repeat until nothing changes" is the mathematical stopping rule, and implementations add two practical ones: stop when the centroids move by less than a small tolerance, and stop after a fixed maximum number of iterations. Both exist for the same reason, that on large data the last few iterations move a handful of borderline points and improve the WCSS by almost nothing.

The cost of one iteration is \(O(mkn)\) for \(m\) points, \(k\) centroids and \(n\) features, since every point is compared with every centroid, so a run of \(i\) iterations costs \(O(mkni)\). This is linear in the number of points, which is why k-means is the method that scales to millions of rows. It is also coordinate descent: the algorithm alternates between improving the assignments with the centroids fixed and improving the centroids with the assignments fixed, as gradient descent improved one parameter at a time in Unit 3, and like it can only promise a local minimum.

Soft clustering and mixture models

In hard clustering every point belongs to exactly one cluster. A soft clustering gives each point a membership in every cluster, and the memberships of a point add up to 1. A point lying between two groups is then described as, say, 82% in one and 18% in the other, which is more honest than forcing a choice.

The standard soft method is the Gaussian mixture model. Each cluster is a normal distribution with its own mean, and the membership of a point, called its responsibility, is the probability that the point came from that component. With two components of equal spread \(\sigma\) and equal weight, centred at \(\mu_{1}\) and \(\mu_{2}\), the responsibility of the first is

\[r_{1}(x) = \frac{e^{-(x-\mu_{1})^{2}/2\sigma^{2}}}{e^{-(x-\mu_{1})^{2}/2\sigma^{2}} + e^{-(x-\mu_{2})^{2}/2\sigma^{2}}} = \frac{1}{1 + e^{-\left[(x-\mu_{2})^{2} - (x-\mu_{1})^{2}\right]/2\sigma^{2}}}\]

which is a logistic curve in the difference of the two squared distances. With \(\mu_{1} = 2\), \(\mu_{2} = 8\) and \(\sigma = 2\):

\(x\) 2 3 4 5 6 7 8
\(r_{1}(x)\) 0.989 0.953 0.818 0.500 0.182 0.047 0.011

The point \(x = 5\), midway between the centres, is exactly 50% in each; the point \(x = 4\) is 82% in the first. The fitting procedure is the EM algorithm, and it has the same two-half-step shape as k-means. The E-step computes the responsibilities with the current parameters; the M-step recomputes each mean (and spread and weight) as a responsibility-weighted average of the data. K-means is the hard limit of this procedure: shrink \(\sigma\) towards zero and the logistic curve becomes a step, so every responsibility is 0 or 1 and the weighted mean becomes the ordinary mean of the points assigned. Mixtures also allow elliptical clusters of different sizes, which is how they escape the equal-size, round-cluster assumption of k-means. Fuzzy c-means is another soft method, with memberships defined by distance rather than by a probability model.

k-medoids

K-means needs a mean, and a mean exists only for numeric features and is dragged by outliers. k-medoids keeps the same assign-and-update structure but restricts each cluster centre to be one of the data points, the medoid: the member with the smallest total dissimilarity to the others in its cluster. The classical algorithm (PAM, partitioning around medoids) picks \(k\) medoids, assigns each point to its nearest, and then tries swapping each medoid with a non-medoid, keeping a swap whenever it lowers the total dissimilarity. For the cluster \(\{1, 2, 3, 4, 100\}\) the mean is \(22\), which is not close to anything, while the medoid is \(3\) (total distance \(101\), against \(102\) for \(2\) and \(4\)). Because only pairwise dissimilarities are used, k-medoids works with any distance, including those for categorical data, and it is the robust choice when outliers cannot be removed. The price is speed: the swap search is much more expensive than computing means, so it is used on modest data sizes.

Density-based clustering and DBSCAN

K-means and the linkage methods describe a cluster by its centre or its diameter. A density-based method instead calls a cluster a region where points are packed densely, separated from other clusters by sparse regions. DBSCAN has two parameters, a radius \(\varepsilon\) and a count minPts, and sorts points into three kinds:

  • a core point has at least minPts points (itself included) within distance \(\varepsilon\);
  • a border point is not core but lies within \(\varepsilon\) of a core point;
  • every other point is noise.

A cluster is a maximal set of core points that can be reached from one another through chains of neighbouring core points, plus the border points attached to them. Take the points \(1, 2, 3, 4, 10, 11, 12, 25\) with \(\varepsilon = 1.5\) and minPts \(= 3\). The points 2, 3 and 11 each have three points within 1.5, so they are core. The points 1 and 4 are within reach of core point 2 or 3, and 10 and 12 of core point 11, so they are border points. The point 25 has no neighbours and is noise. The result is the clusters \(\{1, 2, 3, 4\}\) and \(\{10, 11, 12\}\) with 25 labelled as an outlier, and nobody had to say that there were two clusters.

The same 200 points arranged as two interlocking crescents. (a) K-means with k = 2 cuts both crescents with a straight line and mixes them. (b) DBSCAN follows each crescent and recovers them exactly.
Figure 13.4. The same 200 points arranged as two interlocking crescents. (a) K-means with k = 2 cuts both crescents with a straight line and mixes them. (b) DBSCAN follows each crescent and recovers them exactly.

DBSCAN is the standard answer to the shapes k-means cannot represent. It finds clusters of any shape, labels outliers instead of absorbing them, and needs no \(k\). Its weaknesses are that the result is sensitive to \(\varepsilon\) and minPts, which must be chosen to suit the data, and that one pair of values cannot suit clusters of very different densities. It is covered here only as context, as the contrast to the partitional methods.

13.6 Worked examples

The examples below work through the calculations of this chapter in full. Try each one on paper before reading the steps.

Example 13.2: Two full iterations of k-means

Problem. Points \(A(1,1), B(1.5,2), C(3,4), D(5,7), E(3.5,5), F(4.5,5), G(3.5,4.5)\). Initial centroids \(\mu _{1} = A = (1,1)\) and \(\mu _{2} = D = (5,7)\). Run two iterations.

Iteration 1, assignment — compare squared distances

point \(d^{2}\) to (1,1) \(d^{2}\) to (5,7) cluster
A (1,1) 0 \(16+36 = 52\) 1
B (1.5,2) \(0.25+1 = 1.25\) \(12.25+25 = 37.25\) 1
C (3,4) \(4+9 = 13\) \(4+9 = 13\) tie \(\to 1\)
D (5,7) \(16+36 = 52\) 0 2
E (3.5,5) \(6.25+16 = 22.25\) \(2.25+4 = 6.25\) 2
F (4.5,5) \(12.25+16 = 28.25\) \(0.25+4 = 4.25\) 2
G (3.5,4.5) \(6.25+12.25 = 18.5\) \(2.25+6.25 = 8.5\) 2

No square roots are needed: comparing \(d^{2}\) gives the same winner, and the arithmetic stays exact. \(C\) is equidistant; ties are broken by taking the lower index.

Iteration 1, update

Cluster \(1 =\) {A, B, C}: \(\mu _{1} = ((1+1.5+3)/3, (1+2+4)/3) = (5.5/3, 7/3) = (1.833, 2.333)\)

Cluster \(2 =\) {D, E, F, G}: \(\mu _{2} = ((5+3.5+4.5+3.5)/4, (7+5+5+4.5)/4) = (16.5/4, 21.5/4) = (4.125, 5.375)\)

Iteration 2, assignment

\(A: d^{2}\) to \(\mu _{1} = 0.694+1.777 = 2.47\); to \(\mu _{2} = 9.77+19.14 = 28.9 \to\) cluster 1

B: \(0.111+0.111 = 0.22\) vs \(6.89+11.39 = 18.3 \to\) cluster 1

C: \(1.361+2.777 = 4.14\) vs \(1.266+1.891 = 3.16 \to\) cluster 2 (it has changed sides)

D: \(10.03+21.78 = 31.8\) vs \(0.766+2.64 = 3.41 \to\) cluster 2

E, F, G: all clearly nearer \(\mu _{2} \to\) cluster 2

Iteration 2, update

Cluster \(1 =\) {A, B}: \(\mu _{1} = (1.25, 1.5)\)

Cluster \(2 =\) {C, D, E, F, G}: \(\mu _{2} = (19.5/5, 25.5/5) = (3.9, 5.1)\)

Answer. After two iterations: {A, B} with centroid (1.25, 1.5) and {C, D, E, F, G} with centroid (3.9, 5.1).

Comment. \(C\) changing sides in the second iteration is the interesting event: the first assignment was made by centroids that were just two arbitrary data points, and once the centroids moved to real means, the correct answer for \(C\) changed. A third iteration would leave everything where it is — no point wants to move — so the algorithm has converged.

Example 13.3: Four measures on one pair of vectors

Problem. Two short documents are described by counts of three words: \(a = (2, 0, 1)\) and \(b = (1, 0, 3)\). Compute the Euclidean, Manhattan, Minkowski (\(p = 3\)) and Chebyshev distances, the cosine similarity and the cosine distance, and check the ordering of the distances.

Step 1 — coordinate differences

\(a - b = (2-1,\; 0-0,\; 1-3) = (1, 0, -2)\)

Step 2 — the four distances

\(d_{2} = \sqrt{1^{2} + 0^{2} + (-2)^{2}} = \sqrt{5} = 2.236\)

\(d_{1} = |1| + |0| + |-2| = 3\)

\(d_{3} = \left(|1|^{3} + |0|^{3} + |-2|^{3}\right)^{1/3} = 9^{1/3} = 2.080\)

\(d_{\infty} = \max(1, 0, 2) = 2\)

Step 3 — cosine similarity and cosine distance

\(a \cdot b = 2\cdot 1 + 0\cdot 0 + 1\cdot 3 = 5\), \(\;\Vert a\Vert = \sqrt{5}\), \(\;\Vert b\Vert = \sqrt{10}\)

\(\cos(a, b) = \dfrac{5}{\sqrt{5}\,\sqrt{10}} = \dfrac{5}{\sqrt{50}} = \dfrac{1}{\sqrt{2}} = 0.7071\)

The angle between the vectors is \(\arccos(0.7071) = 45^{\circ}\), and the cosine distance is \(1 - 0.7071 = 0.2929\).

Step 4 — the arithmetic check

\(d_{\infty} \le d_{3} \le d_{2} \le d_{1}\) gives \(2 \le 2.080 \le 2.236 \le 3\), which holds.

Answer. Euclidean \(\sqrt{5} = 2.236\); Manhattan \(3\); Minkowski (\(p=3\)) \(2.080\); Chebyshev \(2\); cosine similarity \(0.7071\) (angle \(45^{\circ}\)); cosine distance \(0.2929\).

Comment. The Minkowski distance falls as \(p\) rises, from \(d_{1} = 3\) towards \(d_{\infty} = 2\), so \(d_{3}\) lies between Chebyshev and Euclidean, not between Euclidean and Manhattan. A larger \(p\) lets the single biggest coordinate gap count for more of the total, and in the limit it is the only thing that counts.

Example 13.4: Cosine against Euclidean, and what scaling does to a distance

Problem. (a) Ravi rates three films on a 1 to 5 scale, \((5, 1, 4)\), and Meera, who used a 1 to 10 slider, gives \((10, 2, 8)\). Do they have the same taste? (b) Six customers are described by age (years) and salary (rupees). Show what the raw Euclidean distance between customers 1 and 2 measures, and how standardising changes it.

ID Age Salary
1 44 72000
2 27 48000
3 30 54000
4 38 61000
5 50 83000
6 37 67000

Step 1 — part (a): the two measures

Meera's vector is exactly twice Ravi's, \((10, 2, 8) = 2\,(5, 1, 4)\), so the vectors point in the same direction.

\(\cos = \dfrac{5\cdot 10 + 1\cdot 2 + 4\cdot 8}{\sqrt{42}\,\sqrt{168}} = \dfrac{84}{\sqrt{7056}} = \dfrac{84}{84} = 1\)

\(d_{2} = \sqrt{(5-10)^{2} + (1-2)^{2} + (4-8)^{2}} = \sqrt{25 + 1 + 16} = \sqrt{42} = 6.481\)

Cosine says the tastes are identical; Euclidean distance calls them far apart, because it is measuring the difference in the scale people used rather than in what they liked.

Step 2 — part (b): the raw distance

The differences between customers 1 and 2 are \(44 - 27 = 17\) years and \(72000 - 48000 = 24000\) rupees.

\(d^{2} = 17^{2} + 24000^{2} = 289 + 576\,000\,000 = 576\,000\,289\), so \(d = 24\,000.006\)

Age supplies \(289 / 576\,000\,289 \approx 5 \times 10^{-7}\) of the squared distance. The raw distance is the salary difference and nothing else.

Step 3 — standardise each feature

Age: mean \(= 226/6 = 37.667\), and \(\sigma = \sqrt{365.33/6} = 7.803\).

Salary: mean \(= 385000/6 = 64166.7\), and \(\sigma = 11538.6\).

(Here \(\sigma\) is the population standard deviation, dividing by 6. The sample version, dividing by 5, would change every \(z\)-score by the same factor and leave the conclusion alone.)

Step 4 — the same two customers after scaling

\(z_{\text{age}}\): \(\;(44 - 37.667)/7.803 = 0.812\) and \((27 - 37.667)/7.803 = -1.367\)

\(z_{\text{salary}}\): \(\;(72000 - 64166.7)/11538.6 = 0.679\) and \((48000 - 64166.7)/11538.6 = -1.401\)

\(d^{2} = (0.812 + 1.367)^{2} + (0.679 + 1.401)^{2} = 2.179^{2} + 2.080^{2} = 4.748 + 4.326 = 9.074\), so \(d = 3.012\)

Now age supplies \(4.748/9.074 = 52\%\) of the squared distance and salary the other \(48\%\).

Answer. (a) Cosine similarity \(1\), Euclidean distance \(6.481\): same direction, different length. (b) Raw \(d = 24\,000.006\), entirely salary; standardised \(d = 3.012\), with age and salary contributing about equally.

Comment. Standardising does not make the two customers more or less similar in any absolute sense. It changes the question from "how many rupees apart?" to "how many standard deviations apart, summed over the features?", which is the question you meant to ask. Any \(k\)-means run on the raw table would have been a clustering by salary.

Example 13.5: K-means in one dimension, with WCSS tracked

Problem. Cluster \(\{2, 3, 6, 8, 10, 12\}\) into \(k = 2\) groups, starting with centroids \(c_{1} = 2\) and \(c_{2} = 10\). Run to convergence and record the WCSS after each half-step.

Step 1 — assignment (iteration 1)

\(x\) \(\lvert x - 2\rvert\) \(\lvert x - 10\rvert\) cluster
2 0 8 1
3 1 7 1
6 4 4 tie, take 1
8 6 2 2
10 8 0 2
12 10 2 2

So \(C_{1} = \{2, 3, 6\}\) and \(C_{2} = \{8, 10, 12\}\).

Step 2 — the WCSS of this assignment, about the old centroids

\(\text{WCSS} = (0 + 1 + 16) + (4 + 0 + 4) = 17 + 8 = 25\)

Step 3 — update

\(c_{1} = (2 + 3 + 6)/3 = 11/3 = 3.667\), \(\quad c_{2} = (8 + 10 + 12)/3 = 10\)

The same two clusters now measured about their means:

\(\text{WCSS} = \left[(2 - 3.667)^{2} + (3 - 3.667)^{2} + (6 - 3.667)^{2}\right] + 8 = (2.778 + 0.444 + 5.444) + 8 = 8.667 + 8 = 16.667\)

Step 4 — assignment (iteration 2)

Distances to \(c_{1} = 3.667\) and \(c_{2} = 10\): for \(x = 6\) they are \(2.333\) and \(4\), so 6 stays in cluster 1; for \(x = 8\) they are \(4.333\) and \(2\), so 8 stays in cluster 2. The other four points are plainly unchanged. No point moves, so the centroids stay at \(3.667\) and \(10\) and the algorithm has converged.

Answer. \(C_{1} = \{2, 3, 6\}\) with centroid \(3.667\) and \(C_{2} = \{8, 10, 12\}\) with centroid \(10\). The WCSS fell \(25 \to 16.667\) at the first update and then stopped changing.

Comment. The whole improvement came from the centroid update, because the initial centres \(2\) and \(10\) were already data points and the first assignment was reasonable. The tie at point 6 was broken in favour of cluster 1, the lower index, which is what a library does. Break it the other way and the same algorithm converges to \(\{2, 3\}\) and \(\{6, 8, 10, 12\}\) with centroids \(2.5\) and \(9\) and WCSS \(20.5\), a worse local optimum reached from the same starting centres.

Example 13.6: A poor start recovers: WCSS at every half-step

Problem. Cluster \(x_{1}(1,1),\; x_{2}(2,1),\; x_{3}(4,3),\; x_{4}(5,4),\; x_{5}(6,5),\; x_{6}(6,3)\) with \(k = 2\) and deliberately bad starting centroids \(\mu_{1} = (1,1)\), \(\mu_{2} = (2,1)\), which sit side by side. Run to convergence and give the WCSS after every half-step.

Step 1 — first assignment

Squared distances to \((1,1)\) and \((2,1)\):

point to \(\mu_{1}\) to \(\mu_{2}\) cluster
\(x_{1}\) (1,1) 0 1 1
\(x_{2}\) (2,1) 1 0 2
\(x_{3}\) (4,3) \(9 + 4 = 13\) \(4 + 4 = 8\) 2
\(x_{4}\) (5,4) \(16 + 9 = 25\) \(9 + 9 = 18\) 2
\(x_{5}\) (6,5) \(25 + 16 = 41\) \(16 + 16 = 32\) 2
\(x_{6}\) (6,3) \(25 + 4 = 29\) \(16 + 4 = 20\) 2

The WCSS of this assignment about the starting centroids is the sum of the smaller entries: \(0 + 0 + 8 + 18 + 32 + 20 = 78\).

Step 2 — first update

\(\mu_{1} = (1, 1)\) and \(\mu_{2} = \left(\dfrac{2+4+5+6+6}{5}, \dfrac{1+3+4+5+3}{5}\right) = (4.6,\; 3.2)\)

About these centroids the same assignment has WCSS \(= 0 + (11.6 + 0.4 + 0.8 + 5.2 + 2.0) = 20\), where, for example, \(x_{2}\) contributes \((2 - 4.6)^{2} + (1 - 3.2)^{2} = 6.76 + 4.84 = 11.6\).

Step 3 — second assignment

Squared distances to \(\mu_{1} = (1,1)\) and \(\mu_{2} = (4.6, 3.2)\): \(x_{2}\) gives \(1\) and \(11.6\), so it moves to cluster 1. The others give \(x_{3}\): \(13\) and \(0.4\); \(x_{4}\): \(25\) and \(0.8\); \(x_{5}\): \(41\) and \(5.2\); \(x_{6}\): \(29\) and \(2.0\), so they stay in cluster 2.

Now \(C_{1} = \{x_{1}, x_{2}\}\) and \(C_{2} = \{x_{3}, x_{4}, x_{5}, x_{6}\}\). Measured about the old centroids the WCSS is \(0 + 1 + 0.4 + 0.8 + 5.2 + 2.0 = 9.4\).

Step 4 — second update

\(\mu_{1} = (1.5, 1)\), giving \(0.25 + 0.25 = 0.5\).

\(\mu_{2} = \left(\dfrac{4+5+6+6}{4}, \dfrac{3+4+5+3}{4}\right) = (5.25,\; 3.75)\), giving \(2.125 + 0.125 + 2.125 + 1.125 = 5.5\).

WCSS \(= 0.5 + 5.5 = 6.0\). A third assignment moves nobody, so the algorithm stops.

Answer. Final clusters \(\{x_{1}, x_{2}\}\) and \(\{x_{3}, x_{4}, x_{5}, x_{6}\}\) with centroids \((1.5, 1)\) and \((5.25, 3.75)\). The WCSS sequence is \(78 \to 20 \to 9.4 \to 6.0 \to 6.0\).

Comment. Every half-step lowers the WCSS or leaves it unchanged. That sequence is the termination proof of the chapter made visible: a non-increasing list of numbers that cannot go on falling for ever. Notice also how much the poor start cost: the first assignment put five points into one cluster, and it took two updates to undo it.

Example 13.7: One bad point, and why a medoid does not move

Problem. The points \((0,0), (1,0), (0,1)\) form a tight cluster. A data-entry slip adds \((100, 100)\). Find the centroid before and after, and compare with the medoid.

Step 1 — the centroid before the slip

\(\bar{x} = (0 + 1 + 0)/3 = 0.333\) and \(\bar{y} = (0 + 0 + 1)/3 = 0.333\), so the centroid is \((0.333, 0.333)\), with WCSS \(= \tfrac{2}{9} + \tfrac{5}{9} + \tfrac{5}{9} = 1.333\).

Step 2 — the centroid after the slip

\(\bar{x} = (0 + 1 + 0 + 100)/4 = 25.25\) and \(\bar{y} = 25.25\). The centroid moves to \((25.25, 25.25)\), which is nowhere near any of the four points, and the cluster's WCSS becomes

\(1275.125 + 1225.625 + 1225.625 + 11175.125 = 14\,901.5\)

about 11 000 times its value before the slip.

Step 3 — what k-means does about it

With \(k = 2\), putting the bad point in a cluster of its own removes almost the whole 14 901.5 and leaves 1.333. So the cheapest way to spend one of the two clusters is on a single typing error.

Step 4 — the medoid

A medoid must be one of the data points, chosen to minimise the total distance to the others.

candidate total Euclidean distance to the rest
\((0,0)\) \(1 + 1 + 141.42 = 143.42\)
\((1,0)\) \(1 + 1.414 + 140.72 = 143.13\)
\((0,1)\) \(1 + 1.414 + 140.72 = 143.13\)
\((100,100)\) \(141.42 + 140.72 + 140.72 = 422.85\)

The medoid is \((1, 0)\) (tied with \((0, 1)\)), a real point sitting inside the genuine group.

Answer. The centroid jumps from \((0.333, 0.333)\) to \((25.25, 25.25)\); a medoid is still a genuine point at \((1,0)\) or \((0,1)\).

Comment. The squared distance is what makes the outlier so powerful: a point about 141 units from the group contributes roughly 20 000 to a sum of squared distances and only 141 to a sum of distances. That is the same reason the mean is outlier-sensitive and the median is not, and it is why k-medoids and k-medians are the standard robust variants.

13.7 Common mistakes to avoid

Each of the following is a mistake that costs marks in an examination or accuracy in practice.

  • Do not cluster unscaled features. It is the commonest cause of a meaningless result, and it is invisible unless you check.
  • Do not choose \(k\) by minimising WCSS. It always answers \(k = m\).
  • Do not run k-means once and trust it. Restart, and keep the best.
  • Do not apply k-means to shapes it cannot represent. Straight boundaries, convex clusters — that is the whole of its vocabulary.
  • Do not take square roots when you only need to compare distances. \(d^{2}\) gives the same ordering and stays exact.
  • Do not use Euclidean distance on text. Cosine, on TF-IDF vectors.

13.8 Summary

After working through this chapter you should be able to do the following.

  • State what clustering is for — high similarity inside, low similarity between — and place any method in the partitional / hierarchical / density scheme and on the hard–soft axis.
  • Compute every distance in the course, know that Chebyshev \(\le\) Euclidean \(\le\) Manhattan as a check on your arithmetic, and can argue for cosine on text because it measures direction rather than length.
  • Run k-means by hand using squared distances, and you can prove it terminates: both half-steps lower WCSS, the mean is exactly the minimiser of squared distance, and there are only finitely many partitions.
  • Name all five ways k-means fails — local optima, a guessed \(k\), non-convex shapes, unequal sizes, outliers — with the remedy for each, and you know what k-means++ changes and why.

13.9 Exercises

  1. \(A = (2, 4, 5), B = (5, 1, 9)\). Compute the Euclidean, Manhattan and Chebyshev distances and the cosine similarity.

    Answer

    The differences are \((-3, 3, -4)\).

    Euclidean: \(\sqrt{9 + 9 + 16} = \sqrt{34} = 5.831\). Manhattan: \(3 + 3 + 4 = 10\). Chebyshev: \(\max(3, 3, 4) = 4\).

    Cosine: \(A \cdot B = 10 + 4 + 45 = 59\), \(\Vert A\Vert = \sqrt{45} = 6.708\), \(\Vert B\Vert = \sqrt{107} = 10.344\), so \(\cos = 59/69.39 = 0.8503\).

    Check: \(4 \le 5.831 \le 10\), as it must be.

  2. Points (1,2), (2,1), (8,9), (9,8) with initial centroids (1,2) and (9,8). Run k-means to convergence and give the final centroids.

    Answer

    Assignment: (1,2) goes to the first centroid (distance 0); (2,1) has squared distances \(2\) and \(98\), so it goes to the first; (8,9) has \(98\) and \(2\), so it goes to the second; (9,8) goes to the second.

    Update: \(\mu_{1} = (1.5, 1.5)\) and \(\mu_{2} = (8.5, 8.5)\). A second assignment moves nothing, so the algorithm has converged.

    Final centroids \((1.5, 1.5)\) and \((8.5, 8.5)\), with WCSS \(= 4 \times 0.5 = 2\).

  3. Prove that the mean minimises \(\sum (x - c)^{2}\) over \(c\), and say why this makes it the right centroid for k-means.

    Answer

    Let \(f(c) = \sum_{i=1}^{n} (x_{i} - c)^{2}\). Then \(f'(c) = -2\sum_{i}(x_{i} - c) = 0\) gives \(\sum_{i} x_{i} = nc\), so \(c = \bar{x}\). Since \(f''(c) = 2n > 0\), this is a minimum.

    A second proof needs no calculus. Write \(x_{i} - c = (x_{i} - \bar{x}) + (\bar{x} - c)\) and square. The cross term is \(2(\bar{x} - c)\sum (x_{i} - \bar{x}) = 0\), so \(\sum (x_{i} - c)^{2} = \sum (x_{i} - \bar{x})^{2} + n(\bar{x} - c)^{2}\), which is smallest exactly when \(c = \bar{x}\).

    For vectors the same argument holds coordinate by coordinate, because the squared Euclidean distance is a sum over coordinates.

    In k-means the update step holds the assignment fixed and chooses each centroid to minimise its cluster's contribution to WCSS. The mean is that minimiser, so the update cannot increase WCSS. Together with an assignment step that cannot increase it either, and finitely many partitions, this is why the algorithm terminates.

  4. A clustering has clusters {(0,0), (0,2)} and {(6,6), (6,8), (6,10)}. Compute the WCSS.

    Answer

    The first centroid is \((0, 1)\) and the squared distances are \(1 + 1 = 2\). The second centroid is \((6, 8)\) and the squared distances are \(4 + 0 + 4 = 8\). WCSS \(= 2 + 8 = 10\).

  5. Explain why WCSS is a legitimate way to compare two runs at the same \(k\) but not a way to compare \(k = 3\) with \(k = 5\).

    Answer

    Two runs at the same \(k\) are two local optima of the same objective with the same number of centroids, so the lower WCSS is simply the better solution to the problem being solved, and n_init keeps the lowest.

    Across values of \(k\) the comparison is rigged. A clustering with more centroids can always match or beat one with fewer, because adding a centroid can only bring points closer to a centre, and at \(k = m\) every point is its own centroid and the WCSS is zero. So the larger \(k\) almost always wins whether or not the extra clusters are real. To compare different \(k\) use something that is not monotone in \(k\): the elbow of the WCSS curve, the average silhouette, the gap statistic, or the purpose the clusters serve.

  6. You cluster 10 000 customers on 30 standardised features and get five clusters with average silhouette 0.11. What do you conclude, and what would you try next?

    Answer

    An average silhouette near \(0.1\) is close to zero: on average the points are barely nearer their own cluster than the next one. The clusters overlap heavily, so you should not describe the five groups as real, distinct segments. The result is a partition, not a discovery.

    Things to try: compute the silhouette for several \(k\) to see whether any is clearly better; draw the silhouette plot to find whether one or two clusters are good and the rest ragged; reduce dimension first, since in 30 dimensions distances between points become similar to each other and silhouette suffers (PCA, or dropping redundant features); check with the gap statistic whether the data has cluster structure at all; try another method such as a Gaussian mixture, which allows overlap; and ask whether the groups are useful for the task even if they are not sharp, because a soft boundary does not make a segmentation worthless.

  7. Describe how to compress an image to 16 colours with k-means: what are the examples, what are the features, and what is stored at the end?

    Answer

    The examples are the pixels, so \(m = \text{rows} \times \text{columns}\). The features are the three colour values (R, G, B) of each pixel, so every example is a point in a three-dimensional colour cube. Run k-means with \(k = 16\).

    The 16 centroids are the palette: sixteen representative colours. Each pixel is replaced by the colour of its nearest centroid. What is stored is the palette (16 colours of 24 bits each) and, for each pixel, a 4-bit index into it, since \(2^{4} = 16\). The quantity minimised, WCSS, is exactly the total squared colour error of the compressed image.

    For a \(1000 \times 800\) image, 800 000 pixels at 24 bits take \(19\,200\,000\) bits (2.4 MB). With the palette it takes \(800\,000 \times 4 + 16 \times 24 = 3\,200\,384\) bits (about 0.40 MB), a saving of about six times, the palette being negligible.

  8. For \(a = (1, 3, 4)\) and \(b = (4, 3, 0)\) compute the Euclidean, Manhattan, Minkowski (\(p = 3\)) and Chebyshev distances and the cosine similarity.

    Answer

    The difference is \((-3, 0, 4)\).

    Euclidean \(\sqrt{9 + 0 + 16} = 5\). Manhattan \(3 + 0 + 4 = 7\). Minkowski (\(p=3\)): \((27 + 0 + 64)^{1/3} = 91^{1/3} = 4.498\). Chebyshev \(4\).

    Cosine: \(a \cdot b = 4 + 9 + 0 = 13\), \(\Vert a\Vert = \sqrt{26} = 5.099\), \(\Vert b\Vert = 5\), so \(\cos = 13/25.495 = 0.510\).

    The ordering \(4 \le 4.498 \le 5 \le 7\) confirms the arithmetic.

  9. Two users rate items as \(u = (2, 2)\) and \(v = (6, 6)\). Compute the Euclidean distance and the cosine similarity, say what each tells you, and explain why a recommender system may prefer cosine here.

    Answer

    \(d_{2} = \sqrt{16 + 16} = \sqrt{32} = 5.657\). \(\cos = \dfrac{12 + 12}{\sqrt{8}\,\sqrt{72}} = \dfrac{24}{24} = 1\).

    The Euclidean distance says the points are far apart; the cosine says they point in exactly the same direction. Both rate the two items equally and differ only in how generously they rate: \(v\) is \(u\) multiplied by 3. A recommender wants to know whether two users like the same things in the same proportions, and a habit of giving high or low scores should not count against them, so cosine, which ignores the length of the vector, is the better measure.

  10. Points \(P_{1} = (1, 2), P_{2} = (1, 4), P_{3} = (2, 2), P_{4} = (6, 4), P_{5} = (7, 3), P_{6} = (7, 5)\), initial centroids \(\mu_{1} = (1, 2)\) and \(\mu_{2} = (2, 2)\). Run k-means to convergence. Give the final clusters, centroids and WCSS, and say whether any point changed cluster after the first update.

    Answer

    First assignment (squared distances to \(\mu_{1}\), \(\mu_{2}\)): \(P_{1}\): 0, 1; \(P_{2}\): 4, 5; \(P_{3}\): 1, 0; \(P_{4}\): 29, 20; \(P_{5}\): 37, 26; \(P_{6}\): 45, 34. So \(C_{1} = \{P_{1}, P_{2}\}\) and \(C_{2} = \{P_{3}, \dots, P_{6}\}\).

    Update: \(\mu_{1} = (1, 3)\) and \(\mu_{2} = (5.5, 3.5)\). The WCSS of this partition is \(2 + 22 = 24\).

    Second assignment: \(P_{3}\) has squared distances \(2\) and \(14.5\), so it moves to cluster 1; the others stay.

    Update: \(\mu_{1} = (4/3, 8/3) = (1.333, 2.667)\) and \(\mu_{2} = (20/3, 4) = (6.667, 4)\). A further assignment changes nothing.

    Final clusters \(\{P_{1}, P_{2}, P_{3}\}\) and \(\{P_{4}, P_{5}, P_{6}\}\); WCSS \(= 3.333 + 2.667 = 6\). The WCSS went \(24 \to 6\) at the last update and never rose.

  11. The one-dimensional data \(\{4, 8, 12, 20, 32, 36, 48\}\) is clustered with \(k = 2\) and initial centres \(32\) and \(48\). Run k-means, and give the clusters, the centres and the sum of squared errors at the end of every iteration.

    Answer

    Iteration 1: \(4, 8, 12, 20, 32, 36\) are nearer 32 (the point 36 is 4 from 32 and 12 from 48); 48 goes to the second. Centres \(18.667\) and \(48\); SSE \(= 853.33 + 0 = 853.33\).

    Iteration 2: 36 is now nearer 48 (12 against 17.33), while 32 stays with the first (13.33 against 16). Clusters \(\{4, 8, 12, 20, 32\}\) and \(\{36, 48\}\); centres \(15.2\) and \(42\); SSE \(= 492.8 + 72 = 564.8\).

    Iteration 3: 32 is now nearer the second centre (16.8 against 10). Clusters \(\{4, 8, 12, 20\}\) and \(\{32, 36, 48\}\); centres \(11\) and \(38.667\); SSE \(= 140 + 138.67 = 278.67\).

    Iteration 4: nothing moves, so these are the final clusters. The SSE fell \(853.33 \to 564.8 \to 278.67\).

  12. (a) True or false, with a reason: k-means is guaranteed to find the clustering with the smallest possible WCSS. (b) True or false, with a reason: increasing \(k\) never increases the WCSS.

    Answer

    (a) False. It is guaranteed to stop, at a local optimum that depends on the initial centroids. Different starts can give different WCSS, which is why you restart and keep the best.

    (b) True for the best clustering at each \(k\): the optimal WCSS is non-increasing in \(k\) and reaches 0 at \(k = m\). It need not be true of the single runs you actually make, because a poor local optimum at a larger \(k\) can have a higher WCSS than a good one at a smaller \(k\). Even where it holds, it is the reason WCSS cannot be used to choose \(k\).

  13. A shop clusters customers on age (about 20 to 60) and annual income (about 20 000 to 2 000 000 rupees) without scaling. By how much does income outweigh age in a squared distance for the most extreme gaps, and what is the fix?

    Answer

    The most extreme gaps are \(40\) years and \(1\,980\,000\) rupees. In the squared distance age contributes \(40^{2} = 1600\) and income \(1\,980\,000^{2} = 3.92 \times 10^{12}\), about \(2.5 \times 10^{9}\) times as much. For ordinary gaps the ratio is smaller but still enormous, so the clusters are effectively clusters by income, and age is ignored.

    The fix is to put the features on comparable scales before computing any distance: standardise each to mean 0 and standard deviation 1 (the \(z\)-score), or rescale each to \([0, 1]\).

  14. Five points on a line are \(1, 2, 3, 10, 11\). In k-means++ the first centre is the point \(2\). What are the probabilities that each point is chosen as the second centre, and how does this compare with choosing uniformly among the other four points?

    Answer

    The squared distances to the nearest chosen centre are \(1, 0, 1, 64, 81\) for the points \(1, 2, 3, 10, 11\), which sum to \(147\). The selection probabilities are these divided by 147: \(0.0068,\; 0,\; 0.0068,\; 0.4354,\; 0.5510\).

    The chance that the second centre lands in the far group \(\{10, 11\}\) is \(145/147 = 0.986\). Choosing uniformly among the other four points gives only \(2/4 = 0.5\), so a plain random start has an even chance of putting both centres in the same group, which k-means++ almost never does.