在茫茫人海中发现相似的你——局部敏感哈希（LSH）
一、引入
在做微博文本挖掘的時候，會發現很多微博是高度相似的，因為大量的微博都是轉發其他人的微博，并且沒有添加評論，導致很多數據是重復或者高度相似的。這給我們進行數據處理帶來很大的困擾，我們得想辦法把找出這些相似的微博，再對其進行去重處理。
如果只是要找到重復的微博，我們可以用兩兩比較所有的微博，對相同的微博值保留一條即可；但這只能在數據量很小的情況下才有可能，當我們有1000萬條微博時，需要兩兩比較的微博有10^6億（n*(n-1)/2）對，這個計算量是驚人的，即便你用map-reduce，擁有強大的集群，那也頂不住數據再增加一兩個數量級。一種稍微好一點的辦法是對所以微博進行一次hash，再對桶內的微博進行比較，利用hash可以過濾了絕大多數不相同的微博，避免了無謂的比較，時間復雜度O(n)，顯著提高效率。Hash的一個基本特性就是隨機性，它將一個字符串隨機的hash到一個桶中，對于相同的兩個字符串，hash值總是相同的，但兩個hash值只要相差一點，hash值就就可能大相徑庭，可謂差之毫厘謬以千里：
>>> s1 = "我是一個字符串" >>> s2 = "我是一個字符串" >>> hash(s1) 2006838971 >>> hash(s2) 2006838971 >>> s3 = "我就是一個字符串" >>> hash(s3) -1823451294如果能有一種hash算法，能將相似的字符串hash得到相似的hash值，那就能在接近線性的時間解決海量微博中的去重問題。幸好，這樣的hash已經有大牛發明了，它叫局部敏感哈希（Locality Sensitive Hashing，簡稱LSH）。接下來我們通過海量微博文本相似項發現的例子來探討這個神奇的hash。
二、文檔相似度計算
按照文本處理的術語，我們認為一條微博是一篇文檔，度量兩篇文檔相似度有多種方法，有歐式距離、編輯距離、余弦距離、Jaccard距離，我們這里使用Jaccard距離。這里注意一下，距離和相似度是不同的概念，距離越近相似度應該越高，距離越遠相似度應該越低，因此similar = 1-distace。
集合S和T的Jaccard相識度
SIM(S,T)=|S交T||S并T|
當我們不考慮微博中重復出現的詞時，一條微博就可以看成一個集合，集合的元素是一個個的詞：
s1 = '''從 決心 減肥 的 這 一刻 起 請 做 如下 小 改變 你 做 得 到 么''' s2 = '''從 決心 減肥 的 這 一刻 起 請 做 如下 小 改變'''sim(s1,s2)=11/16=0.69.
三 文檔的Shingling
為了字面上相似的文檔，將文檔表示成集合最有效的方法是構建文檔中的短字符串集合，一個常用的方法時Shingling（不知道翻譯成什么，囧），看定義很簡單的：文檔的k-shingle定義為其中長度為k的子串。對于上面的字符串s2，選擇k=2，這s2中的所有2-single組成的集合為:
{"從 決心","決心 減肥","減肥 的","的 這","這 一刻","一刻 起","起 請","請 做","做 如下","如下 小","小 改變"}k值的選取具有一定的技巧，k越大越能找到真正相似的文檔，而k越小就能召回更多的文檔，但他們可能相似度不高，比如k=1，就變成了基本詞的比較了。我這里詞作為shingle的基本單位，在英文處理中，是以字母為基本單位，原因在于漢字有上萬個，而英文字母只有27個，以漢字為單位將造成shingle集合巨大。
遍歷所用文檔，就得到了shingle全集。
四、保持相似度矩陣表示
1、集合的矩陣表示
假設我們有這樣4篇文檔（分詞后）：
s1 = "我 減肥" s2= "要" s3 = "他 減肥 成功" s4 = "我 要 減肥"為方便敘述，我們取k=1，這時shingle全集為{我，他，要，減肥，成功}，將文檔表示成特征矩陣，行代表shingle元素，列代表文檔，只有文檔j出現元素i時，矩陣M[i][j]=1，否則M[i][j] = 0.
| 元素 | S1 | S2 | S3 | S4 |
| 我 | 1 | 0 | 0 | 1 |
| 他 | 0 | 0 | 1 | 0 |
| 要 | 0 | 1 | 0 | 1 |
| 減肥 | 1 | 0 | 1 | 1 |
| 成功 | 0 | 0 | 1 | 0 |
實際上，真正計算的過程中矩陣不是這樣表示的，因為數據很稀疏。得到矩陣表示后，我們來看最小hash的定義。
五、最小哈希（min-hashing）
最小hash定義為：特征矩陣按行進行一個隨機的排列后，第一個列值為1的行的行號。舉例說明如下，假設之前的特征矩陣按行進行的一個隨機排列如下：
| 元素 | S1 | S2 | S3 | S4 |
| 他 | 0 | 0 | 1 | 0 |
| 成功 | 0 | 0 | 1 | 0 |
| 我 | 1 | 0 | 0 | 1 |
| 減肥 | 1 | 0 | 1 | 1 |
| 要 | 0 | 1 | 0 | 1 |
最小哈希值：h(S1)=3，h(S2)=5，h(S3)=1，h(S4)=2.
為什么定義最小hash？事實上，兩列的最小hash值就是這兩列的Jaccard相似度的一個估計，換句話說，兩列最小hash值同等的概率與其相似度相等，即P(h(Si)=h(Sj)) = sim(Si,Sj)。為什么會相等？我們考慮Si和Sj這兩列，它們所在的行的所有可能結果可以分成如下三類：
（1）A類：兩列的值都為1；
（2）B類：其中一列的值為0，另一列的值為1；
（3）C類：兩列的值都為0.
特征矩陣相當稀疏，導致大部分的行都屬于C類，但只有A、B類行的決定sim(Si,Sj)，假定A類行有a個，B類行有b個，那么sim(si,sj)=a/(a+b)。現在我們只需要證明對矩陣行進行隨機排列，兩個的最小hash值相等的概率P(h(Si)=h(Sj))=a/(a+b)，如果我們把C類行都刪掉，那么第一行不是A類行就是B類行，如果第一行是A類行那么h(Si)=h(Sj)，因此P(h(Si)=h(Sj))=P(刪掉C類行后，第一行為A類)=A類行的數目/所有行的數目=a/(a+b)，這就是最小hash的神奇之處。
六、最小hash簽名
有了最小hash還不夠，一次最小hash只是一次獨立的隨即事件，中心極限定理告訴我們，只有多次重復隨機事件才能造就必然。選擇n個隨機排列作用于特征矩陣，得到n個最小hash值，h1,h2,...,hn，這n個最小hash值組成一個n維向量，即為最小簽名，兩列的最小簽名的相似度即為兩列的Jaccard相似度的估計。
現在就看如何計算最小簽名了。對一個很大的矩陣按行進行隨機排列，首先需要得到一個隨機排列，然后按這個隨機排列去排序，這將耗費很長的時間。我們需要一種方法來模擬隨機排列的過程。又有一個神奇的辦法是：找一個哈希函數h，將第r行放在排列轉換后的第h(r)的位置上。我們不再是選擇n個隨機排列，而是選擇n個hash，h1,h2,...,hn作用于行，這樣我們就可以得到簽名矩陣。令SIG(i,c)為第i個哈希函數在第c列上的元素。一開始對所有的SIG(i,c)初始化為無窮大，然后從上往下對列c進行處理：
if特征矩陣中的c列r行值為1:
for i in xrange(n):#對每個hash函數
SIG(i,c)=min(SIG(i,C),hi(r))
else:
continue
按上面的方法處理每一列，即得到最小簽名矩陣。
七、基于最小hash的局部敏感hash
前面我們辛辛苦苦的工作貌似只是將一個文檔的集合轉換為一個最小簽名，雖然這個簽名大大壓縮了集合的空間，但要計算兩列的相似度還是需要兩兩比較簽名矩陣兩列的相似度，如果有n篇文檔，兩個比較的次數是n*(n-1)/2。接下來就看局部敏感hash怎么個敏感法。
我們對簽名矩陣按行進行分組，將矩陣分成b組，每組由r行組成，下面的實列將一個簽名矩陣分成6組，每組由3行組成。
| 組1 | ... | 1 0 0 0 2 3 2 1 2 2 0 1 3 1 1 | ... |
| 組2 | ? | ? | ? |
| 組3 | ? | ? | ? |
| 組4 | ? | ? | ? |
| 組5 | ? | ? | ? |
| 組6 | ? | ? | ? |
分組之后，我們對最小簽名向量的每一組進行hash，各個組設置不同的桶空間。只要兩列有一組的最小簽名部分相同，那么這兩列就會hash到同一個桶而成為候選相似項。簽名的分析我們知道，對于某個具體的行，兩個簽名相同的概率p =兩列的相似度= sim(S1,S2)，然后：
（1）在某個組中所有行的兩個簽名值都相等概率是pr;
（2）在某個組中至少有一對簽名不相等的概率是1?pr;
（3）在每一組中至少有一對簽名不相等的概率是(1?pr)b;
（4）至少有一個組的所有對的簽名相等的概率是1?(1?pr)b;
于是兩列成為候選相似對的概率是1?(1?pr)b，它采樣值以及曲線如下：
| p | 1-(1-p^5)^20 |
| 0.1 | 0.0002 |
| 0.2 | 0.0064 |
| 0.3 | 0.0475 |
| 0.4 | 0.1860 |
| 0.5 | 0.4701 |
| 0.6 | 0.8019 |
| 0.7 | 0.9748 |
| 0.8 | 0.9996 |
| 0.9 | 1.0000 |
當兩篇文檔的相似度為0.8時，它們hash到同一個桶而成為候選對的概率是0.9996，而當它們的相似度只有0.3時，它們成為候選對的概率只有0.0475，因此局部敏感hash解決了讓相似的對以較高的概率hash到同一個桶，而不相似的項hash到不同的桶的問題。
對于每個桶內的文檔，會有一部分是不相似的，因為hash有沖突，需要進行桶內檢驗。基于最小簽名的LSH很容易轉化為Map-reduce來計算。
下面是我對微博進行局部敏感hash的一個結果（分詞并刪掉標點）：
1 "外表 活潑 內心 孤僻 的 人 會 做 的 事 1 手機 不 離 身 2 對待 不同 的 人 有 不同 的 性格 3 從 小 懂得 很多 道理 4 有 時候 很 神經 有時候 很 鎮靜 5 會 因為 別人 一 句 話 傷心 但 不 會 被 發現 6 安慰 很多 人 但 自己 卻 沒 人 安慰 7 會 懷念 從前 討厭 現在 8 有時候 會 笑 的 沒 心 沒 肺 有 時 卻 很 沉默"2 "外表 活潑 內心 孤僻 的 人 會 做 的 事 1. 手機 不 離 身 2. 對待 不同 的 人 有 不同 的 性格 3. 從小 懂得 很多 道理 4. 有時候 很 神經 有時候 很 鎮靜 5. 會 因為 別人 一 句 話 傷心 但 不 會 被 發現 6. 安慰 很多 人 但 自己 卻 沒 人 安慰 7. 會 懷念 從前 討厭 現在 8. 有時候 會 笑 的 沒 心 沒 肺 有時 卻 很 沉默"3 "射手 座 的 特征 1 手機 不 離 身 2 對待 不同 的 人 有 不同 的 性格 3 從 小 懂得 很多 道理 4 有 時候 很 神經 有時候 很 鎮靜 5 會 因為 別人 一 句 話 傷心 但 不 會 被 發現 6 安慰 很多 人 但 自己 卻 沒 人 安慰"4 "外表 活潑 內心 孤僻 的 人 會 做 的 事 1 手機 不 離 身 2 對待 不同 的 人 有 不同 的 性格 3 從 小 懂得 很多 道理 4 有 時候 很 神經 有時候 很 鎮靜 5 會 因為 別人 一 句 話 傷心 但 不 會 被 發現 6 安慰 很多 人 但 自己 卻 沒 人 安慰 7 會 懷念 從前 討厭 現在 8 有時候 會 笑 的 沒 心 沒 肺 有 時 卻 很 沉默 你 是 這樣 嗎"5 "金牛座 特征 1 手機 不 離 身 2 對待 不同 的 人 有 不同 的 性格 3 從 小 懂得 很多 道理 4 有 時候 很 神經 有時候 很 鎮靜 5 會 因為 別人 一 句 話 傷心 但 不 會 被 發現 6 安慰 很多 人 但 自己 卻 沒 人 安慰 7 會 懷念 從前 討厭 現在 8 有時候 會 笑 的 沒 心 沒 肺 有時 卻 很 沉默"6 "外表 活潑 內心 孤僻 的 人 會 做 的 事 1 手機 不 離 身 2 對待 不同 的 人 有 不同 的 性格 3 從 小 懂得 很多 道理 4 有 時候 很 神經 有時候 很 鎮靜 5 會 因為 別人 一 句 話 傷心 但 不 會 被 發現 6 安慰 很多 人 但 自己 卻 沒 人 安慰 7 會 懷念 從前 討厭 現在 8 有時候 會 笑 的 沒 心 沒 肺 有 時 卻 很 沉默 你 是 這樣 嗎"7 "天蝎座 特征 1 手機 不 離 身 2 對待 不同 的 人 有 不同 的 性格 3 從 小 懂得 很多 道理 4 有 時候 很 神經 有時候 很 鎮靜 5 會 因為 別人 一 句 話 傷心 但 不 會 被 發現 6 安慰 很多 人 但 自己 卻 沒 人 安慰 7 會 懷念 從前 討厭 現在 8 有時候 會 笑 的 沒 心 沒 肺 有時 卻 很 沉默"8 "雙子座 的 你 是 這樣 的 嗎 1 手機 不 離 身 睡覺 不 關機 2 對待 不同 的 人 有 不同 的 性格 3 從 小 懂得 很多 道理 但 知 行 往往 難以 合 一 4 有 時候 很 神經 有時候 很 鎮靜 5 會 因為 別人 一 句 話 傷心 但 不 會 被 發現 6 很 會 安慰 別人 卻 不 會 安慰 自己 7 會 經常 懷念 從 前"9 "外表 活潑 內心 孤僻 的 人 會 做 的 事 1 手機 不 離 身 2 對待 不同 的 人 有 不同 的 性格 3 從 小 懂得 很多 道理 4 有 時候 很 神經 有時候 很 鎮靜 5 會 因為 別人 一 句 話 傷心 但 不 會 被 發現 6 安慰 很多 人 但 自己 卻 沒 人 安慰 7 會 懷念 從前 討厭 現在 8 有時候 會 笑 的 沒 心 沒 肺 有時 卻 很 沉默 你 是 這樣 嗎"10 "外表 活潑 內心 孤僻 的 人 會 做 的 事 1 手機 不 離 身 2 對待 不同 的 人 有 不同 的 性格 3 從 小 懂得 很多 道理 4 有 時候 很 神經 有時候 很 鎮靜 5 會 因為 別人 一 句 話 傷心 但 不 會 被 發現 6 安慰 很多 人 但 自己 卻 沒 人 安慰 7 會 懷念 從前 討厭 現在 8 有時候 會 笑 的 沒 心 沒 肺 有 時 卻 很 沉默 你 是 這樣 嗎 轉"11 "外表 活潑 內心 孤僻 的 人 會 做 的 事 1. 手機 不 離 身 2. 對待 不同 的 人 有 不同 的 性格 3. 從小 懂得 很多 道理 4. 有時候 很 神經 有時候 很 鎮靜 5. 會 因為 別人 一 句 話 傷心 但 不 會 被 發現 6. 安慰 很多 人 但 自己 卻 沒 人 安慰 7. 會 懷念 從前 討厭 現在 8. 有時候 會 笑 的 沒 心 沒 肺 有時 卻 很 沉默"看了這個，你還相信星座嗎？
八、局部敏感hash的一般定義
局部敏感hash實質上是滿足一定條件的函數簇，上面介紹只是一個基于Jaccard的例子，實際上還有面向其他距離的LSH。
令d1<d2是定義在距離測定d下得兩個距離值，如果一個函數族的每一個函數f滿足：
（1）如果d(x,y)<=d1,則f(x)=f(y)的概率至少為p1，即P(f(x)=f(y)) >= p1;
（2）如果d(x,y)>=d2,則f(x)=f(y)的概率至多為p2，即p(f(x)=f(y)) <= p2.
那么稱F為(d1,d2,p1,p2)-敏感的函數族。實際上我們之前的最小hash函數族是(d1,d2,1-d1,1-d2)-敏感的。
局部敏感hash族還可以進行放大處理，已獲得更高的準確率和召回率，當然也有面向其他距離的LSH。本文的東西全部源自參考文獻的課本，有興趣可以好好讀一下這本書。
參考文獻：
《Mining of Massive Dataset》
《互聯網大規模數據挖掘與分布式處理》
from: http://www.kuqin.com/shuoit/20140619/340686.html
總結
以上是生活随笔為你收集整理的在茫茫人海中发现相似的你——局部敏感哈希（LSH）的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： R树空间索引
- 下一篇： K Nearest Neighbor 算