0. 前提知識
ソーシャルデータや多くのユーザーを抱えるWeb・モバイルサービスにとって、
高次元ベクトルデータの扱いに困ることは少なくないと思います。
多くのユーザーの行動データや登録データからユーザー間の類似度を算出したり、
行動データを解析して適切なコンテンツをレコメンドしたりする場合に、データ量によっては計算時間やサーバーの負荷などがボトルネックになり、リアルタイム性を妥協したり、精度を妥協したりすることが出てきてしまうことがあります。
今回ヤフーが公開したNGTというソフトウェアは高次元ベクトルデータにおいて超高速に近傍検索をしてくれるので、実際に使ってみたら結構すごかったので、実際に利用した内容も含めて公開したいと思います。
1. NGTの環境構築
CentOSにngtをインストール
console
wget http://i.yimg.jp/dl/docs/research_lab/ngt-0.0.1.zip
unzip ngt-0.0.1.zip
cd ngt-0.0.1
mkdir build
cd build
cmake ..
make
make install
export LD_LIBRARY_PATH=$LD_LIBRARY_PATH:/usr/local/lib64
2. データの準備&実行
・ヤフーのngtのzipファイルに入っているテストデータで行う場合
console
cd ngt-0.0.1
ngt create -d 128 -o c index ./data/sift-dataset-5k.tsv
ngt search -n 20 index ./data/sift-query-3.tsv
・独自のデータも用意してみる
今回試してみたのは、userがuserに興味を示すようなデータを元にuser間の類似度を算出するというサンプルで試してみました。
user_user_favorite.tsv：userがuserに興味を示した度合いを要素にしたベクトルデータ
example_user_favorite.tsv：その中で抽出した1人のuserの興味ベクトルデータ
console
cd ngt-0.0.1
ngt create -d 128 -o c index ./data/user_user_favorite.tsv
ngt search -n 5 index ./data/example_user_favorite.tsv
3. 結果
特定のuser_idのユーザーとの距離が近い上位5人を取得してみると以下のような結果が得られる。
| Rank | IN-ID | ID | Distance |
|---|---|---|---|
| 1 | 151 | 151 | 231.003 |
| 2 | 661 | 661 | 231.981 |
| 3 | 178 | 178 | 237.763 |
| 4 | 2241 | 2241 | 244.102 |
| 5 | 558 | 558 | 249.453 |
1列目：距離が近い順位
2列目：user_id
3列目：tsvデータ上のID
4列目：距離
1万×1万の正方行列のベクトルデータの計算でも500ms未満で返ってくるのはマジですごい！！
※残念ながら商用利用は不可なのでご注意を。