費倫科，秦建陽，滕少華，張 巍，劉冬寧，侯 艷

（廣東工業(yè)大學(xué) 計算機學(xué)院，廣東 廣州 510006）

1 相關(guān)方法介紹

1.1 數(shù)據(jù)檢索方法

隨著互聯(lián)網(wǎng)的快速發(fā)展，網(wǎng)絡(luò)信息以指數(shù)級的速度增長。近年來Google每年的搜索量達2萬億次以上，Twitter每日上傳的信息量達4億條，Youtube的上傳速度達到400 h/min。此外，不僅數(shù)據(jù)量快速增長，數(shù)據(jù)的維度也隨著多媒體的發(fā)展而快速增加。面對如此龐大的信息，如何更好地利用信息，從而提高互聯(lián)網(wǎng)利用效率，解決信息有效存儲、索引與查詢的問題迫在眉睫。目前主要有精確檢索[1]和近似最鄰近檢索[2]兩種數(shù)據(jù)檢索方法。

1.1.1 精確檢索

精確檢索在數(shù)據(jù)庫中依次計算訓(xùn)練樣本與查詢樣本之間的距離，抽取出距離最小的樣本即為所要查找的最近鄰。最早的精確檢索方法包括線性搜索[3]等，這是一種窮舉搜索方法，當樣本數(shù)量巨大時搜索效率急劇下降。后來發(fā)展出k-d trees[4]，metric trees[5]和混合型索引結(jié)構(gòu)[6]等基于空間分割的方法，但這些方法隨著樣本的特征維度增加效率急劇下降，表現(xiàn)甚至不如線性搜索。因此精確檢索實際應(yīng)用有限。

1.1.2 近似最近鄰檢索

近似最近鄰檢索利用了數(shù)據(jù)量增大后數(shù)據(jù)之間會形成簇狀聚集分布的特性，通過分析和聚類對數(shù)據(jù)庫中的數(shù)據(jù)進行分類或編碼，并根據(jù)目標數(shù)據(jù)的特征預(yù)測其所屬類別，返回類別中的部分或全部作為檢索結(jié)果。近似最近鄰檢索的核心思想是搜索潛在的近鄰數(shù)據(jù)而不局限于返回最近鄰的數(shù)據(jù)，在犧牲可接受范圍內(nèi)的精度的情況下提高檢索效率。近似最近鄰檢索主要分為兩類方法：一類是哈希散列方法，另一類是矢量量化方法。矢量量化需要先建立碼本然后搜索碼字，碼本建立和碼字搜索的復(fù)雜度都會隨著矢量維數(shù)的增加而增加，為此帶來巨大的計算開銷。盡管Jégou等[7]提出的乘積量化(Product Quantization)方法對此進行了改善，在此只關(guān)注更加高效簡便的哈希散列方法。

1.2 哈希散列方法介紹

1.2.1 哈希散列方法過程

哈希散列方法是一種數(shù)據(jù)檢索方法，實現(xiàn)過程如下：首先構(gòu)建一個映射矩陣將高維的訓(xùn)練數(shù)據(jù)投影成低維的連續(xù)數(shù)據(jù)，然后將低維連續(xù)數(shù)據(jù)量化成二進制數(shù)據(jù)；測試數(shù)據(jù)使用相同的映射矩陣投影量化成二進制數(shù)據(jù)；最后通過比較訓(xùn)練數(shù)據(jù)和測試數(shù)據(jù)的二進制代碼，實現(xiàn)快速檢索。

哈希散列方法的訓(xùn)練過程一般分成兩步，對于訓(xùn)練數(shù)據(jù) X，有：第一步，投影：Y =XP，將高維的訓(xùn)練數(shù)據(jù) X通過映射矩陣 P投影成低維的連續(xù)數(shù)據(jù)Y ，本質(zhì)上屬于降維過程；第二步，量化： B=sgn(Y)，一般使用符號函數(shù)s gn(·)將 連續(xù)數(shù)據(jù)Y 量化成二元哈希數(shù)據(jù) B。在投影和量化過程中，引用損失函數(shù) L衡量原始數(shù)據(jù)與二元數(shù)據(jù)間的信息損失，確保二元哈希數(shù)據(jù)仍然保持原始數(shù)據(jù)的相關(guān)結(jié)構(gòu)和信息。

1.2.2 哈希散列方法的難點

哈希散列方法的難點有3個：第一，構(gòu)建一個良好的映射矩陣將高維數(shù)據(jù)投影成低維數(shù)據(jù)；第二，減少量化的損失，即減少二進制數(shù)據(jù)與原始數(shù)據(jù)之間的差異；第三，用于學(xué)習(xí)二進制代碼的參數(shù)和用于編碼新測試圖像的算法應(yīng)該是非常有效的。

1.2.3 哈希散列方法的優(yōu)點

哈希散列方法的優(yōu)點主要在于，將高維的數(shù)據(jù)轉(zhuǎn)化成低維的二進制數(shù)據(jù)，即將歐氏距離轉(zhuǎn)換成漢明距離后，依舊能較好地保留數(shù)據(jù)之間的原始相似性；通過基于快速二進制操作的漢明距離排序或在某個漢明距離內(nèi)的哈希表查找，可以在子線性甚至恒定時間內(nèi)完成近似數(shù)據(jù)點的檢索，不必像高維的數(shù)據(jù)需要進行復(fù)雜耗時的方程式求解；再者，原始數(shù)據(jù)的二進制壓縮可以減少大量存儲空間，即使使用大數(shù)據(jù)集，依舊有可能調(diào)用到內(nèi)存中進行操作。

2 距離計算

哈希散列方法通過距離計算比較兩個數(shù)據(jù)樣本之間的相似度。本節(jié)主要介紹不同形式的距離計算方法以及它們的特點。對于數(shù)據(jù) X=(x1,x2,···,xn)，其中列向量 xi是d 維的數(shù)據(jù)特征，有以下的距離定義。

2.1 歐幾里得距離

歐氏距離計算 n 維空間中兩個點之間的實際距離，也可以計算圖像的相似度。歐氏距離越小相似度越大。歐氏距離的定義如式(1)所示。

2.2 漢明距離

漢明距離通過比較二進制每一位是否相同來計算二進制數(shù)據(jù)的相似度，若不同則漢明距離加1。漢明距離定義如式(2)所示。

如成對數(shù)據(jù)00和01、01和11的漢明距離都為1，00和11的漢明距離為2。二進制數(shù)據(jù)相似度越高，對應(yīng)的漢明距離越小。

2.3 漢明親和度

漢明親和度計算兩個二進制數(shù)據(jù)的內(nèi)積。親和度是距離的非線性函數(shù)，因此均勻地近似親和度將導(dǎo)致近似具有不均勻的距離。但是近似親和度矩陣可以化為二元矩陣分解問題。漢明親和度定義如式(3)所示。

2.4 余弦相似度

余弦相似度利用兩個向量夾角 θ的余弦值來衡量兩個向量之間的相似度。兩個向量越相似夾角越小，余弦值越接近1。余弦相似度定義如式(4)所示。

2.5 Jaccard相似度

給定兩個集合 A,B ，Jaccard系數(shù)定義為A 與 B交集大小與并集大小的比值，Jaccard值越大說明相似度越高。Jaccard相似度定義如式(5)所示。

其中| ·|表示集合中元素的個數(shù)。

3 損失函數(shù)

由于高維數(shù)據(jù)映射到低維數(shù)據(jù)過程，或者量化過程都會丟失一定的信息。為了盡量保證信息的完整，以及提高哈希檢索的效率，將更多的相似數(shù)據(jù)映射到相同的二進制代碼中，通常需要使用損失函數(shù)對映射和量化過程進行約束和判斷。

現(xiàn)有方法傾向于優(yōu)化單一形式的哈希散列函數(shù)，其參數(shù)針對整體損失函數(shù)直接優(yōu)化。優(yōu)化過程與所選擇的哈希散列函數(shù)族相結(jié)合。不同類型的哈希散列函數(shù)提供了測試時間和排名準確度之間的權(quán)衡。例如，簡單線性感知器函數(shù)與核函數(shù)相比在評估效率上相對較高，但在最近鄰檢索的準確率上相對較低。

本節(jié)對不同的損失函數(shù)進行分類介紹。

3.1 按照計算距離的方法分類

根據(jù)前文介紹的距離計算方法，哈希散列方法的損失函數(shù)主要用到漢明距離和漢明親和度兩種度量方式控制信息損失。

3.1.1 基于相似和不相似數(shù)據(jù)對的漢明距離

比如二元重構(gòu)嵌入(Binary Reconstructive Embedding)[8]方法。BRE損失函數(shù)定義如式(6)所示。

其中， bi和 bj表示二進制代碼，dh表示漢明距離計算。利用漢明距離比較二進制代碼之間的差異位數(shù)，并除以二進制代碼長度 m將數(shù)值控制在[0,1]的范圍內(nèi)。sij是有監(jiān)督模型下對應(yīng)數(shù)據(jù)樣本 xi和 xj的相似度標簽，若兩者相似則 sij=1， 否則 sij=0。最小化有監(jiān)督模型標簽與二進制代碼相似度的歐氏距離，即可最優(yōu)化二進制編碼的信息損失。但有監(jiān)督模型標簽并不是必要的，在無監(jiān)督模型下只需最小化二進制代碼的漢明距離即可最優(yōu)化信息損失。

3.1.2 基于漢明親和度

比如核監(jiān)督哈希(Kernels Supervised hashing)[9]方法。KSH損失函數(shù)定義如式(7)所示。

漢明親和度還會結(jié)合其他方法，比如?2-損失，指數(shù)損失，鉸鏈損失。比如半監(jiān)督連續(xù)投影學(xué)習(xí)哈希(Semi-supervised Sequential Projection Learning Hashing)[10]。SPLH損失函數(shù)定義如式(8)所示。

其中， exp 表示指數(shù)損失， bTibj表示漢明親和度值，sij是半監(jiān)督模型下的相似度標簽。當二進制代碼越相似時，指數(shù)損失的值越小。最小化指數(shù)損失值即可最優(yōu)化二進制編碼的信息損失。

3.2 按照形式分類

哈希散列方法的損失函數(shù)按照形式劃分主要有3類，分別是線性感知器函數(shù)，核函數(shù)和特征函數(shù)。

3.2.1 線性感知器函數(shù)

比如均衡哈希(Harmonious Hashing)[11]方法。HH損失函數(shù)定義如式(9)所示。

其中， sgn表示符號函數(shù)，若值大于零則返回1，否則返回-1。 ω表示映射矩陣，將高維數(shù)據(jù) x映射成低維連續(xù)數(shù)據(jù)。 b表示偏置參數(shù)，不是必須設(shè)置的。線性感知器函數(shù)由于其計算快速的特點，是哈希方法中常用的損失函數(shù)類型。

3.2.2 核函數(shù)

比如可伸縮核哈希(Scalable Kernel Hashing)[12]。SKH方法損失函數(shù)定義如式(10)所示。

其中 sgn表示符號函數(shù)，ω 表示映射矩陣，b 表示偏置參數(shù)。表 示核函數(shù)表示數(shù)據(jù)中心點。核函數(shù)通常定義為空間中任一點 x 到某一中心之間歐氏距離的單調(diào)函數(shù)。核函數(shù)有許多類型，比如高斯核函數(shù)κ (x,y)=exp(-‖x-y‖2/2σ2)、 線性核函數(shù)κ(x,y)=xTy等等。低維空間線性不可分的數(shù)據(jù)通過非線性映射到高維特征空間可以實現(xiàn)線性可分。為了得到線性可分的結(jié)果，常常需要對低維數(shù)據(jù)進行非線性變換。但是非線性變換計算是復(fù)雜的。為了簡便計算，可以使用核函數(shù)直接得到高維數(shù)據(jù)非線性變換的內(nèi)積，從而得到線性可分的結(jié)果。

3.2.3 特征函數(shù)

比如譜哈希(Spectral Hashing)[13]方法。SH方法損失函數(shù)定義如式(11)所示。

其中， tr(·)表 示跡函數(shù)， L 表示圖拉普拉斯矩陣，Y 表示連續(xù)的哈希代碼。 Y的解是圖拉普拉斯矩陣 L的最小k 個特征值對應(yīng)的特征向量。具體的算法將會在第6.2節(jié)介紹。

3.3 按照數(shù)據(jù)對分類

3.3.1 僅考慮相似數(shù)據(jù)對之間的相關(guān)性

比如上文提到的損失函數(shù)都是僅考慮相似數(shù)據(jù)對之間的相關(guān)性。

3.3.2 同時考慮不相似數(shù)據(jù)對之間的差異性

比如彈性嵌入方法(Elastic Embedding)[14]。EE方法的損失函數(shù)定義如式(12)所示。

4 離散約束

由于哈希散列方法的學(xué)習(xí)結(jié)果是二進制代碼B，因此最終的二進制代碼一般具有離散約束，離散約束的定義如式(13)所示。

其中，約束的第一項表示二進制代碼 B遵循二值化約束；第二項表示二進制代碼 B遵循平衡性約束，即每位編碼可能為1或者0的概率為50%；第三項表示二進制代碼 B遵循不相關(guān)性約束，即每位編碼與其他編碼互不相關(guān)。

到目前為止，很少有方法直接工作在離散空間中。參數(shù)敏感哈希(Parameter-Sensitive Hashing)[15]和二元重構(gòu)嵌入方法通過逐步調(diào)整由函數(shù)生成的代碼來學(xué)習(xí)預(yù)定義哈希散列函數(shù)的參數(shù)。迭代量化哈希(Iterative Quantization)[16]迭代地學(xué)習(xí)代碼過程中明確地施加了二進制約束。雖然迭代量化哈希和二元重構(gòu)嵌入方法工作在離散空間中并生成哈希代碼，但它們不能很好地捕獲代碼空間中原始數(shù)據(jù)的局部鄰域。迭代量化哈希的目標是最小化二進制代碼和主成分分析(Principle Component Analysis)[17]結(jié)果之間的量化誤差。二元重構(gòu)嵌入訓(xùn)練漢明距離來模擬有限數(shù)量的采樣數(shù)據(jù)點之間的 ?2-距離，但由于復(fù)雜的優(yōu)化程序，無法訓(xùn)練整個數(shù)據(jù)集。

由于離散約束的不連續(xù)問題，在優(yōu)化時非常困難。因此對離散約束的處理方法有3種，分別是：忽略離散約束，放松離散約束和保持離散約束。

4.1 忽略離散約束

忽略離散約束通常指忽略平衡性約束或不相關(guān)性約束，其中主要忽略平衡性約束。比如迭代量化哈希為了減少數(shù)據(jù)之間的量化誤差，使用了旋轉(zhuǎn)矩陣將投影矩陣旋轉(zhuǎn)到量化誤差最小的方向。最終二進制代碼的定義如式(14)所示。

其中 X 表示訓(xùn)練集， P表示由主成分分析對訓(xùn)練集分解得到的投影矩陣， R表示正交旋轉(zhuǎn)矩陣。從式(14)可得，直接使用符號函數(shù)導(dǎo)致二進制代碼正負值并不均等，完全忽略了平衡性約束。而即使PCA分解得到的特征向量(投影矩陣) P是不相關(guān)的，正交矩陣R 也是不相關(guān)的。但與訓(xùn)練集 X相乘后，不能保證其不相關(guān)性，故也忽略了不相關(guān)性約束。

4.2 放松離散約束

放松離散約束通常指對離散約束進行松弛優(yōu)化，圍繞連續(xù)解來獲得二進制代碼。放松離散約束是常見的兩步法哈希，即先投影后量化。投影的結(jié)果是連續(xù)值(實值) Y 。投影過程中保持Y 的平衡性和不相關(guān)性。最后量化成二進制代碼 B 時能較好地保持 B的離散性。比如譜哈希通過圖拉普拉斯的特征分解得到連續(xù)矩陣Y ，該結(jié)果使用符號函數(shù)量化后可得到二進制代碼 B。由于各特征向量是線性無關(guān)的，因此連續(xù)矩陣Y 中的每個向量保持不相關(guān)性。通過量化后的二進制代碼 B也 能保持不相關(guān)性。但在求解 B的時候使用了符號函數(shù)，依然忽略了平衡性。因此該算法是屬于放松了離散約束，先圍繞連續(xù)解 Y進行求解，最后量化成二進制代碼 B。

4.3 保持離散約束

保持離散約束是指將投影和量化結(jié)合起來進行交替求解。比如離散圖哈希(Discrete Graph Hashing)[18]方法。DGH方法的定義如式(15)所示。

其中， B 表示二進制代碼，Y 表示近似于 B的連續(xù)代碼。即使保持離散約束，還是需要求解連續(xù)代碼Y ，然后通過最優(yōu)化二進制代碼 B 和連續(xù)代碼Y 之間的信息損失，來獲得最優(yōu)解的二進制代碼 B。上述公式中第一項表示譜哈希的圖拉普拉斯構(gòu)造，第二項表示通過歐氏距離量化二進制代碼 B 和連續(xù)代碼 Y之間的信息損失。在一步法中，即使需要求解連續(xù)代碼 Y，但因為交替迭代求解過程中保持了二進制代碼 B的離散約束。這樣能減少過度優(yōu)化離散約束帶來的信息損失。

5 外樣本學(xué)習(xí)

面對龐大的數(shù)據(jù)集，一般無法直接學(xué)習(xí)所有數(shù)據(jù)的哈希散列函數(shù)和二進制代碼。通常選取少量的樣本進行訓(xùn)練得到投影矩陣，對于新的樣本或者測試集，利用投影矩陣可以直接生成二進制代碼，這稱之為外樣本學(xué)習(xí)。如何加快外樣本學(xué)習(xí)，是提高在線哈希檢索的關(guān)鍵。幾種常用的外樣本學(xué)習(xí)方法包括：直接學(xué)習(xí)投影矩陣，引入期望學(xué)習(xí)測試數(shù)據(jù)的分布，近似投影矩陣和機器學(xué)習(xí)算法學(xué)習(xí)投影矩陣。

5.1 直接學(xué)習(xí)投影矩陣

很多哈希散列方法并不直接學(xué)習(xí)二進制編碼B，而是學(xué)習(xí)高效的投影矩陣 P。這樣不僅可以快速地對外樣本進行投影得到新的二進制代碼，還可以在學(xué)習(xí)過程中通過添加不同的約束實現(xiàn)不同的特征選擇效果。比如迭代量化哈希直接對訓(xùn)練數(shù)據(jù)進行主成分分析，求解出投影矩陣 P對高維的訓(xùn)練數(shù)據(jù)進行降維。這樣新測試樣本也可以直接通過投影矩陣P 編碼成二進制代碼 B。

5.2 引入期望學(xué)習(xí)測試數(shù)據(jù)的分布

引入期望學(xué)習(xí)測試數(shù)據(jù)分布的前提是認為數(shù)據(jù)遵循某種分布，通過學(xué)習(xí)訓(xùn)練數(shù)據(jù)后，可以根據(jù)數(shù)據(jù)分布情況編碼出測試數(shù)據(jù)的二進制代碼 B。比如譜哈希認為數(shù)據(jù)是均勻分布的，故圖拉普拉斯的特征向量(投影矩陣)和特征值都是均勻分布下的期望值，定義如式(16)所示。

其中，數(shù)據(jù)均勻分布在 [a,b]范 圍內(nèi)。特征向量Φk(x)表示訓(xùn)練樣本 X對應(yīng)的第k 位二進制編碼。特征值λk為特征向量Φk(x) 對應(yīng)的第k 小的特征值。

5.3 近似投影矩陣

近似投影矩陣是指不直接學(xué)習(xí)訓(xùn)練數(shù)據(jù) X對應(yīng)的投影矩陣 P，而是對訓(xùn)練數(shù)據(jù) X進行變換得到新的數(shù)據(jù) X～ ，然后學(xué)習(xí)新數(shù)據(jù) X～ 對應(yīng)的投影矩陣 P～。由于變換后的新數(shù)據(jù) X～具有更良好的特征，比如維度更小、數(shù)據(jù)間的區(qū)分度更大，通過學(xué)習(xí)這些數(shù)據(jù) X～的投影矩陣 P～，將會更好地線性區(qū)分不同的樣本，獲得更好的二進制代碼 B。

比如錨圖哈希(Anchor Graph Hashing)[19]方法。AGH方法對訓(xùn)練集 X 進行聚類獲得聚類中心U (也稱為錨點)，然后計算訓(xùn)練集與錨點之間的相似矩陣 Z，定義如式(17)所示。

并通過相似矩陣 Z 構(gòu)建錨圖 A(類似于譜哈希中的拉普拉斯圖)。錨圖 A的定義如式(18)所示。

5.4 機器學(xué)習(xí)算法學(xué)習(xí)投影矩陣

如果哈希散列函數(shù)無法直接求解投影矩陣 P或者近似投影矩陣 P～， 可以先求解出二進制代碼 B或者連續(xù)代碼Y ，然后通過機器學(xué)習(xí)算法對原始數(shù)據(jù)和二進制代碼 B或連續(xù)代碼Y 進行學(xué)習(xí)，進而求解出投影矩陣 P。定義如式(20)所示。

典型的方法比如稀疏哈希(Sparse Hashing)[20]。稀疏哈希無法直接學(xué)習(xí)投影矩陣，利用字典進行外樣本學(xué)習(xí)的效果也不好。因此使用機器學(xué)習(xí)算法典型相關(guān)分析(Canonical Correlation Analysis)[21]學(xué)習(xí)投影矩陣。

6 哈希散列算法介紹

哈希散列算法可分類為無監(jiān)督哈希、有監(jiān)督哈希和半監(jiān)督哈希。有監(jiān)督哈希和半監(jiān)督哈希的學(xué)習(xí)需要數(shù)據(jù)的標簽信息，由于標簽的采集和學(xué)習(xí)需要額外的消耗，因此本文主要關(guān)注更簡便的無監(jiān)督哈希算法。本節(jié)中將詳細介紹幾個典型的無監(jiān)督哈希算法以及它們的相關(guān)方法。

6.1 局部敏感哈希

局部敏感哈希(Locality-Sensitive Hashing)由A.Gionis等[22]于1999年在VLDB數(shù)據(jù)庫會議(Very Large Data Bases)上提出，首次引入了哈希散列的概念。

局部敏感哈希是與數(shù)據(jù)不相關(guān)的哈希檢索算法。數(shù)據(jù)不相關(guān)是指將原始高維數(shù)據(jù) X映射成低維二進制代碼 B過程中并不探索數(shù)據(jù)的內(nèi)部結(jié)構(gòu)，因此通過投影得到的二進制代碼 B的數(shù)據(jù)區(qū)分度并不明顯。局部敏感哈希的算法通過隨機構(gòu)造一個投影矩陣 P ，將原始數(shù)據(jù)映射成短編碼的二進制數(shù)據(jù) B。局部敏感哈希方法的定義如式(21)所示。

由于隨機投影方法需要增加編碼長度來提高準確率，因此局部敏感哈希的實際應(yīng)用有限。但局部敏感哈希提出的兩點思想奠定了哈希散列方法的基礎(chǔ)：

(1) 數(shù)據(jù)通過投影變換后，相鄰數(shù)據(jù)點在新的數(shù)據(jù)空間中仍然相鄰的概率很大，而不相鄰的數(shù)據(jù)點被映射到同一個桶的概率很小。

(2) 如果原始空間中相鄰的數(shù)據(jù)落入相同的桶，那么在超大集合內(nèi)查找相鄰元素的問題轉(zhuǎn)化為在一個很小的集合內(nèi)查找相鄰元素的問題。

為了提高局部敏感哈希的性能，Datar等[23]提出了p-穩(wěn)態(tài)分布哈希，在歐氏空間下使用 ?p-范數(shù)代替?2-范數(shù)計算數(shù)據(jù)相似度，提高了計算效率，投影的結(jié)果服從p-穩(wěn)態(tài)分布。Kulis等[24]提出核化局部敏感哈希(Kernelized Locality-Sensitive Hashing)，使用核函數(shù)求解哈希函數(shù)而不是隨機投影。Lin等[25]提出了密度敏感哈希算法，該算法使用K-均值聚類(Kmeans)方法構(gòu)建相鄰組探索數(shù)據(jù)的局部結(jié)構(gòu)，并根據(jù)熵值選取信息量最大的超平面進行投影。

6.2 譜哈希

為了改進局部敏感哈希對數(shù)據(jù)進行隨機投影產(chǎn)生的低效二進制代碼，譜哈希提出使用無向圖探索數(shù)據(jù)內(nèi)部結(jié)構(gòu)，見圖1。譜哈希認為數(shù)據(jù)可以根據(jù)其相鄰程度構(gòu)造成無向圖，如圖1(a)所示。根據(jù)無向圖可以構(gòu)造出鄰接矩陣 W，如圖1(b)所示，若 xi和 xj相鄰則Wij=1， 否則Wij=0。利用鄰接矩陣可以構(gòu)造出圖拉普拉斯矩陣 L= D-W ，其中 D是鄰接矩陣的行的和的對角陣，如圖1(c)。 L矩陣是一個對稱方陣。通過對圖拉普拉斯矩陣 L進行特征分解，得到圖1(d)中的特征值和特征向量，舍棄0特征值，選取最小的特征值0.4對應(yīng)的特征向量并將其按照正負進行劃分。可以看出相似的A、B、C被分成了一類，而D、E、F、G被分成了另一類。結(jié)果符合預(yù)期。

圖 1 譜哈希的使用無向圖探索數(shù)據(jù)內(nèi)部結(jié)構(gòu)演示Fig.1 Undirected graph (a), affinity matrix (b), graph Laplacian (c) and eigendecomposition of graph Laplacian (d) of Spectral Hashing

其中，約束的第一項表示二進制代碼 B遵循二值化約束；第二項表示二進制代碼 B遵循平衡性約束，即每位編碼可能為1或者0的概率為50%；第三項表示二進制代碼 B遵循不相關(guān)性約束，即每位編碼與其他編碼互不相關(guān)。在離散約束下直接求解問題(22)是個NP難問題，可以在連續(xù)空間中對其進行譜放松，定義如式(23)所示。

其中， L= D-W是圖拉普拉斯。問題(23)的解就是連續(xù)空間中圖拉普拉斯的最小k 個特征值對應(yīng)的特征向量，但需要使用符號函數(shù)量化 Y后才得到目標的二進制代碼 B。

譜哈希通過構(gòu)造相似度矩陣，學(xué)習(xí)了數(shù)據(jù)的局部結(jié)構(gòu)。而Su等[26]在主成分分析的啟發(fā)下，提出在圖拉普拉斯中添加全局方差約束，同時考慮數(shù)據(jù)的全局和局部結(jié)構(gòu)，使得二進制編碼保留了更多的有效信息。

譜哈希學(xué)習(xí)數(shù)據(jù)分布的期望函數(shù)，對外樣本進行編碼。但實際應(yīng)用中，數(shù)據(jù)的分布并不均勻，因此使用期望函數(shù)編碼外樣本的性能較低。為了改進這個問題，Bodó等[27]提出了線性譜哈希(Linear Spectral Hashing)，通過尋找圖拉普拉斯特征空間中的最優(yōu)超平面，將原始高維數(shù)據(jù)映射成低維二進制數(shù)據(jù)。但線性譜哈希要求相似矩陣必須是非負的，因此限制了它的應(yīng)用。Xia等[28]提出引用量化誤差最小化，同時求解圖拉普拉斯特征問題和哈希函數(shù)，哈希函數(shù)可以直接用于外樣本編碼。

6.3 錨圖哈希

盡管譜哈希在學(xué)習(xí)數(shù)據(jù)的內(nèi)部流形結(jié)構(gòu)上取得不錯的效果，但當樣本數(shù)量n 很大時鄰近矩陣的構(gòu)建非常耗時，不適合在線檢索。

為了克服這個缺點，Liu等[19]提出了錨圖哈希。錨圖哈希對訓(xùn)練集 X 進行聚類獲得m 個聚類中心[u1,u2,···,um]， 也稱為錨點。由于m ?n，聚類的速度很快。接著錨圖哈希計算所有數(shù)據(jù)樣本和錨點之間的截斷相似度 Z。

總而言之，錨圖哈希相對譜哈希在學(xué)習(xí)過程中內(nèi)存和計算量需求都很小，并且保持了數(shù)據(jù)的流形結(jié)構(gòu)，因此它的實際應(yīng)用更廣泛。因此許多哈希散列算法都基于錨圖進行學(xué)習(xí)[29-30]。

然而錨圖哈希存在過分依賴聚類結(jié)果的情況，錯誤的聚類結(jié)果會降低錨圖哈希的檢索性能。因此，Takebe等[31]提出基于數(shù)據(jù)的錨圖選擇方法(Data-Dependent Anchor Selection)，認為錨圖是完整數(shù)據(jù)集的低維表示，通過主成分分析降維學(xué)習(xí)錨圖的效果比聚類學(xué)習(xí)更好。

6.4 迭代量化哈希

迭代量化哈希是另一個經(jīng)典的哈希算法。迭代量化通過主成分分析得到投影矩陣 P，但它認為該投影矩陣不能很好地區(qū)分數(shù)據(jù)間的差異。它希望通過交替最小化方案，找到零中心數(shù)據(jù)的旋轉(zhuǎn)，以便最小化該數(shù)據(jù)映射到零中心的二進制超立方體頂點的量化誤差，從而得到最優(yōu)的二進制代碼。迭代量化哈希的定義如式(25)所示。其中旋轉(zhuǎn)矩陣Q 是隨機構(gòu)造正交矩陣。迭代量化哈希不僅可以與主成分分析進行耦合，還可以與正交基礎(chǔ)上的任何投影耦合，提高算法的結(jié)果[32-33]。比如，可以將迭代量化分析與典型相關(guān)分析相結(jié)合，以整合干凈或嘈雜的類標簽中的信息，提高代碼的語義一致性。

迭代量化哈希的投影結(jié)果是各向異性的，即每個哈希函數(shù)映射的結(jié)果方差各不相同，方差大的向量將會攜帶更多的信息。為了平均每個哈希函數(shù)的效率，Kong等[34]提出了各向同性哈希(Isotropic Hashing)，通過添加各向同性約束保證每個哈希函數(shù)的映射結(jié)果方差相等，提高了哈希檢索的效率。此外，Xia等[35]對投影矩陣 P施 加了 ?0-范數(shù)約束，提出了稀疏投影哈希(Sparse Projection Hashing)，投影矩陣的稀疏性可以提高特征選擇能力和計算效率。Xu等[36]提出了雙線性迭代量化哈希(Bilinear Iterative Quantization Hashing)，使用了兩個投影矩陣進行投影，減小了投影矩陣的維度并提高了計算的效率，投影效果與迭代量化哈希相匹配。

6.5 聯(lián)合稀疏哈希

譜哈希和錨圖哈希都存在兩個缺點：第一是學(xué)習(xí)哈希函數(shù)過程中忽略了特征選擇；第二是投影和量化是一個兩階段過程，采用了譜松弛，無法減少數(shù)據(jù)從高維到低維的信息損失。

根據(jù)數(shù)據(jù)降維和聚類領(lǐng)域的研究，提高哈希函數(shù)特征選擇能力的一種可行方法是增加哈希函數(shù)的稀疏性。因此，Zheng等[37]結(jié)合了稀疏表示和圖拉普拉斯，提出了圖正則化稀疏編碼(Graph Regularized Sparse Coding)。Zhu等[20]提出稀疏哈希，在圖正則化稀疏編碼的基礎(chǔ)上增加解的非負性約束，進一步提高原始數(shù)據(jù)與二進制編碼間的語義相似性。Ding等[38]提出了稀疏嵌入哈希(Sparse Embedded Hashing)，利用線性嵌入方法將稀疏表示和主成分分析的結(jié)果結(jié)合起來，使得結(jié)果同時保留了主成分分析的有用信息和稀疏性。

然而以上的方法學(xué)習(xí)稀疏字典的過程較慢，并且沒有解決譜松弛帶來的信息損失問題。因此，聯(lián)合稀疏哈希(Joint Sparse Hashing)[39]提出使用 ?2,1-范數(shù)來提高投影矩陣的特征選擇能力，并且采用一步法模型交替求解投影和量化兩個子問題。

6.6 離散譜哈希

根據(jù)本文第4部分提出的離散約束問題，上文介紹的各種算法都存在一定程度的離散松弛問題。在連續(xù)空間中求解原始數(shù)據(jù)的投影或者哈希代碼然后量化成二進制代碼的過程增加了原始空間到離散空間的信息損失。

盡管離散約束難以求解，但Liu等[18]通過懲罰離散代碼與引入的連續(xù)變量之間的距離直接求解離散代碼，提出了離散圖哈希。但離散圖哈希的平衡約束和不相關(guān)約束依然工作在連續(xù)空間中。Hu等[40]提出了類似離散圖哈希模型的角度重構(gòu)嵌入方法(Angular Reconstruction Embedding)，但使用了余弦距離計算二進制代碼與原始數(shù)據(jù)的距離，并且可以同時學(xué)習(xí)投影矩陣。角度重構(gòu)嵌入方法在離散空間中保持了離散約束，但沒有保留原始數(shù)據(jù)的局部結(jié)構(gòu)。

為了更好地求解離散代碼，Hu等[41]提出了離散譜哈希(Disctrete Spectral Hashing)，結(jié)合了譜哈希和迭代量化哈希的思想，將兩步法合成一步，交替求解問題。具體算法如式(27)所示。

其中，第一項是圖拉普拉斯，第二項是類似迭代量化哈希的旋轉(zhuǎn)操作。式(27)中雖然使用了連續(xù)值 Y，但是離散代碼 B并沒有單獨求解，依然保持了二值性和平衡性的離散約束。而不相關(guān)性約束，放松到連續(xù)空間Y 中。由于 Y和Q 都是不相關(guān)的，它們相乘的結(jié)果也是不相關(guān)的，則 B的求解結(jié)果也是不相關(guān)的，因此B也能保持不相關(guān)約束。從而較好地保持了離散約束。此外，由于連續(xù)值依然在譜哈希中求解，故能保持原始數(shù)據(jù)的流型結(jié)構(gòu)。

7 實驗

7.1 評估標準

采用傳統(tǒng)的評估指標，包括漢明排名和哈希查找。具體來說，漢明排名側(cè)重于整個檢索項目的質(zhì)量，而哈希查找只處理檢索到的最高項目。

平均精度(MAP)是漢明排名評價。平均精度判斷每個測試數(shù)據(jù)是否檢索到正確的鄰近數(shù)據(jù)。此外，哈希查找根據(jù)查詢的半徑為2的漢明球內(nèi)的檢索項來計算{召回率，F(xiàn)-值}分數(shù)。其中召回率(recall)是哈希查找評價，判斷檢測到的正確數(shù)據(jù)與總的正確數(shù)據(jù)的比例。F-值(F-measure)是哈希查找評價，由于精度和召回率評估存在偏差情況，F(xiàn)-measure是綜合兩者進行加權(quán)判斷。此外，還可以通過精度(precision)進行量化。精度是哈希查找評價，側(cè)重于近似最鄰近數(shù)據(jù)的檢索質(zhì)量。在漢明半徑為2的范圍內(nèi)，判斷最鄰近的數(shù)據(jù)是否檢索正確。由于本文研究的哈希方法是無監(jiān)督方法，因此哈希投影之后直接評估保留的最近鄰的數(shù)據(jù)。

7.2 常用數(shù)據(jù)集

哈希檢索常用的數(shù)據(jù)集包括MNIST[42-43]、CIFAR-10[44-45]、Caltech-101[46-47]、SUN397[48-49]、YouTubeFaces[50-51]和NUS-WIDE[52-53]。

7.2.1 MNIST

MNIST數(shù)據(jù)集由70 000個手寫數(shù)字圖像組成，從“0”到“9”。這些圖像都是28×28像素，不進行預(yù)處理，直接使用784維特征向量用于表示。

7.2.2 CIFAR-10

CIFAR-10由60 000個微小圖像組成的集合，共10個對象類別(每個類別6 000個圖像)。每張圖像提取512維的GIST矢量[54]作為圖像特征。

7.2.3 Caltech-101

Caltech 101數(shù)據(jù)集包含9 145張訓(xùn)練圖像，由102類對象類別組成，包括一個背景類。每張圖像使用稀疏編碼技術(shù)將縮放不變性特征變換(Scale-Invariant Feature Transform)[55]預(yù)處理后的數(shù)據(jù)壓縮成1024維數(shù)據(jù)作為表示。

7.2.4 SUN397

SUN397數(shù)據(jù)集由102類對象類別組成，包含106 953張訓(xùn)練圖像(每個類別的圖像個數(shù)80～2 000張不定)。每張圖像使用主成分分析從12 288維深度卷積激活特征(Deep convolutional activation features)[56]提取的數(shù)據(jù)中提取出1 600維特征向量作為圖像特征表示。

7.2.5 NUS-WIDE

NUS-WIDE由269 648個多標簽圖像組成。與MNIST等數(shù)據(jù)集每張圖片都具有唯一標簽不同，NUS-WIDE中每張圖片都擁有多個標簽，兩張被認為相似的圖片中至少共享一個相同標簽。一般選取常見的21個標簽，比如動物、人類、建筑物等，構(gòu)成訓(xùn)練集和測試集樣本。每個樣本使用縮放不變性特征變換將圖像表示為500維數(shù)據(jù)。

7.2.6 YouTubeFaces

YouTube Faces數(shù)據(jù)庫包含1 595個不同人物的3 425個面部視頻。一般選擇具有至少500張面部圖像的樣本來構(gòu)建子集，總共370 319個樣本。每個樣本預(yù)處理成1 770D維的LBP向量[57]作為圖像特征表示。

7.3 實驗結(jié)果

本文在MNIST、CIFAR-10和YouTubeFaces上進行了實驗。MNIST隨機選取了6 900張圖片(每類690張)作為訓(xùn)練集，以及1 000張圖片(每類100張)作為測試集。CIFAR-10隨機選取了5 900張圖片(每類590張)作為訓(xùn)練集，以及1 000張圖片(每類100張)作為測試集。YouTubeFaces隨機選取了圖像數(shù)目大于2 000張的類別共38個類，總共103 390張圖片，其中每類選取100張圖片構(gòu)成測試集，其余圖片作為訓(xùn)練集。

本文選取譜哈希[58]、錨圖哈希[59]、迭代量化哈希[60]、聯(lián)合稀疏哈希[61]和譜旋轉(zhuǎn)譜哈希(Large Graph Hashing with Spectral Rotation)[62-63]作為對比算法。

MNIST 數(shù)據(jù)庫上的結(jié)果如表1、圖2和圖3所示。從表1中可以看出聯(lián)合稀疏哈希和譜旋轉(zhuǎn)譜哈希表現(xiàn)最好。由于聯(lián)合稀疏哈希具有稀疏特征選擇能力，因此隨著編碼長度的增加，它的檢索平均精度也逐步增加，優(yōu)于其他算法。而譜旋轉(zhuǎn)譜哈希由于保持了離散約束，因此在短編碼尤其是12 bits的時候表現(xiàn)優(yōu)異；但它不具備稀疏特征選擇能力，因此隨著編碼長度增加效果不如聯(lián)合稀疏哈希。從圖2和圖3中，可以看出聯(lián)合稀疏哈希獲得最好的召回率。但值得注意，聯(lián)合稀疏哈希在短編碼的召回率過高，存在將大量的圖像都映射成相同的編碼的情況，這種情況在CIFAR-10數(shù)據(jù)庫中表現(xiàn)更加明顯。

表 1 MNIST數(shù)據(jù)庫下各算法的平均精度結(jié)果Table 1 Results of MAP of different algorithms on the MNIST database

圖 2 MNIST數(shù)據(jù)庫下各算法的召回率Fig.2 Results of recall of different algorithms on the MNIST database

圖 3 MNIST數(shù)據(jù)庫下各算法的F-值Fig.3 Results of F-measure of different algorithms on the MNIST database

CIFAR-10數(shù)據(jù)庫上的結(jié)果如表2、圖4和圖5所示。由于8～24 bits的編碼中，聯(lián)合稀疏哈希的召回率都為100%即將所有的編碼映射成同一個編碼，因此它的平均精度并不正確。所以8～24 bits的編碼中認為譜旋轉(zhuǎn)譜哈希的平均精度更高。但隨著編碼長度的增加，聯(lián)合稀疏哈希的平均精度超過了譜旋轉(zhuǎn)譜哈希。從圖4和圖5中，可以看出聯(lián)合稀疏哈希和譜旋轉(zhuǎn)譜哈希都獲得了最好的表現(xiàn)。

YouTubeFaces數(shù)據(jù)庫上的結(jié)果如表3、圖6和圖7所示。由于YouTubeFaces數(shù)據(jù)庫的龐大，而且人臉數(shù)據(jù)庫適合稀疏特征選擇，因此聯(lián)合稀疏哈希的表現(xiàn)遠遠超過了其他算法的表現(xiàn)，獲得了最佳的結(jié)果。在YouTubeFaces數(shù)據(jù)庫下，迭代量化哈希的表現(xiàn)在所有編碼長度上超過了譜旋轉(zhuǎn)譜哈希，這一方面表現(xiàn)出迭代量化哈?？梢云胶鈹?shù)據(jù)的方差的優(yōu)勢，另一方面說明了譜旋轉(zhuǎn)譜哈希過于考慮離散代碼的平衡性情況下有時候會失去效率。

8 總結(jié)

本文介紹了哈希檢索方法的基礎(chǔ)知識以及經(jīng)典的基于數(shù)據(jù)的無監(jiān)督的哈希算法。此外，進行了一系列實驗，以比較現(xiàn)有各種基于哈希的方法的性能。這些方法都是在線檢索方法，表現(xiàn)了哈希檢索算法的效率和可行性。往后，將繼續(xù)研究新穎的哈希散列方法以便在保留更多局部信息、減少信息損失的同時，保持二進制代碼的離散約束，避免哈希檢索性能對于二進制代碼長度的敏感性。為了提高哈希檢索方法的應(yīng)用性，將繼續(xù)探索提高哈希散列學(xué)習(xí)的離線訓(xùn)練和在線編碼的效率，以及短二進制編碼的準確率來達到時間和空間上的高效性。

表 2 CIFAR-10數(shù)據(jù)庫下各算法的平均精度結(jié)果Table 2 Results of MAP of different algorithms on the CIFAR-10 database

圖 4 CIFAR-10數(shù)據(jù)庫下各算法的召回率Fig.4 Results of recall of different algorithms on the CIFAR-10 database

圖 5 CIFAR-10數(shù)據(jù)庫下各算法的F-值Fig.5 Results of F-measure of different algorithms on the CIFAR-10 database

表 3 YouTubeFaces數(shù)據(jù)庫下各算法的平均精度結(jié)果Table 3 Results of MAP of different algorithms on the YouTubeFaces database

圖 6 YouTubeFaces數(shù)據(jù)庫下各算法的召回率Fig.6 Results of recall of different algorithms on the YouTubeFaces database

圖 7 YouTubeFaces數(shù)據(jù)庫下各算法的F-值Fig.7 Results of F-measure of different algorithms on the YouTubeFaces database