《数据挖掘关联规则》PPT课件

《《数据挖掘关联规则》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、关联规则AssociationRules1内容提要引言Apriori算法Frequent-patterntree和FP-growth算法多维关联规则挖掘相关规则基于约束的关联规则挖掘总结2关联规则关联规则表示了项之间的关系示例:cereal,milkfruit“买谷类食品和牛奶的人也会买水果.”商店可以把牛奶和谷类食品作特价品以使人们买更多的水果.3市场购物篮分析分析事务数据库表我们是否可假定?Chips=>SalsaLettuce=>SpinachPersonBasketAChips,Salsa,Cookies,Crackers,Coke,B

2、eerBLettuce,Spinach,Oranges,Celery,Apples,GrapesCChips,Salsa,FrozenPizza,FrozenCakeDLettuce,Spinach,Milk,Butter4基本概念通常,数据包含:TIDBasket事务ID项的子集5关联规则挖掘在事务数据库,关系数据库和其它信息库中的项或对象的集合之间,发现频繁模式,关联,相关,或因果关系的结构.频繁模式:数据库中出现频繁的模式(项集,序列,等等)6基本概念项集事务关联规则事务数据集(例如右图)事务标识TID：每一个事务关联着一个标识Transa

3、ction-idItemsbought10A,B,C20A,C30A,D40B,E,F7度量有趣的关联规则支持度sD中包含A和B的事务数与总的事务数的比值规则AB在数据集D中的支持度为s,其中s表示D中包含AB(即同时包含A和B)的事务的百分率.8度量有趣的关联规则可信度cD中同时包含A和B的事务数与只包含A的事务数的比值规则AB在数据集D中的可信度为c,其中c表示D中包含A的事务中也包含B的百分率.即可用条件概率P(B

4、A)表示.confidence(AB)=P(B

5、A)条件概率P(B

6、A)表示A发生的条件下B也发生的概率.9度量有趣的

7、关联规则关联规则根据以下两个标准(包含或排除):最小支持度–表示规则中的所有项在事务中出现的频度最小可信度-表示规则中左边的项(集)的出现暗示着右边的项(集)出现的频度10市场购物篮分析I是什么?事务IDB的T是什么?s(Chips=>Salsa)是什么?c(Chips=>Salsa)是什么?事务ID购物篮AChips,Salsa,Cookies,Crackers,Coke,BeerBLettuce,Spinach,Oranges,Celery,Apples,GrapesCChips,Salsa,FrozenPizza,FrozenCakeDLe

8、ttuce,Spinach,Milk,Butter,Chips11Stepone:频繁项集项集–任意项的集合k-项集–包含k个项的项集频繁(或大)项集–满足最小支持度的项集若I包含m个项,那么可以产生多少个项集?12Steptwo:强关联规则给定一个项集,容易生成关联规则.项集:{Chips,Salsa,Beer}Beer,Chips=>SalsaBeer,Salsa=>ChipsChips,Salsa=>Beer强规则是有趣的强规则通常定义为那些满足最小支持度和最小可信度的规则.13关联规则挖掘两个基本步骤Stepone:找出所有的频繁项集满足

9、最小支持度Steptwo:找出所有的强关联规则由频繁项集生成关联规则保留满足最小可信度的规则14内容提要引言Apriori算法Frequent-patterntree和FP-growth算法多维关联规则挖掘相关规则基于约束的关联规则挖掘总结15生成频繁项集Naïvealgorithmn<-

10、D

11、foreachsubsetsofIdol<-0foreachtransactionTinDdoifsisasubsetofTthenl<-l+1ifminimumsupport<=l/nthenaddstofrequentsubsets16生成频繁项集na

12、ïvealgorithm的分析I的子集:O(2m)为每一个子集扫描n个事务测试s为T的子集:O(2mn)随着项的个数呈指数级增长!我们能否做的更好?17Apriori性质定理(Apriori性质):若A是一个频繁项集,则A的每一个子集都是一个频繁项集.证明:设n为事务数.假设A是l个事务的子集,若A’A,则A’为l’(l’l)个事务的子集.因此,l/n≥s(最小支持度),l’/n≥s也成立.18Apriori算法Apriori算法是一种经典的生成布尔型关联规则的频繁项集挖掘算法.算法名字是缘于算法使用了频繁项集的性质这一先验知识.思想:Apr

13、iori使用了一种称作level-wise搜索的迭代方法,其中k-项集被用作寻找(k+1)-项集.首先,找出频繁1-项集,以L1表示.L