高次元ベクトルデータの近傍検索を「NGT」で試してみる

三国志のゲームの武将データを(サンプルに)使った近傍検索を、検索ライブラリ「NGT」を使って、試してみた話です。

More from Liverpool Cathedral

ひょんなことから、久しぶりに高次元(多次元)ベクトルのデータを扱うことになりました。(もとい仕事で扱うことにしました。)

というのも、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

用意されているサブコマンド

公式ドキュメントにすべて記載がありますが、せっかくなのでサマっておきます。

  • create
    • インデックスの作成
  • append
    • インデックスにオブジェクトを追加登録
  • search
    • インデックスを使って検索
  • remove
    • インデックスからオブジェクトを削除
  • prune
    • インデックスのグラフ中の長いエッジを削減
  • reconstruct graph
    • グラフを再構成したインデックスの作成

まとめ

高次元ベクトル向けの特徴空間を対象とした検索ライブラリの検証に、6次元のデータを数百オブジェクト程度の使用で、たいした検証になっていない点は重々承知ですが、個人的には、割と馴染みのあるデータを使ったこともあり、正しそうな結果になっていそうな感じであるとは思いました。

正確には、自身で評価ツールを作って、個別にユークリッド距離(距離計算も他アルゴリズムを試すとかも)を測定した上で、再現率や適合率を指標に使って、検索精度とパフォーマンスを含めて評価すべきかとは思いますが、もう少し時間があるタイミングで、その辺まで踏み込んでみようかなと思っています。

一旦、カジュアルに使ってみた感じのまとめにはなりますが、何かのご参考になれば幸いです。

それでは!=͟͟͞͞(๑•̀=͟͟͞͞(๑•̀д•́=͟͟͞͞(๑•̀д•́๑)=͟͟͞͞(๑•̀д•́