Voronoi tessellation
Section of K-means clustering, part of Statistical learning
Voronoi tessellation
| Type | Section |
| Taught in | K-means clustering |
| Part | Statistical learning |
| Questions using it | 2 |
The assignment step gives every point to the nearest current centre, so the clusters are the cells of the Voronoi tessellation with those centres as seeds. The boundary between the cells of \mathbf{m}_a and \mathbf{m}_b is the set of points at equal squared distance from both. Expand the squared norms. The quadratic terms \|\mathbf{x}\|^2 cancel, which is special to squared Euclidean distance, and the boundary is linear:
\|\mathbf{x}-\mathbf{m}_a\|^2=\|\mathbf{x}-\mathbf{m}_b\|^2 \iff 2(\mathbf{m}_b-\mathbf{m}_a)^\top\mathbf{x}=\|\mathbf{m}_b\|^2-\|\mathbf{m}_a\|^2.
This is a hyperplane of dimension p-1, perpendicular to the segment joining the centres and passing through the midpoint of that segment. The cluster boundaries are pieces of hyperplanes in every dimension.
In the plane, three non-collinear centres have perpendicular bisectors meeting at their circumcentre. In \mathbb{R}^p with p>2, the points equidistant from all three instead form a (p-2)-dimensional affine set. Its intersection with the plane of the three centres is the circumcentre. A two-dimensional picture of three centres meeting at one point does not become, by itself, a claim about a higher-dimensional intersection.
The criterion does not specify a density. There is nothing to sample from the fitted partition, and this page gives no confidence interval or test for the centres. The cells just derived are convex and cut by hyperplanes, so the method is aimed at separated spherical clusters. Overlapping groups are separated by force, because each point is given wholly to one centre. A ring of points is a poor target for the same geometric reason: the cells cannot follow a hole.
Used in
- Taught in K-means clustering
- Also used in Mixtures and the EM algorithm
- Questions that use it (2) — What a K-means diagram must show (answer) · Euclidean clusters and mixture components (answer)
- All 8 questions on K-means clustering
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 · Why the partitions are not all searched · Initialising k-means