集群環(huán)境下企業(yè)應(yīng)用系統(tǒng)的關(guān)聯(lián)規(guī)則算法研究

趙向兵,張景安

(山西大同大學(xué)計算機與網(wǎng)絡(luò)工程學(xué)院，山西大同037009)

隨著移動互聯(lián)網(wǎng)、物聯(lián)網(wǎng)、云計算等技術(shù)的飛速發(fā)展，信息爆炸時代已經(jīng)來臨，海量數(shù)據(jù)已變成一種資源，深受企業(yè)的重視，對大數(shù)據(jù)的存儲，分析，管理，應(yīng)用，決定著企業(yè)的未來發(fā)展。大數(shù)據(jù)在各個領(lǐng)域的快速發(fā)展，也推動著企業(yè)不斷地發(fā)展新業(yè)務(wù)和創(chuàng)造新的發(fā)展模式，隨之而來的數(shù)據(jù)倉庫、數(shù)據(jù)安全、數(shù)據(jù)分析、數(shù)據(jù)挖掘等圍繞大數(shù)據(jù)的商業(yè)價值的利用逐漸成為行業(yè)人士爭相追捧的利潤焦點。大數(shù)據(jù)的整理和分析使企業(yè)產(chǎn)品更符合消費者需求，幫企業(yè)鎖定目標(biāo)客戶，幫企業(yè)提供更好的推廣方案，提高有效轉(zhuǎn)化率，幫企業(yè)危機預(yù)警等。同時，大數(shù)據(jù)技術(shù)應(yīng)用對于企業(yè)也面臨著前所未有的挑戰(zhàn)，Hadoop[1]為核心的大數(shù)據(jù)生態(tài)系統(tǒng)，解決了數(shù)據(jù)的存儲和相關(guān)計算問題，是一個優(yōu)秀的分布式計算系統(tǒng)，利用通用硬件構(gòu)建一個強大、穩(wěn)定、高效的分布式集群計算系統(tǒng)，滿足了互聯(lián)網(wǎng)公司基礎(chǔ)架構(gòu)的需求，為企業(yè)大數(shù)據(jù)技術(shù)應(yīng)用提供了巨大的支持。

大數(shù)據(jù)技術(shù)的應(yīng)用是企業(yè)信息化建設(shè)的重要方面，我校作為我省唯一一所“廳市共建”院校[2]，對地方企業(yè)的信息化建設(shè)情況做了調(diào)研，并對得到的數(shù)據(jù)進(jìn)行了數(shù)據(jù)分析，特別是對企業(yè)的交易數(shù)據(jù)進(jìn)行了關(guān)聯(lián)規(guī)則分析，得到了很好的效果，為地方企業(yè)的發(fā)展做出了貢獻(xiàn)。

關(guān)聯(lián)規(guī)則[2]挖掘是大數(shù)據(jù)挖掘研究領(lǐng)域的一個主要研究內(nèi)容，發(fā)現(xiàn)數(shù)據(jù)背后隱藏的數(shù)據(jù)項集之間的關(guān)聯(lián)關(guān)系和依賴關(guān)系，使其中的一個事物通過其他事物得以預(yù)測和發(fā)現(xiàn)。關(guān)聯(lián)規(guī)則挖掘應(yīng)用廣泛，經(jīng)典的案例是購物籃分析，發(fā)現(xiàn)交易數(shù)據(jù)庫中不同商品之間的聯(lián)系，通過“加工”實現(xiàn)數(shù)據(jù)的“增值”，找出顧客購買行為模式，提高企業(yè)的效益。

1 關(guān)聯(lián)規(guī)則的發(fā)展情況

關(guān)聯(lián)規(guī)則挖掘算法的一個關(guān)鍵問題是從事務(wù)集合中得出所有滿足用戶給定的最小支持度的頻繁項目集，關(guān)聯(lián)規(guī)則挖掘算法基本模型如圖1[3]：

圖1 關(guān)聯(lián)規(guī)則挖掘基本模型

經(jīng)典的關(guān)聯(lián)規(guī)則挖掘算法分為兩類：Apriori[4]算法和FP-Growth[5]算法。Apriori算法算法思路簡單，以遞歸統(tǒng)計為基礎(chǔ)，生成頻繁集易于實現(xiàn)，但該算法多次掃描事物數(shù)據(jù)庫，在確定是否是候選集之前依然需要對它生成子項集，再進(jìn)行連接比較和剪枝步驟，造成I/O開銷巨大，算法效率大幅度減低。頻繁模式增長（FP-growth）算法把一個大數(shù)據(jù)庫有效地壓縮成比原始數(shù)據(jù)庫小的多的高密度結(jié)構(gòu)，避免了重復(fù)掃描數(shù)據(jù)庫的開銷；該算法基于FP-tree的挖掘采用模式增長的遞歸策略和分區(qū)策略，無候選項目集，提高了挖掘效率，使用壓縮后的數(shù)據(jù)庫分成條件數(shù)據(jù)庫，各個條件數(shù)據(jù)庫關(guān)聯(lián)一個頻繁項，條件數(shù)據(jù)庫遠(yuǎn)遠(yuǎn)小于原始數(shù)據(jù)庫。

頻繁模式增長（FP-growth）對關(guān)聯(lián)規(guī)則發(fā)現(xiàn)提高了挖掘效率，接著 Ye Gao[6]、Huiling Penguins[7]、張繼福[8-9]等對該算法進(jìn)行了有效的改進(jìn)，但根本的問題沒有解決，包括：FP-tree樹生成過程時對條件模式基進(jìn)行遍歷，導(dǎo)致頻繁訪問本地數(shù)據(jù)庫或服務(wù)器；隨著數(shù)據(jù)量的急劇增加，構(gòu)造樹占用內(nèi)存過大，影響到系統(tǒng)的正常運行。針對關(guān)聯(lián)規(guī)則算法發(fā)展中存在的問題，采用分布式并行計算模式[10]提高關(guān)聯(lián)規(guī)則挖掘算法的效率是一個不錯的解決方法。

2 基于MapReduce的關(guān)聯(lián)規(guī)則并行挖掘

2.1 頻繁模式挖掘

已知數(shù)據(jù)庫記為DB，設(shè)I={i1,i2,i3,…,in}，I是n個不同數(shù)據(jù)項目的集合，T是DB中的事務(wù)，且T?1,用TID唯一標(biāo)識標(biāo)記每個事物。對于任意的項集X?1若X?T，則事務(wù)T對項集X是支持的。數(shù)據(jù)庫DB中包含X事務(wù)的個數(shù)就是項集X在DB中的支持度計數(shù)，數(shù)據(jù)庫DB包含X的事務(wù)占整個DB事務(wù)總數(shù)的百分比叫做DB中項集X的支持度。如果項集X的支持度大于等于用戶給出的最小支持度的闕值，稱項集X為數(shù)據(jù)庫DB中的頻繁項集，頻繁模式挖掘的本質(zhì)就是通過對數(shù)據(jù)庫的DB的處理分析，得出滿足所給最小支持度闕值的所有頻繁項集。

2.2 基于MapReduce的頻繁模式挖掘算法

首先針對待處理的數(shù)據(jù)集進(jìn)行遍歷得出頻繁1-項集，接著構(gòu)造FP-Tree，再調(diào)用FP-Growth算法進(jìn)行挖掘，最終得到頻繁項集。挖掘過程中使用了兩對Map和Reduce函數(shù)，實現(xiàn)了將數(shù)據(jù)事務(wù)映射為頻繁項計數(shù)和頻繁項集，最后生成關(guān)聯(lián)規(guī)則。具體步驟如下：

1）設(shè)集群系統(tǒng)中有N個節(jié)點，首先將數(shù)據(jù)庫根據(jù)事務(wù)條數(shù)分成大小相同的N個部分，且將每個部分分配到不同的節(jié)點并存儲在節(jié)點本地磁盤中；

2）掃描每個節(jié)點上的數(shù)據(jù)集，處理每個節(jié)點中的數(shù)據(jù)，計算出所有1項的支持度計數(shù)，再根據(jù)給定的最小支持度闕值，生成頻繁1項集合，并對頻繁1項集排序然后上傳到HDFS上。此過程通過一對Map和Reduce函數(shù)實現(xiàn)；

3）第二對Map和Reduce函數(shù)的Map階段：根據(jù)排好序的頻繁1項集，將事務(wù)數(shù)據(jù)排好序，然后遍歷排好序的事務(wù)數(shù)據(jù)，以頻繁項為鍵，事務(wù)數(shù)據(jù)為值傳遞給Reduce階段。

第二對Map和Reduce函數(shù)的Reduce階段：Re?duce節(jié)點接收到從Map節(jié)點過來的數(shù)據(jù)，遍歷這個頻繁項對應(yīng)的事務(wù)數(shù)據(jù)集，將它們構(gòu)建起該頻繁項的條件FP樹。從條件FP樹進(jìn)而得到包含本頻繁項的頻繁項集，如圖2；

圖2 MapReduce實現(xiàn)過程

4）基于頻繁項目集滿足最小置信度度量標(biāo)準(zhǔn)，產(chǎn)生關(guān)聯(lián)規(guī)則。

3 系統(tǒng)實現(xiàn)

該系統(tǒng)采用Eclipse作為開發(fā)工具，從系統(tǒng)的輸入（企業(yè)交易數(shù)據(jù)參數(shù)）與輸出（交易數(shù)據(jù)分析）之間復(fù)雜非線性的關(guān)系中抽取兩者之間的關(guān)聯(lián)規(guī)則，用以解釋客戶購買模式特點以及提供解決方案。然后將得到的交易數(shù)據(jù)分析情況反饋到企業(yè)產(chǎn)品生產(chǎn)和銷售的改進(jìn)中，進(jìn)而優(yōu)化企業(yè)的生產(chǎn)和銷售環(huán)節(jié)，實現(xiàn)“加工”實現(xiàn)數(shù)據(jù)的“增值”，提高企業(yè)的競爭力。

該原型系統(tǒng)包含了三大功能，分別是：并行環(huán)境的參數(shù)設(shè)置，頻繁項集的生成和最后客戶購買模式的關(guān)聯(lián)規(guī)則的生成。

并行參數(shù)設(shè)置中，選擇不同的集群環(huán)境時，可對相應(yīng)的參數(shù)選項進(jìn)行設(shè)置，系統(tǒng)涉及Hadoop并行計算平臺。數(shù)據(jù)經(jīng)過預(yù)處理后，首先選擇要處理的企業(yè)交易數(shù)據(jù)文件，數(shù)據(jù)導(dǎo)入完成后，輸入生成頻繁項集的最小支持度，按照介紹的算法思想，生成頻繁項集，輸入最小置信度度量標(biāo)準(zhǔn)，生成的關(guān)聯(lián)規(guī)則。

4 實驗結(jié)果及分析

運行環(huán)境：8個計算節(jié)點，都是在內(nèi)存16G服務(wù)器上搭建的虛擬機（內(nèi)存為512M），主要使用插件有：Ubuntu Linux10.10，JDK 1.6.0_37，Hadoop-1.1.1，Java eclipse，Hadoop-eclipse。

實驗數(shù)據(jù)：采用大同市企業(yè)信息化調(diào)研數(shù)據(jù)（規(guī)模以上141家，其它2011家）,數(shù)據(jù)經(jīng)過預(yù)處理，每條數(shù)據(jù)共40個屬性。

4.1 可擴展性

由圖3表明，在輸入數(shù)據(jù)集、支持度和置信度一定的情況下，對于所對應(yīng)的柱狀圖觀察，節(jié)點數(shù)的增加，加速比是逐漸升高的趨勢。從增長的幅度上來看，加速比在6個節(jié)點之前，增長緩慢，但是6個節(jié)點之后，加速比迅速增加，說明節(jié)點增加，計算能力提高，但同時造成了節(jié)點之間通信負(fù)荷也隨著有所提高，節(jié)點數(shù)目越大，系統(tǒng)通信代價越大，降低了系統(tǒng)并行化挖掘的加速比。

圖3 計算節(jié)點對算法效率的影響

4.2 可伸縮性

圖4表明，在相同節(jié)點、支持度和置信度下，數(shù)據(jù)集比較小時第一次掃描數(shù)據(jù)庫用時較少，構(gòu)造頻繁項的條件FP樹較小，系統(tǒng)挖掘效率明顯升高。隨著數(shù)據(jù)集的增加，第一次掃描數(shù)據(jù)庫用時逐漸增加，構(gòu)造頻繁項的條件FP樹和挖掘階段時間也逐漸增加，占用內(nèi)存也增加，故系統(tǒng)處理數(shù)據(jù)集到達(dá)一定程度時，運行時間增加變快。

圖4 數(shù)據(jù)集對算法效率的影響

5 總結(jié)

提出的算法，采用分布式并行計算模式，解決了FP-growth算法中，存在頻繁訪問本地數(shù)據(jù)庫或服務(wù)器，構(gòu)造樹占用內(nèi)存過大等問題。實驗結(jié)果表明，該算法有較強的可拓展性、收縮性和可行性。下一步的研究工作是在數(shù)據(jù)集動態(tài)改變的環(huán)境下，實現(xiàn)全局關(guān)聯(lián)規(guī)則的快速挖掘。