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 (). These methods often rely on replacing empty cell by splitting regions with high variance.