摘  要： 頻繁項(xiàng)集挖掘是數(shù)據(jù)挖掘過(guò)程中的重要部分，傳統(tǒng)數(shù)據(jù)挖掘算法中常用Apriori算法和FP增長(zhǎng)算法來(lái)挖掘頻繁項(xiàng)集,。在實(shí)際應(yīng)用中,，傳統(tǒng)算法往往不能用于頻繁更新的數(shù)據(jù)庫(kù)，采用IMBT數(shù)據(jù)結(jié)構(gòu)能從不斷更新的數(shù)據(jù)庫(kù)中挖掘頻繁項(xiàng)集,，但是這將導(dǎo)致存儲(chǔ)空間不足和運(yùn)行效率低下的問(wèn)題,。基于MapReduce的增量數(shù)據(jù)挖掘能夠有效解決這些問(wèn)題,，通過(guò)對(duì)比基于MapReduce的增量數(shù)據(jù)挖掘和傳統(tǒng)增量數(shù)據(jù)挖掘的運(yùn)行時(shí)間可以證明,，基于Mapeduce的增量數(shù)據(jù)挖掘更高效,。
關(guān)鍵詞： 增量數(shù)據(jù)挖掘,；MapReduce；增量挖掘二叉樹(shù),；頻繁項(xiàng)集

　目前,，數(shù)據(jù)挖掘[1]在計(jì)算機(jī)領(lǐng)域正飛速發(fā)展。數(shù)據(jù)庫(kù)系統(tǒng)領(lǐng)域的發(fā)展主要在數(shù)據(jù)收集,、數(shù)據(jù)庫(kù)創(chuàng)建,、數(shù)據(jù)管理、數(shù)據(jù)分析,、數(shù)據(jù)挖掘,、數(shù)據(jù)倉(cāng)庫(kù)等方面。在數(shù)據(jù)挖掘中,，挖掘關(guān)聯(lián)規(guī)則是相當(dāng)重要的部分。該部分的主要研究集中在挖掘算法上,。國(guó)內(nèi)外對(duì)頻繁項(xiàng)集挖掘算法一直都有著很深的研究,，例如：Apriori算法[1]，F(xiàn)P增長(zhǎng)算法[1-2],。
　但是,，現(xiàn)實(shí)應(yīng)用中新的事務(wù)會(huì)不斷地錄入數(shù)據(jù)庫(kù)，這使得許多挖掘算法不能處理動(dòng)態(tài)的數(shù)據(jù),。數(shù)據(jù)庫(kù)隨機(jī)變動(dòng),，這些算法不能有效應(yīng)對(duì)數(shù)據(jù)的增添、刪除等操作,，這使得增量數(shù)據(jù)挖掘[3-5]變得尤為重要,。
1 增量數(shù)據(jù)挖掘的必要性
　在現(xiàn)實(shí)應(yīng)用中,，事務(wù)數(shù)據(jù)庫(kù)常處于動(dòng)態(tài)更新?tīng)顟B(tài),，這需要對(duì)傳統(tǒng)關(guān)聯(lián)規(guī)則挖掘算法做進(jìn)一步改進(jìn),，因此出現(xiàn)了一些新的關(guān)聯(lián)規(guī)則。一些傳統(tǒng)的批量挖掘算法通過(guò)反復(fù)掃描數(shù)據(jù)庫(kù)來(lái)發(fā)現(xiàn)是否有新的事物添加到數(shù)據(jù)庫(kù)中,，但是這樣做需要大量的運(yùn)算時(shí)間,。
　實(shí)際應(yīng)用中，由于新的事務(wù)不停地添加到數(shù)據(jù)庫(kù)中,，原先產(chǎn)生的頻繁項(xiàng)集將被淘汰掉,，基于新的數(shù)據(jù)庫(kù)會(huì)產(chǎn)生新的頻繁項(xiàng)集。增量挖掘算法能有效避免這樣的問(wèn)題,。增量數(shù)據(jù)挖掘以之前挖掘的結(jié)果為基礎(chǔ),，利用新增的事務(wù)來(lái)進(jìn)行增量挖掘。
2 增量挖掘發(fā)展現(xiàn)狀
2.1 基于IMBT的增量挖掘
　為了能更好地利用現(xiàn)成的挖掘結(jié)果,，采用了一種新的樹(shù)形結(jié)構(gòu)來(lái)代替FP樹(shù),。該結(jié)構(gòu)叫做增量挖掘二叉樹(shù)（IMBT）[2]，在事務(wù)添加到數(shù)據(jù)庫(kù)中或從數(shù)據(jù)庫(kù)中刪除后,，它能給出每個(gè)項(xiàng)集的支持度計(jì)數(shù),。與之前的在數(shù)據(jù)庫(kù)更新后通過(guò)反復(fù)掃描數(shù)據(jù)庫(kù)得出的頻繁項(xiàng)集支持度計(jì)數(shù)相比，該算法一次只處理一條事務(wù)并且記錄數(shù)據(jù)集結(jié)構(gòu)中可能的頻繁項(xiàng)集,，節(jié)約了大量的時(shí)間,。

2.4 在數(shù)據(jù)庫(kù)更新后挖掘頻繁項(xiàng)集
　給定一個(gè)項(xiàng)集X，如果X在事務(wù)數(shù)據(jù)庫(kù)中出現(xiàn)的頻率大于或等于預(yù)設(shè)的最小支持度,，X則稱(chēng)為頻繁項(xiàng)集,。如果項(xiàng)集X不是頻繁項(xiàng)集，它的左半部分的子項(xiàng)集也不是頻繁的,，該算法會(huì)停止處理左半部分的子項(xiàng)集,，這樣可以提高挖掘效率。構(gòu)建好IMBT樹(shù)后,，需要遍歷該樹(shù)來(lái)找出滿足最小支持度閾值的頻繁項(xiàng)集,，挖掘結(jié)果被保存在一張表中以便將來(lái)使用。由于IMBT樹(shù)的構(gòu)建不需要支持度閾值,，所以可以在數(shù)據(jù)庫(kù)更新后以任何支持度閾值挖掘頻繁項(xiàng)集,。
　該方法采用IMBT樹(shù)結(jié)構(gòu)，重用從源數(shù)據(jù)庫(kù)中挖掘出來(lái)的結(jié)果挖掘新增事務(wù),，使得性能有大幅度提升,。但是該方法仍面臨內(nèi)存空間不夠的問(wèn)題。隨著程序運(yùn)行,，IMBT樹(shù)將會(huì)逐漸擴(kuò)大,，這使得內(nèi)存空間容納不下IMBT樹(shù)，運(yùn)行效率也將大大降低,。采用并行機(jī)制來(lái)改進(jìn)現(xiàn)有的串行挖掘算法將在性能上有很大地飛躍,。
3 問(wèn)題解決方案
3.1 并行算法
　在并行計(jì)算[6-7]中,，數(shù)據(jù)會(huì)被分發(fā)到不同的計(jì)算機(jī)節(jié)點(diǎn)中去，并行過(guò)程中每臺(tái)計(jì)算機(jī)對(duì)不同的數(shù)據(jù)塊執(zhí)行相同的任務(wù),。
　由于真實(shí)環(huán)境中的數(shù)據(jù)庫(kù)通常非常大,，把整個(gè)數(shù)據(jù)庫(kù)保存在每個(gè)節(jié)點(diǎn)計(jì)算機(jī)上將造成存儲(chǔ)空間過(guò)多的浪費(fèi)。將數(shù)據(jù)庫(kù)拆分則能成功地將子數(shù)據(jù)庫(kù)分發(fā)在不同的計(jì)算機(jī)節(jié)點(diǎn)上,。由于每臺(tái)計(jì)算機(jī)都保存子數(shù)據(jù)庫(kù),，節(jié)約了大量的存儲(chǔ)空間。
3.2 并行算法的優(yōu)勢(shì)
　隨著數(shù)據(jù)的增加,，當(dāng)數(shù)據(jù)量超過(guò)了GB的時(shí)候,，串行數(shù)據(jù)挖掘算法將很難在短時(shí)間內(nèi)給出挖掘結(jié)果。而且單臺(tái)電腦沒(méi)有足夠的內(nèi)存來(lái)容納全部的數(shù)據(jù),。在并行條件下,，由于聚集了多臺(tái)計(jì)算機(jī)的存儲(chǔ)空間和處理能力,，因此并行算法能很好地解決運(yùn)行效率低下,，存儲(chǔ)空間不足的問(wèn)題,。
3.3 MapReduce工作流程
　要順利實(shí)現(xiàn)并行算法需用MapReduce框架[8],。MapReduce是由谷歌開(kāi)發(fā)的標(biāo)準(zhǔn)軟件架構(gòu)，主要用于處理大數(shù)據(jù)操作任務(wù),。該架構(gòu)由Map和Reduce組成。
　當(dāng)有數(shù)據(jù)輸入時(shí),，輸入數(shù)據(jù)被分割成塊發(fā)送到各個(gè)節(jié)點(diǎn)計(jì)算機(jī)上，被分配了任務(wù)的節(jié)點(diǎn)計(jì)算機(jī)讀取并處理收到的輸入數(shù)據(jù)塊,。Map函數(shù)處理完數(shù)據(jù)后輸出中間數(shù)據(jù)：鍵值對(duì),，輸出的中間鍵值對(duì)暫時(shí)緩沖到內(nèi)存,，這些內(nèi)存中的的鍵值對(duì)將會(huì)寫(xiě)入到本地硬盤(pán),，然后將中間鍵值對(duì)在本地硬盤(pán)的位置信息發(fā)送給主節(jié)點(diǎn)計(jì)算機(jī)，主節(jié)點(diǎn)計(jì)算機(jī)負(fù)責(zé)向執(zhí)行Reduce函數(shù)的計(jì)算機(jī)發(fā)送位置信息,，這些計(jì)算機(jī)通過(guò)位置信息遠(yuǎn)程從運(yùn)行Map函數(shù)的計(jì)算機(jī)硬盤(pán)上讀取中間鍵值對(duì),，并將中間鍵值對(duì)按鍵分類(lèi),，擁有相同鍵的值都分在一起,，由Reduce函數(shù)處理后輸出最終結(jié)果[8]。圖4給出了其工作流程圖,。

4 提出系統(tǒng)
4.1 系統(tǒng)思路
　針對(duì)上述內(nèi)存空間和運(yùn)行效率的問(wèn)題,，提出了一種并行構(gòu)建IMBT樹(shù)挖掘頻繁項(xiàng)集的方法。該方法主要完成兩項(xiàng)工作：并行構(gòu)建IMBT樹(shù)及頻繁項(xiàng)集計(jì)數(shù),。由于單臺(tái)計(jì)算機(jī)內(nèi)存和處理器能力有限，該算法不適用于單臺(tái)電腦上運(yùn)行,。為了讓算法的性能更高,，就需要盡量減少計(jì)算機(jī)之間數(shù)據(jù)的傳輸并且避免過(guò)多的處理過(guò)程。
4.2 系統(tǒng)設(shè)計(jì)
　首先將輸入文件分為若干獨(dú)立文件塊,。然后并行處理輸入的每一個(gè)文件塊。由于該方法需要用到基本數(shù)據(jù)結(jié)構(gòu)IMBT進(jìn)行增量挖掘,，不需要為IMBT樹(shù)定義最小支持度閾值,。當(dāng)本地IMBT樹(shù)在各個(gè)節(jié)點(diǎn)計(jì)算機(jī)中生成后，每個(gè)項(xiàng)集將會(huì)在獨(dú)立的節(jié)點(diǎn)計(jì)算機(jī)中進(jìn)行支持度計(jì)數(shù),。然后將生成的局部頻繁項(xiàng)集結(jié)合起來(lái),，在全局?jǐn)?shù)據(jù)庫(kù)中生成一個(gè)全局的頻繁項(xiàng)集。最后,，由用戶定義一個(gè)最小支持度閾值,，并將其用于全局頻繁項(xiàng)集從而計(jì)算出真正的頻繁項(xiàng)集。MapReduce框架的工作模式能很好地實(shí)現(xiàn)該方法,，該方法的設(shè)計(jì)流程圖如圖5所示,。

5 性能仿真與結(jié)果分析
　為了對(duì)比基于MapReduce的增量數(shù)據(jù)挖掘和傳統(tǒng)增量數(shù)據(jù)挖掘的運(yùn)行效率，實(shí)驗(yàn)選取一個(gè)擁有85 643條事務(wù)的數(shù)據(jù)庫(kù),，數(shù)據(jù)庫(kù)中每條事務(wù)的項(xiàng)目數(shù)平均為7個(gè),，項(xiàng)目總共有1 300種，實(shí)驗(yàn)用計(jì)算機(jī)總共3臺(tái),，配置均為雙核CPU AMD Athlon（tm）64 X2 Dual Core Processor 4000+,，內(nèi)存為2 GB，安裝Ubuntu10.10與Window XP雙系統(tǒng),，其中傳統(tǒng)IMBT挖掘算法在單臺(tái)電腦上用XP系統(tǒng)運(yùn)行,，基于MapReduce的IMBT在3臺(tái)電腦上用Ubuntu10.10運(yùn)行，其中1臺(tái)計(jì)算機(jī)配置為namenode,，另外2臺(tái)配置為datanode,。由于是實(shí)驗(yàn),，所以沒(méi)有配置second namenode,。
　在數(shù)據(jù)挖掘進(jìn)行之前，數(shù)據(jù)庫(kù)中預(yù)存有30 000條事務(wù),，在基于MapReduce的IMBT算法中,，這30 000條事務(wù)被平均分配到3臺(tái)電腦上，實(shí)驗(yàn)開(kāi)始后不斷地向數(shù)據(jù)庫(kù)錄入事務(wù)數(shù),，兩種算法均取支持度閾值為800,。圖6給出在不斷向數(shù)據(jù)庫(kù)中添加事務(wù)時(shí)，兩種算法的耗時(shí)對(duì)比,。
　從圖6中可以看出,，基于MapReduce的IMBT算法的運(yùn)行效率幾乎比傳統(tǒng)IMBT算法快一倍，圖中的運(yùn)行時(shí)間并非完全線性增長(zhǎng),，這是由于數(shù)據(jù)庫(kù)中每條事務(wù)的項(xiàng)目種類(lèi)和項(xiàng)目數(shù)量不一致導(dǎo)致的,。理論上基于MapReduce的IMBT算法采用2臺(tái)計(jì)算機(jī)同時(shí)進(jìn)行挖掘任務(wù)，效率應(yīng)該快一倍,，圖中結(jié)果并未達(dá)到一倍是因?yàn)檎麄€(gè)MapReduce過(guò)程需要頻繁傳遞信息,，namenode需要一定的響應(yīng)時(shí)間，導(dǎo)致實(shí)際效率與理論效率存在一定誤差,。但基于MapReduce的增量數(shù)據(jù)挖掘算法在運(yùn)行效率上比傳統(tǒng)數(shù)據(jù)挖掘算法仍然有了質(zhì)的提升。

　傳統(tǒng)數(shù)據(jù)挖掘技術(shù)：Apriori,、FP樹(shù)等算法,，雖然都能有效地找出頻繁項(xiàng)集，但不能適用于真實(shí)環(huán)境下動(dòng)態(tài)的數(shù)據(jù),。所以出現(xiàn)了增量數(shù)據(jù)挖掘,，本文給出了一種基于IMBT結(jié)構(gòu)的增量數(shù)據(jù)挖掘算法，該算法能夠在新事務(wù)添加到數(shù)據(jù)庫(kù)或從數(shù)據(jù)庫(kù)中刪除后有效地列舉出每一個(gè)項(xiàng)集的支持度計(jì)數(shù),。由于在樹(shù)的構(gòu)建過(guò)程中不需要預(yù)設(shè)最小支持度閾值，該算法允許用戶以任何支持度閾值挖掘頻繁項(xiàng)集,。結(jié)合之前從數(shù)據(jù)庫(kù)中挖掘出來(lái)的結(jié)果,，該算法能夠挖掘更新后的數(shù)據(jù)庫(kù),，效率上有很大的提升,。但是IMBT樹(shù)在單臺(tái)計(jì)算機(jī)中運(yùn)行時(shí)，該算法面臨存儲(chǔ)空間不足的問(wèn)題,，隨著算法的進(jìn)行,，IMBT樹(shù)逐漸擴(kuò)展，會(huì)造成內(nèi)存溢出,，效率降低,。
為此提出了一種新的方法，該方法采用MapReduce框架,，將數(shù)據(jù)庫(kù)分為若干子數(shù)據(jù)庫(kù)然后發(fā)向多個(gè)節(jié)點(diǎn)計(jì)算機(jī),，由于計(jì)算機(jī)集群聚集了多臺(tái)計(jì)算機(jī)的存儲(chǔ)能力和計(jì)算能力，在存儲(chǔ)空間上可以動(dòng)態(tài)的增加,，并且能夠并行處理數(shù)據(jù),，從而解決了運(yùn)行效率和存儲(chǔ)空間的問(wèn)題，因此該方法比傳統(tǒng)的非并行增量算法更高效,。
參考文獻(xiàn)
[1] 范明,，孟小峰.數(shù)據(jù)挖掘概念與技術(shù)[M].北京：機(jī)械工業(yè)出版社，2012.
[2] 蔣翠清,，胡俊妍.基于FP-tree的最大頻繁項(xiàng)集挖掘算法[J].合肥工業(yè)大學(xué)學(xué)報(bào)（自然科學(xué)版）,，2010，33（9）：387-1391.
[3] HONG T P,， WANG C Y,， TAO Y H. A new incremental data mining algorithm using pre-large itemsets[J]. Intelligent Data Analysis， 2001,， 5（2）： 111-129.
[4] HONG T P,， LIN C W， WU Y L. Incrementally fast updated frequent pattern trees[J]. Expert Systems With Applications,，2008,，34（4）：2424- 2435.
[5] YANG C H， YANG D L. IMBT-a binary Tree for Efficient Support Counting of Incremental Data Mining[J]. 2009 International Conference on Computational Science & Engineering,， 2009,，1（1）：324-329.
[6] 劉鵬.云計(jì)算[M].北京：電子工業(yè)出版社，2011.
[7] 高嵐嵐.云計(jì)算與網(wǎng)格計(jì)算的深入比較研究[J].海峽科學(xué),，2009（2）：56-57.
[8] LAM C,， 韓冀中.Hadoop實(shí)戰(zhàn)[M].北京：人民郵電出版社，2012.