基于鄰居聚類的近似最近鄰搜索

趙 增，李明勇，胡航飛

（1東華大學 計算機科學與技術學院，上海 201620；2上海市計算機軟件評測重點實驗室，上海 200235）

0 引 言

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

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

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

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

1 鄰居選擇對網絡搜索質量的影響

在圖網絡上，每個點都擁有若干個鄰居，例如圖1（a）中，O1的鄰居擁有4個結點，點q是查詢點。圖1（b）中，O1、O2互為鄰居。因此若干個此類結點組合將構建成圖網絡。

圖1 鄰居和圖網絡Fig.1 Neighbor and Graph Network

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

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

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

由于構建精確kNN圖的成本非常高，因此基于圖的索引通常需要創建一個近似kNN圖。在圖上，每個數據點都連接到它的k個近似最近鄰居。完成該算法需要二個階段：構建圖索引階段和基于構建索引的查詢階段。

2.1 索引構建階段

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

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

2.2 查詢階段

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

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

3 實驗結果分析

通過實驗，將對公共數據集進行詳細分析，以證明本文方法的有效性。

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

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

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

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

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

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

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

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

3 結束語

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