SciPyでベクトル量子化

ベクトル量子化（Vector Quantization: VQ）とは、ベクトルで表されたデータ集合を有限個の代表的なパターン（セントロイド）に置き換える処理のことです。代表パターン（セントロイド）のリストはコードブック（code book）と呼ばれます。また、クラスタの番号をコードと呼びます。各ベクトルデータは、距離が一番近いコードに置き換えられます。大量のデータを少ない代表パターンで置き換えることができるためデータの圧縮に使えます。ただし、コードブックから元のデータは復元できないため非可逆圧縮になります。

コードブックを学習するためのアルゴリズムの代表例がk-meansクラスタリングです。ベクトルデータをクラスタリングして、各データをそのデータが属するクラスタのセントロイドに置き換えることでベクトル量子化が実現できます。

ベクトル量子化の応用

ベクトル量子化の応用例の一つに、前に取り上げた画像のBag-of-Visual Words表現（2010/02/27）があります。Bag-of-Visual Wordsでは、ベクトルで表される画像の局所特徴量（SIFT、SURFなど）をK個のクラスタに分類します。そして、K個のクラスタのセントロイドをVisual Wordとし、各画像をVisual Wordのヒストグラムで表現します。ここでは、Visual Wordsの集合がコードブックになりますね。

今回は、類似楽曲検索にベクトル量子化を応用する予定です。その場合、楽曲のMFCCベクトル集合がベクトルデータになり、これをK個のクラスタに分類し、各クラスタの多次元分布（平均ベクトルと分散・共分散行列）を楽曲の特徴量とします。こうすることで、楽曲のMFCCベクトル集合をより少ないパラメータで表現できます（データ次元の圧縮）。

まあ、応用は今後いろいろ試すことにして、ここでは単純な人工データでベクトル量子化を試してみます。

SciPyでベクトル量子化

k-meansクラスタリングは、以前実装しましたが、SciPyには、scipy.cluster.vqというベクトル量子化に関するライブラリがあるのでそれを使ってみます。使うのは、コードブックを学習するkmeans()関数とデータをベクトル量子化するvq()関数です。

この例では、3つのガウス分布から二次元データを100個ずつ生成しました。このベクトルデータをクラスタリングしてコードブックを求めています。そのコードブックをもとにベクトル量子化して各データをコードに置き換えています。最後にベクトル量子化されたデータをコード別に色分けして図示してみました。

#coding:utf-8
import numpy as np
import scipy.cluster
frompylab import *

if __name__ == "__main__":
    cls1 = []
    cls2 = []
    cls3 = []

    # 分布1
    mean1 = [-2, 2]
    cov1 = [[1.0, 0.0], [0.0, 1.0]]

    # 分布2
    mean2 = [0, 0]
    cov2 = [[1.0, 0.8], [0.8, 1.0]]

    # 分布3
    mean3 = [2, -2]
    cov3 = [[0.5, 0.3], [0.8, 0.4]]

    # 分布にしたがうデータ生成
    cls1.extend(np.random.multivariate_normal(mean1, cov1, 100))
    cls2.extend(np.random.multivariate_normal(mean2, cov2, 100))
    cls3.extend(np.random.multivariate_normal(mean3, cov3, 100))
    X = vstack((cls1, cls2, cls3))

    # データをクラスタリング
    codebook, destortion = scipy.cluster.vq.kmeans(X, 3, iter=20, thresh=1e-05)
    print codebook, destortion

    # ベクトル量子化
    # 各データをセントロイドに分類する
    code, dist = scipy.cluster.vq.vq(X, codebook)

    # 各データをクラスタ別に色分けして描画
    for i in range(len(X)):
        x1, x2 = X[i, ]

        if code[i] == 0: color = 'r+'
        elif code[i] == 1: color = 'b+'
        elif code[i] == 2: color = 'g+'
        plot(x1, x2, color)

    # セントロイドを描画
    x1, x2 = np.transpose(codebook)
    plot(x1, x2, 'yo')

    xlim(-6.0, 6.0)
    ylim(-6.0, 6.0)
    show()

実行するとこうなります。黄色い●がコードブックのセントロイドです。

ちゃんと各データがクラスタに分類されていることがわかります。今回は、3つの分布からデータを生成したのでコードブックサイズ（クラスタ数、セントロイド数）は3としましたが、わからないときははいくつにすればいいんでしょうね？クラスタ数を多くすればするほどkmeans()の返すdestortion（歪み）は小さくなり、量子化の精度も上がるようです。だけどその代償としてコードブックのサイズは大きくなります。コードブックサイズと精度の間にトレードオフは応用や目的によって試行錯誤で決めるのかな？