相似度的計算在文本的分類、聚類、推薦系統、反作弊中應用廣泛。本文以文本的相似度計算為例，講述如何基於MR計算相似度。文本相似度的計算一般先使用VSM（向量空間模型）將文本表示成向量，向量的每個分量都代表某個詞語在文檔中的權重，權重的計算可以用詞頻或者TF-IDF等算法得到。
本文中，我們使用向量的內積來表示文本的相似度：
從而，我們知道，對文本相似度計算有貢獻的是在兩個文本中同時出現過的詞語。
而一個數據集的文本相似度計算問題是計算該數據集中每個文本對的相似度。同許多問題一樣，在文本數目比較小的時候，內存可以完全載入這些向量，可以很快的計算；但是當文本數目變大到一定程度，程序就會運行的很慢，一是因為內存不能裝載下，不停的內存換入換出十分耗時，二是因為該問題的時間複雜度是O(N3)，N變大會導致程序的時間成立方級增長。
那麼如何使用Map-Reduce框架解決這個問題呢？
首先，問題的輸入可以看成一個矩陣，如圖1[1]所示：
圖 1 文本-詞語矩陣或者用戶-特徵矩陣
圖 1 文本-詞語矩陣或者用戶-特徵矩陣
其中，U代表文本，F代表詞語。如果直接以U為鍵進行Map-Reduce，那麼會遇到一個問題，因為要計算數據集中所有的二元文本對的相似度，所以不得不將所有的數據發往每一個節點，或者只有一個Reduce任務工作，以計算每個二元文本對的相似度。
所以，為了解決這個問題，我們將矩陣轉置，以F為鍵。這樣，解決該問題就由兩個Map-Reduce過程完成。第一個MR過程稱為倒排索引，對每個文檔，對其中的每個詞語，以詞語為鍵，文檔標號與詞語在該文檔中的權重為值輸出，這樣，我們就得到如(F4,[(U1,0.1),(U2,0.9),(U7,0.5)])格式的輸出。第二個MR過程計算文本相似度，以上一個MR過程的輸出為輸入，在Map過程中以文本對為鍵，以權重值的乘積為輸出，比如上面的F4輸出，map後變為[((U1,U2),0.09),((U1,U7),0.05),((U2,U7),0.45)]，這樣，就得到了在所有的在兩個文本中共同出現的詞語針對該兩個文本的權重乘積；然後在reduce過程中將相同鍵的值相加，就得到了所有的二元文本對的文本相似度。完整的Map-Reduce樣例如圖2[2]所示：
圖 2 矩陣轉置後的Map-Reduce過程
其中，U代表文本，F代表詞語。如果直接以U為鍵進行Map-Reduce，那麼會遇到一個問題，因為要計算數據集中所有的二元文本對的相似度，所以不得不將所有的數據發往每一個節點，或者只有一個Reduce任務工作，以計算每個二元文本對的相似度。
所以，為了解決這個問題，我們將矩陣轉置，以F為鍵。這樣，解決該問題就由兩個Map-Reduce過程完成。第一個MR過程稱為倒排索引，對每個文檔，對其中的每個詞語，以詞語為鍵，文檔標號與詞語在該文檔中的權重為值輸出，這樣，我們就得到如(F4,[(U1,0.1),(U2,0.9),(U7,0.5)])格式的輸出。第二個MR過程計算文本相似度，以上一個MR過程的輸出為輸入，在Map過程中以文本對為鍵，以權重值的乘積為輸出，比如上面的F4輸出，map後變為[((U1,U2),0.09),((U1,U7),0.05),((U2,U7),0.45)]，這樣，就得到了在所有的在兩個文本中共同出現的詞語針對該兩個文本的權重乘積；然後在reduce過程中將相同鍵的值相加，就得到了所有的二元文本對的文本相似度。完整的Map-Reduce樣例如圖2[2]所示：
圖 2 矩陣轉置後的Map-Reduce過程
經過這種設計之後，我們就可以使用Map-Reduce過程處理文本相似度問題了。
我們還可以通過Stripe算法[3]來優化IO，Stripe算法的詳細可以參考引申鏈接3，它與上圖方法的不同之處的根本在於輸出的表示形式，文本相似度問題的輸出是一個對稱矩陣，而上圖中的輸出的表示方法是以二元對為鍵，以相似度為值，在Stripe算法中，輸出的表示則是以單個文檔為鍵，以一個關聯數組為值，關聯數組中的鍵為文檔，值為關聯數組中的鍵與輸出鍵對應的兩個文檔的相似度，上圖的輸出使用Stripe算法的輸出表示為(d1,[(d2,1),(d3,4)]) ,(d2,[(d3,2)])，當然，根據輸出的形式，上圖中的Pairwise Similarity部分的map與shuffle的輸出都做出相應變化，據說，該算法可以節省1/3的空間。
還能做的優化就是負載均衡方面的考慮了。利用貪婪算法切分負載，對於任務隊列中的每一個任務，將其放到負載最小的機器上面去。這種方法對數據實時切分，作為Map的輸入。
還有一種優化是熱點消除，使用Mirror Mark算法對比較大的任務進行切分，MirrorMark算法的基本思想是將所有的數據複製成多份到多臺機器上，每臺機器上只對一部分數據進行計算，Mirror是指數據存儲多份，Mark是指數據分配到機器前對要在該機器上計算的數據做標記，在機器上只計算標記的數據；Mirror Mark算法能夠使運行時間最長的任務運行時間變短，從而降低整個Map-Reduce的時間。
實際上，對於文本-詞語矩陣或者用戶-特徵矩陣，計算相似度的問題其實可以看做是矩陣乘以矩陣的轉置的問題。圖2所示的MR過程實際上對矩陣的乘法做了兩個方面的優化，一是按照用戶對或者文本對進行分佈式劃分，二是利用了矩陣的稀疏性，不計算特徵值為0的部分。
閱讀更多 人工智能小迷妹 的文章
