---
tag: D5PN3G41D6
kind: concept
name: k-means clustering
msc: [62H30]
specializes: [D9Y3A9RH6J]
sources:
  - url: https://en.wikipedia.org/wiki/K-means_clustering
same_as:
  wikidata: Q310401
  wikipedia: K-means clustering
---

## Summary

$k$-means clustering splits points of $\R^d$ into $k$ groups.
It makes the sum of squared distances from each point to the mean of its group as small as possible.
It is one of the most widely used methods of [[cluster analysis|D9Y3A9RH6J]].
Finding the exact optimum is computationally hard in general, so it is approximated by Lloyd's algorithm, which alternates between assigning points and updating means.
The method works best for compact, roughly round clusters of similar size.

## Explanations

### L1 human

Choose $k$ starting centres.
Give each point to its nearest centre, then move each centre to the average of the points it received.
Repeat until nothing changes.
For the points $0, 1, 10, 11$, $k = 2$ and the starting centres $0$ and $1$, the method ends with the groups $\set{0, 1}$ and $\set{10, 11}$, with centres $0.5$ and $10.5$.