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

余小高 魯群志

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

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

DOIDOI：10.11907/rjdk.171746

中圖分類號：TP391文獻標識碼：A文章編號：16727800（2017）010016604

0引言

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

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

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

1總體架構

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

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

圖1總體架構

2工作流程

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

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

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

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

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

2.1具體流程

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

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

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

（2）驗證最大允許增量。

（3）通過MPI向從節(jié)點分配任務。

（4）各并行從節(jié)點接收主節(jié)點請求并開始讀取分配任務。

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

（6）從節(jié)點為本地增量事務生成候選列表，并對候選項進行分類。

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

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

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

候選項置信度>=次頻繁項置信度；

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

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

候選項置信度>=次頻繁項置信度。

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

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

（11）主節(jié)點對從節(jié)點接收的所有候選項執(zhí)行全局計算。

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

（13）輸出結果，并結束計算。

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

2.2.1主節(jié)點偽代碼

（1）Read Old Association Rules Mining Information；

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

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

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

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

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

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

//給所有的從節(jié)點分配任務

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

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

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

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

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

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

（10）EndIF；

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

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

{

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

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

（14）EndIF；}

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

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

End Application； //若存在錯誤，則將詳細的錯誤傳給用戶和應用程序

（16）ENDIF；

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

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

（19）Show Output Result； //輸出結果

（20）Finalize MPI； //結束MPI

（21）End

2.2.2從節(jié)點偽代碼

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

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

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

（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ù)據庫記錄

（8）OpenMP Parallel For each Record R In RL

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

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

//更新候選記錄 }

（10）OpenMP Parallel For each Record C In CL

//并行篩選候選記錄

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

//驗證候選記錄 }

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

（13）Send Candidate List CL to Controller.

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

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

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

（16）End

3實驗

為了驗證模型準確性及處理時效性，在Windows環(huán)境下進行了實驗。集群由6臺機器組成，每臺機器CPU為2.4GHz，4G內存，使用以太網組網，安裝Windows 2003。

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

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

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

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

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

實驗結果表明，混合模型比現(xiàn)有方法處理速度快、性能強。

4結語

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

參考文獻參考文獻：

[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]余小高.電子商務環(huán)境中分布式數(shù)據挖掘的研究[M].武漢：湖北人民出版社，2008.

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

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

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

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

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

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

責任編輯（責任編輯：何麗）endprint