面向大規(guī)模數(shù)據集的索引學習算法研究

李 繁，嚴 星

(新疆財經大學，新疆 烏魯木齊 830012)

1 引言

在大規(guī)模數(shù)據集中使用窮舉搜索法是不可行的。因此，目前最近鄰搜索算法使用的非常廣泛，也帶來了許多新的挑戰(zhàn)及討論，眾多的算法都希望能在準確率、效能及內存使用等方面找到一個較好的平衡點。

在最近鄰搜索算法中，有兩種主要做法：數(shù)據量化與二元嵌入。在數(shù)據量化中，是通過一些分群算法，進行分群并得到各群群中心信息，再將所有數(shù)據分配至最鄰近的群中心。而在二元嵌入中，則是通過雜湊函數(shù)轉換至對應的二元碼當中。在這兩種方法的幫助下，不管是內存使用或是計算量都大幅降低。此外也可以利用這些群中心、二元碼，創(chuàng)建索引表或代碼表(codebook)，通過這些索引表可以快速篩選出最近的候選集。但存在的問題是，原始數(shù)據對應到索引表后有著無法避免的數(shù)據損失，導致搜索準確率下降。

為此，本文提出了面向大規(guī)模數(shù)據集的索引學習方法，依照近鄰概率去訪問各群使候選集信息更為精準。同時，通過事先計算出各大群中包含了多少最相關子群，也能有效的分散計算量。

2 相關研究

2.1 樹狀索引

樹狀索引結構技術廣泛使用在向量空間索引(vector space indexing)[1，2]，比較常見的如文獻[3]所使用的hierarchical k-means可以有效的降低搜索時間。

hierarchical k-means方法是先將數(shù)據進行第一次的k-means分群產生k個群中心(第一層)，再個別對這k個群中心內所包含的數(shù)據進行一次k-means分群，分為k個子群(第二層)，使總群數(shù)量可達到k2個。

2.2 二元碼嵌入

在處理大規(guī)模數(shù)據時，傳統(tǒng) tree-based方法(如：KD tree[5]，ball tree[6]，metric tree[7]，vantage point tree[8])往往會造成很大的內存負擔，在處理高維度數(shù)據集時，效率會急劇下降[9]。

二元碼嵌入提供了最簡潔的數(shù)據表示方式，二元碼轉換是通過哈希函數(shù)將數(shù)據投影至二元空間。二元碼嵌入方法主要可以分為兩種，一種是數(shù)據獨立性(Data-independent)。例如：kernelized LSH[10]與其中比較著名的 Locality Sensitive Hashing，LSH[11，12]，屬于數(shù)據獨立的哈希函數(shù)，通過高斯隨機分布的哈希矩陣，將原始空間相鄰點隨機投影至其它空間時，相鄰機會很大；反之不相鄰的點則會很少，此方法實現(xiàn)容易、速度快；不過檢索精度相對不那么準確。而另一種則為數(shù)據依賴性(Data-dependent)，需要依賴原始數(shù)據來學習哈希函數(shù)[13，14]。

二元嵌入方法優(yōu)點在于節(jié)省海量存儲器空間。如要將一數(shù)據庫中十億筆128維數(shù)據存入內存中，可能就得花費將近476GB的內存空間，若將其轉至二元空間，卻僅需花費14GB的內存空間。在二元空間內，將原始數(shù)據產生的二元碼作為索引，并建立反向索引表，搜索時只需要對索引值二元碼進行搜索即可。雖然二元碼嵌入在漢明空間里，計算上可以更快速，但也相對的無法避免數(shù)據距離計算不夠準確的問題。

2.3 乘積量化、非對稱距離計算

乘積量化(product quantization，簡稱PQ)在高維度空間上，是一個很有效率的有損壓縮技術。PQ把每個原始向量分解成各自的子向量，每個子向量再分別進行索引而產生多張不同的索引表；而各個原始向量將由量化后的子向量串聯(lián)代替而成。

非對稱距離計算通常用于最近鄰搜索法的第二階段，重新排序候選集名單，讓更相似的數(shù)據排在前面。非對稱距離計算是在查詢值不需進行量化的情況下，與各數(shù)據進行距離計算，來彌補量化誤差的問題，可以使候選集名單更精確。文獻[15]中提出了一個使用PQ有效計算非對稱距離的方式，將原始數(shù)據分解成不同的子向量，個別進行分群，產生不同的多張索引表。而在搜索時，不需將查詢值進行量化，只需計算查詢值與各個向量的距離總和，即可算出非對稱距離，再利用這些距離，重新排序候選集名單，讓搜索更為精確。

2.4 多重反向索引表

反向索引系統(tǒng)與非對稱距離計算(IVFADC)是個基于如何有效處理數(shù)十億筆數(shù)據集所產生的架構。采用了k-means進行粗略量化(coarser quantization)且有效的將殘差值運用在乘積量化中。非對稱距離計算(asymmetric distance computation，簡稱ADC)是為了應用在反向索引表中，快速的計算歐幾里得距離[16]。

多重反向索引表(inverted multi-index，簡稱IMI)使用了多維索引列表，各列表群中心是將原本的索引表分隔建構而成。多重序列比對算法被套用在IMI中。由于大量的群可將原本數(shù)據密集的分散于各群中，可以使得 IMI達到相當高的召回率(recall)。

3 算法描述

下面開始介紹所使用的分群結構，及如何利用類神經網絡模型找出查詢值與各群間的近鄰概率，再介紹如何有效利用這些近鄰概率，進行多層式的數(shù)據檢索。

假設有一個數(shù)據集包含了N個s維度的特征向量D={dn∈{R}s|n=1，2，…，N}。建構了一個擁有M群的索引結構{(Cm，Im)|m=1，2，…，M}而Cm則是第m群，且Im則是反向索引列表，紀錄了第m群所包含的索引內擁有的向量編號

Im={n|Z(dn)=Cm}

(1)

其中Z(dn)是量化函數(shù)，從而得到dn最接近的群。給予一個查詢值q，最典型利用索引結構的方法則是檢索出前R個最接近q的群中心信息，如下述表示

(2)

為了解決在索引結構里所產生的量化誤差問題，通過類神經網絡學習近鄰關系，而產生一個非線性模型函數(shù)f再將查詢點的原始數(shù)據作為類神經網絡的輸入，投入該模型當中，從而得到各群與查詢值的近鄰概率{pC1，pC2，…，pCM}，其中pCm代表第m群Cm與查詢值的近鄰概率

{pC1，pC2，…，pCM}=f(q)

(3)

接著依照各群的近鄰概率，由大至小進行排序，得到檢索順序R，前R個與查詢值q最相關的群中心信息

(4)

3.1 整體流程

3.1.1 預處理

Step 1：將數(shù)據使用k-means分成m群，并建立反向索引表Im。

Step 2：使用Im訓練類神經網絡模型Ω。

3.1.2 索引搜索

Step 1：通過式(5)先將查詢值q正規(guī)化，再將其投入類神經網絡模型Ω中，得到Cm各群預測的近鄰概率pm。

Step 3：利用總訪問數(shù)量T與Cr各群的近鄰概率計算出Cr該子群所需訪問數(shù)量。

Step 5：重復Step 3、Step 4，直到所取群數(shù)達到設定的閾值。

Step 6：進行非對稱距離計算，重新排序候選集名單，取出前i筆數(shù)據，當作最終候選集名單。

3.2 訓練模塊

(5)

由于查詢值為一個s維度的特征向量，將各個向量(各維度)分別進行標準化，讓輸入數(shù)據介于0與1之間，作為模型的輸入(Dmin、Dmax為數(shù)據庫里最小值、最大值)

(6)

(7)

通過訓練得到的類神經網絡模型，可用來敘述查詢值q與各群之間的近鄰關系。讓Ω表示訓練好的類神經網絡模型。Ω包含了一層輸入層，一層隱藏層與一層輸出層。每一層都為完全連接神經元。輸入層接收了s個特征向量(查詢的q標準化后結果)，輸出層則是m個機率值，相對應到m群的近鄰概率。

3.3 索引搜索

(8)

(9)

接著找Sr個最接近的子群：

PartialSort(subDistancesr[ ]，Sr)

(10)

3.4 非對稱距離計算

為了能讓候選集名單更加精確，使用非對稱距離計算，進行了第二次候選集的篩選。在數(shù)據預處理中，先將原始數(shù)據向量D切成n個子向量，再將各子向量進行量化分群(product quantizer pq)：

pq(D)=(pq1(D1)，pq2(D2)，…，pqn(Dn))

(11)

切割并個別進行分群后將會有n張不同的索引表(codebook)記錄群中心信息。再建立n張查找表(lookuptable)，分別記錄各個數(shù)據點在第n張表屬于哪一個群。最后在搜索時，只需將查詢值q切割成n個子向量，與候選集n個子向量所屬的群中心做距離計算，并總和得到非對稱距離：

(12)

最后再將候選集名單利用非對稱距離進行排序，取出前i筆(通常為1000筆)當作最終候選集信息

PartialSort(Distances[]，i)

(13)

4 實驗仿真結果

4.1 實驗數(shù)據與環(huán)境

實驗數(shù)據使用SIFT_1B，此數(shù)據庫包含10億筆128維度SIFT特征向量，提供1萬筆的查詢值Query數(shù)據與每筆查詢值的對應1000筆正確鄰居信息(正解)。使用8000筆query與正解作為類神經網絡的訓練數(shù)據，2000筆作為測試數(shù)據，總和1萬筆，測試數(shù)據將不會用于訓練數(shù)據內。實驗環(huán)境：Intel Core i7-5820 CPU @3.30GHz 128GB RAM，采用 C++與 Python 3.6編寫(使用 Keras套件編寫類神經網絡進行模型訓練、預測，使用CPU，無GPU加速)。

本實驗將十億筆特征數(shù)據取出一千萬筆作為分群訓練資料，經過hierarchical k-means clustering分群法，分為256×256群、1024×1024群以及4096×4096群。類神經網絡將套用在第一層上。類神經網絡的設計使用了一層輸入層、一層隱藏層、一層輸出層，每層都是完全連接神經元。第一層神經元數(shù)量為query特征向量數(shù)量128。第二層神經元數(shù)量為第一層的兩倍。第三層則為群中心數(shù)量256、1024、4096，代表各群近鄰概率。一到二層使用relu作為激活函數(shù)，最后一層則使用softmax使近鄰概率加總等于1。誤差函數(shù)使用交叉熵(cross-entropy)來計算標簽與從類神經網絡輸出的誤差。輸入為經過正規(guī)化后查詢值的特征向量，輸出為第一層k-means總群數(shù)量(代表各群的近鄰概率)。訓練次數(shù)為：epochs=295，batch_size=8。最后將所訓練出來的模型套用至搜索上，并與沒有使用模型的搜索結果進行比較。

4.2 實驗設計與結果

使用召回率(Recall)、精確率(Precision)來計算所挑選出的候選集質量。召回率為候選集名單所包含的正解數(shù)量。Top@R(Top-N Recall)則是代表候選集名單中包含了N個正解。著重于候選集的精度，所有實驗均以Top1000R作為比較對象。

以下實驗將沒有套用類神經網絡模型的實驗結果統(tǒng)稱為baseline，套用類神經網絡模型的結果統(tǒng)稱為probability。

4.2.1 單層取法

baseline方法為找出n個與查詢值距離最近的群，取出群內所有候選集數(shù)據當作搜索結果，計算出查詢值與各群的距離，并由小至大進行排序。probability方法則會將標準化后的查詢值query，使用類神經網絡模型Ω，計算出各群的近鄰概率，接著將各群的近鄰概率由大至小進行排序，最后再取出前n群距離最近(baseline)、機率最大(probability)的候選集信息作為結果。

以下所呈現(xiàn)的是SIFT1B_1B數(shù)據庫使用k-measn(一層)分為256群、1024群與4096群的搜索結果，見表1、表2、表3。baseline找出n個與查詢值距離最近的群，取出群內所有候選集數(shù)據當作搜索結果。probability則是套用類神經網絡后，找出n筆近鄰概率最高的當作搜索結果。

表1 SIFT_1B 256群的結果

表2 SIFT_1B 1024群的結果

表3 SIFT_1B 4096群的結果

可以從結果觀察到，使用類神經網絡模型去預測各群的近鄰概率，由高至低進行檢索，取代原本的歐幾里得距離，各種群數(shù)下，Recall、precision都比baseline要好，也間接證明了使用類神經網絡模型所預測的近鄰概率，是可以改善候選集質量的。

4.2.2 多層取法

以下為使用hierarchical k-means clustering(兩層)的結果，如圖1所示。第二層采用固定最后所取總群數(shù)量，作為互相比較的標準。由于baseline無法自行決定第一層所需使用的群數(shù)量，所以將baseline的實驗結果設定為取m群(1、2、4、8群)，總群數(shù)量則固定與probability相同。假設現(xiàn)在所需總群數(shù)量為n，baseline將會有五組不同Recall。第一組為1群，則會在該群下取出n/1個子群作為結果，第二組為2群，則會在這兩群中，各取n/2個與查詢值query最近的子群作為結果，以此類推。

圖1 Precision-Recall曲線

由此可以看出，本文的方法與baseline相比都有著一定的改善幅度，雖然baseline第一層拜訪的群數(shù)越多，結果可能會越好，但這也代表著必須自行觀察搜索結果，找出最適合的參數(shù)。而由近鄰概率來決定第一層所需訪問的群數(shù)量，則可以不必再觀察搜索結果，利用近鄰概率自動找出(算出)最適合的參數(shù)。

4.2.3 非對稱距離計算

以下為上一小節(jié)實驗經過非對稱距離(ADC)計算后的結果。ADC結構為：原始特征切為8段，各16維，每段分256群剛好可以以一個字節(jié)來代表(1byte)。經過ADC后取出前1000筆，并計算Top1000 Recall。如圖2所示。

圖2 ADC的結果

通過實驗可以觀察到利用近鄰概率，整體候選集質量有所提升，因此經過ADC后可以明顯看出優(yōu)勢所在。除了256×256群外，其它兩種都有明顯的改善。

5 結束語

本文展現(xiàn)了如何利用類神經網絡去學習查詢值與各群之間的近鄰概率，舍棄原先使用歐幾里得距離的方式，在某些條件下還可以減少計算距離的時間。針對不同參數(shù)與實驗結果，對本文所提出的方法進行了深入分析。本文主要研究工作和結論如下：

1)利用近鄰概率重新排列檢索順序作為第一階段篩選，取代原本的基于距離產生的檢索順序。

2)有效運用近鄰概率在樹狀索引的分群方法，也可以與其它近鄰搜索方法做整合，提升它們的檢索精度。

3)用本文提出的方法重新排序檢索表后，在十億筆數(shù)據集實驗中，準確度都得到了明顯的提升。