K-means criterion
Section of K-means clustering, part of Statistical learning
K-means criterion
| Type | Section |
| Taught in | K-means clustering |
| Part | Statistical learning |
Give each of K centres a position, then assign each observation to its nearest centre. Now move each centre to the mean of its assigned observations. Those two operations are Lloyd’s algorithm. Squared Euclidean distance makes the mean the right update. The identity below explains why. The resulting cells are convex polyhedra, not necessarily spheres. The method tends to suit compact groups of comparable spread better than elongated groups or nested rings.
Distance decides how much each coordinate matters. Multiplying one variable by ten multiplies its contribution to squared distance by one hundred. Subtracting a constant changes nothing. Standardising to variance one gives each variable the same marginal scale, and that is a modelling choice, not a mathematical requirement. Variables measured in the same units can still deserve different weights. For iris, compare the scientific meaning of absolute centimetre differences with differences measured in standard deviations before choosing the metric.
A different dissimilarity defines a different optimisation problem and may require a different centre update. Absolute deviations, for example, lead to coordinatewise medians rather than means. The calculations here use squared Euclidean distance,
d(\mathbf{x}_i,\mathbf{x}_l)=\sum_{j=1}^p(x_{ij}-x_{lj})^2=\|\mathbf{x}_i-\mathbf{x}_l\|^2.
Used in
See also
Lloyd’s K-means algorithm · Descent of Lloyd’s algorithm · Why the raw sum of squares cannot choose · Within-cluster scatter · From pairs to cluster means · Why the partitions are not all searched · Initialising k-means · Choosing K: the gap statistic