吳家皋，王永榮，鄒志強(qiáng)，胡 斌

(1.南京郵電大學(xué) 計(jì)算機(jī)學(xué)院，江蘇 南京 210023;2.江蘇省大數(shù)據(jù)安全與智能處理重點(diǎn)實(shí)驗(yàn)室，江蘇 南京 210023;3.南京師范大學(xué) 虛擬地理環(huán)境教育部重點(diǎn)實(shí)驗(yàn)室，江蘇 南京 210046)

0 引 言

大數(shù)據(jù)時(shí)代的多媒體數(shù)據(jù)正在迅速增長，例如高清攝像機(jī)生成的數(shù)據(jù)量已達(dá)到約3.6 GB/小時(shí)，并且由如此大量的攝像機(jī)生成的視頻數(shù)據(jù)量將達(dá)到EB級(jí)別[1]。高維數(shù)據(jù)(如圖像和視頻)的特征維度通?？梢赃_(dá)到數(shù)百維甚至數(shù)千維[2-3]，這些高維數(shù)據(jù)通常表現(xiàn)出非結(jié)構(gòu)化特征，因此傳統(tǒng)的處理數(shù)據(jù)方法不能很好地滿足高維數(shù)據(jù)的處理要求，相似性數(shù)據(jù)檢索等任務(wù)正面臨著巨大的困難。

由于在實(shí)際檢索數(shù)據(jù)的時(shí)候，用戶對于檢索效率要比檢索質(zhì)量的要求更高，這也就是說，允許一定的誤差存在于查找結(jié)果和真實(shí)值之間[4]，基于該理念而提出了近似近鄰(approximate nearest neighbor，ANN)算法[5]?，F(xiàn)在，在低維數(shù)據(jù)檢索方面，基于樹結(jié)構(gòu)的近鄰查找的效果很好，它的分類主要是基于數(shù)據(jù)的劃分[6]和基于空間劃分。雖然樹索引算法在處理較低維數(shù)據(jù)時(shí)效果很好，但是近鄰搜索在處理高維數(shù)據(jù)時(shí)遇到了“維度詛咒”問題[7]：樹索引結(jié)構(gòu)算法的效率隨著特征維度的增加而快速下降。在高維數(shù)據(jù)索引方面，基于哈希的索引技術(shù)一直受到國內(nèi)外研究人員的廣泛關(guān)注[8-9]。與基于樹的索引技術(shù)相比，哈希索引技術(shù)在高維數(shù)據(jù)索引上具有顯著的優(yōu)勢：時(shí)間復(fù)雜度低，內(nèi)存占用少。

在眾多哈希索引技術(shù)中，由Indyk和Motwani在1998年提出的局部敏感哈希(locality sensitive hash，LSH)[10]算法是最具代表性的算法之一。它的基本思想是通過一組哈希函數(shù)對特征數(shù)據(jù)建立多張哈希表，使得映射后相似的點(diǎn)沖突的概率大，而不相似的點(diǎn)沖突的概率小，從而將相似和不相似的數(shù)據(jù)能夠進(jìn)行很好的區(qū)分。局部敏感哈希的性能對幾個(gè)參數(shù)非常敏感，而如何選擇這些參數(shù)是算法實(shí)現(xiàn)時(shí)必須考慮的問題。

針對上述問題，文中提出了一種基于二分查找的LSH參數(shù)優(yōu)化方法。首先根據(jù)局部敏感哈希函數(shù)族和圖像檢索的目標(biāo)建立局部敏感哈希優(yōu)化模型，明確指出算法優(yōu)化參數(shù)和優(yōu)化目標(biāo)函數(shù)，然后分析圖像特征數(shù)據(jù)的距離分布特點(diǎn)，得出參數(shù)之間的關(guān)系，最后結(jié)合數(shù)值微分和二分查找提出相應(yīng)的參數(shù)優(yōu)化算法。實(shí)驗(yàn)結(jié)果表明，該方法可以大幅降低算法的復(fù)雜度，提高運(yùn)行效率，同時(shí)保持較高的精確值和召回率的調(diào)和均值F1。

1 相關(guān)工作

1.1 局部敏感哈希算法

局部敏感哈希對數(shù)據(jù)點(diǎn)集利用一組哈希函數(shù)建立多張哈希表，使得經(jīng)過哈希映射后相似的點(diǎn)沖突的概率大，而不相似的點(diǎn)沖突的概率小。自LSH提出以來，與其有關(guān)的各種哈希索引方法相繼被提出。P-Stable LSH[11]將LSH的空間距離計(jì)算由海明空間轉(zhuǎn)移到歐氏空間；Entropy-based LSH[12]在查詢項(xiàng)的周圍隨機(jī)產(chǎn)生擾動(dòng)對象作為查詢項(xiàng)集合，這種算法是以時(shí)間為代價(jià)來減少空間的消耗；Multi-probe LSH[13]通過大量實(shí)驗(yàn)指出幾乎所有候選查詢結(jié)果與查詢對象在相同或者相鄰的映射桶內(nèi)，并據(jù)此提出有效的索引方案；Dynamic Collision Counting(C2LSH)[14]利用一組由多個(gè)單獨(dú)的LSH函數(shù)組成的函數(shù)基底構(gòu)造“動(dòng)態(tài)”的組合哈希函數(shù)，并且提出了一個(gè)新的LSH方案；文獻(xiàn)[15]提出的方法證明至少在漢明空間，與傳統(tǒng)的基于LSH的方法相比可以減少誤報(bào)率問題。

1.2 局部敏感哈希參數(shù)優(yōu)化

局部敏感哈希的性能對幾個(gè)參數(shù)非常敏感，而這些參數(shù)必須在算法實(shí)現(xiàn)時(shí)選擇。算法中需要確定的參數(shù)有：區(qū)間大小w、哈希函數(shù)族維度k、哈希表個(gè)數(shù)L等。局部敏感哈希森林[16]通過固定其中一個(gè)參數(shù)部分解決了這個(gè)問題。然而，算法實(shí)現(xiàn)仍然留下了為其他參數(shù)尋找最優(yōu)值的問題。參數(shù)調(diào)整過程既單調(diào)乏味又嚴(yán)重阻礙算法的應(yīng)用，而目前對這些參數(shù)值的選取提供的指導(dǎo)又很少。文獻(xiàn)[17]中優(yōu)化的最佳參數(shù)有：映射區(qū)間大小w，形成的復(fù)合哈希函數(shù)中哈希函數(shù)的數(shù)量k，哈希表的數(shù)量L，以及每張表中探測到的哈希桶數(shù)量T。先對召回率和選擇性建模并且將其應(yīng)用到參數(shù)優(yōu)化中，這兩個(gè)性能度量被定義為數(shù)據(jù)分布的函數(shù)，而由真實(shí)數(shù)據(jù)得到的分布滿足伽馬分布。然后，在召回率滿足要求的前提下，通過最小化選擇性來計(jì)算最佳參數(shù)。相似的更加完整的參數(shù)優(yōu)化分析由文獻(xiàn)[18]給出。首先將距離分布函數(shù)轉(zhuǎn)變成映射區(qū)間w的沖突概率函數(shù)，然后假設(shè)w和k的值來估計(jì)表的最佳數(shù)量L。鑒于L的估計(jì)，找到最小化搜索時(shí)間成本的k。最后根據(jù)k和L的最佳值找到最好的w。

然而上述優(yōu)化方法的性能指標(biāo)考慮仍不夠周全。為了同時(shí)保證較高的查詢效率和查詢質(zhì)量，并且由于精確率和召回率的加權(quán)調(diào)和平均值F1綜合考慮了精確率和準(zhǔn)確率對圖像檢索算法的影響，所以性能指標(biāo)采用F1，提出使F1取得最大值的局部敏感哈希圖像檢索參數(shù)優(yōu)化方法。為了取得最優(yōu)的F1，可以采用數(shù)值微分結(jié)合二分查找得出參數(shù)之間的關(guān)系。

2 算法描述

2.1 局部敏感哈希優(yōu)化模型

在對局部敏感哈希算法進(jìn)行實(shí)驗(yàn)時(shí)發(fā)現(xiàn)，當(dāng)進(jìn)行算法實(shí)現(xiàn)的時(shí)候，其中的一些參數(shù)需要用戶自己選擇。針對這一問題，文中提出一種局部敏感哈希參數(shù)快速選擇的方法。該方法能根據(jù)局部敏感哈希理論模型和圖像數(shù)據(jù)的距離分布函數(shù)，快速計(jì)算得到最優(yōu)的精確率和召回率的調(diào)和平均F1。

設(shè)任一圖像都能表示為d維特征向量空間Rd中的一個(gè)點(diǎn)，則所有圖像構(gòu)成d維特征向量數(shù)據(jù)集D，DRd；定義局部敏感哈希函數(shù)族H={h|D→U}為從數(shù)據(jù)集D到整數(shù)域U的映射：

(1)

其中，v∈D是任一圖像的特征向量；a是d維正態(tài)分布隨機(jī)向量；b是[0,w]上均勻分布的隨機(jī)實(shí)數(shù)；w是映射區(qū)間大小的整數(shù)。

首先計(jì)算兩點(diǎn)經(jīng)過哈希之后的沖突概率。使用fp(t)表示正態(tài)分布的絕對值的概率密度函數(shù)，對于兩點(diǎn)v1和v2，r=|v1-v2|為兩點(diǎn)的歐氏距離。當(dāng)w=w0時(shí)，經(jīng)過哈希函數(shù)映射之后兩點(diǎn)的沖突概率為[11]：

(2)

從H中取k個(gè)函數(shù)，定義k維局部敏感哈希函數(shù)族G={g|DUk}為從數(shù)據(jù)集D到k維整數(shù)域U的映射：

g(v)=(h1(v),…,hk(v))

(3)

其中，hi(v)∈H,i∈[1,k]。

從G中取L個(gè)哈希函數(shù)：gi(v)G，l[1,L]。對于所有vD，利用gi(v)建立L張哈希索引表。經(jīng)過哈希函數(shù)映射之后得到的沖突概率為：

q(r,k,L)=1-[1-p(r)k]L

(4)

圖像檢索的目標(biāo)是從圖像數(shù)據(jù)集中找出所有與查詢點(diǎn)的歐氏距離不大于查詢范圍r0的所有圖像，在求得沖突概率q(r,k,L)和圖像數(shù)據(jù)的距離分布概率密度函數(shù)f(r)之后，精確率和召回率分別為：

(5)

(6)

F1為精確率和召回率的調(diào)和平均，即：

(7)

定義參數(shù)最優(yōu)化問題如下：

(8)

L≤L0

其中，L0為哈希表數(shù)的上限。

2.2 兩點(diǎn)間的距離分布

下面分析圖像特征數(shù)據(jù)兩點(diǎn)間距離分布的概率密度f(r)。兩點(diǎn)的歐氏距離的平方曲線可以用伽馬分布進(jìn)行擬合[17]，伽馬分布的概率密度函數(shù)為：

(9)

其中，β是形狀參數(shù)；θ是尺度參數(shù)；α是使函數(shù)積分為1的歸一化系數(shù)。

伽馬分布的參數(shù)可以用最大似然估計(jì)進(jìn)行計(jì)算，僅僅和樣本的算術(shù)平均E和幾何平均G相關(guān)，而E和G可以通過采樣獲得。給出E和G，則β和θ可由以下方程組求得：

(10)

其中，ω(β)=Γ(β)Γ(β)為雙伽馬函數(shù)。

圖1顯示的是典型的圖像數(shù)據(jù)集任意兩點(diǎn)的距離平方的概率密度曲線，可以從圖中看出距離平方分布基本符合伽馬分布。

圖1 距離平方的概率密度直方圖

2.3 局部敏感哈希參數(shù)優(yōu)化算法

當(dāng)r0=4,w0=10,L0=100且兩點(diǎn)距離平方的概率密度分布為伽馬分布時(shí)，采用枚舉算法得到F1和k、L的關(guān)系如圖2所示。從圖中可知，F(xiàn)1隨著L的增加單調(diào)增加，因此，最優(yōu)的L應(yīng)取其約束上限L0，即Lopt=L0。又因?yàn)?，對于給定的L，F(xiàn)1為k單峰函數(shù)，所以可采用二分查找算法快速確定最優(yōu)的k值。

圖2 F1和k、L的關(guān)系示意

采用數(shù)值微分的方法求F1對k的偏導(dǎo)數(shù)，即求：

(11)

其中h為一個(gè)微小的數(shù)值。因?yàn)镕1為單峰函數(shù)，所以偏導(dǎo)數(shù)為零的點(diǎn)兩邊異號(hào)，可以對數(shù)值微分計(jì)算得到的數(shù)組采用二分查找算法，從而求得k的最優(yōu)值。設(shè)置k取值范圍為1≤k≤kmax，其中kmax為設(shè)置的一個(gè)越過峰值的較大的整數(shù)。由于采用了二分查找算法，所以參數(shù)優(yōu)化算法時(shí)間復(fù)雜度為O(logkmax)。

求解最優(yōu)參數(shù)k的算法如下：

算法：局部敏感哈希參數(shù)優(yōu)化算法

輸入：kmax，r0，w0，L0

輸出：最優(yōu)參數(shù)kopt

1.low=1

2.high=kmax

3.whilelow≤high do

4.mid=?(low+high)/2」

5.if dF1(mid)=0 then

6.break

7.else if dF1(mid)<0 then

8.high=mid-1

9.else

10.low=mid+1

11.end if

12.end while

13.kopt=mid

3 測試與性能分析

文中采用GitHub開源項(xiàng)目JorenSix/TarsosLSH自帶的數(shù)據(jù)集，一共有4 764條圖像特征數(shù)據(jù)，提取到的圖像特征的維度為256維，因此實(shí)驗(yàn)的數(shù)據(jù)集是基于真實(shí)的特征數(shù)據(jù)，實(shí)驗(yàn)用到的數(shù)據(jù)集大小為3.96 M。

當(dāng)r0=4,w0=10,L0=100且兩點(diǎn)距離平方的概率密度分布為伽馬分布時(shí)，若使用枚舉法求F1最大值對應(yīng)的k，得到kopt=16。若采用數(shù)值微分計(jì)算偏導(dǎo)數(shù)，然后再對偏導(dǎo)數(shù)計(jì)算結(jié)果采用二分查找，則能夠和枚舉法得到相同的最優(yōu)結(jié)果，從而驗(yàn)證了上述算法的有效性。

為了討論不同的數(shù)據(jù)分布對算法結(jié)果的影響，令r0=4,w0=10，設(shè)兩點(diǎn)距離分布為均勻分布和伽馬分布，取不同的L0，最優(yōu)的k所對應(yīng)的曲線如圖3所示?？梢钥闯?，kopt隨著L0的增加而增加。當(dāng)L0確定時(shí)，伽馬分布取的kopt比均勻分布的大。

圖3 不同分布時(shí)最優(yōu)的k和L0的關(guān)系示意

下面針對伽馬分布和均勻分布分別討論不同的參數(shù)對算法的影響。

(1)當(dāng)r0=4，取不同的w0，分別針對伽馬分布和均勻分布，得到L0與最優(yōu)的k所對應(yīng)的曲線，如圖4(a)和(b)所示?？梢钥闯觯顑?yōu)的k隨著w0的增加而增加。這是因?yàn)閣0越大哈希桶的粒度就越粗，要達(dá)到同等的檢索精準(zhǔn)度，k值也要增加。在當(dāng)w0和L0相同時(shí)，伽馬分布kopt取值比均勻分布的要大。

(a)伽馬分布

(b)均勻分布

(2)當(dāng)w0=10，取不同的r0，分別針對伽馬分布和均勻分布，得到L0與最優(yōu)的k所對應(yīng)的曲線，如圖5(a)和(b)所示?？梢钥闯觯顑?yōu)的k隨著r0增加而減小。因?yàn)檩^大的r0對應(yīng)檢索條件也較寬，需要的k值也較小。同樣，當(dāng)r0和L0相同時(shí)，伽馬分布kopt取值比均勻分布的要大。

(a)伽馬分布

(b)均勻分布

(3)當(dāng)r0=4，L0[1,100]，取不同的w0，分別針對伽馬分布和均勻分布，得到最優(yōu)的k與最優(yōu)F1所對應(yīng)的曲線，如圖6(a)和(b)所示?？梢钥闯?，F(xiàn)1opt隨kopt的增加而增加，同時(shí)，隨著w0增大，最優(yōu)的k和F1也在增大。另外，在相同參數(shù)條件下，均勻分布的最優(yōu)F1明顯高于伽馬分布的F1，說明不同分布對檢索性能的影響是比較明顯的。

(a)伽馬分布

(b)均勻分布

(4)當(dāng)w0=10，L0[1,100]，取不同的r0，分別針對伽馬分布和均勻分布，得到最優(yōu)的k與最優(yōu)F1所對應(yīng)的曲線，如圖7(a)和(b)所示。同樣可以看出，F(xiàn)1opt隨kopt的增加而增加，同時(shí)隨著r0增大，最優(yōu)的k在減小，F(xiàn)1則增大。而均勻分布的F1opt仍明顯比伽馬分布的高。

(a)伽馬分布

最后，將提出的二分查找算法和枚舉法進(jìn)行比較，以驗(yàn)證局部敏感哈希參數(shù)優(yōu)化算法求解參數(shù)最優(yōu)化問題的高效性。當(dāng)r0=4,w0=10,L0[1,100]，kmax設(shè)置為固定的較大的整數(shù)r0，針對伽馬分布，得到不同算法的運(yùn)行時(shí)間T與L0所對應(yīng)的曲線，如圖8所示?？梢钥闯觯杜e法的運(yùn)行時(shí)間隨著L0的增大顯著增加，而提出的二分查找算法的運(yùn)行時(shí)間比較穩(wěn)定，隨著L0的增大變化不大，且明顯小于枚舉法。這是因?yàn)榫植棵舾泄?shù)優(yōu)化算法直接取最優(yōu)的L=L0，同時(shí)采用二分法搜索最優(yōu)參數(shù)kopt，從而使其運(yùn)行時(shí)間與枚舉法相比有顯著優(yōu)勢。

圖8 算法運(yùn)行時(shí)間T和L0的關(guān)系曲線

4 結(jié)束語

提出了一種基于局部敏感哈希的參數(shù)優(yōu)化方法，提高了圖像檢索的計(jì)算效率。實(shí)驗(yàn)結(jié)果表明，局部敏感哈希算法在參數(shù)優(yōu)化后運(yùn)行，能夠加快圖像檢索的運(yùn)行效率。在當(dāng)今圖像數(shù)據(jù)爆炸性增長的背景下，在圖像檢索上采用高效的參數(shù)計(jì)算方法實(shí)現(xiàn)局部敏感哈希算法具有深遠(yuǎn)的意義。后期將對局部敏感哈希采用分布式方式加快圖像檢索，并在此基礎(chǔ)上進(jìn)行基于分布式的參數(shù)選擇模型相關(guān)的分析。