minhash該如何使用

本篇文章給大家分享的是有關minhash該如何使用，小編覺得挺實用的，因此分享給大家學習，希望大家閱讀完這篇文章后可以有所收獲，話不多說，跟著小編一起來看看吧。

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

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

1. 相似性的度量

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

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

2. minhash

剛才我們知道在求相似度的時候我們用到了文檔和單詞。通常情況下，我們都會將文檔和單詞表示成doc-term矩陣的形式，能夠看到term詳細的是什么對最后的結果沒有不論什么影響。所以我索性用行號來代表term，行號跟term是一一相應的。比如

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

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

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

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

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

我們用h2、h3兩個hash函數(shù)產(chǎn)生了兩個行號順序，那么接下來就是關鍵步驟了

比如求文檔s1的值。遍歷s1相應的單詞

從第0行到第四行

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

2. 第1行為0，不關心，跳過

3. 第2行為0，不關心。跳過

4. 第3行為1， 看一下h2計算出來的行號為4。4大于此時h2的值，h2的值不變。假設小于h2此時的值，將值付給h2

5. 第4行為0。不關心，跳過

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

這個時候就能夠計算s1、s2的相似度了，J=0/3=0

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

問題：兩個集合的隨機的一個行排列的minhash值相等的概率和兩個集合的Jaccard相似度相等

證明例如以下：

兩個集合。A、B。對一行來說。他們的狀態(tài)有三種

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

Y：A、B當中一個為1，當中一個不為1，即一個有這個單詞，一個沒有

Z：A、B都為0，即表示A、B中都沒有這個單詞。

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

4. 怎樣進行相似查詢比較

通過前面的方法。我們將文檔進行了壓縮，比如使用了30個hash函數(shù)。那么就將一篇文檔壓縮成了30位表示。接下來的問題是怎樣進行查詢。

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

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

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

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

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

最后建立倒排是這種。

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

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

索引建立完畢了之后，下一步就是檢索，一篇新的文檔。也要經(jīng)過全面的步驟，得到對應的桶。比如桶1，桶3，那么接下來就是用桶1查詢，得到跟這篇文檔相似的文檔。為了保證確實相似。還能夠對候選文檔計算一下跟本片文檔的相似度

以上就是minhash該如何使用，小編相信有部分知識點可能是我們?nèi)粘９ぷ鲿姷交蛴玫降?。希望你能通過這篇文章學到更多知識。更多詳情敬請關注億速云行業(yè)資訊頻道。