宣正邦 黃樹成 王 遜

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

1 引言

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

2 Hadoop平臺的設(shè)計

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

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

在Hadoop 架構(gòu)中，HDFS 是一個負責在集群中多個節(jié)點之間進行可靠地存儲并復制數(shù)據(jù)的模塊。HDFS被設(shè)計的初衷是能夠在廉價機器上部署分布式文件系統(tǒng)，它的優(yōu)勢和特點能夠為我們提供高吞吐量的數(shù)據(jù)訪問、高容錯性能以及安全保障等。

2.2 MapReduce框架

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

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

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

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

3 Apriori算法分析

3.1 Apriori算法簡述

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

3.2 Apriori算法缺點

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

4 Apriori算法改進

對于Apriori算法的不足之處進行如下改進：

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

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

5 實驗結(jié)果分析

5.1 實驗數(shù)據(jù)

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

5.2 實驗分析與討論

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

圖1 四種方法完成時間圖

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

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

圖2 候選頻繁項集消耗時間圖

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

實驗3：在Hadoop 平臺運行環(huán)境下，保持最小支持度不變的條件下進行三組對照實驗。第一組：對1 個候選項集生成后遍歷數(shù)據(jù)庫進行最小支持度對比并剪枝的消耗時間計時。第二組：對每3 個候選項集生成后遍歷數(shù)據(jù)庫進行最小支持度對比并剪枝的消耗時間計時。第三組：在第一組與第二組的條件下，繼續(xù)對頻繁項集消耗時間進行計時對比。改變頻繁項集的產(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ù)更改后生成各頻繁項集所消耗時間具體如下：

表1 實驗對比結(jié)果表

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

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

6 結(jié)語

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