Apriori算法改进研究

摘要：Apriori算法作为数据挖掘技术中的经典算法，它在事务数量少的数据库中具有较好性能从而得到了人们的广泛应用，但该算法具有的两个固有缺陷，影响了apriori算法在大数据库中挖掘信息的效率。文中对apriori算法的两个固有缺陷进行改进以便提高apriori算法在大数据库中的挖掘效率。

关键词：apriori算法；关联规则；数据挖掘；频繁项目集

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2013）09-2037-03

数据挖掘是近年来非常活跃的一个研究领域，它是在机器学习、统计学、数据库技术、信息科学的理论基础上发展而成。数据挖掘（DM，Data Mining）就是从大量的、不完全的、有噪声的、模糊的、随机的数据中，提取隐含在其中的、人们事先不知道的、但又是潜在的有用信息和知识的过程[1]，其主要目的是从大量的数据源提取有用的并且用户感兴趣的知识和模式。数据挖掘的一个重要分支就是关联规则挖掘，关联规则反映的是一个事件跟其他事件之间的关联或依赖，是事务内部的规律或模式，体现了现实世界中事物的关联关系，比如人们从超市销售数据中发现购买啤酒的客户很有可能购买尿布，因此超市管理人员根据这种关联关系将啤酒和尿布摆放在相邻的位置以促进商品的销售。

关联规则的形式描述为：设I=[[I1，I2，I3，...，In]]是事务数据库D中所有项的集合，D中每个事务T都有唯一的标识符[Tid]，[T?I]，A、B为项集，关联规则是形如 A=>B的蕴涵式，其中[A?I，B?I，并且A?B=?]。

关联规则有两个重要的度量标准：支持度（support）和置信度（confidence）。通常人们在挖掘关联规则时会设置最小支持度阈值（min_sup）和最小置信度阈值（min_conf），我们将支持度大于或等于最小支持度阈值的项集称为频繁项集，将同时满足最小支持度阈值和最小置信度阈值的规则称为强关联规则，否则为弱关联规则，强关联规则才是用户感兴趣的关联规则。

关联规则的挖掘过程分为两个步骤：

第一步：根据最小支持度阈值从事务数据库中找出所有的频繁项集。

第二步：根据最小置信度阈值由频繁项集生成强关联规则。

其中，从事务数据库中发现频繁项集是关联规则挖掘的关键步骤，该步骤决定了关联规则挖掘的整体性能。

1 apriori算法

1.1 apriori算法基本思想

apriori算法是针对关联规则挖掘的第一个步骤，也就是从事务数据库中发现所有的频繁项集，apriori算法采用逐层搜索的迭代方法来生成频繁项集[2]，首先扫描事务数据库D，根据用户设置的最小支持度找出数据库D中的1-项频繁项集L1，然后由1-项频繁项集L1进行连接操作生成2-项候选项集C2，再次扫描事务数据库从2-项候选项集C2中找出2-项频繁项集L2，然后再由2-项频繁项集L2进行连接生成3-项候选项集C3，再次扫描事务数据库找出3-项候选项集中的3-项频繁项集L3，依次类推，直到没有更大模式的k-项频繁项集或候选项集为空，则apriori算法结束（如图1）。

1.2 Apriori算法的缺陷

1） 每次由候选项集生成频繁项集时都需要扫描数据库，而数据库一般都存放在外存上，这样就导致该算法在执行过程中需要很大的I/O负载。

2） 频繁项集进行自我连接时会产生大量的候选项集，这些候选项集的存放需要很大的空间，而且由候选项集经过再次扫描数据库生成频繁项集时也需要大量的时间来处理。

2 apriori算法改进方法

apriori算法执行过程中需要经过数据库扫描操作和频繁项集连接操作，我们针对这两个操作进行改进以便提高apriori算法的执行效率。改进的基本思想是：每次由候选项集生成频繁项集时需要扫描数据库，而每次扫描数据库时并不需要扫描数据库中的所有事务数据，所以我们对每次扫描的数据库进行优化，就可以减少扫描数据库的IO操作；另外，频繁项集进行连接操作生成的候选项集中，不是所有的候选项集经过数据库扫描后会转化为频繁项集，因此，在每次生成候选项集之前，我们对已有的频繁项集进行优化，既可以减少频繁项集的连接操作，也可以减少生成的候选项集转化为频繁项集的处理时间，我们从数据库优化、频繁项集优化、连接操作优化这三个方面对Apriori算法来进行改进。

2.1 数据库优化

Apriori算法每次迭代生成频繁项集时，都需要扫描数据库中的所有数据，以便将候选项集中支持度大于或等于最小支持度阈值的项集找出来构成新的频繁项集，比如频繁项集中包含10个分项，则apriori算法就必须迭代10次，apriori算法执行过程中就必须对数据库中的所有数据扫描10次。根据性质1：如果频繁项集的长度为k，则长度小于k的事务肯定不满足频繁项集的要求，我们在生成k-项频繁项集扫描数据库时就可以跳过长度小于k的事务，这样可以减少数据库扫描时间。

根据性质1，我们可以减少数据库扫描时的事务个数，在剩下的数据库事务中还存在对生成频繁项集不起作用的事务，如果我们将剩下的对生成频繁项集不起作用的的事务再一次进行优化，就可以进一步减少扫描数据库中事务的个数，从而进一步减少apriori算法的IO操作。

性质2：我们将数据库中所有的不同项作为一个集合，记为集合A，将所有频繁项集中的不同项作为一个集合，记为集合B，则任何一个事务T在集合A的分项个数一定大于在集合B中的分项个数，即[|TB|

证明：因为频繁项集B中的所有项都是来自于集合A，因此有[B?A]，对于数据库中的任意事务T，T中的任意分项[Ii]（[1

根据性质2，我们由生成的所有频繁项集中的不同分项构成一个集合B，如果数据库中的某个事务T在集合B中的分项个数小于本次迭代生成的频繁项集中的分项个数，则这样的事务对下一次迭代生成频繁项集不起作用，我们就可以删除该事务或跳过该事务的扫描，从而减少Apriori算法的IO操作。

2.2频繁项集优化

性质3 k-维数据项目集是频繁项集的必要条件为它的所有k-1 维子集均是频繁项集[3]，也就是，如果k-项集X的任意一个 （k-1）-项子集不是频繁的，则X也不是频繁的[4]。

性质4 若存在k-项集X={[i1，i2，…ik]}，该项集X中如果存在项j[∈X使得|Lk-1（j）|]

证明： k-项集X={[i1，i2，…ik]}有k个（k-1）-项子集，并且只有一个（k-1）-项子集不包含项j（ j为K项集X中任意项），由性质3可得，项集X为频繁项集时有[|Lk-1（j）|=（k-1）]，故[|Lk-1（j）|

我们根据性质4，在频繁项集进行连接操作前就可以判断连接操作后生成的候选项集是否为更大模式的频繁项集，如果生成的候选项集肯定不是更大模式的频繁项集，我们就可以在连接操作前对这样的频繁项集不进行连接操作，从而减少连接操作的时间及候选项集转化为更大模式的频繁项集的处理时间。

2.3 连接操作优化

连接操作是apriori算法执行过程中的一个重要步骤，只有进行连接操作后才能生成更大模式的候选项集，只有生成更大模式的候选项集，通过再次扫描数据库后才能得到更大模式的频繁项集。两个频繁项集进行连接操作必须满足下面这个条件：这两个频繁项集的最后一项不能相同，除最后一项外，这两个频繁项集的其他项必须分别相同，即满足条件

[l1[1]=l2[1]∧l1[2]=l2[2]∧…∧l1[k-2]=l2[k-2]∧l1[k-1]]

[l1]、[l2]都是（k-1）-频繁项集，并且在频繁项集[L（k-1）]中项集[l2]位于项集[l1]的后面位置，由于频繁项集及频繁项集中的分项都是有序排列的，根据项集的这个有序性，如果频繁项集[l1]与频繁项集[l2]不满足连接条件，则位于频繁项集[l2]后面的频繁项集也不满足与频繁项集[l1]的连接条件，这样，就可以减少大量的连接操作次数，从而提高apriori算法的效率。

3 实验结果分析

改进后的apriori算法我们记为apriori-1算法，测试环境是：操作系统为Microsoft Windows XP Professional，CPU 为Intel（R） Pentium（R） 4，3.00 GHz，内存为 512M，实验样本数据由IBM公司Almaden中心提供的标准数据集[5]，测试结果如图2。

从图2中可以得到，在支持度阈值相同的条件下，Apriori-1算法的运行时间要比Apriori算法的运行时间少，原因有：1） Apriori-1算法中每次扫描的事务个数比传统的Apriori算法要少。2） Apriori-1算法在连接操作前对[Lk-1]中的项集进行优化，减少了生成k-项候选项集集合[Ck]的连接操作次数和剪枝操作次数。3） Apriori-1算法利用项的有序性，减少连接操的次数。

参考文献：

[1] 邵峰晶，于忠清.数据挖掘原理与算法[M].北京：中国水利水电出版社，2003：2-3.

[2] 杨金凤，刘锋.一种新的改进Apriori算法[J].微型机与应用，2010（1）：55-57.

[3] 钱光超，贾瑞玉，张然，等.Apriori 算法的一种优化方法[J].计算机工程，2008，34（23）：196-198.

[4] 陈宁军，高志年.一种改进的正负关联规则挖掘算法[J].计算机科学，2011，38（12）：191-193，212.

[5] Apriori算法样本数据集下载网址：http：//fimi.ua.ac.be/data/chess.dat.