趙 增，李明勇，胡航飛

（1 東華大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院，上海 201620；2 上海市計算機(jī)軟件評測重點(diǎn)實驗室，上海 200235）

0 引言

數(shù)十年來，最近鄰居搜索（NNS）一直是一個熱門話題，它在數(shù)據(jù)挖掘，機(jī)器學(xué)習(xí)和人工智能的許多應(yīng)用中發(fā)揮著重要作用。當(dāng)前，可用的數(shù)據(jù)集涵蓋了廣泛的應(yīng)用程序和數(shù)據(jù)類型，包括圖像、音頻、視頻、文本、合成和深度學(xué)習(xí)數(shù)據(jù)。SIFT、CIFAR 等圖像數(shù)據(jù)集是將局部圖像區(qū)域壓縮到高維度空間中的單個點(diǎn)，這些外部點(diǎn)使用64 到512 個外部維度。

計算高維向量之間的歐幾里得距離是NNS 的基本要求。由于維數(shù)災(zāi)難，NNS 本質(zhì)上很昂貴。具有n個數(shù)據(jù)點(diǎn)并在n維空間Rd中查詢q的數(shù)據(jù)集D，NNS的目的是找到最接近q的點(diǎn)o*∈D。其中，o*稱為q的最近鄰居。定義如式（1）：

通常，最接近查詢點(diǎn)q的K個點(diǎn)是從數(shù)據(jù)集中返回的，稱為K-最近鄰居搜索（K-NNS）。查找kNN 集的簡單方法是計算查詢q與數(shù)據(jù)集D中每個點(diǎn)之間的距離，并選擇距離最小的點(diǎn)。當(dāng)處理稀疏數(shù)據(jù)時，可以通過高級索引結(jié)構(gòu)（例如，反向索引）有效地計算NNS。但是，對于具有密集特征的數(shù)據(jù)，查找NNS 的成本為O（n）。當(dāng)數(shù)據(jù)集很大時，耗時嚴(yán)重。對于高維NNS，由于難以找到準(zhǔn)確的結(jié)果，大多轉(zhuǎn)向NNS 的近似版本，即近似k最近鄰搜索（K-ANNS），在近二十年中已被廣泛使用。

近來，基于圖的方法引起了人們的極大關(guān)注。例如NSG［1］、HNSW［2］、EFANNA［3］和FANNG［4］等方法?；趫D的方法離線構(gòu)造kNN 圖，可以將其視為高維空間中的大型網(wǎng)絡(luò)圖。使用基于圖的方法所面臨的挑戰(zhàn)是精確kNN 圖的高構(gòu)造復(fù)雜性，尤其是涉及大型數(shù)據(jù)集時，計算復(fù)雜性將成倍增加。許多研究人員轉(zhuǎn)向建立近似的kNN 圖，但仍然很耗時。本文提出了一種新的基于圖的搜索方法，該方法可以應(yīng)用于各種基于圖的搜索算法中。經(jīng)實驗驗證，這種方法的搜索性能已經(jīng)超過了最新的搜索算法，在Trevi 可以將查詢成本縮短40%以上，在Audio 數(shù)據(jù)集上可以縮短50%以上。

1 鄰居選擇對網(wǎng)絡(luò)搜索質(zhì)量的影響

在圖網(wǎng)絡(luò)上，每個點(diǎn)都擁有若干個鄰居，例如圖1（a）中，O1的鄰居擁有4 個結(jié)點(diǎn)，點(diǎn)q是查詢點(diǎn)。圖1（b）中，O1、O2互為鄰居。因此若干個此類結(jié)點(diǎn)組合將構(gòu)建成圖網(wǎng)絡(luò)。

圖1 鄰居和圖網(wǎng)絡(luò)Fig.1 Neighbor and Graph Network

在早期基于圖的方法中，圖上各個點(diǎn)使用精確的鄰居點(diǎn)作為鄰居集合，但由于構(gòu)建精確kNN 圖的計算成本很高，因此許多研究人員轉(zhuǎn)向構(gòu)建近似的kNN 圖，即選擇近似最近鄰作為鄰居集合。圖上的每個結(jié)點(diǎn)都可能未連接到其實際鄰居，而是連接到其近似鄰居。此類方法盡管可以極大地提高索引構(gòu)建速度，但可能會影響搜索精度。實際上，在EFANNA 中的實驗結(jié)果證明，低精度的近似kNN 圖仍然表現(xiàn)良好。這是因為EFANNA 構(gòu)造的近似kNN 圖的“錯誤”鄰居實際上是更遠(yuǎn)的鄰居。這些更遠(yuǎn)的鄰居在搜索過程中扮演“高速公路”角色，這使搜索路徑更快地到達(dá)查詢點(diǎn)的鄰域。

為了減少在圖上搜索的時間，構(gòu)造一個近似的kNN 圖通常需要降低圖的出度。在有向圖中，出度表示某個結(jié)點(diǎn)指向任意結(jié)點(diǎn)的邊連接數(shù)量的總和，入度則表示任意結(jié)點(diǎn)指向某個結(jié)點(diǎn)的邊連接數(shù)量的總和。通常，如果一個點(diǎn)具有較大的出度，那么它將成為kNN 圖的“交通樞紐”，這將增加搜索的復(fù)雜度。由此看來，從每個點(diǎn)的鄰居候選集中選擇最終鄰居變得尤為重要。一些比較先進(jìn)的算法使用有趣的邊緣選擇策略，例如MRNG［1］、RNG［5］，并取得了引人的效果。

2 基于鄰居聚類的搜索方法

由于構(gòu)建精確kNN 圖的成本非常高，因此基于圖的索引通常需要創(chuàng)建一個近似kNN 圖。在圖上，每個數(shù)據(jù)點(diǎn)都連接到它的k個近似最近鄰居。完成該算法需要二個階段：構(gòu)建圖索引階段和基于構(gòu)建索引的查詢階段。

2.1 索引構(gòu)建階段

同NSG 構(gòu)建網(wǎng)絡(luò)類似，使用NN 下降的方法構(gòu)建一個近似的kNN 圖，為圖上的每一個結(jié)點(diǎn)計算鄰居候選集，并設(shè)每個點(diǎn)的最大鄰居上限是R個。計算數(shù)據(jù)集的近似中心（各個維度求和取均值），對于圖上的某一結(jié)點(diǎn)e，從中心結(jié)點(diǎn)開始，使用貪婪搜索算法直到找到該結(jié)點(diǎn)e。在搜索過程中，所有和點(diǎn)e發(fā)生歐氏距離計算的點(diǎn)，將被放入候選集合中。最后使用MRNG 的邊緣選擇策略，將鄰居集合篩選至R以下。為了查詢階段的快速搜索，將鄰居集合進(jìn)行K-means聚類。如圖2 所示，點(diǎn)p擁有7 個鄰居，和點(diǎn)p具有相似角度的鄰居將被聚為一類。使用每個鄰居點(diǎn)和點(diǎn)p之間的余弦距離來聚類，余弦距離相似的點(diǎn)將被聚為一類。若指定聚類個數(shù)K＝4，那么所有的鄰居將被聚為4 類，C1、C2、C3 和C4 為聚類中心。這樣在圖上每個結(jié)點(diǎn)的鄰居集合將被分為4 類，這些聚類信息被保留并將在查詢階段使用。

圖2 鄰居集合的聚類過程Fig.2 Neighbor set clustering process

2.2 查詢階段

本文對基于傳統(tǒng)的貪婪搜索算法進(jìn)行改進(jìn)，使用隨機(jī)方法初始化候選集。由于所有結(jié)點(diǎn)的鄰居集合都在索引階段進(jìn)行聚類，因此可以指定在搜索過程中要檢查的聚類數(shù)k＇。在圖3 中，聚類K的數(shù)目為3，點(diǎn)1 和點(diǎn)2 在兩個不同的聚類中，點(diǎn)3 和點(diǎn)4 在同一聚類中。當(dāng)?shù)鹗键c(diǎn)為p時，計算點(diǎn)p的3 個聚類中心和查詢點(diǎn)q之間的角度（用余弦相似度代替）。如果指定k＇＝2（k＇＜＝K），并且a1、a2、a3的角度分別為30°、100°、120°，則只需要檢查點(diǎn)2、3、4。其原因是，點(diǎn)1 所在的聚類中心和查詢點(diǎn)q之間的角度太大，則不必計算。反之，如果檢查太多的聚類，那么必然會增加計算成本。如果k＇＝K，算法就需要檢查所有鄰居集合中的所有點(diǎn)，那么將失去構(gòu)造包含聚類信息圖的意義。如果檢查的聚類太少，即使可以降低計算成本，也很難實現(xiàn)高精度。使用此方法一直迭代檢查整個圖網(wǎng)絡(luò)，最終查詢路徑會在查詢點(diǎn)的鄰域附近收縮，迭代次數(shù)和查詢輪次的個數(shù)有關(guān)。圖3 中橘黃色曲線代表查詢點(diǎn)q的最近鄰鄰域，鄰域內(nèi)有極有可能包含點(diǎn)q的真實最近鄰。合理的檢查聚類個數(shù)將降低成本并實現(xiàn)高精度。通過調(diào)整參數(shù)可以很容易獲得要檢查的最佳聚類個數(shù)。

圖3 基于角度的貪婪搜索算法Fig.3 Greedy-search algorithm based on angle

3 實驗結(jié)果分析

通過實驗，將對公共數(shù)據(jù)集進(jìn)行詳細(xì)分析，以證明本文方法的有效性。

實驗使用Audio 和Trevi 兩個數(shù)據(jù)集。Audio 是音頻數(shù)據(jù)集，Trevi 是圖像數(shù)據(jù)集。Audio 擁有192 維度的特征向量53 387 個，Trevi 擁有4 096 維度的特征向量99 900 個。在Audio 數(shù)據(jù)集的實驗中，統(tǒng)一使用獨(dú)立于數(shù)據(jù)集之外的200 個192 維的特征向量作為查詢。Trevi 數(shù)據(jù)集同樣使用200 個4 096維的特征向量作為查詢。程序代碼以C ++編寫，并由帶有“O3”選項的g++5.4 編譯。所有數(shù)據(jù)集上的實驗都是在配備i5-8300H CPU 和16GB 內(nèi)存的計算機(jī)上進(jìn)行的。

為了衡量不同算法的ANNS 性能，使用召回率和成本作為評估準(zhǔn)確性的標(biāo)準(zhǔn)。平均召回率和平均成本則是多個查詢點(diǎn)的結(jié)果求均值得到。給定一個查詢點(diǎn)，所有算法均應(yīng)返回k個點(diǎn)。需要比較這k個點(diǎn)中有多少個在真正的k個最近鄰居中。假設(shè)給定查詢返回的k個點(diǎn)的集合為R＇，而查詢的真實k個最近鄰居集合為R，則召回率定義如式（2）：

另一個績效評估指標(biāo)是成本。在查詢階段，將計算與查詢點(diǎn)進(jìn)行歐幾里德距離計算的點(diǎn)。假設(shè)數(shù)字為C，數(shù)據(jù)集中的點(diǎn)總數(shù)為N，則將成本定義為式（3）：

將HNSW 和NSG 兩種最新的圖算法來作為比較，以此來驗證實驗的高效性。HNSW 基于可導(dǎo)航小世界（NSW）［6］提出的分層圖結(jié)構(gòu)，是NSW 的改進(jìn)版本，并且在性能上有很大的提高。HNSW 具有多個實現(xiàn)版本，例如Faiss、Hnswlib。實驗中使用性能更好的Hnswlib 進(jìn)行比較。NSG 是基于kNN 圖的方法，其中該圖上每個點(diǎn)的鄰居集都通過MRNG 方法進(jìn)行裁剪。在查詢階段，每個查詢點(diǎn)都從相同的導(dǎo)航結(jié)點(diǎn)開始搜索。NSG 可以很好地近似單調(diào)的搜索路徑。此外，NSG 在淘寶（阿里巴巴集團(tuán)）的電子商務(wù)搜索場景中顯示出卓越的性能，并已以十億個結(jié)點(diǎn)的規(guī)模集成到其搜索引擎中。

通過在搜索階段增加候選集列表的長度來增加召回率，可以得出一些有趣的結(jié)論。

實驗中，統(tǒng)一比較在高精度下（99%以上），對比3 種方法的查詢成本。通過驗證，相同召回率下，本文的方法需要更少的查詢成本。圖4 是Audio 和Trevi 兩個數(shù)據(jù)集上的召回率（Recall）和成本（cost）的對應(yīng)曲線。為了方便比較，cost 直接使用查詢點(diǎn)的訪問個數(shù)，200 個查詢點(diǎn)取平均作為性能評估指標(biāo)。圖中展示的是top20 的結(jié)果（求前20 近鄰）。在Audio 數(shù)據(jù)集的Recall 達(dá)到99.75%以上時，本文方法所需要的cost 低于其它二種方法。同理，在Trevi 數(shù)據(jù)集的Recall 達(dá)到98%以上時，同樣得到類似的效果。圖5 展示的是，在其它參數(shù)不變的情況下，3 種方法求top50 的結(jié)果。從實驗結(jié)果可以看出，本文的方法依然展示出優(yōu)越的性能。通過Trevi 數(shù)據(jù)集可以看出，高維度的數(shù)據(jù)集在本文方法上依然有效。

圖5 3 種算法的召回率-成本曲線（Top50）Fig.5 The recall-cost curves of three algorithms

3 結(jié)束語

本文提出了一種新的近似最近鄰搜索算法，該算法可以在基于圖的算法上縮短搜索時間并降低計算成本。該方法是基于kNN 圖構(gòu)造的，為了從與查詢點(diǎn)的角度引導(dǎo)查詢路徑，預(yù)先根據(jù)角度對所有點(diǎn)的鄰居進(jìn)行聚類，并且在搜索階段僅比較一些靠近查詢點(diǎn)的點(diǎn)的聚類。通過大量實驗，該方法在Audio 和Trevi 等數(shù)據(jù)集上，與現(xiàn)存的先進(jìn)算法NSG和HNSW 對比可以達(dá)到50%和40%的成本縮減。