多次元尺度構成法（MDS）で文字列の編集距離を可視化してみる
はじめに
ベクトルとして表現するのが難しいけど、個体間の距離（非類似度）は定義できる……というデータがたまにあります。こういうとき、多次元尺度構成法を使うと可視化がうまくいきます。
ということで、編集距離を可視化してみようと思います。
データ
hogehogeとfugafugaを適当に変えた文字列を10個ずつ考えます。こんなのです。
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.ones((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
これも特に難しいことはありません。
コード全体
importから可視化のプロットなども含めたコードの全体像がこちらです。
import Levenshtein import numpy as np import matplotlib.pyplot as plt from sklearn.manifold import MDS 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) 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 mds = MDS(n_components=2, dissimilarity="precomputed") X_2d = mds.fit_transform(A) 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()
可視化では文字列のプロットと、散布図をやっています。これでわかりやすく見えるはずです。
実行結果
結果を以下に示します。
似ているものが近くに来るように配置されることがわかります。だいたいきれいに2グループに分かれています。
まとめ
このように多次元尺度構成法（MDS）が使えるときがあるので、名前だけは覚えておいても損はしません。こういうものもある、ということを知っておきましょう。
追記
書き上げてから「同じことをやっている人がいるかなぁ」と思って「多次元尺度構成法 編集距離」で検索したら、いくつか出てきました。
https://www.jstage.jst.go.jp/article/iieej/38/5/38_5_634/_pdf/-char/ja
これは画像処理かな。専門外なのでよくわかってはいません。
主座標分析について簡単に紹介するよ！ - ほくそ笑む
編集距離も使える、という説明だけ。
http://db-event.jpn.org/deim2012/proceedings/final-pdf/c10-1.pdf
学会の抄録ですかね。
そんなに目ぼしいものはないといえばない状況です。今回は単純なデータで実験したのでいい感じの結果になりましたが、実用的にはなかなか厳しいのかもしれません。
あと、MDSでは距離の公理という面倒くさいものが絡んでくることがあります。これを満たさないものは普通のMDSでは扱えないので、「非計量多次元尺度構成法（nMDS）」で取り扱え、ということが言われていたりします。レーベンシュタイン距離は一応大丈夫らしいですが、（研究やビジネスなどで）ちゃんと使いたい場合はこの辺りにも気を配るべきでしょう。
