k-means clustering

Builds on Cluster analysis Partition of a set Euclidean distance

Definition

Let $x_1, \ldots, x_n \in \R^d$ and let $1 \le k \le n$ . For a partition of $\set{1, \ldots, n}$ into non-empty sets $S_1, \ldots, S_k$ , let $m_j = \frac{1}{\abs{S_j}} \sum_{i \in S_j} x_i$ be the mean of cluster $j$ . The $k$ -means problem is to find a partition that minimises the within-cluster sum of squares $W(S_1, \ldots, S_k) = \sum_{j=1}^k \sum_{i \in S_j} \abs{x_i - m_j}^2,$ where $\abs{\cdot}$ is the Euclidean norm. $k$ -means clustering is the clustering given by a solution, or by an approximate solution, of this problem.

Remarks

Lloyd's algorithm starts from $k$ centres and repeats two steps: assign each $x_i$ to a nearest centre, then replace each centre by the mean of its assigned points. Neither step increases $W$ , and there are finitely many partitions, so the algorithm stops after finitely many steps, at a local minimum that need not be global. Example: for $0, 1, 10, 11 \in \R$ and $k = 2$ , the partition $\set{0, 1}, \set{10, 11}$ has means $0.5$ and $10.5$ and $W = 4 \cdot 0.25 = 1$ . Non-example: the partition $\set{0}, \set{1, 10, 11}$ has means $0$ and $22/3$ and $W = 546/9 \approx 60.7$ , so it is not a solution. The mean is used because, for fixed clusters, $m_j$ is the point $c$ that minimises $\sum_{i \in S_j} \abs{x_i - c}^2$ .

Reading path

To understand this page from the ground up, read these 4 pages in order. The foundations come first.

Show the path as a graph

Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.

no evidence level

Tag	`PNF97STBAW`
URI	`m2://PNF97STBAW`
Kind	definition
Writing	W0 stub
MSC	62H30
Defines	k-means clustering
Uses	Cluster analysis, Partition of a set, Euclidean distance

k-means clustering

Definition

Remarks

Reading path

Further reading

What this page needs for W1

What links here