Locality Sensitive Hashを試してみた
- 作者: arton,桑田誠,角田直行,和田卓人,伊藤直也,西田圭介,岡野原大輔,縣俊貴,大塚知洋,nanto_vi,徳永拓之,山本陽平,田中洋一郎,下岡秀幸,ミック,武者晶紀,高林哲,小飼弾,はまちや2,WEB+DB PRESS編集部
- 出版社/メーカー: 技術評論社
- 発売日: 2009/02/23
- メディア: 大型本
- 購入: 10人 クリック: 373回
- この商品を含むブログ (45件) を見る
Web+DB Pressのレコメンド特集に載っていたLocality Sensitive Hashを試してみました。あまりよく理解できてないので間違っているかもしれませんが、せっかくなのでブログに書いておきます。
作成したコードは以下に置いてあります。
ただし、記事中ではランダムに選択するベクトルを平均0、分散1の正規分布に従って生成するよう書かれていましたが、ここでは入力されたベクトル群の中からランダムに選択するようにしちゃってます。なので選択されたベクトルに偏りが生じる場合があるため、適切な結果が得られない可能性があります。
またビットベクトルの添字をシャッフルする時に近似式により計算するように書かれていましたが、上記のプログラムでは普通にリストをシャッフルしてるだけです。これは多分結果には影響しないと思いますが。
さて実際に試してみようと思います。入力には、以前作成したWikipediaの各キーワードのTFIDFによる特徴ベクトルDBMを使います。(ただしワードとポイントの間の区切り文字はコロンからタブに変更したものを使用しています)
% 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
うーん、合ってるような合ってないような。というか知らない単語ばかりでよく分からない…^^; 全部の結果は以下の場所に置きましたので、興味のある方はご参照ください。すごい関係が深いものがペアになっている、というわけではないですが、ある程度関係性のあるものは取れているように思います。
また今のプログラムでは、ランダムに選択したベクトルとビットベクトルを保存していないのですが、これを保存して再利用できるようにしておけば、未知の入力に対しても類似するコンテンツを求めることが可能になると思います。
あと、転置インデックスを作って、それを使用して対象を絞り込んでから類似度を求める方法でも、同じようなことは出来ると思うんだけど、それと比べたときのLSHの利点は何だろう。転置インデックスを用意する必要がないことと、多少比較する回数が減るところだろうか？でもその分、再現率は減少するだろうから、その辺はトレードオフになっちゃうんでしょうか。