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

1、網(wǎng)絡(luò)技術(shù)的快速發(fā)展和信息共享系統(tǒng)的大量應(yīng)用催生了大數(shù)據(jù)時(shí)代的來(lái)臨，很多傳統(tǒng)的基于單機(jī)的數(shù)據(jù)挖掘算法已經(jīng)無(wú)法滿足大數(shù)據(jù)的挖掘需求，如何進(jìn)行高效的并行的數(shù)據(jù)挖掘成為當(dāng)前研究的熱點(diǎn)。當(dāng)前各種計(jì)算機(jī)應(yīng)用系統(tǒng)處理的數(shù)據(jù)規(guī)模日漸增長(zhǎng)和結(jié)構(gòu)日益復(fù)雜，大規(guī)模圖數(shù)據(jù)和大規(guī)模高維數(shù)據(jù)的出現(xiàn)對(duì)傳統(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)域包含龐大的社會(huì)網(wǎng)絡(luò)、WEB網(wǎng)頁(yè)網(wǎng)絡(luò)，

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

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

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

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

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

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

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

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