5-3 Learning Vector Quantization (學習式向量量化)

[chinese][english] Learning vector quantization (LVQ) combines the concepts of vector quantization and nearest-neighbor classification to update the cluster centers for better recognition rates. More specifically, LVQ updates the cluster centers in an incremental manner, such that the updated centers can lead to a better accuracy of recognition, as follows:

1. Set repesentative centers for each class. Suppose that we have 3 clusters for a 4-class problem, then the number of centers are 12 in total. These cluster centers can be obtained by k-means clustering over each individual class. (In practice, the number of clusters for each class can be set to be proportional to the size of the class.)
2. For each data point x, find the nearest centers y_k. Based on the class labels of x and y_k, update centers as follows:
   • If the class labels are the same, then move y_k toward x: y_k = y_k + α [x - y_k]
   • If the class labels are different, then move y_i away from x: y_k = y_k - α [x - y_k]
3. Update the learning rate α.
4. Back to step 2 until all the centers converge.

Note that the learning rate α is decreased with each iteration, with 0<α<1.

學習式向量量化（learning vector quantization）簡稱 LVQ，此方法是透過自動學習的演進過程，進行即時的微調，使各個類別的代表點趨近最佳值，可說明如下：

1. 設定每一個類別的代表點。假設共有四個類別，每一個類別有三個代表點，那就共有 12 個代表點。每個類別的代表點，可由此類別的資料來進行 k-means 分群法而得到，這方面是和 VQ 完全相同。（如果每個類別資料個數差距很大，也可以讓具有大量資料的類別有較多的代表點。）
2. 對每一個資料點 x，尋找最接近的代表點，假設是 y_k
3. 比較 x 和 y_k 的類別，進行下列處理：
   • 若類別相同，則將 y_k 朝 x 的方向拉近： y_k = y_k + α [x - y_k]
   • 若類別不同，則將 y_i 朝 x 的反方向拉遠： y_k = y_k - α [x - y_k]
4. 回到步驟二，反覆對所有資料點進行運算並微調代表點，直到代表點不再變化。

其中，α 是一個隨疊代次數而遞減函數，而且0 < α < 1。

After the cluster centers converge, we can then use these centers to represent the original class. For any unseen data, we can apply k-nearest-neighbor classification to determine its class.

上述疊代方法收斂後，我們即可以使用每個類別的代表點來代表這一類的資料分佈。遇到未知類別的新資料，我們只需以最近鄰居法則，找出最近的代表點，即可判定該資料的類別。

Here is a summary of the difference between LVQ and VQ.

• VQ is used for data compression and representation, which is applicable for unlabeled data.
• The goal of LVQ is to find representative points for each class. And then update these points for best recognition rate. Therefore it is suitable for labeled data (classification problem).

LVQ 的方法和 VQ 很接近，但不同的是：

• VQ 是用在資料的壓縮與取編碼向量，適用於無類別資訊的資料。
• LVQ 的目標再找出同一個類別資料的代表點，再以代表點來進行分類，因此適用於分類問題。

Hint

If you have installed Neural Network Toolbox, you can type "nnd14lv1" or "nnd14lv2" to view interactive demos of LVQ.

Hint

如果你有安裝「類神經網路工具箱」，就可以在 MATLAB 輸入 nnd14lv1 或是 nnd14lv2，就可以看到 LVQ 的互動式展示。

References:

1. T. Kohonen, "Improved Versions of Learning Vector Quantization", International Joint Conference on Neural Networks (IJCNN), 1990.

---

Data Clustering and Pattern Recognition (資料分群與樣式辨認)