Lloyd's method attempts to find the best codebook by a simple iterative procedure. Lloyd's method starts from a given initial codebook, then it follows a fairly simple algorithm:
Figure 1 In step 1, the data is dividing into cells. In step2, the centroid of each cell is calculated. In the third step new cell boundaries are calculated between the centroids. If a cell contains no points, the cell is removed.
Lloyd's method can be effective but relies on a good initial
codebook and can get stuck in local minima. To avoid prejudicing the solution
the initial model is often a random set of vectors. To solve the second
problem, several methods have been developed Linde et al. (1980).
These methods often rely on replacing empty cell by
splitting regions with high variance.