淺談實值向量的近鄰檢索方案

顧亞文

（金肯職業(yè)技術(shù)學(xué)院人工智能與信息工程學(xué)院，江蘇 南京 211156）

0 引言

半導(dǎo)體與互聯(lián)網(wǎng)技術(shù)的飛速發(fā)展使數(shù)據(jù)信息規(guī)模呈爆發(fā)性增長，并進一步推動了人工智能技術(shù)的進步。如何有效地從這些飛速增長的數(shù)據(jù)中挖掘有效的信息是一個非常重要的挑戰(zhàn)，而作為數(shù)據(jù)挖掘方案的前置技術(shù)——近鄰檢索問題（即如何從海量數(shù)據(jù)中找出與查詢數(shù)據(jù)最相近的一些數(shù)據(jù)）一直受到學(xué)術(shù)界與工業(yè)界的關(guān)注。

由于精確尋找最近向量的計算代價過高，因此現(xiàn)有研究聚焦于近似近鄰檢索問題，其嚴(yán)格定義如下：給定一個歐式空間E中的點集，包括個點，對進行一定的預(yù)處理，從而能夠快速返回與給定查詢點最接近的點，使（，）≤（1+）（，）。其中，為與最接近的點，、∈；為給定的距離度量函數(shù)；為某個預(yù)設(shè)常量。

在實際應(yīng)用中，通常需要找到最接近的若干個點（例如個），而非單個點；即關(guān)注近似近鄰檢索問題。在超過50年的發(fā)展過程中，三類方案（樹形索引、哈希散列以及近鄰圖）被證明適合于該問題，其總體思路如圖1 所示。該文對三類方案中的主流方案進行介紹。

圖1 三類主流方案總體思路

1 樹形方案

在近鄰檢索方案中，為了保證較高的檢索效率，三類方案都需要在實際檢索前對數(shù)據(jù)集進行較長時間的索引構(gòu)建工作；因此，描述1 個近鄰檢索方案須關(guān)注2 個問題：1） 如何構(gòu)建索引。2） 如何進行檢索。為方便起見，該文相關(guān)字母解釋如下：為向量的維度；為待檢索向量集合；為中維點的個數(shù)；為需要返回的結(jié)果個數(shù)。具體來說，樹形方案可按索引劃分方式進一步劃分為以下3 種類型。

1.1 基于平衡樹的樹形索引

樹形方案可追溯到標(biāo)量（即=1）下的經(jīng)典數(shù)據(jù)結(jié)構(gòu)。通過二分法可以在對數(shù)復(fù)雜度上找到有序數(shù)組中的某個值，即在1 個平衡二叉樹中對數(shù)次查詢即可找到葉子節(jié)點。受平衡樹思想的啟發(fā)，kd 樹最早為維向量構(gòu)造索引，可以將其視為平衡二叉樹的高維拓展。在構(gòu)造索引時，選擇向量的某一個維度進行劃分，然后隨著深度增加不斷變化選擇的維度，直至劃分的2 個子區(qū)域都不存在新的點。在檢索時，先根據(jù)每個維度的切分點坐標(biāo)來判斷深入方向，直至找到葉節(jié)點；再遞歸地回退，檢查現(xiàn)有找到的最近點與查詢節(jié)點為半徑所形成的超球體是否可能與父節(jié)點的另一子節(jié)點所形成的區(qū)域相交，如果相交，則移動到對應(yīng)子區(qū)域重復(fù)執(zhí)行上述操作，否則，向父節(jié)點繼續(xù)回退；當(dāng)回退至根節(jié)點時，即找到了最近鄰點。

當(dāng)較低而較高時，超球體相交的可能性較低；但維度上升時，出現(xiàn)相交的概率快速上升，從而使kd 樹近乎于普通的線性掃描。為應(yīng)對上述問題，Arya 等人提出使用優(yōu)先檢索策略，其索引構(gòu)建過程與kd 樹相同；而在檢索時，維護1 個優(yōu)先隊列，先將根節(jié)點放入優(yōu)先隊列，再重復(fù)以下步驟：1） 從隊列中找到高優(yōu)先級節(jié)點對應(yīng)的子樹，然后嘗試在該子樹中找到更好的最近子節(jié)點，并比較每個遇到的節(jié)點，從而盡可能更新優(yōu)先隊列。2） 當(dāng)優(yōu)先隊列為空時，將找到的節(jié)點視為最近子節(jié)點。通過限制優(yōu)先隊列的長度，可在盡可能保證精度的同時，避免檢索效率降至線性掃描。Silpa-Anan 等人進一步指出優(yōu)先搜索在返回較多結(jié)果時精度會大幅降低，并指出其原因是樹中的節(jié)點在優(yōu)先隊列中相互關(guān)聯(lián)，從而帶來誤差。為了避免該問題，他們提出利用多個搜索樹來共同查詢，每個搜索樹都為原始樹的一個隨機旋轉(zhuǎn)；他們還指出主成分分析降維后的樹可有效避免在某些不重要的維度上出現(xiàn)相交的情況。

1.2 基于聚類的樹形索引

受聚類方案的啟發(fā)，Nister 等人指出可以使用k 均值聚類并按照聚類中心對中的點進行劃分；而對每個小類又可繼續(xù)進行聚類劃分，直至每類中的點數(shù)量少于某個固定值。此時，中的點根據(jù)聚類中心自然地形成1 顆樹，檢索時通過與聚類中心進行距離度量來避免進入無用的子樹。后續(xù)工作結(jié)合該思路與優(yōu)先隊列的思想進一步編寫了開源庫FLANN，并成為OpenCV 中的重要組成工具。

1.3 結(jié)合支撐點技術(shù)的樹形索引

在度量空間的近鄰檢索問題中，由于缺少一般意義的坐標(biāo)，因此常常使用支撐點技術(shù)來加快最近鄰檢索。具體來說，先選出若干個支撐點，計算支撐點與中的點以及支撐點之間的距離；在檢索時，通過基本的三角不等式或托勒密不等式就可以快速確定大量中的點不可能成為最近鄰點，從而達到快速過濾的效果。

Arora 等人的工作綜合使用了包括支撐點技術(shù)在內(nèi)的多種想法，其索引構(gòu)建過程如下：首先，將點投影到希爾伯特曲線上，即將高維值降至一維希爾伯特曲線值，由于希爾伯特曲線可能會破壞部分相鄰性，因此，不完全使用維空間上的希爾伯特曲線，而分別使用部分維度生成多條希爾伯特曲線，以避免出現(xiàn)過度過濾的現(xiàn)象。其次，根據(jù)希爾伯特曲線值生成B+樹的非葉節(jié)點，使用支撐點技術(shù)計算節(jié)點與支撐點間的距離，并將距離值存放在生成的B+樹的葉子節(jié)點中。在檢索時，首先通過B+樹非葉節(jié)點過濾，此時也已隱含利用了希爾伯特曲線投影的過濾。其次，使用支撐點組成的不等式進一步過濾。最后，計算未被過濾掉的點的實際距離，以得到最終結(jié)果?？梢钥闯?，該方案充分考慮了多種已有方案的過濾手段，在提升檢索效率的同時，也導(dǎo)致了其參數(shù)設(shè)置變得復(fù)雜，且與硬件緊密相關(guān)。

2 哈希散列

與樹形索引不同，哈希類方案希望將中的點投影到鍵值對表中。其中，鍵常被稱為“桶號”，而值為在該桶中的向量ID 號；在檢索時，先計算檢索點所對應(yīng)的桶號，再對該桶號對應(yīng)的所有向量的實際距離進行度量。因此，哈希類方案一方面試圖尋找一種投影方式，使高維空間中相近的點投影至一維時，其桶號的值相同；另一方面，還需要考慮在確定投影方式后如何提高準(zhǔn)確率。

2.1 靜態(tài)綁定框架

單個投影函數(shù)無法保證較高的精度，因此通常隨機生成個同分布的投影函數(shù)，即在索引構(gòu)建時生成張表；在檢索時，得到每張表中查詢向量對應(yīng)的桶號，度量檢索向量與對應(yīng)桶中靠前的點的實際距離，以獲得結(jié)果。上述策略被稱為靜態(tài)綁定框架，其存在2 個明顯缺陷：1） 需要計算很多張表才能維持較好的精度，計算過于復(fù)雜。2） 如果所有桶中沒有足夠多的點，那么就無法完成近似k 近鄰檢索，須重新生成索引表。上述問題本質(zhì)上是由索引表在構(gòu)建完成后完全固定、缺少靈活性所造成的。

2.2 動態(tài)綁定框架

3 近鄰圖方案

上述2 種方案本質(zhì)上都是通過劃分空間來避免檢索時計算無意義的距離；然而，如果將中的點視作一個整體，那么這些點會構(gòu)成一張圖。近鄰圖類方案試圖通過僅在圖上計算來找到相近的點。

眾所周知，圖由若干點以及點上的邊組成。圖類方案中通常使用爬山算法來尋找近鄰點。具體來說，其遵循的思路是鄰居的鄰居很可能是鄰居；在檢索時，從隨機點或某個固定點出發(fā)，將距離較小的相鄰點放入一個優(yōu)先隊列中；然后不斷從優(yōu)先隊列中距離最小的點出發(fā)，尋找新的鄰居直至收斂到個固定值。因此，檢索的時間復(fù)雜度與2 個參數(shù)有關(guān)，即圖中每個點的平均出度、找到想要的點需要經(jīng)過的跳數(shù)。接下來主要介紹在圖方案中構(gòu)建索引的方法，默認(rèn)其在檢索時使用爬山算法或類似變體?，F(xiàn)有的方案主要基于4 種特殊的圖，即德勞內(nèi)圖、相對近鄰圖、可通航小世界網(wǎng)絡(luò)和單調(diào)搜索網(wǎng)絡(luò)。

3.1 德勞內(nèi)圖

德勞內(nèi)圖指如果圖中任意3 點兩兩相連，則其形成的外接圓中無點集中的其余點。德勞內(nèi)圖雖適用于爬山算法，但當(dāng)維度較高時，其十分接近于全連接圖，因而構(gòu)圖效率與檢索效率都較低。雖然如此，后續(xù)實用的圖結(jié)構(gòu)（例如K 近鄰圖）往往簡化自德勞內(nèi)圖。K 近鄰圖指圖中每個點與其最接近的個點相連。雖然這是一個檢索前可完成的工作，但與前方案類似，得到精確的K 近鄰圖計算代價過高。Dong 等人提出一種重要的近似K 近鄰圖生成方案。其核心思路是將自己的鄰居介紹給另一個鄰居：先隨機生成圖中的邊，然后不斷借助圖中所有點當(dāng)前的相鄰節(jié)點的相鄰節(jié)點信息進行更新，以得到更準(zhǔn)確的自身相鄰節(jié)點。該方案在數(shù)學(xué)上論證了這樣的迭代過程在很大程度上可以保證近鄰圖的精確性，其時間復(fù)雜度一般記為（）。

3.2 可通航小世界網(wǎng)絡(luò)

3.3 相對近鄰圖

在相對近鄰圖中，如果2 點間存在邊，則當(dāng)且僅當(dāng)該邊為半徑時，以兩端點為圓心做圓形成的交集空間內(nèi)無圖中其他點。相對近鄰圖的平均出度為常數(shù)，且僅與數(shù)據(jù)維度有關(guān)。MALKOV 等人在可通航小世界圖的基礎(chǔ)上，進一步結(jié)合了相對近鄰圖的思路對索引構(gòu)建的流程進行改進，即添加新節(jié)點時不完全按照最近距離連接，而是加上相對近鄰圖的約束，這帶來更多高質(zhì)量的“捷徑”。

3.4 單調(diào)搜索網(wǎng)絡(luò)

基于圖的方案通常需要將所有節(jié)點讀取至內(nèi)存中，因此所占資源較高；但由于這一類方案在效率與精度上表現(xiàn)出的顯著優(yōu)勢以及半導(dǎo)體技術(shù)的飛速進步，因此這一類方案更被工業(yè)界認(rèn)可。此外，近年來有乘積量化類方案可用于壓縮索引，以輔助快速檢索。可以將圖方案與這一類策略結(jié)合，以獲得資源與精度的權(quán)衡。最后，將三類方案的總體優(yōu)、缺點進行歸納，見表1。

表1 三類方案的總體優(yōu)劣分析

4 結(jié)語

該文針對近鄰檢索問題，從索引構(gòu)造方法與檢索流程上對現(xiàn)有的主流或經(jīng)典方案進行梳理。需要注意的是，各類方案在不同的現(xiàn)實維度中存在自身的優(yōu)勢，因此在實際應(yīng)用中需要根據(jù)數(shù)據(jù)的可能分布、計算機的性能等各項參數(shù)進行細致地分析。近鄰檢索仍是一個不斷發(fā)展的領(lǐng)域，希望該文能夠讓讀者從宏觀角度了解索引構(gòu)造思路。