Apriori算法的改进

摘要：在数据挖掘中关联规则中是一个重要的研究方向。Apriori算法是关联规则中最著名的算法。本文分析了Apriori算法存在的不足，与可以改进的方向。并提出了一种基于压缩事务项的改进方法，以提高Apriori算法的效率。

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

中图分类号：TP301文献标识码：A文章编号：1009-3044(2007)04-11096-01

1 引言

关联规则挖掘是在数据库挖掘领域中较早提出的一个研究方向，目前该领域的新算法、新应用层出不穷，相关问题定义和背景也不尽相同。关联分析是揭示数据之间相互关系的一项数据挖掘任务，而这种关系在数据库中没有表现出来。关联规则就是较早提出于超市的购物篮的分析，这也是数据挖掘领域里最为活跃的研究方向之一。在关联规则中其中以Apriori算法是比较经典的一个算法，本文章就是对Apriori算法的一个研究。

2 Apriori算法分析

2.1 Apriori算法的描述

Apriori算法是R.Agrawal和R.Srikant在1994年提出的基本的关联规则挖掘算法。为了减少候选数据项集的数目，Apriori算法使用逐层搜索的方法，通过对数据库D的所有事务数据项扫描来发现所有的频繁项目集。通过频繁项集的性质知道，只有哪些确认是频繁项的候选集所称成的超级才可能是频繁项集。所以只用频繁项集生成下一趟扫描的候选集，也就是用Li-1生成Ci(L为频繁项集的集合，C候选项集的集合，i为当前扫描数据库的次数)，在每次扫描数据库时只考虑具有同数目数据项的集合。Apriori算法可以生成相对较少的候选数据项集，候选数据项集不必再反复地根据数据库中的记录产生，而是在寻找k频繁数据项集的过程中由前一次循环产生的k-1频繁数据项集一次产生。

算法的描述：

Apriori算法：

Apriori-Gen算法是用来生成除第一趟之外的每一趟的候选项目集。所有的单元素项目集都作为第一趟的候选集。前一趟发现的大项目集的集合Li-1与自身进行连接运算以确定候选项。当输入Li-1时，Apriori-Gen能够生成大小为i的频繁项。

2.2 算法的不足

虽然Apriori算法在很多情况下可以大幅的消减它的候选项集数目，产生很好的效果。但是它还是有一些的不足：

(1)在生成候选项集的时候会产生许多最后证明不是频繁项集的候选项集，如果能在生成候选频繁项集之前能判断出某些候选集不是频繁项集，则这样可以避免在扫描数据库时的开销；

(2)连接程序中相同的项目重复比较的太多，如果能避免这些重复的比较，则可以提高算法的效率；

(3)有些事务项在一次扫描之后可以判断出下次不必再扫描，但结果又被多次扫描。如果能避免这些稍描，则可以提高算法效率。

3 算法改进

这个改进只是对上面说的第三个不足进行改进。我们知道Apriori算法的第k次的候选集是由第k-1次的频繁项目集通过函数Apriori-Gen产生的。那么在第k-1次扫描数据库时，如果有一个事务t它不包含任何的一个候选项集，即任何一个C(k-1)∩t=φ。那么这个事务t也一定不包含以后C(k-1)所产出任何候选集，即C(m)∩t=φ(m>k-1)。那么如果在k-1次后还扫描这个事务项，就会浪费系统的开销，特别是当候选项很多时，就要对一个本来不用比较的事务数据项进行多次不必要的扫描和比较，这样影响了扫描数据库的效率。如果对这些不必要的事务项进行标记，那么就会提高下次的扫描效率。同理也可以标记那些虽然当前包含候选项集，但其包含的项数等于当前候选项的项数的事务。因为在第k次扫描数据库后，当k+1次扫描数据库时，此时的候选项数就会比上次多1即k+1项。那么与上次候选项的项数相同的事务(只有k项)就不可能包含任何一个C(k+1)，所以这个事务在第k次扫描数据库时可以也可以标记。

3.1 Apriori算法改进

这个算法是在每次扫描数据库后就会标记数据库中的一些对下次扫描时没有用的事务项。这样可以在不动数据库的前提下压缩要扫描的事务，提高算法的扫描效率，提高了输入输出效率。

3.2 其它优化的讨论

当然还有其它的许多优化的方法，这里只是表达本人自己对Apriori算法的一些改进方法。对Apriori算法还有以下的优化：

3.2.1 基于散列(hash)的技术

这种散列的技术可用于压缩候选k-项集Ck。在由C1中的候选1-项集产生频繁1-项集L1时，可使用散列函数将每个事务的所有项集散列到不同的桶中，并对对应的桶进行计数，通过桶的计数寻找候选频繁项集。这种技术可以大大压缩待考察的K-项集，尤其有利于改进频繁2-项集的生成效率，这就是DHP算法。

3.2.2 基于划分的方法

使用划分技术，可以只需要对数据库进行两遍扫描，就可以发现全部频繁集，从而大大降低对数据库的扫描遍数。

3.3.3 选样

该方法的基本思想是，选取给定数据库D的随机样本S，然后在S中而非是D中搜索频繁项集。这种方法是以精度的牺牲换取搜索速度和效率。为避免丢失全局频繁项集，可以使用比全局支持度阀值低的样本支持度阀值来对样本寻找频繁项集。

4 结束语

频繁项集的挖掘发现强规则的基础，而连接与剪枝操作是逐层迭代求解频繁项集中的核心算法。文中是对事务项进行了“压缩”，这样在扫描数据库时就提高了效率。特别对候选项集很多时效果更好。当然算法还存在一定的缺陷，那就是对数据库需要进行多次扫描。今后的工作是在“压缩”事务的基础上，尽量减少对数据库的扫描。

参考文献：

[1]杨晓平. 关联规则Apriori算法的改进[J]. 浙江海洋学报(自然科学版)，25(2),176-195.

[2]Margaret H.Dunham著，郭崇慧，田凤占，勒晓明，等译. 数据挖掘教程[M]. 清华大学出版社,2005.141-154.

[3]章兢, 张小刚,等. 数据挖掘算法及其工程应用[M]. 北京:机械工业出版社, 2006.77-98.

[4]Rakesh Agrawal, Tomasz Imielinski, Arun Swami. Mining Association Rules between Sets of Items in Large Databases[J]. IBM Almaden Research Center 650 Harry Road, San Jose, CA 95120.

[5]R. Agrawal, T. Imielinski, and A. Swami. Mining association rules between sets of items in large databases. Proceedings of the ACM SIGMOD Conference on Management of data, p.p. 207-216, May 1993.

[6]R. Agrawal, and J. Shafer. Parallel mining of association rules: Design, Implementation, and Experience. IEEE Trans. Knowledge and data engineering, 1996,8:962-969.

本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。