趙 增,李明勇,胡航飛
(1東華大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,上海 201620;2上海市計(jì)算機(jī)軟件評(píng)測(cè)重點(diǎn)實(shí)驗(yàn)室,上海 200235)
數(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%以上。
在圖網(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],并取得了引人的效果。
由于構(gòu)建精確kNN圖的成本非常高,因此基于圖的索引通常需要?jiǎng)?chuàng)建一個(gè)近似kNN圖。在圖上,每個(gè)數(shù)據(jù)點(diǎn)都連接到它的k個(gè)近似最近鄰居。完成該算法需要二個(gè)階段:構(gòu)建圖索引階段和基于構(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
本文對(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
通過(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
本文提出了一種新的近似最近鄰搜索算法,該算法可以在基于圖的算法上縮短搜索時(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%的成本縮減。