接上篇譯文； 1.盡管我們利用minhashing技術將大數據量的文檔壓縮到小數據量的signatures，并且能夠保證文檔對之間的相似度大致不變。但是由于文檔對的數目可能非常的大，我們仍然不能很有效的找到最相似的文檔對。 如果我們的目標是計算每一對文檔對之間的相似度，那么我們就沒有更好的辦法了，或者可以用并行的方法減少運行的時間規模；但是如果我們的目的僅僅是找到的最相似的文檔對或者相似度在某種程度之上的文檔對，這時候我們就可以采用LSH技術（locality-sensitive hashing or near-neighbor search）。 2. ? ?應用于尋找相似文檔的LSH技術 一般來說，我們這樣應用LSH技術：將所有的items（要比較的東西）進行多次的hash，從而能夠將可能相似的文檔hash到同一個bucket中；然后我們會只考慮那些hash到同一個bucket中的items，認為他們組成的item對才有可能是我們要找的item對。 ?這其中就會產生兩個概念，一個是 false positives: 就是指那些本來不相似的item對卻被hash到一個bucket中；另一個是false negatives： 指那些本來相似的items對卻沒有被hash到同一個bucket中。 如何具體使用lsh技術呢？ ?一個比較有效的hashing方法是將signature matrix（由所有文檔的signature組成，每一列存儲一個文檔的signature）分為b個bands，每個band包含r行（相當于將每個文檔的b*r 個signatures分成b組）； 對于每一個band用一個hash函數（輸入是每個文檔的r個signature，相當于將一列考慮為hash的輸入），將每一列的signature hash到一些大數量的bucket中。（我們可以對不同的band使用相同的hash函數，但是不同的band的bucket要放在不同的位置，從而保證不同band中相同的列不會被hash到同樣的bucket中。） 3. 對lsh的banding技術的分析 將設我們有b bands而且每個band有r行。并且假設一個特定的文檔對的jaccard距離是s。 ?從前文的minhash技術的分析（沒有翻譯 o(╯□╰)o）中可以知道該文檔對的任何一行的signature相同的概率是s。 ?然后我們就可以計算著文檔對成為一個候選的文檔對（被hash到同一個bucket中）的概率，過程如下： 在一個特定的band中，該文檔對的所有的signature都相等的概率是 s^r; ?那么不相等的概率就是 1-s^r; 所有的band中，該文檔對的signature都不相等的概率是 (1-s^r)^b; ?該文檔對至少會在一個band中相等的概率就是 1-(1-s^r)^b. 分析： 將b r看作一個常量，可以看出該概率是s的函數而且是一個典型的S型曲線. 該曲線橫軸是 文檔對的相似度； 縱軸為該文檔對被放到一個bucket中成為候選文檔對的概率；兩者之間的關系是一條我們非常熟知s型曲線，對于s型曲線，中間有一段非常陡峭的上升部分，可以將這個部分的橫軸看作相似度的閾值，高于這個相似度的一般以接近于1的概率(具體的概率可以通過前邊的分析計算出來)被分到同一個bucket中，而低于這個相似度閾值的則以接近于0的概率被分到同一個bucket中；而且這個閾值是b,r的函數：s=(1/b)^(1/r)。 ? 這種函數的s型特性就滿足了我們對于LSH技術的要求，即將相似的文檔hash到同一bucket中，而將不相似的文檔hash到不同的bucket中，至于具體的false positive 和false negatives 與具體的b和r取值有關。（這種方法會產生一定的false positives 和 false negatives）
4. ? ? 最后我們總結下如何在大數據量的文檔對中找到相似的文檔對 1) 針對文檔特性選取合適的k值，對每一個文檔進行k-shingle，并對shingle結果映射為整數。 2) 對每個文檔的shingle標簽進行排序。? 3) ?利用前文所述算法，計算每個文檔的signature（signature的長度n的選擇是一個需要tradeoff的量） 4) 選取合適的閾值t， 用來決定相似度多高的文檔對會被放到同一個bucket中作為候選對；然后選取bands：b以及rows：r，使得b*r=n，而且 t ≈ (1/b)^(1/r)。 如果希望false negatives盡量的低，可以選取b r使得t盡量小；如果追求速度，那就是的t盡量大。 5) 利用LSH技術計算出候選文檔對； 并對文檔對的最初的signatures進行檢測，確保其相似度確實在t之上。 6） 最后回到文檔對最原始的字符狀態，進行檢測文檔對是否確實相似。

總結

以上是生活随笔為你收集整理的在大数据中如何寻找相似的文档（shingle， minhash， LSH）（二）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。