基于频集的Apriori关联规则算法的应用研究

沈慧娟 曹晓丽

摘 要：大数据时代，数据被源源不断地创造着，人们逐渐陷入“数据丰富而信息贫乏”的尴尬境地。那么，如何从繁杂的大数据中找出有价值的信息和知识成为人们的迫切需求。文章从数据挖掘的意义及关联规则算法演变入手，对关联规则中较为典型的Apriori算法进行了深入分析与研究，详细阐明了Apriori算法的基本思想及挖掘过程，利用Apriori算法对电大系统1 369位学生关于网上教学满意度的调研数据进行挖掘分析，经历了数据扫描、计数、比较、剪枝、连接等一系列操作，找出了数据间的強关联规则，并由此推出数据关系，为改进网上教学提供了很好的参考依据。

关键词：Apriori;关联规则;数据挖掘;剪枝;强关联;C++

中图分类号：TP311文献标识码：A文章编号：2095-1302（2020）10-00-05

0 引 言

大数据时代，伴随着计算机软硬件及数据库技术的飞速发展，人类积累的数据量正呈指数级增长，并曾一度因数据分析技术缺乏和数据质量不符合要求而产生“数据丰富而信息贫乏”的现象。能够解决这一现象的有效方法[1]便是数据挖掘（Data Mining），即从大型数据库中的大量原始数据中提取出人们感兴趣的、隐含的、未知的、具有潜在价值的信息和知识。

如今，关联规则是数据挖掘研究的一个重要分支，学会数据挖掘的一个重要问题就是从数据中发现关联规则[2]。IBM公司Almaden研究中心的R.Agrawal等人于1993年首先提出关联规则挖掘概念[3]及相关算法。关联规则挖掘算法成为数据挖掘领域的研究热点，亦是数据挖掘的重要分支，被学术界广泛深入研究，目前获得了长足的发展。

1 关联规则挖掘算法的形式化定义

设T={T1， T2， ...， Tm}是一个构成关联规则事务数据库（Transaction Database）[5]的事务集，其中Ti（i=1， 2， ...， m）表示T的第i条记录;I={I1， I2， ...， In}是T中所有项的集合，包含k（k=1， 2， ...， n）个项的项集是k-项集，即I的一个子集与一个唯一的标识符T_id相联系。

关联规则是形如X→Y的蕴涵式，其中XI，YI，且X∩Y=?。

2 关联规则挖掘算法的发现步骤

若人为设定一个最小支持度阈值min_sup和一个最小置信度阈值min_conf，则支持度不小于min_sup的项集为频繁项集（或频集），置信度不小于min_conf的规则为强关联规则。

发现关联规则的步骤即首先找出所有频集，然后再由这些频集产生满足最小置信度阈值[9]的强关联规则。

3 关联规则挖掘算法的演变

关联规则的第一个算法AIS[4]是Agrawal等人提出关联规则模型时给出的求解算法，基本思想是通过扫描事务数据库产生频集并计数[5]，若上一步的频集出现在被扫描的当前事务中，则用事务中的项扩展这些项集获得新的候选集，但该算法的一大缺陷是产生了过多的小候选集。之后，Cumulate和Stratify，Houstsma等人提出用SQL语句计算频集的关联规则算法—SETM算法[4]，基本思想是将候选的产生与计数分开，用SQL中的JOIN操作产生候选，然后以线性结构保存候选副本及产生事务的T_id，并以此获得事务包含的频集，这是一种将关联规则挖掘转化为SQL语句执行的算法。

用AIS和SERM算法构造候选项集时需要通过扫描数据库得到，而数据库中的非频繁项集较多，寻找出频集必须扫描不需要的非频集，因此浪费了大量的时间和空间，导致挖掘效率不理想。为改进该算法，1994年Agrawal等人又设计出一个新的关联规则算法—Apriori[6]，该算法依据频集的所有非空子集也必频繁的特性，通过连接和剪枝逐步缩小数据量的方法找出频集，节省了时间和空间，提高了挖掘效率，成为关联规则挖掘算法中的经典。

随后的几年，一些研究人员又在Apriori算法的基础上进行了深入研究和分析，陆续产生了FP-Tree，GSP，CBA等一系列改进算法，进一步提高了执行效率，为关联规则挖掘技术的应用奠定了基础。

4 基于频集的Apriori算法描述与C++实现

Apriori算法的核心问题是获得频繁项集，采用逐层搜索迭代法[7]，描述如下：

（1）给定min_sup和min_conf，并输入数据库;

（2）扫描数据库中的所有数据项，得到候选1-项集，计算所有项的支持度[8]，剔除所有支持度小于min_sup的项，得到频繁1-项集，记作L1;

（3）对L1执行连接操作，即L1 JOIN L1，得到候选2-项集，同样计算所有项的支持度，剔除所有支持度小于min_sup的项，得到频繁2-项集，记作L2;

（4）按步骤（3）重复执行，直到频繁项集为空。

算法流程如图1所示。

用C++实现可形式化描述：

class Apriori{

private：

//存储所有事务及其项

map >Ti;

//存储频繁项集

map，unsigned int> Li;

Unsigned int n;//事务数

Unsigned int min_sup;//最小支持度

public：

//构造函数，给定事务数及最小支持度

Apriori（unsigned int is=0，unsigned int mv=0）

{  n=is;  min_sup=mv; }

void Input_T（）;//输入所有事务的项集

//找出频繁项集

map，unsigned int> find_L（）;

//连接频繁k-1项集，得到频繁k项集

map，unsigned int> apri_gen（unsigned int K，map，unsigned int>Li）;

//输出频繁项集

void Output_T（unsigned int K，map，unsigned int> outmap）;

};

上述过程中，找出频繁项集是Apriori算法的关键[6]。寻找频繁项集的过程实际上是对项集的子集进行搜索并判断其是否满足最小支持度的过程。逻辑上，可以将频繁项集的生成过程组织成一棵树，然后以一定的方法遍历该树，并适当剪枝[10]，根据给定的最小支持度，由频繁k-1-项集生成频繁k-项集，直到频集为空。

最后，从每个频繁项集L中找到非空子集x，对每个x得到一条关联规则“x→L-x”，计算并比较它们的置信度，不低于min_conf的关联规则为强关联规则[11]。

以某超市某天的一个简单交易清单为例（表1），该表形象地说明了Apriori算法的执行过程，清单中包括5个事务和5个项，即i1，i2，i3，i4，i5。

首先，扫描数据库，得出各项的支持度计数分别为4，2，3，3，2，由项集的支持度指定项集的支持度计数与事务总数的比值[12]，得到表2所列候选1-项集C1的支持度。

将Support与min_sup比较，剔除所有小于min_sup的项集，若给定min_sup=0.5，可得到表3所列的频繁1-项集L1及支持度。

连接L1L1，得出表4所列的候选2-项集及支持度。

将Support与min_sup比较，剔除所有小于min-sup的项集，便得到表5所列的频繁2-项集L2及支持度。

上述操作需经历连接和剪枝[13]，其中连接的原则是保证前k-2项相同，犹如下列代码：

select p.i1，p.i2，…，p.ik-1，q.ik-1

from Lk-1.p，Lk-1.q

where p.i1=q.i1，…，p.ik-2=q.ik-2，p.ik-1

剪枝是剔除所有小于min-sup的项集，用以确保任一频集的所有非空子集亦频繁。图2所示为发现频繁项集的过程。

若min_conf =0.6，则{i1}→{i3}和{i3}→{i1}均为强关联规则[13]。

5 Apriori关联规则算法的应用

Apriori算法凭借简单、易理解、数据要求低等诸多优点被广泛应用于商业、网络、教育等领域。

（1）商业方面，部分购物网站利用Apriori算法对消费者的消费习惯进行分析和挖掘，为商户瞄准目标客户、增加收入提供参考依据。

（2）网络方面，利用Apriori算法快速发现网络用户的异常行为模式，快速锁定攻击者，为提高入侵检测系统的检测性提供帮助。

（3）教育教学方面，利用Apriori算法可以对收集的与学生学习相关的数据，如网络教学反馈、学生登录次数与学习时长、网上测评结果等进行关联性分析和挖掘，找出数据相关性，对网上教学进行重组和配置，为提高网上教学效果、实现网络教学个性化设计提供参考依据[14]。

用Apriori算法对1 369位学生针对国家开放大学网上教学平台满意度调查数据进行分析与挖掘[15]，内容涉及学习网的界面操作是否方便、能否实时开展师生视音频在线交流、课程教学设计是否合理、数字化教学资源能否满足学生需求、考核方式是否合理、教师网上教学能力、网上实践实训环节是否达到预期效果等。设定min_sup=0.12，min_conf=0.45，调查内容分别用A，B，C，D，E，F，G表示。

首先，扫描数据库，得出候选1-项集C1及各项的支持度计数和支持度，见表6所列。

将C1中各项的支持度与最小支持度阈值比较，剔除小于min_sup的項集，得到频繁1-项集，见表7所列。

对L1执行连接操作，如L1L1，扫描数据库，得到候选2-项集及各项的支持度计数和支持度，见表8所列。

继续与最小支持度阈值比较，剔除小于min_sup的项集，得出频繁2-项集L2，见表9所列。

执行连接操作，如L2L2，扫描数据库，得出候选3-项集及各项的支持度计数和支持度，见表10所列。

C3中的所有项都小于min_sup，故未找到频繁3-项集，寻找频繁项集的操作到此为止。

计算频繁2-项集的置信度，具体如下：

将小于min_conf的项集全部剔除，得到强关联规则E→A和D→B。由此得出结论：多数学生认为网上课程考核方式不合理和学习网界面操作不方便，以及数字化教学资源无法满足需要并无法开展师生实时视频、音频等在线交流，这为改进网上教学平台设计[16]、解决课程繁多但组织随意、教学资源不合理等问题提供了参考依据。

6 结 语

Apriori算法可以使用户从找到的频繁项集中选择某些感兴趣的项，以求发现某些新奇的、有价值的或反常的规则。且算法通过连接和剪枝大大缩小了数据规模，与AIS和SERM相比，算法效率得到大幅提高，但终因数据库需多次扫描带来的开销以及迭代过程中产生的大量频繁项集导致算法在挖掘效率上未能很好地满足人们的需求。尽管如此，与其他数据挖掘方法相比，Apriori算法凭借简单易懂、无复杂推导规则表达形式等原因备受推崇。随着对数据挖掘算法研究的不断深入，会有更多更好的挖掘算法出现，以便更好地满足大数据时代的需求。

参考文献

[1]刘言哲，柳炳祥.基于Apriori算法的国家经济数据分析[J].中国管理信息化，2020，23（4）：148-150.

[2]温亮明，郭蕾，王晓东，等.基于关联规则的国内外数据期刊载文特征比较分析：以《Scientific Data》和《中国科学数据》为例[J].情报科学，2019，37（1）：112-121.

[3]王平水.关联规则挖掘算法研究[J].计算机工程与应用， 2010，46（30）：115-116

[4]郭鹏，蔡骋.基于聚类和关联算法的学生成绩挖掘与分析[J].计算机工程与应用，2019，55（17）：169-179.

[5]刘雯婷，周军.基于缓冲区技术的增量数据关联规则挖掘算法[J].辽宁工业大学学报（自然科学版），2020，40（2）：71-74.

[6]尹远，朱璐伟，文凯.基于差异点集的频繁项集挖掘算法[J].计算机工程与设计，2020，41（3）：716-720.

[7]黄剑，李明奇，郭文强.基于Hadoop的Apriori改进算法[J].计算机科学，2017，44（7）：262-266.

[8]余晓平，刘丽娅，朱东芹.基于项集的多支持度关联规则挖掘算法[J].微计算机信息，2009，25（33）：147-148.

[9]丁燕妮.模糊多维关联规则的研究与应用[D].北京：中国地质大学，2019.

[10]李广璞，黄妙华.频繁项集挖掘的研究进展及主流方法[J].计算机科学，2018，45（11A）：1-11.

[11]熊桂喜，刘谢.改进的Apriori算法在交通事故分析中的应用[J].微计算机信息，2010，26（25）：205-207.

[12]刘海涛.一种改进的数据挖掘算法[J].科技通報，2016，32（11）：142-147.

[13]方蓉.基于关联规则的数据挖掘算法的分析及应用[J].电子测试，2016，23（1）：36-38.

[14]梁燕红.改进的Apriori算法在网络教学中的应用[J].玉林师范学院学报，2012，33（2）：130-133.

[15]赵杨.关联规则技术在网络学习评价中的应用研究[D].桂林：广西师范大学，2014.

[16]叶根梅.Apriori算法改进及其在高校网络教学平台的应用[J].河池学院学报，2019，39（2）：73-76.