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

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

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

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