矢量量化和K-means算法

矢量量化和K-means算法

矢量量化（VQ —Vector Quantization）论文翻译网站推荐：彩云小译 是70年代后期发展起来的一种数据压缩技术基本思想：**将若干个标量数据组构成一个矢量，然后在矢量空间给以整体量化，**从而压缩了数据而不损失多少信息矢量量化编码也是在图像、语音信号编码技术中研究得较多的新型量化编码方法，它的出现并不仅仅是作为量化器设计而提出的，更多的是将它作为压缩编码方法来研究的。在传统的预测和变换编码中，首先将信号经某种映射变换变成一个数的序列，然后对其一个一个地进行标量量化编码。而在矢量量化编码中，则是把输入数据几个一组地分成许多组，成组地量化编码，即将这些数看成一个k维矢量，然后以矢量为单位逐个矢量进行量化。矢量量化是一种限失真编码，其原理仍可用信息论中的率失真函数理论来分析。而率失真理论指出，即使对无记忆信源，矢量量化编码也总是优于标量量化。

在矢量量化编码中，关键是码本的建立和码字搜索算法。 码本的生成算法有两种类型，一种是已知信源分布特性的设计算法；另一种是未知信源分布，但已知信源的一列具有代表性且足够长的样点集合（即训练序列）的设计算法。可以证明，当信源是矢量平衡且遍历时，若训练序列充分长则两种算法是等价的。 码字搜索是矢量量化中的一个最基本问题，矢量量化过程本身实际上就是一个搜索过程，即搜索出与输入最为匹配的码矢。矢量量化中最常用的搜索方法是全搜索算法和树搜索算法。全搜索算法与码本生成算法是基本相同的，在给定速率下其复杂度随矢量维数K以指数形式增长，全搜索矢量量化器性能好但设备较复杂。树搜索算法又有二叉树和多叉树之分，它们的原理是相同的，但后者的计算量和存储量都比前者大，性能比前者好。树搜索的过程是逐步求近似的过程，中间的码字是起指引路线的作用，其复杂度比全搜索算法显著减少，搜索速度较快。由于树搜索并不是从整个码本中寻找最小失真的码字，因此它的量化器并不是最佳的，其量化信噪比低于全搜索。

VectorQuantization (VQ)是一种基于块编码规则的有损数据压缩方法。事实上，在 JPEG 和 MPEG-4 等多媒体压缩格式里都有 VQ 这一步。它的基本思想是：将若干个标量数据组构成一个矢量，然后在矢量空间给以整体量化，从而压缩了数据而不损失多少信息。 在以前，VQ运用的一个难点在于它要要解决一个多维积分（multi-dimensional integration）的问题。后来，在1980年，Linde, Buzo和Gray（LBG，这个缩写也是LBG算法的命名）提出一种基于训练序列的VQ设计算法，对训练序列的运用绕开了多维积分的求解，使得世上又诞生了一种经典的被世人称为LBG-VQ的算法！它一直延绵至今，经典永不褪色

举一个例子

在这里，我们用蓝色实线将这张图划分为16个区域。任意的一对数（也就是横轴x和纵轴y组成的任意的一个坐标点(x, y)）都会落到上面这张图中的某一特定区域。然后它就会被该区域的红星的点近似。这里有16块不同区域，就是16个红星点。然后这16个值就可以用4位的二进制码来编码表示（2^4=16）。因此，这是个2-dimensional, 4-bit VQ，它的速率同样是2bits/dimension。上面这些红星点就是量化矢量，表示图中的任意一个点都可以量化为这16个矢量中的其中一个。

对于二维，我们还可以用图像压缩来说明。类似于将图像的每个像素点当作一个数据，跑一下 K-means 聚类，假设将图像聚为k类，就会得到每类的质心centroids，共k个，然后用这些质心的像素值来代替对应的类里的所有点的像素值。这样就起到压缩的目的了，因为只需要编码k个像素值（和图像每个像素点的对这k个值得索引）就可以表示整张图像了。当然，这会存在失真了，失真的程度就是k的个数了。最偏激的就是原图像每个像素就是一个类，那就没有失真了，当然这也没有了压缩。 以上的两个例子，红星被称为码矢（codevectors）。而由蓝色边定义的区域叫做编码区域（encoding regions）。所有码矢的集合称为码书（codebook），所有编码区域的集合称为空间的划分（partition of thespace）。

VQ设计问题 VQ问题可以这样描述：给定一个已知统计属性的矢量源（也就是训练样本集，每一个样本是一个矢量）和一个失真测度。还给定了码矢的数量（也就是我们要把这个矢量空间划分为多少部分，或者说量化为多少种值），然后寻找一个具有最小平均失真度（数据压缩，肯定是失真越小越好）的码书（所有码矢的集合，也就是上面的那些所有红色星星点）和空间的划分（图中所有蓝色线的集合）。

假定我们有一个有M个矢量源（训练样本）的训练序列（训练集）：T={x1, x2,…, xM}；

这个训练序列可以通过一些大数据库得到。例如如果这个矢量源是语音的话，那么我们就可以对一些电话录音裁剪得到。我们假设M足够大（训练样本足够多），这样才可以保证这个训练序列包含了源的所有统计特性。我们假设源矢量是k维的：

假设码矢的数目是N（也就是我们要把这个矢量空间划分为N个部分，或者说量化为N种值），码书（所有码矢的集合）表示为：C={c1, c2,…, cN}；

每一个码矢是个k维向量：cn=(cn,1, cn,2, …, cn,k),n=1,2,…,N；

与码矢cn对应的编码区域表示为Sn，然后将空间的划分表示为：P={S1, S2,…,SN}；如果源矢量xm在Sn内，那么它的近似（用Q(xm)表示）就是cn， Q(xm)=cn, 如果xm 属于Sn假设我们采用均分误差失真度量，那么平均失真度表示如下：

这里||e||2为欧式距离。 那么设计问题就可以简单的描述为：给定T（训练集）和N（码矢数目），找到能使Dave（平均失真度）最小的C（码书）和P（空间划分）。

四、优化准则

如果C和P是上面这个最小化问题的一个解，那么这个解需要满足以下两个条件：

1）Nearest NeighborCondition 最近邻条件：

这个条件的意思是编码区域Sn应该包含所有与cn最接近的矢量（相比于与其他码矢的距离）。对于在边界（蓝色线）上面的矢量，需要采用一些决策方法（any tie-breaking procedure）。

2）Centroid Condition质心条件：

LBG-VQ算法是一个迭代算法，它交替地调整P和C（解上面这两个优化准则），使失真度不断地趋向于它的局部最小值（有点EM的思想哦）。这个算法需要一个初始的码书C(0)。这个初始码书可以通过分裂（splitting）方法得到。这个方法主要是把一个初始码矢设置为所有训练样本的平均值。然后把这个码矢分裂成两个（分裂的方式见下面的LBG算法的第3步的公式，只要是乘以一个扰乱系数）。把这两个码矢作为初始的码书，然后迭代算法就在这个初始的码书上面跑。它每一次都将每个码矢分裂为2个，重复这个过程，直到获得要求的码矢个数。1个分裂为2个，2个分裂为4个，4个分裂为8个……

LBG算法：

1、给定训练集T。固定ɛ（失真阈值）为一个很小的正数。

2、让N=1（码矢数量），将这一个码矢设置为所有训练样本的平均值：

计算总失真度（这时候的总失真很明显是最大的）

3、分裂：对i=1,2,…,N，他们的码矢分别为

让N=2N，就是每个码矢分裂（乘以扰乱系数1+ɛ和1-ɛ）为两个，这种每一次分裂后的码矢数量就是前一次的两倍

4、迭代：让初始失真度为：

。将迭代索引或者迭代计数器置零i=0.

1）对于训练集T中的每一个训练样本m=1,2,…,M。在所有码矢中寻找

的最小值，也就是看这个训练样本和哪个码矢距离最近。我们用n*记录这个最小值的索引。然后用这个码矢来近似这个训练样本：

2）对于n=1,2,…,N，通过以下方式更新所有码矢：

也就是将所有属于cn所在的编码区域Sn的训练样本取平均作为这个编码区域的新的码矢。

3）迭代计数器加1：i=i+1.

4）计算在现阶段的C和P基础上的总失真度：

6）否则最终失真度为

。对n=1,2,…,N，最终码矢为：

1）训练样本集是由零均值和单位方差的高斯分布产生。

2）小的绿色的点就是这些训练样本。有4096个。

3）我们把阈值设置为ɛ=0.001。

4）这个算法会保证得到一个局部最小解。 5、重复步骤3和4至到码矢的数目达到要求的个数。

参考：​​参考来源​​​​参考​​

1. 算法描述 本次实验选择了K-means算法对数据进行矢量量化。算法主要包括以下几个步骤

（1）初始化：载入训练数据，确定初始码本中心（4个）； （2）最近邻分类：对训练数据计算距离（此处采用欧式距离），按照距离最小分类； （3）码本更新：重新生成包腔对应的质心； （4）重复分类和码本更新步骤，知道达到最大迭代次数或满足一定停止准则； （5）利用上述步骤得到的码本对测试数据进行矢量量化，并求最小均方误差。 本实验准备使用MATLAB软件完成矢量量化任务，具体步骤实现如下

将training.dat和to_be_quantized.dat置于当前工作文件夹内，采用load命令载入training.dat 。

采用合适的规则选取初始的码本中心。如图 1所示。

1、计算训练数据和每一码本中心之间的距离。

2、采用最近邻准则进行分类。

3、重新计算质心，计算公式如下所示。

4、重复3～5，直到满足最大迭代次数或是两次迭代结果没有发生改变时，此时结果为训练结果。 5、利用训练结果对to_be_quantized.dat进行矢量量化。

2. 代码 MATLAB代码如下：​​​代码​​

3. 实验结果

图 2展示了训练数据的分布，图 3～6是迭代过程中分类的变化情况，迭代完成后的码本为

Z1 = [1.62060631541935 -0.108624145483871] Z2 = [7.96065094375000 -0.999061308437500] Z3 = [1.72161941468750 6.82121444062500] Z4 = [4.43652765757576 2.18874305151515]

4. 实验数据 training.dat

1 8.4416189e+000 -7.9885975e-001 2 1.1480908e+000 7.8735044e+000 3 7.7380144e+000 -1.2165061e+000 4 8.9727144e-001 7.3962468e+000 5 7.5343823e+000 -1.1424504e+000 6 -6.9234039e-001 -1.7096610e+000 7 7.6418740e+000 -1.3563792e+000 8 3.1091418e+000 6.3850541e+000 9 2.3482174e+000 4.7553506e-001 10 -1.3840364e+000 -2.5480394e+000 11 8.2008897e+000 -1.1448387e+000 12 -1.1392497e+000 -2.0809884e+000 13 3.7970116e+000 1.6906469e+000 14 3.4484200e+000 1.3980911e+000 15 2.5701485e+000 5.3755044e+000 16 8.3899076e+000 -6.6675309e-001 17 2.0146545e+000 5.6984592e+000 18 1.8853328e+000 5.2762628e-001 19 5.6781432e+000 3.2588691e+000 20 1.0102480e+000 5.8167707e+000 21 7.7302763e+000 -1.2030348e+000 22 4.2118845e+000 1.6527181e+000 23 4.3920049e-001 6.7168970e+000 24 8.1934984e-001 -5.1917945e-001 25 4.3708769e+000 2.1613573e+000 26 1.8569681e+000 4.8380565e+000 27 3.4732504e+000 1.7953635e+000 28 7.5822756e+000 -1.1521814e+000 29 2.6434078e+000 6.3295690e+000 30 1.9968582e+000 7.3529314e+000 31 4.0833513e+000 1.4936002e+000 32 3.6767894e+000 6.7446912e+000 33 1.3524515e+000 6.8177858e+000 34 3.9711504e+000 1.5452503e+000 35 1.5594711e+000 6.3885281e+000 36 3.4692089e+000 1.7118124e+000 37 5.2575491e+000 2.5601553e+000 38 7.8827882e+000 -6.8867840e-001 39 4.8176593e+000 2.1684005e+000 40 2.7402486e+000 8.3320174e+000 41 2.2549011e+000 3.9393641e-001 42 8.0840542e+000 -7.3155184e-001 43 8.8753667e-001 6.1607892e+000 44 1.8067727e+000 -2.1099454e-001 45 6.8650914e+000 4.4228389e+000 46 6.4174056e+000 3.7590081e+000 47 4.0933273e+000 1.3598676e+000 48 2.2882999e+000 5.1876795e-001 49 7.9225523e+000 -1.1725456e+000 50 4.3561335e+000 1.8976163e+000 51 8.3279098e+000 -1.0232899e+000 52 6.2551331e+000 3.3449949e+000 53 3.1276024e+000 7.8463356e-001 54 6.5241605e+000 3.4561490e+000 55 4.1588140e-001 6.4974858e+000 56 2.7379263e+000 6.4746080e+000 57 7.2185639e+000 -1.3525589e+000 58 7.5424890e+000 -1.5317814e+000 59 3.7468423e+000 1.6110753e+000 60 8.8708536e+000 -5.6439331e-001 61 7.6960713e+000 -1.1960633e+000 62 7.5979552e+000 -1.1469059e+000 63 2.8220978e+000 1.0360184e+000 64 3.8165165e+000 1.6082223e+000 65 6.6799248e-002 -1.2910367e+000 66 2.3054028e+000 2.8450986e-001 67 4.2788715e+000 5.1995858e+000 68 3.0006534e+000 9.1250414e-001 69 7.6051326e+000 -1.1005476e+000 70 2.5331653e+000 9.7428007e-001 71 1.0743104e+000 6.0859296e+000 72 6.7237149e-001 8.6117274e+000 73 2.4333003e+000 7.1421389e-001 74 1.7723473e+000 7.1841833e+000 75 3.5762796e+000 1.5348648e+000 76 2.7863558e+000 7.3565043e-001 77 8.0284284e+000 -7.9636983e-001 78 8.4672682e+000 -8.2062254e-001 79 2.3519727e+000 8.1632796e-001 80 7.4240720e+000 4.1800229e+000 81 1.9724319e+000 4.4328699e-001 82 7.7622621e+000 -1.3506605e+000 83 2.3793018e+000 -4.3107386e-001 84 3.2455220e+000 1.2697488e+000 85 1.3644859e+000 5.9712644e+000 86 5.4815655e+000 2.6608754e+000 87 -1.2002073e+000 -2.1765731e+000 88 -3.5558595e-001 6.4387512e+000 89 3.9418185e+000 1.9858047e+000 90 1.0533626e+000 -7.9068285e-001 91 1.9560213e+000 6.2001316e+000 92 7.5555203e+000 -1.2087337e+000 93 1.7851705e+000 7.0073148e+000 94 2.2736274e+000 7.9336349e-001 95 7.6615799e+000 -1.0445564e+000 96 2.7181608e+000 4.7615418e-001 97 1.8291149e+000 -6.7261971e-001 98 7.8640867e+000 -1.4296092e+000 99 2.6362814e+000 5.8303048e-001 100 3.7771102e+000 1.2928196e+000 101 7.5360359e+000 -9.7942712e-001 102 4.0257498e+000 1.2217666e+000 103 8.4500853e+000 -7.6599648e-001 104 3.0488646e+000 6.2159289e+000 105 2.0954150e+000 2.5848825e-001 106 1.6592148e+000 7.5650162e+000 107 3.5535363e+000 1.3326217e+000 108 4.3388636e+000 2.1235893e+000 109 3.1233524e+000 1.3971470e+000 110 7.6317385e+000 -1.0744610e+000 111 8.5028402e-001 -3.2822876e-001 112 8.6903131e+000 -2.6843242e-001 113 4.4418011e+000 2.5676053e+000 114 2.5119872e+000 -1.0521242e-001 115 1.9613752e+000 7.0072931e+000 116 3.2607143e+000 1.5432286e+000 117 3.2830401e+000 1.0228031e+000 118 8.0201528e+000 -7.0827461e-001 119 3.1597313e+000 7.6750043e+000 120 9.0059933e+000 -9.6130246e-001 121 1.1037820e+000 -1.2980812e-001 122 1.5334911e+000 7.4282719e+000 123 6.0948533e-001 6.3861341e+000 124 4.0065706e-001 -1.1015776e+000 125 2.3451558e+000 8.6384057e+000 126 1.4490876e+000 8.6646066e+000 127 8.0421821e+000 -8.1100509e-001 128 8.0175747e+000 -5.6119093e-001 View Code to_be_quantized

1 3.7682247e+000 8.3609865e-001 2 2.6963398e+000 6.5766226e-001 3 3.3438207e+000 1.2495321e+000 4 1.3646195e+000 -6.3947640e-001 5 7.8227583e+000 -8.8616996e-001 6 1.3532508e+000 7.6607304e+000 7 2.2741739e+000 6.9387226e+000 8 3.5361382e+000 5.9729821e+000 9 8.0409138e+000 -1.1234886e+000 10 7.9630460e+000 -1.3032200e+000 11 2.3478158e+000 6.9759690e+000 12 3.2632942e+000 1.5675470e+000 13 1.5241488e+000 7.1053147e+000 14 5.7320838e+000 3.4042655e+000 15 2.3339411e+000 6.9428434e+000 16 6.5330392e+000 3.4415860e+000 17 3.1068803e+000 8.0080363e+000 18 7.4078126e+000 -1.3416027e+000 19 1.9925474e+000 -2.7782790e-001 20 5.0187915e+000 2.7058427e+000 21 2.6535497e-001 -1.2622069e+000 22 1.4960584e+000 6.3355004e+000 23 3.1933474e-001 7.1467466e+000 24 8.2821020e+000 -9.5178778e-001 25 2.5653586e+000 6.9836115e+000 26 3.6937139e+000 1.1535671e+000 27 8.5390043e+000 -5.0678923e-001 28 7.5436898e-001 -6.7669379e-001 29 2.1638213e+000 7.6142401e+000 30 4.8522826e+000 2.7079076e+000 31 5.4890641e+000 3.3875394e+000 32 4.2525899e+000 1.8861744e+000 33 8.4088615e+000 -1.1920963e+000 34 5.5396960e+000 2.9680110e+000 35 3.3334381e+000 1.4384861e+000 36 3.5212919e+000 1.0327602e+000 37 4.6303492e+000 2.1627805e+000 38 3.9385929e+000 1.0010804e+000 39 8.4553633e+000 -7.2297277e-001 40 1.8111095e+000 7.6132396e+000 41 1.1240984e+000 -2.7029879e-001 42 -3.3840083e-002 -1.5590834e+000 43 7.1674870e+000 -1.5449905e+000 44 8.5103026e+000 -9.8820393e-001 45 7.7529857e+000 -1.4787432e+000 46 1.8704913e+000 6.9370116e+000 47 6.0271939e+000 3.2118915e+000 48 2.8287461e+000 7.3399383e+000 49 4.1568876e+000 1.5631238e+000 50 8.2187067e-001 -5.8546437e-001 51 3.1084965e+000 5.3512449e+000 52 4.1581386e+000 2.1763345e+000 53 3.2267474e+000 1.4105815e+000 54 8.1564752e-001 7.2540175e+000 55 8.0241402e+000 -8.2411742e-001 56 6.2773554e+000 3.1729045e+000 57 8.5460058e+000 -1.0330056e+000 58 8.6215210e+000 -7.4057378e-001 59 7.4872291e+000 -1.0113921e+000 60 3.3155133e+000 9.7636038e-001 61 2.1051593e+000 3.4894654e-001 62 3.6776134e+000 1.5387928e+000 63 2.9009105e+000 5.6931589e+000 64 8.0567164e+000 -1.0000803e+000

​​参考连接​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。