基于MapReduce的大規(guī)模數(shù)據(jù)挖掘技術(shù)研究.pdf_第1頁(yè)
已閱讀1頁(yè),還剩119頁(yè)未讀 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

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)

溫馨提示

  • 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 眾賞文庫(kù)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

最新文檔

評(píng)論

0/150

提交評(píng)論