近似最近邻 (ANN) 搜索在深度学习中用于最佳猜测给定集合中与另一点最相似的点。本文解释了 ANN 搜索与传统搜索方法之间的区别，并介绍了 NGT，这是一个由 Yahoo! Japan Research 开发的顶尖开源 ANN 库。
高维数据的最近邻搜索
不同的搜索方法用于不同的数据类型。例如，全文搜索用于文本数据，基于内容的图像检索用于图像，关系数据库用于数据关系。深度学习模型可以轻松地从各种数据中生成向量，从而使向量空间在源数据之间具有嵌入式关系。这意味着如果两个源数据相似，则来自这两个数据的向量将位于向量空间中彼此附近。因此，您所要做的就是搜索向量而不是源数据。
此外，向量不仅代表源数据的文本和图像特征，还代表产品、人类、组织等等。因此，您可以搜索相似的文档和图像，以及具有相似属性的产品、具有相似技能的人、具有相似特征的服装等等。例如，Yahoo! Japan 使用 NGT 提供基于相似性的时尚物品搜索。
由于深度学习模型中的维度数量趋于增加，因此当搜索超过数百万个高维向量时，ANN 搜索方法是必不可少的。ANN 搜索方法允许您在高维空间中搜索指定查询向量的邻居。
有许多最近邻搜索方法可供选择。 ANN Benchmarks 评估了最著名的 ANN 搜索方法，包括 Faiss (Facebook)、Flann 和 Hnswlib。根据此基准测试，NGT 实现了顶级的性能。
NGT 算法
NGT 索引结合了图和树。这种组合实现了非常好的搜索性能，其中图的顶点代表可搜索的对象。相邻的顶点通过边连接。
此动画展示了图是如何构建的。
在搜索过程中，可以通过下降图来找到指定查询的相邻顶点。密集连接的顶点使用户能够有效地探索图。
NGT 提供了命令行工具，以及 C、C++ 和 Python API。本文重点介绍命令行工具和 Python API。
使用 NGT 命令行工具
Linux 安装
下载最新版本的 NGT ZIP 文件，并在 Linux 上使用以下命令安装：
unzip NGT-x.x.x.zip
cd NGT-x.x.x
mkdir build
cd build
cmake ..
make
make install由于 NGT 库默认安装在 /usr/local/lib(64) 中，请将该目录添加到搜索路径
export PATH="$PATH:/opt/local/bin"
export LD_LIBRARY_PATH="$LD_LIBRARY_PATH:/usr/local/lib"示例数据集生成
在搜索大规模数据集之前，您必须生成一个 NGT 数据集。例如，从 fastText 网站下载 fastText 数据集，然后使用以下命令将其转换为 NGT 注册格式：
curl -O https://dl.fbaipublicfiles.com/fasttext/vectors-english/wiki-news-300d-1M-subword.vec.zip
unzip wiki-news-300d-1M-subword.vec.zip
tail -n +2 wiki-news-300d-1M-subword.vec | cut -d " " -f 2- > objects.ssvObjects.ssv 是一个包含 100 万个对象的注册文件。文件中的一个对象被提取作为查询。
head -10000 objects.ssv | tail -1 > query.ssv索引构建
可以使用以下命令构建 ngt_index：
ngt create -d 300 -D c index objects.ssv-d 指定向量的维度数。-D c 表示使用余弦相似度。
近似最近邻搜索
可以使用以下命令搜索 ngt_index：
ngt search -n 10 index query.ssv-n 指定结果对象的数量。
搜索结果是：
Query No.1
Rank ID Distance
1 10000 0
2 21516 0.184495
3 201860 0.240375
4 71865 0.241284
5 339589 0.267265
6 485158 0.280977
7 7961 0.283865
8 924513 0.286571
9 28870 0.286654
10 395274 0.290466
Query Time= 0.000972628 (sec), 0.972628 (msec)
Average Query Time= 0.000972628 (sec), 0.972628 (msec), (0.000972628/1)有关更多信息，请参阅 NGT 命令行 README。
从 Python 使用 NGT
虽然 NGT 具有 C 和 C++ API，但 ngtpy Python 绑定是编程最简单的选择。
安装 ngtpy
通过 PyPI 安装 Python 绑定 (ngtpy)：
pip3 install ngt示例数据集生成
使用此代码从您下载的示例数据集中为 Python 示例程序生成数据文件：
dataset_path = 'wiki-news-300d-1M-subword.vec'
with open(dataset_path, '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:])))索引构建
使用以下命令构建 NGT 索引：
import ngtpy
index_path = 'index'
with open('objects.tsv', 'r') as fin:
n, dim = map(int, fin.readline().split())
ngtpy.create(index_path, dim, distance_type='Cosine') # create an index
index = ngtpy.Index(index_path) # open the index
print('inserting objects...')
for line in fin:
object = list(map(float, line.rstrip().split('¥t')))
index.insert(object) # insert objects
print('building objects...')
index.build_index()
print('saving the index...')
index.save()
近似最近邻搜索
这是一个 ANN 搜索程序示例：
import ngtpy
print('loading words...')
with open('words.tsv', 'r') as fin:
words = list(map(lambda x: x.rstrip('¥n'), fin.readlines()))
index = ngtpy.Index('index', zero_based_numbering = False) # open index
query_id = 10000
query_object = index.get_object(query_id) # get the object for a query
result = index.search(query_object) # aproximate nearest neighbor search
print('Query={}'.format(words[query_id - 1]))
print('Rank¥tID¥tDistance¥tWord')
for rank, object in enumerate(result):
print('{}¥t{}¥t{:.6f}¥t{}'.format(rank + 1, object[0], object[1], words[object[0] - 1]))这是搜索结果，与 NGT 命令行选项的结果相同：
loading words...
Query=Horse
Rank ID Distance Word
1 10000 0.000000 Horse
2 21516 0.184495 Horses
3 201860 0.240375 Horseback
4 71865 0.241284 Horseman
5 339589 0.267265 Prancing
6 485158 0.280977 Horsefly
7 7961 0.283865 Dog
8 924513 0.286571 Horsing
9 28870 0.286654 Pony
10 395274 0.290466 Blood-Horse有关更多信息，请参阅 ngtpy README。
近似最近邻 (ANN) 原理是分析数据的重要特征。学习如何在您自己的项目中使用它，或理解您正在分析的数据，是建立关联和解释信息的强大方法。借助 NGT，您可以以任何您需要的方式使用 ANN，或者在其基础上添加自定义功能。
评论已关闭。