基于关联规则挖掘的Apriori改进算法

白莹莹++申晨晨

摘 要关联规则挖掘是数据挖掘技术的一个重要分支，其中Apriori算法是最经典和最有影响力的算法。本文在讨论和分析了关联规则挖掘的基本概念后，提出了一种减少扫描数据库次数的改进算法。改进后的算法分析证明，它可以有效地提高数据挖掘的性能。

【关键词】关联规则挖掘 数据挖掘 Apriori算法

数据挖掘是从大量数据中挖掘有趣模式和知识的过程，数据源包括数据库、数据仓库、Web、其他信息存储库或动态地流入系统的数据 。现今计算机技术与数据库技术在飞速地发展，如何从海量的数据中快速准确地找出有用的信息是数据挖掘问题中的一项重要研究内容。

在1994年，由Agrawal提出的Apriori算法，是关联规则里的一项基本算法，它的基本思想是重复扫描数据库，由长度为k的频繁项集进行迭代计算产生长度为k+1的候选集，再对数据库进行扫描判断其是否为频繁项集。

在过往的研究当中，许多文献提出了基于Apriori算法的改进。林佳雄等人提出的基于数组向量的Apriori算法改进 ，该算法改进了连接比较的次数、减少不必要事务的扫描和提高了算法对内存空间的利用效率。曹莹等人提出的基于向量矩阵优化频繁项的改进Apriori算法 ，赵学健等人的一种正交链表存储的改进Apriori算法，该算法Apriori算法复杂的自连接和剪枝过程进行了优化，简化了频繁项目集的生成过程，提高了Apriori算法的时间效率 。

1 关联规则挖掘的概况

关联规则挖掘是数据挖掘中的一个很重要的课题，顾名思义，它是从数据背后发现事物之间可能存在的关联或者联系。最早是为了发现超市交易数据库中不同的商品之间的关系。目的在于发现数据项之间的潜在关系，通过它提取出的信息将有助于人们把握和预测行业发展规律，从而更好地制定发展计划和规避风险。

那么问题如下所述：假设I={i1，i2，...im}是所有项目的集合，D是一个数据库，事务T是一个子项（TI）。每个T都有自己独特的标识 。A是由项目组成的集合，即项集。T包含A，当且仅当AT。如果项集A的项目数为k，则称为k维项目集。项集A的出现频率是包含项集的事务数，简称为项集的支持度。如果项集支持度超过由用户给定的最小支持度阈值，则称为频繁项集，简称频繁集。

关联规则是形如的蕴涵式，其中，X称为关联规则的先导，Y称为后继。其中，关联规则X与Y存在支持度和置信度。关联规则在D中的支持度（support）是D中事务同时包含X和Y的百分比，即概率。置信度（confidence）是D中事务已经包含X的情况下，包含Y的百分比，即条件概率。如果满足最小支持度阈值和最小置信度阈值，则认为关联规则是有趣的。

2 Apriori算法

2.1 核心思想

最著名的关联规则挖掘算法是Apriori算法，它是一种以概率为基础的关联规则算法，能实现从少到多，从简单到复杂寻找极大频繁集。Apriori算法主要利用了向下封闭属性：如果一个项集是频繁项目集，那么它的非空子集必定是频繁项目集。在运算过程中首先生成1-频繁项目集，再利用1-频繁项目集生成2-频繁项目集，然后根据2-频繁项目集生成3-频繁项目集，依次类推，直至生成所有的频繁项目集。最后从频繁项目集中找出符合条件的关联规则。

2.2 算法过程

Apriori算法采用递推的方法来生成所需的频繁集，主要步骤如下：

（1）制定最小支持度及最小置信度；

（2）Apriori算法使用了候选项集的概念，通过扫描数据库产生候选项目集，如果候选项目集的支持度不小于最小支持度，则该候选项目集为频繁项目集；

（3）从数据库中读入所有事务数据，得出候选1项集C1及相应的支持度数据，通过将每个1项集的支持度与最小支持度比较，得出频繁项集合L1，然后将这些频繁1项集两两连接，产生候选2项集和C2；

（4）然后再次扫描数据库得到候选2项集合C2的支持度，将2项集的支持度与最小支持度比较，确定频繁2项集。类似地，利用这些频繁2项集L2产生候选3项集和确定频繁3项集，以此类推；

（5）反复扫描数据库，与最小支持度比较，产生更高项的频繁项集合，再结合产生下一级候选项集，直到不再产生出新的候选项集为止；

3 Apriori算法的改进及分析

3.1 改进算法的思想

关联规则是其支持度和置信度分别满足用户给定阈值的规则，发现关联规则需要如下两步骤：

（1）找出所有的频繁集，其最后出现的频率和预定义的最小支持度是相同的。

（2）强关联规则是由频繁集产生的，它必须满足最小支持度和最小置信度。

但是Apriori算法由于需要多次扫描数据库，而造成过重的I/0负担，因此改进算法将通过减少数据库扫描次数的方式来减轻I/0负担。

改进算法的思想就是利用频繁k+1项集中的任一元素，一定可以表示成频繁k项集中某一元素与频繁1项集中某一元素的交集这一性质来产生频繁集，从而减少扫描数据库的次数。

改进算法先对事务数据库进行扫描，得到1项集L1={l1，l2，...，ln}，对1项集L1进行剪枝，得到频繁1项集M1={l|cardl≥sup且l∈L1}，然后由频繁1项集M1中元素求得2项集L2={l|l=li∪lj，li∈M1且i≠j}，对L2进行剪枝得到频繁2项集M2={l|cardl≥sup且l∈L2}，再由M2中元素与M1中元素产生3项集L3，通过剪枝得到频繁3项集M3，以此類推，可求得频繁k项集Mk，直到频繁k项集中项数小于k，则由性质2可知，频繁k项集Mk无法产生频繁k+1项集，迭代停止。

3.2 改进算法分析

根据上面改进的算法，对该算法进行分析。表1为事务数据库，设最小支持度为20%，则最小支持度计数等于2。

从表1中可知：i1={D1， D4， D5， D6， D7， D8， D9}，i2={D1， D2， D3， D4， D8， D9， D10}，i3={D3， D5， D6， D7， D8， D9}，i4={D2， D4， D10}，i5={D1， D9}，所以M1={i1，i2，i3，i4，i5}，利用频繁1项集M1，可以生产C25个2项集，i1={D1， D2， D3， D4， D5， D6， D7， D8， D9}

即：L2={l12， l13， l14， l15， l23， l24， l25， l34，l35，l45}，l12={D1，D4，D7，D8}，l13={D5，D6，D7，D8，D9}，l14={D4}，l15={D1，D8}，l23={D3，D8，D9}，l24={D2，D4，D10}，l25={D1，D8}，l35={D8}，l34=l35=φ。

对2项集进行剪枝，可得到频繁2项集M2={l12， l13， l15， l23， l24， l25}。利用频繁2项集M2与频繁1项集M1，可以得到频繁3项集M3={l123， l125}。

根据频繁项集的性质2，频繁项集M3中的项数为2，其无法产生频繁4项集，因此迭代停止。计算结果见表2。

3.3 实验与分析

实验所用到的数据选用本校教职工的一次调查问卷，数据库中共有1694条记录，用来证明文中的改进算法具有有效性。我们把它与Apriori算法进行比较，部分记录如表3所示。由于在这次调查中，教师只需要在36个选项中，选出最符合自己意愿的某几个选项，因此数据的存储采用简单二维表，可以节省存储空间。

图1是改进算法与Apriori经典算法在不同支持度下执行时间对比。

由图1可以看出，改进算法在效率上优于Apriori算法，并且在最小支持度较小时，改进算法的执行时间相对于Apriori算法具有明显优势，但是随着最小支持度的增加，两种算法的执行时间均大幅减少，Apriori算法与改进算法的执行时间开销非常接近，这是因为随着最小支持度的增加，迭代次数减少，运算过程中产生的频繁项集的数量均大幅度减少，使得算法的执行时间减少。

4 结论与思考

由于Apriori算法多次扫描事务数据库，需要很大的I/O负载，因此在改进的算法中，以项集中存在的集合数量与最小支持度计數进行对比，进而判断其是否为频繁项集，这样就不用对数据库进行多次扫描。虽然改进算法减少了I/0次数，提高了算法的执行效率，但是算法在执行过程中，由于需要保存大量的数据，而需要占用较多的内存空间，因此如何对数据量较大的数据库执行本算法，还有待进一步的研究与改进。

参考文献

[1]Han J.W.，Kamber M.Data Mining：Concepts and Techniques，数据挖掘：概念与技术[M].范明，孟小峰等译.北京：机械工业出版社，2001.

[2]林佳雄，黄战.基于数组向量的Apriori算法改进[J].计算机应用与软件，2011（05）：248.

[3]曹莹，苗志刚.基于向量矩阵优化频繁项的改进Apriori算法[J].吉林大学学报，2016（02）：349.

[4]赵学健，孙知信，袁源，陈勇.一种正交链表存储的改进Apriori算法[J].计算机技术与发展，2016（10）：2291.

[5]朱惠.关联规则中Apriori算法的研究与改进[D].安徽：安徽理工学，2014.

[6]朱翼.基于数组的Apriori算法的改进研究[D].哈尔滨：哈尔滨师范学，2014.

作者简介

白莹莹（1992-）女，陕西省宝鸡市人。工作于西安工程大学计算机科学学院。主要研究方向为智能信息处理。

申晨晨（1993-）男，安徽省阜阳市人。工作于西安工程大学计算机科学学院。主要研究方向为系统仿真与系统控制。

作者单位

西安工程大学计算机科学学院 陕西省西安市710048