The Linde–Buzo–Gray algorithm (introduced by Yoseph Linde, Andrés Buzo and
Robert M. Gray in 1980) is a
vector quantization
Vector quantization (VQ) is a classical quantization technique from signal processing that allows the modeling of probability density functions by the distribution of prototype vectors. It was originally used for data compression. It works by di ...
algorithm to derive a good
codebook
A codebook is a type of document used for gathering and storing cryptography codes. Originally codebooks were often literally , but today codebook is a byword for the complete record of a series of codes, regardless of physical format.
Cryptog ...
.
It is similar to the
k-means
''k''-means clustering is a method of vector quantization, originally from signal processing, that aims to partition ''n'' observations into ''k'' clusters in which each observation belongs to the cluster with the nearest mean (cluster centers o ...
method in
data clustering
Cluster analysis or clustering is the task of grouping a set of objects in such a way that objects in the same group (called a cluster) are more similar (in some sense) to each other than to those in other groups (clusters). It is a main task of ...
.
The algorithm
At each iteration, each vector is split into two new vectors.
*A initial state: centroid of the training sequence;
*B initial estimation #1: code book of size 2;
*C final estimation after
LGA: Optimal code book with 2 vectors;
*D initial estimation #2: code book of size 4;
*E final estimation after
LGA: Optimal code book with 4 vectors;
References
* The original paper describing the algorithm, as an extension to
Lloyd's algorithm In electrical engineering and computer science, Lloyd's algorithm, also known as Voronoi iteration or relaxation, is an algorithm named after Stuart P. Lloyd for finding evenly spaced sets of points in subsets of Euclidean spaces and partitions of t ...
:
**
{{DEFAULTSORT:Linde-Buzo-Gray algorithm
Cluster analysis algorithms
Machine learning algorithms
Artificial neural networks