Why the partitions are not all searched
Section of K-means clustering, part of Statistical learning
Why the partitions are not all searched
| Type | Section |
| Taught in | K-means clustering |
| Part | Statistical learning |
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
Lloyd’s K-means algorithm · Descent of Lloyd’s algorithm · Why the raw sum of squares cannot choose · K-means criterion · Within-cluster scatter · From pairs to cluster means · Initialising k-means · Choosing K: the gap statistic