高維空間逼近最近鄰評測

最近鄰方法是機(jī)器學(xué)習(xí)中一個(gè)非常流行的方法，它的原理很容易理解：鄰近的數(shù)據(jù)點(diǎn)是相似的數(shù)據(jù)點(diǎn)，更可能屬于同一分類。然而，在高維空間中快速地應(yīng)用最近鄰方法，卻是非常有挑戰(zhàn)性的工作。

全球最大的流媒體音樂服務(wù)商Spotify需要向上面的海量用戶推薦音樂，其中就用到了最近鄰方法。也就是在高維空間、大型數(shù)據(jù)集上應(yīng)用最近鄰方法。

由于維度高、數(shù)據(jù)規(guī)模大，直接應(yīng)用最近鄰方法并不可行，因此，最佳實(shí)踐是使用逼近方法搜索最近鄰。這方面有不少開源庫，比如Spotify開源的Annoy庫。Annoy庫的作者Erik Bernhardsson在開發(fā)Annoy的過程中發(fā)現(xiàn)，盡管有成百上千的使用逼近方法搜索最近鄰的論文，卻很少能找到實(shí)踐方面的比較。因此，Erik開發(fā)了ANN-benchmarks，用來評測逼近最近鄰（approximate nearest neighbor，ANN）算法。

評估的實(shí)現(xiàn)

Annoy Spotify自家的C++庫（提供Python綁定）。Annoy最突出的特性是支持使用靜態(tài)索引文件，這意味著不同進(jìn)程可以共享索引。

FLANN 加拿大英屬哥倫比亞大學(xué)出品的C++庫，提供C、MATLAB、Python、Ruby綁定。

scikit-learn 知名的Python機(jī)器學(xué)習(xí)庫scikit-learn提供了LSHForest、KDTree、BallTree實(shí)現(xiàn)。

PANNS 純Python實(shí)現(xiàn)。已“退休”，作者建議使用MRPT。

NearPy 純Python實(shí)現(xiàn)?；诰植棵舾泄＃↙ocality-sensitive hashing，簡稱LSH，一種降維方法）。

KGraph C++庫，提供Python綁定?；趫D（graph）算法。

NMSLIB (Non-Metric Space Library) C++庫，提供Python綁定，并且支持通過Java或其他任何支持Apache Thrift協(xié)議的語言查詢。提供了SWGraph、HNSW、BallTree、MPLSH實(shí)現(xiàn)。

hnswlib（NMSLIB項(xiàng)目的一部分） 相比當(dāng)前NMSLIB版本，hnswlib內(nèi)存占用更少。

RPForest 純Python實(shí)現(xiàn)。主要特性是不需要在模型中儲(chǔ)存所有索引的向量。

FAISS Facebook出品的C++庫，提供可選的GPU支持（基于CUDA）和Python綁定。包含支持搜尋任意大小向量的算法（甚至包括可能無法在RAM中容納的向量）。

DolphinnPy 純Python實(shí)現(xiàn)?；诔矫婢植棵舾泄Ｋ惴?。

Datasketch 純Python實(shí)現(xiàn)?；贛inHash局部敏感哈希算法。

PyNNDescent 純Python實(shí)現(xiàn)?；趉-近鄰圖構(gòu)造（k-neighbor-graph construction）。

MRPT C++庫，提供Python綁定?；谙∈桦S機(jī)投影（sparse random projection）和投票（voting）。

NGT: C++庫，提供了Python、Go綁定。提供了PANNG實(shí)現(xiàn)。

數(shù)據(jù)集

ANN-benchmarks提供了一些預(yù)先處理好的數(shù)據(jù)集。

結(jié)果

Erik提供了在AWS EC2機(jī)器（c5.4xlarge）上運(yùn)行測試的結(jié)果——跑了好幾天才跑完，費(fèi)用約100美元。

glove-100-angular

sift-128-euclidean

fashion-mnist-784-euclidean

gist-960-euclidean

nytimes-256-angular

glove-25-angular

從以上評測可以看出（越靠上、靠右，成績越好），幾乎在所有數(shù)據(jù)集上，排名前五的實(shí)現(xiàn)為：

HNSW（NMSLIB的低內(nèi)存占用版本），比Annoy快10倍。

KGraph位于第二，和HNSW的差距不算很大。和HNSW一樣，KGraph也是基于圖（graph）的算法。

SW-graph，源自NWSLIB的另一個(gè)基于圖的算法。

FAISS-IVF，源自Facebook的FAISS。

Annoy

在“評估的實(shí)現(xiàn)”一節(jié)中，我們看到，有不少使用局部敏感哈希（LSH）的庫。這些庫的表現(xiàn)都不是很好。在之前進(jìn)行的一次評測中，F(xiàn)ALCONN表現(xiàn)非常好（唯一表現(xiàn)優(yōu)良的使用局部敏感哈希的庫）。但是這次評測中，F(xiàn)ALCONN看上去退步得很厲害——原因未明。

從這次評測來看，基于圖的算法是當(dāng)前最先進(jìn)的算法（名列三甲的算法全都基于圖），特別是HNSW表現(xiàn)突出。