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]
Least Squares Quantization in PCM by Stuart P. Lloyd. Sections IV–VI, printed pages130–132, equations14 and17 and Quantization Procedures
Write the objective as , where identifies the assigned center. With centers fixed, each point minimizes its own contribution by choosing a nearest center. For a nonempty cluster , its arithmetic mean satisfiesThus the center update minimizes the contribution for fixed assignments. Both steps make nonincreasing, but this does not guarantee a global minimum.
An original example makes initialization matter. For the six scalar data points , two initial centers give a boundary at . Assign the tied value to the first center. The clusters become and , with means . Their new boundary is , preserving the assignments, and .
Instead initialize at . The boundary gives clusters and . Their means have boundary , again preserving the assignments, but now . 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]
Least Squares Quantization in PCM by Stuart P. Lloyd. SectionVI and AppendixB: necessary conditions, saddle points and multiple minima
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.
Articles by others on the same topic
Lloyd's algorithm is a popular iterative method used for quantization and clustering, particularly in the context of k-means clustering. It is often employed to partition a dataset into \( k \) clusters by minimizing the variance within each cluster. Here is a summary of the steps involved in Lloyd's algorithm: 1. **Initialization**: Begin by selecting \( k \) initial cluster centroids. These can be chosen randomly from the dataset or via other methods.