分布式动态数据库增量关联规则挖掘研究

余小高 鲁群志

摘要：为了解决分布式动态数据库关联规则挖掘效率低的问题，利用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