分布式動態數據庫增量關聯規則挖掘研究

余小高 魯群志

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

關鍵詞：關聯規則；分布式數據庫；動態數據

DOIDOI：10.11907/rjdk.171746

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

0引言

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

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

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

1總體架構

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

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

圖1總體架構

2工作流程

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

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

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

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

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

2.1具體流程

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

輸出：更新的頻繁項關聯規則及次頻繁項關聯規則。

（1）主節點讀取輸入信息。

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

（3）通過MPI向從節點分配任務。

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

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

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

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

（8）根據以下情況生成基于候選項計數的關聯規則與次頻繁項規則。endprint

情況1：候選項數>支持度

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

情況2：候選項數<次頻繁項支持度

候選項數>次頻繁項支持度

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

（9）向主節點返回錯誤狀態并生成候選列表。

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

（11）主節點對從節點接收的所有候選項執行全局計算。

（12）生成全局頻繁項及次頻繁項規則。

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

2.2主從節點工作流程描述

2.2.1主節點偽代碼

（1）Read Old Association Rules Mining Information；

//讀取已有的關聯規則信息

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

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

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

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

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

//給所有的從節點分配任務

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

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

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

//接收從節點i的候選規則和錯誤狀態。

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

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

（10）EndIF；

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

//接收所有從節點返回信息

{

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

（13）Receive Candidate Rules Count and Error Status. //接受候選項計數和錯誤狀態

（14）EndIF；}

//若從節點沒有錯誤，則接收候選規則和錯誤狀態

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

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

（16）ENDIF；

（17）Generate Large/Pre Large Local Association Rules； //生成局部關聯規則

（18）Generate Large/Pre Large Global Association Rules； //生成全局關聯規則

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

（20）Finalize MPI； //結束MPI

（21）End

2.2.2從節點偽代碼

（1）DBInf：Database Information //定義數據庫信息

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

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

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

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

（6）Initialize MPI //初始化MPI

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

（8）OpenMP Parallel For each Record R In RL

//并行處理讀取的數據庫記錄

（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. //返回候選規則

（16）End

3實驗

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

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

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

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

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

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

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

4結語

關聯規則是發現數據庫隱藏知識的一種重要方法，隨著硬件與軟件技術的發展，可以通過并行與分布式處理動態數據方式提高關聯規則挖掘的性能。本文提出的基于MPI與OpenMP的分布式動態數據庫增量關聯規則挖掘方法，在大數據環境下高風險學生預測研究應用中取得了良好效果[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]余小高.電子商務環境中分布式數據挖掘的研究[M].武漢：湖北人民出版社，2008.

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

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

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

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

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

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

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