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

趙 增，李明勇，胡航飛

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

0 引 言

數(shù)十年來(lái)，最近鄰居搜索（NNS）一直是一個(gè)熱門話題，它在數(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ū)域壓縮到高維度空間中的單個(gè)點(diǎn)，這些外部點(diǎn)使用64到512個(gè)外部維度。

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

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

近來(lái)，基于圖的方法引起了人們的極大關(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ù)集時(shí)，計(jì)算復(fù)雜性將成倍增加。許多研究人員轉(zhuǎn)向建立近似的kNN圖，但仍然很耗時(shí)。本文提出了一種新的基于圖的搜索方法，該方法可以應(yīng)用于各種基于圖的搜索算法中。經(jīng)實(shí)驗(yàn)驗(yàn)證，這種方法的搜索性能已經(jīng)超過(guò)了最新的搜索算法，在Trevi可以將查詢成本縮短40%以上，在Audio數(shù)據(jù)集上可以縮短50%以上。

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

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

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

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

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

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

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

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

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

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

2.2 查詢階段

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

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

3 實(shí)驗(yàn)結(jié)果分析

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

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

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

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

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

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

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

圖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 結(jié)束語(yǔ)

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