1. 概述

LSH是由文獻[1]提出的一種用于高效求解最近鄰搜索問題的Hash算法。LSH算法的基本思想是利用一個hash函數把集合中的元素映射成hash值，使得相似度越高的元素hash值相等的概率也越高。LSH算法使用的關鍵是針對某一種相似度計算方法，找到一個具有以上描述特性的hash函數。LSH所要求的hash函數的準確數學定義比較復雜，以下給出一種通俗的定義方式：

對于集合S，集合內元素間相似度的計算公式為sim(*,*)。如果存在一個hash函數h(*)滿足以下條件：存在一個相似度s到概率p的單調遞增映射關系，使得S中的任意兩個滿足sim(a,b)>=s的元素a和b，h(a)=h(b)的概率大于等于p。那么h(*)就是該集合的一個LSH算法hash函數。

一般來說在最近鄰搜索中，元素間的關系可以用相似度或者距離來衡量。如果用距離來衡量，那么距離一般與相似度之間存在單調遞減的關系。以上描述如果使用距離來替代相似度需要在單調關系上做適當修改。

根據元素相似度計算方式的不同，LSH有許多不同的hash算法。兩種比較常見的hash算法是隨機投影法和min-hash算法。本文即將介紹的隨機投影法適用于集合元素可以表示成向量的形式，并且相似度計算是基于向量之間夾角的應用場景，如余弦相似度。min-hash法在參考文獻[2]中有相關介紹。

2 隨機投影法(Random projection)

假設集合S中的每個元素都是一個n維的向量：

，集合中兩個元素和之間的相似度定義為

。

對于以上元素集合S的隨機投影法hash函數h(*)可以定義為如下：

在n維空間中隨機選取一個非零向量。考慮以該向量為法向量且經過坐標系原點的超平面，該超平面把整個n維空間分成了兩部分，將法向量所在的空間稱為正空間，另一空間為負空間。那么集合S中位于正空間的向量元素hash值為1，位于負空間的向量元素hash值為0。判斷向量屬于哪部分空間的一種簡單辦法是判斷向量與法向量之間的夾角為銳角還是鈍角，因此具體的定義公式可以寫為

。

根據以上定義，假設向量和之間的夾角為，由于法向量是隨機選取的，那么這兩個向量未被該超平面分割到兩側（即hash值相等）的概率應該為：。假設兩個向量的相似度值為s，那么根據,有

。因此，存在相似度s到概率p的單調遞增映射關系，使得對于任意相似度大于等于s的兩個元素，它們hash值相等的概率大于等于。所以，以上定義的hash值計算方法符合LSH算法的要求。

以上所描述的h(*)函數雖然符合LSH算法的要求，但是實用性不高。因為該hash函數只產生了兩個hash值，沒有達到hash函數將元素分散到多個分組的目的。為了增加不同hash值的個數，可以多次生成獨立的函數h(*)，只有當兩個元素的多個h(*)值都相等時才算擁有相同的hash值。根據該思路可以定義如下的hash函數H(*)：

。其中每個表示一個獨立的h(*)函數，H(*)函數值的二進制表現形式中每一位都是一個h(*)函數的結果。

以H(*)為hash函數的話，兩個相似度為s的元素具有相同hash值的概率公式為

。hash值的個數為。很容易看出H(*)函數同樣也是符合LSH算法要求的。一般隨機按投影算法選用的hash函數就是H(*)。其中參數b的取值會在后面小節中討論。

3 隨機投影法在最近鄰搜索中的應用

3.1 最近鄰搜索

最近鄰搜索可以簡單的定義為：對于m個元素的集合T，為一個待查詢元素q找到集合中相似度最高的k個元素。

最近鄰搜索最簡單的實現方法為：計算q與集合T中每一個元素的相似度，使用一個具有k個元素的大頂堆（優先隊列）保存相似度計算結果（相似度值為key）。這種實現方法每一次查詢都要遍歷整個集合T來計算相似度，當m很大并且查詢的頻率很高的時候這種暴力搜索的方法無法滿足性能要求。

當最近鄰搜索的近鄰要求并不是那么嚴格的時候，即允許top k近鄰的召回率不一定為1（但是越高越好），那么可以考慮借助于LSH算法。

3.2 隨機投影法提高執行速度

這里我們介紹當集合T的元素和查詢元素q為同維度向量(維度為n)，并且元素相似度計算方法為余弦相似度時，使用隨機投影法來提高最近鄰搜索的執行速度。具體的實現方法為：

預處理階段：使用hash函數H(*)計算集合T中所有元素的hash值，將集合T分成一個個分組，每個分組內的元素hash值均相等。用合適的數據結構保存這些hash值到分組的映射關系（如HashMap）。

查詢階段：計算查詢元素q的hash值H(q)，取集合T中所有hash值為H(q)的分組，以該分組內的所有元素作為候選集合，在候選該集合內使用簡單的最近鄰搜索方法尋找最相似的k個元素。

該方法的執行效率取決于H(*)的hash值個數，也就是分組的個數。理想情況下，如果集合T中的向量元素在空間中分布的足夠均勻，那么每一個hash值對應的元素集合大小大致為。當m遠大于向量元素的維度時，每次查詢的速度可以提高到倍。

根據以上分析H(*)中b的取值越大算法的執行速度的提升越多，并且是指數級別的提升。但是，在這種情況下H(*)函數下的概率公式p(s)，實際上表示與查詢元素q的相似度為s的元素的召回率。當b的取值越大時，top k元素的召回率必然會下降。因此算法執行速度的提升需要召回率的下降作為代價。例如：當b等于10時，如果要保證某個元素的召回率不小于0.9，那么該元素與查詢元素q的相似度必須不小于0.9999998。

3.3 提高召回率改進

為了在保證召回率的前提下盡可能提高算法的執行效率，一般可以進行如下改進：

預處理階段：生成t個獨立的hash函數，根據這t個不同的hash函數，對集合T進行t種不同的分組，每一種分組方式下，同一個分組的元素在對應hash函數下具有相同的hash值。用合適的數據結構保存這些映射關系（如使用t個HashMap來保存）。

查詢階段：對于每一個hash函數，計算查詢元素q的hash值，將集合T中所對應的分組方式下hash值為的分組添加到該次查詢的候選集合中。然后，在該候選集合內使用簡單的最近鄰搜索方法尋找最相似的k個元素。

以上改進使得集合中元素與查詢元素q的t個hash值中，只要任意一個相等，那么該集合元素就會被加入到候選集中。那么，相似度為s的元素的召回率為

在執行效率上，預處理階段由于需要計算t個hash函數的值，所以執行時間上升為t倍。查詢階段，如果單純考慮候選集合大小對執行效率的影響，在最壞的情況下，t個hash值獲得的列表均不相同，候選集集合大小的期望值為，查詢速度下降至，與簡單近鄰搜索相比查詢速度提升為倍。

下圖是召回率公式在不同的b和t取值下的s-p曲線。我們通過這些曲線來分析這里引入參數t的意義。4條藍色的線以及最右邊紅色的線表示當t取值為1（相當于沒有引入t），而b的取值從1變化到5的過程，從圖中可以看出隨著b的增大，不同相似度下的召回率都下降的非常厲害，特別的，當相似度接近1時曲線的斜率很大，也就說在高相似度的區域，召回率對相似度的變化非常敏感。10條紅色的線從右到左表示b的取值為5不變，t的取值從1到10的過程，從圖中可以看出，隨著t的增大，曲線的形狀發生了變化，高相似度區域的召回率變得下降的非常平緩，而最陡峭的地方漸漸的被移動到相對較低的相似度區域。因此，從以上曲線的變化特點可以看出，引入適當的參數t使得高相似度區域在一段較大的范圍內仍然能夠保持很高的召回率從而滿足實際應用的需求。

3.4 參數選取

根據以上分析，H(*)函數的參數b越大查詢效率越高，但是召回率越低；參數t越大查詢效率越低但是召回率越高。因此選擇適當參數b和t來折中查詢效率與召回率之間的矛盾是應用好隨機投影法的關鍵。下面提供一種在實際應用中選取b和t的參考方法。

根據實際應用的需要確定一對(s,p)，表示相似度大于等于s的元素，召回率的最低要求為p。然后將召回率公式表示成b-t之間的函數關系。根據(s,p)的取值，畫出b-t的關系曲線。如s=0.8,p=0.95時的b-t曲線如下圖所示。考慮具體應用中的實際情況，在該曲線上選取一組使得執行效率可以達到最優的(b,t)組合。

3.5 關于最近鄰文本搜索

在最近鄰文本搜索中，一般待檢索的文本或查詢文本，都已被解析成一系列帶有權重的關鍵詞，然后通過余弦相似度公式計算兩個文本之間的相似度。這種應用場景下的最近鄰搜索與以上所提到的最近鄰搜索問題相比存在以下兩個特點：

如果把每個文本的帶權重關鍵詞表都看作是一個向量元素的話，每個關鍵詞都是向量的一個維度，關鍵詞權重為該維度的值。理論上可能關鍵詞的個數并不確定（所有單詞的組合都可能是一個關鍵詞），因此該向量元素的維數實際上是不確定的。
由于關鍵詞權重肯定是大于零的，所以向量元素的每一個維度的值都是非負的。

對于第一個特點，我們需要選取一個包含n個關鍵詞的關鍵詞集合，在進行文本相似度計算時只考慮屬于該集合的關鍵詞。也就是說，每一個文本都視為是一個n維度的向量，關鍵詞權重體現為對應維度的值。該關鍵詞集合可以有很多種生成辦法，比如可以是網站上具有一定搜索頻率的關鍵詞集合，總的來說該關鍵詞集合應當能夠涵蓋所有有意義并且具有一定使用頻率的關鍵詞。通常n的取值會比較大，如幾十萬到幾百萬，由于在使用隨機投影算法時，每一個生成的隨機向量維度都為n，這種情況下需要特別考慮利用這些高維隨機向量對執行效率造成的影響，在確定b、t參數時需要考慮到這方面的影響。

對于第二個特點，由于向量元素各維度值都非負，那么這些元素在高維空間中只會出現在特定的區域中。比如當n為3時，只會出現在第一象限中。一個直觀的感覺是在生成隨機向量的時候，會不會生成大量的無用切割平面（與第一個象限空間不相交，使得所有元素都位于切割平面的同側）。這些切割平面對應的H(*)函數hash值中的二進制位恒定為1或者0，對于提高算法執行速度沒有幫助。以下說明這種擔心是沒有必要的：

切割平面與第一象限空間不相交等價于其法向量的每一個維度值都有相同的符號（都為正或者負），否則總能在第一象限空間中找到兩個向量與法向量的乘積符號不同，也就是在切割平面的兩側。那么，隨機生成的n維向量所有維度值都同號的概率為，當n的取值很大時，該概率可以忽略不計。

參考文獻

[1] P. Indyk and R. Motwani. Approximate Nearest Neighbor:Towards Removing the Curse of Dimensionality. In Proc. of the 30th Annual ACM Symposium on Theory of Computing, 1998, pp. 604–613.

[2] Google News Personalization: Scalable Online Collaborative Filtering

from:http://www.strongczq.com/2012/04/locality-sensitive-hashinglsh%E4%B9%8B%E9%9A%8F%E6%9C%BA%E6%8A%95%E5%BD%B1%E6%B3%95.html

總結

以上是生活随笔為你收集整理的局部敏感哈希Locality Sensitive Hashing(LSH)之随机投影法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。