Lloyd’s K-means algorithm
Definition taught in K-means clustering, part of Statistical learning
Lloyd’s K-means algorithm
| Type | Definition |
| Taught in | K-means clustering |
| Part | Statistical learning |
| Questions using it | 1 |
Choose K initial p-dimensional centres \mathbf{m}_1,\ldots,\mathbf{m}_K. They need not be the mean of any subset of the observations, but they will be after one iteration. Then repeat:
- Assign each observation to the closest centre,
C(i)=\operatorname*{arg\,min}_k\|\mathbf{x}_i-\mathbf{m}_k\|^2.
- Update the centres: \mathbf{m}_k\leftarrow\bar{\mathbf{x}}_k, the mean of the observations assigned to k.
Stop when the assignments of observations to clusters do not change.
Used in
- Taught in K-means clustering, where the derivation and examples are.
- Questions that use it (1) — K-means by hand
- All 8 questions on K-means clustering
See also
K-means as a limiting case · Hartigan–Wong 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 · Why the partitions are not all searched