一種基于Hadoop 的Apriori 改進(jìn)算法*

宣正邦 黃樹成 王 遜

（江蘇科技大學(xué) 鎮(zhèn)江 212003）

1 引言

隨著數(shù)據(jù)時(shí)代的到來，我們的生活方式也隨著發(fā)生天翻地覆的變化，各行各業(yè)都會(huì)產(chǎn)生數(shù)億級(jí)別的數(shù)據(jù)量，這些數(shù)據(jù)中隱含著重要知識(shí)，如何挖掘和利用這些知識(shí)具有重要意義。結(jié)合當(dāng)前海量數(shù)據(jù)的環(huán)境對(duì)Apriori 算法進(jìn)行改進(jìn)并與時(shí)下流行的Hadoop 云計(jì)算平臺(tái)相結(jié)合，設(shè)計(jì)出一個(gè)有效的算法，可以快速有效地挖掘大數(shù)據(jù)，提取重要知識(shí)。

2 Hadoop平臺(tái)的設(shè)計(jì)

Hadoop 平臺(tái)支持在服務(wù)器集群之間進(jìn)行分布式處理，可以從集群中的單個(gè)服務(wù)器擴(kuò)展到數(shù)千個(gè)服務(wù)器。Hadoop 平臺(tái)現(xiàn)已在各研究和實(shí)踐領(lǐng)域得到廣泛應(yīng)用，其中包括社交網(wǎng)絡(luò)、生物信息學(xué)和商業(yè)智能化等方面。Hadoop 平臺(tái)最主要的兩大核心模塊分別為HDFS 分布式文件系統(tǒng)和MapReduce框架。

2.1 HDFS分布式文件系統(tǒng)

在Hadoop 架構(gòu)中，HDFS 是一個(gè)負(fù)責(zé)在集群中多個(gè)節(jié)點(diǎn)之間進(jìn)行可靠地存儲(chǔ)并復(fù)制數(shù)據(jù)的模塊。HDFS被設(shè)計(jì)的初衷是能夠在廉價(jià)機(jī)器上部署分布式文件系統(tǒng)，它的優(yōu)勢(shì)和特點(diǎn)能夠?yàn)槲覀兲峁└咄掏铝康臄?shù)據(jù)訪問、高容錯(cuò)性能以及安全保障等。

2.2 MapReduce框架

MapReduce 是由Google 公司開發(fā)的分布式編程框架，它是Hadoop 平臺(tái)最重要的核心模塊之一。MapReduce具體執(zhí)行步驟如下：

1）文件輸入并將其劃分為n 個(gè)大小在16MB-64MB 之間的片段數(shù)據(jù)，將這些劃分好的數(shù)據(jù)分發(fā)給Hadoop 集群中各個(gè)計(jì)算節(jié)點(diǎn)。管理機(jī)主程序給計(jì)算節(jié)點(diǎn)分發(fā)所需要執(zhí)行的Map 或Reduce作業(yè)，并進(jìn)行狀態(tài)監(jiān)控，降低容錯(cuò)并提供決策依據(jù)給任務(wù)調(diào)度。

2）工作機(jī)程序接受分配任務(wù)，并讀取有關(guān)任務(wù)數(shù)據(jù)和格式化處理，將鍵值對(duì)以固定格式整理出來并用Map對(duì)其分解，分解得到的中間鍵值對(duì)將被保存在本地內(nèi)存緩沖區(qū)域。

3）用函數(shù)分類中間結(jié)果寫入本地磁盤，管理機(jī)主程序獲取這些中間結(jié)果的存儲(chǔ)路徑并將路徑信息分配給工作機(jī)程序。工作機(jī)程序執(zhí)行Reduce 工作并在得到路徑信息之后，訪問各存儲(chǔ)中間鍵值對(duì)節(jié)點(diǎn)緩沖區(qū)，并逐一讀取其數(shù)據(jù)，完成中間結(jié)果的整合和排序任務(wù)。此任務(wù)結(jié)束后，Reduce 會(huì)把最終結(jié)果輸入并存儲(chǔ)在文件里。

3 Apriori算法分析

3.1 Apriori算法簡(jiǎn)述

Apriori 算法通過逐層搜索的迭代過程來挖掘出數(shù)據(jù)之間的關(guān)聯(lián)規(guī)則，它通過限制生成候選項(xiàng)來挖掘頻繁項(xiàng)集，在兩個(gè)重要集合（頻繁項(xiàng)集與候選項(xiàng)集）之間交替進(jìn)行。第一個(gè)是從先前迭代的頻繁項(xiàng)集中生成候選項(xiàng)集，第二個(gè)是掃描數(shù)據(jù)庫針對(duì)所有事務(wù)對(duì)候選項(xiàng)進(jìn)行計(jì)數(shù)。在第k 次迭代（k≥2）中，從k-1 頻繁項(xiàng)集Ck-1生成候選k 項(xiàng)集Ck，然后針對(duì)Ck候選項(xiàng)集剪枝那些不滿足最小支持度的項(xiàng)集，如果Ck-1中不存在任何k-1 個(gè)子集，則可以從Ck中刪除所有Ck項(xiàng)集。

3.2 Apriori算法缺點(diǎn)

傳統(tǒng)Apriori 算法在如今數(shù)億網(wǎng)民產(chǎn)生的數(shù)據(jù)量下，它的不足之處顯而易見：第一，Apriori算法只能對(duì)單一事務(wù)數(shù)據(jù)進(jìn)行分析，效率低下；第二，算法在迭代過程中頻繁掃描數(shù)據(jù)庫，耗時(shí)長(zhǎng)；第三，算法候選項(xiàng)對(duì)比工作量大，并且算法自身產(chǎn)生的數(shù)據(jù)內(nèi)存也會(huì)導(dǎo)致系統(tǒng)I/O過于負(fù)載，效率得不到保證。

4 Apriori算法改進(jìn)

對(duì)于Apriori算法的不足之處進(jìn)行如下改進(jìn)：

1）降低算法對(duì)數(shù)據(jù)庫的遍歷次數(shù)。通過減少相應(yīng)數(shù)據(jù)庫掃描，將數(shù)據(jù)庫遍歷分為可變多階段掃描。原先每次掃描數(shù)據(jù)庫之后將會(huì)產(chǎn)生一個(gè)候選項(xiàng)集Ck，多階段掃描則在數(shù)據(jù)掃描的前后兩階段之間同時(shí)產(chǎn)生Ck，Ck+1…，C(k+m-1)n（其中n為可變值）個(gè)候選項(xiàng)集。

2）減少算法在連接步時(shí)的對(duì)比次數(shù)。Apriori算法中Ck-1通過自連接產(chǎn)生候選項(xiàng)集Ck，對(duì)于Ck-1隨著迭代次數(shù)的不斷增加其規(guī)模也隨之變大，而對(duì)于候選項(xiàng)集Ck所需要的自連接次數(shù)可能比前一次次數(shù)更多。讓Ck-1取消自連接過程，轉(zhuǎn)變成Ck-1與J1連接生成新的Ck。這時(shí)不需要Ck-1的每一項(xiàng)進(jìn)行兩兩比較，而是用Ck-1最后一項(xiàng)對(duì)J1每一項(xiàng)進(jìn)行大小對(duì)比，大幅度降低對(duì)比工作以提高運(yùn)行效率。

5 實(shí)驗(yàn)結(jié)果分析

5.1 實(shí)驗(yàn)數(shù)據(jù)

本次實(shí)驗(yàn)數(shù)據(jù)為MSD 音樂數(shù)據(jù)網(wǎng)站所提供，這里提取其站內(nèi)114 萬條音樂播放記錄，涉及歌曲989 首，并通過實(shí)驗(yàn)所需要的事務(wù)數(shù)據(jù)格式，按照相同用戶播放不同曲目合并為一條事務(wù)，共計(jì)生成88256 條事務(wù)數(shù)，并將同一歌曲名稱替換成同一數(shù)字形式（計(jì)1~989）。

5.2 實(shí)驗(yàn)分析與討論

實(shí)驗(yàn)1：采取四種不同運(yùn)行方式的對(duì)照實(shí)驗(yàn)，對(duì)改進(jìn)算法的完成時(shí)間進(jìn)行驗(yàn)證。四種方法分別為：原Apriori算法單機(jī)運(yùn)行、原Apriori算法Hadoop平臺(tái)運(yùn)行、改進(jìn)Apriori 算法單機(jī)運(yùn)行、改進(jìn)Apriori算法Hadoop 平臺(tái)運(yùn)行。其中最小支持度計(jì)數(shù)、最小置信度數(shù)值在四種方法中保持一致。首先，對(duì)四組實(shí)驗(yàn)對(duì)象進(jìn)行單次數(shù)據(jù)庫全局掃描進(jìn)行計(jì)時(shí)。在單機(jī)上算法改進(jìn)前后對(duì)全局?jǐn)?shù)據(jù)庫單次掃描時(shí)間為7.6s，在Hadoop集群下算法改進(jìn)前后單次全局?jǐn)?shù)據(jù)掃描時(shí)間為2.8s（算法的改進(jìn)對(duì)數(shù)據(jù)庫一次全局掃描時(shí)間并沒有受到影響）。在數(shù)據(jù)庫一次全局掃描時(shí)間消耗上，Hadoop 平臺(tái)極大的利用它對(duì)數(shù)據(jù)庫分塊處理能力，多個(gè)計(jì)算節(jié)點(diǎn)被平均分配任務(wù)，掃描時(shí)間對(duì)比單機(jī)掃描時(shí)間下降很多，而單機(jī)工作則承受全部數(shù)據(jù)庫掃描的壓力，在這種程度上算法效率提高不少，也是在本實(shí)驗(yàn)中第一次展露出Hadoop 集群對(duì)大量數(shù)據(jù)處理的優(yōu)勢(shì)。實(shí)驗(yàn)1 中四種方法最終完成時(shí)間如圖1所示。

圖1 四種方法完成時(shí)間圖

本組實(shí)驗(yàn)通過設(shè)置最小支持度分別為0.5、0.3來分別對(duì)四種實(shí)驗(yàn)方式進(jìn)行比較。從圖1 中可直觀了解到原算法與改進(jìn)算法在Hadoop 集群與單臺(tái)計(jì)算機(jī)中工作時(shí)間耗費(fèi)都明顯降低。當(dāng)支持度越低的時(shí)候，頻繁項(xiàng)集的項(xiàng)會(huì)更多，計(jì)算量程度也是隨之加大，改進(jìn)算法在Hadoop 集群上的時(shí)間消耗差也是比其他三種方法更小。

實(shí)驗(yàn)2：在單機(jī)運(yùn)行環(huán)境下，對(duì)改進(jìn)算法與原算法進(jìn)行候選頻繁項(xiàng)集消耗時(shí)間對(duì)比，實(shí)驗(yàn)中最小支持度設(shè)置為0.5。由于候選頻繁項(xiàng)集C1是通過候選1 項(xiàng)集直接對(duì)比最小支持度計(jì)數(shù)產(chǎn)生而無須先進(jìn)行自連接，這里便不與其他候選頻繁項(xiàng)集消耗時(shí)間作對(duì)比。從C2開始各項(xiàng)集產(chǎn)生的消耗時(shí)間如圖2所示。

圖2 候選頻繁項(xiàng)集消耗時(shí)間圖

通過實(shí)驗(yàn)數(shù)據(jù)對(duì)比，自連接過程在傳統(tǒng)算法中伴隨k 值增大而頻繁候選項(xiàng)集的產(chǎn)生時(shí)間逐漸遞減，但隨著迭代不斷進(jìn)行K 值變大之后，（k-2）項(xiàng)的對(duì)比次數(shù)也增多，各項(xiàng)集之間消耗時(shí)間下降量變化并不顯著。改進(jìn)后算法的連接方法不需要再進(jìn)行自連接過程，在對(duì)比時(shí)只用頻繁1 項(xiàng)集各項(xiàng)和頻繁k 項(xiàng)集的末尾項(xiàng)比較大小便可以生成k+1 頻繁項(xiàng)集。在時(shí)間消耗上，k 值變大時(shí)節(jié)省時(shí)間優(yōu)勢(shì)更加顯著。

實(shí)驗(yàn)3：在Hadoop 平臺(tái)運(yùn)行環(huán)境下，保持最小支持度不變的條件下進(jìn)行三組對(duì)照實(shí)驗(yàn)。第一組：對(duì)1 個(gè)候選項(xiàng)集生成后遍歷數(shù)據(jù)庫進(jìn)行最小支持度對(duì)比并剪枝的消耗時(shí)間計(jì)時(shí)。第二組：對(duì)每3 個(gè)候選項(xiàng)集生成后遍歷數(shù)據(jù)庫進(jìn)行最小支持度對(duì)比并剪枝的消耗時(shí)間計(jì)時(shí)。第三組：在第一組與第二組的條件下，繼續(xù)對(duì)頻繁項(xiàng)集消耗時(shí)間進(jìn)行計(jì)時(shí)對(duì)比。改變頻繁項(xiàng)集的產(chǎn)生規(guī)則：C1由第1 次與第2次掃描數(shù)據(jù)庫之間生成；C2由第2、3 次掃描數(shù)據(jù)庫之間生成；C3由第3、4 次掃描數(shù)據(jù)庫之間生成；C4、C5在第4、5 次掃描數(shù)據(jù)庫之間生成；C6、C7、C8在第5、6 次掃描數(shù)據(jù)庫之間生成……以此類推。三組實(shí)驗(yàn)對(duì)迭代次數(shù)更改后生成各頻繁項(xiàng)集所消耗時(shí)間具體如下：

表1 實(shí)驗(yàn)對(duì)比結(jié)果表

由上表三組數(shù)據(jù)對(duì)比可知，在Ck-1和L1連接生成頻繁Ck項(xiàng)集的迭代中，當(dāng)k從1開始較小的前幾項(xiàng)中，因C1項(xiàng)數(shù)生產(chǎn)量過大，對(duì)數(shù)據(jù)庫進(jìn)行頻繁掃描再通過統(tǒng)計(jì)局部候選項(xiàng)集計(jì)數(shù)并進(jìn)行全局剪枝任務(wù)，對(duì)去除算法中不需要的候選項(xiàng)集有很好的作用，也為后面迭代過程生成新的候選項(xiàng)集減少任務(wù)負(fù)擔(dān)。隨著迭代不斷的進(jìn)行，Ck的大小會(huì)隨著k值變大而減小，但Ck的項(xiàng)數(shù)減少并沒有減少相應(yīng)掃描數(shù)據(jù)庫所需時(shí)間，這時(shí)在兩次數(shù)據(jù)庫掃描之間提高候選集個(gè)數(shù)，平衡在各迭代過程中所需工作時(shí)間，以此達(dá)到提高算法效率的目的。

根據(jù)實(shí)驗(yàn)1、實(shí)驗(yàn)2、實(shí)驗(yàn)3的實(shí)驗(yàn)結(jié)果，將改進(jìn)后Apriori算法移植到Hadoop 平臺(tái)后的效率有顯著提高。其次，對(duì)于本文改進(jìn)的算法，通過可變多階段掃描機(jī)制與改變自連接方式的方法對(duì)算法的工作效率提升也得以證明是有效的。

6 結(jié)語

Apriori算法雖然已經(jīng)有幾十年歷史，但傳統(tǒng)的運(yùn)算模式無法適應(yīng)當(dāng)前大數(shù)據(jù)環(huán)境，本文將傳統(tǒng)Apriori 算法不足之處進(jìn)行改進(jìn)，并與Hadoop 平臺(tái)相結(jié)合，提出一種改進(jìn)的知識(shí)提取算法，通過實(shí)驗(yàn)證明了此算法的優(yōu)勢(shì)。