カーネルPCAで文字列の編集距離を可視化してみる

はじめに

　以前に編集距離が計算された文字列間の位置関係をMDSを使ってまったく同じことをしましたが、今度はカーネルPCAでやってみます。

　違いとしては、MDSは距離行列から計算を行うのに対してカーネルPCAは類似度行列から計算を行えるということがあると思います。逆に言えば、それくらいしか違わないし、だいたい同じようなことができるということです。

　なお、この記事を読む前に、以下の2記事を先にご覧いただくとやっていることがわかりやすいと思います。

多次元尺度構成法（MDS）で文字列の編集距離を可視化してみる - 静かなる名辞
scikit-learnのSVMを自分で計算したカーネルで使う - 静かなる名辞

実験

　カーネルPCAのドキュメントはこちらです。

sklearn.decomposition.KernelPCA — scikit-learn 0.21.3 documentation

　kernel="precomputed"として、あとは淡々と実装します。

import Levenshtein
import numpy as np
import matplotlib.pyplot as plt
from sklearn.decomposition import KernelPCA

def main():
    # データ（自作）
    X = ["hogehoge", "hogghheg", "fogefoge", "hagbhcgd", "hogeratt",
         "hohohoho", "fugefuge", "hokehoke", "hogehope", "kogekoge",
         "fugafuga", "fugafuge", "fufufufu", "faggufaa", "fuuuuuuu",
         "fhunfhun", "ufagaguf", "agufaguf", "fogafoga", "fafafaoa"]
    label = np.array(["hoge"]*10 + ["fuga"]*10, dtype=object)

    # 類似度行列の作成（levenshtein距離）
    A = np.zeros((len(X), len(X)))
    for i in range(len(X)):
        for j in range(i + 1, len(X)):
            d = Levenshtein.distance(X[i], X[j])
            A[i,j] = A[j,i] = d
    A = -A  # 距離->類似度変換のためマイナスをかける

    # kernel pcaによる変換
    kpca = KernelPCA(n_components=2, kernel="precomputed")
    X_2d = kpca.fit_transform(A)

    # plot
    for (x, y), l in zip(X_2d, X):
        plt.text(x, y, l)
    
    for l in set(label):
        plt.scatter(X_2d[label==l, 0], X_2d[label==l, 1], label=l)

    plt.xlim(X_2d[:,0].min() - 1, X_2d[:,0].max() + 1)
    plt.ylim(X_2d[:,1].min() - 1, X_2d[:,1].max() + 1)
    plt.legend()

    plt.savefig("result.png")
   
if __name__ == "__main__":
    main()

　んー、こんなもんですかね。以前の結果も再掲します。

　なぜか色の関係が逆転している気もしますがそれはともかく、基本的な構造はどちらでもつかめていると思います。

違いについて

　カーネルPCAだとtransformを呼べるので、データを追加して元の空間でどの辺に来るのかを予想する、といった用途には便利です。

　たとえば、を追加してみます。

import Levenshtein
import numpy as np
import matplotlib.pyplot as plt
from sklearn.decomposition import KernelPCA

def main():
    # データ（自作）
    X = ["hogehoge", "hogghheg", "fogefoge", "hagbhcgd", "hogeratt",
         "hohohoho", "fugefuge", "hokehoke", "hogehope", "kogekoge",
         "fugafuga", "fugafuge", "fufufufu", "faggufaa", "fuuuuuuu",
         "fhunfhun", "ufagaguf", "agufaguf", "fogafoga", "fafafaoa"]
    label = np.array(["hoge"]*10 + ["fuga"]*10, dtype=object)

    # 類似度行列の作成（levenshtein距離）
    A = np.zeros((len(X), len(X)))
    for i in range(len(X)):
        for j in range(i + 1, len(X)):
            d = Levenshtein.distance(X[i], X[j])
            A[i,j] = A[j,i] = d
    A = -A  # 距離->類似度変換のためマイナスをかける

    # kernel pcaによる変換
    kpca = KernelPCA(n_components=2, kernel="precomputed")
    X_2d = kpca.fit_transform(A)

    # plot
    for (x, y), l in zip(X_2d, X):
        plt.text(x, y, l)
    
    for l in set(label):
        plt.scatter(X_2d[label==l, 0], X_2d[label==l, 1], label=l)

    # hogefugaを写像（追加）
    data = "hogefuga"
    A = np.zeros((1, len(X)))
    for i in range(len(X)):
        d = Levenshtein.distance(data, X[i])
        A[0,i] = d
    A = -A  # 距離->類似度変換のためマイナスをかける
    hg_X = kpca.transform(A)
    plt.text(hg_X[0,0], hg_X[0,1], data, color="r")

    # 見た目調整
    plt.xlim(X_2d[:,0].min() - 1, X_2d[:,0].max() + 1)
    plt.ylim(X_2d[:,1].min() - 1, X_2d[:,1].max() + 1)
    plt.legend()

    plt.savefig("result2.png")
   
if __name__ == "__main__":
    main()

　このようにhogefugaがどのあたりに位置するのかを、既存の点を再計算せずに写像して見てみることができます。MDSだと全体を再計算しないとできないはずなので、これができることがカーネルPCAの明確なメリットの一つだと思います。

　transformに渡す配列のshapeに関しては若干自信がなかったのですが、逆にしたら（つまり.Tをつけたら）

ValueError: Precomputed metric requires shape (n_queries, n_indexed). Got (20, 1) for 20 indexed.

　なる見たことも聞いたこともないようなエラーが出たので、たぶんこれで合っています。

まとめ

　まあ同じようなことができるんだなぁと思いました。