三国志のゲームの武将データを（サンプルに）使った近傍検索を、検索ライブラリ「NGT」を使って、試してみた話です。
ひょんなことから、久しぶりに高次元（多次元）ベクトルのデータを扱うことになりました。（もとい仕事で扱うことにしました。）
というのも、15年以上前の話ですが、私、学生の頃は情報検索に関する研究をしていまして、いわゆる大容量ファイル等の類似検索で扱えるような高次元なベクトルデータ向けの効率的なインデックスに関することをテーマとしてやっていたんですよね。
・・・閑話休題。
で、良さげな検索ライブラリがないかなー、と探してみたら、Yahoo!様が「NGT」というドンピシャなライブラリをオープンソースとして公開してくれていたので、早速試してみました。
NGTと高次元ベクトルの検索について
「NGT」は、GitHub の README によると "Neighborhood Graph and Tree for Indexing High-dimensional Data" とのことで、以下の記載があります。
大量（数百万から数千万データ）の高次元ベクトルデータ（数十～数千次元）に対して高速な近似近傍検索を可能とするコマンド及びライブラリを提供します。
https://github.com/yahoojapan/NGT/blob/master/README-jp.md
高次元ベクトルのデータ近傍検索の例えとして、わかりやすいのは画像の類似検索などですが、画像や映像などのメディアデータというのは基本的には大きなサイズとなり、検索対象となるデータ集合が大量な場合、莫大な計算量を必要とします。
で、画像から特徴抽出（何かしらの多次元ベクトルによる数値化）をして、さらに次元圧縮を行っていって、（例えば）数百次元とかの数値データで表現したりするのですが、それでも普通に多次元の特徴空間でユークリッド距離を計算をしていくのも、そこそこ計算量が必要であり、検索などのために総当たりで計算していくと普通に処理に時間がかかります。
（検索結果が出るまでに物凄く時間がかかることになる。）
それらをいい感じで可能な限り高速化するべく世の中では色々な研究が行われていて、その1つがこの「NGT」としてYahoo!様がオープンソースとして公開されているわけです。
（本当に素晴らしい取り組みです。ありがとうございます。）
尚、「NGT」のライセンスは現時点では「Apache License 2.0」のようです。
NGTのインストール
README に記載されている通りですが、インストール手順をログに残しておきます。
ちなみに使ったサーバのOSは "Ubuntu 18.04.2 LTS" です。
# apt-get update # apt-get install build-essential cmake
まず、ビルドに必要なパッケージを apt でインストールします。
# wget https://github.com/yahoojapan/NGT/archive/v1.7.4.tar.gz # tar zxvf v1.7.4.tar.gz
GitHubからパッケージングされたファイルをダウンロードして展開。
# cd NGT-1.7.4/ # mkdir build # cd build # cmake -DNGT_LARGE_DATASET=ON .. # make # make install # ldconfig /usr/local/lib
あとは、ビルドして、インストールして、共有ライブラリパスを更新。
尚、 "-DNGT_LARGE_DATASET=ON" のパラメータはドキュメントによると、約500万以上のオブジェクトを登録する場合に、検索速度向上に寄与するとのことで、今回の検証では不要なんですが、ゆくゆくは数億件くらいの規模感で動かしていきたいとは考えているので、最初から付与して検証しています。
さて、インストールはここで完了で、とりあえず ngt コマンドを叩くと以下のように Usage が表示されるかと思います。
# ngt
Usage : ngt command database data
command : create search remove append export import prune reconstruct-graph
三国志の武将データをインデックス化してみる
さて、試しに何のデータを入れてみようかなー、と色々考えたのですが、ある程度肌感（知見）があるデータじゃないと評価が難しいので、その時頭をよぎったのは、コーエー（光栄）さんのゲーム、三國志シリーズの武将データとかどうだろうか、とw
昔、中でも三國志3を結構やりこんでた時期があって、登場人物とかパラメータとか微妙に覚えていたので、すごく懐かしさを感じながら、三國志3の武将データを使わせていただくことにしました。
・・・ここで謝罪ですが、三國志3の武将データのパラメータって、おおまかには6種類（武力、知力、政治、魅力、陸指、水指）なんですよね・・・つまり6次元のベクトルデータなので、たいして高次元じゃないやんけ、というツッコミが入りそうな点、お許しください。。。
というわけで、まず三國志III (三國志DS) で使われていた武将データを用意。
ngt コマンドで読み込むデータファイル（検索対象の母集団）は、タブかスペース区切りのフォーマットにする必要があるので、TSV に変換。
そして、以下のように "create" コマンドでインデックスを作成します。
$ ngt create -d [次元数] [インデックス名] [母集団ファイルパス]
一番簡単な（デフォルトパラメータでの）実行は、こんな感じ。
$ ngt create -d 6 sangokushi3 ./sangokushi3_busho_list.tsv Data loading time=0.00234013 (sec) 2.34013 (msec) # of objects=770 Index creation time=0.0222825 (sec) 22.2825 (msec)
実際は、こんな感じで実行しました。
ちなみに "-d" オプションでは次元数を指定します。
今回は、最初の6つのパラメータだけを読ませたいので、「6」を指定すると、値を6つ分読み込んだ後、残りの後続パラメータは無視されます。
あと、 ngt コマンドは実行すると、上記出力のように完了するまでにかかった時間が表示されます。
さて、これでインデックスの作成は完了です。ホームディレクトリにインデックス名でつけた名前のディレクトリが作成されて、そこにインデックスデータがあるかと思います。
NGTを使った特徴空間で "関羽" のパラメータに近い武将を探す
では、先ほど作ったインデックスを使って、検索を試してみたいと思います。
インプットのデータとして三国志では蜀を代表する名将である "関羽" のパラメータを与えて、関羽のパラメータに近い武将を検索してみます。
つまり、最高クラスの武力や魅力を持ちつつ、軍師としても張れるような武将です。
$ cat query01.tsv 98 82 64 96 100 78
関羽のパラメータ6つを記載したクエリファイル（TSV）を作ります。
$ ngt search -n [検索結果数] [インデックス名] [クエリファイルパス]
で、検索するときは "search" コマンドを使います。
$ ngt search -n 10 sangokushi3 ./query01.tsv Query No.1 Rank ID Distance 1 113 0 2 207 20.4695 3 500 20.9284 4 451 21.5174 5 153 22.0681 6 424 26.7955 7 81 28.5307 8 429 29.2404 9 175 29.5804 10 761 29.7658 Query Time= 6.3707e-05 (sec), 0.063707 (msec) Average Query Time= 6.3707e-05 (sec), 0.063707 (msec), (6.3707e-05/1)
これが結果の出力です。
こんな感じで、武将データのパラメータから計算された特徴空間内において、ユークリッド距離が短い結果から、近似値オブジェクト（パラメータが近しい武将）が結果として返されます。
↑の結果で、Rank 1 にいる距離が 0 のオブジェクトはズバリ関羽本人ですw （同じ母集団リストに含まれているため）
なので、2位以降の ID の武将が関羽のパラメータに近しい武将たち。
結果がどんな感じかというと、↑のランク順のIDに武将をマッピングした結果が以下です。
ID,名前,武力,知力,政治,魅力,陸指,水指 -- 113,関羽,98,82,64,96,100,78 -- 207,黄忠,95,67,64,87,90,76 500,張遼,90,80,68,83,87,74 451,趙雲,98,84,80,93,87,83 153,姜維,91,92,72,85,88,75 424,孫堅,90,84,72,87,81,90 81,郝昭,85,76,70,83,80,76 429,孫策,91,85,74,89,82,96 175,厳顔,86,71,68,76,87,73 761,呂蒙,84,91,65,88,80,90
おおお！！確かに関羽に匹敵するような名将たちが綺麗に並んでいます！
"諸葛亮" のパラメータに近い武将を探す
同じ要領で、次は "諸葛亮" に近いパラメータを持つ武将を検索してみます。
諸葛孔明様といえば三国志を代表する名軍師。知的なだけではなく戦場にも出陣・指揮していけるような名軍師達が結果として出てくることを期待。
$ cat query02.tsv 61 100 92 95 92 78
先ほどと同じように "諸葛亮" のパラメータを記載したクエリファイルを作成して、、、
$ ngt search -n 10 sangokushi3 ./query02.tsv Query No.1 Rank ID Distance 1 337 0 2 632 13.0767 3 340 15.1987 4 265 15.6205 5 768 17.6352 6 572 26.5895 7 770 26.8514 8 267 29.6479 9 307 30.2655 10 308 31.8904 Query Time= 6.8188e-05 (sec), 0.068188 (msec) Average Query Time= 6.8188e-05 (sec), 0.068188 (msec), (6.8188e-05/1)
検索を実施。さっきと同じ要領で結果を見ていくと、、、
ID,名前,武力,知力,政治,魅力,陸指,水指 -- 337,諸葛亮,61,100,92,95,92,78 -- 632,龐統,60,98,82,88,88,77 340,徐庶,65,95,87,85,85,74 265,司馬懿,62,98,90,80,95,79 768,魯粛,61,95,84,90,78,79 572,杜預,70,85,80,81,86,83 770,盧植,47,82,83,85,88,80 267,司馬師,65,87,81,75,79,76 307,蒋琬,60,85,80,84,73,70 308,鐘会,70,94,70,79,80,74
こちらも期待通りの結果！
魏呉蜀を代表する、戦場でも指揮できるレベルの名軍師達が勢揃いという結果に。
全てのパラメータが "80" に近い武将を探す
次は、全パラメータが "80" に近いような、何をやらせてもそつなくこなせる万能的な優秀な武将を探してみます。
$ cat query03.tsv 80 80 80 80 80 80
同じ要領でクエリファイルを作成し、、、
$ ngt search -n 10 sangokushi3 ./query03.tsv Query No.1 Rank ID Distance 1 487 12.2474 2 81 12.8841 3 572 13.0767 4 287 13.2665 5 585 16.1245 6 45 16.9411 7 21 17 8 767 17.2916 9 531 17.3205 10 546 17.4642 Query Time= 6.1101e-05 (sec), 0.061101 (msec) Average Query Time= 6.1101e-05 (sec), 0.061101 (msec), (6.1101e-05/1)
検索を実施。で、こえまた同じ要領で結果のファイルを見ていきます。
ID,名前,武力,知力,政治,魅力,陸指,水指 -- 487,張悌,70,81,78,83,74,80 81,郝昭,85,76,70,83,80,76 572,杜預,70,85,80,81,86,83 287,朱桓,83,75,69,82,76,81 585,馬忠,73,70,74,73,81,75 45,王濬,71,79,70,78,81,90 21,閻柔,70,70,73,80,78,74 767,魯淑,70,76,77,73,70,75 531,程普,69,81,70,85,73,82 546,鄧艾,85,93,81,74,87,75
ふむふむ、こちらも期待通りの結果となっています。
どのパラメータも優秀な優等生揃いで、ゲームでいう太守を任せられそうな存在。（この層の将軍を太守に任命する是非についてはまた別の議論ということで・・・w）
全てのパラメータが "90" に近い武将を探す
さっきより高いレベルである、全パラメータが "90" に近いような、超エリート武将を検索します。
先ほど、やった "関羽" を探す行為にかなり近いような気もしていますがw
$ cat query04.tsv 90 90 90 90 90 90
同じ要領でクエリファイルを作って、、、
$ ngt search -n 10 sangokushi3 ./query04.tsv Query No.1 Rank ID Distance 1 451 16.3401 2 429 19.5704 3 424 21.2132 4 425 23.9792 5 686 24.0832 6 153 24.1454 7 546 24.5967 8 572 25.9037 9 286 26.2869 10 761 27.6767 Query Time= 6.2751e-05 (sec), 0.062751 (msec) Average Query Time= 6.2751e-05 (sec), 0.062751 (msec), (6.2751e-05/1)
検索！けんさくぅ〜！
ID,名前,武力,知力,政治,魅力,陸指,水指 -- 451,趙雲,98,84,80,93,87,83 429,孫策,91,85,74,89,82,96 424,孫堅,90,84,72,87,81,90 425,孫権,86,87,71,98,80,95 686,陸遜,80,95,87,88,71,99 153,姜維,91,92,72,85,88,75 546,鄧艾,85,93,81,74,87,75 572,杜預,70,85,80,81,86,83 286,周瑜,75,96,86,95,73,100 761,呂蒙,84,91,65,88,80,90
結果です。・・・関羽様がいない。
関羽様は "政治: 64" が 90 から離れているので、そこが距離を生んでいる気がしますね。
トップは、パラメータの合計値は全武将の中でも1位な上に、全パラメータが80以上と超エリート的な "趙雲" 様ということで、こちらも納得の結果に。
あと、こうやってみると、呉の将軍が、2〜5位までを占めるあたり、ハイクラスな部分の層の厚さを感じますね。
段々、本筋から話が逸れてきましたが、概ね、インプットに対する検索結果としては、期待通りの結果になっているように思います。
全体的にパラメータが低い割りに、なぜか魅力だけが高い武将を探す
最後に完全に興味本位なのですが、"魅力" 以外に良いパラメータがない武将（魅力値だけが高い武将）って、誰だろう、、、とw
$ cat query05.tsv 0 0 0 100 0 0
こんな感じで、魅力だけ 100 でそれ以外は 0 というかなり偏ったパラメータのクエリファイルを作成し、、、
$ ngt search -n 5 sangokushi3 ./query05.tsv Query No.1 Rank ID Distance 1 720 59.5315 2 378 66.8655 3 484 72.581 4 106 77.3499 5 8 78.6956 Query Time= 7.7432e-05 (sec), 0.077432 (msec) Average Query Time= 7.7432e-05 (sec), 0.077432 (msec), (7.7432e-05/1)
検索しました。段々面倒くさくなってきたので結果は5件で・・・w
クエリとして与えたパラメータがかなり極端だったので、それなりに距離は離れてしまっていますね。
ID,名前,武力,知力,政治,魅力,陸指,水指 -- 720,劉禅,22,20,32,64,18,4 378,全尚,16,21,38,56,15,13 484,貂蝉,1,36,63,100,1,1 106,何進,39,10,39,71,40,20 8,尹大目,12,37,50,56,12,10
そんな中でも、トップは "劉禅" と。
なんか妙に納得させられる結果に。
3位の貂蝉は、まさにイメージにぴったりといえばぴったりですが、"政治:63" が距離を離している結果になっていますね。
2位の全尚って誰だったかな・・・ → 全尚 - Wikipedia
用意されているサブコマンド
公式ドキュメントにすべて記載がありますが、せっかくなのでサマっておきます。
まとめ
高次元ベクトル向けの特徴空間を対象とした検索ライブラリの検証に、6次元のデータを数百オブジェクト程度の使用で、たいした検証になっていない点は重々承知ですが、個人的には、割と馴染みのあるデータを使ったこともあり、正しそうな結果になっていそうな感じであるとは思いました。
正確には、自身で評価ツールを作って、個別にユークリッド距離（距離計算も他アルゴリズムを試すとかも）を測定した上で、再現率や適合率を指標に使って、検索精度とパフォーマンスを含めて評価すべきかとは思いますが、もう少し時間があるタイミングで、その辺まで踏み込んでみようかなと思っています。
一旦、カジュアルに使ってみた感じのまとめにはなりますが、何かのご参考になれば幸いです。
それでは！=͟͟͞͞(๑•̀=͟͟͞͞(๑•̀д•́=͟͟͞͞(๑•̀д•́๑)=͟͟͞͞(๑•̀д•́
参考リンク
- 高次元ベクトルデータにおいて高速な近傍検索を実現するNGTの公開 - Yahoo! JAPAN Tech Blog
- 高次元ベクトルデータ検索技術「NGT」の性能と使い方の紹介 - Yahoo! JAPAN Tech Blog
- 高次元ベクトルデータ検索技術「NGT」のpythonライブラリ公開のお知らせ - Yahoo! JAPAN Tech Blog
- 高次元ベクトルデータ検索技術「NGT」のGo APIとサーバ機能のOSS公開 - Yahoo! JAPAN Tech Blog
- NGT -グラフ型インデックスによる近似近傍検索の基本- - Yahoo! JAPAN Tech Blog
- NGT - グラフの探索起点の選択方法 - - Yahoo! JAPAN Tech Blog
- NGT - 検索ロジックの詳細と実装方法 - - Yahoo! JAPAN Tech Blog
- NGT - 最適化グラフの生成方法 - - Yahoo! JAPAN Tech Blog
- 作者: 山田浩之,末永匡
- 出版社/メーカー: 技術評論社
- 発売日: 2014/09/25
- メディア: 単行本（ソフトカバー）
- この商品を含むブログ (4件) を見る
- 作者: Christopher D.Manning,Prabhakar Raghavan,Hinrich Schutze,岩野和生,黒川利明,濱田誠司,村上明子
- 出版社/メーカー: 共立出版
- 発売日: 2012/06/23
- メディア: 単行本
- 購入: 2人 クリック: 69回
- この商品を含むブログ (5件) を見る
