実データでのPython利用例

ここでは大規模な実データを利用して、NGTの2つの主要なグラフ形式（ANNG、ONNG）の使い方を紹介します。

データセットの生成

大規模なデータを検索する方法を説明しますので、まず、データセットの準備をします。 以下のように fastText のデータをダウンロードします。

curl -O https://dl.fbaipublicfiles.com/fasttext/vectors-english/wiki-news-300d-1M-subword.vec.zip
unzip wiki-news-300d-1M-subword.vec.zip

以下のスクリプトで上記データセットをサンプルスクリプトが読めるような形式に変換します。

# dataset.py 
with open('wiki-news-300d-1M-subword.vec', 'r') as fi,\
     open('objects.tsv', 'w') as fov, open('words.tsv', 'w') as fow:
    n, dim = map(int, fi.readline().split())
    fov.write('{0}\t{1}\n'.format(n, dim))
    for line in fi:
        tokens = line.rstrip().split(' ')
        fow.write(tokens[0] + '\n')
        fov.write('{0}\n'.format('\t'.join(tokens[1:])))

ANNGインデックスの生成と検索

以下は距離関数にコサイン類似度を指定してANNGを構築する方法の例です。

# create-anng.py
import ngtpy

index_path = 'fasttext.anng'
with open('objects.tsv', 'r') as fin:
    n, dim = map(int, fin.readline().split())
    ngtpy.create(index_path, dim, distance_type='Cosine') # create an empty index
    index = ngtpy.Index(index_path) # open the index
    for line in fin:
        object = list(map(float, line.rstrip().split('\t')))
        index.insert(object) # insert objects
index.build_index() # build the index
index.save() # save the index

ANNGは以下のスクリプトで検索できます。

# search.py
import ngtpy

with open('words.tsv', 'r') as fin:
    words = list(map(lambda x: x.rstrip('\n'), fin.readlines()))

index = ngtpy.Index('fasttext.anng') # open the index
query_id = 10000
query_object = index.get_object(query_id) # get the object

result = index.search(query_object, epsilon = 0.15) # approximate nearest neighbor search
print('Query={}'.format(words[query_id]))
for rank, object in enumerate(result):
    print('{}\t{}\t{:.6f}\t{}'.format(rank + 1, object[0], object[1], words[object[0]]))

以下は検索結果です。

Query=Doctors
1       10000   0.000000        Doctors
2       4631    0.244096        Doctor
3       79542   0.258944        Medics
4       2044    0.263412        doctors
5       339397  0.274972        Doctoring
6       20667   0.280508        Physicians
7       80646   0.292580        Dentists
8       24255   0.292752        Nurses
9       9480    0.322195        Scientists
10      623160  0.330500        Practioners

高い精度が必要なときには、以下のようにデフォルト値の0.1より大きな値を epsilon に指定します。

index.search(query_object, epsilon = 0.15)

精度を犠牲にしても高速な検索が必要であれば、epsilon の値を小さくします。

ONNG生成用のANNGの生成

次に、より性能の向上が期待できるONNGを生成します。ONNGを生成する前にエッジが多いANNGを作成します。ONNGを生成するときにエッジが最適に削減されるので、エッジを多めにしておく必要があります。ただし、エッジが多すぎるとANNGの生成が遅くなります。以下は100のエッジでANNGを生成する例です。ほとんどのデータセットではエッジ数100は多すぎるので、データセットの検索精度を基にしてエッジ数を削減できます。

# create-anng-for-onng.py
import ngtpy

index_path = 'fasttst.anng-100'
with open('objects.tsv', 'r') as fin:
    n, dim = map(int, fin.readline().split())
    ngtpy.create(index_path, dim, distance_type='Cosine', edge_size_for_creation=100) # create an empty index                
    index = ngtpy.Index(index_path) # open the index 
    for line in fin:
        object = list(map(float, line.rstrip().split('\t')))
        index.insert(object) # insert objects
index.build_index() # build the index
index.save() # save the index

ANNGからONNGの生成

次のようにして、ONNGはngt.Optimizerを利用してANNGから変換できます。

import ngtpy

optimizer = ngtpy.Optimizer()
optimizer.set(num_of_outgoings = 10, num_of_incomings = 100)
optimizer.execute("fasttext.anng", "fasttext.onng")

execute() はパスの最適化と検索時の動的エッジ生成係数の最適化を行います。num_of_outgoings と num_of_incomings で、それぞれ、出力エッジと入力エッジの数を指定します。この例では入力エッジをANNG生成時のエッジ数と同じ100にしています。しかし、ANNGの実際のエッジ数は指定したエッジ数よりも多くなるので、入力エッジより大きな値を指定できます。

ONNGによる検索

search.pyの以下で'fasttext.anng'を 'fasttext.onng'に置き換えて実行してください。

index = ngtpy.Index('fasttext.onng') # open the index

ANNGと比較して検索時間が遅くなる場合があるかもしれませんが、検索精度が上がっているはずです。したがって、ANNG で高い精度を得るためにはsearch_range_coefficient を大きしなければならず、結果としてANNGの検索時間はONNGよりも増大します。