3-5 ?煾??誩?

Old Chinese version
向量量化（vector quantization）可以說是近年來在降低資料量上最常被提出討論的方法之一，尤其是在傳統資料壓縮的領域上，向量量化更是不可缺乏的一環。
在整個向量量化的過程中，最重要的工作便是編碼表（codebook）的設計。所謂編碼表，指的是一群編碼向量（codevector 或 codeword）的集合，而我們最終的目標，便是以這些挑選出來的編碼向量來代表該空間中全部的資料向量。
舉例來說，如下圖所示，在一個二維的空間中，我們將整個空間分割成若干等分，每個等分以一個編碼向量（黑點）來代表，如此一來，空間中全部的向量都可以只這些有限的編碼向量來代替，這便是向量量化的精神所在。圖5-2-4.a：二維空間上的向量量化範例
假設x是D維空間中的向量，在圖形辨識流程中，x可能就代表某種特徵字串（feature string），例如在影像處理中可能是DCT係數，在語音辨識中可能是LPC（linear prediction coefficient），我們希望透過某種對應方式Q，將全部的x對應到同樣是D維空間中有限的編碼向量yi上，而yi的數目，便稱為該編碼表的大小。
從直觀上來看，對應Q的目的當然是希望向量x對應到yi後的失真（distortion） d（x, yi）能越低越好。而d（x, yi）可以各式各樣的距離估測或是失真估測方式，例如平方差（square error）。
最基本的向量量化演算法應該要算是1980年Y. Linde, A. Buzo, 和R. Gray共同提出的向量量化演算法 [25]，後來人們就將該演算法稱為LBG演算法。LBG演算法在本質上採用了k-means分群法 [1]，根據預期的編碼表大小（假設是k），將所有的訓練向量（training vector）分為k群，而各群的群中心便成為代表各群的編碼向量。
之後，各種改良的向量量化演算法不斷被提出來 [21] [9]，基本上都採用一種樹狀的分類方式，整個向量量化的過程可以簡化成以下幾個步驟：

將全部的訓練向量歸成一群。
挑選某種分割特徵，將每個樹狀結構最底層的群聚分割成兩部分，並進行k-means 分群法。至於分割的方式，可以由原中心點開始，選擇沿主要分量（principal component）的方向，各取左右兩點，當作 k-means 的啟始中心點。
假如最底層的群聚數目仍然小於預期的編碼表大小，則回到步驟二。
計算樹狀結構最底層每個群聚的群中心，即為代表各群的編碼向量。
在步驟二中的分割特徵，則根據不同的應用及不同的演算法而有所不同，例如在影像處理中，便可能是擁有最大變異量的DCT係數 [3] ，亦或是採用主要分量分析法（principal component analysis）找出較為重要的投影特徵 [26]。
Data Clustering and Pattern Recognition (資料分群與樣式辨認)