簡介

隨著深度學(xué)習(xí)的發(fā)展和普及，很多非結(jié)構(gòu)數(shù)據(jù)被表示為高維向量，并通過近鄰搜索來查找，實現(xiàn)了多種場景的檢索需求，如人臉識別、圖片搜索、商品的推薦搜索等。另一方面隨著互聯(lián)網(wǎng)技術(shù)的發(fā)展及5G技術(shù)的普及，產(chǎn)生的數(shù)據(jù)呈爆發(fā)式增長，如何在海量數(shù)據(jù)中精準(zhǔn)高效的完成搜索成為一個研究熱點，各路前輩專家提出了不同的算法，今天我們就簡單聊下當(dāng)前比較常見的近鄰搜索算法。

主要算法

Kd-Tree

K-dimension tree，二叉樹結(jié)構(gòu)，對數(shù)據(jù)點在k維空間（如二維 (x，y)，三維(x，y，z)，k維(x，y，z..)）中劃分。

構(gòu)建過程

確定split域的值(輪詢 or 最大方差)

確定Node-data的域值（中位數(shù) or 平均值）

確定左子空間和右子空間

遞歸構(gòu)造左右子空間

查詢過程

進行二叉搜索，找到葉子結(jié)點

回溯搜索路徑，進入其他候選節(jié)點的子空間查詢距離更近的點

重復(fù)步驟2，直到搜索路徑為空

性能

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

改進算法

Best-Bin-First：通過設(shè)置優(yōu)先級隊列（將“查詢路徑”上的結(jié)點進行排序，如按各自分割超平面與查詢點的距離排序）和運行超時限定（限定搜索過的葉子節(jié)點樹）來獲取近似的最近鄰，有效地減少回溯的次數(shù)。采用了BBF查詢機制后Kd樹便可以有效的擴展到高維數(shù)據(jù)集上。

Randomized Kd tree：通過構(gòu)建多個不同方向上的Kd tree，在各個Kd tree上并行搜索部分?jǐn)?shù)量的節(jié)點來提升搜索性能（主要解決BBF算法隨著Max-search nodes增長，收益減小的問題）

Hierarchical k-means trees

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

構(gòu)建過程：

隨機選擇兩個點，執(zhí)行k為2的聚類，用垂直于這兩個聚類中心的超平面將數(shù)據(jù)集劃分

在劃分的子空間內(nèi)進行遞歸迭代繼續(xù)劃分，直到每個子空間最多只剩下K個數(shù)據(jù)節(jié)點

最終形成一個二叉樹結(jié)構(gòu)。葉子節(jié)點記錄原始數(shù)據(jù)節(jié)點，中間節(jié)點記錄分割超平面的信息

搜索過程

從根節(jié)點開始比較，找到葉子節(jié)點，同時將路徑上的節(jié)點記錄到優(yōu)先級隊列中

執(zhí)行回溯，從優(yōu)先級隊列中選取節(jié)點重新執(zhí)行查找

每次查找都將路徑中未遍歷的節(jié)點記錄到優(yōu)先級隊列中

當(dāng)遍歷節(jié)點的數(shù)目達到指定閾值時終止搜索

性能

搜索性能不是特別穩(wěn)定，在某些數(shù)據(jù)集上表現(xiàn)很好，在有些數(shù)據(jù)集上則有些差

構(gòu)建樹的時間比較長，可以通過設(shè)置kmeans的迭代次數(shù)來優(yōu)化

LSH

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

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

若空間中兩點p和q之間的距離D(p,q)p1

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

審核編輯：劉清