基于mapreduce框架的頻繁項(xiàng)集挖掘算法研究

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

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

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

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

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

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

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

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

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