基于MapReduce的大規(guī)模數(shù)據(jù)挖掘技術(shù)研究.pdf

1、網(wǎng)絡(luò)技術(shù)的快速發(fā)展和信息共享系統(tǒng)的大量應(yīng)用催生了大數(shù)據(jù)時代的來臨，很多傳統(tǒng)的基于單機的數(shù)據(jù)挖掘算法已經(jīng)無法滿足大數(shù)據(jù)的挖掘需求，如何進行高效的并行的數(shù)據(jù)挖掘成為當(dāng)前研究的熱點。當(dāng)前各種計算機應(yīng)用系統(tǒng)處理的數(shù)據(jù)規(guī)模日漸增長和結(jié)構(gòu)日益復(fù)雜，大規(guī)模圖數(shù)據(jù)和大規(guī)模高維數(shù)據(jù)的出現(xiàn)對傳統(tǒng)的數(shù)據(jù)挖掘方法提出了挑戰(zhàn)。大規(guī)模圖結(jié)構(gòu)數(shù)據(jù)在各種應(yīng)用中大量出現(xiàn)，例如生物信息學(xué)領(lǐng)域包含龐大的基因相互作用網(wǎng)絡(luò);WEB數(shù)據(jù)管理領(lǐng)域包含龐大的社會網(wǎng)絡(luò)、WEB網(wǎng)頁網(wǎng)絡(luò)，

2、社會媒體數(shù)據(jù)也多是以圖的形式描述的。很多互聯(lián)網(wǎng)上的信息如音頻、視頻都可表示為高維數(shù)據(jù)，在大數(shù)據(jù)背景下有效地進行圖數(shù)據(jù)和高維數(shù)據(jù)的數(shù)據(jù)挖掘需要合適的分布式計算模型。
　　MapReduce計算模型是目前最流行的一種云計算環(huán)境下的分布式計算模型，它可以將計算均勻地分布在多臺異構(gòu)的計算機上，并且屏蔽了復(fù)雜的并行編程，使得復(fù)雜的并行應(yīng)用可以歸結(jié)到兩個簡單的函數(shù)，map函數(shù)和reduce函數(shù)，它的高可用性、高可擴展性、高容錯性以及簡單性使得

3、其受到企業(yè)界和學(xué)術(shù)界的重視。一些著名的IT公司如Facebook、雅虎等均采用Hadoop作為云計算環(huán)境中的重要基礎(chǔ)軟件。雖然MapReduce在分布式計算方面取得了巨大的聲譽，但由于很多圖數(shù)據(jù)和高維數(shù)據(jù)的數(shù)據(jù)挖掘算法的計算及其分布式處理往往涉及復(fù)雜的處理流程，經(jīng)常需要多次迭代和大量的通信，而MapReduce通常適用于大數(shù)據(jù)集上的簡單應(yīng)用，導(dǎo)致MapReduce模型并不適用于具有局部性和迭代性的數(shù)據(jù)挖掘應(yīng)用。但是其他的圖處理系統(tǒng)，如P

4、regel，Hama等卻不具備MapReduce優(yōu)異的可擴展性和容錯性，這對大規(guī)模的數(shù)據(jù)挖掘是非常重要的一個性質(zhì)。為了使得MapReduce模型適用于圖數(shù)據(jù)和高維數(shù)據(jù)的挖掘，本文對其進行了改造，提出了基于MapReduce的局部迭代的MapReduce模型(LI-MR模型)，并且在局部迭代的MapReduce模型指導(dǎo)下，研究一些具體的具有局部迭代性的數(shù)據(jù)挖掘算法，包括社會網(wǎng)絡(luò)的權(quán)威值計算和社會網(wǎng)絡(luò)的社區(qū)挖掘，以及高維數(shù)據(jù)聚類問題。

5、>　　本文主要研究內(nèi)容和研究貢獻包含以下幾個部分。
　　1.提出局部迭代的MapReduce模型以支持圖挖掘
　　由于MapReduce編程模型缺乏對算法迭代性和局部性的有效的支持策略，為了適應(yīng)數(shù)據(jù)挖掘算法的迭代性和局部性，我們提出了局部迭代的MapRedue模型(LI-MR模型)，并且通過兩種方式實現(xiàn)了LI-MR模型的主要思想，第一種方式是擴展Hadoop系統(tǒng)，對其內(nèi)核API進行改造以實現(xiàn)緩存和索引，從而支持Hadoop應(yīng)

6、用對數(shù)據(jù)的隨機存取需求;第二種方式是Hadoop系統(tǒng)集成HBase數(shù)據(jù)庫來實現(xiàn)緩存和索引。LI-MR模型的主要思想包括以粗粒度的數(shù)據(jù)塊作為處理單位，消息通訊主要為數(shù)據(jù)塊之間的信息交互;通過緩存和索引機制從上一次迭代的結(jié)果中獲得對應(yīng)數(shù)據(jù)塊計算需要的局部信息，支持?jǐn)?shù)據(jù)塊的內(nèi)存計算，支持算法的局部計算。
　　2.提出局部迭代的標(biāo)號傳播算法
　　大規(guī)模圖的劃分問題一直是人們所關(guān)注的熱點問題，社會網(wǎng)絡(luò)的社區(qū)挖掘作為圖劃分問題的一個應(yīng)用

7、，有很高的時效性的要求。標(biāo)號傳播算法(LPA)是一個時間復(fù)雜度為線性的快速社區(qū)挖掘算法，但是對于大規(guī)模的社會網(wǎng)絡(luò)其運行時間仍然過長，本文提出局部迭代的標(biāo)號傳播算法運用LI-MR模型來解決標(biāo)號傳播算法的并行化問題。
　　3.提出局部迭代的PageRank算法
　　以往在MapReduce上運行PageRank算法，采取的方法以邊為處理單位，這樣導(dǎo)致數(shù)據(jù)在集群內(nèi)的大量遷移。局部迭代的PageRank算法在LI-MR模型的指導(dǎo)下，

8、將傳統(tǒng)的基于內(nèi)存的PageRank算法與MapReduce的良好的可擴展性結(jié)合起來，采用子圖作為處理單位，子圖內(nèi)部的通訊不必在整個集群中遷移，這樣，既保存了傳統(tǒng)內(nèi)存算法的效率，又得益于MapReduce的高可用性。
　　4.提出基于局部敏感哈希函數(shù)的海量高維數(shù)據(jù)的分布式聚類方法
　　對于海量高維數(shù)據(jù)的聚類，本文提出一種有效的基于代表點的批量處理方式，通過局部敏感性哈希函數(shù)，可以將距離近的數(shù)據(jù)點快速地聚集在一個桶中，采用桶的中

9、心點作為代表點來代表這個桶內(nèi)的所有點，通過這種代表點機制可以有效地削減聚類的數(shù)據(jù)規(guī)模。對于海量數(shù)據(jù)，需要一個較大的分類個數(shù)來滿足對數(shù)據(jù)精度的刻畫，對于較大的分類個數(shù)，本文通過局部敏感哈希函數(shù)來對比較計算進行裁減，尤其是對于具有較大k值的聚類，該方法可以在保證聚類質(zhì)量的前提下大幅度提高聚類的效率。提高k-means運行效率的另一種方法是提高所選中心點的質(zhì)量，本文針對k-means++不易于并行化的問題，提出了一種基于LI-MR模型的中心點