LBG算法、Lloyd算法和K均值算法

---------------------------------LBG算法、Lloyd算法和K-Means算法---------------------------------

LBG算法是一种矢量量化算法，由Lloyd算法推广而来。在编码过程中，我们可以先对信源输出进行分组，再将每个组看做一个整体块进行编码，这样可以得到高效的有损或无损压缩算法。其实量化过程同样可以这么做，我们将数据块视为矢量，所以这类量化称为矢量量化。较之通常的标量量化，使用矢量量化所得失真度将更低，其原因是：

1.由于信源输出之间的相关性结构，研究整个信源输出序列要比分别研究每个样本更为高效。

2.即使信源输出不相关，矢量量化也比标量量化更高效，因为随着研究的信源序列的长度增加，设计算法就会更加灵活，可以与信源的统计特性更匹配。

LBG算法由Lloyd算法推广而来，而Lloyd算法由源于K均值算法聚类方法。所以我们从K均值算法开始一步步来介绍。

1.K-Means算法

K-means算法主要用于对数据聚类。

如上左图所示，我们很容易看出图中的点分成上右图中的了4个点群，而K-Means算法能让计算机也可以知道这件事。

K-Means算法原理如下（避免截图，没有使用公式- -！）：

1. 随机在图中任取K个点为种子点；

2. 计算图中所有点到这K个种子点的距离，设图中原有点位q1-qn，这K个种子点为n1-nK，如果qi离ni点最近，那么令qi属于ni点群；

3. 通过第二步，我们得到了K个点群，每个点群包含一定数量的原有点和本身的一个种子点（这些点离该点群的种子点的距离比离其他种子点都近）；

4. 逐个计算上述K个点群的质心，并将属于自己点群的那个种子点移动到该位置；

5. 重复2-4步，直到所有种子点不再移动。

K-means算法原理很简单，仅仅用到了一个求距离的公式和一个求中心点的公式（比如计算所有点的x和y坐标的均值）。

然后是Lloyd算法。

2.Lloyd算法

Lloyd算法工作方式：

然后转到第2步。

Linde、Buzo和Gray将该算法推广到输入为矢量的情形，这就是LBG算法，亦称为广义Lloyd算法。

3. LBG算法

LBG算法的大致步骤为：

可以看到LBG算法与K-Means算法非常类似，同样是一步步迭代，失真度定义为了一个与距离相关的量，然后当失真度相对变化程度小于一个阈值时停止。它将K-Means算法推广到了矢量领域。

同时可以看出LBG算法也存在一定的问题，比如：

1.其计算复杂度相比于K均值算法大大增加。虽然LBG算法可以保证某次迭代的失真不会大于上一次的失真，但并不能保证收敛到确定的最优点。

2.LBG算法非常依赖于训练集的真实程度，而非常具有代表性的训练集并不容易找到，所以当没有训练集时并不是很实用。而且算法是当新的码矢量与原码矢量变化不大时，就停止码书的训练，但这并不能保证这时就是最优的情况。