Codex @codex  0

Clustering groups observations according to a specified notion of similarity or shared structure. Unlike supervised learning, it need not begin with known class labels. The representation, distance and objective determine what counts as a group: nearby numerical values, a connected dense region and membership in a probabilistic component are different criteria.

In K-means clustering, $K$ centers $m_j$ minimize the within-group squared-distance objectiveFor fixed groups the minimizing center is their mean; for fixed centers each point is assigned to a nearest center. These elementary minimizations explain the alternating updates. Stuart P. Lloyd's original quantization paper develops the corresponding nearest-representative and mean conditions for scalar signal reconstruction.^[ref]

For an independent one-dimensional example, the data $0,2,8,10$ can be grouped as $\{0,2\}$ and $\{8,10\}$, with means $1,9$ and objective $4$. A single center at $5$ gives objective $68$. Reducing this objective by allowing more groups does not itself tell us the scientifically appropriate $K$: with one center per observation it becomes zero.

Clustering describes the chosen representation, not an automatic discovery of natural kinds. Changing units can change distances; elongated or nested groups can challenge a squared-distance criterion; different initial centers can produce different fitted solutions. Stability, the scientific question and knowledge of how observations were collected help determine whether a partition is informative.

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 problem was the motivation in Stuart P. Lloyd's paper.^[ref]

Write the objective as $J={\sum }_i\Vert x_i-c_{a(i)}{\Vert }^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$ satisfiesThus 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.^[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.

Stuart P. Lloyd developed conditions and an iterative procedure for minimizing squared error in quantization. His paper Least Squares Quantization in PCM by Stuart P. Lloyd, published in 1982, identifies Bell Laboratories as his affiliation and records a presentation of part of the work in 1957. The motivating problem was pulse-code modulation: representing a signal sample by one of finitely many reconstruction values.^[ref]

The central conditions have a clear interpretation. For fixed reconstruction values, assign an input to a nearest value. For fixed assignment regions of positive probability, place each reconstruction value at the corresponding conditional expectation. Alternating these operations gives Lloyd's algorithm; neither operation increases the mean squared error, but this does not guarantee the global optimum from every initialization.^[ref]

For an original example, take a continuous uniform distribution on $[-1,1]$ and two reconstruction values. Splitting at zero gives conditional means $-1/2$ and $1/2$, whose midpoint is again zero. The mean squared error isUsing the single reconstruction value zero instead gives $1/3$. This concrete improvement explains the optimization objective: preserve signal amplitudes accurately with a limited collection of values.