大型数据库的关联挖掘算法设计

黄瑜

摘 要： 针对大型数据库在进行关联挖掘过程中，挖掘准确度低、效率差的问题，提出并设计了基于贝叶斯信息标准BIC评分函数的大型数据库关联挖掘算法。在对大型数据库关联数据获取基础上，采用贝叶斯信息标准BIC评分函数对数据进行预处理，并给出预处理流程，建立挖掘所需的新关联规则，根据其关联规则实现大型数据库的关联挖掘。实验结果表明，采用改进挖掘算法，其挖掘准确率达到了91.3%，相比传统挖掘算法提高了约35.9%，具有一定的优势。

关键词： 大型数据库； 关联规则； 挖掘算法； 关联挖掘； 评分函数； 数据预处理

中图分类号： TN919.25?34； TP301.6 文献标识码： A 文章编号： 1004?373X（2018）20?0045?04

Abstract： In allusion to the problems of low mining accuracy and poor mining efficiency during the association mining process of the large?scale database， an association mining algorithm based on the Bayesian information standard BIC scoring function is proposed and designed for the large?scale database. On the basis of association data acquisition of the large?scale database， the data is preprocessed by using the Bayesian information standard BIC scoring function， the preprocessing flow is given， new association rules needed in mining are established， and the association mining of the large?scale database is realized according to the association rules. The experimental results show that the improved mining algorithm achieves a mining accuracy of 91.3%， which improves approximately 35.9% in comparison with the traditional mining algorithm and has a certain advantage.

Keywords： large?scale database； association rule； mining algorithm； association mining； scoring function； data preprocessing

0 引 言

当今，数据容量规模的扩大，导致数据规模扩大、复杂化，人们无法快速找到感兴趣的数据，对于此类爆炸式增长的数据，人们进行数据处理以及数据分析的能力非常有限。因此，数据挖掘技术得到了广泛重视及深入研究，逐步成为重要研究领域[1?2]。

数据挖掘即从大量不完全、有噪声、模糊随机数据中获取包含有人们事先不知道又潜在有用信息及知识处理进程[3]。该方法之所以被称为未来信息处理重要技术之一，关键是它以一种全新概念转变着人类使用数据的模式。但数据库技术作为一种最基础的信息储存及管理形式，依旧以联机事务处理为重点使用，对决策、解析、预测等高级性能的支持技术较少。关联规则挖掘是数据挖掘的一个重要分支，广泛应用在多个领域，如数据分析、数据库设计、仓储规划、网络故障解析等[4?5]，导致已有的数据库规模迅速扩大，对大规模数据库关联规则挖掘的研究成为了该领域具备关键理论价值及现实意义事件。对此，提出并设计了基于贝叶斯信息标准BIC评分函数的大型数据库关联挖掘算法。

1 数据库关联数据分析

在对大型数据库进行关联挖掘过程中，其数据库的获取及数据预处理是影响关联挖掘的关键步骤。对此，在数据库获取后，对数据进行预处理过程中，采用自适应函数对其进行分析，提高大型数据库数据性能，为进行关联挖掘提供基础依据。

1.1 数据库获取分析

数据库还原模块在运行时，首先将运行环境初始化，包括环境变量初始化、配置文件初始化、公共变量和数据缓存初始化[6]。然后进行网络设备初始化，最后创建数据库还原模块的工作线程，包括数据流还原线程、拦截数据包线程和数据包处理分析调度线程[7]。拦截数据包线程的主要功能是拦截网上的数据包，数据流还原线程的主要功能是还原网络数据包，并将还原结果存入数据库还原模块的数据库中。数据包处理分析调度线程主要对不同的数据包进行调度。

数据获取中主要获取内容是相关数据来源记录信息、具体数据特征、获取数据所需时间等。实现这一目标的方式有很多种，其主要依据是借助各种途径，对数据进行采集。

1.2 数据库关联数据预处理

数据库数据量较大，若要增加挖掘效率，实现挖掘的目的，要对数据提前进行一定处理，即预处理，重点包括数据采集、整理、选择、转存等流程。在数据整理方面，重点是对具有冗余特征的数据删除、对类似数据项进行合并、筛查修正数据信息等[7]。在此之后进行集体的筛选处理，把来自不同源点的数据汇集起来，对数据进行筛查，找出适合搜寻需求的数据种类[8]。最后对数据进行转换，把最终得到的数据对应地进行适应度函数调整、转变成更适合使用的格式，方便进行关联挖掘解析。

在进行关联数据预处理过程中，把网络结构学习作为最优化问题，对挖掘目标进行搜索评分。对此采用较为常用的评分函数有贝叶斯信息标准BIC评分函数，对数据进行预处理。该评分函数具备以下几个优点[9]：一是不依附先验概率，不对先验概率分布情况进行估计；二是在样本集合过大时，能夠近似地对后验概率进行验证；三是在没有规定多项式分布及Dirichlet先验概率情况下，和MDL测度取负号的结果近似相等。因此，在本算法中使用BIC评分函数作为适应度函数，并认为BIC的得分越高，适应度越好，为后续的关联挖掘提供基础。BIC评分函数如下：

在数据关联挖掘中，若每个部分均要给出相应的挖掘规则、频繁集等，则需对选取范围进行确认，并建立对应向量，采用普通的安全多方循环协议进行集合的合并。为了增加预处理的安全性能，采用基于可交换密钥顺序方法进行安全加密处理。在共享的状况下，能够采用其余方式进行可交换加密[10]。数据库预处理流程如图1所示，数据库关联挖掘系统结构图如图2所示。

2 关联挖掘算法优化研究

在进行大数据关联挖掘算法优化过程中，首先对数据进行一次扫描，搜出整体的频繁1_项集；然后对搜出的频繁1_项集进行组合，依次产生频繁2_项集、频繁3_项集等。

关联挖掘算法优化流程图如图3所示。

在上述伪代码显示的过程中，采用“动态系统扩散”的方式从数据库中形成一个基集，用基集替换初始数据集当作挖掘目标，计算支持度函数，获取各项集支持度，搜出全部支持度大于支持度阈值的频繁项集，形成全部的关联规则。

3 系统性能测试

3.1 系统性能评估方法

实验采用系统仿真的方式对算法有效性进行验证，实验环境如下。

系统硬件采用4 核1.66 GHz的CPU；RAM 10 GB。系统操作系统采用Windows 2010 Server；源数据库使用默认.dat二进制的数据；输出文件为.txt文本文件；以VC++ 6.0 sp6 编制为实验程序；实验期间断开网络连接，防止出现误差；每一次实验后对系统内存进行整理，让每一次程序运行环境尽量统一。

3.2 结果分析

准确率对比结果如图4所示。

由图4可知，采用传统挖掘算法进行数据库挖掘时，在时间不定的情况下，其挖掘准确率随着时间的增加出现下降的趋势，准确率最高达到73.4%，最低为50.8%，平均准确率约为56.4%；采用改进方法时，随着时间的增加，其挖掘准确率具有上升趋势，准确率最高达到99.4%，最低为80.1%，平均值约为91.3%，相比传统挖掘算法提高了约34.9%，具有一定的优势。

4 结 论

针对传统挖掘算法一直存在挖掘准确率低、效率差的问题，提出基于贝叶斯信息标准BIC评分函数的大型数据库关联挖掘算法。实验结果表明，采用改进算法相比传统挖掘算法准确率提高了约34.9%，具有显著优势。

参考文献

[1] 张忠林，田苗凤，刘宗成.大数据环境下关联规则并行分层挖掘算法研究[J].计算机科学，2016，43（1）：286?289.

ZHANG Zhonglin， TIAN Miaofeng， LIU Zongcheng. Parallel hierarchical association rule mining in big data environment [J]. Computer science， 2016， 43（1）： 286?289.

[2] 郝海涛，马元元.应用Aprion算法实现大规模数据库关联规则挖掘的技术研究[J].现代电子技术，2016，39（7）：124?126.

HAO Haitao， MA Yuanyuan. Using Aprion algorithm to implement association rule mining technology of large?scale database [J]. Modern electronics technique， 2016， 39（7）： 124?126.

[3] 刘平，王晓，刘春.小差异化图像数据库中的特定特征挖掘方法设计[J].沈阳工业大学学报，2017，39（5）：562?566.

LIU Ping， WANG Xiao， LIU Chun. Design of specific feature mining method in image database with small alienation [J]. Journal of Shenyang University of Technology， 2017， 39（5）： 562?566.

[4] 杨小琴.大型数据库中的并行高效检测方法仿真分析[J].计算机仿真，2016，33（7）：392?394.

YANG Xiaoqin. Simulation analysis of parallel and efficient detection method in large database [J]. Computer simulation， 2016， 33（7）： 392?394.

[5] 赵学健，孙知信，袁源.基于预判筛选的高效关联规则挖掘算法[J].电子与信息学报，2016，38（7）：1654?1659.

ZHAO Xuejian， SUN Zhixin， YUAN Yuan. An efficient association rule mining algorithm based on prejudging and screening [J]. Journal of electronics & information technology， 2016， 38（7）： 1654?1659.

[6] 徐春，李广原，王玄，等.一种基于倒排索引树的增量更新关联挖掘算法[J].计算机工程与科学，2016，38（5）：1039?1045.

XU Chun， LI Guangyuan， WANG Xuan， et al. An incremental updating association rule mining algorithm based on inverted index tree [J]. Computer engineering and science， 2016， 38（5）： 1039?1045.

[7] 朱益立，邓珍荣，谢攀.基于有向无环图的频繁模式挖掘算法[J].计算机工程与设计，2017，38（5）：1237?1241.

ZHU Yili， DENG Zhenrong， XIE Pan. Mining frequent itemsets algorithm based on directed acycline graph [J]. Computer engineering and design， 2017， 38（5）： 1237?1241.

[8] 张亚玲，王婷，王尚平.增量式隱私保护频繁模式挖掘算法[J].计算机应用，2018，38（1）：176?181.

ZHANG Yaling， WANG Ting， WANG Shangping. Incremental frequent pattern mining algorithm for privacy?preserving [J]. Journal of computer applications， 2018， 38（1）： 176?181.

[9] 林基明，班文娇，王俊义，等.基于并行遗传?最大最小蚁群算法的分布式数据库查询优化[J].计算机应用，2016，36（3）：675?680.

LIN Jiming， BAN Wenjiao， WANG Junyi， et al. Query optimization for distributed database based on parallel genetic algorithm and max?min ant system [J]. Journal of computer applications， 2016， 36（3）： 675?680.

[10] 林凌，许然.基于图像特征细化的海量数据挖掘系统设计与实现[J].现代电子技术，2016，39（24）：113?115.

LIN Ling， XU Ran. Design and implementation of mass data mining system based on image feature refinement [J]. Modern electronics technique， 2016， 39（24）： 113?115.