原始LSH算法詳解

SimilaritySearchinHighDimensionviaHashingLSH算法：1、 算法思想：將高維空間中的元素視為點并賦以坐標值，坐標值為正整數(shù)。通過一族哈希函數(shù)J?將空間所有點映射到n個哈希表二中，n=|、「|，即每個哈希函數(shù)於卜對應一個哈希表，每個哈希表都存放著空間所有的點。對于給定的查詢子q，分別計算f1(q)、f2(q)、…、f(q)，fJF，i=1,2,…,n。以所有f(q)落入的哈希表7中n i i i的桶中所有點作為候選集，比較其與q之間的距離，選出距離最近的K個點(K-NNS)。2、 算法步驟預處理：對于任意一點P6P，P為d維空間。設p=｛氣，％，…，七｝,將空間P映射到d'維Hamming空間"d，，映射方法如下：PTP6P，p=Unary(x)Unary(x)?.?Unary(x)c1 c2 cd其中Unary(x)表示x個1緊跟C-x個0,C表示空間P中任意ci i i點P坐標的最大值。這種映射是保距的，即Vp,q6P，d[(p,q)=dH(p,q)。其中《表示定義在空間P上I】準則下的歐幾里得距離，dH表示定義在兀dd空間下的Hamming距離。因此原問題一一找出空間P中與查詢子q距離最近的K個點——轉(zhuǎn)化為在”d'空間中的f-NNS問題。在算法實現(xiàn)中，并沒有顯式將p轉(zhuǎn)化為P'，而是用別的計算方法利用了這種轉(zhuǎn)化，使算法易于描述并且實現(xiàn)的時空效率高。下面定義哈希函數(shù)的過程中，p代表了原始點的向量形式(即P')，即不會區(qū)分p與P'。定義哈希函數(shù)族：定義I=｛1,2，…，d'｝，定義正整數(shù)l，取l個I的子集，分別記為I1,12，…，【I。定義p|I為向量p在坐標集I上的投影，即以坐標集I中每個坐標為位置索引，取向量p對應位置的比特值并將結(jié)果串聯(lián)起來。比如I={1,5,7,8}，p=110010001110(對應原始點p={2,1,3}，d=3,C=4)，則p|I=1100。記g.(p)=p|I，我們將空間P中的所有點利用哈希函數(shù)族gj(P)都存入哈希表的哈希桶中。哈希族的形式如下圖所示：T1g](D=?I'gi(Pii)g](p2i) ?…??g(p )1 kJT2g2(D=?112g2(P1「g2(P2「??…-g(P)2 k2iT3g3(D=?113g3(P1i)g3(p2i)??…-g(P)3k*******,Tig(D=11i igl(p1i?)gl(P2i)?…??g(p)i kj表1表中有/個哈希表，第i個哈希表有k個哈希桶，即第i個哈希表i將空間？中的點映射到了k個不同位置。因此表中共有寸k個哈i ii=1希桶。因為哈希桶的數(shù)量可能會很大，因此采用第二層哈希，利用標準哈希函數(shù)將所有的哈希桶映射到一個大小為M的哈希表中。記該哈希表中的哈希桶最大容量為B，在算法中采取的沖突解決方法是：當一個哈希桶內(nèi)點的個數(shù)超過B時，則新分配一個大小為B的桶并將該新桶連接到原來的桶中，而在實現(xiàn)的過程中，采取了更簡單的方法：當一個哈希桶中點的個數(shù)超過B時，則不能再有點插入，當有新點分配到該桶中時，該點會被分配到其他未滿的哈希桶中。新的哈希表如下表所示：BBB■,?B123MB中邏輯上存儲的是表1中的哈希桶，物理上存儲的是表1的哈希桶中存儲的空間p中的點。查詢操作：對于給定的查詢子q，計算g(q)，g(q)，…，g(q)，取1 2 l出g(q)對應哈希桶中所有的點(即滿足g(q)=g(p)的點p的集i i i合)作為候選集。最后在候選集中選出K個距離查詢子q最近的K個點。小問題集合I的子集/，/，…，/，對于j=1,2,…，1，I由從集合｛1,2,…,1 2 l jd'｝隨機的均勻的可放回的選取k個元素組成。最好的k要使距離近的元素映射到同一個桶中，距離遠的元素映射到不同的桶中。前面提到，實際實現(xiàn)中不必顯式的將d維空間P中的點p映射到d'維Hamming空間的向量礦，而是使用其他的方法隱式的進行。方法是這樣的：記d維空間P中的點p映射到d'維Hamming空間的向量為p'，坐標集I。｛1,2，…，d'｝，p'|I的含義如前所述。定義I|i，其中ie｛1,2,…,d｝，I|i的含義為對應到p的第i個坐標的排好序的I中的坐標。舉例說明，I=｛1,2,5,8,13｝，p=｛2,3,1,4｝，d=4,C=5，p'=11000111001000011110,I|1=｛1,2,5｝，I|2=｛8｝，I|3=｛13｝，I|4=0，因為d=4,所以I有四個映射：I|1，I|2,I|3,I|4。因為C=5,所以I|1表示I中范圍在1-5中的坐標，I|2表示I中范圍在6-10中的坐標，以此類推。顯然，P'在I|i上的投影是一串1緊跟一串0的形式，比如上面討論中p'在111上的投影是110,在112上的投影是1,這是顯然的。因為I中坐標是排好序的，而如果將p'中每C個比特為一組劃分的話，每一組是一串1加一串0組成的串，I|i是I中坐標與p'第i組中索引的交集，p'在I|i上的投影是從p'的第i組中從左至右的選擇索引為交集中元素的比特值，所得投影必定是一串1緊跟一串0組成的串。而礦在I上的投影即為將p在I|i(i=1,2,…,d)上投影的串聯(lián)起來得到的串。因此，要得到p'在I上的投影，只需得到P在I|i上的投影;要得到P'在I|i上的投影，只需得知P'在I|i上的投影中1的個數(shù)匕；要想得到1的個數(shù)，只需比較I|i和點p的第i個坐標值x,o=|{I|i}-C*(i-1)<x|，ii i|，|表示集合,的元素個數(shù)。即比較I|i中小于等于七的元素個數(shù)，因為I，{1,2,…,d}，d=Cd，因此對于i>1的情況，要減去c的i-1倍，才能與x的值在同一度量上。舉例說明：d=4,C=5,d'=20，ip={2,4,3,5}，p'=11000111101110011111,I={1,2,3,5,7,8}，因此I|1={1,2,3,5}，I|2={7,8}，I|3=I|4=0，p'在I|1，I|2上的投影分別為1100,11。觀察I|1與x，I|2與x，I|1中小于等于x=21 2 1的個數(shù)為2,因此P'在111上的投影有兩個1，I|2元素減去C=5后小于等于x2=4的個數(shù)為2，因此P'在112上的投影有兩個1。0的個數(shù)為I|i的元素個數(shù)減去1的個數(shù)。最后得到的結(jié)果是，P'在I上的投影p'|I=110011。整個過程中，用到的變量有d，C，I，這里的I對應算法步驟中的I.。然后就可以計算I|i，通過比較I|i中元素與p的坐標就可以得到P'在I|i上的投影，最后串聯(lián)得到P'在I上的投影。因此沒有顯式的用到P'。主要運算在比較p的坐標與I|i中的元素，即找到I|i中小于等于p的第i個坐標的所有元素，因為I|i是排好序的，找到I|i中小于等于p的第i個坐標的臨界元素即可，使用二分法查找，每次查找的時間復雜度為O(log2C)，因為i=1,2,…,d，共需查找d次，故計算每個哈希函數(shù)g(p)所用i

的時間復雜度為(dlog2C)。LSH算法分析一、符號定義：1、集合S2、 S中元素p,q距離記為D(p,q)3、 VpeS，p的r鄰域記為0(p,r)。二、局部敏感的一般化定義:從S映射到U的函數(shù)族"稱為對距離。是(r,r,p,p)-敏感的，如果12 12滿足以下兩個條件:⑴ifpeO(q⑴ifpeO(q,r「,thenP加(h(q)=h(p))>p1②ifPW°(q，r2),thenP加(h(q)=h(p))<p2三、d'維Hamming空間中的點p,q，對于任意的r,e,選取的函數(shù)族為氣,={h「h((b,b,…，b))=b,fori=1,2,…，d'｝，則其在Hamming距離下是i1 2 d'r r(1+e)(r,r(1+Q,1-歹,1- 了)-敏感的。四、將前面算法的應用推廣到一般的函數(shù)族五，即將函數(shù)gj(p)定義為如下形式:g(p)=(h(p),h(p)，…，h(p))j" ‘2 i即從函數(shù)族7/中可重復的選取k個函數(shù)組成一個g函數(shù)，并按這種方法生成1個g函數(shù)。當函數(shù)族h為函數(shù)族氣，時，即得到上面算法中用到的g函數(shù)：gj(P)=PII。O五、將LSH算法用來解決(r,：)-Neighbor問題：問題描述：給定一個點q，確定在q的r鄰域內(nèi)是否存在一點p，若存在，返回q的r(1+)鄰域內(nèi)一點P';若不存在，判斷是否在q的r(1+i)鄰域內(nèi)不存在其它點。記,二r,七二r(1+i)。記P'為P中與q的距離大于二的點的集合。LSH算法能解決(r,：)-Neighbor問題，當其能滿足一下兩個條件：P1：如果在q的尸］鄰域內(nèi)有點P*存在，則對某些j=1,2,…I，使得gj(P*)=gj(q)(把q與距q較近的點映射到同一塊中，是應該追求的，這種情況越多越好。)P2：q經(jīng)過g函數(shù)映射落入的塊中僅包含P中點的塊數(shù)小于cI。(把q與距q較遠的點映射到同一個塊中，是應該避免的，這種情況越少越好。)P1和P2中的塊對應二級哈希表中的每個哈希桶。每個點經(jīng)過g函數(shù)映射得到一個k維的哈希值，因為有/個g函數(shù)，因此每個點會有1個不同的k維哈希值分別存放在每個g函數(shù)中。在二層哈希的時候，利用下面哈希函數(shù)將每個點的每個k維向量(即所有g(shù)函數(shù)所有哈希桶的所有內(nèi)容)映射到大小為M的二級哈希表中：h(v,v….,v)=av+av+..?+avmodM1 2k11 22 kk(匕,叩…，匕)為點的k維向量值，a，i=1,2,…，k為［0,M-1］中隨機k1 2k i個數(shù)。一級哈希表中同一個哈希桶中的點一定在二級哈希表中的同一個哈希桶中一級哈希表不同哈希桶中但相近的點可能會在二級哈希表的同一個哈希桶中l(wèi)n1/p假設.打為(r,r,p,p)-敏感的，定義p= 1，則有如下定理：12 12 ln1/p2n、定理：設定k=log (n/B)，l=(節(jié))p，可以保證條件P1和P2同時滿足的1/p2 B概率至少為1—->0.132。2e備注：對于任意的5>0,重復將LSH算法進行°(1/5)次，則至少會有一次將成功的概率提高到1-5。證明：設條件P1發(fā)生的概率為P，條件P2發(fā)生的概率為P，以下將證明P和1 2 1P2都比較大。不妨設查詢子q的二鄰域內(nèi)存在一點p*，反之證明類似。設k=log"n/B)，則對于P中的任一點p'，由局部敏感的定義，式子Bg(p)=g(q)成立的概率最大是p「n。對于每個g函數(shù)gj，將二級哈希中分配給g的只包含pf中點的塊(每個塊對應一個哈希桶)的數(shù)量的期望值設為j2,則分配給所有g(shù)/的符合條件的塊的數(shù)量不超過21，因此，由馬爾可夫不等式：Pr(X>a)<竺2得知，符合條件的塊數(shù)超過 41的概率小于1/2aTOC\o"1-5"\h\zE(X) 21 1 「1(Pr(X>41)<—^-< =-)，若選擇c=4,則條件2滿足的概率P>萬。41 41 2 22由于事先假設的條件是查詢子q的二鄰域內(nèi)存在一點P*，所以下面討論式子g(p*)=g(q)成立的概率P。P是以下面式子為下限的：j j 1 1_log1Spk=砰饑n/B=(n/B)log1/p2=(n/B)_p11，頊、 z ，、前面已設I=(*)p，故式子gj(p*)豐gj(q)的概率小于等于1-p,故對于所有j=1,2,…，I，都有式子gj(p*)豐gj(q)成立的概率為(1—pk)1=(1—(n/B)_p)(n/B