大數據集怎麼求彼此相似度？

01-23

我們大概有3000W個文檔，想計算出跟每個文檔最相似的TopN個文檔。已經為每個文檔提取了平均20個關鍵詞並計算了idf值，本來打算用餘弦公式來計算相似度，但是在計算公式的分子時，發現數據量大的驚人（有些詞在幾百萬個文檔中出現了），我們用的MapReduce，產生的中間數據達到800W*800W*5000*21的規模，以至於hdfs都存不下了（2T左右），請問這種情況應該怎麼計算相似度呢？

用WAND演算法，按我們組 @lvhl1983 呂博士的實踐計算，在計算時間和空間消耗上WAND演算法都剛剛的。具體看paper http://www.cis.upenn.edu/~jstoy/cis650/papers/WAND.pdf

先預處理一下

df大於某一閾值的認為是stop words，統統濾掉。

再考慮一下降維

用LDA或PLSA這樣的topic model來生成document-topic模型

我去。。。這個說來話長了。。。佔個位子兩個月後再來更。。。。

1、如果直接求KNN的話，不管用餘弦相似度還是歐氏距離，總是要求3000W的平方次相似度的，這個中間數據2T其實不算多。另外，每一次計算最多只需要兩個文本的40個關鍵詞作為維度，所以維度並不算多。

2、基於HDFS的空間緊張，建議使用LSH（局部敏感哈希）演算法來求KNN，這種演算法的原理是遍歷3000W文檔，為每一個文檔計算特定的哈希值，把可能相似的文檔放到一個桶內。然後第二次遍歷，只需要為每個文檔計算與其可能相似的其他文檔即可，計算量會極大的縮小。

3、除了LSH，還有Min Hash也可以用，具體我沒有深入研究過，建議去翻一下看看。

我也在處理類似的問題，用的是Google SimHash簽名作為索引，然後根據索引極大縮小比較範圍再逐個比較。

simhash應該是最有效的

simhash

如果有用戶行為可以大大降低計算量

1，simhash等簽名演算法。

2，PCA等降維演算法。

3000w的話就simhash之類的標籤演算法最靠譜

用map/reduce的話，也是先做倒排，然後計算相似度的，也不是兩兩計算的

之做做過類似的事。這個裡面是否有重複計算的問題，MapReduce的話是否可以使用一個外存存儲中間結果？我不確定你的流程是怎麼樣的，是否可以畫下簡單的思路。

WAND演算法與VSM結合可以較好的得到你想要的結果。

另外，也可以考慮在你現有的index-based pairwise similarity MapReduce演算法基礎上，做一些改進：

1、將df 較大的keyword過濾掉，如你提到df=800w，計算近似相似度（只取40個keyword已經是近似了）

2、分治思想，將文檔做粗粒度分堆（如文本分類），僅對屬於同堆的文檔求TOP-N。

P.S.：2T 的中間結果不算大吧

我覺得得先降維，如每個詞都是一個維度，這個維度爆炸太可怕了