基于关联规则的Apriori改进算法的研究综述

彭新宇 李丛煊 郭金盈 赫彦文

摘要：关联规则挖掘是数据挖掘的重要技术之一，Apriori算法作为关联规则的基本算法，简单、易理解、数据要求低，但是存在效率低的问题，效率低的原因有两点，Apriori算法1/0负载较大且会产生庞大的候选集，一些研究人员针对这些问题提出了等转换数据存储方式、减少扫描数据库次数等改进方法，由此介绍近几年研究人员对Apriori改进算法的研究概况，并对关联规则的Apriori算法未来的研究方向进行了探讨。

关键词：大数据;数据挖掘;关联规则;Apriori算法改进

中图分类号：TP3

文献标识码：A

文章编号：1009-3044（2019）34-0216-02

数据挖掘一般是指从大量的数据中挖掘隐藏于其中的有着特殊关系性。关联规则为数据挖掘的重要技术，该技术通过大型关系数据集中发现数据项之间的相关性。关联规则的挖掘过程分为两个阶段：第一个阶段从大量的数据集中选出达到要求的候选项集合，第二个阶段从候选项集合中发现符合要求的频繁项集，最终便得到有关联的项集并产生关联规则，在核心思想的指导下，Apriori算法应运而生，Apriori算法是一种发现频繁项集的基本算法，这个算法存在两个方面的问题，一个方面是多次扫描事务数据库，1/0负载很高，另一个方面生成候选集时，候选集的数量呈指数式增长，是可能生成庞大的候选集[1]，因此Apriori算法存在进步的空间，基于以上背景，国内外的许多研究人员提出了Apriori改进算法并将改进算法投入到应用中，改进包括对算法、数据、平台等方式的改进，接下来会对Apriori算法不同改进方式的研究概况进行介绍。

1 基于Apriori算法本身的改进，减少扫描次数

为解决需要频繁扫描事务集的问题，有的研究人员也采用了基于累加数组的方法来获得频繁项集，该方法根据事务集生成一维数组，在生成数组的同时就能统计出支持度并生成频繁l一项集（1]，任意两两频繁1-项集的数组，对应项做累加求和运算得到候选集L2，统计出支持度并生成2-项集，对上述过程迭代循环，最终得到符合要求的所有频繁项集。改进算法只需要扫描事务集一次，通过建模公式减少了剪枝这个步骤，通过公式计算的方式减少了候选项集。

Apriori算法中扫描数据库计数部分所占时间比例最大，其次是项集连接和筛选剪枝，故优先减少扫描计数在整个算法中的时间开销，有的研究人员在改进算法中对计算候选项集支持度的部分做出改进，扫描计数阶段的时间复杂度增加了一个变量，变量和迭代次数成反比关系，即随着迭代次数的增加，目标事务在事务数据库中所占的比例越来越小，时间复杂度随之下降[2]。稀疏型数据中，变量的下降速度会非常快，因此处理稀疏型数据的效果较好。

2 转换存储方式的改进

2.1 基于前缀项集的存储方式改进

Apriori算法不断进行查找进行连接，浪费了大量时间，查找效率低，因此有研究人员提出利用哈希表可以快速查找的特性，采用前缀项集的存储方式来提高算法中生成候选集与频繁项集的查找效率[3]，对于数据项集，采用类似Map结构的哈希表来保存，生成候选集Ln时，其中key代表前缀n-l项的数据值，value代表第n项数据值，在连接步中，对有相同前缀的value值中任意两个项进行合并，即可得到新的候选集，在剪枝步中，因频繁项集的子集也必须是频繁项集，故只考虑（k+1）一项候选集中同时包含用于连接的两个k一项集尾项的可能的k一项子集即可，再遍历原始数据库，找出满足最小支持度的频繁项集，该过程进行迭代即可得到最终的关联项集，该存储方式使得在连接步骤和剪枝步骤的运行时间有了很大程度的降低。

2.2 基于矩阵的存储方式改进

基于矩阵的Apriori算法也是对数据存储方式的改进，该算法将事务数据库D转换为矩阵。每一事务以矩阵的行来表示即行维度，事务中的项用列来表示即列维度，当要对数据进行挖掘时就可以直接调用转换为矩阵中的信息[4]，在行列指定的位置处若存在数据则为1，否则记为0，修改矩阵中对应位置的频次，计算出各项的支持度得到候选集，删除事务长度小于最小置信度的事务对应的行与列。免去了對D再次扫描的过程，节省了1/0的开销和时间。在基于矩阵的Apriori算法上，有的研究人员进一步进行改进，将矩阵看成是行向量的集合，根据向量的操作规则，在矩阵中只需要使用“与”操作就可以快速地产生项目集的支持频度[4]，这两种基于矩阵的改进算法都只需对事务数据库扫描两次，但前者会产生大量临时键值对，后者临时键值对较少，高效利用了并行化，更好地提高了算法的效率。

3 基于减少数据的改进

对于指定行业的数据挖掘关联规则算法改进，例如医院的大数据等，有明显的行业数据特点，根据行业的数据特点与属性产生关联规则，对信息进行提取，确定医疗大数据中项集间的关联关系，同样能提高医疗大数据预处理的水平[5]。

对大批量的原始数据集首先进行清洗，清除无效、噪音数据，使得原始数据得到一定程度的减少并结合数据挖掘的分类方法[6]，采用决策树的分类算法对原始数据集进行分类，为数据找到一种准确的模型进行分块处理，从分层的大量数据随机抽取样本，从每层数据中抽取出简单随机均值方差为指定值的样本作为数据集，将数据分为多块，对每一块的数据集扫描出每块的频繁项集，集合所有的局部频繁项集，扫描一次频繁项集，构成候选项集得到频繁项集，从频繁项集中获取关联规则，从中得到有价值的关联规则。

4 基于平台与编程模型的改进

有的研究人员针对关联规则挖掘1/0负载严重与内存受限的问题，提出利用Hadoop平台编程模型MapReduce实现并行化的方法来改进关联规则算法[7]，Hadoop平台具有可靠性、扩展性、高效性、容错性等优点，MapReduce是对大规模数据进行并行计算的一种编程模型和计算框架，封装了并行处理、数据分布、负载均衡等复杂的细节，在Hadoop平台上运行MapRe-duce程序时，若某一个节点计算失败，Hadoop系统会把它的计算任务重新分配到其他计算节点，利用Map0和Reduce0来从海量数据中快速寻找出频繁项集，在Map阶段主要利用k-l项频繁项集的连接操作得出候选项集，计算其读取的部分数据中的k项候选集的支持数，在Reduce阶段主要将相同key的值合并，并且进行剪枝操作，筛选符合要求的频繁项集，通过k次迭代计算频繁项目集。由频繁项集生成关联规则，使Apriori算法处理海量数据不再受到单机运算能力的限制。

但是上述改进办法仍存在一些缺陷，MapReduce编程框架只能保存到Hadoop分布式文件系统中，每次提交计算任务时都需重启资源，MapReduce编程框架不适合多次迭代，需要多次遍历原始数据集，仅考虑了频繁项集的计算并未考虑强关联规则的挖掘，因此有的研究人员基于以上的研究做出了进一步的改进，针对之前的研究未将强关联规则的挖掘考虑的问题提出了解决方法，将频繁项目集数据导人支持高速读取的Redis数据库中，从而实时获取任何频繁项集支持度嘲，该改进方式更适用于大型的数据集。

Spark是对早前Map-Reduce编程框架的扩展，相较于Ma-pReduce，Spark机制对处理大数据集以及数据迭代更具有优势，基于Spark的性能优势，有的研究人员利用分布式框架Spark解决单机内存资源限制、性能缺陷的问题[9]，增强了强关联规则挖掘时数据的实时性，从整体上提高了关联规则挖掘的效率。

5 总结

从上述的改进方式可以看出，对Apriori算法的改进由原来对算法本身的改进逐步转变为对数据集的存储方式的改进，并利用一些框架进行提升效率，这些改进使得Apriori算法的效率大幅度提升，接下来的研究方向可能转向与其他算法、技术的融合或各种改进方式综合使用，例如利用平台的优势.结合遗传、分类等算法对Apriori算法进行改进提升，Apriori算法是否还有上升进步的空间，我们拭目以待。

参考文献：

[1]陈维兴，曲睿，孙毅刚，基于改进Apriori算法的地面空调间歇故障预测[J].计算机应用，2016，36（12）：3505-3510.

[2]徐开勇，龚雪容，成茂才.基于改进Apriori算法的审计日志关联规则挖掘[J].计算机应用，2016，36（07）：1847-1851.

[3]于守健，周羿阳.基于前缀项集的Apriori算法改进[J]，计算机应用与软件，2017，34（02）：290-294.

[4]谢志明，王鹏.基于MapReduce架构的并行矩阵Apriori算法[J].计算机应用研究，2017，34（02）：401-404.

[5]岳根霞.基于关联规则的医疗大数据挖掘算法[J].微电子学与计算机，2019，36（04）：105-108.

[6]朱付保，白庆春，汤萌萌，等.基于改进Apriori算法的铁路轨道质量分析与评价[J].微电子学与计算机，2015，32（10）：159-162.

[7]刘丽娟，改进的Apriori算法的研究及应用[J].计算机工程与设计，2017，38（12）：3324-3328.

[8]王英博，马菁，柴佳佳，等.基于Hadoop平台的改进关联规则挖掘算法[J].計算机工程，2016，42（10）：69-74+79.

[9]李融，杨淙钧，高泽，等.基于Spark的精准关联规则挖掘算法实现[J].信息技术，2018（02）：153-158.

[10] S.M. Shafaei，M. Loghavi，S. Kamgar. Feasibility of implemen-tation of intelligent simulation configurations Based on datamining methodologies for prediction of tractor wheel slip[Jl. In-formation Processing in Agriculture，2019，6（2）.

【通联编辑：王力】

收稿日期：2019-08-26

基金项目：硕士研究生创新资助项目（校级项目，编号：YKY-2019-07）

作者简介：彭新宇（1996-），女，河北衡水人，北华航天工业学院在读硕士研究生，主要研究方向为计算机应用技术，软件测试;李丛煊（1996-），女，河北石家庄人，北华航天工业学院在读硕士研究生，主要研究方向为计算机应用技术，软件测试;郭金盈（1996-），女，河北沧州人，北华航天工业学院在读硕士研究生，研究方向为计算机应用技术，遥感信息安全;赫彦文（1997—），女，河北张家口人，北华航天工业学院在读硕士研究生，研究方向为计算机应用技术，软件测试。