本篇文章給大家分享的是有關(guān)minhash該如何使用，小編覺(jué)得挺實(shí)用的，因此分享給大家學(xué)習(xí)，希望大家閱讀完這篇文章后可以有所收獲，話(huà)不多說(shuō)，跟著小編一起來(lái)看看吧。

創(chuàng)新互聯(lián)公司是一家專(zhuān)注于成都網(wǎng)站建設(shè)、成都網(wǎng)站設(shè)計(jì)與策劃設(shè)計(jì),市中網(wǎng)站建設(shè)哪家好?創(chuàng)新互聯(lián)公司做網(wǎng)站,專(zhuān)注于網(wǎng)站建設(shè)十余年,網(wǎng)設(shè)計(jì)領(lǐng)域的專(zhuān)業(yè)建站公司;建站業(yè)務(wù)涵蓋:市中等地區(qū)。市中做網(wǎng)站價(jià)格咨詢(xún):028-86922220

在實(shí)際應(yīng)用的過(guò)程中。相似性度量和計(jì)算是很經(jīng)常使用的一個(gè)方法。比如網(wǎng)頁(yè)去重、推斷帖子是否相似、推薦系統(tǒng)衡量物品或者用戶(hù)的相似度等等。當(dāng)數(shù)據(jù)量大的時(shí)候，計(jì)算的時(shí)間和空間復(fù)雜度就會(huì)是一個(gè)很重要的問(wèn)題，比如在推斷相似發(fā)帖的時(shí)候。我們能夠用kmeans來(lái)進(jìn)行聚類(lèi)?？墒琴Y源的消耗是巨大的。所以本文推薦一種方法，minhash+lsh（局部敏感hash），用minhash來(lái)降維。用lsh來(lái)做近似查詢(xún)，下面主要介紹一下minhash。

在介紹minhash之前，先給出相似性的度量方法。

1. 相似性的度量

相似性度量有非常多方法，歐氏距離是比較經(jīng)常使用的。這里我們用一下Jaccard相似性系數(shù)，公式例如以下

計(jì)算方法非常easy。文檔A和文檔B共同擁有的單詞數(shù)除以A和B單詞的集合。比如A={a,b,c,d}，B={c,d,e,f}，那么相似性系數(shù)就是2/6=0.33。

2. minhash

剛才我們知道在求相似度的時(shí)候我們用到了文檔和單詞。通常情況下，我們都會(huì)將文檔和單詞表示成doc-term矩陣的形式，能夠看到term詳細(xì)的是什么對(duì)最后的結(jié)果沒(méi)有不論什么影響。所以我索性用行號(hào)來(lái)代表term，行號(hào)跟term是一一相應(yīng)的。比如

第一行中的S1,、S2、S3表示文檔，第一列的01234表示行號(hào)。也即單詞。其它部分1表示文檔S中有這個(gè)單詞，0表示沒(méi)有這個(gè)單詞，有了這個(gè)集合，我們看一下minhash是怎么做的

隨機(jī)確定一個(gè)順序。比如上面的順序是01234。隨機(jī)確定一個(gè)順序，比如12340。注意這里是隨機(jī)。目的就是不讓最后的結(jié)果受人為的干擾。結(jié)果例如以下

我們看到，行號(hào)是不變的，行號(hào)還是那個(gè)行號(hào)，變化的是矩陣的內(nèi)容。找到排在最前面的1代表這個(gè)文檔，比如S1排在最前面的1行號(hào)為2，那么就用2代表文檔S1，同理，用1代表S2，那么能夠計(jì)算S1和S2的相似性系數(shù)了，1交2除以1并2等于0。

后面會(huì)給出為什么用這樣的方法是合理的證明。我們臨時(shí)先跳過(guò)。能夠想象一下，用一個(gè)單詞來(lái)代表一個(gè)文檔偶然性會(huì)比較大，那么這個(gè)時(shí)候我們的想法可能是，能夠隨機(jī)的產(chǎn)生多次變換，取出多個(gè)單詞來(lái)進(jìn)行比較。這個(gè)時(shí)候問(wèn)題就來(lái)了，在實(shí)際應(yīng)用的過(guò)程中，文檔可能有幾百萬(wàn)，單詞也會(huì)有幾萬(wàn)，對(duì)如此龐大的矩陣做變換時(shí)間和空間的代價(jià)都會(huì)比較大。是不是有別的方法呢，答案是肯定的，我們知道運(yùn)動(dòng)是相對(duì)的。之前是變換矩陣內(nèi)容不變行號(hào)。我們?nèi)缃癫蛔兙仃嚕瑑H僅變換行號(hào)，是不是計(jì)算量少了許多。

所以問(wèn)題轉(zhuǎn)換為怎樣產(chǎn)生隨機(jī)的行號(hào)，我們能夠用hash函數(shù)來(lái)產(chǎn)生行號(hào)的順序，兩個(gè)函數(shù)能夠自定義。最好保證hash后的值均勻。比如x+1mod5，3x+1mod5。我們選用這兩個(gè)hash函數(shù)來(lái)產(chǎn)生行號(hào)的順序?？匆幌挛覀?nèi)缃竦那闆r

我們用h2、h3兩個(gè)hash函數(shù)產(chǎn)生了兩個(gè)行號(hào)順序，那么接下來(lái)就是關(guān)鍵步驟了

比如求文檔s1的值。遍歷s1相應(yīng)的單詞

從第0行到第四行

1. 第0行為1，看一下h2計(jì)算出來(lái)的行號(hào)為1。賦值h2為1（就是行號(hào)）。繼續(xù)遍歷

2. 第1行為0，不關(guān)心，跳過(guò)

3. 第2行為0，不關(guān)心。跳過(guò)

4. 第3行為1， 看一下h2計(jì)算出來(lái)的行號(hào)為4。4大于此時(shí)h2的值，h2的值不變。假設(shè)小于h2此時(shí)的值，將值付給h2

5. 第4行為0。不關(guān)心，跳過(guò)

遍歷完了之后此時(shí)h2的值就是1，能夠看到。我們事實(shí)上在做的就是遍歷矩陣中的值，對(duì)0的不關(guān)心。跳過(guò)。對(duì)1的?？匆幌耯ash函數(shù)產(chǎn)生的行號(hào)，找到行號(hào)最小的值作為h2輸出的值。同理，h3也一樣，最后得到例如以下的矩陣

這個(gè)時(shí)候就能夠計(jì)算s1、s2的相似度了，J=0/3=0

3. 為什么minhash的方法是合理的

問(wèn)題：兩個(gè)集合的隨機(jī)的一個(gè)行排列的minhash值相等的概率和兩個(gè)集合的Jaccard相似度相等

證明例如以下：

兩個(gè)集合。A、B。對(duì)一行來(lái)說(shuō)。他們的狀態(tài)有三種

X：A、B都為1，即表示A、B集合中都有這個(gè)單詞

Y：A、B當(dāng)中一個(gè)為1，當(dāng)中一個(gè)不為1，即一個(gè)有這個(gè)單詞，一個(gè)沒(méi)有

Z：A、B都為0，即表示A、B中都沒(méi)有這個(gè)單詞。

如果有x行為X，y行為Y，z行為z。這是jaccard系數(shù)為x/(x+y)。再看minhash，由于排列是隨機(jī)的，在遇到Y(jié)之前遇到X的概率是x/(x+y)。是不是正好等于jaccard系數(shù)的值。

4. 怎樣進(jìn)行相似查詢(xún)比較

通過(guò)前面的方法。我們將文檔進(jìn)行了壓縮，比如使用了30個(gè)hash函數(shù)。那么就將一篇文檔壓縮成了30位表示。接下來(lái)的問(wèn)題是怎樣進(jìn)行查詢(xún)。

一種思路是：建立倒排，term是一個(gè)單詞，doclist就是擁有這個(gè)單詞的其它文檔。

還有一種思路是：不是建立單個(gè)單詞的倒排，而是建立多個(gè)單詞的聯(lián)合倒排，比如

一篇文檔：通過(guò)前面的方式用30位進(jìn)行了表示，將這30為進(jìn)行分成m個(gè)桶，每桶r個(gè)單詞，即m*r=30，這個(gè)倒排建立的是：term是r個(gè)單詞（或者將這r個(gè)單詞求hashcode），doclist就是擁有這r個(gè)單詞的文檔。

那么這里的問(wèn)題就是。m、r怎樣求解，m等于幾好。r等于幾好。

假設(shè)兩個(gè)文檔相似度為p，那么相應(yīng)位數(shù)相似的概率也是p，那么一個(gè)桶里全然同樣的概率是p^r，不同樣的概率是1-p^r，那么m個(gè)桶都不同樣的概率是(1-p^r)^m。所以至少有一個(gè)桶同樣的概率是1-(1-p^r)^m，我們能夠依據(jù)我們想要的概率p去分配m和r。

最后建立倒排是這種。

桶1——>doc1，doc2，doc3，doc4

桶2——>doc2，doc5，doc9，doc10

索引建立完畢了之后，下一步就是檢索，一篇新的文檔。也要經(jīng)過(guò)全面的步驟，得到對(duì)應(yīng)的桶。比如桶1，桶3，那么接下來(lái)就是用桶1查詢(xún)，得到跟這篇文檔相似的文檔。為了保證確實(shí)相似。還能夠?qū)蜻x文檔計(jì)算一下跟本片文檔的相似度

以上就是minhash該如何使用，小編相信有部分知識(shí)點(diǎn)可能是我們?nèi)粘９ぷ鲿?huì)見(jiàn)到或用到的。希望你能通過(guò)這篇文章學(xué)到更多知識(shí)。更多詳情敬請(qǐng)關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道。