加權(quán)自學(xué)習(xí)哈希高維數(shù)據(jù)最近鄰查詢算法

熊一利

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

0 引 言

所謂的最近鄰查詢，實(shí)際上是給定數(shù)據(jù)集中返回與查詢對象q最為相近的數(shù)據(jù)對象問題。在數(shù)據(jù)挖掘[1]、模式識別[2]等多個領(lǐng)域當(dāng)中最近鄰都屬于基礎(chǔ)研究問題，一般應(yīng)用時會將其轉(zhuǎn)化成求解近似最近鄰問題。在數(shù)據(jù)增長速度極快且類型越來越多的同時，研究者們都將高效的查詢算法與索引結(jié)構(gòu)的設(shè)計作為主要研究重點(diǎn)。

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

1 加權(quán)自學(xué)習(xí)哈希算法

1.1 算法目標(biāo)

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

1.2 自學(xué)習(xí)哈希

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

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

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

圖1 自學(xué)習(xí)哈?？蚣?/p>

1.3 查詢自適應(yīng)權(quán)重

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

1.4 權(quán)重求解原理

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

(1)

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

(2)

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

(3)

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

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

定理1 普通的哈希函數(shù)促使相應(yīng)的數(shù)據(jù)對象轉(zhuǎn)變?yōu)橐粯拥谋忍?，則這個哈希函數(shù)的可信值也非常大，其比特的權(quán)重也很高。

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

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

(4)

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

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

(5)

計算出各個指標(biāo)的信息熵為E1,E2,…,Ek,…,El，通過信息熵計算各比特的權(quán)重

(6)

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

證畢

1.5 求解步驟

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

(7)

參數(shù)q和所選擇的參數(shù)的二進(jìn)制編碼中的第k位一樣的機(jī)率是pk，N代表的是候選集的值，則

pk=C(k)/N

(8)

wk與pk近似單調(diào)的線性關(guān)系，所有在實(shí)際應(yīng)用中，為了簡化計算，可用pk來代替wk。

2 實(shí)驗驗證和結(jié)果分析

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

2.1 數(shù)據(jù)集

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

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

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

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

2.2 評 估

2.2.1 查詢結(jié)果的F1值

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

P=返回結(jié)果集中與查詢對象是同一類的數(shù)量/
返回結(jié)果集的大小

(9)

R=返回結(jié)果集中與查詢對象是同一類的數(shù)量/
數(shù)據(jù)集中與查詢對象是同一類的數(shù)據(jù)數(shù)量

(10)

標(biāo)準(zhǔn)的F1值表示為

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

(11)

2.2.2 時間效率

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

(12)

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

2.3 實(shí)驗結(jié)果

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

圖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)

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

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

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

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

圖5 Reuters21578上準(zhǔn)確率對比

圖6 20Newsgroups上準(zhǔn)確率對比

圖7 TDT2上準(zhǔn)確率對比

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

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

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

圖8 Reuters21578上KNN分類準(zhǔn)確性

圖9 20Newsgroups上KNN分類準(zhǔn)確性

圖10 TDT2上KNN分類準(zhǔn)確性

3 結(jié)束語

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