Lloyd's Method

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.

Steps 1-3 are repeated until the solution no longer changes significantly.

 

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