数据挖掘关联分析.doc

数据挖掘关联分析
1 引言
在大型数据库中,关联规则挖掘是最常见的数据挖掘任务之一. 关联规则挖掘就是从大量数据中发现项集之间的相关联系. Apriori 算法,前者采用逐层搜索的迭代策略,先产生候选集,再对候选集进行筛选,然后产生该层的频繁集。
2 Apriori 算法
Apriori 算法是关联规则挖掘中最基本也是最常见的算法. 它是由 Agrawal 等人于 1993年提出的一种最有影响的挖掘布尔关联规则频繁项集的算法,主要用来在大型数据库上进行快速挖掘关联规则。
算法基本思想
Apriori 算法采用逐层迭代搜索方法,使用候选项集来找频繁项集。其基本思想是: 首先找出所有频繁1-项集的集合Ll,L1用于找频繁2-项集的集合L2,而L2用于找L3,如此下去,直到不能找到频繁k-项集。并利用事先设定好的最小支持度阈值进行筛选,将小于最小支持度的候选项集删除,再进行下一次的合并生成该层的频繁项集。经过筛选可减少候选项集数,从而加快关联规则挖掘的速度。
算法的挖掘
如果一个项集是频繁的,那么它的所有子集都是频繁的
先验原理成立的原因:
一个项集的支持度不会超过其任何子集的支持度
该性质称作支持度的反单调性质

Apriori 算法使用了Apriori性质来产生候选项集. 任何非频繁的( k-1 )项集都不可能是频繁k-项集的子集. 因此,如果一个候选k-项集的( k-1 )-子集不在Lk-1中,则该候选项集也不可能是频繁的,从而可以从Ck中删除.
-1 生成 Lk
设定k=1
扫描事务数据库一次,生成频繁的1-项集
如果存在两个或以上频繁k-项集,重复下面过程:
[候选产生] 由长度为k的频繁项集生成长度为k+1的候选项集
[候选前剪枝] 对每个候选项集,若其具有非频繁的长度为k的子集,则删除该候选项集
[支持度计算] 扫描事务数据库一次,统计每个余下的候选项集的支持度
[候选后剪枝] 删除非频繁的候选项集,仅保留频繁的(k+1)-项集,设定k = k+1
Apriori流程图

扫描事务数据库,决定每个候选项集的支持度。
为了减少比较次数,将候选项集保存在散列(hash)结构中,将每个事务与保存在散列 结构的候选项集作匹配


当前是列出我们实验中用到的一个候选项集:
{1 4 5}, {1 2 4}, {4 5 7}, {1 2 5}, {4 5 8}, {1 5 9}, {1 3 6}, {2 3 4}, {5 6 7}, {3 4 5}, {3 5 6}, {3 5 7}, {6 8 9}, {3 6 7},