Locality Sensitive Hashを試してみた

WEB+DB PRESS Vol.49

Web+DB Pressのレコメンド特集に載っていたLocality Sensitive Hashを試してみました。あまりよく理解できてないので間違っているかもしれませんが、せっかくなのでブログに書いておきます。

作成したコードは以下に置いてあります。

• http://github.com/mjmania/mining/blob/991a855fc378d831a057c36c65ce118e197907ff/lsh/lsh.pl

ただし、記事中ではランダムに選択するベクトルを平均0、分散1の正規分布に従って生成するよう書かれていましたが、ここでは入力されたベクトル群の中からランダムに選択するようにしちゃってます。なので選択されたベクトルに偏りが生じる場合があるため、適切な結果が得られない可能性があります。

またビットベクトルの添字をシャッフルする時に近似式により計算するように書かれていましたが、上記のプログラムでは普通にリストをシャッフルしてるだけです。これは多分結果には影響しないと思いますが。

さて実際に試してみようと思います。入力には、以前作成したWikipediaの各キーワードのTFIDFによる特徴ベクトルDBMを使います。(ただしワードとポイントの間の区切り文字はコロンからタブに変更したものを使用しています)

• TFIDFを使ってwikipediaの各キーワードの特徴量を抽出 - のんびり読書日記

% tchmgr list -pv tfidf_tab.hdb | head -1
宝井誠明        映画    847     フロム・ファーストプロダクション        777     年      744     テニス  666     シコ    569 -
        538     1992    501     特技    494     型      482     月      459     出身    450     山本    428     血液    390  宝井    375     東京    355     誠      351     役      327     1975    326     サッカー        305     春雄    300     明  297      11      291     O       291     CM      291     俳優    289     1       280     デビュー        270     *       252  出演    251     日      249     ドラマ  249     所属    247     都      246     野球    245     数々    243     2       225  まさ    225
d

では実際に動かしてみます。とりあえずランダム選択するベクトルの数は10個、ビットベクトルの添字をシャッフルする回数は5回で、コサイン類似度が0.7以上のペアだけを出力するようにしています。適当に選んだ数字ですが、実際はどれくらいの値が一番いいもんなんですかね？

% ./lsh.pl tfidf_tab.hdb out.txt
Select random vectors
Calculate bits
Loop No.0
 Shuffle bits
 Get similar keys
Loop No.1
 Shuffle bits
 Get similar keys
Loop No.2
 Shuffle bits
 Get similar keys
Loop No.3
 Shuffle bits
 Get similar keys
Loop No.4
 Shuffle bits
 Get similar keys

ゴミっぽい語を外して結果を見てみます。

% sort -t "    " -k 3 -g -r out.txt | grep -v "ファイル:" | grep -v "Template:" | grep -v "Category:" | grep -v "Portal:" | head
人名一覧 に     人名一覧 や     1
人名一覧 し     人名一覧 と     1
IATA空港コードの一覧/M  IATA空港コードの一覧/S  1
IATA空港コードの一覧/G  IATA空港コードの一覧/Z  1
ED14    ED15    1
ED12    ED17    1
ㄽ      ㅄ      1
腰外側横突間筋  腰内側横突間筋  0.994469509662891
斥前王朝        疑惑    0.992928087585636
真法会  大西賢治        0.990816673861238
人間発展論      戸田市児童合唱団        0.990265827114968
メジャーリーグ選手一覧 F        メジャーリーグ選手一覧 K        0.989775319616109
疑惑    今浪祐介        0.989574427352262
株式会社コーケン        京浜家族        0.988301506511739
佐倉惣五郎      色川三中        0.987181482040356
永久寿夫        昭和鉄風伝 日本海       0.98616784759357
猪苗代警察署    郡山警察署 (福島県)     0.985511357646904
河北警察署      白石警察署 (宮城県)     0.985341109030206
中警察署        熱田警察署      0.985244748731653
津島警察署      天白警察署      0.984575913684946
江南警察署 (新潟県)     新潟西警察署    0.983341530648179
アモック        MAJESTIC CIRCUS 0.982210962978045
職業訓練指導員 (漆器科) 職業訓練指導員 (塗装科) 0.982116598007288

うーん、合ってるような合っていないような。警察署のペアがやたら多いですね。もうちょい下位の方も見てみます。

聖應女学院放送局        南の虹のルーシー        0.831625376771682
めざせ!!カードマスター  AZEL -パンツァードラグーン RPG- 0.831544323236761
飛行第5戦隊 (日本軍)    飛行第4戦隊 (日本軍)    0.831488221371462
メタルダンジョン        ひまわり (朝ドラ)       0.831465811425831
何なら俺に話してみろ    仙豆    0.831460166966955
職業訓練指導員 (ホテル・旅館・レストラン科)     職業訓練指導員 (インテリア科)   0.831458630727353
ルーンファクトリー フロンティア スシ王子!       0.831398551766701
キャッシュレジスター    何なら俺に話してみろ    0.831379733306556
北北西  南南西  0.831115494491915
ハイパーレストラン      びっくり熱血新記録      0.831108298496472
プリンセスチュチュ      GOOD LUCK!!     0.831069855040055
SONIC A-GO-GO!! FNNニュースレポート     0.83106626790226
職業訓練指導員 (印章彫刻科)     職業訓練指導員 (貴金属・宝石科) 0.831052281622264
職業訓練指導員 (工業包装科)     職業訓練指導員 (建築板金科)     0.830981136625595
フルアヘッド!ココ       マスツーリズム  0.830871708012674

うーん、合ってるような合ってないような。というか知らない単語ばかりでよく分からない…^^; 全部の結果は以下の場所に置きましたので、興味のある方はご参照ください。すごい関係が深いものがペアになっている、というわけではないですが、ある程度関係性のあるものは取れているように思います。

• http://mahjong-mania.net/mining/data/lsh_wikipedia.txt

また今のプログラムでは、ランダムに選択したベクトルとビットベクトルを保存していないのですが、これを保存して再利用できるようにしておけば、未知の入力に対しても類似するコンテンツを求めることが可能になると思います。

あと、転置インデックスを作って、それを使用して対象を絞り込んでから類似度を求める方法でも、同じようなことは出来ると思うんだけど、それと比べたときのLSHの利点は何だろう。転置インデックスを用意する必要がないことと、多少比較する回数が減るところだろうか？でもその分、再現率は減少するだろうから、その辺はトレードオフになっちゃうんでしょうか。