基于临时表的Apriori改进算法(2)

为便于算法的比较,选取文献[6]中Apriori算法使用的AllElectronics某分店的事务数据库中的数据进行算法模拟,如表1所示。

TID	项的列表
T100	I1,I2,I5
T200	I2,I4
T300	I2,I3
T400	I1,I2,I4
T500	I1,I3
T600	I2,I3
T700	I1,I3
T800	I1,I2,I3,I5
T900	I1,I2,I3

表1

  假定min_sup=2,Apriori算法执行过程:

(1)    算法第一次扫描数据库，确定1-项集及各元素的覆盖频度。如图1所示：

  

(2)    利用L₁⊕L₁来产生候选2-项集C₂，由C₂确定频繁2-项集。如图2所示：

             

     (3) 利用L₂⊕L₂进行连接操作，获得候选3-项集C₃，为{(I1,I2,I3),(I1,I2,I5),(I1,I3,I5),

(I2,I3,I5),(I2,I4,I5)}。根据Apriori“一个频繁项集的所有子集也是频繁的”的性质，可以确定后四个项集不可能是频繁的，因此可以删除它们，从而减少了扫描次数。结果如图3所示：

                    

图3

(4)  利用L₃⊕L₃进行连接操作得到C₄，根据Apriori性质可知C₄=Φ。算法至此结束。

由此可见，Apriori算法每次扫描都要彻底扫描整个数据库D，而改进后的算法及时的将不符合要求的项集删除，从而减少了下次扫描数据库的记录数；Apriori算法进行连接操作时需生成完整的项集，而使用临时表则只需将最后一个不同的项进行连接，从而节省了大量的存储空间。算法比较结果如下表所示：

表2

说明：表2中数据库规模是指数据库中的记录数，空间耗费是指生成的候选项集所占的空间。从表2可以看到，在扫描规模上，Apriori每次需要对所有的事务数据库进行扫描，而基于临时表的改进算法在第二趟数据扫描后，数据中二元组 T200，T300，T500，T600，T700被删除，第三次的扫描量减至4。在空间耗费上，第一次对 5 个单项进行判断每一个单项占一位空间，需要的空间耗费为 5。第二次进行 JOIN 运算时，需要（C14+C13+C12+C11）×2=10×2=20 个单元空间，第三次进行 JOIN 运算，需要（C13+C12+C11）×3=18个单元空间。临时表压缩算法采用了逐个动态生成频繁项，依次所需空间均为 1。

 

    本文在对Apriori挖掘算法的深入研究基础上，提出了基于临时表的改进算法。通过分析比较，在减少扫描数据库中记录数量和进行连接操作所需空间耗费上，取得了较好的效果。与 Apriori相比，基于临时表的改进算法在数据规模及空间耗费上均占有优势，随数据规模的增大，这种优势将更加明显。

 

1 R Agrawal,R Wrikant. Fast Algorithms for Mining Association Rules in Large Databases. Proc,20^th int’l Conf.Very large databases.1994：478~499

2 Margarent H.Dunham. Data Mining Introductory and Advanced Topics. Southern Mehodist University.2003

3 Brin S, Motwani R. Dynamic Itemset Counting and Implication Rules for Market Basket Data. In: Proc. Of the 1997 ACM_SIGMOD Int’1 Conf, On the Management of Data. New York: ACM Press, 1997

4 陈江平,傅仲良,徐志红.一种Apriori的改进算法.武汉大学学报(信息科学版),2003,2.

5 李雄飞，李军.数据挖掘与知识发现.北京：高等教育出版社，2003.

6 韩家炜.数据挖掘概念与技术.北京:机械工业出版社,2001

7 Savasere A,Ong B, Mitbander B. An efficient algorithm for mining association rules in large databases[A]. In Proc 1995, Int Conf Very Large Databases(VLDB’95)[C].1995

8 Bayardo R J, Agrawal R. Mining the Most Interesting Rules[c]. Processing of the 5^th International Conference on knowledge Discovery and Data Mining. San Diego: ACM

Press, 1999:145-154