Hadoop 架構(gòu)下數(shù)量關(guān)聯(lián)規(guī)則的數(shù)據(jù)挖掘研究

左文濤，胡必波，劉鐘凌

（廣州工商學(xué)院 廣東 廣州 510850）

0 引言

面對(duì)數(shù)據(jù)與知識(shí)間的屏障，融合機(jī)器學(xué)習(xí)、數(shù)理統(tǒng)計(jì)等多學(xué)科的數(shù)據(jù)挖掘技術(shù)應(yīng)運(yùn)而生。 數(shù)據(jù)挖掘技術(shù)能夠根據(jù)設(shè)定的實(shí)際需求，挖掘出海量數(shù)據(jù)內(nèi)潛在的價(jià)值信息，為用戶科學(xué)合理地分析決策提供強(qiáng)有力的數(shù)據(jù)支撐。數(shù)量關(guān)聯(lián)規(guī)則作為數(shù)據(jù)挖掘技術(shù)的核心要素，其可關(guān)聯(lián)出不同量值參數(shù)間潛在的規(guī)則和聯(lián)系。

社會(huì)的發(fā)展帶動(dòng)科技的進(jìn)步，數(shù)據(jù)信息量呈顯著的增長(zhǎng)趨勢(shì)，傳統(tǒng)模式下的數(shù)量關(guān)聯(lián)規(guī)則挖掘算法在操作處理海量數(shù)據(jù)信息時(shí)，部分?jǐn)?shù)據(jù)能夠有效完成挖掘工作，但所需時(shí)間較長(zhǎng)；另一部分可能會(huì)存在數(shù)據(jù)溢出的狀況，從而最終無(wú)法完成數(shù)據(jù)挖掘，對(duì)用戶造成嚴(yán)重影響。 因此，針對(duì)傳統(tǒng)模式下的數(shù)量關(guān)聯(lián)規(guī)則挖掘算法，本文提出一種基于Hadoop 的數(shù)量關(guān)聯(lián)規(guī)則的數(shù)據(jù)挖掘算法（data mining algorithm of quantity association rules In hadoop architecture，DMQAH），以期能夠最大程度上挖掘數(shù)據(jù)中的關(guān)聯(lián)規(guī)則，為數(shù)據(jù)與知識(shí)的轉(zhuǎn)化搭建橋梁。

1 相關(guān)理論概述

1.1 Hadoop

Hadoop 是一個(gè)基于Master-Slave 主從模式的系統(tǒng)基礎(chǔ)架構(gòu)，系統(tǒng)內(nèi)部每個(gè)數(shù)據(jù)集群都包含一個(gè)主節(jié)點(diǎn)和多個(gè)從節(jié)點(diǎn)，其中主節(jié)點(diǎn)的核心工作是實(shí)現(xiàn)Name Node、Job Tracker 系統(tǒng)功能，并協(xié)助系統(tǒng)內(nèi)其他從節(jié)點(diǎn)實(shí)現(xiàn)Task Tracker、Data Node 等功能［1］。

Hadoop 體系架構(gòu)的主要組件為分布式文件系統(tǒng)（hadoop distributed file system，HDFS）和MapReduce，其中HDFS 主要用于存儲(chǔ)系統(tǒng)內(nèi)海量的數(shù)據(jù)信息；MapReduce利用海量的數(shù)據(jù)信息進(jìn)行高精度計(jì)算，從而獲得更多的有效數(shù)據(jù)。 與此同時(shí)，Hadoop 內(nèi)部的諸多組件均可單獨(dú)地應(yīng)用到各類分布式場(chǎng)景中，并以組件的模式進(jìn)行分布式的數(shù)據(jù)運(yùn)算和存儲(chǔ)，具體如圖1 所示。

圖1 Hadoop 體系架構(gòu)結(jié)構(gòu)圖

1.2 關(guān)聯(lián)規(guī)則挖掘概述

1.2.1 購(gòu)物式分析

關(guān)聯(lián)規(guī)則挖掘是一種基于數(shù)量關(guān)聯(lián)規(guī)則的機(jī)器學(xué)習(xí)算法，其來(lái)源于“購(gòu)物式分析”，其是以消費(fèi)者的主觀意識(shí)為前提，根據(jù)消費(fèi)者在超市購(gòu)買(mǎi)商品的類型來(lái)挖掘消費(fèi)習(xí)慣的一種形式。 如大量消費(fèi)者都前往同一家超市購(gòu)買(mǎi)大量的“炸雞、啤酒”，那么可認(rèn)為“炸雞、啤酒”可能是消費(fèi)者的購(gòu)物習(xí)慣。 商鋪可通過(guò)分析大量消費(fèi)者購(gòu)買(mǎi)商品的記錄，獲取消費(fèi)者的購(gòu)物習(xí)慣，從而根據(jù)消費(fèi)者的購(gòu)物習(xí)慣等數(shù)據(jù)來(lái)制定切實(shí)可行的營(yíng)銷計(jì)劃，并科學(xué)合理地規(guī)劃商品貨架分布等情況。 實(shí)際上，消費(fèi)者購(gòu)物習(xí)慣或商品重復(fù)被購(gòu)買(mǎi)的模式就是一種數(shù)量關(guān)聯(lián)規(guī)則，可表示為式（1）［2］：

其中“fried chicken?beer”表示消費(fèi)者在購(gòu)買(mǎi)炸雞商品時(shí)，更多地也會(huì)購(gòu)買(mǎi)啤酒的一種關(guān)聯(lián)關(guān)系；support表示商鋪在詳細(xì)分析了大量商品購(gòu)買(mǎi)數(shù)據(jù)后，其中有5%的消費(fèi)者同時(shí)購(gòu)買(mǎi)了這兩種商品；confidence表示在全部購(gòu)買(mǎi)數(shù)據(jù)中，購(gòu)買(mǎi)炸雞產(chǎn)品的消費(fèi)者中有70%的人同時(shí)購(gòu)買(mǎi)了啤酒。 由此可知，數(shù)量關(guān)聯(lián)規(guī)則就是通過(guò)海量數(shù)據(jù)信息發(fā)生的概率來(lái)詳細(xì)分析內(nèi)在規(guī)則是否具有價(jià)值，發(fā)生概率越高，其規(guī)則關(guān)聯(lián)度越強(qiáng)，就越具有可信性。

1.2.2 頻繁參量集和關(guān)聯(lián)規(guī)則

假設(shè)D為一類事務(wù)數(shù)據(jù)庫(kù)，L＝｛I1，I2，…，In｝ 表示全部量值的總和，T主要用于記錄D數(shù)據(jù)庫(kù)中涉及的全量事務(wù)，且不為空，A和B表示兩個(gè)不同的量值集合。 根據(jù)關(guān)聯(lián)規(guī)則的定義，可將其表示為A?B，其中A?L，B?L，A≠?，B≠?，且A∩B＝?。 關(guān)聯(lián)規(guī)則A?B包含兩種模式的量值屬性，即支持度和置信度，其中支持度support為整個(gè)事務(wù)數(shù)據(jù)庫(kù)D內(nèi)同時(shí)包括A和B量值的概率；置信度confidence為包含A量值的全量事務(wù)中兼顧B量值的事務(wù)概率，此時(shí)可得式（2）［3］：

為了保證不同量值參數(shù)間呈強(qiáng)關(guān)聯(lián)規(guī)則，此時(shí)需要通過(guò)關(guān)聯(lián)規(guī)則A?B確認(rèn)參數(shù)：支持度最小限制閾（min_sup） 、置信度最小限制閾（min_conf） ，若想兩者之間為強(qiáng)關(guān)聯(lián)規(guī)則關(guān)系，此時(shí)需滿足：support量值需大于等于min_sup，且confidence量值不小于min_conf， 此時(shí)將其中滿足min_sup的量值事務(wù)集合稱為頻繁參量集，可得式（3）［4］：

通過(guò)公式（3）可知，關(guān)聯(lián)規(guī)則A?B的置信度可通過(guò)A、A∪B的支持度計(jì)算而獲取。 當(dāng)實(shí)際的應(yīng)用過(guò)程中，若已成功獲得量值參數(shù)A、B及A∪B事務(wù)集合的支持度后，也可得出關(guān)聯(lián)規(guī)則A?B、B?A，并通過(guò)公式評(píng)估兩者之間是否存在強(qiáng)關(guān)聯(lián)規(guī)則關(guān)系。 因此關(guān)聯(lián)規(guī)則的數(shù)據(jù)挖掘核心在于頻繁數(shù)量集的采集獲取，一般情況下不同參量間的數(shù)據(jù)挖掘過(guò)程主要分為頻繁數(shù)量集獲取、頻繁數(shù)量集的強(qiáng)關(guān)聯(lián)規(guī)則。

2 Hadoop 架構(gòu)下數(shù)量關(guān)聯(lián)規(guī)則的數(shù)據(jù)挖掘算法

2.1 基于數(shù)量關(guān)聯(lián)規(guī)則挖掘算法流程

由于Hadoop 架構(gòu)具有分布式數(shù)據(jù)處理能力，在海量數(shù)據(jù)中能夠通過(guò)數(shù)據(jù)參量間的強(qiáng)關(guān)聯(lián)規(guī)則挖掘有用的數(shù)據(jù)信息，其中基于數(shù)量關(guān)聯(lián)規(guī)則挖掘算法，其通過(guò)運(yùn)用MapReduce 計(jì)算模式，對(duì)系統(tǒng)內(nèi)數(shù)據(jù)進(jìn)行多模塊劃分，劃分步驟為：

步驟1：假定minsup，k ＝1。 對(duì)Hadoop 架構(gòu)內(nèi)的參量A進(jìn)行初始化，將數(shù)據(jù)矩陣內(nèi)數(shù)值為1 的量值存儲(chǔ)于A內(nèi)，并將D轉(zhuǎn)化為M布爾矩陣。

步驟2：獲取M量值，并計(jì)算矩陣內(nèi)每行的支持度sup值。 計(jì)算獲取sup值后，將其與minsup進(jìn)行比較，將不滿足minsup閾值的向量刪除，將其中大于minsup向量所對(duì)應(yīng)的頻繁參量集整合為L(zhǎng)1，根據(jù)L1中sup量值的大小進(jìn)行重新排列，此時(shí)將獲得一個(gè)新的M1矩陣。

步驟3：對(duì)M1矩陣內(nèi)的向量進(jìn)行內(nèi)積運(yùn)算，運(yùn)算后將其與minsup進(jìn)行比較，將不滿足minsup閾值的向量刪除，將其中大于minsup向量所對(duì)應(yīng)的頻繁參量集整合為L(zhǎng)2，并重新建立M2矩陣。 此時(shí)需將大于minsup的向量按位累加到參量A內(nèi)，并令k ＝2，當(dāng)且僅當(dāng)k大于2 時(shí)，將依次進(jìn)行步驟4、5、6 的循環(huán)運(yùn)算。

步驟4：獲取Mk量值，將Lk內(nèi)不能與相鄰位置處向量進(jìn)行連接的數(shù)據(jù)刪除，依次對(duì)參量A內(nèi)的數(shù)據(jù)進(jìn)行修正，最后獲取一個(gè)新的Mk矩陣。

步驟5：掃描參量A，將參量A內(nèi)小于1 的列向量全部刪除，并將刪除后剩余的列向量重新組合為新的Mk矩陣。

步驟6：將參量A內(nèi)的全部數(shù)據(jù)清空。 將Mk矩陣內(nèi)能夠?qū)崿F(xiàn)關(guān)聯(lián)的向量進(jìn)行內(nèi)積運(yùn)算，此時(shí)將滿足minsup閾值條件的行向量構(gòu)成新的Lk+1，并組合為Mk+1矩陣，依次將滿足minsup閾值條件的行向量按位累計(jì)至參量?jī)?nèi)A，最后Mk+1的行數(shù)與k +2 進(jìn)行大小比較，若小于k +2，則表示算法完成，否則令其中的k ＝k +1，循環(huán)進(jìn)行運(yùn)算，直到滿足條件為止。

2.2 多模塊的數(shù)據(jù)算法代碼

DMQAH 算法主要是通過(guò)MapReduce 模型計(jì)算不同量值參數(shù)間的關(guān)聯(lián)性，并對(duì)系統(tǒng)內(nèi)數(shù)據(jù)進(jìn)行多模塊劃分，從而利用數(shù)量參數(shù)間的關(guān)聯(lián)規(guī)則挖掘有效數(shù)據(jù)。 其中數(shù)據(jù)模塊的劃分對(duì)整個(gè)系統(tǒng)應(yīng)用效果具有顯著的影響，若劃分的數(shù)據(jù)塊整體偏小，將會(huì)對(duì)數(shù)據(jù)信息的傳輸造成壓力，增加數(shù)據(jù)的整體傳輸時(shí)間；若劃分的數(shù)據(jù)塊整體偏大，將會(huì)給單塊數(shù)據(jù)的運(yùn)算增加壓力，降低數(shù)據(jù)處理的時(shí)效性。因此，本文將采用并行模式的數(shù)據(jù)劃分方式，通過(guò)并行模式獲取數(shù)據(jù)庫(kù)內(nèi)每個(gè)數(shù)據(jù)節(jié)點(diǎn)的頻繁參量集，依次獲取單個(gè)模塊的頻繁參量集后將其匯總歸類，其中各模塊的具體實(shí)現(xiàn)情況如下［5］：

針對(duì)算法的管理應(yīng)用平臺(tái)自動(dòng)生成系統(tǒng)（management autonomy platform，MAP）端而言，其算法代碼Input：DBi（i＝1，2…，n），Output：各結(jié)點(diǎn)的局部Lk和c.sup算法；

L1＝Sear-fre1-itemsets（DBi） ／ ／對(duì)劃分后的全量數(shù)據(jù)塊進(jìn)行比較，獲得頻繁參量集1。

調(diào)用數(shù)量關(guān)聯(lián)規(guī)則的數(shù)據(jù)挖掘算法，此時(shí)可產(chǎn)生部分頻繁參量集

針對(duì)算法的Reduce 端而言，核心任務(wù)是將合并后的頻繁參量集與計(jì)算獲得的minsup閾值進(jìn)行比較，若大于整體的支持度，此時(shí)將獲得部分頻繁參量集，其算法代碼Input：〈c，c.sup〉，Output：部分頻繁參量集1 到k項(xiàng)的算法：

2.3 基于Hadoop 的數(shù)量關(guān)聯(lián)規(guī)則的數(shù)據(jù)挖掘算法描述

基于Hadoop 的數(shù)量關(guān)聯(lián)規(guī)則的數(shù)據(jù)挖掘算法的具體實(shí)現(xiàn)過(guò)程，如圖2 所示。

圖2 基于Hadoop 的數(shù)量關(guān)聯(lián)規(guī)則的數(shù)據(jù)挖掘算法流程圖

步驟1：將事務(wù)數(shù)據(jù)庫(kù)D進(jìn)行水平劃分，將劃分后的n個(gè)數(shù)據(jù)塊傳輸?shù)紿adoop 架構(gòu)的集群節(jié)點(diǎn)位置處，此時(shí)假定節(jié)點(diǎn)的總量為m個(gè)，開(kāi)始運(yùn)行MAP 端數(shù)據(jù)。

步驟2：當(dāng)數(shù)據(jù)傳輸至集群內(nèi)不同的數(shù)據(jù)節(jié)點(diǎn)后，將其轉(zhuǎn)化為相應(yīng)的布爾矩陣，然后通過(guò)掃描的方式獲取頻繁參量集1，并重組形成部分頻繁參量集。

步驟3：依次對(duì)獲取的布爾矩陣進(jìn)行行向量、列向量的壓縮，壓縮過(guò)程采用基于數(shù)量關(guān)聯(lián)規(guī)則挖掘算法的具體步驟。

步驟4：此時(shí)將Hadoop 集群內(nèi)各個(gè)節(jié)點(diǎn)獲取的壓縮矩陣，轉(zhuǎn)化為部分頻繁參量集。

步驟5：依次統(tǒng)計(jì)頻繁參量集的部分支持度，并將其與minsup閾值進(jìn)行比較，若大于minsup閾值條件，此時(shí)可將其合并至頻繁參量集k內(nèi)，從而整合為并集Lk。

步驟6：根據(jù)置信度大小的比較，循環(huán)計(jì)算得到最終符合要求的關(guān)聯(lián)規(guī)則。

3 Hadoop 架構(gòu)下數(shù)量關(guān)聯(lián)規(guī)則的數(shù)據(jù)挖掘算法實(shí)現(xiàn)

Hadoop 架構(gòu)下數(shù)量關(guān)聯(lián)規(guī)則的數(shù)據(jù)挖掘算法實(shí)現(xiàn)，將DMQAH 與傳統(tǒng)模式下的Apriori 數(shù)據(jù)挖掘算法分別進(jìn)行實(shí)驗(yàn)測(cè)試，從而獲取實(shí)驗(yàn)參數(shù)。 該測(cè)試實(shí)驗(yàn)將采用7 臺(tái)VMWare 虛擬機(jī)搭建Hadoop 集群，將其中任意一臺(tái)作為集群的主節(jié)點(diǎn)，其余均為系統(tǒng)的從節(jié)點(diǎn)。

實(shí)驗(yàn)一：采用條數(shù)不同、大小不同的事務(wù)數(shù)據(jù)庫(kù)，分別計(jì)算出傳統(tǒng)模式下的Apriori 數(shù)據(jù)挖掘算法與DMQAH 算法的運(yùn)行時(shí)間，從而針對(duì)兩者的運(yùn)行時(shí)間得出結(jié)論。 如表1 所示。

表1 不同條數(shù)的事務(wù)數(shù)據(jù)庫(kù)結(jié)果

通過(guò)表1 可知，當(dāng)事務(wù)數(shù)為7 萬(wàn)條時(shí)，傳統(tǒng)模式下的Apriori 數(shù)據(jù)挖掘算法的運(yùn)行時(shí)間為950.45 s，DMQAH 算法的運(yùn)行時(shí)間僅3.13 s，兩者之間相差947.32 s。 隨著事務(wù)數(shù)的逐漸增加，雖然DMQAH 算法的運(yùn)行時(shí)間也呈顯著的增長(zhǎng)趨勢(shì)，但相較于傳統(tǒng)算法差距依舊較大。 當(dāng)事務(wù)數(shù)總量達(dá)到100 萬(wàn)條時(shí)，DMQAH 算法的運(yùn)行時(shí)間為48.98 s，但由于數(shù)量級(jí)比過(guò)高，使得傳統(tǒng)算法無(wú)法計(jì)算出運(yùn)行時(shí)間，此時(shí)可明顯地看出DMQAH 算法的優(yōu)勢(shì)。

實(shí)驗(yàn)二：采用統(tǒng)一事務(wù)數(shù)據(jù)庫(kù)，將其設(shè)置不同參量的支持度，分別計(jì)算出傳統(tǒng)模式下的Apriori 數(shù)據(jù)挖掘算法與DMQAH 算法的運(yùn)行時(shí)間，從而針對(duì)兩者的運(yùn)行時(shí)間得出結(jié)論。 如表2 所示。

表2 統(tǒng)一事務(wù)數(shù)據(jù)庫(kù)設(shè)置不同支持度結(jié)果

通過(guò)表2 可知，當(dāng)將支持度設(shè)置為10%時(shí)，傳統(tǒng)模式下的Apriori 數(shù)據(jù)挖掘算法的運(yùn)行時(shí)間為6 020.36 s，DMQAH 算法的運(yùn)行時(shí)間為11.28 s，遠(yuǎn)低于傳統(tǒng)算法的運(yùn)行時(shí)間。 隨著支持度的不斷增多，兩者的運(yùn)行時(shí)間均呈遞減狀態(tài)，但DMQAH 算法的整體時(shí)長(zhǎng)更小。 由此可見(jiàn)，DMQAH 算法在挖掘支持度較小的關(guān)聯(lián)規(guī)則時(shí)，其運(yùn)行的效率更佳。

4 結(jié)語(yǔ)

綜上所述，隨著智能化時(shí)代的到來(lái)，數(shù)據(jù)量變得越來(lái)越大，數(shù)據(jù)種類越來(lái)越多樣化，以Hadoop 為代表的分布式框架結(jié)構(gòu)，利用MapReduce 的強(qiáng)大計(jì)算優(yōu)勢(shì)對(duì)海量數(shù)據(jù)信息進(jìn)行并行處理，從而在最短的運(yùn)行時(shí)間內(nèi)獲得最多的有效數(shù)據(jù)。 基于此，本文提出一種DMQAH 算法。 通過(guò)兩組對(duì)比實(shí)驗(yàn)，分別對(duì)DMQAH 算法及傳統(tǒng)算法進(jìn)行分析比較，實(shí)驗(yàn)結(jié)果表明DMQAH 算法在運(yùn)算時(shí)間、運(yùn)算效率等方面均優(yōu)于傳統(tǒng)算法。