王 星,于江旭,唐曉亮,閆慧斌

1(遼寧工程技術(shù)大學(xué) 電子與信息工程學(xué)院,遼寧 葫蘆島 125105)2(遼寧工程技術(shù)大學(xué) 研究生院,遼寧 阜新 123000)3(遼寧工程技術(shù)大學(xué) 軟件學(xué)院,遼寧 葫蘆島 125105)

1 引 言

隨著網(wǎng)絡(luò)設(shè)備和信息技術(shù)的飛速發(fā)展,數(shù)據(jù)在社會生活的方方面面起著越來越重要的作用,如何更快更準確地對大規(guī)模數(shù)據(jù)進行處理一直是人們的研究熱點,近鄰搜索[1]是最常見的數(shù)據(jù)處理方式之一.近鄰搜索算法可以分為精確最近鄰搜索[2,3]和近似最近鄰ANNs[4](Approximate Nearest Neighbors)搜索.k最近鄰[5]是比較經(jīng)典的精確近鄰搜索算法,許多精確近鄰搜索算法都是基于樹結(jié)構(gòu)(比如說KD樹[6],R樹[7]等)的近鄰搜索,但是在高維數(shù)據(jù)的檢索中,這些算法效率會直線下降,因此近似最近鄰搜索的研究得到了人們的關(guān)注,越來越多基于哈希的ANNs算法[8,9]被提了出來.ANNs的特點是在損失少量精度的條件下實現(xiàn)快速的近鄰搜索,提高效率的同時也可以得到精度相對較高的搜索結(jié)果.基于哈希的方法是ANN搜索的代表之一.按照其產(chǎn)生哈希函數(shù)的原理,哈希算法大致可以分為基于隨機映射的哈希算法和基于學(xué)習(xí)的哈希算法.前者不考慮數(shù)據(jù)分布[8],而后者根據(jù)數(shù)據(jù)分布形成哈希函數(shù)[9].

上述的精確最近鄰搜索算法和基于哈希的搜索算法都是基于靜態(tài)數(shù)據(jù)的搜索算法,其處理數(shù)據(jù)的量總體上是不變的.但在實際應(yīng)用中,遇到動態(tài)的數(shù)據(jù),或者數(shù)據(jù)量比較大,無法一次性放入內(nèi)存時,這些算法就無法使用.比如在數(shù)據(jù)庫中進行數(shù)據(jù)搜索,當(dāng)有新的數(shù)據(jù)加入數(shù)據(jù)庫時重新對數(shù)據(jù)進行一次近鄰搜索是不現(xiàn)實的,浪費大量的時間和內(nèi)存,于是許多處理動態(tài)數(shù)據(jù)的技術(shù)[10,11]被提了出來.在線k均值聚類算法[11]可以在保持原來數(shù)據(jù)樣本不變的情況下對新的數(shù)據(jù)樣本進行快速聚類.

針對現(xiàn)階段的哈希算法無法有效處理大規(guī)模動態(tài)數(shù)據(jù)的問題,本文提出一種新的在線k均值聚類算法,并將其與密度敏感哈希算法[12]結(jié)合,形成一種基于在線學(xué)習(xí)[13]的哈希算法,即在線密度敏感哈希ODSH (Online Density Sensitive Hash),該算法首先使用在線k均值聚類對數(shù)據(jù)進行預(yù)處理量化,然后根據(jù)產(chǎn)生的量化結(jié)果生成動態(tài)的超平面,根據(jù)超平面求出哈希方程,求出對應(yīng)的投影向量和截距,最后使用投影向量對數(shù)據(jù)進行映射,得到哈希編碼,并使用漢明距離進行對比,獲得需要的近鄰結(jié)果.實驗證明,ODSH不僅具有基于學(xué)習(xí)哈希算法的特點,可以返回精確的結(jié)果,而且還可以快速地處理大規(guī)模動態(tài)數(shù)據(jù).

2 相關(guān)工作

本節(jié)介紹哈希算法的基本概念和常見的哈希算法.

2.1 哈希算法的基本概念

哈希算法是一種可以將原始數(shù)據(jù)樣本快速映射到新的數(shù)據(jù)空間并生成二值編碼,可以實現(xiàn)高效數(shù)據(jù)檢索的搜索算法.各種哈希算法之間的主要區(qū)別在于采用了不同的哈希函數(shù),根據(jù)哈希函數(shù)得到投影向量,再對數(shù)據(jù)進行映射獲取哈希編碼,哈希算法中最基本的哈希函數(shù)如公式(1)所示:

y=h(x)

(1)

h(·)是哈希函數(shù),y是經(jīng)過哈希函數(shù)映射后的哈希編碼,通常情況會使用多個哈希函數(shù)來組成一族哈希函數(shù),產(chǎn)生多組哈希編碼,即,Y=[y1y2…ym]=[h1(x)h2(x)…h(huán)m(x)].哈希算法將任意長度的二進制值映射為較短的二進制值,廣泛地應(yīng)用于快速檢索.基于映射的線性哈希搜索,第k個哈希函數(shù)定義如公式(2)[14]所示:

(2)

x是任意的一個數(shù)據(jù)點,wk是投影向量,tk是一個閾值,也可以稱為投影向量對應(yīng)的截距,而f(·)表示的是一個目標函數(shù).定義中的sgn函數(shù)只會返回{-1,1},經(jīng)過哈希函數(shù)映射后的二進制編碼可以表示為bk=(1+Hk(x))/2.下面總結(jié)一下比較常見的哈希算法.

2.2 基于隨機映射的哈希

局部敏感哈希LSH[8](Locality Sensitive Hash)是最常用的哈希算法之一,它的基本思路是將原來空間中相鄰的數(shù)據(jù)點通過映射或者投影到新的數(shù)據(jù)空間中,其仍然相鄰的概率較大,而不相鄰的數(shù)據(jù)點映射到同一個數(shù)據(jù)空間的概率很小.LSH通過生成大量的隨機映射,生成較長的哈希表來保證數(shù)據(jù)檢索的準確率,其哈希函數(shù)比較簡單,容易實現(xiàn),且速度較快,但是較長的哈希表會占用較大的內(nèi)存,而較短的哈希編碼會導(dǎo)致檢索的準確率降低.

平移不變核哈希算法SKLSH[15](shift-invariant kernels Locality Sensitive Hash),平移不變核哈希算法利用了平移不變的核方法來產(chǎn)生隨機投影,原理近似于LSH.

2.3 基于學(xué)習(xí)的哈希

以上算法是非數(shù)據(jù)驅(qū)動的哈希算法,在哈希編碼長度較長的時候效果較好,但是有占用內(nèi)存大,復(fù)雜度較高等限制,因此基于學(xué)習(xí)的數(shù)據(jù)驅(qū)動型哈希算法被提了出來.基于學(xué)習(xí)的哈希算法一般會通過分析數(shù)據(jù)點之間的關(guān)系和性質(zhì)來指導(dǎo)哈希方程的產(chǎn)生,進而獲得投影向量對數(shù)據(jù)進行哈希映射,獲得需要的哈希編碼,主成分分析哈希算法PCAH[16](Principal Component Analysis Hash)通過主成分分析獲得數(shù)據(jù)的主要成分,將主要成分作為投影向量產(chǎn)生哈希編碼.

譜哈希算法SH[9](Spectral Hash)是比較常用的基于數(shù)據(jù)學(xué)習(xí)的哈希算法.它通過對原始數(shù)據(jù)集進行PCA降維獲得相似圖拉普拉斯矩陣的特征向量,然后對特征向量進行閾值化產(chǎn)生最后需要的二值編碼,譜哈希可以較好地提升檢索精度,但是譜哈希對多維數(shù)據(jù)的要求必須是均勻分布的,且不同維度上的哈希編碼相互獨立.

基于核的監(jiān)督哈希KSH[17](Kernel-based Supervised Hash)使用帶標簽的數(shù)據(jù)進行學(xué)習(xí)得到哈希函數(shù),將各數(shù)據(jù)再輸入到各哈希函數(shù)中得到數(shù)據(jù)對應(yīng)的哈希編碼,實驗表明該基于核的監(jiān)督哈希算法在度量距離和語義相似的搜索中表現(xiàn)出良好的性能.相比小規(guī)模的低維數(shù)據(jù),大規(guī)模高維數(shù)據(jù)本身會存在某些結(jié)構(gòu)特性,所以基于學(xué)習(xí)的數(shù)據(jù)驅(qū)動型哈希技術(shù)可以較好地實現(xiàn)數(shù)據(jù)(圖像,文本等)的快速檢索.本文提出的在線密度敏感哈希算法,可以有效地處理動態(tài)數(shù)據(jù),并通過數(shù)據(jù)之間的密度特性來指導(dǎo)哈希函數(shù)的生成,可以有效地解決普通哈希方法無法對數(shù)據(jù)庫里中不斷增加的數(shù)據(jù)以及新抓取的網(wǎng)頁進行近鄰搜索的問題.

3 在線密度敏感哈希

本節(jié)將對ODSH算法分為三小節(jié)進行詳細闡述,首先給出在線k均值聚類算法的推導(dǎo)公式,然后描述投影向量的獲取過程,最后根據(jù)信息熵值對獲得的投影向量進行篩選.

3.1 在線k均值聚類

給出固定聚類個數(shù)的在線k均值聚類的調(diào)整公式:在某一段時間內(nèi),(t-1)和(t)表示時間的前后,N表示數(shù)據(jù)點的個數(shù),K為固定好的分類結(jié)果組數(shù).

(3)

(4)

(5)

下面列出時間(t)下的在線k均值聚類的誤差平方和.

(6)

(7)

(8)

(9)

結(jié)合上式(7)(8)(9)可得公式(10)

(10)

公式(10)是在線更新的在線k均值聚類方程,通過它可以在不斷有新的數(shù)據(jù)點加入到原數(shù)據(jù)集的時候,快速而準確地獲得新的聚類結(jié)果.關(guān)于在線k均值聚類算法的組數(shù)k的確定將在實驗部分給出.

3.2 投影向量的獲取

經(jīng)過在線k均值聚類獲得不同時間下的k個聚類結(jié)果,表示為{S1,S2…,Sk},(k的數(shù)已經(jīng)固定),然后根據(jù)聚類結(jié)果來指導(dǎo)投影向量的產(chǎn)生.首先定義一下需要的變量,聚類結(jié)果將使用[12]中的n-最近鄰矩陣進行表示:

定義1.分類結(jié)果數(shù)據(jù)組的n最近鄰矩陣M

Nn(μj)代表了中心點μj的n個最近中心點集合,繼而得到n-相鄰組對的定義.

定義2.n-相鄰組對

當(dāng)Mij=1的時候,組Si和組Sj為n-相鄰組對.

通過上一步得到的n-相鄰組對,下面通過這些相鄰組對來生成對應(yīng)的投影向量,根據(jù)3.1得到的動態(tài)kmeans量化結(jié)果,對于相鄰組的表示點μi和μj,構(gòu)建表示點的中垂面(假設(shè)三維空間,三維以上用超平面來表示)來對相鄰組進行切分.根根據(jù)文獻[12]的中垂面定義和公式(10)推導(dǎo)出動態(tài)超平面公式,見公式(11),公式等號左面的公式表示的是時間(t)下的超平面,等號右邊為時間(t-1)下的超平面表示公式.

(11)

(12)

再根據(jù)超平面推得動態(tài)的哈希函數(shù):

(13)

w(t)=w(t-1)+φ2

(14)

(15)

3.3 投影向量的篩選

4 實驗結(jié)果

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

該實驗使用以下三個公用數(shù)據(jù)集:

?Sift_128d數(shù)據(jù)集:該數(shù)據(jù)集是從ANN_SIFT1M中截取出來的,因受設(shè)備的限制,只使用其中的60000個sift特征,每個特征128維度.

?Gist_320d_CIFAR-10:CIFAR-10數(shù)據(jù)集是從Alex Krizhevsky等人收集的8千萬小圖片數(shù)據(jù)集中取到的子數(shù)據(jù)集,該數(shù)據(jù)集包含了60000個彩色圖片的gist特征,維度為320維,數(shù)據(jù)集以及實驗中對比的哈希算法相關(guān)代碼可以在*https://github.com/willard-yuan/hashing-baseline-for-image-retrieval處下載.

?Gist_960d:該數(shù)據(jù)集從ANN_GIST1M中截取,同樣含有60000個sift特征,維度為960維.ANN_SIFT1M和ANN_GIST1M可在*http://corpus-texmex.irisa.fr/處下載.

4.2 實驗中對比的哈希算法

局部敏感哈希算法LSH[8]是通過生成大量的隨機映射來生成哈希編碼的哈希算法.

平移不變核哈希算法SKLSH[15](shift-invariant kernels Locality Sensitive Hash),它是LSH的一種改進算法.

主成分分析哈希算法PCAH[16]通過主成分分析來獲得數(shù)據(jù)主要成分來指導(dǎo)投影向量的產(chǎn)生.

譜哈希SH[9],該算法基于上述的PCA哈希算法,對PCA后的特征向量進行閾值化產(chǎn)生最后需要的二值哈希編碼.

主成分分析-隨機旋轉(zhuǎn)矩陣哈希算法[18]PCA-RR(Principal Component Analysis- Random Rotation),該算法在PCAH算法的基礎(chǔ)上融入隨機旋轉(zhuǎn)矩陣,相比PCAH算法性能有較大提升.

在線密度敏感哈希算法ODSH(Online Density Sensitive Hash),這是本文提出的哈希算法.

4.3 實驗設(shè)計與分析

首先對實驗參數(shù)進行設(shè)置,哈希編碼的位數(shù)l設(shè)置為ln=8,16,32,64,128位編碼,通過不同的哈希編碼位數(shù)來測試哈希算法的性能.

本文的在線k均值聚類算法需要預(yù)先固定好聚類的個數(shù),k的值由哈希編碼的位數(shù)決定,因為哈希編碼的位數(shù)越大,需要的投影向量就越多,對應(yīng)的超平面也越多,所以需要的數(shù)據(jù)組的個數(shù)也越多,所以組數(shù)k的個數(shù)與哈希編碼的位數(shù)有關(guān),故設(shè)置一個參數(shù)A來確定組數(shù)k,令k=A*ln,后續(xù)實驗中,通過固定哈希編碼的位數(shù),以及固定的A和n-相鄰組對中的參數(shù)n,會發(fā)現(xiàn)當(dāng)A=2,n=3的時候,在各位哈希編碼下在線密度敏感哈希算法的性能最好.下面會給出圖示和分析.

為了更好地與其他的哈希算法對比,本文使用同樣的數(shù)據(jù)集進行測試.針對本文提出的哈希算法,在程序中固定一部分數(shù)據(jù)集,然后通過迭代的方式將數(shù)據(jù)逐批次地導(dǎo)入到工作空間中,以此來實現(xiàn)數(shù)據(jù)的動態(tài)導(dǎo)入,根據(jù)每一批次數(shù)據(jù)導(dǎo)入后獲得的聚類結(jié)果構(gòu)建超平面,訓(xùn)練得到在線密度敏感哈希算法的哈希方程,求得投影向量和截距,最后獲得多組投影向量和截距.使用同樣的訓(xùn)練數(shù)據(jù)集獲得其他哈希算法的哈希方程,通過投影向量獲得測試和訓(xùn)練數(shù)據(jù)集對應(yīng)的二值哈希編碼,計算訓(xùn)練數(shù)據(jù)集與測試數(shù)據(jù)集之間的海明距離并排序,最后計算得到precision-recall值,以及平均準確率的平均值mAP(mean Average Precision),來衡量算法的性能.對本文提出的在線密度敏感哈希算法,根據(jù)多批次的結(jié)果計算得到多組precision-recall值和mAP值,取其平均值來與其他哈希算法進行對比.

4.3.1 參數(shù)選擇

實驗中使用mAP作為標準來進行參數(shù)的選擇,將哈希編碼長度設(shè)置為64位.首先將參數(shù)A固定,改變參數(shù)n的值來對本文的在線密度敏感哈希算法進行測試,并將數(shù)據(jù)可視化展現(xiàn)出來,然后再將參數(shù)n固定,改變參數(shù)A的值進行測試,結(jié)果如圖1、圖2所示.

圖1 64位哈希編碼:不同參數(shù)n下的mAP 圖2 64位哈希編碼:不同參數(shù)A 下的mAP

如圖1所示,首先將參數(shù)A設(shè)置為2,固定不變,橫坐標n為選取的相鄰組參數(shù),n從1到8取值,縱坐標為mAP的值.三條折線表示mAP在三個數(shù)據(jù)集下的變化.根據(jù)圖示可以看出隨著n-相鄰組的參數(shù)n取3到6時,mAP是比較理想的,考慮到n的取值不需要太大,算法里的超平面只需要切割比較近的數(shù)據(jù)簇,因此選n=3作為后續(xù)的實驗測試參數(shù).

如圖2所示,這里將參數(shù)n設(shè)置為3,參數(shù)A從1到3取值,從圖2可以看出,三個數(shù)據(jù)集對應(yīng)的三條折線,mAP的值在參數(shù)A=2時比較理想,在保證相對較高的準確度和較低的時間消耗情況下,選擇A=2作為實驗測試參數(shù).

4.3.2 測試結(jié)果

圖3到圖5表示的是各哈希算法在三個數(shù)據(jù)集下,32位,64位,128位哈希編碼的precision-recall曲線圖,可以看出在不同維度的數(shù)據(jù),不同位數(shù)的哈希編碼下,本文提出的在線密度敏感哈希均具有較好的性能.

圖6表示不同的哈希算法在三種數(shù)據(jù)集下,哈希編碼從8位到128位的平均準確率的平均值,SKLSH和LSH屬于非數(shù)據(jù)驅(qū)動型的哈希算法,可以看出他們在哈希編碼位數(shù)較少的情況下性能較差,但隨著哈希編碼位數(shù)的增加,其準確率增長幅度較大.基于數(shù)據(jù)驅(qū)動型的哈希算法如SH隨著哈希編碼位數(shù)的準確率增長幅度相比LSH等算法較小,特別是PCAH算法隨著哈希編碼的位數(shù)增長性能反而下降了,其原因是PCAH算法里的主成分分析得到的數(shù)據(jù)主成分分布比較集中,只能在有限位數(shù)的哈希編碼中起作用,隨著哈希編碼位數(shù)的增長,在后面的哈希編碼中識別最近鄰數(shù)據(jù)的性能會下降,PCA-RR算法引入了隨機旋轉(zhuǎn)矩陣,隨著哈希編碼位數(shù)的增加,平均準確率的增長比較明顯.分析本文提出的ODSH算法在三個不同維度的數(shù)據(jù)集中的表現(xiàn)可以發(fā)現(xiàn),在線密度敏感哈希算法在不同編碼不同維度的性能都要好于上述哈希算法,也可以看出隨著維度的增加,其平均準確率的平均值會更高一些,可以看出在線密度敏感哈希算法同樣適合于高維數(shù)據(jù)的檢索.

圖3 Sift _128維數(shù)據(jù)集Fig.3 Sift_128 dimension data set

圖4 Gist _320維數(shù)據(jù)集Fig.4 Gist _320 dimension data set

圖5 Gist_960維數(shù)據(jù)集Fig.5 Gist_960 dimension data set

圖6 三種數(shù)據(jù)集下的平均準確率的平均值Fig.6 Average of the average accuracy of the three datasets

5 結(jié)論與未來工作

本文提出的基于在線k均值聚類的密度敏感哈希算法可以較好地應(yīng)對動態(tài)數(shù)據(jù)搜索的情況,可以解決普通哈希算法無法解決的在線學(xué)習(xí)問題,通過大量的實驗對比,可以發(fā)現(xiàn)該算法具有較好的準確度和速度,但是該算法在超高維的數(shù)據(jù)下,比如說4096維度的數(shù)據(jù)下性能略低,故本文的下一步工作是對在線k均值聚類算法以及密度敏感哈希算法進行一系列參數(shù)優(yōu)化,使其能更快速地對超高維數(shù)據(jù)進行處理,并在云平臺上測試算法性能.

：

[1] Brin S.Near neighbor search in large metric spaces [C].Proceedings of the 21th International Conference on Very Large Data Bases,1996:574-584.

[2] Dasgupta S,Sinha K.Randomized partition trees for nearest neighbor search [J].Algorithmica,2015,72(1):237-263.

[3] Tao Y F,Papadias D,Shen Q M.Continuous nearest neighbor search [C].Proceedings of the 28th International Conference on Very Large Data Bases,2002:287-298.

[4] Indyk P,Motwani R.Approximate nearest neighbors:towards removing the curse of dimensionality [C].Proceedings of the 30th Annual ACM Symposium on Theory of Computing,2000:604-613.

[5] Zhang Xu,He Xiang-nan,Jin Che-qing,et al.Processing K-nearest neighbors query over uncertain graphs [J].Journal of Computer Research and Development,2011,48(10):1871-1878.

[6] Friedman J H.An Algorithm for finding best matches in logarithmic expected time [J].ACM Transactions on Mathematical Software,1977,3(3):209-226.

[7] Guttman A.R-trees:a dynamic index structure for spatial searching [C].Proceedings of the 10th ACM SIGMOD International Conference on Management of Data,ACM,1984:47-57.

[8] Datar M,Immorlica N,Indyk P,et al.Locality-sensitive hashing scheme based on P-stable distributions [C].Proceedings of the 20th Annual Symposium on Computational Geometry,ACM,2004:253-262.

[9] Weiss Y,Torralba A,Fergus R.Spectral hashing [C].Proceedings of the 21th International Conference on Neural Information Processing Systems,2008:1753-1760.

[10] Li Song,Zhang Li-ping,Hao Zhong-xiao.Strong neighborhood pair query in dynamic dataset [J].Journal of Computer Research and Development,2015,52(3):749-759.

[11] Liberty E,Sriharsha R,Sviridenko M.An algorithm for online K-means clustering [J].Computer Science,2014:81-89.

[12] Jin Z,Li C,Lin Y,et al.Density sensitive hashing [J].IEEE Transactions on Cybernetics,2014,44(8):1362-1371.

[13] Mairal J,Bach F,Ponce J,et al.Online learning for matrix factorization and sparse coding[J].Journal of Machine Learning Research,2010,11(1):19-60.

[14] Wang J,Kumar S,Chang S.Sequential projection learning for hashing with compact codes [C].Proceedings of the 27th International Conference on Machine Learning,2010:1127-1134.

[15] Raginsky M,Lazebnik S.Locality-sensitive binary codes from shift-invariant kernels [C].Proceedings of the 22th International Conference on Neural Information Processing Systems,2009:1509-1517.

[16] Zhou X,Huang Z,Ng WWY.Weighted grid principal component analysis hashing [C].Proceedings of the 13th International Conference on Machine Learning and Cybernetics,2015:200-205.

[17] Liu W,Wang J,Ji R,et al.Supervised hashing with kernels [C].Proceedings of the 25th International Conference on Computer Vision and Pattern Recognition,2012:2074-2081.

[18] Gong Y,Lazebnik S,Gordo A,et al.Iterative quantization:a procrustean approach to learning binary codes [C].Proceedings of the 24th International Conference on Computer Vision and Pattern Recognition,2011:817-824.

附中文參考文獻：

[5] 張 旭,何向南,金澈清,等.面向不確定圖的k最近鄰查詢[J].計算機研究與發(fā)展,2011,48(10):1871-1878.

[10] 李 松,張麗平,郝忠孝.動態(tài)數(shù)據(jù)集環(huán)境下的強鄰近對查詢[J].計算機研究與發(fā)展,2015,52(3):749-759.