Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
The enhanced LBG algorithm
Patané G., Russo M. Neural Networks14 (9):1219-1237,2001.Type:Article
Date Reviewed: Apr 2 2003

The vector quantization approach to clustering derives a set of representative or prototype points to represent the various clusters in a given collection of points. The points are, in general, vectors of a given length. Linde et al. [1] describe an algorithm, known as the generalized Lloyd algorithm or LBG algorithm, for identifying these prototype points (called codebook). The algorithm starts with a suitably initialized set of codewords. Viewing these as cluster centroids, the points are partitioned, and mean quantization error is computed, based on the distance of each point to the codeword of the partition in which it belongs. If the error is not acceptable, the codebook is revised, and the process is repeated.

The authors observe problems with this approach, in that codewords are not evenly distributed with regard to the density of points, and there may be empty partitions. To address these, this paper proposes a measure of the utility of a codeword, to capture these aspects, and revises the LBG algorithm by adding a stage in which some partitions are split or merged based on their utility values. A number of experimental results are reported, showing useful improvement in the final error, and in the number of iterations, as compared to LBG. Empirically, it has been shown that runtime overhead due to the revision is acceptably small.

Although the paper is generally well organized and fairly well written, I felt that the initial section could have done a better job of placing the current work in context. The usage of “D” was very confusing between the first and second half of the paper. Overall, this is a good paper.

Reviewer:  M Sasikumar Review #: CR127173 (0307-0697)
1) Linde, Y.; Buzo, A.; Gray, R. An algorithm for vector quantization design. IEEE Transactions on Communications 28, 1(1980), 84–94.
Bookmark and Share
  Featured Reviewer  
 
Clustering (I.5.3 )
 
 
Learning (I.2.6 )
 
Would you recommend this review?
yes
no
Other reviews under "Clustering": Date
On the convergence of “A self-supervised vowel recognition system”
Pathak A., Pal S. Pattern Recognition 20(2): 237-244, 1987. Type: Article
Aug 1 1988
Conceptual clustering of structured objects: a goal-oriented approach
Stepp R., Michalski R. (ed) Artificial Intelligence 28(1): 43-69, 1986. Type: Article
Sep 1 1986
Self-organizing map for clustering in the graph domain
Günter S., Bunke H. Pattern Recognition Letters 23(4): 405-417, 2002. Type: Article
Aug 4 2003
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy