近鄰搜索算法淺析

語言: CN / TW / HK

簡介

隨着深度學習的發展和普及,很多非結構數據被表示為高維向量,並通過近鄰搜索來查找,實現了多種場景的檢索需求,如人臉識別、圖片搜索、商品的推薦搜索等。另一方面隨着互聯網技術的發展及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更新技術乾貨
要是覺得文章對你有幫助的話,歡迎評論轉發點贊~