摘 要 Apriori算法是发现频繁项目集的经典算法，但是该算法需反复扫描数据库，因此效率较低。本文介绍了Apriori算法的思想，并分析了该算法的性能瓶颈。在此基础上，针对Apriori算法提出了一种改进方法，该方法采用转置矩阵的策略，只扫描一次数据库即可完成所有频繁项目集的发现。与其他经典的算法相比，本文提出的算法在项目集长度较大时，性能明显提高。
关键字 关联规则，支持度，置信度，Apriori
1 引言
关联规则挖掘就是在海量的数据中发现数据项之间的关系，是数据挖掘领域中研究的热点问题。1993年Agrawal等人[1]首先提出了交易数据库中不同商品之间的关联规则挖掘，并逐渐引起了专家、学者的重视。关联规则挖掘问题可以分为：发现频繁项目集和生成关联规则两个子问题，其中发现所有的频繁项目集是生成关联规则的基础。近年来，发现频繁项目集成为了关联规则挖掘算法研究的重点，在经典的Apriori算法的基础上提出里大量的改进算法。Savasere等[2]设计了基于划分(partition)的算法，该算法可以高度并行计算，但是进程之间的通信是算法执行时间的主要瓶颈；Park等[3]通过实验发现寻找频集主要的计算是在生成频繁2-项集上，利用这个性质Park等引入杂凑（Hash）技术来改进产生频繁2-项集的方法，该算法显著的提高了频繁2-项集的发现效率；Mannila等[4]提出：基于前一遍扫描得到的信息，对此仔细地作组合分析，可以得到一个改进的算法了。针对Mannila的思想Toivonen[5]进一步提出：先使用从数据库中抽取出来的采样得到一些在整个数据库中可能成立的规则，然后对数据库的剩余部分验证这个结果。Toivonen的算法相当简单并显著地减少了I/O代价，但是一个很大的缺点就是产生的结果不精确，存在数据扭曲(data skew)。
上述针对经典Apriori算法的改进算法在生成频繁项目集时都需要多次扫描数据库，没有显著的减少I/O的代价。本文在分析了经典的Apriori算法的基础上，给出了一种改进的方法，该方法采用转置矩阵的策略，只扫描一次数据库即完成频繁项目集的发现，在项目集长度较大时，性能明显提高。
2 Apriori算法
2.1 基本概念
设I={i1, i2,…, im}是二进制文字的集合，其中的元素称为项(item)。定义交易(transaction)T为项的集合，并且TÍI，定义D为交易T的集合。设X是I中若干项的集合，如果XÍT，那么称交易T包含X。项目集中包含项的个数成为项目集长度。
关联规则是形如XÞY的蕴涵式，这里XÌI, YÌI，并且XÇY=F。
规则XÞY在交易数据库D中的支持度（support）是交易集合中包含X和Y的交易数与所有交易数之比，记为support(XÞY)，即support(XÞY)= 页码：123456789101112131415161718192021222324252627282930313233