顧亞文

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

0 引言

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

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

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

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

1 樹形方案

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

1.1 基于平衡樹的樹形索引

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

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

1.2 基于聚類的樹形索引

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

1.3 結合支撐點技術的樹形索引

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

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

2 哈希散列

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

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

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

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

3 近鄰圖方案

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

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

3.1 德勞內圖

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

3.2 可通航小世界網絡

3.3 相對近鄰圖

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

3.4 單調搜索網絡

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

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

4 結語

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