分布式動(dòng)態(tài)數(shù)據(jù)庫(kù)增量關(guān)聯(lián)規(guī)則挖掘研究

余小高 魯群志

摘要：為了解決分布式動(dòng)態(tài)數(shù)據(jù)庫(kù)關(guān)聯(lián)規(guī)則挖掘效率低的問題，利用MPI與OpenMP的優(yōu)點(diǎn)，提出了實(shí)現(xiàn)增量關(guān)聯(lián)規(guī)則挖掘的混合模式。在次頻繁項(xiàng)概念基礎(chǔ)上，給出該混合模式總體架構(gòu)，設(shè)計(jì)了基于MPI與OpenMP的分布式動(dòng)態(tài)數(shù)據(jù)庫(kù)增量關(guān)聯(lián)規(guī)則挖掘混合模式工作流程，并給出了偽代碼描述，該模式只處理變化的數(shù)據(jù)。實(shí)驗(yàn)結(jié)果表明，該模式比現(xiàn)有的串行與分布式關(guān)聯(lián)規(guī)則挖掘方法效率更高、性能更優(yōu)。

關(guān)鍵詞：關(guān)聯(lián)規(guī)則；分布式數(shù)據(jù)庫(kù)；動(dòng)態(tài)數(shù)據(jù)

DOIDOI：10.11907/rjdk.171746

中圖分類號(hào)：TP391文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：16727800（2017）010016604

0引言

關(guān)聯(lián)規(guī)則是一種能夠從數(shù)據(jù)庫(kù)海量數(shù)據(jù)中發(fā)現(xiàn)知識(shí)的重要方法[1，2]。大多數(shù)關(guān)聯(lián)規(guī)則挖掘算法以靜態(tài)數(shù)據(jù)庫(kù)為前提，但實(shí)際上許多數(shù)據(jù)庫(kù)是動(dòng)態(tài)的，因此有必要研究動(dòng)態(tài)數(shù)據(jù)庫(kù)的關(guān)聯(lián)規(guī)則挖掘[35]。有學(xué)者提出了增量關(guān)聯(lián)規(guī)則挖掘方法，如CHEUNG提出基于次頻繁項(xiàng)的快速更新算法FUP，這種算法在處理數(shù)據(jù)更新方面仍然很慢?，F(xiàn)今大多數(shù)計(jì)算機(jī)有多個(gè)內(nèi)核，大多數(shù)單位內(nèi)部是通過(guò)局域網(wǎng)互聯(lián)，具有多個(gè)節(jié)點(diǎn)，因此，串行算法不能有效利用當(dāng)前的硬件資源。為了應(yīng)對(duì)大數(shù)據(jù)的出現(xiàn)與更新，串行關(guān)聯(lián)規(guī)則算法可擴(kuò)展性問題亟待解決。有學(xué)者提出了并行或分布式關(guān)聯(lián)規(guī)則法，但在時(shí)間執(zhí)行上依然存在問題。針對(duì)上述問題，本文綜合MPI編程模型[2，3]與OpenMP[5，6]優(yōu)點(diǎn)，提出了基于MPI與OpenMP的分布式動(dòng)態(tài)數(shù)據(jù)庫(kù)增量關(guān)聯(lián)規(guī)則挖掘方法（簡(jiǎn)稱為“混合模式”），可以有效地對(duì)分布式動(dòng)態(tài)數(shù)據(jù)庫(kù)進(jìn)行關(guān)聯(lián)規(guī)則挖掘。

MPI與 OpenMp結(jié)合，可以用OpenMP更細(xì)的粒度，并行使用MPI的顯式控制數(shù)據(jù)放置策略。在該方法中，通信模式采用兩級(jí)，節(jié)點(diǎn)間與節(jié)點(diǎn)內(nèi)通信。通過(guò)對(duì)每個(gè)節(jié)點(diǎn)共享內(nèi)存的共同訪問實(shí)現(xiàn)節(jié)點(diǎn)內(nèi)通信，通過(guò)節(jié)點(diǎn)間消息傳遞實(shí)現(xiàn)節(jié)點(diǎn)間通信[79]。

MPI與OpenMp結(jié)合，可以通過(guò)分布式節(jié)點(diǎn)，有效利用處理器中不同內(nèi)核提高性能。該模式應(yīng)用MPI處理分布式存儲(chǔ)，利用OpenMP、Threading及TPL等架構(gòu)處理共享內(nèi)存。能夠在短時(shí)間內(nèi)對(duì)大數(shù)據(jù)進(jìn)行分析，使用多進(jìn)程多核技術(shù)中的增強(qiáng)技術(shù)，通過(guò)內(nèi)核間并行運(yùn)行代碼，利用消息傳遞接口在不同處理器間分配工作。

1總體架構(gòu)

本文設(shè)計(jì)了基于MPI與OpenMP的分布式動(dòng)態(tài)數(shù)據(jù)庫(kù)增量關(guān)聯(lián)規(guī)則挖掘的混合模式（見圖1）。該模式綜合了MPI與OpenMP優(yōu)點(diǎn)，MPI用于實(shí)現(xiàn)不同節(jié)點(diǎn)之間的消息通信，還能夠在多個(gè)節(jié)點(diǎn)上分配工作；OpenMP通過(guò)線程實(shí)現(xiàn)并行處理，能夠利用可用內(nèi)核，并行處理各節(jié)點(diǎn)。

工作思路如下：將分布式數(shù)據(jù)庫(kù)動(dòng)態(tài)數(shù)據(jù)通過(guò)MPI分配到不同工作節(jié)點(diǎn)，在每個(gè)節(jié)點(diǎn)內(nèi)部，分配的任務(wù)能夠通過(guò)OpenMP在內(nèi)核中并行運(yùn)行，分布式數(shù)據(jù)庫(kù)就能夠在多臺(tái)計(jì)算機(jī)上處理。此外，該方法可以檢測(cè)節(jié)點(diǎn)中的故障，并將工作重新分配給其它節(jié)點(diǎn)。對(duì)于數(shù)據(jù)庫(kù)中已有的關(guān)聯(lián)規(guī)則，包括頻繁項(xiàng)與次頻繁項(xiàng)規(guī)則，該方法只處理數(shù)據(jù)庫(kù)中新的事務(wù)更新關(guān)聯(lián)規(guī)則，不需要重新處理已有的數(shù)據(jù)庫(kù)事務(wù)。圖1中，該方法的輸出是全局?jǐn)?shù)據(jù)庫(kù)與本地?cái)?shù)據(jù)庫(kù)中更新的頻繁項(xiàng)及次頻繁項(xiàng)關(guān)聯(lián)規(guī)則。

圖1總體架構(gòu)

2工作流程

該方法是基于“主-從”（masterslave ）模式設(shè)計(jì)的，工作流程如圖2所示。主節(jié)點(diǎn)（或主處理器，又稱管理節(jié)點(diǎn)）起著管理器的作用，功能有5個(gè)：①將任務(wù)分配給不同從節(jié)點(diǎn)（或從處理器，又稱處理節(jié)點(diǎn)）；②監(jiān)測(cè)從節(jié)點(diǎn)工作狀態(tài)，檢測(cè)故障；③診斷發(fā)生故障的從節(jié)點(diǎn)，重新分配數(shù)據(jù)；④接收不同從節(jié)點(diǎn)處理完的數(shù)據(jù)；⑤執(zhí)行全局計(jì)算，生成全局關(guān)聯(lián)規(guī)則與本地關(guān)聯(lián)規(guī)則。

從節(jié)點(diǎn)功能也有5個(gè)：①讀取主節(jié)點(diǎn)分配任務(wù)；②使用OpenMP，以并行方式處理任務(wù)，生成候選項(xiàng)；③篩選候選項(xiàng)；④若發(fā)生故障，向主節(jié)點(diǎn)報(bào)警；⑤將處理結(jié)果返回主節(jié)點(diǎn)。

在整個(gè)工作過(guò)程中，該混合模式用一個(gè)主節(jié)點(diǎn)控制著多個(gè)從節(jié)點(diǎn)，主從之間沒有依賴關(guān)系。主節(jié)點(diǎn)讀取現(xiàn)有關(guān)聯(lián)規(guī)則信息，包括次頻繁項(xiàng)規(guī)則、頻繁項(xiàng)規(guī)則、支持度閾值、次頻繁項(xiàng)支持度閾值、置信度閾值、次置信度閾值。同時(shí)，它也讀取所有數(shù)據(jù)庫(kù)中新添加、修改及刪除任務(wù)的數(shù)量，通過(guò)式（1）生成要處理的允許事務(wù)最大數(shù)目（Mx），其中S表示支持度，PLS表示次頻繁項(xiàng)支持度閾值，DT表示總的現(xiàn)有數(shù)據(jù)庫(kù)事務(wù)。

Mx = （S-PLS）*DT（1）

圖2說(shuō)明了主節(jié)點(diǎn)與從節(jié)點(diǎn)之間的通信，它解釋了主節(jié)點(diǎn)如何給不同從節(jié)點(diǎn)分配工作，還解釋了主節(jié)點(diǎn)如何收集從節(jié)點(diǎn)信息。通過(guò)OpenMP框架使用可用內(nèi)核，使從節(jié)點(diǎn)能夠并行處理任務(wù)。表明該方法不重新處理原有數(shù)據(jù)庫(kù)事務(wù)，但它利用原有關(guān)聯(lián)規(guī)則信息，在數(shù)據(jù)庫(kù)更新后生成新的規(guī)則。

2.1具體流程

輸入：已有關(guān)聯(lián)規(guī)則信息、次頻繁項(xiàng)規(guī)則、頻繁項(xiàng)規(guī)則、支持度、次頻繁項(xiàng)支持度、置信度、次頻繁項(xiàng)置信度、新添加任務(wù)、新修改任務(wù)、已刪除任務(wù)及總事務(wù)記錄計(jì)數(shù)。

輸出：更新的頻繁項(xiàng)關(guān)聯(lián)規(guī)則及次頻繁項(xiàng)關(guān)聯(lián)規(guī)則。

（1）主節(jié)點(diǎn)讀取輸入信息。

（2）驗(yàn)證最大允許增量。

（3）通過(guò)MPI向從節(jié)點(diǎn)分配任務(wù)。

（4）各并行從節(jié)點(diǎn)接收主節(jié)點(diǎn)請(qǐng)求并開始讀取分配任務(wù)。

（5）從節(jié)點(diǎn)并行處理過(guò)程中，使用OpenMP添加、刪除、修改事務(wù)記錄。

（6）從節(jié)點(diǎn)為本地增量事務(wù)生成候選列表，并對(duì)候選項(xiàng)進(jìn)行分類。

（7）從節(jié)點(diǎn)驗(yàn)證生成候選列表，并且移除零計(jì)數(shù)候選項(xiàng)。由于一些候選項(xiàng)計(jì)數(shù)隨著新添加規(guī)則而增加，同時(shí)隨著記錄刪除與修改而減少，因此應(yīng)該移除零計(jì)數(shù)候選項(xiàng)，以減少傳遞給管理節(jié)點(diǎn)的候選項(xiàng)數(shù)，將降低通信與處理成本。

（8）根據(jù)以下情況生成基于候選項(xiàng)計(jì)數(shù)的關(guān)聯(lián)規(guī)則與次頻繁項(xiàng)規(guī)則。endprint

情況1：候選項(xiàng)數(shù)>支持度

候選項(xiàng)置信度>=次頻繁項(xiàng)置信度；

情況2：候選項(xiàng)數(shù)<次頻繁項(xiàng)支持度

候選項(xiàng)數(shù)>次頻繁項(xiàng)支持度

候選項(xiàng)置信度>=次頻繁項(xiàng)置信度。

（9）向主節(jié)點(diǎn)返回錯(cuò)誤狀態(tài)并生成候選列表。

（10）主節(jié)點(diǎn)檢查是否有錯(cuò)誤發(fā)生，如果出現(xiàn)錯(cuò)誤，則將錯(cuò)誤數(shù)據(jù)分發(fā)給其他成功從節(jié)點(diǎn)，并從步驟4開始重復(fù)運(yùn)行，然后記錄錯(cuò)誤，以防錯(cuò)誤仍然存在。

（11）主節(jié)點(diǎn)對(duì)從節(jié)點(diǎn)接收的所有候選項(xiàng)執(zhí)行全局計(jì)算。

（12）生成全局頻繁項(xiàng)及次頻繁項(xiàng)規(guī)則。

（13）輸出結(jié)果，并結(jié)束計(jì)算。

2.2主從節(jié)點(diǎn)工作流程描述

2.2.1主節(jié)點(diǎn)偽代碼

（1）Read Old Association Rules Mining Information；

//讀取已有的關(guān)聯(lián)規(guī)則信息

（2）Read and Validate Databases Size of New Incremental Records；

// 讀取并驗(yàn)證新增量記錄數(shù)據(jù)庫(kù)的大小

（3）Initialize MPI； //初始化MPI

（4）Distribute Database Records on Available Workers Nodes； //給空閑的工作節(jié)點(diǎn)分配數(shù)據(jù)庫(kù)記錄。

（5）for （i=1 to number of Slave Workers） do begin

//給所有的從節(jié)點(diǎn)分配任務(wù)

（6）{Send Slave Worker Process[i] （Database Location Starting Record Index and End Record Index；）} //給從節(jié)點(diǎn)i分配任務(wù)

（7）for （i=1 to number of Slave Workers Process） do begin {

（8）Receive Candidate Rules Count and Error Status from Process[i]；}

//接收從節(jié)點(diǎn)i的候選規(guī)則和錯(cuò)誤狀態(tài)。

（9）IF （Error Occurs） Then Distribute Records On Other Successful Slave Workers（）

//若有錯(cuò)誤，將記錄分配給空閑的從節(jié)點(diǎn)

（10）EndIF；

（11）For （i=1 to number of Slave Workers）

//接收所有從節(jié)點(diǎn)返回信息

{

（12）if （i is not in Failure slave worker） Then

（13）Receive Candidate Rules Count and Error Status. //接受候選項(xiàng)計(jì)數(shù)和錯(cuò)誤狀態(tài)

（14）EndIF；}

//若從節(jié)點(diǎn)沒有錯(cuò)誤，則接收候選規(guī)則和錯(cuò)誤狀態(tài)

（15）if （Error Status Exist）Then Log Error Details to User and

End Application； //若存在錯(cuò)誤，則將詳細(xì)的錯(cuò)誤傳給用戶和應(yīng)用程序

（16）ENDIF；

（17）Generate Large/Pre Large Local Association Rules； //生成局部關(guān)聯(lián)規(guī)則

（18）Generate Large/Pre Large Global Association Rules； //生成全局關(guān)聯(lián)規(guī)則

（19）Show Output Result； //輸出結(jié)果

（20）Finalize MPI； //結(jié)束MPI

（21）End

2.2.2從節(jié)點(diǎn)偽代碼

（1）DBInf：Database Information //定義數(shù)據(jù)庫(kù)信息

（2）SI：Start Records Index //定義記錄起始索引

（3）EI：End Records Index //定義記錄結(jié)束索引

（4）RL：New Record List //定義新記錄列表

（5）CL：Candidate Rules List //定義候選規(guī)則列表

（6）Initialize MPI //初始化MPI

（7）RL={Get Database Records From DBInf Starting From SI Till EI} //讀取數(shù)據(jù)庫(kù)記錄

（8）OpenMP Parallel For each Record R In RL

//并行處理讀取的數(shù)據(jù)庫(kù)記錄

（9）{update Candidate ListCL（R.RecordType）；

//更新候選記錄 }

（10）OpenMP Parallel For each Record C In CL

//并行篩選候選記錄

（11）{CL=Validate CandidateList（CL）；

//驗(yàn)證候選記錄 }

（12）if Error Code Then Send Error Informtion To Controller. //將錯(cuò)誤信息送至控制器endprint

（13）Send Candidate List CL to Controller.

//將候選列表送至控制器

（14）Finalize MPI //MPI完成工作

（15）return CL. //返回候選規(guī)則

（16）End

3實(shí)驗(yàn)

為了驗(yàn)證模型準(zhǔn)確性及處理時(shí)效性，在Windows環(huán)境下進(jìn)行了實(shí)驗(yàn)。集群由6臺(tái)機(jī)器組成，每臺(tái)機(jī)器CPU為2.4GHz，4G內(nèi)存，使用以太網(wǎng)組網(wǎng)，安裝Windows 2003。

測(cè)試中使用的原始數(shù)據(jù)庫(kù)是校園一卡通數(shù)據(jù)[10]，包含3 869 182個(gè)刷卡記錄，用于測(cè)試的第二個(gè)數(shù)據(jù)庫(kù)是教務(wù)系統(tǒng)數(shù)據(jù)，包含有學(xué)習(xí)論壇上352 168個(gè)記錄，增量記錄將31 000個(gè)記錄分布在多個(gè)數(shù)據(jù)庫(kù)上。在下列3種情況下分別進(jìn)行實(shí)驗(yàn)：①4臺(tái)計(jì)算機(jī)上執(zhí)行，1臺(tái)充當(dāng)主節(jié)點(diǎn)，另3臺(tái)充當(dāng)從節(jié)點(diǎn)；②6臺(tái)計(jì)算機(jī)上執(zhí)行，1臺(tái)充當(dāng)主節(jié)點(diǎn)，另5臺(tái)充當(dāng)從節(jié)點(diǎn)；③8臺(tái)計(jì)算機(jī)上執(zhí)行，1臺(tái)充當(dāng)主節(jié)點(diǎn)，另7臺(tái)充當(dāng)從節(jié)點(diǎn)。

由圖3可見，針對(duì)校園一卡通數(shù)據(jù)庫(kù)的31 000個(gè)增量新事務(wù)，同等條件下混合模型完成關(guān)聯(lián)規(guī)則挖掘比單一MPI所需處理時(shí)間少。

圖3校園一卡通數(shù)據(jù)庫(kù)處理時(shí)間（s）比較

由圖4可見，針對(duì)學(xué)習(xí)論壇數(shù)據(jù)庫(kù)的31 000個(gè)增量新事務(wù)，同等條件下混合模型完成關(guān)聯(lián)規(guī)則挖掘比單一MPI所需處理時(shí)間少。

由圖5可見，針對(duì)校園一卡通數(shù)據(jù)庫(kù)中添加31 000個(gè)增量記錄，同等條件下混合模型加速比單一MPI高。

實(shí)驗(yàn)結(jié)果表明，混合模型比現(xiàn)有方法處理速度快、性能強(qiáng)。

4結(jié)語(yǔ)

關(guān)聯(lián)規(guī)則是發(fā)現(xiàn)數(shù)據(jù)庫(kù)隱藏知識(shí)的一種重要方法，隨著硬件與軟件技術(shù)的發(fā)展，可以通過(guò)并行與分布式處理動(dòng)態(tài)數(shù)據(jù)方式提高關(guān)聯(lián)規(guī)則挖掘的性能。本文提出的基于MPI與OpenMP的分布式動(dòng)態(tài)數(shù)據(jù)庫(kù)增量關(guān)聯(lián)規(guī)則挖掘方法，在大數(shù)據(jù)環(huán)境下高風(fēng)險(xiǎn)學(xué)生預(yù)測(cè)研究應(yīng)用中取得了良好效果[11]。

參考文獻(xiàn)參考文獻(xiàn)：

[1]ZEIAD ELSAGHIR， HAMDY KELASH，SAYED ELNAZLY. Parallel implementation of smithwaterman algorithm using MPI， openMP and hybrid model[M]. Bhopal：Blue Eyes Intelligence Engineering & Sciences Publication Pvt. Ltd，2014.

[2]P FOURNIERVIGER，A GOMARIZ， M CAMPOS，et al. Fast vertical sequential pattern mining using concurrence information[C].In Proc. 18th PacificAsia Conf. Knowl. Discovery Data Mining，2014.

[3]SDD P FOURNIERVIGER，U FAGHIHI，R NKAMBOU.An efficient algorithm for mining sequential rules common to several sequences [J]. Knowl Based Syst.，2012，25（1）：6376.

[4]CHUNWEI LIN，GUOCHENG LAN，TZUNGPEI HONG. An incremental mining algorithm for high utility itemsets[J]. Expert Systems with Applications，2012（39）：71737180.

[5]余小高.電子商務(wù)環(huán)境中分布式數(shù)據(jù)挖掘的研究[M].武漢：湖北人民出版社，2008.

[6]崔妍，包志強(qiáng).關(guān)聯(lián)規(guī)則挖掘綜述[J].計(jì)算機(jī)應(yīng)用研究，2016，33（2）：330334.

[7]余小高.電子商務(wù)智能推薦系統(tǒng)研究[M]. 武漢：湖北人民出版社，2012.

[8]崔亮，郭靜，吳玲達(dá).一種基于動(dòng)態(tài)散列和事務(wù)壓縮的關(guān)聯(lián)規(guī)則挖掘算法[J].計(jì)算機(jī)科學(xué)，2015，42（9）：4144.

[9]郝海濤，馬元元.應(yīng)用Aprior算法實(shí)現(xiàn)大規(guī)模數(shù)據(jù)庫(kù)關(guān)聯(lián)規(guī)則挖掘的技術(shù)研究[J].現(xiàn)代電子技術(shù)，2016，39（7）：124126.

[10]余小高，余小鵬.大數(shù)據(jù)環(huán)境下高校學(xué)生作息規(guī)律判斷方法研究[J].中國(guó)教育信息化，2017，8（15）：14.

[11]余小高，余小鵬.基于時(shí)間軸的高校學(xué)生基本特征值分析[J].教育觀察，2017，6（13）：1214.

責(zé)任編輯（責(zé)任編輯：何麗）endprint