数据挖掘关联规则.ppt

1关联规那么

AssociationRules

2内容提要引言Apriori算法Frequent-patterntree和FP-growth算法多维关联规那么挖掘相关规那么基于约束的关联规那么挖掘总结

3关联规那么挖掘在事务数据库,关系数据库和其它信息库中的项或对象的集合之间,发现频繁模式,关联,相关,或因果关系的结构.频繁模式:数据库中出现频繁的模式(项集,序列,等等)

4根本概念项集事务关联规那么事务数据集(例如右图)事务标识TID：每一个事务关联着一个标识

5根本概念支持度sD中包含A和B的事务数与总的事务数的比值规那么A?B在数据集D中的支持度为s,其中s表示D中包含A?B(即同时包含A和B)的事务的百分率.

6根本概念支持度sD中包含A和B的事务数与总的事务数的比值规那么A?B在数据集D中的支持度为s,其中s表示D中包含A?B(即同时包含A和B)的事务的百分率.

7根本概念可信度cD中同时包含A和B的事务数与只包含A的事务数的比值规那么A?B在数据集D中的可信度为c,其中c表示D中包含A的事务中也包含B的百分率.即可用条件概率P(B|A)表示.confidence(A?B)=P(B|A)条件概率P(B|A)表示A发生的条件下B也发生的概率.

8关联规那么挖掘两个根本步骤Stepone:找出所有的频繁项集满足最小支持度Steptwo:找出所有的强关联规那么由频繁项集生成关联规那么保存满足最小可信度的规那么

9Apriori性质定理(Apriori性质):假设A是一个频繁项集,那么A的每一个子集都是一个频繁项集.证明:设n为事务数.假设A是l个事务的子集,假设A’?A,那么A’为l’(l’?l)个事务的子集.因此,l/n≥s(最小支持度),l’/n≥s也成立.

10Apriori算法Apriori算法是一种经典的生成布尔型关联规那么的频繁项集挖掘算法.算法名字是缘于算法使用了频繁项集的性质这一先验知识.思想:Apriori使用了一种称作level-wise搜索的迭代方法,其中k-项集被用作寻找(k+1)-项集. 首先,找出频繁1-项集,以L1表示.L1用来寻找L2,即频繁2-项集的集合.L2用来寻找L3,以此类推,直至没有新的频繁k-项集被发现.每个Lk都要求对数据库作一次完全扫描..

11生成频繁项集中心思想:由频繁(k-1)-项集构建候选k-项集方法找到所有的频繁1-项集扩展频繁(k-1)-项集得到候选k-项集剪除不满足最小支持度的候选项集

12Apriori:一种候选项集生成-测试方法Apriori剪枝原理:假设任一项集是不频繁的,那么其超集不应该被生成/测试!方法:由频繁k-项集生成候选(k+1)-项集,并且在DB中测试候选项集性能研究显示了Apriori算法是有效的和可伸缩(scalablility)的.

13TheApriori算法—一个例如DatabaseTDB1stscanC1L1L2C2C22ndscanC3L33rdscan

14频繁模式挖掘的挑战挑战屡次扫描事务数据库巨大数量的候选项集繁重的计算候选项集的支持度工作改进Apriori:大体的思路减少事务数据库的扫描次数缩减候选项集的数量使候选项集的支持度计算更加方便

15内容提要引言Apriori算法Frequent-patterntree和FP-growth算法多维关联规那么挖掘相关规那么基于约束的关联规那么挖掘总结

16频繁模式挖掘的瓶颈屡次扫描数据库是高代价的长模式的挖掘需要屡次扫描数据库以及生成许多的候选项集找出频繁项集i1i2…i100扫描次数:100候选项集的数量:(1001)+(1002)+…+(110000)=2100-1=1.27*1030!瓶颈:候选项集-生成-测试我们能否防止生成候选项集?

17不生成候选项集的频繁模式挖掘利用局部频繁的项由短模式增长为长模式“abc”是一个频繁模式得到所有包含“abc”的事务:DB|abc“d”是DB|abc的一个局部频繁的项?abcd是一个频繁模式

18FPGrowth算法(Han,Pei,Yin2000)Apriori算法的一个有问题的方面是其候选项集的生成指数级增长的来源另一种方法是使用分而治之的策略(divideandconquer)思想:将数据库的信息压缩成一个描述频繁项相关信息的频繁模式树

19利用FP-树进行频繁模式挖掘思想:频繁模式增长递归地增长频繁模式借助模式和数据库划分方法对每个频繁项,构建它的条件模式基,然后构建它的条件FP-树.对每个新