一种改进的关联规则算法

徐晶晶

摘要： 该文对关联规则算法进行了分析研究，并针对传统的Apriori算法在对海量数据进行处理时的效率低，I/O负担过重，产生大量候选项集导致计算量过大等问题，提出了一种改进方法New_Apriori算法。通过对项集的支持度计数进行条件判断，来减少对事务数据库的扫描次数和CPU的计算时间，从而提高算法的执行效率。通过实例和实验对Apriori算法和New_Apriori算法进行对比分析，验证了算法的可行性，结果表明New_Apriori算法的执行效率更高，能够满足大数据处理需求。

关键词：Apriori；关联规则；大数据

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2018）18-0257-04

Improved Association Rule Algorithm

XU Jing-jing

（College of Computer and information Technology， Henan Normal University， Xinxiang 453007， China）

Abstract： This paper analyzes and studies the Association Rule Algorithm， and it proposes an improved method that is New_Apriori Algorithm to solve problems. During the processing of traditional Apriori algorithm， the low efficiency of it and the heavy burden of I/O will produce a large amount of candidate items， which can be solved by the New_Apriori Algorithm. The new method reduces the number of scanning times of the transaction database and the calculation time of CPU by judging the condition by counting the degree of Support_count， thus it can improve the executive efficiency of itself. The feasibility of the New_Apriori Algorithm is verified by comparison and analysis of Apriori and New_Apriori Algorithm through examples and experiments， and the results show that the executive efficiency of New_Apriori Algorithm is higher which can meet the demand of large data processing.

Key words： Apriori； Association rules； Big Data

隨着云计算和互联网的飞速发展，各行业的数据都在呈爆炸性增长[1]。大数据时代的到来，使得大数据技术越来越受关注，利用数据挖掘技术找到海量数据当中隐藏的、有价值的信息已经成为当前信息社会的一笔重要财富。关联规则挖掘算法就是数据挖掘当中的一个重要分析方法，在大数据背景下，关联规则挖掘算法能够帮助人们从海量数据中发现许多潜在的又有价值的信息。最经典的就是购物篮分析，帮助超市发现啤酒和尿不湿的消费规律。在教育行业，利用关联规则算法找到学生成绩与课程之间的关系、挖掘在线学习的学生的行为偏好对学生进行合理的资源推荐[2]；在金融行业挖掘客户的行为需求和习惯、以及购买意向；在医学界挖掘疾病和药物之间的关系等。最经典的关联分析算法就是Apriori算法，在1994年由Agrwal和R.Srikant提出来的，是一种布尔关联规则挖掘频繁项集的一种原创性算法[3]。该算法的重点工作就是在挖掘过程中找出所有的频繁项集，算法的性能决定了频繁项集挖掘的性能[4]。在深度挖掘和使用的过程中，发现该算法还存在以下不足：（1）在挖掘频繁项集的过程中，总是先产生候选项集，再对候选项集的支持度和最小置信度进行计算比较，最终找到需要的所有频繁项集。候选项集的支持度计数每增加1，都会对事务数据库扫描一次，这样就增加了I/O的开销，当候选项集非常多时，算法的时间和空间开销会更大，降低了算法的效率。（2）在算法不断进行当中，会产生大量的候选项集，其中有很多无关的项集也进行了连接，连接步的过程开销增大，后剪枝的工作量也随之增加，不利于算法的执行。因此本文提出了一种改进的关联规则挖掘算法New_Apriori，通过对频繁项计数和不频繁计数最小阈值的判断，来减少对事务的扫描次数，减少了CPU的计算时间，提高算法的运行效率，有效地减轻了I/O负担。

1 Apriori算法分析

1.1 Apriori算法概述

Apriori算法使用一种被称作逐层搜索的迭代方法[5-6]，通过k项集来生产（k+1）项集的候选项集，经过扫描数据集库，将计算（k+1）项集的候选项集的支持计数，其中满足最小支持度的项集则为频繁项集，一直找到所有的频繁项集为止，每找到一个频繁项集都需要对数据库进行一次完整的扫描[7]，频繁项集的先验性质，使得k项集可以用作去探索（k+1）项集，而不用重新地开始查找频繁项集。

1.2 Apriori算法的核心思想

（1）自动连接步

[Lk]与[Lk+1]自动连接，产生候选项k+1项候选项集[Ck+1]；设[I1]和[I2]是[Lk]当中的两个项集，[Ii[k]]表示[Ii]中的第k項，为了能实现Apriori算法，假定项集当中的所有项都按照字典序进行排序。对于k项集Ii，[Ii1

（2）剪枝步

[Lk]是[Ck]的真子集，[Ck]当中的项集也可以是不频繁的，但是最终结果得到的所有频繁项集都包含在[Ck]当中。在扫描事务数据库时，通过计算[Ck]中的每个候选项集的计数，来确定得出频繁项集[Lk]，当计数的值不小于预定义的最小支持度阈值时，该项集就是频繁项集，属于[Lk]当中。当[Ck]很大时，这样涉及的计算量就非常大，所以要压缩[Ck]，利用先验性质，任何非频繁项集都不是频繁项集的子集，所以，如果一个候选项k项集中的（k-1）项集的子项集不在[Lk]项集当中，则该项集就是不频繁的，就要从[Ck]当中删除。

（3）产生有效的关联规则

使用频繁项集产生强关联规则（依据：置信度）。

对于每个频繁项集L，产生L的所有非空子集S，则对于规则[S→L-S]，如果

[ConfidenceS→L-S≥min_Confidence]（其中[min_Confidence]为最小置信度阈值），则称规则[S→L-S]为强关联规则。

注意：在这一阶段中计算各个规则的置信度时不需要再对数据集进行扫描，直接运用第一阶段产生频繁项集时扫描得到的相应的计数即可。

满足最小支持度和最小置信度的规则叫作“强关联规则”，然而在强关联规则里也分有效的强关联规则和无效的强关联规则。

如果[LiftS→L-S>1]，则规则[S→L-S]是有效的强关联规则；

如果[LiftS→L-S<1]，则规则[S→L-S]是无效的强关联规则；

如果[LiftS→L-S=1]，则规则表示S和（L-S）相互独立。

也就是说，强关联规则还需通过提升度的检验才能真正视之为有用的关联规则，才能用于指导实践，同时需注意的是，机器学习得到的关联规则并无人的意识，有效的关联规则中哪些对用户是有实际价值的还需要分析人员做出最终判断，得到最终的关联结果。并且，关联分析得到的关联规则的前后项之间不是因果联系，是一种可能同时发生的关联性。

2 改进的关联规则挖掘算法

2.1 New_Apriori算法思想

该方法的主要思想是减少事务扫描的次数。

（1）在扫描事务数据库时，每当项集存在事务中一次，则该项集的支持度计数[（support_count）]就加1，当项集的支持度计数等于预定的最小支持度阈值（[min_sup]）时，该项集就是频繁项集，停止对剩下事务的扫描，进入下一个项集的扫描。

（2）不频繁项集支持度=总事务数-最小支持度阈值+1

[Infrequent_support= Total transaction – min_sup+1]

当扫描事务数据库时，某项集不在事务中时，项集的不频繁计数[（Infrequent_count]）增加1，当项集的不频繁计数等于不频繁项集支持度时，该项集为不频繁项集，直接终止扫描，直接删除该项集。如果最小支持度阈值很高时，这个不频繁项集支持度就起着非常重要的作用，例如有个事务，[min_sup] = 9，则[Infrequent_support] = 2，因此，当扫描事务数据库时，某项集的不频繁项集计数达到2时，就可以中断事务的扫描，将该项集定为不频繁项集，并且将该项集直接删除。

（3）双向搜索：通常数据集的扫描是从上到下进行的。但是这里笔者对数据集的扫描是从上到下和从下到上依次进行到数据集的中间。

2.2 New_Apriori算法方法

输入：事务数据库D，最小支持度阈值[min_sup]

输出：L中的频繁项集

方法：

[Infrequent_support] = 总数事务数 –[ min_sup] + 1；

For（k=1；Lk！= Φ；k++） do begin

a）Ck+1= 从Lk中产生候选项集

b）Prune（CK+1）

c）扫描事务从上到下和从下到上依次进行，增加CK+1中的所有候选项集的支持度计数和不频繁项集支持度计数；

d）if support_count= min_sup

or Infrequent_count= InfrequentSupport 停止扫描

e）when support_count= min_sup ，该项集为频繁项集，保留该项集

Infrequent_count= InfrequentSupport，该项集为不频繁项集，删除该项集

f） （Lk+1） = candidates in （Ck+1）

end

return UkLK

end procedure

3 改进算法实例说明

实例事务数据库D：

这里对事务数据库的扫描是从上到下和从下到上依次进行完成的，首先扫描事务T1，然后再扫描事务T9，每扫描一次，事务中存在该项集，项集的支持度计数就递增1。当Support_conut 达到2时，就和预定的最小支持度阈值相同，这时停止对项集{I1}的扫描，该项集就是频繁项集。

同样地，对候选项集{I2}，{I3}，{I4}，{I5}依次进行扫描，如表2所示。

当对项集{I1、I4}的扫描时，不频繁项集支持度（Infrequent_count）先满足预定义的不频繁项集支持（Infrequent_support）的值，停止扫描数据集，该项集被定为不频繁项集，直接删除该项集即可，减少了候选项集的扫描次数。如果此时的min_sup= 9，那么Infrequent_support=1，只需扫描事务T1时，Infrequent_count = 1→break，扫描终止，该项集被删除，不用再次对扫描事务数据库求其支持度计数，减少了对事务的扫描次数，大大地提高了算法的运行效率。

候选项集C2的扫描过程如下表3所示：

由L3?C4 = {{I1，I2，I3，I5}}；经过剪枝，C4被删除。算法终止，得到所有频繁项集。

笔者用原始的Apriori算法进行了分析，统计出兩种算法扫描数据库的总次数，然后进行对比分析，得知改进的Apriori算法与原始的相比，扫描次数明显减少，因此降低了CPU的计算时间，提高了算法的运行效率。

4 实验分析与结果展示

为了验证改进的算法的性能，笔者将改进前和改进后的Apriori算法进行了对比试验。

（1）选择相同的数据集，比较改进前和改进后的算法在相同的支持度下产生频繁项集所需的时间。结果如表6所示：

（2）选择相同的数据集，将最小支持度阈值设置成不同的值进行试验，比较改进前和改进后的Apriori算法在不一样的支持度下，产生频繁项集所需的时间。对比试验的结果如图1所示：

（3）选择相同的数据集，在同一最小支持度阈值的情况下，比较数据集的事务扫描总数。如图2所示：

通过上述试验验证，New_Apriori算法与传统的算法相比，减少了对事物数据库的扫描次数，提高了算法的运行效率，减少了CPU的执行时间。

5 结束语

本文提出了一种改进的关联规则算法New_Apriori算法，通过判断项集的支持度计数是否满足频繁项集的最小支持度阈值或者是不频繁项集的最小支持度的阈值来停止对事务数据库的扫描，减少CPU的计算时间，从而提高了算法的执行效率。当频繁项集的最小支持度阈值很低时，项集的支持度计数达到最小支持度阈值时，停止对事务数据库的扫描；当频繁项集的最小支持度阈值很高时，基于不频繁项集的最小支持度阈值，停止对事务数据库的扫描。实验证明，改进后的Apriori算法较之前的算法更具有优势，能够满足大数据分析对数据挖掘需求。

参考文献：

[1] Casado R， Younas M. Emerging trends and technologies in big data processing[J]. Concurrency & Computation Practice & Experience， 2015， 27（8）：2078-2091.

[2] 邱鑫仪， 沈良忠. 基于数据挖掘的学生学业预警研究[J]. 电脑知识与技术， 2017， 13（36）：226-227.

[3] Yi K， Chen T， Cong G. Library personalized recommendation service method based on improved association rules[J]. Library Hi Tech， 2017.

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

[5] Oruganti S， Ding Q， Tabrizi N. Exploring HADOOP as a Platform for Distributed Association Rule Mining[J]. 2013：62-67.

[6] 周发超， 王志坚， 叶枫，等. 关联规则挖掘算法Apriori的研究改进[J]. 计算机科学与探索， 2015， 9（9）：1075-1083.

[7] 王华， 刘萍. 改进的关联规则算法在学生成绩预警中的应用[J]. 计算机工程与设计， 2015（3）：679-682.