LSH

locality sensitive hashing(LSH) 是哈希算法中，比較重要的方法。LSH方法是將相似的數據以較高的概率哈希到同一個桶里面，從而達到近似鄰檢索的目的，另外，待測數據維度非常大時，lsh也可用于降維。

LSH族^[1]

LSH族 \(\mathcal H = \{h: S\rightarrow U\}\) 稱為\((r1,r2,p1,p2)\)對于測度\(D\)是局部敏感的，如果 \(\forall v,q\in S\)有

如果\(v\in B(q,r_1)\) , 那么有 \(Pr_{\mathcal H}[h(q)=h)(v)]\ge p_1\),

如果\(v\notin B(q,r_2)\),那么有\(Pr_{\mathcal H}[h(q)=h)(v)]\le p_2\).

其中，(\(B(v, r)=\{q \in X \mid d(v, q) \leq r\}\) 表示以v為中心，r為半徑的球體)

上面的不等式還需要滿足兩個條件，即\(p_1>p_2\)以及\(r_1<r_2\). 在近似最近鄰中，也即\((R,c)\)-NN問題中，可設\(r_1 = R\)以及\(r_2 = c\cdot R\).

已知一啥希族滿足上述定義，可以通過使用多種不同的哈希函數來擴大p1與p2之間的距離，這樣檢索的效果也會更好。比如， 我們選了k個哈希函數，可以定義一個函數族\(\mathcal G = \{g: S\rightarrow U^k\}\)，使得\(\mathcal g(v) = \{h_1(v),h_2(v2),...,h_k(v)\}\),其中\(h_i(v)\in\mathcal H\). 然后我們創建L個\(g_i(v), i \in \{1,2,...,L\}\).\(g_i(v)\)之間是相互獨立的。

LSH是一種思想，或者說是一種框架，只要定好哈希函數以及距離測度D即可。

有幾個比如有代表性的工作：minhash，simhash，p-stable hash等。這些基本區別是使用不同的hash以及不同的距離(或相似)方法。

MinHash特別適用于數據比較稀疏的情形， 比如新聞去重等等。在講minhash之前需要講一個滑動窗口切詞法(shingling).

比如：'today is a sunny day'，使用寬度為3的滑窗,會生成如字符片斷：

'tod', 'oda','day','ay ', 'y a',...

這樣將每個片段one-hot編碼，這樣此句話就會變成類似如下這種只包括0，1兩個值的長向量：

[0,0,0,1,0,0,0,0,1,....]

此過程類似分詞后構建詞表過程。只不過，使用shingle的操作一定程度上保留了文章的詞序性(特別是滑窗較寬時，比如10或20時，比一般的詞長一些，類似n-grams). 此類操作在對網頁去重等，有比較不錯的效果，操作也簡單，只需要計算兩網頁one hot編碼向量的jaccard距離即可。但當兩個向量很大時，計算jaccard距離會很耗資源，耗時. 如果可以找一種簡單快速地計算Jaccard距離的方法，那么對于高維數據的相似性評估就會很方便。經觀察，如果將集合A與B合并成一個集合C, 并從集合C中隨機抽取一個元素X，那么此元素X既屬于A也屬于B的概率為|\(A\cap B\)|/\(|A\cup B|\)，即Jaccard相似度 . 基于此邏輯，我們可以將所有元素找到構成一個詞典列表。然后我們有放回地每次從中隨機抽取一個元素，判斷其是否在某兩個集合中(比如仍是A，B兩集合)，經過多次重復，然后統計取出元素同時在集合A，B中的頻率，即可近似等于兩者的(Jaccard)相似度。

將集合\(\mathbb U\) (可理解為語料)中的元素(如語料中的某篇訪問)用onehot的方式表示，那么對于集合:

其可以其表示成一個二元(共現)矩陣，類似如下（僅為一示例），其中\(s_k\) (k列) 為第k個文章按上述處理得到的onehot表示。

將這二元矩陣按行重新排列，那么某一集合\(S_k\)的minhash值為即為排列后的第一個“1”所在行號。那么

如何理解呢？這里有一個關鍵點要記在心里，即按行進行重新排列的，那么每行的元素是一起同時變動的。那么從第一行開始往下找，在第\(S_{k_1}\)列與第\(S_{k_2}\)列同時出現一的概率就是其jaccard相似度。這樣，可以讓\(n = k\times L\)，即可以執LSH操作。

simhash

首先將數據如網頁文本轉化成一組特征(如基本的nlp操作，如分詞，去停用詞，tdidf等等)，然后，將特征哈希成一個f維的二元特征向量(比如f=64)，然后將其轉化成示性向量(具體做法是將其中的0變成-1，而1還是1)， 然后乘以此特征權重(比如詞頻)，然后，再將所有物征相加，最后再進行轉化成二元特征向量(元素為正變為1， 其他變為0)， 這樣的再拼接成一個哈希值，即是此文本的哈希特征值。

比如: 假設在一網頁中處理后只有三個詞" simhash","simlarity", " algorithm",對應的詞頻分別為3，1，5。使用哈希函數{‘simhash': '101101','simlarity': '110010,,'algorithm':'100001'}， 然后轉化成特征向量化{'simhash':[1,0,1,1,0,1],'simlarity':[1,1,0,0,1,0],'algorithm':[1,0,0,0,0,1]}，再轉化成示性向量{'simhash':[1,-1,1,1,-1,1],'simlarity':[1,1,-1,-1,1,-1],'algorithm':[1,-1,-1,-1,-1,1]}。接著，將特征的特征向量與其權重(即詞頻)相乘：{'simhash':[3,-3,3,3,-3,3],'simlarity':[1,1,-1,-1,1,-1],'alogrithm':[5,-5,-5,-5,-5,5]},再將向量相加：[9, -7,-3,-3,-7,7], 再轉化成二元向量[1,0,0,0,0,1],最后生成文本哈希特征值:'100001'.

根據經驗，如果兩個網頁的漢明距離不大于3的話，那么它們是重復的，基于此，可以將64位的哈希值平均分成四份，根據抽屜原理，至少有一個片斷是相等的。