私認為，文本的相似性可以分為兩類：一類是機械相似性；一類是語義相似性。
機械相似性代表着，兩個文本内容上的相關程度，比如“你好嗎”和“你好”的相似性，純粹代表着内容上字元是否完全共現，應用場景在：文章去重；
語義相似性代表着，兩個文本語義上的相似程度，比如“蘋果”和“公司”的相似性，本篇不做這一讨論，可參考筆者的另外一篇部落格：
NLP︱句子級、詞語級以及句子-詞語之間相似性（相關名稱：文檔特征、詞特征、詞權重）
把LSH局部敏感雜湊演算法講明白的一篇部落格：Locality Sensitive Hashing ( LSH，局部敏感哈希 ) 詳解
正常的敏感hash可以将文本降維成簡單數字串，但是計算相似時候隻能兩兩比較，計算量巨大。
局部敏感雜湊演算法一般用在正常Hash之後，相比兩兩比較，LSH可以實作再降維+局部尋找比對對。
————————————————————————————————————————————————
一、基本概念界定上的差別
1、Hash叫哈希，也叫散列，可以叫雜湊演算法，也可以叫雜湊演算法；
2、hash與其他諸如simhash/minhash的差別：
一般的hash可能兩個文檔本來相似，但是hash之後的值反而不相似了；simhash/minhash可以做到兩個文檔相似，hash之後仍然相似；
3、simhash與Minhash的差別：
simhash和minhash可以做到兩個文檔Hash之後仍然相似，但是simhash計算相似的方法是海明距離；而minhash計算距離的方式是Jaccard距離。
4、局部敏感哈希與simhash、minhash的差別。
局部敏感哈希可以在這兩者基礎上更快的找到相似、可比對的對象，而且繼承了simhash/minhash的優點，相似文檔LSH計算之後還是保持相似的。
————————————————————————————————————————————————
二、hash函數拓展simhash、minhash算法
1、海明距離與Jaccard距離
（1）Hamming Distance（海明距離）
Hamming Distance可以用來度量兩個串（通常是二進制串）的距離，其定義為這兩個二進制串對應的位有幾個不一樣，那麼海明距離就是幾，值越小越相似。例如x=1010，y=1011，那麼x和y的海明距離就是1。又如x=1000，y=1111，那麼x和y的海明距離就是3。
（2）Jaccard Coefficient（Jaccard 系數）
Jaccard Coefficient用來度量兩個集合的相似度，設有兩個集合
和
，它們之間的Jaccard Coefficient定義為：
，值越大越相似。
例如
，
，則
。
參考：常用相似性、相關性度量名額
2、simhash與minhash
simhash和minhash由于hash之後的算法構造不同，是以需要不同的距離去測度，一般simhash用的是海明距離，而minhash用的是Jaccard距離。
hash原理不展開介紹，放一張圖大緻了解一下，詳情可見參考文獻：
（1）simhash：
（2）minhash：
Min-hashing定義為：特征矩陣按行進行一個随機的排列後，第一個列值為1的行的行号。舉例說明如下，假設之前的特征矩陣按行進行的一個随機排列如下：
| 元素 | S1 | S2 | S3 | S4 |
|---|---|---|---|---|
| 他 | 1 | |||
| 成功 | 1 | 1 | ||
| 我 | 1 | |||
| 減肥 | 1 | 1 | 1 | |
| 要 | 1 | 1 |
最小哈希值：h(S1)=3，h(S2)=5，h(S3)=1，h(S4)=2.
參考文獻：
使用simhash進行海量文本去重（來源于：poll的筆記）
局部敏感雜湊演算法(Locality Sensitive Hashing，LSH)（來源于：poll的筆記）
————————————————————————————————————————————————
三、局部敏感哈希(Locality Sensitive Hashing，LSH)算法
局部敏感雜湊演算法應該算是 hash㈡（Hash之後再Hash）。
1、LSH算法流程介紹
整個流程：
1、一般的步驟是先把資料點（可以是原始資料，或者提取到的特征向量）組成矩陣；
2、第一次hash functions（有多個哈希函數，是從某個哈希函數族中選出來的）哈希成一個叫“簽名矩陣（Signature Matrix）”的東西，這個矩陣可以直接了解為是降維後的資料，此時用simhash、minhash來做，第一步的hash過程可以使用不同的functions來做；
3、第二次LSH把Signature Matrix哈希一下，就得到了每個資料點最終被hash到了哪個bucket裡，如果新來一個資料點，假如是一個網頁的特征向量，我想找和這個網頁相似的網頁，那麼把這個網頁對應的特征向量hash一下，看看它到哪個桶裡了。
于是bucket裡的網頁就是和它相似的一些候選網頁，這樣就大大減少了要比對的網頁數，極大的提高了效率。注意上句為什麼說是“候選網頁”，也就是說，在那個bucket裡，也有可能存在和被hash到這個bucket的那個網頁不相似的網頁，原因請回憶前面講的“降維”問題。
但LSH的巧妙之處在于可以控制這種情況發生的機率，這一點實在是太牛了，下面會介紹。
2、LSH實質解讀
那麼可以看出LSH的實質其實就是把hash之上的資料再一次降維。相比兩兩比較，LSH可以實作再降維+局部尋找比對對。
降維會對相似性度量造成什麼影響？
資料的維數在某種程度上能反映其資訊量，一般來說維數越多，其反映的資訊量就越大，比如說對于一個人，假設有一個一維資料：（姓名）,有一個三維資料（姓名，身高，體重），那麼這個三維資料反映的資訊是不是要比一維的多？如果我們知道的資訊越多，是不是就能越準确地判定兩個東西的相似性？
是以，降維就在某種程度上造成的資訊的丢失，在降維後的低維空間中就很難100%保持原始資料空間中的相似性，是以剛才是說“保持一定的相似性”。
一方面想把資料降維，一方面又希望降維後不丢失資訊。
那麼LSH就要做一個妥協了，雙方都讓一步，那麼就可以實作在損失一點相似性度量準确性的基礎上，把資料降維
3、LSH局部敏感雜湊演算法
LSH流程中有兩個流程，第一個hash是用simhash,minhash來做，在第一部分裡面有，第二個hash才是局部敏感哈希的内容。
LSH的具體流程：
1、将Signature Matrix分成一些bands，每個bands包含一些rows（就像把每一個文檔ID變成4個（band）部分，4個（band）顔色）。
2、然後把每個band哈希到一些bucket中，注意bucket的數量要足夠多（篩選：設定bucket個籃子，然後比對，相同的顔色部分扔到相應的籃子裡面）。
3、計算相似性。使得兩個不一樣的bands被哈希到不同的bucket中，這樣一來就有：如果兩個document的bands中，至少有一個share了同一個bucket，那這兩個document就是candidate pair，也就是很有可能是相似的。（找相似：同一個籃子裡面的就是有可能相似的樣本框；如果兩個籃子都有同樣的顔色和同樣的ID，說明這幾個同樣的ID相似性較高）
4、相似性分析案例
下面來看看一個例子，來算一下機率，假設有兩個document，它們的相似性是80%，它們對應的Signature Matrix矩陣的列分别為C1,C2，又假設把Signature Matrix分成20個bands，每個bands有5行，那麼C1中的一個band與C2中的一個band完全一樣的機率就是0.8^5=0.328，那麼C1與C2在20個bands上都沒有相同的band的機率是(1-0.328)^20=0.00035，這個0.00035機率表示什麼？它表示，如果這兩個document是80%相似的話，LSH中判定它們不相似的機率是0.00035，多麼小的機率啊！
再看先一個例子，假設有兩個document，它們的相似性是30%，它們對應的Signature Matrix矩陣的列分别為C1,C2，Signature Matrix還是分成20個bands，每個bands有5行，那麼C1中的一個band與C2中的一個band完全一樣的機率就是0.3^5=0.00243，那麼C1與C2在20個bands至少C1的一個band和C2的一個band一樣的機率是1-（1-0.00243）^20=0.0474，換句話說就是，如果這兩個document是30%相似的話，LSH中判定它們相似的機率是0.0474，也就是幾乎不會認為它們相似，多麼神奇。
這裡涉及到的參數有點多：
第一個參數：buckets，LSH會預先設定一些籃子，作為相似性匹對的粒度，Buckets越多越好，粒度越細，當然越吃計算量；
第二個參數：次元h，就是第一步hash成多長的次元，simhash可以指定劃分的次元；
第三個參數：bands（b），簽名矩陣分塊，分為不同的部分；
第四個參數：行數row（r），r=h/b，簽名矩陣每一塊有r行（r個文本）；
第五個參數：相似性S,代表兩個文檔的相似性。
第六個參數：相似性J,代表buckets共現相似性（J）。
從操作的流程可以得到，LSH第二步是先根據 buckets共現相似性（J） 找出潛在的候選比對對，然後在這些比對對之上計算文檔相似性（S）。兩者互相關系為：
J=1-（1-S^r）^b (1)
文本的相似性才是我們最後要求得的。
更為神奇的是，LSH這些機率是可以通過選取不同的band數量以及每個band中的row的數量來控制的：
縱軸代表buckets共現相似性（J），橫軸代表文檔相似性（S）。看懂這個圖就可以大緻了解實戰過程中，如何設定參數啦。
看圖可知在文本相似性S達到某一個臨界值的時候，臨界值之下LSH會智能得判定 buckets共現相似性（J）極小，而大于某一個臨界值的時候，LSH會判定buckets相似性J極高。
LSH會将相似性高的認為是候選比對對留下，而相似性低的則不考慮。是以大大簡化了計算量。這個閥值的公式為：
S（t）=（1/b）^1/r (2)
當然筆者在這從案例從發設想如何構造該門檻值：
如果設定h=200次元的hash值，bands設定為b=50，那麼r=4，則根據公式（2）可得S（t）=0.376，S（t）>0.376則會判定為比對對，低精度，若有一個文本相似性為S=0.5，則根據公式（1）在已經S情況下：J(buckets)=0.96；
如果設定h=200次元的hash值，bands設定為b=4，那麼r=50，則根據公式（2）可得S（t）=0.972，S（t）>0.972則會判定為比對對，高精度，若有一個文本相似性為S=0.5，則根據公式（1）在已經S情況下：J(buckets)=3.55E-15。
上述結果比較符合預期的就是，在低精度的情況下超過門檻值的，相似性J立刻變得極高，判定為比對對。
從嚴格性來看，可以通過調整h次元、bands的b來調整門檻值，達到調節精度的目的；當然啦，肯定是高精度比較好。
本篇很多都是筆者自己瞎想的，若有錯請大家一定要給我說呀！！！！！
————————————————————————————————————————————
拓展一：應用場景
LSH的應用場景很多，凡是需要進行大量資料之間的相似度（或距離）計算的地方都可以使用LSH來加快查找比對速度，下面列舉一些應用：
（1）查找網絡上的重複網頁
網際網路上由于各式各樣的原因（例如轉載、抄襲等）會存在很多重複的網頁，是以為了提高搜尋引擎的檢索品質或避免重複建立索引，需要查找出重複的網頁，以便進行一些處理。其大緻的過程如下：将網際網路的文檔用一個集合或詞袋向量來表征，然後通過一些hash運算來判斷兩篇文檔之間的相似度，常用的有minhash+LSH、simhash。
（2）查找相似新聞網頁或文章
與查找重複網頁類似，可以通過hash的方法來判斷兩篇新聞網頁或文章是否相似，隻不過在表達新聞網頁或文章時利用了它們的特點來建立表征該文檔的集合。
（3）圖像檢索
在圖像檢索領域，每張圖檔可以由一個或多個特征向量來表達，為了檢索出與查詢圖檔相似的圖檔集合，我們可以對圖檔資料庫中的所有特征向量建立LSH索引，然後通過查找LSH索引來加快檢索速度。目前圖像檢索技術在最近幾年得到了較大的發展，有興趣的讀者可以檢視基于内容的圖像檢索引擎的相關介紹。
（4）音樂檢索
對于一段音樂或音頻資訊，我們提取其音頻指紋（Audio Fingerprint）來表征該音頻片段，采用音頻指紋的好處在于其能夠保持對音頻發生的一些改變的魯棒性，例如壓縮，不同的歌手錄制的同一條歌曲等。為了快速檢索到與查詢音頻或歌曲相似的歌曲，我們可以對資料庫中的所有歌曲的音頻指紋建立LSH索引，然後通過該索引來加快檢索速度。
（5）指紋比對
一個手指指紋通常由一些細節來表征，通過對比較兩個手指指紋的細節的相似度就可以确定兩個指紋是否相同或相似。類似于圖檔和音樂檢索，我們可以對這些細節特征建立LSH索引，加快指紋的比對速度。
來源：局部敏感哈希(Locality-Sensitive Hashing, LSH)方法介紹
每每以為攀得衆山小，可、每每又切實來到起點，大牛們，緩緩腳步來俺筆記葩分享一下吧，please~
———————————————————————————