Within-cluster scatter

Section of K-means clustering, part of Statistical learning

Within-cluster scatter

Type Section
Taught in K-means clustering
Part Statistical learning
Questions using it 2

A clustering is a map C from the observation indices i=1,\ldots,n to the labels 1,\ldots,K. To compare maps one needs a single number. The number used here is the total squared distance between observations that share a label, the within-cluster point scatter,

W(C)=\frac12\sum_{k=1}^K\sum_{C(i)=k}\sum_{C(l)=k}\|\mathbf{x}_i-\mathbf{x}_l\|^2.

The factor \tfrac12 stops each unordered pair from being counted twice. It does not change which clustering is best. It makes the identity with distances to means an equality, rather than an equality up to a factor 2.

From pairs to cluster means

Main article: From pairs to cluster means

The pairwise sum couples every pair inside a cluster, which is an awkward object to minimise directly. The equivalent form sums squared distances from each point to its cluster mean. Let

N_k=\sum_{i=1}^n 1_{\{C(i)=k\}}

be the size of cluster k, and let \bar{\mathbf{x}}_k be the mean of its points. Inside one cluster, add and subtract that mean. The cross term vanishes for the same reason as in the expansion of a corrected cross-product matrix: the sum of deviations from the mean of those points is zero.

\begin{aligned} \sum_{C(i)=k}\sum_{C(l)=k}\|\mathbf{x}_i-\mathbf{x}_l\|^2 &=\sum_{C(i)=k}\sum_{C(l)=k}\bigl\|(\mathbf{x}_i-\bar{\mathbf{x}}_k)-(\mathbf{x}_l-\bar{\mathbf{x}}_k)\bigr\|^2\\ &=\sum_{C(i)=k}\sum_{C(l)=k}\Bigl( \|\mathbf{x}_i-\bar{\mathbf{x}}_k\|^2+\|\mathbf{x}_l-\bar{\mathbf{x}}_k\|^2 -2(\mathbf{x}_i-\bar{\mathbf{x}}_k)^\top(\mathbf{x}_l-\bar{\mathbf{x}}_k) \Bigr)\\ &=N_k\sum_{C(i)=k}\|\mathbf{x}_i-\bar{\mathbf{x}}_k\|^2 +N_k\sum_{C(l)=k}\|\mathbf{x}_l-\bar{\mathbf{x}}_k\|^2\\ &=2N_k\sum_{C(i)=k}\|\mathbf{x}_i-\bar{\mathbf{x}}_k\|^2. \end{aligned}

The cross term is

-2\Bigl(\sum_{C(i)=k}(\mathbf{x}_i-\bar{\mathbf{x}}_k)\Bigr)^\top \Bigl(\sum_{C(l)=k}(\mathbf{x}_l-\bar{\mathbf{x}}_k)\Bigr)=0.

Therefore

W(C)=\sum_{k=1}^K N_k\sum_{C(i)=k}\|\mathbf{x}_i-\bar{\mathbf{x}}_k\|^2.

This writes the pairwise criterion as a size-weighted sum of squared distances to the cluster means. Each point is weighted by N_k. The algorithm of the next section does not descend on that weighted sum. It descends on the unweighted sum of squares

\widetilde W(C,\mathbf{m}_1,\ldots,\mathbf{m}_K) =\sum_{k=1}^K\sum_{C(i)=k}\|\mathbf{x}_i-\mathbf{m}_k\|^2.

At \mathbf{m}_k=\bar{\mathbf{x}}_k this is \tfrac12\sum_k N_k^{-1}\sum_{C(i)=C(l)=k}\|\mathbf{x}_i-\mathbf{x}_l\|^2. It is the criterion most software reports (tot.withinss in R). With the weights N_k of W(C), the reassignment step need not decrease the criterion, because moving a point changes two cluster sizes as well as two sums. The two statements agree as identities at the cluster means. The reassignment step is guaranteed to decrease only the unweighted sum. The worked example below reports both quantities.

Why the partitions are not all searched

Main article: Why the partitions are not all searched

Every partition has a value of W(C), so the minimum could in principle be found by enumeration. The number of ways to partition n observations into K non-empty unlabelled clusters is the Stirling number of the second kind,

S(n,K)=\frac{1}{K!}\sum_{k=1}^K(-1)^{K-k}\binom{K}{k}k^n.

For a very small sample, enumeration is possible. It rapidly becomes expensive: S(10,3)=9330, whereas S(25,5)=2436684974110751 and S(100,5)\approx 6.6\times 10^{67}. The limitation is computational size. Lloyd’s algorithm trades an exhaustive search for inexpensive alternating improvements, so a stable answer has to be distinguished from the best possible answer.

Used in

See also

Hartigan–Wong algorithm · Ward’s method · Lloyd’s K-means algorithm · Descent of Lloyd’s algorithm · Why the raw sum of squares cannot choose · K-means criterion · From pairs to cluster means · Why the partitions are not all searched

Glossary and index