= Lloyd's algorithm
{c}
<Lloyd's algorithm> alternates two updates to reduce squared-distance distortion for a fixed number of centers: assign each data point to a nearest center, then replace each nonempty cluster's center by its <arithmetic mean>. For a probability distribution, the corresponding center is the <conditional expectation> on the assigned region. The scalar <quantization (signal processing)> problem was the motivation in <Stuart P. Lloyd>'s paper.<Least Squares Quantization in PCM by Stuart P. Lloyd>[Sections IV–VI, printed pages130–132, equations14 and17 and Quantization Procedures]{ref}
Write the objective as $J=\sum_i\|x_i-c_{a(i)}\|^2$, where $a(i)$ identifies the assigned center. With centers fixed, each point minimizes its own contribution by choosing a nearest center. For a nonempty cluster $C$, its <arithmetic mean> $\bar x_C$ satisfies
$$
\sum_{x\in C}\|x-c\|^2=\sum_{x\in C}\|x-\bar x_C\|^2+|C|\|c-\bar x_C\|^2.
$$
Thus the center update minimizes the contribution for fixed assignments. Both steps make $J$ nonincreasing, but this does not guarantee a global minimum.
An original example makes initialization matter. For the six scalar data points $0,1,4,5,9,10$, two initial centers $0,10$ give a boundary at $5$. Assign the tied value $5$ to the first center. The clusters become $\{0,1,4,5\}$ and $\{9,10\}$, with means $2.5,9.5$. Their new boundary is $6$, preserving the assignments, and $J=17.5$.
Instead initialize at $0,5$. The boundary $2.5$ gives clusters $\{0,1\}$ and $\{4,5,9,10\}$. Their means $0.5,7$ have boundary $3.75$, again preserving the assignments, but now $J=26.5$. This second fixed configuration cannot be globally optimal because the first is a better feasible configuration. Lloyd explicitly distinguishes stationary configurations from the absolute optimum.<Least Squares Quantization in PCM by Stuart P. Lloyd>[SectionVI and AppendixB: necessary conditions, saddle points and multiple minima]{ref}
An implementation must specify tie handling and what to do with empty clusters, whose <arithmetic means> are undefined. Objective decrease is a useful check; it does not certify discovery of a unique underlying grouping.
Back to article page
