一种改进的挖掘关联规则Apriori算法

王志春

摘要：该文通过分析Apriori算法存在的瓶颈问题，给出了一种对Apriori算法改进的策略。该策略针对挖掘关联规则步骤中Apriori算法形成的候选项目集进行了优化，以避免产生重复的候选集，减少扫描数据库的次数，提高算法的效率。在实验评估中显示，改进后的Apriori算法在执行效率上有一定的提高。

关键词：数据挖掘；关联规则；Apriori算法

中图分类号：TP391 文献标识码：A 文章编号：1009-3044（2015）34-0004-02

1 概述

随着计算机和网络技术的迅速发展，积累的数据海量增长，如何在这些海量数据中获取有价值的信息和知识变得越来越重要。数据挖掘[1]在此背景下得到迅速发展，目前被广泛地应用于数据分析领域中，其目的是从大量的数据中挖掘隐藏的、潜在的、有价值的模式或规则，以对政府和企业的决策提供有用的依据。关联规则[2]作为数据挖掘中的一个重要课题，通过在大量数据中的挖掘和计算，获取看似不相关的项目间的关联性。在关联规则的相关研究中，由Agrawal和Srikant（1994）所提出的Apriori算法[3]是最具代表性的经典算法之一，在以后的研究中，提出了许多可改善Apriori算法的性能的优化算法，如Park等人提出的基于hash的算法[4]、Savasere等人提出的基于划分的算法[5]、Toivonen提出基于采样的算法[6]、Brin等人提出的动态项集计数算法[7]以及曾万聪等人提出的矩阵算法[8]等等，这些算法都在不同方面对Apriori算法进行了优化。

在大量的数据中找出项目间的关联性，首先必须要找出频繁项目集，然后得到满足设定条件的关联规则，其中找出频繁项目集的过程是挖掘关联规则过程中最费时的步骤。传统的Apriori算法及其类似算法在找出频繁项目集的过程中，必须扫描全部的频繁项目集，以形成新的候选项目集。本算法对Apriori算法形成候选项目集的方式进行修改，避免产生重复的候选集项目集，从而提高算法的效率。

2 Apriori算法

2.1 关联规则

设[I=i1，i2，…im]是事务数据库全部项目的集合，[T=t1，t2，…tm]是事务数据库的集合，Tj是一组项目组成的项目集。关联规则是形如[A?Bs，c]的蕴含式[9]，其中A称为前项，B称为后项，[A?I]，[B?I]且[A?B=Φ]，参数s（Support）是支持度，参数c是置信度（Confidence）。挖掘关联规则的过程中，必须由参数s和c决定关联规则[A?B]是否形成有效的规则。支持度Support是事务同时包含A和B的比率，即[Support=PA?B=A，B.count/T.count]，反映了A和B所含的项同时出现在事务集T中的概率，其中（A，B）.count表示事务集T中同时包含A和B的事务的个数，T.count表示事务集T中事务的个数；置信度Confidence是事务集T中包含A事务的同时也包含B事务的比率，即[Confidence=PB|A=A，B.count/A.count ]，其中A.count表示事务集T中包含A的事务的个数。为了挖掘有效的关联规则，支持度和置信度必须大于或等于指定的最小支持度和置信度，关联规则[A?B]称为强规则，挖掘关联规则即是对最小支持度和置信度求解其强规则。

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

1） 找出满足最小支持度的频繁项目集，即找出支持度不小于指定的最小支持度的事务集，若该事务集包含k个项目则称为频繁k项集。

2） 从频繁项目集中生成满足最低置信度的关联规则，即产生支持度和置信度分别不小于指定的最下支持度和置信度的关联规则。

第一个步骤的任务是高效的找出T中的所有频繁项目集，这是挖掘关联规则的核心问题，也是衡量挖掘关联规则算法效率的主要指标，目前大多数有关挖掘关联规则算法的研究都是针对第一个步骤展开的。第二个步骤只是由频繁项目集生成强规则的枚举探查过程，算法比较简单。

2.2 Apriori算法

Apriori算法是最常用的挖掘关联规则的算法之一，同时也经常以该算法评估和比较其他算法的性能。

主要利用了向下封闭属性：如果一个项集，是频繁项目集，那么它的非空子集必定是频繁项目集。Apriori算法采用一种逐层搜索的迭代方法，k项集用于搜索（k+1）项集。首先，通过扫描事务集，找出所有的频繁1项集，该集合记做L1，然后利用L1找频繁2项集的集合L2，L2用于找L3，如此下去，直到不能再找到任何频繁k项集。最后再在所有的频繁集中找出强规则，即产生用户感兴趣的关联规则。生成频繁项目集的步骤如下：

1） 找出 频繁项目集Lk-1，k>1，若为?，则停止执行。

2） 由步骤（1）中组合任两个有k-2项目相同的Lk-1形成候选k项集Ck。

3） 判断由步骤（2）所找出的Ck，其包含的k-1之子集合是否都出现在步骤（1）中，若成立就保留此Ck；否则就删除。

4） 再检查由步骤（3）所保留的Ck是否满足最小支持度，若符合就成为频繁项目集Lk；否则就删除。

5） 跳至步骤（1）找Lk+1，直到无法产生频繁项目集为止。

2.3 Apriori算法分析

Apriori算法的优点是结构简单，没有复杂的推导，另外利用检查候选生成频繁项目集的方法也大幅度的压缩了候选集的大小。但是Apriori算法在执行速度和效率上仍然存在一定的问题。

1） Apriori算法计算过程中需要产生大量的候选项目集。当候选项集的基数很大，如频繁1-项集很大的时候，由此产生的候选集会以指数方式增长，这样会增加系统I/O的计算负荷，影响算法的执行效率。

2） 需要多次扫描数据库。Apriori算法每生成一次候选项集都需要遍历数据库进行支持度的计数，此外产生候选项集时还需要进行模式上的匹配。这些都会花费大量的时间，影响算法的执行速度。

3 Apriori算法的改进

Apriori算法在形成候选集Ck的过程中，k>1，必须扫描全部频繁项目集Lk-1找出可形成Ck的组合，然后再判断Ck是否为频繁项目集，如此组合过程必定产生很多重复的候选项目集。改进算法在组合形成候选项目集的过程中，修改产生候选项目集的组合方式，将项目集中出现次数最小的项目即首项目置于最前面，并且只考虑出现最少的一种组合方式，以避免重复候选集的产生。同时在生成L1的过程中，将事务数据库由水平存储方式转化为垂直存储方式，即一项事务包含那些项目的存储方式，调整为一个项目属于那些事务的方式存储，转换后的存储方式在判断候选项目集是否为频繁项目集时，可减少所需扫描事务的数量。改进后挖掘频繁项目集的步骤如下：

1） 扫描事务集T并计算C1的出现次数，若满足最小支持度则为L1，并将事务集由水平存储转化为垂直存储并以Ti表示。

2） 组合任意两个L1形成C2，将出现次数最小者置于最前面，称为字首项目，计算C2出现的次数。若C2包含的项目分别为A和B且出现次数A

3） 找出Lk-1，k>2，及T Lk-1

4） 由步骤（3）中组合字首项目相同的两个Lk-1形成Ck，保留字首项目。

5） 判断由步骤（4）所产生的Ck，其包含的Ik-1项是否都出现在步骤（3）中，若成立就保留Ck，并计算否则[TCk=TLk-1?TLk-1]，否则删除。

6） 计算TCk包含事务的数量，若满足最小支持度则为Lk，并保留TLk。

7） 转至步骤（3）找Lk+1，直到无法产生频繁项目集为止。

以上挖掘过程中，步骤（1）将事务集存储方式的转换垂直存储方式，可以提升后续计算候选项目集出现次数的执行效率。步骤（2）将出现次数最小的项目置于项目集字首，并在步骤（4）中只组合字首项目相同的两个Lk-1形成Ck 可以减少产生重复候选项目集的组合计算。在整个过程中通过保留TLk，在后续找出LK+1时可以减少事务集所需的交集运算。相比较Apriori算法挖掘关联规则的过程，改进后的算法的效率更高。

4 实验结果与分析

为了比较算法改进前后的效率，对Apriori算法和改进算法进行测试。算法采用C#实现，实验数据来自于Microsoft SQL Server2008中的示例数据库AdventureWorks-DW，采用视图vAssocSeqLineItems中的52761条记录、21254个事务集进行挖掘关联规则的实验。

在不同支持度下，改进Apriori算法和传统Apriori算法执行时间的测试结果如图1所示。

从图1中可以看出，当数据规模相同而支持度不同时，改进算法的执行时间要比Apriori算法短，并且支持度越小算法执行时间增长越长，而改进算法执行时间的增长速度远低于Apriori算法。

在支持度和事务项数相同，而事务数不同的情况下，改进Apriori算法和传统Apriori算法执行时间的测试结果如图2所示。

从图2中可以看出随着事务数量的增长，算法的执行时间都不断增长，但改进的算法比 Apriori算法增长的速度要慢。

综上所述，改进的Apriori算法避免了重复候选集的产生，采用了新的数据存储方式，减少了扫描数据库的次数，整体上提高了挖掘关联规则算法的执行效率。

5 结论

本文通过分析Apriori算法，对挖掘关联规则产生频繁项目集的步骤进行了改进，并给出了改进算法的完整描述。通过理论分析和实验结果评价来看，提高了算法的执行效率，证明了改进后的算法的有效性。

参考文献：

[1] Chen M S， Han J W， Yu P S. Data Mining： An Overview from a Data base Perspective [J]. IEEE Transactions on Know ledge and Data Engineering， 1996， 8 （6）： 866 883.

[2] 何军， 刘红岩， 杜小勇. 多关系关联规则挖掘研究综述 [J]. 软件学报， 2007， 18（11）： 2752- 2765.

（下转第17页）

（上接第5页）

[3] Han JW， K amber M. Data Mining Concepts and Techniques [M]. Beijing： Higher Education Press， 2001.

[4] PARKJ S ， CHEN M S ， YU P S. Efficient parallel data mining of association rules[C]/ / Proceeding of the ACM SIGMOD In2ternational Conference on Management of Data. New York： ACM， 1995： 31236.

[5] SAVASERE A， OMIECINSKI E， NAVATHE S. An efficient algorithm for mining association rules in large databases[C]/ /Proceedings of the 21st International Conference on Very Large Database. New York： ACM， 1995：4322443.

[6] TOLVONEN H. Sampling large databases for association rules[C]/ / Proceedings of the 22nd International Conference on Very Large Database. Bombay， India： [s. n. ] ， 1996 ： 1342145.

[7] RIN S ， MOTWANI R ， ULLMAN J D. Dynamic item set counting and implication rules for market basked data [C]/ /Proceeding of the ACM SIGMOD International Conference on Management of Data. New York： ACM ， 1997 ：2552264.

[8] 曾万聪，周绪波，戴勃，等.关联规则挖掘的矩阵其法[J]. 计算机工程，2006，32（2）：4524.

[9] 蔡丽艳.数据挖掘算法及其应用研究[M].成都：电子科技大学出版社，2013.