LSH (Locality Sensitive Hashing) を用いた類似インスタンスペアの抽出
GW 中の長距離移動のために体調が優れない takahi-i です. 今回は巨大なデータをマイニングする一つの技術として LSH (Localtiy Sensitive Hashing) を紹介させていただきます.
LSH とは
LSH は大量なデータから類似度が高いインスタンスのペアを高速に抽出してくれるアルゴリズムです. ここでインスタンスはデータ集合の一つの要素を表します. たとえば扱うデータが E-コマースサイトの購買ログであれば, インスタンスは各ユーザですし, 画像データ集合であれば, インスタンスは個々の画像データです. LSH の詳しい解説については以下のサイトがあります. 本稿ではE-コマースサイトの購買履歴データを基に LSH の機能について述べてゆきます.以下のような E-コマースサイトの購買履歴 (ログ) データがあったとします. この表において一列目はユーザ番号を二列目はユーザが購入した商品一覧をそれぞれ表します.
| ユーザID | 購買アイテム一覧 |
|---|---|
| 0 | iPad, Microsoft Zune, うまい棒 |
| 1 | ヘルシオ, REGZA |
| 2 | Nicon D3000, チョコレート |
| 3 | チーズケーキ, ロレックス, オメガ |
| 4 | エルメス, グッチ, ユニクロ |
| 5 | Microsoft Zune, うまい棒, 任天堂DS |
上記のような表から類似度の高いユーザペアを抽出するには, ユーザが購入した商品が要素となるベクトル間の類似度 (コサイン関数等) を総当たりで計算し, 類似度があるしきい値以上のユーザペアを抽出する方法が一般的です. しかし, たくさんのユーザが存在する場合 (たとえばミクシィでは 2000 万を越えるユーザが利用しています) すべてのユーザ間の類似度を総当りで計算するのでは計算コストが非常に大きくなってしまいます.
これに対して LSH はユーザ間の類似度を総当たりで計算する処理は行いません. LSH ではベクトル (上記の例ではユーザの購入した商品が要素となるベクトル) を入力として, スカラ値を出力する関数 (ハッシュ関数) を定義します. この関数は似たベクトルであれば同一の値を返す (返しやすい) という特徴を持ちます. LSH は関数からかえされるハッシュ値が同一のユーザペアを抽出することで類似するユーザペアを高速に抽出できます. 各ユーザベクトルを並列に処理することができ, さらに類似度を全ての組み合わせで計算しなくても良いため計算量の大幅な低減が望めます.
上記の例ように E-コマースサイトのログから興味が近いユーザを抽出することができますが, LSH を利用することで, ニュースのレコメンド, 類似画像の抽出に利用できることが知られています.
LSH の一実装 (Likelike)
LSH の一実装として, Likelike (リケリケ) というツールを作りました (ここからダウンロードできます). Likelike の特徴として Hadoop の MapReduce 上で動作するため, 使用する計算機の数を増やすことでより大規模なデータに対応できるという点があります. 予備の実験として1000 万件のデータ (各データは 10 個の特徴量を持つ) を自動生成し 4 台の計算機で計算したところ, 一時間程度で終了しました (パラメータ depth=2, iterate=20 の時). Likelike の入力として以下の様なタブとスペースで区切られたファイルが必要です.% cat src/test/resources/testInput.txt 0 776 2919 4576 4485 2380 4261 3622 1456 2109 3227 1 4358 4350 559 1136 2848 1345 1428 4212 2681 120 2 3614 3035 4592 1191 441 1408 734 1005 4826 33 3 691 878 1938 3381 127 4283 2269 3814 2908 1864 4 3781 603 1262 1988 1309 864 3511 729 1454 2845 5 3183 3575 180 4367 3616 4072 824 4976 4021 3361 6 3210 1956 2421 203 3006 2706 4794 4805 4180 2124 7 1548 3831 1447 3040 4137 3055 809 4497 2052 4994 ...このファイルにおいて, 一列目はインスタンス ID を表し, スペースで区切られている 2 列目以降はインスタンスの特徴量をそれぞれ表します. たとえば, このファイルに含まれるデータを E-コマースサイトのユーザの購買履歴とすれば, 一列目はユーザ ID を, スペースで区切られた二列目以降は購入した商品 ID を表します. 次にこのファイルを入力として指定して Likelike を実行します. 詳しい使用方法については Likelike の QuickStart を参照してください.
% sh bin/likelike lsh -input src/test/resources/testInput.txt -output testOutputDir上記のコマンドを実行すると, 以下の様に各行が類似ベクトルペアからなる結果が出力ディレクトリ testOutputDir 内のファイルに出力されます.
0 5766 0 1962 0 2649 ...これはユーザ 0 の関連ユーザとして 5766, 1962 が抽出されたことを示しています.
