介紹當(dāng)前比較常見(jiàn)的幾種近鄰搜索算法

簡(jiǎn)介

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

主要算法

Kd-Tree

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

構(gòu)建過(guò)程

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

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

確定左子空間和右子空間

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

查詢過(guò)程

進(jìn)行二叉搜索，找到葉子結(jié)點(diǎn)

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

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

性能

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

改進(jìn)算法

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

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

Hierarchical k-means trees

類似k-means tree，通過(guò)聚類的方法來(lái)建立一個(gè)二叉樹(shù)來(lái)使得每個(gè)點(diǎn)查找時(shí)間復(fù)雜度是O(log n) 。

構(gòu)建過(guò)程：

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

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

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

搜索過(guò)程

從根節(jié)點(diǎn)開(kāi)始比較，找到葉子節(jié)點(diǎn)，同時(shí)將路徑上的節(jié)點(diǎn)記錄到優(yōu)先級(jí)隊(duì)列中

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

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

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

性能

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

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

LSH

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

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

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

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

審核編輯：劉清