[转]文本相似性算法：simhash/minhash/余弦算法
數(shù)據(jù)挖掘之lsh（局部敏感hash） minhash、simhash
在項(xiàng)目中碰到這樣的問題：
互聯(lián)網(wǎng)用戶每天會(huì)訪問很多的網(wǎng)頁，假設(shè)兩個(gè)用戶訪問過相同的網(wǎng)頁，說明兩個(gè)用戶相似，相同的網(wǎng)頁越多，用戶相似度越高，這就是典型的CF中的user-based推薦算法。
算法的原理很簡單，只要兩兩計(jì)算用戶的相似性，針對(duì)每個(gè)用戶，獲取最相似的K個(gè)用戶即可。
但是在實(shí)際的工程上，假定用戶規(guī)模在億的規(guī)模N，計(jì)算復(fù)雜度為N*N，即使是分布式，也是非常可怕的復(fù)雜度。
考慮一下，我們是不是真的需要計(jì)算所有用戶之間的相似性？其實(shí)我們只需要計(jì)算和用戶A最相似的K個(gè)用戶即可，如果已知B和A一定不相似，那么就沒有必要計(jì)算，這就是LSH的思想。
?
LSH：local sensitive hash，局部敏感哈希，關(guān)注可能相似的pair，而非所有的pair，這是lsh的基本思想。
?
舉個(gè)例子：
用戶user1 訪問過 url1,url2
用戶user2訪問過 url2,url3
用戶user3訪問過url3
很明顯，user1和user2相似，而 user1和user3是不相似的，換句話，user1和user3是不需要比較的。
如何做到呢?最簡單的思路，把url作為hash的key，user作為value，計(jì)算同一個(gè)key下面user的相似度。
url1:user1
url2:user1 user2
url3:user2 user3
這樣分別計(jì)算user1 user2 以及user2和user3的相似性即可，不用計(jì)算user1和user3,也就是不相似的user不需要計(jì)算其相似性，基本上就是LSH的思想
?
但是，很明顯，上面的作法過于簡單和粗暴：
1.如果每個(gè)user有上w維的特征，針對(duì)每個(gè)特征做一個(gè)hash，會(huì)導(dǎo)致計(jì)算復(fù)雜度大大增加，兩個(gè)特征相同的用戶，需要計(jì)算w次相似性
2.無法刻畫lsh中，只關(guān)注相似的paire 中的"相似”程度，比如如果相似性<0.5,則認(rèn)為不相似，盡量不出現(xiàn)在一個(gè)桶等等
?
第一個(gè)問題談到是降維，第二個(gè)是如何進(jìn)行刻畫相似性以及進(jìn)行hash。
?
?
minhash以及simhash就是來解決上面的兩個(gè)問題的，這兩個(gè)都是來刻畫jaccard距離的。
回到剛開始的例子，及時(shí)就是計(jì)算user1與user2的jaccard距離，假設(shè)url進(jìn)行了編號(hào)，有唯一的id，最大編號(hào)為N，每個(gè)用戶訪問過的url數(shù)目為N(u)。
這樣我們可以理解每個(gè)用戶有N個(gè)特征，其中訪問過的對(duì)應(yīng)位置為1，沒有訪問的為0，維數(shù)很高，幾十B的規(guī)模。
?
minhash就是來解決降維的問題，具體的minhash原理網(wǎng)上有很多介紹，就不在詳細(xì)說了。
minhash最后的產(chǎn)出是每個(gè)用戶有K維的特征{id1,id2....idk}，不同用戶第k特特征相同的概率和直接利用用戶原始的N維特征計(jì)算jaccard距離的相似性相同, K<<N，達(dá)到降維的目的。
如果利用K維特征，計(jì)算2-2相似性，復(fù)雜度還是很高。
?
利用LSH思想，我們只需要計(jì)算可能形似用戶的相似度，保證相似的用戶對(duì)應(yīng)的hash值一樣，而不相似的對(duì)應(yīng)的hash值不同。
兩個(gè)用戶度為p，則用戶對(duì)應(yīng)相同位置特征值相同的概率為p，有證明。
將K個(gè)特征劃分為band，b1,b2...bm，每個(gè)band里面的元素個(gè)數(shù)為r個(gè)，r*m=K
用戶每個(gè)band里面r個(gè)特征全部相同的概率為p^r，也就是基于這個(gè)band作為hash值，兩個(gè)用戶hash值相同的概率為p^r，那么hash值不同的概率為1-s^r，m個(gè)band hash值都不一樣的概率為(1-p^r)^m，也就是兩個(gè)用戶不在任何一個(gè)桶里面的概率。
而1-（1-p^r)^m 則為兩個(gè)用戶落在至少一個(gè)桶里面的概率，很容易理解，如果r越小，最后值越大，很不相似（p很小)的元素落在一個(gè)桶里面的概率很大，計(jì)算的復(fù)雜度高。如果r很大，則最后的值很小，也就是很相似(p比較到)落在一個(gè)桶里面的概率很小.
比如 r=1, m=16，p=0.2，計(jì)算后為99.8%，也就是相似性為0.2的兩個(gè)元素，99.2%的概率會(huì)落在一個(gè)桶里面，進(jìn)行計(jì)算，事實(shí)上是沒有必要的。
r=20,m=1,p=0.8，計(jì)算后0.02%,也就是說相似性為0.8的兩個(gè)元素，0.02%的概率是落著一個(gè)桶里面，概率很低，影響召回率。
這時(shí)候根據(jù)實(shí)際需要來確定r的大小，比如 r=2,m=8，
p=0.3時(shí)為53%概率落在一個(gè)桶
p=0.5時(shí)為90%概率落在一個(gè)桶
p=0.7時(shí)為99.6%概率裸著一個(gè)桶。
通過這個(gè)方法平衡計(jì)算復(fù)雜度和項(xiàng)目需求
?
整體來看,minhash主要是用來降維，且為LSH提供的條件。
?
simhash和minhash有很大的相似性，都是lsh的一個(gè)方法，但是其牛逼的地方在于，simhash值之間的海明距離可以刻畫其相似程度。
simhash本身也是用來降維以及很方便的利用LSH思想。
?
具體的simhash的介紹很多，不做介紹。
假設(shè)simhash的結(jié)果是16bit的0-1串作為特征 ，假設(shè)有最多k個(gè)bit不同，我們認(rèn)為其相似，那么需要將其劃分成k+1個(gè)band
比如 k=3,我們需要?jiǎng)澐殖?個(gè)band，這個(gè)比較容易理解，也有很完整的證明。
?
整體來看，lsh是來解相似性計(jì)算的規(guī)模問題，避免計(jì)算所有pair，只計(jì)算可能相似的pair。
基本的思路就是劃分band，band的大小和計(jì)算復(fù)雜度以及召回率有很大的關(guān)系。
針對(duì)基于jaccard距離的問題，直接基于在原始特征上，無法劃分band，因?yàn)榫S度過高以及數(shù)據(jù)很稀疏，效果不好。
這時(shí)候，就需要將數(shù)據(jù)降維，便于高效處理。
minhash、simhash從不同的角度解決這個(gè)問題。
來源：http://blog.csdn.net/hxxiaopei/article/details/7977248?minHash(最小哈希)和LSH(局部敏感哈希)
? ? ? ? ?在數(shù)據(jù)挖掘中，有一個(gè)比較基本的問題，就是比較兩個(gè)集合的相似度。關(guān)于這個(gè)問題，最笨的方法就是用一個(gè)兩重循環(huán)來遍歷這兩個(gè)集合中的所有元素，進(jìn)而統(tǒng)計(jì)這兩個(gè)集合中相同元素的個(gè)數(shù)。但是，當(dāng)這兩個(gè)集合里的元素?cái)?shù)量非常龐大時(shí)，同時(shí)又有很多個(gè)集合需要判斷兩兩之間的相似度時(shí)，這種方法就呵呵了，對(duì)內(nèi)存和時(shí)間的消耗都非常大。因此，為了解決這個(gè)問題，數(shù)據(jù)挖掘中有另一個(gè)方法。
Jaccard相似度
?????????在介紹具體算法之前，我們首先來了解一個(gè)概念：Jaccard相似度。
???????? Jaccard相似度是用來描述兩個(gè)集合間的相似度的，其計(jì)算方法如下（假設(shè)有兩個(gè)集合A，B）：，也就是A與B交集的元素個(gè)數(shù)除以A與B并集的元素個(gè)數(shù)；為了書寫方便，下面的討論中我們將集合A和B的Jaccard相似度記為SIM(A,B)；
例如：上圖中有兩個(gè)集合A，B；A中有4個(gè)元素，B中有5個(gè)元素；A，B的交集元素個(gè)數(shù)為2，并集元素個(gè)數(shù)為7，所以SIM(A,B) = 2 / 7；
k-Shingle
? ? ???假如我們把一整篇文章看成一個(gè)長的字符串，那么k-shingle就是這篇文檔中長度為k的任意字符子串。所以，一篇文章就是很多個(gè)不同的k-shingle的集合。
? ? ? ? 例如：現(xiàn)在我們有一篇很短的文章，文章內(nèi)容為abcdabd，令k=2，那么這篇文章中所有的2-shingle組成的集合為{ab,bc,cd,da,bd}，需要注意的是，ab在文章中出現(xiàn)了兩次，但是在集合中只出現(xiàn)一次，這是因?yàn)榧现胁荒苡邢嗤脑亍?/span>
???????? 盡管用k-shingle的方式來表示每篇文章，然后再通過判斷每篇文章中shingle集合的相同元素的數(shù)量，就可以得出文章的相似度；但是，一篇文章得到的shingle集合的元素個(gè)數(shù)是很多的。假定k=4，那么每個(gè)shingle中就會(huì)有4個(gè)字符，存在內(nèi)存中就至少需要4個(gè)字節(jié)；那么要以這種方式存下一篇文章的所有shingle，需要的內(nèi)存空間大概是原文檔大小的4倍（假設(shè)原文檔大小為100K，那么存下這篇文檔的所有shingle則需要400K），這是因?yàn)樵臋n中的每個(gè)字符串都會(huì)出現(xiàn)在4個(gè)shingle中（除了開頭和結(jié)尾那幾個(gè)字符）。因此，以shingle的方式來存文章會(huì)消耗大量的內(nèi)存。
???????? 接下來，我們需要把上面的shingle集合替換成規(guī)模小很多的“簽名”集合。這樣，就可以通過比較兩篇文章的簽名集合的相似度，就能夠估計(jì)shingle的相似度了。這樣得到的相似度只是原來相似度的近似值。
???????? 在介紹簽名集合之前，我們先來看下如何將集合表示成其特征矩陣。
特征矩陣
特征矩陣的一列就對(duì)應(yīng)一個(gè)集合，所有的行加起來就是所有集合元素的全集，如果集合中有那個(gè)元素，則矩陣中的對(duì)應(yīng)位置為1，否則為0（好吧，講的不是很清楚，還是直接上例子吧）：
假設(shè)現(xiàn)在有4個(gè)集合，分別為S1，S2，S3，S4；其中，S1={a,d}, S2={c}, S3={b,d,e}, S4={a,c,d}，所以全集U={a,b,c,d,e}
那么這4個(gè)集合的特征矩陣為：
其中第一行和第一列不是特征矩陣的一部分，只是為了便于理解而寫上的。
最小哈希
構(gòu)建集合的特征矩陣是為了計(jì)算集合的最小哈希。
???????? 為了計(jì)算最小哈希，首先對(duì)特征矩陣的行進(jìn)行打亂（也即隨機(jī)調(diào)換行與行之間的位置），這個(gè)打亂是隨機(jī)的。然后某一列的最小哈希值就等于打亂后的這一列第一個(gè)值為1的行所在的行號(hào)（不明白的直接看例子），行號(hào)從0開始。
例如，定義一個(gè)最小哈希函數(shù)h，然后對(duì)上面的特征矩陣進(jìn)行行打亂，原來第一列的順序?yàn)閍bcde，打亂后為beadc，則新的特征矩陣為：
對(duì)于列S1，從這一列的第一行往下走，直到遇到第一個(gè)1，所在的行號(hào)則為這一列的最小哈希值。所以這4列的最小哈希值依次為h(S1) = 2, h(S2) = 4, h(S3) = 0, h(S4) = 2.
最小哈希與Jaccard相似度
???????? 在經(jīng)過行打亂后的兩個(gè)集合計(jì)算得到的最小哈希值相等的概率等于這兩個(gè)集合的Jaccard相似度。簡單推導(dǎo)如下：
???????? 假設(shè)只考慮集合S1和S2，那么這兩列所在的行有下面三種類型：
1.??????這一行的S1和S2的值都為1（即兩列值都為1），記為X類；
2.??????這一行只有一個(gè)值為1，另一個(gè)值為0，記為Y類；
3.??????這一行兩列的值都為0，記為Z類。
假設(shè)屬于X類的行有x個(gè)，屬于Y類的行有y個(gè)，所以S1和S2交集的元素個(gè)數(shù)為x，并集的元素個(gè)數(shù)為x+y，所以SIM(S1,S2) = x / (x+y)。注：SIM(S1,S2)就是集合S1和S2的Jaccard相似度。
接下來計(jì)算最小哈希h(S1) = h(S2)的概率。經(jīng)過行打亂之后，對(duì)特征矩陣從上往下掃描，在碰到Y(jié)類行之前碰到X類行的概率是x / (x+y)；又因?yàn)閄類行中h(S1)=h(S2)，所以h(S1)=h(S2)的概率為x/(x+y)，也就是這兩個(gè)集合Jaccard相似度。
最小哈希簽名
???????? 上面是用一個(gè)行打亂來處理特征矩陣，然后就可以得到每個(gè)集合最小哈希值，這樣多個(gè)集合就會(huì)有多個(gè)最小哈希值，這些值就可以組成一列。當(dāng)我們用多個(gè)隨機(jī)行打亂（假設(shè)為n個(gè)，分別為h1,h2…h(huán)n）來處理特征矩陣時(shí)，然后分別計(jì)算打亂后的這n個(gè)矩陣的最小哈希值；這樣，對(duì)于集合S，就會(huì)有n個(gè)最小哈希值，這n個(gè)哈希值就可以組成一個(gè)列向量，為[h1(S), h2(S)…h(huán)n(S)]；因此對(duì)于一個(gè)集合，經(jīng)過上面的處理后，就能得到一個(gè)列向量；如果有m個(gè)集合，就會(huì)有m個(gè)列向量，每個(gè)列向量中有n個(gè)元素。把這m個(gè)列向量組成一個(gè)矩陣，這個(gè)矩陣就是特征矩陣的簽名矩陣；這個(gè)簽名矩陣的列數(shù)與特征矩陣相同，但行數(shù)為n，也即哈希函數(shù)的個(gè)數(shù)。通常來說，n都會(huì)比特征矩陣的行數(shù)要小很多，所以簽名矩陣就會(huì)比特征矩陣小很多。
最小簽名的計(jì)算
?????????? 其實(shí)得到上面的簽名矩陣之后，我們就可以用簽名矩陣中列與列之間的相似度來計(jì)算集合間的Jaccard相似度了；但是這樣會(huì)帶來一個(gè)問題，就是當(dāng)一個(gè)特征矩陣很大時(shí)（假設(shè)有上億行），那么對(duì)其進(jìn)行行打亂是非常耗時(shí)，更要命的是還要進(jìn)行多次行打亂。?????????????? 為了解決這個(gè)問題，可以通過一些隨機(jī)哈希函數(shù)來模擬行打亂的效果。具體做法如下:
?????????? 假設(shè)我們要進(jìn)行n次行打亂，則為了模擬這個(gè)效果，我們選用n個(gè)隨機(jī)哈希函數(shù)h1,h2,h3…h(huán)n（注意，這里的h跟上面的h不是同一個(gè)哈希函數(shù)，只是為了方便，就不用其他字母了）。處理過程如下：
令SIG(i,c)表示簽名矩陣中第i個(gè)哈希函數(shù)在第c列上的元素。開始時(shí)，將所有的SIG(i,c)初始化為Inf(無窮大)，然后對(duì)第r行進(jìn)行如下處理：
1.??????計(jì)算h1(r), h2(r)…h(huán)n(r)；
2.??????對(duì)于每一列c:
a)????????如果c所在的第r行為0，則什么都不做；
b)????????如果c所在的第r行為1，則對(duì)于每個(gè)i=1,2…n，將SIG(i,c)置為原來的SIG(i,c)和hi(r)之間的最小值。
（看不懂的直接看例子吧，這里講的比較晦澀）
例如，考慮上面的特征矩陣，將abcde換成對(duì)應(yīng)的行號(hào)，在后面加上兩個(gè)哈希函數(shù)，其中h1(x)=(x+1) mod 5，h2(x) = (3*x+1) mod 5，注意這里x指的是行號(hào)：
接下來計(jì)算簽名矩陣。一開始時(shí)，全部初始化為Inf:
接著看特征矩陣中的第0行；這時(shí)S2和S3的值為0，所以無需改動(dòng)；S1和S4的值為1，需改動(dòng)。h1= 1，h2= 1。1比Inf小，所以需把S1和S4這兩個(gè)位置對(duì)應(yīng)的值替換掉，替換后效果如下：
接著看第1行；只有S3的值為1；此時(shí)h1= 2，h2= 4；對(duì)S3那一列進(jìn)行替換，得到：
接著看第2行；S2和S4的值為1；h1=3，h2=2；因?yàn)楹灻仃嘢4那一列的兩個(gè)值都為1，比3和2小，所以只需替換S2那一列：
接著看第3行；S1，S3和S4的值都為1，h1=4, h2= 0；替換后效果如下：
接著看第4行；S3值為1，h1=0, h2= 3，最終效果如下：
這樣，所有的行都被遍歷一次了，最終得到的簽名矩陣如下：
基于這個(gè)簽名矩陣，我們就可以估計(jì)原始集合之間的Jaccard相似度了。由于S2和S4對(duì)應(yīng)的列向量完全一樣，所以可以估計(jì)SIM(S1，S4)=1;同理可得SIM(S1，S3) = 0.5;
局部敏感哈希算法（LSH）
???????? 通過上面的方法處理過后，一篇文檔可以用一個(gè)很小的簽名矩陣來表示，節(jié)省下很多內(nèi)存空間；但是，還有一個(gè)問題沒有解決，那就是如果有很多篇文檔，那么如果要找出相似度很高的文檔，其中一種辦法就是先計(jì)算出所有文檔的簽名矩陣，然后依次兩兩比較簽名矩陣的相似度；這樣做的缺點(diǎn)是當(dāng)文檔數(shù)量很多時(shí)，要比較的次數(shù)會(huì)非常大。那么我們可不可以只比較那些相似度可能會(huì)很高的文檔，而直接忽略過那些相似度很低的文檔。接下來我們就討論這個(gè)問題的解決方法。
???????? 首先，我們可以通過上面的方法得到一個(gè)簽名矩陣，然后把這個(gè)矩陣劃分成b個(gè)行條(band)，每個(gè)行條由r行組成。對(duì)于每個(gè)行條，存在一個(gè)哈希函數(shù)能夠?qū)⑿袟l中的每r個(gè)整數(shù)組成的列向量（行條中的每一列）映射到某個(gè)桶中。可以對(duì)所有行條使用相同的哈希函數(shù)，但是對(duì)于每個(gè)行條我們都使用一個(gè)獨(dú)立的桶數(shù)組，因此即便是不同行條中的相同列向量，也不會(huì)被哈希到同一個(gè)桶中。這樣，只要兩個(gè)集合在某個(gè)行條中有落在相同桶的兩列，這兩個(gè)集合就被認(rèn)為可能相似度比較高，作為后續(xù)計(jì)算的候選對(duì)；而那些在所有行條中都不落在同一個(gè)桶中的兩列，就會(huì)被認(rèn)為相似度不會(huì)很高，而被直接忽略。下面直接看一個(gè)例子：
例如，現(xiàn)在有一個(gè)12行簽名矩陣，把這個(gè)矩陣分為4個(gè)行條，每個(gè)行條有3行；為了方便，這里只寫出行條1的內(nèi)容。
可以看出，行條1中第2列和第4列的內(nèi)容都為[0,2,1]，所以這兩列會(huì)落在行條1下的相同桶中，因此無論在剩下的3個(gè)行條中這兩列是否有落在相同桶中，這兩個(gè)集合都會(huì)成為候選對(duì)。在行條1中不相等的兩列還有另外的3次機(jī)會(huì)成為候選對(duì)，因?yàn)樗麄冎恍柙谑Ｏ碌?個(gè)行條中有一次相等即可。
???????? 經(jīng)過上面的處理后，我們就找出了相似度可能會(huì)很高的一些候選對(duì)，接下來我們只需對(duì)這些候選隊(duì)進(jìn)行比較就可以了，而直接忽略那些不是候選對(duì)的集合。這個(gè)方法適合用來計(jì)算相似度超過某個(gè)值的文檔的相似度，而不適用于計(jì)算所有文檔的相似度，因?yàn)槟切┫嗨贫瓤赡芎艿偷奈臋n已經(jīng)被直接忽略了。
文章來源：http://blog.csdn.net/liujan511536/article/details/47729721
聚類之minhash
最小哈希法
最小哈希原理介紹
最小哈希：
? | S1 | S2 | S3 |
A | 1 | 0 | 0 |
B | 0 | 1 | 0 |
C | 0 | 0 | 0 |
D | 1 | 0 | 1 |
行的隨機(jī)排列轉(zhuǎn)換（也稱置換運(yùn)算）
? | S1 | S2 | S3 |
B | 0 | 1 | 0 |
D | 1 | 0 | 1 |
A | 1 | 0 | 0 |
C | 0 | 0 | 0 |
哈希值：排列轉(zhuǎn)換后的行排列次序下第一個(gè)列值為1的行的行號(hào)，例如h(S1)=D，h(S2)=B
兩個(gè)集合經(jīng)隨機(jī)排列之后得到的兩個(gè)最小哈希值相等的概率等于這兩個(gè)集合的Jaccard相似度。
問題：
對(duì)于上百萬甚至數(shù)十億的行選擇一個(gè)隨機(jī)排列轉(zhuǎn)換極其消耗時(shí)間，怎么辦？
a) ?如果c在第r行為0，則什么也不做；
b)?? 否則，如果c在第r行為1，那么對(duì)于每個(gè)i=1,2，…，n，將SIG（i,c）置為原來的SIG（i，c）和h(r)中的較小值
?
行 | S1 | S2 | S3 | S4 | x+1 mod 5 | 3x+1 mod 5 |
0 | 1 | 0 | 0 | 1 | 1 | 1 |
1 | 0 | 0 | 1 | 0 | 2 | 4 |
2 | 0 | 1 | 0 | 1 | 3 | 2 |
3 | 1 | 0 | 1 | 1 | 4 | 0 |
4 | 0 | 0 | 1 | 0 | 0 | 3 |
計(jì)算最小哈希簽名矩陣：
? | S1 | S2 | S3 | S4 |
h1 | 1 | 3 | 0 | 1 |
h2 | 0 | 2 | 0 | 0 |
計(jì)算Jaccard相似度：
SIM(S1，S4)=1.0；SIM(S1，S3)=1/3；SIM(S1，S2)=0
真實(shí)SIM(S1，S4)=2/3；SIM(S1，S3)=1/4；SIM(S1，S2)=0
?
相關(guān)論文：
1.《Google News Personalization: Scalable Online Collaborative Filtering》
根據(jù)用戶的歷史點(diǎn)擊數(shù)據(jù)，進(jìn)行新聞推薦；采用最小哈希聚類的協(xié)同過濾算法
2.《The Link-Prediction Problem for Social Networks》
比較社交網(wǎng)絡(luò)鏈接預(yù)測(cè)問題的各種算法
計(jì)算好友相似度的流程：
- 找到N個(gè)哈希函數(shù)，對(duì)每個(gè)用戶好友集合生成一組Minhash（N個(gè)）
- 對(duì)于一個(gè)用戶，按Minhash相同個(gè)數(shù)做排序，給出推薦候選集
- 計(jì)算用戶跟被備選集的Jaccard Index
- 按Jaccard結(jié)果排序，給出TopN進(jìn)行推薦
哈希函數(shù)生成和哈希值計(jì)算：
- numHashFunctions--預(yù)設(shè)生成hash函數(shù)的個(gè)數(shù)（假定為10個(gè)）
- for (int i = 0; i < numHashFunctions; i++) {for (Vector.Element ele : featureVector) {int value = (int) ele.get();bytesToHash[0] = (byte) (value >> 24);bytesToHash[1] = (byte) (value >> 16);bytesToHash[2] = (byte) (value >> 8);bytesToHash[3] = (byte) value;int hashIndex = hashFunction[i].hash(bytesToHash); //計(jì)算哈希函數(shù)值//只保留最小哈希值if (minHashValues[i] > hashIndex) {minHashValues[i] = hashIndex;}}}
?
- Random random = new MersenneTwisterRNG(new FastRandomSeedGenerator());
- org.uncommons.maths.random.MersenneTwisterRNG.MersenneTwisterRNG(SeedGeneratorseedGenerator)
- Mersenne Twister（馬特賽特旋轉(zhuǎn)演算法），是偽隨機(jī)數(shù)發(fā)生器之一，其主要作用是生成偽隨機(jī)數(shù)。
Mersenne Twister算法的原理：Mersenne Twister算法是利用線性反饋移位寄存器(LFSR)產(chǎn)生隨機(jī)數(shù)的，LFSR的反饋函數(shù)是寄存器中某些位的簡單異或，這些位也稱之為抽頭序列。一個(gè)n位的LFSR能夠在重復(fù)之前產(chǎn)生2^n-1位長的偽隨機(jī)序列。只有具有一定抽頭序列的LFSR才能通過所有2^n-1個(gè)內(nèi)部狀態(tài)，產(chǎn)生2^n - 1位長的偽隨機(jī)序列，這個(gè)輸出的序列就稱之為m序列。為了使LFSR成為最大周期的LFSR，由抽頭序列加上常數(shù)1形成的多項(xiàng)式必須是本原多項(xiàng)式。一個(gè)n階本原多項(xiàng)式是不可約多項(xiàng)式，它能整除x^(2*n-1)+1而不能整除x^d+1，其中d能整除2^n-1。例如(32,7,5,3,2,1,0)是指本原多項(xiàng)式x^32+x^7+x^5+x^3+x^2+x+1，把它轉(zhuǎn)化為最大周期LFSR就是在LFSR第32，7，5，2，1位抽頭。利用上述兩種方法產(chǎn)生周期為m的偽隨機(jī)序列后，只需要將產(chǎn)生的偽隨機(jī)序列除以序列的周期，就可以得到(0，1)上均勻分布的偽隨機(jī)序列了。Mersenne Twister有以下優(yōu)點(diǎn)：隨機(jī)性好，在計(jì)算機(jī)上容易實(shí)現(xiàn)，占用內(nèi)存較少(mt19937的C程式碼執(zhí)行僅需624個(gè)字的工作區(qū)域)，產(chǎn)生隨機(jī)數(shù)的速度快、周期長，可達(dá)到2^19937-1，且具有623維均勻分布的性質(zhì)，對(duì)于一般的應(yīng)用來說，足夠大了，序列關(guān)聯(lián)比較小，能通過很多隨機(jī)性測(cè)試。
- MAX_INT_SMALLER_TWIN_PRIME = 2147482949；為什么選這個(gè)值？
- 它是整型范圍內(nèi)最大孿生素?cái)?shù)（相差為2的兩個(gè)數(shù)都是質(zhì)數(shù)的情況）的較小值；哈希用素?cái)?shù)取模沖突小
- seedA、seedB、seedC是采用MersenneTwisterRNG隨機(jī)生成器生成的0~11均勻分布的隨機(jī)數(shù)
- 第一種：LinearHash
@Overridepublic int hash(byte[] bytes) {long hashValue = 31;for (long byteVal : bytes) {hashValue *= seedA * byteVal;hashValue += seedB;}return Math.abs((int) (hashValue % RandomUtils.MAX_INT_SMALLER_TWIN_PRIME));} - 第二種:PolynomialHash @Overridepublic int hash(byte[] bytes) {long hashValue = 31;for (long byteVal : bytes) {hashValue *= seedA * (byteVal >> 4);hashValue += seedB * byteVal + seedC;}return Math.abs((int) (hashValue % RandomUtils.MAX_INT_SMALLER_TWIN_PRIME));}
- 第三種：MurmurHashWrapper@Overridepublic int hash(byte[] bytes) {long hashValue = MurmurHash.hash64A(bytes, seed);return Math.abs((int) (hashValue % RandomUtils.MAX_INT_SMALLER_TWIN_PRIME));}
- 第四種:MurmurHash3Wrapper@Overridepublic int hash(byte[] bytes) {long hashValue = MurmurHash3.murmurhash3_x86_32(bytes, 0, bytes.length, seed);return Math.abs((int) (hashValue % RandomUtils.MAX_INT_SMALLER_TWIN_PRIME));}?
來源：http://www.cnblogs.com/shipengzhi/articles/2826209.html
simhash算法原理及實(shí)現(xiàn)
simhash是google用來處理海量文本去重的算法。 google出品，你懂的。 simhash最牛逼的一點(diǎn)就是將一個(gè)文檔，最后轉(zhuǎn)換成一個(gè)64位的字節(jié)，暫且稱之為特征字，然后判斷重復(fù)只需要判斷他們的特征字的距離是不是<n（根據(jù)經(jīng)驗(yàn)這個(gè)n一般取值為3），就可以判斷兩個(gè)文檔是否相似。
原理
simhash值的生成圖解如下
大概花三分鐘看懂這個(gè)圖就差不多怎么實(shí)現(xiàn)這個(gè)simhash算法了。特別簡單。谷歌出品嘛，簡單實(shí)用。
算法過程大概如下：
到此，如何從一個(gè)doc到一個(gè)simhash值的過程已經(jīng)講明白了。 但是還有一個(gè)重要的部分沒講，
『simhash值的海明距離計(jì)算』
二進(jìn)制串A 和 二進(jìn)制串B 的海明距離 就是?A xor B?后二進(jìn)制中1的個(gè)數(shù)。
舉例如下：
A = 100111; B = 101010; hamming_distance(A, B) = count_1(A xor B) = count_1(001101) = 3;當(dāng)我們算出所有doc的simhash值之后，需要計(jì)算doc A和doc B之間是否相似的條件是：
A和B的海明距離是否小于等于n，這個(gè)n值根據(jù)經(jīng)驗(yàn)一般取值為3,
simhash本質(zhì)上是局部敏感性的hash，和md5之類的不一樣。 正因?yàn)樗木植棵舾行?#xff0c;所以我們可以使用海明距離來衡量simhash值的相似度。
『高效計(jì)算二進(jìn)制序列中1的個(gè)數(shù)』
/* src/Simhasher.hpp */ bool isEqual(uint64_t lhs, uint64_t rhs, unsigned short n = 3) {unsigned short cnt = 0;lhs ^= rhs;while(lhs && cnt <= n){lhs &= lhs - 1;cnt++;}if(cnt <= n){return true;}return false; }由上式這個(gè)函數(shù)來計(jì)算的話，時(shí)間復(fù)雜度是 O(n); 這里的n默認(rèn)取值為3。由此可見還是蠻高效的。
『計(jì)算二進(jìn)制序列中1的個(gè)數(shù)之O(1)算法實(shí)現(xiàn)』
感謝?@SCatWang?的評(píng)論分享：
感謝您做的simhash庫，感覺會(huì)很方便。 有關(guān)求二進(jìn)制中1的個(gè)數(shù)，其實(shí)有各種O(1)的實(shí)現(xiàn)。可以參考這個(gè)地方：http://stackoverflow.com/a/14682688
simhash 實(shí)現(xiàn)的工程項(xiàng)目
- C++ 版本?simhash
- Golang 版本?gosimhash
主要是針對(duì)中文文檔，也就是此項(xiàng)目進(jìn)行simhash之前同時(shí)還進(jìn)行了分詞和關(guān)鍵詞的抽取。
對(duì)比其他算法
『百度的去重算法』
百度的去重算法最簡單，就是直接找出此文章的最長的n句話，做一遍hash簽名。n一般取3。 工程實(shí)現(xiàn)巨簡單，據(jù)說準(zhǔn)確率和召回率都能到達(dá)80%以上。
『shingle算法』
shingle原理略復(fù)雜，不細(xì)說。 shingle算法我認(rèn)為過于學(xué)院派，對(duì)于工程實(shí)現(xiàn)不夠友好，速度太慢，基本上無法處理海量數(shù)據(jù)。
『其他算法』
具體看微博上的討論
參考
- Similarity estimation techniques from rounding algorithms
- simhash與Google的網(wǎng)頁去重
- 海量數(shù)據(jù)相似度計(jì)算之simhash和海明距離
來源：http://yanyiwu.com/work/2014/01/30/simhash-shi-xian-xiang-jie.html
實(shí)現(xiàn)文本相似度算法（余弦定理）
? ? ? ?最近由于工作項(xiàng)目，需要判斷兩個(gè)txt文本是否相似，于是開始在網(wǎng)上找資料研究，因?yàn)樵诔绦蛑袝?huì)把文本轉(zhuǎn)換成String再做比較，所以最開始找到了這篇關(guān)于?距離編輯算法?Blog寫的非常好，受益匪淺。
????? ?于是我決定把它用到項(xiàng)目中，來判斷兩個(gè)文本的相似度。但后來實(shí)際操作發(fā)現(xiàn)有一些問題：直接說就是查詢一本書中的相似章節(jié)花了我7、8分鐘；這是我不能接受……
????? ?于是停下來仔細(xì)分析發(fā)現(xiàn)，這種算法在此項(xiàng)目中不是特別適用，由于要判斷一本書中是否有相同章節(jié)，所以每兩個(gè)章節(jié)之間都要比較，若一本書書有x章的話，這里需對(duì)比x(x-1)/2次；而此算法采用矩陣的方式，計(jì)算兩個(gè)字符串之間的變化步驟，會(huì)遍歷兩個(gè)文本中的每一個(gè)字符兩兩比較，可以推斷出時(shí)間復(fù)雜度至少為?document1.length × document2.length，我所比較的章節(jié)字?jǐn)?shù)平均在幾千～一萬字；這樣計(jì)算實(shí)在要了老命。
????? ?想到Lucene中的評(píng)分機(jī)制，也是算一個(gè)相似度的問題，不過它采用的是計(jì)算向量間的夾角（余弦公式），在google黑板報(bào)中的：數(shù)學(xué)之美（余弦定理和新聞分類）?也有說明，可以通過余弦定理來判斷相似度；于是決定自己動(dòng)手試試。
????? ?首相選擇向量的模型：在以字為向量還是以詞為向量的問題上，糾結(jié)了一會(huì)；后來還是覺得用字，雖然詞更為準(zhǔn)確，但分詞卻需要增加額外的復(fù)雜度，并且此項(xiàng)目要求速度，準(zhǔn)確率可以放低，于是還是選擇字為向量。
????? ?然后每個(gè)字在章節(jié)中出現(xiàn)的次數(shù)，便是以此字向量的值。現(xiàn)在我們假設(shè)：
????? ?章節(jié)1中出現(xiàn)的字為：Z1c1,Z1c2,Z1c3,Z1c4……Z1cn；它們?cè)谡鹿?jié)中的個(gè)數(shù)為：Z1n1,Z1n2,Z1n3……Z1nm；
???????章節(jié)2中出現(xiàn)的字為：Z2c1,Z2c2,Z2c3,Z2c4……Z2cn；它們?cè)谡鹿?jié)中的個(gè)數(shù)為：Z2n1,Z2n2,Z2n3……Z2nm；
????? ?其中，Z1c1和Z2c1表示兩個(gè)文本中同一個(gè)字，Z1n1和Z2n1是它們分別對(duì)應(yīng)的個(gè)數(shù)，
???????最后我們的相似度可以這么計(jì)算：
????? ?程序?qū)崿F(xiàn)如下：（若有可優(yōu)化或更好的實(shí)現(xiàn)請(qǐng)不吝賜教）
public class CosineSimilarAlgorithm {public static double getSimilarity(String doc1, String doc2) {if (doc1 != null && doc1.trim().length() > 0 && doc2 != null&& doc2.trim().length() > 0) {Map<Integer, int[]> AlgorithmMap = new HashMap<Integer, int[]>();//將兩個(gè)字符串中的中文字符以及出現(xiàn)的總數(shù)封裝到，AlgorithmMap中for (int i = 0; i < doc1.length(); i++) {char d1 = doc1.charAt(i);if(isHanZi(d1)){int charIndex = getGB2312Id(d1);if(charIndex != -1){int[] fq = AlgorithmMap.get(charIndex);if(fq != null && fq.length == 2){fq[0]++;}else {fq = new int[2];fq[0] = 1;fq[1] = 0;AlgorithmMap.put(charIndex, fq);}}}}for (int i = 0; i < doc2.length(); i++) {char d2 = doc2.charAt(i);if(isHanZi(d2)){int charIndex = getGB2312Id(d2);if(charIndex != -1){int[] fq = AlgorithmMap.get(charIndex);if(fq != null && fq.length == 2){fq[1]++;}else {fq = new int[2];fq[0] = 0;fq[1] = 1;AlgorithmMap.put(charIndex, fq);}}}}Iterator<Integer> iterator = AlgorithmMap.keySet().iterator();double sqdoc1 = 0;double sqdoc2 = 0;double denominator = 0; while(iterator.hasNext()){int[] c = AlgorithmMap.get(iterator.next());denominator += c[0]*c[1];sqdoc1 += c[0]*c[0];sqdoc2 += c[1]*c[1];}return denominator / Math.sqrt(sqdoc1*sqdoc2);} else {throw new NullPointerException(" the Document is null or have not cahrs!!");}}public static boolean isHanZi(char ch) {// 判斷是否漢字return (ch >= 0x4E00 && ch <= 0x9FA5);}/*** 根據(jù)輸入的Unicode字符，獲取它的GB2312編碼或者ascii編碼，* * @param ch* 輸入的GB2312中文字符或者ASCII字符(128個(gè))* @return ch在GB2312中的位置，-1表示該字符不認(rèn)識(shí)*/public static short getGB2312Id(char ch) {try {byte[] buffer = Character.toString(ch).getBytes("GB2312");if (buffer.length != 2) {// 正常情況下buffer應(yīng)該是兩個(gè)字節(jié)，否則說明ch不屬于GB2312編碼，故返回'?'，此時(shí)說明不認(rèn)識(shí)該字符return -1;}int b0 = (int) (buffer[0] & 0x0FF) - 161; // 編碼從A1開始，因此減去0xA1=161int b1 = (int) (buffer[1] & 0x0FF) - 161; // 第一個(gè)字符和最后一個(gè)字符沒有漢字，因此每個(gè)區(qū)只收16*6-2=94個(gè)漢字return (short) (b0 * 94 + b1);} catch (UnsupportedEncodingException e) {e.printStackTrace();}return -1;} } ????? ?程序中做了兩小的改進(jìn)，以加快效率：
????? ?1. 只將漢字作為向量，其他的如標(biāo)點(diǎn)，數(shù)字等符號(hào)不處理；2. 在HashMap中存放漢字和其在文本中對(duì)于的個(gè)數(shù)時(shí)，先將單個(gè)漢字通過GB2312編碼轉(zhuǎn)換成數(shù)字，再存放。
????? ?最后寫了個(gè)測(cè)試，根據(jù)兩種不同的算法對(duì)比下時(shí)間，下面是測(cè)試結(jié)果：
????? ?余弦定理算法：doc1 與 doc2 相似度為：0.9954971, 耗時(shí)：22mm
????? ?距離編輯算法：doc1 與 doc2 相似度為：0.99425095, 耗時(shí)：322mm
????? ?可見效率有明顯提高，算法復(fù)雜度大致為：document1.length + document2.length。
? ? ? ?
文章來源：?http://my.oschina.net/BreathL/blog/42477
PHP實(shí)現(xiàn)余弦相似度算法
上一次，我用TF-IDF算法自動(dòng)提取關(guān)鍵詞。
今天，我們?cè)賮硌芯苛硪粋€(gè)相關(guān)的問題。有些時(shí)候，除了找到關(guān)鍵詞，我們還希望找到與原文章相似的其他文章。比如，"Google新聞"在主新聞下方，還提供多條相似的新聞。
為了找出相似的文章，需要用到"余弦相似性"（cosine similiarity）。下面，我舉一個(gè)例子來說明，什么是"余弦相似性"。
為了簡單起見，我們先從句子著手。
句子A：我喜歡看電視，不喜歡看電影。
句子B：我不喜歡看電視，也不喜歡看電影。
請(qǐng)問怎樣才能計(jì)算上面兩句話的相似程度？
基本思路是：如果這兩句話的用詞越相似，它們的內(nèi)容就應(yīng)該越相似。因此，可以從詞頻入手，計(jì)算它們的相似程度。
第一步，分詞。
句子A：我/喜歡/看/電視，不/喜歡/看/電影。
句子B：我/不/喜歡/看/電視，也/不/喜歡/看/電影。
第二步，列出所有的詞。
我，喜歡，看，電視，電影，不，也。
第三步，計(jì)算詞頻。
句子A：我 1，喜歡 2，看 2，電視 1，電影 1，不 1，也 0。
句子B：我 1，喜歡 2，看 2，電視 1，電影 1，不 2，也 1。
第四步，寫出詞頻向量。
句子A：[1, 2, 2, 1, 1, 1, 0]
句子B：[1, 2, 2, 1, 1, 2, 1]
到這里，問題就變成了如何計(jì)算這兩個(gè)向量的相似程度。
我們可以把它們想象成空間中的兩條線段，都是從原點(diǎn)（[0, 0, ...]）出發(fā)，指向不同的方向。兩條線段之間形成一個(gè)夾角，如果夾角為0度，意味著方向相同、線段重合；如果夾角為90度，意味著形成直角，方向完全不相似；如果夾角為180度，意味著方向正好相反。因此，我們可以通過夾角的大小，來判斷向量的相似程度。夾角越小，就代表越相似。
以二維空間為例，上圖的a和b是兩個(gè)向量，我們要計(jì)算它們的夾角θ。余弦定理告訴我們，可以用下面的公式求得：
假定a向量是[x1, y1]，b向量是[x2, y2]，那么可以將余弦定理改寫成下面的形式：
數(shù)學(xué)家已經(jīng)證明，余弦的這種計(jì)算方法對(duì)n維向量也成立。假定A和B是兩個(gè)n維向量，A是 [A1, A2, ..., An] ，B是 [B1, B2, ..., Bn] ，則A與B的夾角θ的余弦等于：
使用這個(gè)公式，我們就可以得到，句子A與句子B的夾角的余弦。
余弦值越接近1，就表明夾角越接近0度，也就是兩個(gè)向量越相似，這就叫"余弦相似性"。所以，上面的句子A和句子B是很相似的，事實(shí)上它們的夾角大約為20.3度。
由此，我們就得到了"找出相似文章"的一種算法：
（1）使用TF-IDF算法，找出兩篇文章的關(guān)鍵詞；
（2）每篇文章各取出若干個(gè)關(guān)鍵詞（比如20個(gè)），合并成一個(gè)集合，計(jì)算每篇文章對(duì)于這個(gè)集合中的詞的詞頻（為了避免文章長度的差異，可以使用相對(duì)詞頻）；
（3）生成兩篇文章各自的詞頻向量；
（4）計(jì)算兩個(gè)向量的余弦相似度，值越大就表示越相似。
"余弦相似度"是一種非常有用的算法，只要是計(jì)算兩個(gè)向量的相似程度，都可以采用它。
下面是PHP實(shí)現(xiàn)余弦相似度計(jì)算的算法
<?php /*** 數(shù)據(jù)分析引擎* 分析向量的元素 必須和基準(zhǔn)向量的元素一致，取最大個(gè)數(shù)，分析向量不足元素以0填補(bǔ)。* 求出分析向量與基準(zhǔn)向量的余弦值*/ /*** 獲得向量的模* @param unknown_type $array 傳入分析數(shù)據(jù)的基準(zhǔn)點(diǎn)的N維向量。|eg:array(1,1,1,1,1);*/ function getMarkMod($arrParam){$strModDouble = 0;foreach($arrParam as $val){$strModDouble += $val * $val;}$strMod = sqrt($strModDouble);//是否需要保留小數(shù)點(diǎn)后幾位return $strMod; }/*** 獲取標(biāo)桿的元素個(gè)數(shù)* @param unknown_type $arrParam* @return number*/ function getMarkLenth($arrParam){$intLenth = count($arrParam);return $intLenth; }/*** 對(duì)傳入數(shù)組進(jìn)行索引分配，基準(zhǔn)點(diǎn)的索引必須為k，求夾角的向量索引必須為 'j'.* @param unknown_type $arrParam* @param unknown_type $index* @ruturn $arrBack*/ function handIndex($arrParam, $index = 'k'){foreach($arrParam as $key => $val){$in = $index.$key;$arrBack[$in] = $val;}return $arrBack; }/**** @param unknown_type $arrMark 標(biāo)桿向量數(shù)組（索引被處理過）|array('k0'=>1,'k1'=>2....)* @param unknown_type $arrAnaly 分析向量數(shù)組（索引被處理過）|array('j0'=>1,'j1'=>2....)* @param unknown_type $strMarkMod 標(biāo)桿向量的模* @param unknown_type $intLenth 向量的長度*/ function getCosine($arrMark, $arrAnaly, $strMarkMod ,$intLenth){$strVector = 0;$strCosine = 0;for($i = 0; $i < $intLenth; $i++){$strMarkVal = $arrMark['k'.$i];$strAnalyVal = $arrAnaly['j'.$i];$strVector += $strMarkVal * $strAnalyVal;}$arrAnalyMod = getMarkMod($arrAnaly); //求分析向量的模$strFenzi = $strVector;$strFenMu = $arrAnalyMod * $strMarkMod;$strCosine = $strFenzi / $strFenMu;if(0 !== (int)$strFenMu){$strCosine = $strFenzi / $strFenMu;}return $strCosine; } //基準(zhǔn)點(diǎn)的N維向量 $arrMark = array(1,1,1,1,1); //分析點(diǎn)的N維向量 $arrAnaly = array(1,2,3,4,5); //向量的模 $MarkMod = getMarkMod($arrMark); //向量的長度 $MarkLenth = getMarkLenth($arrMark); //標(biāo)桿向量數(shù)組 $Index1 = handIndex($arrMark,"k"); //分析向量數(shù)組 $Index2 = handIndex($arrAnaly,"j"); //分析向量與基準(zhǔn)向量的余弦值 $Cosine = getCosine($Index1,$Index2,$MarkMod,$MarkLenth); echo "向量的模：".$MarkMod; echo "<br>"; echo "向量的長度：".$MarkLenth; echo "<br>"; echo "標(biāo)桿向量數(shù)組："; print_r($Index1); echo "<br>"; echo "分析向量數(shù)組："; print_r($Index2); echo "<br>"; echo "分析向量與基準(zhǔn)向量的余弦值：".$Cosine; ?>
小潤測(cè)試的demo如上圖
簡單結(jié)論：
標(biāo)題相似性的判斷，一般使用 minhash，內(nèi)容相似性判斷一般使simhash，簡單業(yè)務(wù)可以使用余弦算法。
總結(jié)
以上是生活随笔為你收集整理的[转]文本相似性算法：simhash/minhash/余弦算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 哈工大软件过程与工具
- 下一篇： 如何用 Python 让你的 PPT 数