張 亮,謝曉堯

(1.貴州大學(xué) 計算機科學(xué)與信息學(xué)院,貴州 貴陽 550001;2.貴州省信息與計算科學(xué)重點實驗室,貴州 貴陽 550001)

前言

局部敏感哈希是一種對高維度數(shù)據(jù)通過概率方法降維的一種方法,基本的想法是將輸入的數(shù)據(jù)進行哈希,使得相似的數(shù)據(jù)的哈希值映射到同一個哈希桶的概率非常高。由于在局部敏感哈希中,哈希桶的數(shù)量遠遠小于輸入數(shù)據(jù)的窮舉數(shù)量,它的實現(xiàn)方法和傳統(tǒng)的哈希函數(shù)較不一樣,通常用于數(shù)據(jù)的聚簇和最近鄰搜索[1-3]。

在圖片的相似性搜索的應(yīng)用中[4],給定一張參考圖片,來從圖片數(shù)據(jù)庫中進行搜索,以得到和參考圖片最相似的若干圖片。搜索的過程通常經(jīng)過2個步驟,首先通過特征點提取算法將圖片中的特征點和特征向量提取出來,然后將提取特征點的特征向量在數(shù)據(jù)庫中進行搜索,取得最相似的向量,再進行匹配。而特征向量在數(shù)據(jù)庫中的相似性搜索實際上是一個K近鄰的問題,這就是本論文所研究的問題。在K近鄰的搜索方面,傳統(tǒng)的做法有線性搜索和空間分割,空間分割通常用的是KD-Tree和R-Tree的方法。線性搜索的時間復(fù)雜度為O(Nd),N為樣本空間大小,d為維度。在低維度情況下,KD-Tree和R-Tree的平均時間復(fù)雜度為O(logN?d),最壞時間復(fù)雜度為O(Nd)。而在高維度的情況下,KD-Tree和R-Tree的平均時間復(fù)雜度為O(Nd)。局部敏感哈希方法通過降低結(jié)果的精度,將K近鄰問題轉(zhuǎn)化為近似K近鄰問題,通過常數(shù)的時間復(fù)雜度就可以得到一個粗糙的樣本集合,再從這個樣本集合中去糙取得更為精確的結(jié)果。

1 基本概念和理論基礎(chǔ)介紹

定義1:哈希函數(shù)

把任意長度的輸入,變成固定長度的輸出的一種映射稱為哈希,這個映射關(guān)系稱為哈希函數(shù)。

哈希函數(shù)通常用來做文件校驗,數(shù)字簽名,搜索。在搜索中,通過哈希函數(shù)可以用常數(shù)的時間從原來的搜索集中取得一個集合,再從這個集合中進行搜索。取得的這個集合的大小如果比原來的搜索集小的多,便可以大大降低算法復(fù)雜度。使用哈希方法來搜索關(guān)鍵在于哈希函數(shù)的質(zhì)量。

定義2:1近鄰問題[5]

在一個n個點(向量)的集合P中,用d(p,q)表示點p到q之間的距離函數(shù)(計算距離的方法按照實際應(yīng)用而定)。給一個點p,返回一個不同于p的點 q,對任意r∈P且r≠p,使得 d(p,q)≤d(p,r)。

定義3:K近鄰問題

在n個點(向量)的集合P中,給一個點p,返回K個離p最近的點集。

定義4:近似K近鄰

在很多搜索的應(yīng)用中,所求的解并不要求是絕對的K近鄰的解,可以是K個近似于K近鄰的解,這樣的話,我們找到了可以用于求近似解的哈希方法:局部敏感哈希(Locality-sensitive hashing)。

2 局部敏感哈希算法的介紹

局部敏感哈希是對高維數(shù)據(jù)的一種概率降維的方法?；镜乃枷胧菍?shù)據(jù)hash,使得相似的數(shù)據(jù)將高概率的映射到同一個hash桶中。

在一個度量空間(M,d)中,給定一個閾值R＞0,和一個大約因子c＞1。

F為一個函數(shù)集合h:M-＞S.對任意點p,q∈M,從這個函數(shù)集合中任意選擇一個函數(shù)h,使得

如果d(p,q)≤R,那么h(p)=h(q)的概率至少為P1。

如果d(p,q)≥cR,那么h(p)=h(q)的概率最多為P2。

當(dāng)P1＞P2時,函數(shù)集合F稱之為(R,cR,P1,P2)敏感。

實現(xiàn):[6]

假設(shè)有n個維度為d的向量需要通過局部敏感哈希的方法哈希。

a)將n個維度為d的向量,轉(zhuǎn)換為每個向量的坐標(biāo)都為正整數(shù)的向量。

只要選好一定的A和w,即可將所有的向量按照同一個公式轉(zhuǎn)化為坐標(biāo)都為正整數(shù)的向量。

b)假設(shè)所有向量中最大的坐標(biāo)值為C。將每一個向量做如下的變換。假設(shè)r為向量v的一個坐標(biāo),u(r)=000…0111…1(其中左端全為0,右端全為1,除中間位置并無01交錯的情況)。其中1的個數(shù)為r的值的大小。如最大值C為10,r=4,那么u(r)=0000001111。再假設(shè)運算符|連接2個數(shù),如0011|0001=00110001。每個向量v通過f(v)做轉(zhuǎn)換:f(v)=u(v1)|u(v2)|u(v3)|…|u(vd);v1,v2,…vd為向量的坐標(biāo)。那么每一個向量v都會轉(zhuǎn)化為一個Cd長度的01串。

c)從0到Cd-1的整數(shù)中隨機選取k個數(shù)為:n1,n2,n3,…,nk(一次性預(yù)處理選定常數(shù)),設(shè)h(v,n)為v中第n個坐標(biāo),g(v)=h(v,n1)|h(v,n2)|…|h(v,nk)。

d)g(v)便為向量v的一個hash值。

e)為了提高相似碰撞率,采取多張hash表的方式,每張hash表的處理方法一樣,只是每張hash表中選取的k個數(shù)不一樣。

f)由于g(v)是一個長度為k的2進制數(shù),即hash表的值有2k可能性。當(dāng)k的值很大時,可采用二次hash的方法。設(shè)(v1v2v3…vk)為g(v)的值,每一個vi為一個二進制位,h(v1,v2,v3,…vk)=a1v1+a2v2+…+akvkmod M,M為hash表的大小,ai為[0…M-1]中的隨機正整數(shù)。

3 通過局部敏感哈希在高維向量K近鄰搜索

在圖片的相似性搜索的應(yīng)用中,特征向量的搜索部分可以這樣來處理。

總步驟:

(1)樣本庫的預(yù)處理:將n個d維的向量的樣本庫存放在L個哈希表中,對于每一個向量,通過上述的方法,分別放入L個哈希表中對應(yīng)的鍵值的桶中。

(2)對于某個向量p在樣本庫中的搜索。通過上述的方法計算出向量p在每一個哈希表中對應(yīng)的哈希值:h1,h2,…,hL。再從L個哈希表中取出L個向量的集合取并集。再從得到的并集中,選取離向量p最近的K個點。

通過局部敏感哈希搜索的正確率的分析[7]:

由于漢明距離實際上就是轉(zhuǎn)換成正整數(shù)坐標(biāo)的L1范數(shù)距離。下面的分析忽略2次哈希的效果,實際上2次哈希只會增加正確率,因為在1次哈希中碰撞的向量在第2次哈希中必然碰撞,當(dāng)然2次哈希增加了搜索時候的時間復(fù)雜度。

(1)1張哈希表中的碰撞概率的分析。

假設(shè)兩向量p,q的L1距離為x,d'=Cd,那么兩向量碰撞的概率為:

那么距離在a以內(nèi)的兩向量p,q的碰撞概率為:

這表明兩向量p,q的碰撞概率除了和p,q之間的距離有關(guān),而且和向量的分布情況有關(guān)。

(2)L張哈希表中碰撞概率的分析。

很明顯,哈希表越多,碰撞的概率越大,但同時也增加了時間復(fù)雜度。

時間復(fù)雜度的分析:

(1)樣本庫預(yù)處理的時間復(fù)雜度分析。

樣本庫的插入的時間主要在哈希函數(shù)的計算上,哈希函數(shù)計算的時間復(fù)雜度為O(k),由于原向量轉(zhuǎn)換成的2進制表示方式有著特殊的形式:都是由一段一段的111…00構(gòu)成的?？梢詫⒚恳欢问褂貌楸淼姆绞竭M行哈希計算,這樣哈希函數(shù)的計算將會縮短成為O(d)。

總的時間復(fù)雜度為O(ndL)。哈希表的存儲方式也將是決定最后的時間消耗的重要因素。

(2)單個向量搜索的時間復(fù)雜度分析。

由于向量搜索分為兩個步驟,首先提取出每個哈希表中對應(yīng)鍵值的向量集取并集,然后對取得的向量集做距離的篩選。

總的時間復(fù)雜度為O(dL)+O(Lmd),m為哈希表中平均每個桶中的向量個數(shù)。

4 結(jié)語

在高維度的搜索中,用到的常見方法有KD-Tree,R-Tree等,這些方法能對K-NN(k近鄰)問題搜索到精確解,但是當(dāng)維度到達一定大小后,耗時使得算法不能用于實際應(yīng)用。當(dāng)要求的K-NN問題為近似解的時候,我們可以引入局部敏感哈希的方法來進行索引和搜索,算法的難點在于調(diào)節(jié)哈希表的參數(shù)(包括哈希表的大小和哈希表的數(shù)目,漢明空間中k的選取等)和用于實現(xiàn)哈希表的軟件方法。

[1]P.Indyk and R.Motwani.Approximate nearest neighbors:towards removing the curse of dimensionality[A].InSTOC'98:Proceedings of the thirtieth annual ACM symposium on Theory of computing,New York,USA:ACM Press,1998:604～613.

[2]Aristides Gionis,Piotr Indyk,and Rajeev Motwani.Similarity search in high dimensions via hashing[A].InVLDB'99:Proceedings of the 25th International Conference on Very Large Data Bases[C],San Francisco,CA,USA:Morgan KaufmannPublishers Inc.1999:518～529.

[3]曹玉東,劉福英,蔡希彪.基于局部敏感哈希算法的圖像高維數(shù)據(jù)索引技術(shù)的研究[J].遼寧工業(yè)大學(xué)學(xué)報(自然科學(xué)版),2013,(1):1～4.

[4]夏宇,朱欣焰.高維空間數(shù)據(jù)索引技術(shù)研究[J].測繪科學(xué),2009,(1):60～62.

[5]Alexandr Andoni.Nearest Neighbor Search:the Old,the New,and the Impossible[D].Massachusetts Institute of Technology,2009.

[6]M.Datar,N.Immorlica,P.Indyk,and V.S.Mirrokni.Locality-sensitive hashing scheme based on p-stable distributions[A].In SCG'04:Proceedings of the twentieth annual symposium on Computational geometry[C],New York,USA:ACM Press,2004:253～262.

[7]Wei Dong,Zhe Wang,William Josephson,Moses Charikar,Kai Li.Modeling LSH for Performance Tuning[A].Proceedings of the 17th Conference on Information and Knowledge Management[C].Napa Valley,CA,USA:Information Retrieval Facility,2008:669～678.