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

(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ù)映射到低維的二值編碼空間(哈希空間)，這樣不僅極大減少了存儲空間的需求，而且基于二值編碼的數(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)注，已提出的大部分哈希方法均采用一個量化閾值來劃分投影值并進(jìn)行二值編碼，即單比特量化(single bit quantization,SBQ)，其結(jié)果導(dǎo)致大量同類樣本具有不同編碼，進(jìn)而破壞了原始的相似關(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í)進(jìn)而實現(xiàn)多比特編碼，其中MCC計分能夠有效應(yīng)對數(shù)據(jù)不平衡問題。

1 MCC計分

1.1 MCC

MCC是衡量二分類機器學(xué)習(xí)模型性能的重要指標(biāo)。MCC綜合考慮了二分類的所有分類情況，即正樣本被識別為正類(TP)或負(fù)類(FN)和負(fù)樣本被識別為正類(FP)或負(fù)類(TN)，相對于其他度量準(zhǔn)則，如正確率、精確度和召回率等，MCC能夠更有效地應(yīng)對不平衡數(shù)據(jù)問題，進(jìn)而提供更加客觀的分類性能評價。本文稱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ū)域，使得每個投影值進(jìn)入其中一個區(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計分的過程中，通?？梢园l(fā)現(xiàn)相似數(shù)據(jù)對的規(guī)模遠(yuǎn)遠(yuǎn)小于非相似數(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ū)域下表索引的二進(jìn)制形式來表示多比特編碼，即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]個體進(jìn)行繁殖，記為Chrom′；

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

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

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

end

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

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

本文在典型的圖像數(shù)據(jù)集MNIST上對多比特量化哈希算法進(jìn)行了評估。對于MNIST數(shù)據(jù)集，隨機抽取1 000個樣本作為測試集，1 000個樣本作為訓(xùn)練集，余下的作為數(shù)據(jù)庫樣本，每組實驗進(jìn)行10次，其結(jié)果取平均值。在本文中，采用歐氏距離定義原始特征空間樣本的相似關(guān)系，計算每個樣本的第50個近鄰點，對其歐氏距離取平均，小于等于平均距離的將被視為近鄰點(相似的)，否則視為非近鄰點(非相似的)。另外本文采用典型度量指標(biāo)對不同的多比特量化進(jìn)行評估，包括精確度(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ù)文獻(xiàn)[8]，設(shè)定所有量化方法均采用2 bit量化編碼每個投影維。

4.3 結(jié)果與分析

本文對參數(shù)α進(jìn)行了分析，圖1顯示了在不同投影方法和不同碼字規(guī)模下，指標(biāo)Auprc隨著α的變化情況，其中投影方法選取的是LSH和ITQ方法。從圖中可知，當(dāng)碼字長度較短(≤96 bit)時，在α∈[0.2 0.5]情況下Auprc值能夠達(dá)到最大的值；當(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)表明多比特量化方法可以顯著減少對投影維的需求，也驗證了量化編碼的研究對哈希檢索具有巨大的促進(jìn)作用。此外，對比無監(jiān)督方法(DBQ和MH)，有監(jiān)督的量化策略(NPQ和Ours)對檢索表現(xiàn)達(dá)到了約10 %的促進(jìn)作用。最后，對比所有方法，本文方法的效果均超過了其他流行的量化方法。

表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)。