簡介

隨著深度學習的發展和普及，很多非結構資料被表示為高維向量，並通過近鄰搜尋來查詢，實現了多種場景的檢索需求，如人臉識別、圖片搜尋、商品的推薦搜尋等。另一方面隨著網際網路技術的發展及5G技術的普及，產生的資料呈爆發式增長，如何在海量資料中精準高效的完成搜尋成為一個研究熱點，各路前輩專家提出了不同的演算法，今天我們就簡單聊下當前比較常見的近鄰搜尋演算法。

 

主要演算法

Kd-Tree

K-dimension tree，二叉樹結構，對資料點在k維空間（如二維 (x，y)，三維(x，y，z)，k維(x，y，z..)）中劃分。

 

構建過程

1. 確定split域的值(輪詢 or 最大方差)
2. 確定Node-data的域值（中位數 or 平均值）
3. 確定左子空間和右子空間
4. 遞迴構造左右子空間

 

查詢過程

1. 進行二叉搜尋，找到葉子結點
2. 回溯搜尋路徑，進入其他候選節點的子空間查詢距離更近的點
3. 重複步驟2，直到搜尋路徑為空

 

效能

理想情況下的複雜度是O(K log(N)) 最壞的情況下（當查詢點的鄰域與分割超平面兩側的空間都產生交集時，回溯的次數大大增加）的複雜度為維度比較大時，直接利用K-d樹快速檢索（維數超過20）的效能急劇下降，幾乎接近線性掃描。

 

改進演算法

Best-Bin-First：通過設定優先順序佇列（將“查詢路徑”上的結點進行排序，如按各自分割超平面與查詢點的距離排序）和執行超時限定（限定搜尋過的葉子節點樹）來獲取近似的最近鄰，有效地減少回溯的次數。採用了BBF查詢機制後Kd樹便可以有效的擴充套件到高維資料集上 。

 

Randomized Kd tree：通過構建多個不同方向上的Kd tree，在各個Kd tree上並行搜尋部分數量的節點來提升搜尋效能（主要解決BBF演算法隨著Max-search nodes增長，收益減小的問題）

 

Hierarchical k-means trees

類似k-means tree，通過聚類的方法來建立一個二叉樹來使得每個點查詢時間複雜度是O(log n) 。

 

構建過程 ：

1. 隨機選擇兩個點，執行k為2的聚類，用垂直於這兩個聚類中心的超平面將資料集劃分
2. 在劃分的子空間內進行遞迴迭代繼續劃分，直到每個子空間最多隻剩下K個數據節點
3. 最終形成一個二叉樹結構。葉子節點記錄原始資料節點，中間節點記錄分割超平面的資訊

 

 

搜尋過程

• 從根節點開始比較，找到葉子節點，同時將路徑上的節點記錄到優先順序佇列中

• 執行回溯，從優先順序佇列中選取節點重新執行查詢

• 每次查詢都將路徑中未遍歷的節點記錄到優先順序佇列中
• 當遍歷節點的數目達到指定閾值時終止搜尋

 

效能

• 搜尋效能不是特別穩定，在某些資料集上表現很好，在有些資料集上則有些差
• 構建樹的時間比較長，可以通過設定kmeans的迭代次數來優化

 

LSH

Locality-Sensitive Hashing 高維空間的兩點若距離很近，他們雜湊值有很大概率是一樣的；若兩點之間的距離較遠，他們雜湊值相同的概率會很小 。

 

一般會根據具體的需求來選擇滿足條件的hash函式，(d1,d2,p1,p2)-sensitive 滿足下面兩個條件（D為空間距離度量,Pr表示概率）：

 

• 若空間中兩點p和q之間的距離D(p,q)<d1，則Pr(h(p)=h(q))>p1
• 若空間中兩點p和q之間的距離D(p,q)>d2，則Pr(h(p)=h(q))<p2

離線構建索引

1. 選擇滿足(𝑅,𝑐𝑅,𝑃1,𝑃2)-sensive的雜湊函式；
2. 根據對查詢結果的準確率（即相鄰的資料被查詢到的概率）確定雜湊表的個數𝐿， 每個table內的hash functions的個數（也就雜湊的鍵長𝐾），以及跟LSH hash function 自身有關的引數 ；
3. 利用上面的雜湊函式組，將集合中的所有資料對映到一個或多個雜湊表中，完成索引 的建立。

 

線上查詢

1. 將查詢向量𝑞通過雜湊函式對映，得到相應雜湊表中的編號
2. 將所有雜湊表中相應的編號的向量取出來，（保證查詢速度，通常只取前2𝐿）
3. 對這2𝐿個向量進行線性查詢，返回與查詢向量最相似的向量。

 

查詢耗時主要為：

計算q的hash值（table id）+ 計算q與table中點的距離

 

查詢效果方面由於損失了大量原始資訊從而降低檢索精度 。

 

PQ

product quantization，把原來的向量空間分解為若干個低維向量空間的笛卡爾積，並對分解得到的低維向量空間分別做量化（quantization），這樣每個向量就能由多個低維空間的量化code組合表示 。

 

需要選取最優的量化演算法，我們熟知的k-means演算法就是一個接近最優化的量化演算法。

 

量化

使用k-means進行量化的過程

 

1. 將原始向量切分為m組，每組內使用k-means聚類，產出m組，每組多個聚類中心
2. 將原始向量編碼為m維向量，向量中每個元素代表所在組聚類中心的id

 

查詢過程

1. 將搜尋query劃分子向量，計運算元向量和對應段的所有簇心的距離，得到距離表（m×k*矩陣）
2. 遍歷樣本庫中的向量，根據距離表，計算每個樣本與查詢向量的距離和返回k個距離最接近的樣本

 

距離計算

SDC(symmetric distance computation)，對稱的距離計算方法，對query向量和樣本庫中的向量都進行PQ量化，同時會在構建階段會計算出每組向量各個聚類中心的距離，生成k*k的距離表，在查詢階段計算query向量和樣本庫中的向量時，通過查表即可，減少計算過程，但放大了誤差。

 

ADC(Asymmetric distance computation)，非對稱的距離計算方案，只對樣本庫中的向量進行PQ量化，在查詢階段計算query向量和m組聚類中心的距離，生成m*k的距離表，然後查表計算與樣本庫中向量的距離，由於需要每次對查詢向量實時計算，增加計算開銷，但誤差小。

 

優化

IVFPQ，基於倒排的乘積量化演算法，增加粗量化階段，對樣本進行聚類，劃分為較小的region ，減少候選集資料量（之前是需要遍歷全量的樣本，時間複雜度為O(N*M)）。

 

HNSW

在NSW演算法之上進行改進的基於圖的演算法，使用分層的結構，在每層通過啟發式方法來選擇某節點的鄰居（保證全域性連通性），使其構成一張連通的圖。

 

建圖流程

1. 計算節點的最大層次l；
2. 隨機選擇初始入口點ep，L為ep點所在的最大層；
3. 在L～l+1層，每層執行操作：在當前層找到距離待 插節點最近的節點ep，並作為下一層的輸入；
4. l層以下為待插元素的插入層，從ep開始查詢距離待插元素 最近的ef個節點，從中選出M個與待插節點連線，並將這M 個節點作為下一層的輸入；
5. 在l-1～0層，每層執行操作：從M個節點開始搜尋，找 到距離與待插節點最近的ef個節點，並選出M個與待插元素連線

 

查詢流程

1. 從頂層到倒數第二層，迴圈執行操作：在當前層尋找距離查詢節點最近的一個節點放入候選集中，從候選集中選取出距離查詢節點最近的一個節作為下一層的入口點；
2. 從上層得到的最近點開始搜尋最底層，獲取ef個近鄰點放入候選集中；
3. 從候選集中選取出topk 。

 

實現

當前有比較成熟的庫實現了各種主流的近鄰搜尋演算法，在專案中可以通過這些基礎庫來構建對應的近鄰搜尋服務，其中使用比較廣泛的是faiss庫，由Fackbook開源，在支援不同演算法的同時，也支援在超大規模資料集上構建k近鄰搜尋以及支援GPU來加速索引構建和查詢，同時社群活躍，在考慮到效能和可維護性，faiss庫是構建近鄰檢索服務的比較好的選擇。

總結

本文展示了當前比較常見的幾種近鄰搜尋演算法，並簡單分析了各演算法的原理；隨著深度學習的不斷髮展，不同場景對近鄰搜尋的需求越來越多，必定會有新的演算法不斷地湧現，每種演算法有它適合的場景，在選擇不同演算法時需要結合業務的需求，如資料量的大小，召回的效果，效能，資源消耗等各方面的因素，通過了解不同演算法的實現，可以選擇更適合當前業務的演算法。

 

 

*文/張林

 關注得物技術，每週一三五晚18:30更新技術乾貨
要是覺得文章對你有幫助的話，歡迎評論轉發點贊～