高維空間最近鄰逼近搜索演算法評測
來源：GitHub
編譯：weakish
最近鄰方法是機器學習中一個非常流行的方法，它的原理很容易理解：鄰近的數據點是相似的數據點，更可能屬於同一分類。然而，在高維空間中快速地應用最近鄰方法，卻是非常有挑戰性的工作。
全球最大的流媒體音樂服務商Spotify需要向上面的海量用戶推薦音樂，其中就用到了最近鄰方法。也就是在高維空間、大型數據集上應用最近鄰方法。
由於維度高、數據規模大，直接應用最近鄰方法並不可行，因此，最佳實踐是使用逼近方法搜索最近鄰。這方面有不少開源庫，比如Spotify開源的Annoy庫。Annoy庫的作者Erik Bernhardsson在開發Annoy的過程中發現，儘管有成百上千的使用逼近方法搜索最近鄰的論文，卻很少能找到實踐方面的比較。因此，Erik開發了ANN-benchmarks，用來評測逼近最近鄰（approximate nearest neighbor，ANN）演算法。
評估的實現
Annoy Spotify自家的C++庫（提供Python綁定）。Annoy最突出的特性是支持使用靜態索引文件，這意味著不同進程可以共享索引。
FLANN 加拿大英屬哥倫比亞大學出品的C++庫，提供C、MATLAB、Python、Ruby綁定。
scikit-learn 知名的Python機器學習庫scikit-learn提供了、、實現。
PANNS 純Python實現。已「退休」，作者建議使用MRPT。
NearPy 純Python實現。基於局部敏感哈希（Locality-sensitive hashing，簡稱LSH，一種降維方法）。
KGraph C++庫，提供Python綁定。基於圖（graph）演算法。
NMSLIB (Non-Metric Space Library) C++庫，提供Python綁定，並且支持通過Java或其他任何支持Apache Thrift協議的語言查詢。提供了SWGraph、HNSW、BallTree、MPLSH實現。
hnswlib（NMSLIB項目的一部分） 相比當前NMSLIB版本，hnswlib內存佔用更少。
RPForest 純Python實現。主要特性是不需要在模型中儲存所有索引的向量。
FAISS Facebook出品的C++庫，提供可選的GPU支持（基於CUDA）和Python綁定。包含支持搜尋任意大小向量的演算法（甚至包括可能無法在RAM中容納的向量）。
DolphinnPy 純Python實現。基於超平面局部敏感哈希演算法。
Datasketch 純Python實現。基於MinHash局部敏感哈希演算法。
PyNNDescent 純Python實現。基於k-近鄰圖構造（k-neighbor-graph construction）。
MRPT C++庫，提供Python綁定。基於稀疏隨機投影（sparse random projection）和投票（voting）。
NGT: C++庫，提供了Python、Go綁定。提供了PANNG實現。
數據集
ANN-benchmarks提供了一些預先處理好的數據集。
結果
Erik提供了在AWS EC2機器（c5.4xlarge）上運行測試的結果——跑了好幾天才跑完，費用約100美元。
glove-100-angular
sift-128-euclidean
fashion-mnist-784-euclidean
gist-960-euclidean
nytimes-256-angular
glove-25-angular
從以上評測可以看出（越靠上、靠右，成績越好），幾乎在所有數據集上，排名前五的實現為：
HNSW（NMSLIB的低內存佔用版本），比Annoy快10倍。
KGraph位於第二，和HNSW的差距不算很大。和HNSW一樣，KGraph也是基於圖（graph）的演算法。
SW-graph，源自NWSLIB的另一個基於圖的演算法。
FAISS-IVF，源自Facebook的FAISS。
Annoy
在「評估的實現」一節中，我們看到，有不少使用局部敏感哈希（LSH）的庫。這些庫的表現都不是很好。在之前進行的一次評測中，FALCONN表現非常好（唯一表現優良的使用局部敏感哈希的庫）。但是這次評測中，FALCONN看上去退步得很厲害——原因未明。
從這次評測來看，基於圖的演算法是當前最先進的演算法（名列三甲的演算法全都基於圖），特別是HNSW表現突出。
原文地址：https://github.com/erikbern/ann-benchmarks
TAG:論智 |