From pairs to cluster means

Section of K-means clustering, part of Statistical learning

Type	Section
Taught in	K-means clustering
Part	Statistical learning

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.

Used in

Taught in K-means clustering
All 8 questions on K-means clustering

Used in

See also