摘  要： 頻繁項集挖掘是數據挖掘過程中的重要部分，傳統數據挖掘算法中常用Apriori算法和FP增長算法來挖掘頻繁項集。在實際應用中，傳統算法往往不能用于頻繁更新的數據庫，采用IMBT數據結構能從不斷更新的數據庫中挖掘頻繁項集，但是這將導致存儲空間不足和運行效率低下的問題?；?a class="innerlink" href="http://www.cowatch.cn/tags/MapReduce" title="MapReduce" target="_blank">MapReduce的增量數據挖掘能夠有效解決這些問題，通過對比基于MapReduce的增量數據挖掘和傳統增量數據挖掘的運行時間可以證明，基于Mapeduce的增量數據挖掘更高效。
關鍵詞： 增量數據挖掘；MapReduce；增量挖掘二叉樹；頻繁項集

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

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

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

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

　傳統數據挖掘技術：Apriori、FP樹等算法，雖然都能有效地找出頻繁項集，但不能適用于真實環境下動態的數據。所以出現了增量數據挖掘，本文給出了一種基于IMBT結構的增量數據挖掘算法，該算法能夠在新事務添加到數據庫或從數據庫中刪除后有效地列舉出每一個項集的支持度計數。由于在樹的構建過程中不需要預設最小支持度閾值，該算法允許用戶以任何支持度閾值挖掘頻繁項集。結合之前從數據庫中挖掘出來的結果，該算法能夠挖掘更新后的數據庫，效率上有很大的提升。但是IMBT樹在單臺計算機中運行時，該算法面臨存儲空間不足的問題，隨著算法的進行，IMBT樹逐漸擴展，會造成內存溢出，效率降低。
為此提出了一種新的方法，該方法采用MapReduce框架，將數據庫分為若干子數據庫然后發向多個節點計算機，由于計算機集群聚集了多臺計算機的存儲能力和計算能力，在存儲空間上可以動態的增加，并且能夠并行處理數據，從而解決了運行效率和存儲空間的問題，因此該方法比傳統的非并行增量算法更高效。
參考文獻
[1] 范明，孟小峰.數據挖掘概念與技術[M].北京：機械工業出版社，2012.
[2] 蔣翠清，胡俊妍.基于FP-tree的最大頻繁項集挖掘算法[J].合肥工業大學學報（自然科學版），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] 劉鵬.云計算[M].北京：電子工業出版社，2011.
[7] 高嵐嵐.云計算與網格計算的深入比較研究[J].海峽科學，2009（2）：56-57.
[8] LAM C， 韓冀中.Hadoop實戰[M].北京：人民郵電出版社，2012.