What is the difference between clustering and quantization?

Question

The Lloyd-Max quantizer is a scalar quantizer which can be seen as a special case of a vector quantizer (VQ) designed with the Linde Buzo Gray (LBG) algorithm.

In k-means clustering, we are given a set of n data points in d-dimensional space and an integer k and the problem is to determine a set of k points in $R^d$, called centers, so as to minimize the mean squared distance from each data point to its nearest center. A popular heuristic for k-means clustering is Lloyd's (1982) algorithm.

Confusion :

1. What is the difference between clustering and quantization. I understand the mechanism of clustering technique which is a unsupervised method of grouping data points whereby we map data points into indices of cluster centers which is closest to it. There are different algorithm to perform clustering - Is clustering another way of doing quantization? Quantization are of 2 kinds -scalar and vector. k-means algorithm is applied for vector quantization. Again k-means algorithm is also applied in vector clustering. So, is vector quantization = vector clustering?

   Thank you.

Answer 1

They are essentially the same. The generalized form of the Lloyd's algorithm is LBG which is used for vector quantization (VQ).You may use k-means for the purpose of vector quantization just like the LBG algorithm. In vector quantization, the input space is partitioned into a set of convex areas. They are also referred to as Voronoi regions or cells. If you look at here it says k-means (which is mostly used in computer science) is actually originated from VQ in signal processing as well as pulse code modulation back in fifties.

If you want to implement VQ, you may directly use k-means algorithm. The original LBG algorithm is presented in the following paper if you are interested:

Y. Linde, A. Buzo, and R. M. Gray, ``An Algorithm for Vector Quantizer Design,'' IEEE Transactions on Communications, pp. 702--710, January 1980.

Answer 2

Quantization and clustering both aim at representing samples in groups, groups indexed by one single representative template, according to some proximity metric. The difference in their acceptation mostly resides in the historical use of the terms, and on the field of application.

Indeed, one of the early papers in Hugo Steinhaus' 1956 article: Sur la division des corps matériels en parties (more historical details in blog post Hugo Steinhaus, or K-means clustering in French).

Later, an history of K-means can be found in Data Clustering: 50 Years Beyond K-Means, Anil K. Jain, Pattern recognition letters, 2010. Other historic bits can be found in Origins and extensions of the k-means algorithm in cluster analysis, Hans-Hermann Bock, Electronic Journ@l for History of Probability and Statistics, 2008. This algorithm is deeply linked to Lloyd-Max algorithm, developed by Lloyd in 1957, and rediscovered by Max three after after. It is useful for optimal scalar quantifier design.