王秀平-数据挖掘关联规则.ppt

《王秀平-数据挖掘关联规则.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、1第5章：挖掘关联规则关联规则挖掘事务数据库中(单维布尔)关联规则挖掘的可伸缩算法挖掘各种关联/相关规则基于限制的关联挖掘-顺序模式挖掘小结2关联规则关联规则反映一个事物与其他事物之间的相互依存性和关联性。如果两个或者多个事物之间存在一定的关联关系，那么，其中一个事物就能够通过其他事物预测到。典型的关联规则发现问题是对超市中的货篮数据（MarketBasket）进行分析。通过发现顾客放入货篮中的不同商品之间的关系来分析顾客的购买习惯。3什么是关联规则挖掘关联规则挖掘首先被Agrawal,ImielinskiandSwami在1993年的SIGMOD会议上提

2、出在事务、关系数据库中的项集和对象中发现频繁模式、关联规则、相关性或者因果结构频繁模式:数据库中频繁出现的项集目的:发现数据中的规律超市数据中的什么产品会一起购买？—啤酒和尿布在买了一台PC之后下一步会购买?哪种DNA对这种药物敏感?我们如何自动对Web文档进行分类?4频繁模式挖掘的重要性许多重要数据挖掘任务的基础关联、相关性、因果性序列模式、空间模式、时间模式、多维关联分类、聚类分析更加广泛的用处购物篮分析、交叉销售、直销点击流分析、DNA序列分析等等5关联规则基本模型IBM公司Almaden研究中心的R.Agrawal首先提出关联规则模型，并给出求解算

3、法AIS。随后又出现了SETM和Apriori等算法。其中，Apriori是关联规则模型中的经典算法。给定一组事务产生所有的关联规则满足最小支持度和最小可信度6关联规则基本模型设I={i1,…,im}为所有项目的集合，D为事务数据库，事务T是一个项目子集（TI）。每一个事务具有唯一的事务标识TID。设A是一个由项目构成的集合，称为项集。事务T包含项集A，当且仅当AT。如果项集A中包含k个项目，则称其为k项集。项集A在事务数据库D中出现的次数占D中总事务的百分比叫做项集的支持度。如果项集的支持度超过用户给定的最小支持度阈值，就称该项集是频繁项集（或大项集

4、）。7关联规则基本模型关联规则是形如XY的逻辑蕴含式，其中XI，YI，且XY=。如果事务数据库D中有s%的事务包含XY，则称关联规则XY的支持度为s%实际上，支持度是一个概率值。是一个相对计数。support(XY)=P(XY)项集的支持度计数(频率)support_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)8

7、频繁模式和关联规则ItemsetX={x1,…,xk}找出满足最小支持度和置信度的所规则XY支持度,s,事务包含XY的概率置信度,c,事务含X也包含Y的条件概率.顾客购买尿布顾客购买二者顾客购买啤酒Transaction-idItemsbought10A,B,D20A,C,D30A,D,E40B,E,F50B,C,D,E,F令supmin=50%,confmin=50%Freq.Pat.:{A:3,B:3,D:4,E:3,AD:3}关联规则Associationrules:AD(60%,100%)DA(60%,75%)9挖掘关联规则—一个例子规则A

8、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%10闭频繁项集and极大频繁项集一个长模式包含子模式的数目,e.g.,{a1,…,a100}contains(1001)+(1002)+…+(110000)=2100–1=1.27*1030sub-pat

9、terns!解:Mineclosedpatternsandmax-patternsinstead一个频繁项集X是闭的，如果X是频繁的，且不存在真超项集nosuper-patternYכX,有相同的支持度计数(proposedbyPasquier,etal.@ICDT’99)项集X是极大频繁项集ifXisfrequentandthereexistsnofrequentsuper-patternYכX(proposedbyBayardo@SIGMOD’98)两者有不同，极大频繁项集定义中对真超集要松一些。11闭频繁项集and极大频繁项集Exercise.DB=

10、{,}Min_sup=1