局部敏感哈希在高維向量K近鄰搜索中的應(yīng)用

張 亮,謝曉堯

(1.貴州大學(xué) 計(jì)算機(jī)科學(xué)與信息學(xué)院,貴州 貴陽 550001;2.貴州省信息與計(jì)算科學(xué)重點(diǎn)實(shí)驗(yàn)室,貴州 貴陽 550001)

前言

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

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

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

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

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

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

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

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

定義3:K近鄰問題

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

定義4:近似K近鄰

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

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

局部敏感哈希是對(duì)高維數(shù)據(jù)的一種概率降維的方法。基本的思想是將數(shù)據(jù)hash,使得相似的數(shù)據(jù)將高概率的映射到同一個(gè)hash桶中。

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

F為一個(gè)函數(shù)集合h:M-＞S.對(duì)任意點(diǎn)p,q∈M,從這個(gè)函數(shù)集合中任意選擇一個(gè)函數(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í),函數(shù)集合F稱之為(R,cR,P1,P2)敏感。

實(shí)現(xiàn):[6]

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

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

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

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

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

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

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

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

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

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

總步驟:

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

(2)對(duì)于某個(gè)向量p在樣本庫(kù)中的搜索。通過上述的方法計(jì)算出向量p在每一個(gè)哈希表中對(duì)應(yīng)的哈希值:h1,h2,…,hL。再?gòu)腖個(gè)哈希表中取出L個(gè)向量的集合取并集。再?gòu)牡玫降牟⒓?選取離向量p最近的K個(gè)點(diǎn)。

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

由于漢明距離實(shí)際上就是轉(zhuǎn)換成正整數(shù)坐標(biāo)的L1范數(shù)距離。下面的分析忽略2次哈希的效果,實(shí)際上2次哈希只會(huì)增加正確率,因?yàn)樵?次哈希中碰撞的向量在第2次哈希中必然碰撞,當(dāng)然2次哈希增加了搜索時(shí)候的時(shí)間復(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張哈希表中碰撞概率的分析。

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

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

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

樣本庫(kù)的插入的時(shí)間主要在哈希函數(shù)的計(jì)算上,哈希函數(shù)計(jì)算的時(shí)間復(fù)雜度為O(k),由于原向量轉(zhuǎn)換成的2進(jìn)制表示方式有著特殊的形式:都是由一段一段的111…00構(gòu)成的。可以將每一段使用查表的方式進(jìn)行哈希計(jì)算,這樣哈希函數(shù)的計(jì)算將會(huì)縮短成為O(d)。

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

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

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

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

4 結(jié)語

在高維度的搜索中,用到的常見方法有KD-Tree,R-Tree等,這些方法能對(duì)K-NN(k近鄰)問題搜索到精確解,但是當(dāng)維度到達(dá)一定大小后,耗時(shí)使得算法不能用于實(shí)際應(yīng)用。當(dāng)要求的K-NN問題為近似解的時(shí)候,我們可以引入局部敏感哈希的方法來進(jìn)行索引和搜索,算法的難點(diǎn)在于調(diào)節(jié)哈希表的參數(shù)(包括哈希表的大小和哈希表的數(shù)目,漢明空間中k的選取等)和用于實(shí)現(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é)報(bào)(自然科學(xué)版),2013,(1):1～4.

[4]夏宇,朱欣焰.高維空間數(shù)據(jù)索引技術(shù)研究[J].測(cè)繪科學(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.