基于多比特量化的哈希方法*

汪曙光， 蘇亮亮， 王 琨， 唐 俊

(1.清華大學(xué) 合肥公共安全研究院，安徽 合肥 230601；2.安徽建筑大學(xué) 電子與信息工程學(xué)院，安徽 合肥 230601；3.安徽大學(xué) 電子信息工程學(xué)院，安徽 合肥 230601)

0 引 言

隨著視頻監(jiān)控數(shù)據(jù)的爆炸式增長，從海量數(shù)據(jù)中獲取感興趣的信息時將面臨巨大的時間與存儲代價，使得傳統(tǒng)方法(如窮盡搜索或樹結(jié)構(gòu)[1])無法滿足現(xiàn)實需求。針對該問題，解決方案中基于哈希方法的近似最近鄰搜索是卓有成效的一類方法，具有時間效率高、存儲空間少等優(yōu)點。

哈希方法通過哈希函數(shù)將原始高維數(shù)據(jù)映射到低維的二值編碼空間(哈?？臻g)，這樣不僅極大減少了存儲空間的需求，而且基于二值編碼的數(shù)據(jù)處理也顯著降低了時間代價。通常哈希方法涉及兩個步驟：投影學(xué)習(xí)和量化編碼。前者是將原始數(shù)據(jù)投影到一個超平面而獲得投影值，并使得原始數(shù)據(jù)的相似關(guān)系在投影空間得到保持。在前期的投影學(xué)習(xí)研究中，投影超平面的選取是隨機產(chǎn)生的，典型代表有局部敏感哈希(locality sensitive Hashing,LSH)。與隨機投影方法相比，依賴于數(shù)據(jù)的投影學(xué)習(xí)方法[2～5]既能有效減少編碼長度也能顯著提高檢索效率和精度，通過已有研究發(fā)現(xiàn)，依賴于數(shù)據(jù)的投影策略常常優(yōu)于隨機投影。

量化過程指的是將投影階段產(chǎn)生的投影值轉(zhuǎn)換成二值碼形式，其關(guān)鍵是量化閾值的獲取。與投影研究相比，量化工作得到極少關(guān)注，已提出的大部分哈希方法均采用一個量化閾值來劃分投影值并進行二值編碼，即單比特量化(single bit quantization,SBQ)，其結(jié)果導(dǎo)致大量同類樣本具有不同編碼，進而破壞了原始的相似關(guān)系。針對該問題，學(xué)者們提出了多比特量化策[6～8]來保留原始數(shù)據(jù)的相似關(guān)系。此外考慮到不同投影維可能含有的信息量不同，已有自適應(yīng)比特量化方法[9]被提出。然而上述大部分多比特量化方法是基于投值維數(shù)據(jù)來完成量化閾值的獲取，但事實上，數(shù)據(jù)的投影值并不能夠有效反映原始數(shù)據(jù)的信息分布。本文提出了一種新的基于馬修斯相關(guān)性系數(shù)(Matthews correlation coefficient，MCC)計分與編碼一致性的多比特量化方法，該方法直接利用原始空間中的數(shù)據(jù)信息來指導(dǎo)量化閾值的學(xué)習(xí)進而實現(xiàn)多比特編碼，其中MCC計分能夠有效應(yīng)對數(shù)據(jù)不平衡問題。

1 MCC計分

1.1 MCC

MCC是衡量二分類機器學(xué)習(xí)模型性能的重要指標(biāo)。MCC綜合考慮了二分類的所有分類情況，即正樣本被識別為正類(TP)或負類(FN)和負樣本被識別為正類(FP)或負類(TN)，相對于其他度量準(zhǔn)則，如正確率、精確度和召回率等，MCC能夠更有效地應(yīng)對不平衡數(shù)據(jù)問題，進而提供更加客觀的分類性能評價。本文稱MCC為MCC計分，即

MCC=

(1)

1.2 MCC計分

存在訓(xùn)練數(shù)據(jù)集X={x1,x2,…,xN}，N為數(shù)據(jù)規(guī)模，定義樣本間的相似關(guān)系矩陣S

(2)

式中d(xi,xj)為樣本xi和xj的歐氏距離，D為距離閾值。將X投影到一個超平面上，于是得到一組實值Y=[y1,y2,…，yN]，其中yi是xi的投影值，i=1,2,…,N。本文主要專注于數(shù)據(jù)投影后的量化編碼，即利用2q-1(q≥2)個量化閾值劃分單個投影維為2q個區(qū)域，使得每個投影值進入其中一個區(qū)域，利用q個比特去編碼每個投影值，使得相似數(shù)據(jù)的投影值具有相似的多比特編碼，反之不相似數(shù)據(jù)，則多比特編碼顯著不同。

為了獲取有效的多比特編碼，構(gòu)建了MCC計分函數(shù)，具體為：利用已知量化閾值T={t1,t2,…,t2q-1}，t1≤t2≤…≤t2q-1，將投影值Y=[y1,y2,…,yN]劃分到2q個區(qū)域{sec0,sec1,…,sec2q-1}，根據(jù)劃分，分別計算統(tǒng)計量TP,TN,FP,FN，即處于同一區(qū)域內(nèi)的相似樣本對數(shù)目(TP)與非相似樣本對數(shù)(FP)和處于不同區(qū)域內(nèi)的相似樣本對數(shù)(FN)和非相似樣本對數(shù)(TN)，最后依據(jù)式(1)構(gòu)建MCC計分。

(3)

φxj計算與φxi類似,本文距離計算均采用歐氏距離。結(jié)合式(3)，TP,TN,FP,FN計算如下

(4)

式中 〈a,b〉為a與b是否相等，如果相等,返回1;否則,返回0。在上述計算中，相似關(guān)系矩陣S的對角元素不參與計算。在計算MCC計分的過程中，通常可以發(fā)現(xiàn)相似數(shù)據(jù)對的規(guī)模遠遠小于非相似數(shù)據(jù)對，而MCC計分能夠有效應(yīng)對種不平衡數(shù)據(jù)產(chǎn)生的影響。

2 編碼一致性

(5)

(6)

3 多比特量化

根據(jù)前面的分析，當(dāng)獲取了2q個區(qū)間后，則利用多個比特編碼每個區(qū)間內(nèi)的投影值將變得簡單。如q=2時，則有4個區(qū)域{sec0,sec1,sec2,sec3}，對應(yīng)的編碼方案為用區(qū)域下表索引的二進制形式來表示多比特編碼，即4個區(qū)域內(nèi)數(shù)據(jù)的2 bit編碼為{00,01,10,11}。于是獲取最優(yōu)的量化閾值就成為了關(guān)鍵，本文通過線性組合MCC計分項和編碼一致性量化誤差項E構(gòu)建量化閾值優(yōu)化目標(biāo)函數(shù)

Fobj=α·MCC+(1-α)·(1-E)

(7)

式中參數(shù)α用來平衡MCC和E，通過最大化式(7)，可以獲得一組最優(yōu)的量化閾值T*

(8)

式中T為候選的一組量化閾值。為了獲得T*，本文將選用遺傳算法優(yōu)化目標(biāo)函數(shù)，該算法通過迭代能夠逐漸逼近最優(yōu)解。

遺傳算法的初始設(shè)置：假設(shè)每個投影維需要2q-1個閾值，編碼每個閾值的精度為64 bit(preci)，于是級聯(lián)被這些閾值編碼便形成一條染色體。通過實驗我們報告了相關(guān)參數(shù)的設(shè)置，包括初始種群(染色體數(shù))為Npop=15，變異概率為Pmut=0.001，交叉概率為Pcro=0.7，新染色體比例為Pggap=0.9，最大繁殖代Nmaxg=20?；谶z傳算法優(yōu)化量化閾值:

輸入：相似關(guān)系矩陣S，投影值Y，α，q，NpopPmut，Nmaxg，Pggap，Pcro；

輸出：量化閾值T*。

初始化：隨機產(chǎn)生初始種群Chrom∈{0,1}Npop×(2q-1)×Preci，Chrom中每一行代表一組候選量化閾值

Whilen←1 toNmaxgdo

1)解碼Chrom為Npop組候選量化閾值{T1,T2,…,TNpop}，并根據(jù)式(7)計算初始種群中所有個體的適應(yīng)度；

2)排序這些適應(yīng)度，從Chrom中選取適應(yīng)度高的[Npop×Pggap]個體進行繁殖，記為Chrom′；

3)基于Pcro，對Chrom′中[Npop×Pggap]/2對染色體進行交叉操作；

4)基于Pmut，對交叉后Chrom′中染色體進行突變操作；

5)利用精英選擇方法，合并Chrom′進入Chrom；

end

4 實驗與結(jié)果分析

4.1 數(shù)據(jù)集與實驗設(shè)置

本文在典型的圖像數(shù)據(jù)集MNIST上對多比特量化哈希算法進行了評估。對于MNIST數(shù)據(jù)集，隨機抽取1 000個樣本作為測試集，1 000個樣本作為訓(xùn)練集，余下的作為數(shù)據(jù)庫樣本，每組實驗進行10次，其結(jié)果取平均值。在本文中，采用歐氏距離定義原始特征空間樣本的相似關(guān)系，計算每個樣本的第50個近鄰點，對其歐氏距離取平均，小于等于平均距離的將被視為近鄰點(相似的)，否則視為非近鄰點(非相似的)。另外本文采用典型度量指標(biāo)對不同的多比特量化進行評估，包括精確度(precision，P)、召回率(recall，R)和P-R曲線面積(auprc)，即以召回率為自變量，以精確度為因變量構(gòu)成的曲線與坐標(biāo)圍成的面積，即

(9)

4.2 投影方法與量化方法

本文工作主要專注于哈希方法中量化編碼階段，因此投影方法將采用典型的LSH[2]，PCAH[4]，SH[3]和ITQ[5]方法；為了比較本文方法與其他多比特量化方法，選取了傳統(tǒng)的SBQ方法以及近年來提出的具有代表性的多比特量化方法——DBQ[7]，MH[8]和NPQ[9]方法，其中SBQ，DBQ，MH為無監(jiān)督量化方法，而NPQ為有監(jiān)督量化方法。通過投影方法與量化方法的不同組合，可以得到具體的哈希方法，如“PCAH+Ours”表示一個哈希方法，其投影維由PCAH方法產(chǎn)生，而量化工作則被本文方法完成；需要注意的是，“PCAH+SBQ”等價于原始的PCAH哈希方法，對其他投影方法，類似。根據(jù)文獻[8]，設(shè)定所有量化方法均采用2 bit量化編碼每個投影維。

4.3 結(jié)果與分析

本文對參數(shù)α進行了分析，圖1顯示了在不同投影方法和不同碼字規(guī)模下，指標(biāo)Auprc隨著α的變化情況，其中投影方法選取的是LSH和ITQ方法。從圖中可知，當(dāng)碼字長度較短(≤96 bit)時，在α∈[0.2 0.5]情況下Auprc值能夠達到最大的值；當(dāng)碼字長度較大時(≥96 bit),則α∈[0 0.2]能產(chǎn)生最好的效果。

圖1 參數(shù)α對Auprc的影響

表1給出了編碼長度為32 bit和128 bit時的檢索表現(xiàn)。表中每個值表示一個具體的哈希方法(即投影方法+量化方法)在特定碼字規(guī)模下的Auprc值，其最好的結(jié)果用粗體標(biāo)記。從表1中可以觀察，相對于數(shù)據(jù)獨立的量化方法(SBQ)，數(shù)據(jù)依賴的量化方法(DBQ，MH，NPQ和本文方法)能顯著哈希檢索的效果，同時這些方法用到的投影維數(shù)只有SBQ方法的1/2，些發(fā)現(xiàn)表明多比特量化方法可以顯著減少對投影維的需求，也驗證了量化編碼的研究對哈希檢索具有巨大的促進作用。此外，對比無監(jiān)督方法(DBQ和MH)，有監(jiān)督的量化策略(NPQ和Ours)對檢索表現(xiàn)達到了約10 %的促進作用。最后，對比所有方法，本文方法的效果均超過了其他流行的量化方法。

表1 MNIST數(shù)據(jù)集上的量化方法比較

基于4種不同的投影方法，圖2提供了不同多比特量化策略在MNIST數(shù)據(jù)集上的P-R曲線，無論是在短編碼(32 bit)下還是在長編碼(128 bit)下，本文方法都產(chǎn)生了最好的結(jié)果，分析原因是本文提出的多比特量化方法，充分利用了原始數(shù)據(jù)的相似度信息及局部結(jié)構(gòu)信息，并在編碼一致性的約束下，使得原始數(shù)據(jù)的近鄰結(jié)構(gòu)在哈希碼空間得到有效保持。這一結(jié)果表明了，相對于其他量化方法，利用原始數(shù)據(jù)的信息來指導(dǎo)量化編碼更加有效。

圖2 MNIST數(shù)據(jù)集的P-R曲線

綜上所述，本文提出的多比特量化方法對于提高哈希檢索的表現(xiàn)是可行的、有效的。

5 結(jié) 論

為了在哈希碼空間更有效地維持原始數(shù)據(jù)的相似關(guān)系，本文提出了一種新的多比特量化方法，該方法通過結(jié)合原始數(shù)據(jù)的近鄰關(guān)系及局部信息和數(shù)據(jù)編碼前后的一致性，構(gòu)建了新的目標(biāo)函數(shù)，在遺傳算法的優(yōu)化下，一組最優(yōu)的量化閾值被獲取，從而實現(xiàn)了投影維的多比特量化及編碼。廣泛的實驗結(jié)果顯示本文方法相對于其他多比特量化方法，能夠提供更好的檢索表現(xiàn)。