王铮 周国光

重庆大学计算机学院 重庆 400044

0 引言

为了方便快速的从事务数据库中挖掘出频繁项集，本文依据Apriori算法的思路加以改进，将事务数据库转换成0-1矩阵，通过0-1矩阵可很快计算出各个候选集的支持度计数，省去了 Apriori算法中的连接步骤和删除步骤这样避免了传统Apriori算法频繁扫描数据库的操作，从而提高了算法的效率。

1 关联规则Apriori算法

Apriori算法是R.Agrawal和R.Srikant于1994年提出的为布尔关联规则挖掘频繁项集的原创性算法。Apriori使用一种称作逐层搜索的迭代方法，k项集用于探索(k+1)项集。首先，通过扫描数据库，累积每个项的计数，并收集满足最小支持度的项，找出频繁1项集的集合。该集合记作L1。然后L1用于找频繁2项集的集合L2，L2用于找L3，如此下去，直到不能再找到频繁k项集。找每个Lk需要一次数据库扫描。为提高频繁项集逐层产生的效率，Apriori算法利用了一个性质用于压缩搜索空间。Apriori性质:频繁项集的所有非空子集也必须是频繁的 Apriori性质在挖掘频繁项集中的应用可以用Lk-1产生Lk为例来说明，用Lk-1产生Lk包含两步，即连接步和剪枝步。

（1）连接步：由Apriori性质，频繁项集的子集一定频繁。Lk的任一项集一定是Lk-1某项集的超集。通过Lk-1内部项集间的连接，生成候选 k-项集记作Ck。如果两个项集有(k-2)个相同的项，Lk-1的元素是可连接的。

（2）剪枝步：由Apriori性质：任何非频繁的(k-1)项集都不是频繁k项集的子集。因此如果候选k项集的(k-1)项子集不在Lk-1中，则改候选也不可能是频繁的，从而从Ck中删除。

2 改进算法

2.1 Apriori算法缺陷

Apriori算法作为关联规则挖掘的经典算法，能够比较有效的产生频繁项集，但也存在几个缺陷：