基于Hadoop的DG-Apriori算法

杜佼玲，張向利

（桂林電子科技大學信息與通信學院，廣西桂林 541004）

基于Hadoop的DG-Apriori算法

杜佼玲，張向利

（桂林電子科技大學信息與通信學院，廣西桂林 541004）

針對Apriori算法需要多次掃描數據庫、產生龐大的候選項集和計算時間過長等問題，提出一種基于Hadoop平臺的DG-Apriori算法。該算法改進了頻繁項集的連接方式，只需用頻繁（k-1）-項集與頻繁1-項集連接即可生成頻繁k-項集，極大地減少了連接次數，避免了產生龐大的候選項集，并且將改進后的Apriori算法以并行處理方式移植到Hadoop平臺，并行地計算頻繁項集，減少了計算時間。實驗結果表明，DG-Apriori算法大大提高了Apriori算法的性能。

Apriori算法；數據庫；Hadoop；頻繁項集

關聯規則挖掘是數據挖掘領域的一個重要研究方向，其旨在挖掘事務數據庫中項集之間有價值的關系。其中Apriori算法是最經典且最有影響力的挖掘關聯規則算法之一，已廣泛應用于商業、醫療、農業病蟲害分析、網絡安全、高校管理、移動通信以及氣象分析等領域。針對Apriori算法中存在的多次掃描數據庫和產生龐大候選項集等缺點，近年來已有很多學者對Apriori算法進行了改進，通過將事務數據庫轉化為矩陣表示以簡化其運算，其核心思想是使用“與運算”檢索事務矩陣生成頻繁項集，從而提高計算效率，節省時間。羅丹等［1］用新增的2個數組記錄矩陣行與列中“1”的個數，減少了掃描矩陣次數，并且去除了大量冗余非頻繁項集，有效地壓縮了矩陣；紀懷猛［2］分析了頻繁（k＋1）-項集的生成方法，將支持矩陣與頻繁2-項集矩陣結合實現快速剪枝，從而大大減少了驗證頻繁k-項集的計算量；苗苗苗等［3］壓縮了事務矩陣，減少了算法運算量；Yu Honglie等［4］采用布爾矩陣代替事務數據庫，對向量做“與運算”，并采用具有隨機存儲特性的數組，可直接產生k-頻繁項集。一些學者采用十字鏈表的數據結構對Apriori算法進行了改進。黃建明等［5］將事務數據庫轉化為十字鏈表進行存儲，并證明了對性能的改進；劉玉文［6］采用循環十字鏈表壓縮事務，節省了內存空間；段仰廣等［7］通過優化生成候選集的方法，減少了掃描事務數據庫的次數；胡斌［8］提出了一種采用雙向十字鏈表結構的頻繁項挖掘算法，加快了頻繁項的篩選過程。

但基于矩陣的Apriori算法需要多次檢索并重構矩陣，且在每一項的插入和矩陣的調整方面消耗了大量時間，因此，在某些條件下并非理想選擇。而十字鏈表結構復雜，其生成也需要耗費大量時間。為此，針對已有的串行關聯規則Apriori算法諸多不足，提出一種基于Hadoop平臺的DG-Apriori算法。

1 Hadoop平臺

Hadoop是一個分布式系統的基礎框架，源于A-pache Lucene項目的Nutch（搜索引擎子項目），它主要應用于大數據分布式處理，是用戶可輕易搭建以及使用的分布式計算平臺［9］。Hadoop框架主要包含分布式文件系統HDFS［10］和并行計算框架MapReduce［11］兩大模塊。其中，HDFS為大規模數據提供了分布式存儲，它由一個主控節點NameNode和一組從節點DataNode組成，對于上層的應用程序它是透明的，具備完全透明的數據存儲和訪問支撐功能。MapReduce負責分布式地處理存儲在HDFS中的數據。MapReduce由Map（映射）和Reduce（化簡）2個過程組成，這2個過程均以Key／Value的形式輸入、輸出，其類型由程序員根據具體需要設定。在Map過程中，處理一批輸入的鍵值對（k1，v1），按照相同的Key值生成一個鍵值對（k2，v2）列表。Map將這個鍵值對列表緩存，定期寫入本地磁盤。在Reduce過程中，Reduce的輸入為所有Mapper的輸出，它先按照輸入的Key值對數據進行排序，并將Key值相同的Value合并。然后通過調用Reduce函數，與指定鍵相關聯的值進行迭代處理，生成一個鍵值對列表（k3，v3）。事實上，在Map和Reduce中間還有一個Combine過程，這個過程是將Map輸出的鍵值對列表進行簡單的合并，將相同Key值對應的Value進行合并，若不設定Combine，Combiner默認使用Reduce的類。Combiner的主要作用是為了合并與減少Mapper的輸出，以減少網絡帶寬和Reduce節點的負載。

2 Apriori算法

2.1 算法思想

Agrawal等［12］于1993年提出Apriori算法，是一種挖掘單維、單層、布爾關聯規則的算法，其核心思想是采用逐層搜索遞推的方法。該算法的基本思想是：首先掃描事務數據庫D，計算出所有1-項候選集C1的支持度，并與最小支持度min＿sup比較，產生不小于min＿sup的頻繁1-項集L1；然后通過L1執行自連接（L1∞L1）和剪枝操作，生成2-項候選集C2，并根據min＿sup產生頻繁2-項集L2；再由L2產生L3，如此迭代，直到Lk＝?，算法結束［13］。

連接操作：連接頻繁（k-1）-項集Lk-1生成k-項候選集Ck，可連接的條件是Lk-1中的2個元素當且僅當前（k-2）項元素相同時［14］，即設Lk＝｛l1，l2，…，ln｝，1≤i＜j≤n，當（li［1］＝lj［1］）∩（li［2］＝lj［2］）∩…∩（li［k-1］≠lj［k-1］）時，有li∞lj＝｛li［1］，li［2］，…，li［k-1］，lj［k-1］｝∈ck。

剪枝操作：Ck是Lk的超集，由Apriori性質可知，任何非頻繁（k-1）-項集不屬于頻繁k-項集，因此，若一個k-候選集中出現其（k-1）項子集不屬于Lk-1，則將該k-候選項刪除。記ck∈Ck，若ck-1?Lk-1，則ck?Lk，則在k-項候選集Ck中刪除此ck項元素。

2.2 Apriori算法分析

1）在連接操作中，利用Lk-1自連接 （Lk-1∞Lk-1）生成Ck時，需要判斷是否滿足連接條件，而該判斷會進行多次比較，若Lk-1中有n項，則該連接操作的時間復雜度為O（（k-1）×n2）。此外，該判斷過程可能產生龐大的候選集，如L1的項集個數為100，將生成4950個C2，若L1的項集個數再增加，則C2的項集個數將更大。

2）在剪枝操作中，記?ck∈Ck，判斷ck所有的（k-1）組合項是否都屬于Lk-1，此過程也需要多次掃描數據庫。

3）由Ck（k＝1，2，…，n）生成Lk時，需要計算ck的支持度，并與最小支持度min＿sup比較，在此過程中也要掃描n次數據庫。

通過分析不難發現，Apriori算法存在可能產生龐大的候選項集、需要多次掃描數據庫和進行大量支持度計算等降低算法性能的問題。因此，為了提高Apriori算法的性能，提出一種DG-Aprior算法。

3 DG-Aprior算法

3.1 相關定理及推論

定理1任何頻繁項集的所有非空子集也是頻繁項集，非頻繁項集的超集是非頻繁項集［15］。

推論1若頻繁k-項集Lk還能產生頻繁（k＋1）-項集Lk＋1，則Lk中項集的個數必大于k。

推論2當k≥2時，對于?ck∈Ck，有ck∈（Lk-1∞Lk-1），則ck∈（Lk-1∞L1）。

證明（使用反證法） 假設當k≥2時，對于?ck∈Ck，有ck∈（Lk-1∞Lk-1），且ck∈（Lk-1∞L1）。因為?m∈ck，則有m∈Lk-1，又因為ck?（Lk-1∞L1），那么m?L1。這明顯與當k＝2時，m∈L1相矛盾。故對于?ck∈Ck，有ck∈（Lk-1∞Lk-1），那么ck∈（Lk-1∞L1）。

3.2 DG-Apriori算法步驟

DG-Apriori算法流程如圖1所示。算法步驟為：

1）利用Hadoop Mapreduce框架中的InputFormat類對存儲在HDFS上的原事務數據庫D進行水平劃分，將其分成多個大小相當、格式為〈Tid，Itemset〉的數據分塊InputSplit，每個InputSplit都由一個Map節點獨立計算。其中，Tid表示事務數，Itemset表示與之對應的項集。

2）主程序掃描每個數據分塊〈Tid，Itemset〉，Map階段計算出各自分塊的所有1-項候選集C1，其格式為〈Item，1〉，然后Reduce階段對所有mapper函數的結果合并（相同Item值計數相加，即為其I-tem的支持度），產生不小于min＿sup的頻繁1-項集L1，并緩存在HDFS中供每個Map節點共享讀取與使用。

3）重復步驟2），根據推論2，產生2-候選項集C2，使用Combine函數將所有mapper函數的結果合并，與min＿sup比較，得到局部頻繁2-項集L2，再由Reduce函數將每個Map節點上的局部頻繁2-項集L2合并，得到全局頻繁2-項集L2。

4）重復步驟2）、3），生成全局頻繁k-項集Lk，根據推論1條件，判斷Lk元素個數是否大于k，若大于k繼續執行步驟4），否則算法結束，得到最終的全局頻繁k-項集Lk。

圖1 DG＿Apriori算法流程Fig.1 The flow chart of DG＿Apriori algorithm

4 實驗與分析

為了驗證DG-Apriori算法性能，實驗對Apriori算法與DG-Apriori算法進行比較。測試環境是1臺PC機：Win7x64系統，8GB DDR3內存，500GB硬盤，Intel Core-i5處理器。利用虛擬機VMware Workstation搭建Hadoop集群，1臺主節點Name-Node和3臺從節點DataNode。每臺虛擬機系統采用Ubuntu Linux10.04，Hadoop版本選取1.1.2，測試事務數據來自頻繁項集挖掘數據集存儲庫里的經典mushroom、retail和T10I4D100K三個數據集（http：／／fimi.ua.ac.be／data／）。

1）實驗1。使用mushroom數據集，其事務數Tid為8124條，項集Item為119項，比較Apriori算法與DG-Apriori算法在不同最小支持度下的運行時間，其結果如圖2所示。從圖2可看出，當事務數與項集數均不大時，DG-Apriori算法運行時間是Apriori算法的1／2～1／3，隨著最小支持度的增加，2種算法的運行時間都在遞減，可見DG-Apriori算法性能明顯優于Apriori算法。

2）實驗2。使用retail數據集，其事務數Tid為88 162條，項集Item為16 469項。比較Apriori算法與DG-Apriori算法在不同最小支持度下的運行時間，其結果如圖3所示。從圖2可看出，當事務數與項集數相差不大時，DG-Apriori算法運行時間幾乎是Apriori算法的1／3，隨著最小支持度的增加，2種算法的運行時間都在遞減，但Apriori算法遞減相對緩慢，且隨著最小支持度的增加，當最小支持度大于20%，運行時間幾乎不變，而DG-Apriori算法幾乎呈指數狀遞減，可見DG-Apriori算法性能明顯優于Apriori算法。

圖3 retail數據集的DG-Apriori與Apriori的運行時間Fig.3 The running time of DG-Apriori and Apriori algorithm in retail data set

3）實驗3。使用T10I4D100K數據集，其事務數Tid為100 000條，項集Item為1000項。比較Apriori算法與DG-Apriori算法在不同最小支持度下的運行時間，其結果如圖4所示。從圖4可看出，當事務數遠遠大于項集數時，DG-Apriori算法運行時間是Apriori算法的1／4～1／6。隨著最小支持度的增加，2種算法的運行時間都在遞減，雖然DG-Apriori算法遞減相對緩慢些，但一直都保持著低運算時間狀態，亦可說明DG-Apriori算法性能明顯優于Apriori算法。

圖4 T10I4D100K數據集的DG-Apriori與Apriori的運行時間Fig.4 The running time of DG-Apriori and Apriori algorithm in T10I4D100Kdata set

5 結束語

針對串行關聯規則Apriori算法的不足，提出了一種基于Hadoop平臺的改進的DG-Apriori算法。該算法改進了頻繁項集的連接方式，只需用頻繁（k-1）-項集與頻繁1-項集連接即可生成頻繁k-項集，大大減少了連接次數，從而極大地減少了數據庫的掃描次數，避免了產生龐大的候選項集，并且將改進后的Apriori算法移植到Hadoop平臺上優化，以并行方式計算頻繁項集。實驗結果表明，DG-Apriori算法減少了算法的運算時間，加快了頻繁項集的生成過程，提高了算法的效率。下一步工作：1）用不同的計算機搭建Hadoop集群，并增加其節點數，在不同節點數下對比DG-Apriori算法與Apriori算法的運行時間；2）采用更大規模的事務數據庫進行對比測試。

［1］ 羅丹，李陶深.一種基于壓縮矩陣的Apriori算法改進研究［J］.計算機科學，2013，40（12）：75-80.

［2］ 紀懷猛.基于頻繁2項集支持矩陣的Apriori改進算法［J］.計算機工程，2013，39（11）：183-186.

［3］ 苗苗苗，王玉英.基于矩陣壓縮的Apriori算法改進的研究［J］.計算機工程與應用，2013，49（1）：159-162.

［4］ YU Honglie，WEN Jun，WANG Hongmei，et al.An improved apriori algorithm based on the boolean matrix and Hadoop［J］.Procedia Engineering，2011，15：1827-1831.

［5］ 黃建明，趙文靜，王星星.基于十字鏈表的Apriori改進算法［J］.計算機工程，2009，35（2）：37-38.

［6］ 劉玉文.基于十字鏈表的Apriori算法的研究與改進［J］.計算機應用與軟件，2012，29（5）：267-269.

［7］ 段仰廣，韋玉科.基于循環十字鏈表的頻繁模式挖掘算法［J］.計算機技術與發展，2009，19（10）：73-76.

［8］ 胡斌，張天，胡勇.基于雙向十字鏈表的頻繁項集挖掘［J］.科學技術與工程，2014，14（12）：68-72.

［9］ 趙龍.基于Hadoop的海量搜索日志分析平臺的設計和實現［D］.大連：大連理工大學，2013：5-6.

［10］ GARCIA H，LUDU A.The Google file system［C］／／ACM Sigops Operating Systems Review，2003：29-43.

［11］ DEAN J，GHEMAWAT S.MapReduce：simplelified data processing on large clusters［J］.Communication of the ACM，2008，51（1）：107-113.

［12］ AGRAWAL R，IMIELINSKI T，SWAMI A，et al.Mining association rules between sets of items in large database［J］.Acm Sigmod Record，1993，22（2）：207-216.

［13］ 何云峰.Apriori改進算法綜述［J］.微型機與應用，2013，32（6）：1-3.

［14］ 黃進，尹治本.關聯規則挖掘的Apriori算法的改進［J］.電子科技大學學報，2003，32（1）：76-79.

［15］ 栗曉聰，滕少華.頻繁項集挖掘的Apriori改進算法研究［J］.江西師范大學學報（自然科學版），2011，35（5）：498-502.

編輯：翁史振

DG-Apriori algorithm based on Hadoop

DU Jiaoling，ZHANG Xiangli
（School of Information and Communication Engineering，Guilin University of Electronic Technology，Guilin 541004，China）

Aiming at the problem that the Apriori algorithm needs to scan the database repeatedly and generates large candidate item sets and has long computation time，a DG-Apriori algorithm based on Hadoop is proposed，The algorithm improves connection of frequent item sets，the generation ofk-frequent item sets is only needed to join 1-frequent item sets with（k-1）-frequent item sets，the connection number is greatly reduced and the huge candidate item sets are avoided.And the improved Apriori algorithm is used for Hadoop platform to compute parallel frequent item sets and reduce the computation time.Experimental results show that DG-Apriori algorithm can effectively improve the performance of Apriori algorithm.

Apriori algorithm；database；Hadoop；frequent item sets

TP301.6

：A

：1673-808X（2016）05-0387-04

2016-03-10

國家自然科學基金（61363031，61461010）；廣西高校云計算與復雜系統重點實驗室研究課題（14101）；桂林電子科技大學研究生教育創新計劃（GDYCSZ201450）

張向利（1968-），女，陜西渭南人，教授，博士，研究方向為物聯網技術、網絡化監控系統。E-mail：xlzhang＠guet.edu.cn

杜佼玲，張向利.基于Hadoop的DG-Apriori算法［J］.桂林電子科技大學學報，2016，36（5）：387-390.