CHAPTER6-挖掘关联规则ppt课件.ppt

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

1、费高雷通信与信息工程学院2015年春季第6章挖掘频繁模式、关联和相关性：基本概念和方法第6章：挖掘频繁模式、关联和相关性：基本概念和方法基本概念频繁项集挖掘方法那些模式是有趣的：模式评估方法小结2什么是频繁模式分析?频繁模式:频繁出现在数据集中的模式（如项集、子序列或子结构）首先被Agrawal,ImielinskiandSwami在1993年的SIGMOD会议上提出，称为频繁项集和关联规则挖掘驱动:发现数据中的内在规律超市数据中的什么产品会一起购买？—啤酒和尿布在买了一台PC之后下一步会购买?哪种DNA对这种药物敏感?我们如何自动对Web文档进行分类?更加广泛的用处购物篮分析、交叉销

2、售、直销点击流分析、DNA序列分析等等3什么是频繁模式分析?频繁模式挖掘为什么重要?频繁模式:数据集内在和重要的属性许多重要数据挖掘任务的基础关联,相关,和因果分析序列模式,空间模式（比如子图）时空模式分析,多媒体,时间序列和流数据分类:discriminative,frequentpatternanalysis聚类分析:基于频繁模式的聚类数据仓库:icebergcubeandcube-gradient语义数据压缩:fascicles更广泛应用5关联规则基本模型设I={i1,…,im}为所有项目的集合；D为事务数据库，事务T是一个项目子集（TI）。每一个事务具有唯一的事务标识TID项

3、集：由项目构成的集合，为了方便表述用用A表示事务T包含项集A，当且仅当AT如果项集A中包含k个项目，则称其为k项集支持度：项集A在事务数据库D中出现的次数占D中总事务的百分比频繁项集（或大项集）：项集的支持度超过用户给定的最小支持度阈值I={a,b,c,d,e,f}若A={a,c}，则A的支撑度为50%项属性一个事物数据对象6关联规则基本模型关联规则是形如XY的逻辑蕴含式，其中XI，YI，且XY=如果事务数据库D中有s%的事务包含XY，则称关联规则XY的支持度为s%实际上，支持度是一个概率值，是一个相对计数support(XY)=P(XY)项集的支持度计数(频率)s

4、upport_count包含项集的事务数若项集X的支持度记为support(X)，规则的信任度为support(XY)／support(X)是一个条件概率P(Y

5、X)confidence(XY)=P(Y

6、X)=support_count(XY)／support_count(X)7频繁模式和关联规则itemsetX={x1,…,xk}找出满足最小支持度和置信度的所规则XY支持度s：事务包含XY的概率置信度c：事务含X也包含Y的条件概率顾客购买尿布顾客购买二者顾客购买啤酒Transaction-idItemsbought10A,B,D20A,C,D30A,D,E40B,E,F50

7、B,C,D,E,F令supmin=50%,confmin=50%频繁模式：{A:3,B:3,D:4,E:3,AD:3}关联规则:AD(60%,100%)DA(60%,75%)8挖掘关联规则—一个例子规则AC：支持度=support({A}{C})=50%置信度=support({A}{C})/support({A})=66.6%最小支持度50%最小置信度50%Transaction-idItemsbought10A,B,C20A,C30A,D40B,E,FFrequentpatternSupport{A}75%{B}50%{C}50%{A,C}50%9挖掘关联规则(实际例子)

8、闭频繁项集和极大频繁项集一个长模式包含子模式的数目：e.g.,{a1,…,a100}contains(1001)+(1002)+…+(110000)=2100–1=1.27*1030sub-patterns!解:引入闭频繁项集和极大频繁项集闭项集：不存在具有相同支持度的真超项集闭频繁项集：如果X是频繁的，且不存在真超项集（super-pattern）Y（XY），使X、Y有相同的支持度计数(proposedbyPasquier,etal.@ICDT’99)极大频繁项集：如果X是频繁的，并且不存在超项集Y使得XY，并且Y是频繁的(proposedbyBayardo@SIGMOD’98)

9、两者有不同，极大频繁项集定义中对真超集要松一些11极大频繁项集BorderInfrequentItemsetsMaximalItemsets极大频繁项集的真超项集不频繁闭频繁项集最大频繁项集存在的问题：最大频繁项集的子集是频繁的，但无法推断出其具体的支持度闭频繁项集的集合包含频繁项集的完整信息（包括支持度）例子：数据库包含两个事物，且令最小支持度为1,闭频繁项集{a1,…,a100}:1{a1,…,a5