基于哈希表的关联规则挖掘算法

更新时间:2024-01-15 作者:用户投稿原创标记本站原创 点赞:13410 浏览:57656

摘 要 :经过分析关联规则中Apriori算法存在的不足,为减少对事务数据库的扫描次数,缩减产生频繁项集的时间,列出两种基于哈希表的计算项集支持计数的方法以及利用哈希表来进行项集的地址定位的方法,使得生成频繁项集的效率有所提高.

关 键 词 :关联规则;Apriori算法;频繁项集;哈希表

中图分类号:TP312 文献标识码:A 文章编号:16727800(2013)007006903

1.Apriori算法分析

Apriori算法是一种最有影响的挖掘布尔关联规则频繁项集的算法,采用了一种称作逐层搜索的迭代方法,项集用于探索项集,其过程由连接与剪枝组成.该算法中项集(Itemset)的概念即为项的集合,包含K个项的集合为K项集.项集出现的频率是包含项集的事务数,称为项集的频率.如果某项集满足最小支持度,则称它为频繁项集.


1.1 算法步骤

步骤如下:

(1)设定最小支持度s和最小置信度c.

(2)Apriori算法使用候选项集.首先,产生出候选的项的集合.即候选项集,若候选项集的支持度大于或等于最小支持度,则该候选项集为频繁项集.

(3)在Apriori算法的过程中,首先,从数据库读入所有的事务,每个项都被看作候选1项集,得出各项的支持度,再使用频繁1项集合集来产生候选2项集集合,因为先验原理保证所有非频繁的1项集的超集都是非频繁的.

(4)扫描数据库,得出候选2项集集合,找出频繁2项集,并利用这些频繁2项集集合来产生候选3项集.

(5)重复扫描数据库,与最小支持度比较,产生更高层次的频繁项集,再从该集合里产生下一级候选项集,直到不再产生新的候选项集为止.

5.结语

本文所讨论的基于事务数据哈希表的Apriori算法通过两两扫描各项,对事务编号依次进行比较,可以计算出k项集的支持计数,但是需要对哈希表多次扫描和对各项的比较操作.而二维哈希表通过使用两个哈希函数,可以快速地定位二维数组单元的位置,从而计算各2项集的支持计数,但是只限于对2项集的操作.对k项集的存取同样也可以通过哈希函数来定位地址,使得算法效率得到提高.

相关论文范文