Nmslib高维空间最近邻逼近搜索算法介绍

业务场景

上一次介绍图像搜索的基本原理，现在记录下使用的数据包的问题。
查询图片先进行特征提取，使用一个向量来表示，之后使用该向量与数据库中所有的商品向量进行计算相似度指标，比如cos距离，欧式距离，汉明距离。
具体的取决于向量的形式，有的先用cnn提取特征向量，可以计算其cos距离，有的提取之后对其进行哈希编码，先用汉明距离进行粗排，之后按照欧式距离进行重排。
这里就面临这样的一个问题：

• 特征向量一般都是高维，使用暴力算法计算相似度的话会非常耗时，满足不了实际应用场景；

没有等你算完，使用者的心就哇凉哇凉的，没有耐心等待的，而使用淘宝拍立淘的时候，响应速度非常快，用户体验很好！
这个时候就需要考虑使用一些快速计算的方法——ANN。

ANN

一看到ANN，第一反应应该是人工神经网络，这里是Approximate Nearest Neighbor，近似邻居算法。
关于这方面的算法有很多，比如Annoy， scikit-learn ，hnswlib, nmslib等等。
几乎所有的ANN方法都是对全空间的划分，大多数使用的树模型，详细的介绍可以上网查询一下，这里介绍本人使用过的nmslib包讲解。

NMSLIB

项目地址：https://github.com/nmslib/nmslib
非度量空间库（NMSLIB）是一种高效的跨平台相似性搜索库和用于评估相似性搜索方法的工具包。核心库并没有任何第三方依赖。
NMSLIB是一个可扩展的库，这意味着可以添加新的搜索方法和距离函数。NMSLIB可以直接在C ++和Python中使用。此外，还可以构建一个查询服务器，可以从Java（或Apache Thrift支持的其他语言）中使用。
这里介绍python的使用方法。

实例

import nmslib as nms ## 构建索引 index = nms.init(method='hnsw', space='cosinesimil') __index = {} product_dict_path = JSON_PATH + '/product_cv.json' with open(product_dict_path, 'r') as f: for line in f: pid, feat = line.strip('\n').split('\t') # init knn data frame __index.setdefault(pid, json.loads(feat)) index.addDataPoint(pid, json.loads(feat)) # set knn parameter INDEX_TIME_PARAMS = { 'indexThreadQty': 10, 'M': 100, 'efConstruction': 2000, 'post': 2} index.createIndex(self.INDEX_TIME_PARAMS) ## 使用 pids_index, distance = index.knnQuery(q_feat, k)

上述代码只是片段，详细讲解下各个参数的设置

• method : `hnsw'方法;
• space: 'cosinesimil'空间;
• INDEX_TIME_PARAMS: 详细参数

关于参数的设置可以见

• https://github.com/nmslib/nmslib/blob/master/python_bindings/parameters.md

参考

• 高维空间最近邻逼近搜索算法评测;
• 图像检索：再叙ANN Search;
• nmslib文档