基于Mahout的MinHash算法研究與實現(xiàn).pdf

1、在很多應(yīng)用領(lǐng)域中，需要處理的數(shù)據(jù)往往是海量的并且具有很高的維度。近年來，隨著大數(shù)據(jù)研究領(lǐng)域的興起，針對高維數(shù)據(jù)的最近鄰查找問題已經(jīng)得到廣泛的應(yīng)用和研究。精確最近鄰查找的查詢代價非常大，近似最近鄰查找與精確最近鄰查找相比，能夠在效率上得到很大的提高，因此能有效解決最近鄰查找問題。近似近鄰查找是以犧牲查找精度為代價換取查找效率的提高，從而達到平衡查找效率與查找結(jié)果的目的。
　　位置敏感哈希（LSH）能夠有效的解決近似近鄰查找問題，并在

2、實際應(yīng)用中取得了明顯的效果，是解決維度災(zāi)難的一個很好的方法。LSH方法可以以概率方式保證一定的查詢精確度，從而實現(xiàn)快速的近似最近鄰查詢。MinHash是LSH算法中的一種，可以用來快速估算兩個集合的相似度，查找網(wǎng)絡(luò)上的重復(fù)網(wǎng)頁或者相似新聞網(wǎng)頁，MinHash算法使用Jaccard相似度來度量對象的相似程度。
　　在廣泛閱讀國內(nèi)外參考文獻的基礎(chǔ)上，本文針對MinH ash算法在分布式平臺上的實現(xiàn)進行了分析和研究。我們發(fā)現(xiàn)，在分布式平

3、臺Mahout上原有的Min Has h算法是錯誤的，其性能與理論MinH as h算法分析模型有很大的差距。為此，我們在深入研究MinHas h算法原理和Maho ut分布式平臺的基礎(chǔ)上，給出了新的MinHas h算法。然后，使用真實數(shù)據(jù)集對新舊算法做對比分析，驗證了新的Min Has h算法在處理實際問題上的正確性和準確性。最后，在Maho ut中實現(xiàn)了任意兩個文件對的Jac c ard相似度，得到精確Jacc ard相似度結(jié)果，并