加權自學習哈希高維數據最近鄰查詢算法

熊一利

(江西省教育考試院 信息處，江西 南昌 330038)

0 引 言

所謂的最近鄰查詢，實際上是給定數據集中返回與查詢對象q最為相近的數據對象問題。在數據挖掘[1]、模式識別[2]等多個領域當中最近鄰都屬于基礎研究問題，一般應用時會將其轉化成求解近似最近鄰問題。在數據增長速度極快且類型越來越多的同時，研究者們都將高效的查詢算法與索引結構的設計作為主要研究重點。

學習型哈希[3-8]由于儲存與查詢方面極為高效，索引在最近鄰查詢問題中應用非常廣泛。大多數學習型哈希法，對于一個給定的查詢返回的只是簡單的基于海明距離的排序結果。這種計算方法盡管高效，但因為海明距離都是離散取值的，且數據二進制編碼長度會給其帶來一定的限制，返回結果與查詢對象間存在一致的海明距離，但是很難區分不同的二進制編碼對象，怎樣重新排序候選集中對象是一個非常重要且亟待解決的問題。有關學習型哈希法存在不同二進制編碼及相同海明距離的數據無法深入區分的問題，本文通過加權自學習哈希算法的提出有效解決該問題。

1 加權自學習哈希算法

1.1 算法目標

本文提出了一種加權自學習的哈希算法，用于解決高維數據最近鄰查找，能夠解決不同二進制編碼而相同海明距離的數據無法更為深入區分的難題。通過自學習哈希法的應用把原始數據轉化成二進制編碼，進行學習后獲取哈希函數。一旦迎來查詢對象后，首要做的就是利用已學習獲取的哈希函數轉化成二進制編碼，接著進行其與各數據的二進制編碼之間的海明距離計算，之后回到與特定距離相符的候選集。因為候選集當中有諸多與查詢對象編碼不同而海明距離相同的數據，實際上與查詢對象實際的距離相比這些數據是存在相應差異的，利用海明距離無法進行更為深入的區分。如果去比較原始數據集，那代價比較高昂。為了解決上述問題，我們根據查詢對象以及候選集的二進制編碼兩者具有的特征，賦予二進制變慢不同的權重，最后根據查詢對象與候選集的加權海明距離對候選集進行重新排序，使得與查詢對象具有相同海明距離不同二進制編碼的候選對象能夠在更細粒度上進行區分，從而獲得更精確的距離度量結果。

1.2 自學習哈希

如圖1所示，自學習哈希法實際上包含兩個學習階段，無監督學習為第一個階段，該階段主要目的在于把原始空間中的高維數據x轉成相對較短的二進制編碼y。假設X為數據集合，用m表示，n是數據維度，則數據集的矩陣表示情況如下

自學習哈希通過度量學習方式將xi轉化為長度為l比特的二進制編碼yi∈{0,1}l，則Y可以表示為n×l的矩陣

有監督學習為第二階段，把第一階段獲取的所有數據二進制編碼yi1,…,yil∈{0,1}視作類標簽，通過機器學習法訓練出l個分類器，并視作哈希函數h1,h2,…,hl。查詢數據x到來時，通過哈希H(x)=(h1(x),h2(x),…,hl(x))將其轉化為二進制編碼yi1,…,yil∈{0,1}。會將其稱作自學習哈希法，主要原因在于其中的數據標簽并不是通過人為標注，而是通過學習得到的。

圖1 自學習哈希框架

1.3 查詢自適應權重

自學習哈希的框架為開放型的，主要包含兩個學習步驟，可結合實際的需求以及應用環境明確應使用的方法。和大多數學習型哈希方法一樣，自學習哈希仍然存在與查詢對象編碼不同海明距離相同無法進行更為深入區分的問題。例如q為查詢對象，假設其二進制編碼為“101”，q與o1(001)、o2(111)的海明距離都是1，但是與q的真實距離是不一樣的，通過海明距離無法明確的區分。為使得該問題可得到更好的解決，本文賦予所有的數據二進制編碼權重wi，對其加權海明距離進行計算，并重新排序候選集。不同的查詢對象得到候選集是不一樣的，所以每一次的查詢都應當結合不同的候選集對現有的權重向量進行計算，所有將其稱作查詢自適應權重。

1.4 權重求解原理

假設H(·)=(h1,h2,…,hl)中包含了l個獨立存在的哈希函數，由這些函數共同組合而哈希函數向量，H(·)分別把q和o映射成長度為l的二進制編碼H(o)和H(q)，而第k比特的二進制編碼對應為hk(·)，則q與o的海明距離表示為

(1)

假設查詢對象H(q)各比特的權重為W=(w1,w2,…,wl)，二者的加權海明距離表示為

(2)

用p(H(q)=H(o))進行數據對象q和o映射成概率相同的編碼的表示，因為每一個哈希函數都是獨立存在的，所有相等的兩個數據二進制編碼與每一個被映射成相同編碼概率乘積相同，因此才有

(3)

要想獲得每一個比特的權重，就需要借助一個科學的理念，從而促使哈希函數將類似的數據對象處理成比特一樣的狀態。對于哈希函數而言，可信值提升，對應比特中不同的參數產生了不同的二進制編碼，那么同樣的概率很小，所相對的加權海明距離則很大。例如，假設q的二進制編碼為“101”，o1,o2的二進制編碼為“001”，“111”。由左到右，q和o1的二進制編碼所處的第一比特部位有差別，q和o2所處的第二比特也有差別。若是第一比特的可信度則比第二比特位更高，可以看出：

q和o2非常接近，同時Dw(H(q),H(o2))w2。

定理1 普通的哈希函數促使相應的數據對象轉變為一樣的比特，則這個哈希函數的可信值也非常大，其比特的權重也很高。

證明：根據上面的理論，可按照信息熵來驗證。此理論中，熵的變化性非常大。很多時候，其中的信息熵越低，指標的變化性越高，其中包含的信息越多。而且綜合評估可以實現的效果越大，權重也大，反之亦然。

如果X屬于一個離散隨即變量，那么其可以在R={x1，x2，…，xn}的范圍內取值，這個值是有限的。如果pi=P{X=xi}，那么X的范圍則處于xi中。X的熵是這樣的

(4)

如果參數q的二進制編碼是H(q)，所選擇的數據對象位于k比特中，其編碼和q一樣的機率為pk，不一樣的機率是1-pk，選擇的數據在正常狀態下和搜查參數在對應比特中的編碼相同，設置的閾值為pk>1/2，所以有pk>1-pk，第k比特的信息熵為

Ek(H(q))=-pklnpk-(1-pk)ln(1-pk)

(5)

計算出各個指標的信息熵為E1,E2,…,Ek,…,El，通過信息熵計算各比特的權重

(6)

在信息熵函數中若對數的底取2，則對應熵函數的曲線，當概率pk>1/2時，Ek隨著pk的增大而減小。所以有pk越大，Ek越小，wk就越大。

證畢

1.5 求解步驟

以Ck表示查詢對象q與候選集結果o在k比特上被映射為相同比特的次數，S(hk(q)=hk(oi))表示hk(q)與hk(oi)是否相等。如果相等，則S(hk(q)=hk(oi))=1，否則為0。于是可以得到

(7)

參數q和所選擇的參數的二進制編碼中的第k位一樣的機率是pk，N代表的是候選集的值，則

pk=C(k)/N

(8)

wk與pk近似單調的線性關系，所有在實際應用中，為了簡化計算，可用pk來代替wk。

2 實驗驗證和結果分析

下面將通過實驗來驗證提出的加權自學習哈希算法在解決最近鄰查找問題上的優越性能。在自學習哈希的零監督學習部分，使用拉普拉斯特征映射的方法[9]，促使高維數據映射變成低維實數向量，再借助均值閾值法變成二進制編碼。通過拉普拉斯特，能看出參數中的整體結構，同時借助KNN來建立相鄰參數的相同矩陣聯系，防止因為計算全局相同所以產生時空開銷。但在監督學習的過程中，可使用由LIBLINEAR[10]帶來的線性SVM，從而對分類器進行劃分，獲得l個哈希函數。要想更好解決高維數據問題，避免產生非線性可分問題，可以針對SVM中的數據進行設置，借助高斯核函數來取代線性SVM向量內積，另外的數據則恢復默認狀態。要辨別一般的STH，便需要在監督學習階段，借助SVM來進行調整，這種方式被稱為是STHs。下面的實驗操作中，必須比較STHs與STH的不同。加權自學習哈希(WSTHs)則在STHs基礎上由查詢所得的候選集計算出二進制編碼各位的權重W=(w1,w2,…,wl)，接著計算查詢對象與候選集中各個數據的加權海明距離，從而得到更精確有序的結果。并通過實驗在3個不同的真實數據集上對比WSTHs和STHs查詢性能。

2.1 數據集

筆者針對3個不同的數據集(Reuters21578、TDT2、20Newsgroups)完成操作。在這個過程中，要刪除停用詞、獲取詞干，從而完成TF-IDF的核算工作，并且借助稀疏矩陣來進行表達。

20世紀80年代末期，路透社新聞所發表的文章中，結合了所組成的語料庫，避免了出現在各種各樣的文章中，同時只留下了文章數當中的10個部分，篩選了7300篇不同的文章，訓練集涵蓋了5225(72%)篇文檔，測試集為2057(28%)篇，數據的維度大小為17 024。

TDT2語料庫包含了各種不同的文章，這些文章來自新聞節目、報紙文章、電視廣播等。除掉來源于各種途徑的文章，促使剩下大概30個種類得以保留，獲得9421篇文章。在篩選之后，獲得訓練集的值為5644(60%)篇，測試集為3750(40%)篇，數據的維度大小為33 878。

在語料庫20Newsgroups里，大概有19 216篇文章，這些文章來源于不同的類別。按照實際情況來對數據集進行分類，然后獲得大小均為12 015(60%)篇的訓練集和7532(40%)篇的測試集合，數據的維度大小為25 714。

2.2 評 估

2.2.1 查詢結果的F1值

測試數據集中的每篇文檔是一個查詢數據，根據學習得到的哈希函數將其映射為二進制編碼，在訓練集中檢索滿足特定海明距離的對象作為候選集，然后計算權重，根據加權海明距離對這些數據進行重排序。對于不同的相關參數，如果必須返回和海明距離

P=返回結果集中與查詢對象是同一類的數量/
返回結果集的大小

(9)

R=返回結果集中與查詢對象是同一類的數量/
數據集中與查詢對象是同一類的數據數量

(10)

標準的F1值表示為

F1=2P*R/(P+R)

(11)

2.2.2 時間效率

WTHs對STHs進行了優化，在二進制數據中的比特里，添加了各種權重。同時也對無法區別的參數重新排列，該步驟耗費的時間很多。可以采取簡易的方法來對候選集進行二次排列，借助對參數的搜索，以及篩選的參數的原始距離，算出這些參數的歐式(Euclidean)距離。對于不同的n維向量a(x11,x12,…,x1n)以及b(x21,x22,…,x2n)，可這樣計算

(12)

從上面的公式可以看出，計算歐式距離的時間復雜度為O(n2)。n屬于在搜索之后反饋的達到距離要求的候選集的值，k是參數的二進制編碼參數。在WTHs算法里，針對候選集二次排序時，會經歷這些流程：①按照候選集獲得權重，這一部分的實踐復雜度為O(nl)；②根據權重計算加權海明距離，這部分的時間復雜度為O(k2)。實驗所用的數據集的維度通常很大，二進制編碼的長度卻很短，所以k?n。這樣一來，在花費的時間方面，WTHs二次排列參數，會比采用計算歐式距離對數據進行排序所消耗的時間更少。

2.3 實驗結果

在圖2～圖4中，橫坐標為編碼長度，縱坐標為F1值，從上面的實驗對比圖能夠清楚看到，與之前的STH，STHs相比，通過高斯核函數重寫SVM后會在一定程度提升F1值，表明了高維數據分類選項高斯核函數的SVM將更為適用。WSTHs相比STHs，F1值有顯著提升，前者F1值是后者的1.5～2倍，說明通過加權重排序后，原本難以區分的具有相同海明距離的數據被很好的區分開來，也意味著加權思想的提出是正確的。與此同時，也可得知數據集映以及編碼長度不同，也會獲取不同的F1值，由如圖3～圖5得知，在選取8bit、24bit、32bit這3個數據集長度的情況下F1最大，表明了哈希函數學習具有極強的數據依賴性。數據集不同的情況下分布也會不同，各個數據維度也會具有不同的重要性，且利用加權算法得到更為精確的返回結果。縱觀實驗結果可知，并非是有更長的編碼就意味著更好，主要由于在于有越長的編碼，則與查詢對象具有相同海明距離的不同編碼的可能情況就越多，比特的權重被稀釋，變得難以區分。而編碼的長度太短時，數據量越大，則不同的數據的二進制編碼相同的概率越大，使得查找的準確率降低。

圖2 Reuters21578上F1值隨編碼長度變化曲線(左圖N1=N/2,右圖N1=N/3)

圖3 20Newsgroups上F1值隨編碼長度變化曲線(左圖N1=N/2,右圖N1=N/3)

圖4 TDT2上F1值隨編碼長度變化曲線(左圖N1=N/2,右圖N1=N/3)

從上文中進行的分析時間效率理論得知，WTHs重新排序候選集耗費的時間要比原始數據Euclidean距離直接計算耗費的時間短很多，下文中將利用實驗進行驗證，詳情見表1。

表1 對比WTHs與直接計算Euclidean距離所耗費的時間/s

從上面的實驗數據可以看出，通過WTHs算法對候選集進行重新排序耗費的時間要比歐式距離計算耗費的時間短很多，后者將為前者10至20倍的時間耗費。而時間響應要求較高的應用，必然是要優先選擇WTHs。

此外，對于一個好的算法，需要權衡各方面的因素，除了時間效率外還需考慮空間效率和算法的準確性。空間上，由于WTHs算法將數據轉化為了一串較短的二進制編碼，所有空間效率也大大提高。為了對準確性方面WTHs以及歐式距離直接計算的表現進行對比，任何一次查詢都應當將兩種算法排序后前N/2個數據作為最終的返回結果，根據前面準確率的公式可知，返回結果集中與查詢對象屬于同一類的數據對象越多則查詢的準確率越高實驗結果如圖5～圖7所示。

圖5 Reuters21578上準確率對比

圖6 20Newsgroups上準確率對比

圖7 TDT2上準確率對比

從上面3個數據集合上的實驗對比可以看出，當學習數據的二進制編碼長度小于96 bit時，WTHs與直接計算Euclidean距離兩種算法的對比可知，前者在數據排序查詢方面具有更高的準確率。主要原因為歐式距離采用相同的方式對待數據的各維度，而WTHs采用不同的方式，其更可凸顯數據不同維度重要性差異。當數據的二進制編碼大于96 bit時，直接計算歐式距離的準確率要高于WTHs算法。顯然，學習型哈希的優勢在能夠用較短的二進制編碼來表示數據，并且能夠提高查詢的準確性。

除了進行WTHs和直接計算Euclidean距離兩者在數據排序查詢方面的準確率對比，這兩種方式在KNN分類方面的準確性我們也進行了相應的對比。KNN是通過返回的數據集來推測查詢對象的歸類，有更高的準確率，就意味著取得的k近鄰與其越相似。下面是WTHs和直接計算Euclidean距離時KNN分類準確性實驗對比結果，假設N為每次查詢返回的滿足距離要求的候選集的大小，k取N/2。

從圖8～圖10可以看出通過WTHs所得結果集來進行KNN分類的準確性與直接計算Euclidean距離在編碼長度小于60 bit時并沒有下降，在某些情況下反而有所提高，這也從側面說明了與傳統Euclidean距離計算相比，WTHs在時間方面的優勢極強，同時準確性方面也得到了保證。

圖8 Reuters21578上KNN分類準確性

圖9 20Newsgroups上KNN分類準確性

圖10 TDT2上KNN分類準確性

3 結束語

大部分學習型哈希法把原始空間的高維數據映射到海明空間的低維數據后，因為量化與降維兩個步驟會造成一定的損失，導致海明距離一致的數據對象與查詢對象無法進行更為深入的區分。而不同的數據維度，也會相應的攜帶不同的信息，而相對應的轉化之后的二進制編碼也會具有不同的重要型。為使得返回結果更加準確，在自學習哈希架構基礎之上，依據查詢對象與候選集相同比特的統計特征對比特賦予不同的權重，最后將加權排序結果返回。本文從理論分析入手，并采用實驗的方式對加權自學習哈希方法的高效性以及準確性進行驗證。