基于mapreduce框架的頻繁項集挖掘算法研究

《基于mapreduce框架的頻繁項集挖掘算法研究》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。

1、基于MapReduce框架的頻繁項集挖掘算法研究-->第1章緒論1.1課題研究的背景和意義隨著計算機的普及和互聯(lián)網(wǎng)的發(fā)展，電子商務(wù)逐漸興起，網(wǎng)絡(luò)上每天都產(chǎn)生TB以上等級的巨量數(shù)據(jù)[1]，如何從海量的數(shù)據(jù)中找到有價值的信息是當(dāng)前的一個熱點，對人類社會具有非常重要的社會價值和降級利益，數(shù)據(jù)挖掘就是實現(xiàn)這一功能的技術(shù)。在企業(yè)應(yīng)用方面[2]，可經(jīng)由數(shù)據(jù)挖掘[3]中的關(guān)聯(lián)規(guī)則挖掘算法[4]來分析用戶的瀏覽行為、興趣取向和使用頻率等，提高網(wǎng)站或商品的使用客戶率，進而提高公司得營利。關(guān)聯(lián)規(guī)則挖掘作為數(shù)據(jù)挖掘中最成

2、熟、最活躍的研究內(nèi)容之一，其目的是找出數(shù)據(jù)庫中不同項之間的相關(guān)關(guān)系、核心問題是頻繁項集的獲取[4]。在頻繁項集挖掘中具代表性的經(jīng)典算法─Apriori算法[5,6]。Apriori算法采取循序漸進的方式組合出侯選項集，其思想是利用已知的高頻數(shù)據(jù)項集推導(dǎo)其他高頻數(shù)據(jù)項集。但是單一的主機已經(jīng)無法負擔(dān)大量的運算，從而延伸出的叢集式運算、格網(wǎng)運算、云端運算[7]等，以往提出的分布式數(shù)據(jù)挖掘算法已經(jīng)無法解決現(xiàn)有海量數(shù)據(jù)處理問題[8]。云計算是分布式計算、并行運算和網(wǎng)格計算的進一步演進。將傳統(tǒng)數(shù)據(jù)挖掘算法并行化

3、改進后移植到Hadoop云計算平臺被相繼提出[9]，由于Hadoop具有良好的可靠性、擴展性、通用性、價格低廉、虛擬化、按需服務(wù)、巨大的存儲和計算能力、動態(tài)交互等特色，促使學(xué)者甚至各大企業(yè)大量投入其研究與應(yīng)用[10,11]?，F(xiàn)在已有很多運用在Hadoop的MapReduce計算框架的Apriori算法被提出[12,13]。其中one-phase算法一次產(chǎn)生所有候選項集再進行篩選的特性有著內(nèi)存嚴重占用的問題[14]；而k-phase算法，運用多次MapReduce運算出每一階的候選項集再進行篩選，雖有

4、效節(jié)省內(nèi)存，但多次的MapReduce運算會嚴重增加其基本消耗的時間(一次22秒~25秒左右)，而且由于Hadoop環(huán)境下多臺計算機之間通訊方式采用傳統(tǒng)的通訊協(xié)議，如，TCP/IP，HTTP，造成通訊延遲問題，嚴重影響了以上兩種算法的運算效率[15]。FAMR算法，其利用了AprioriTID[17]的優(yōu)點對數(shù)據(jù)先做前置的處理，目的在于篩選出一階低頻項集，減少候選項集的產(chǎn)生和內(nèi)存使用量，使速度有顯著的提升，但是其算法在Map端仍存在大量低頻項集的產(chǎn)生問題[16]?！?1.2數(shù)據(jù)挖掘的介紹及研究現(xiàn)

5、狀數(shù)據(jù)挖掘是從大量的數(shù)據(jù)中抽取未知的、可信的、新穎的、有效的及有潛在應(yīng)用價值的信息或模式的高級處理過程。也就是說可以從一個大型數(shù)據(jù)庫里頭所儲存的大量數(shù)據(jù)當(dāng)中萃取出有趣、有用的知識。近幾年云端運算的議題非常的熱門，運用Hadoop來處理巨量數(shù)據(jù)的算法也相繼被提出，由于Hadoop具有良好的擴充性、容錯性、經(jīng)濟性等特色，促使學(xué)者甚至各大企業(yè)大量投入其研究與應(yīng)用。而數(shù)據(jù)挖掘被作為數(shù)據(jù)庫中知識發(fā)現(xiàn)的一個基本步驟，因為云端運算技術(shù)的成熟，運用Hadoop來處理巨量數(shù)據(jù)的算法也相繼被提出。數(shù)據(jù)挖掘是數(shù)據(jù)庫知識發(fā)

6、現(xiàn)(Kno,HDFS)和MapReduce為核心[10]。HDFS的高容錯性、高伸縮性等優(yōu)點允許用戶將Hadoop部署在低廉的硬件上，形成分布式系統(tǒng)，MapReduce分布式編程模型允許用戶在不了解分布式系統(tǒng)底層細節(jié)的情況下開發(fā)并行應(yīng)用程序。Hadoop是基于Java程序語言所開發(fā)的，在架設(shè)方面不限于特定的操作系統(tǒng)，使得Hadoop可以輕易部署在低階的計算機叢集中，對于中、小型企業(yè)或者學(xué)術(shù)研究單位，可節(jié)省實際運用及學(xué)習(xí)研究的門檻，Hadoop是一個能夠讓用戶輕松架構(gòu)和使用的分布式計算平臺。用戶可以輕

7、松地在Hadoop上開發(fā)和運行處理海量數(shù)據(jù)的應(yīng)用程序，它在Hadoop上開發(fā)和處理巨量數(shù)據(jù)的應(yīng)用程序更為容易，所以在眾多產(chǎn)業(yè)和學(xué)術(shù)研究單位領(lǐng)域中被高度地重視，最主要有以下幾個特色[35]，如表2-1所示。在2008年1月，Hadoop已經(jīng)成為Apache頂級的項目，證明了它的成功，多樣，活躍性。到目前為止，除Yahoo!之外，被許多公司像Facebook和《紐約時報》等知名企業(yè)使用，其最大貢獻者Yahoo!在同年的2月份建構(gòu)了當(dāng)時運算規(guī)模頂級的Hadoop應(yīng)用，它們在2000個節(jié)點上面執(zhí)行了超過1萬

8、個Hadoop虛擬機器來處理超過5PB的網(wǎng)頁內(nèi)容，這些數(shù)據(jù)經(jīng)過壓縮后超過300TB，有著非常突出的成績，相信在不久未來，Hadoop將會被廣泛應(yīng)用到更多領(lǐng)域中，為大量的數(shù)據(jù)提供更加快速且高質(zhì)的服務(wù)。………2.2Hadoop分布式文件系統(tǒng)Hadoop分布式文件系統(tǒng)(HadoopDistributedFilesystem，HDFS)以流式數(shù)據(jù)訪問模式來存儲超大文件，它具有高容錯性的特點[36]，可以運行于商用硬件集群上。整體來說，HDFS它主要有以下特點。1．處理超大文件