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:

**1**- Find the nearest centroid for all points breaking up the points into cells.
**2**- Recalculate the centroids for each cell.
**3**- Remove any empty cells.

ref
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.
Figure 1 |

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.

6/7/2002