挖掘关联规则ppt课件.ppt

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

1、挖掘关联规则关联规则挖掘事务数据库中关联规则挖掘算法基于限制的关联挖掘1关联规则关联规则反映一个事物与其他事物之间的相互依存性和关联性。如果两个或者多个事物之间存在一定的关联关系，那么，其中一个事物就能够通过其他事物预测到。典型的关联规则发现问题是对超市中的货篮数据进行分析。通过发现顾客放入货篮中的不同商品之间的关系来分析顾客的购买习惯。2什么是关联规则挖掘关联规则挖掘(1993)在事务、关系数据库中的项集和对象中发现频繁模式、关联规则、相关性或者因果结构频繁模式:数据库中频繁出现的项集目的:发现数据中的规律超市数据中的什么产品会一起购买？—啤酒和尿布在买了一台PC

2、之后下一步会购买?我们如何自动对Web文档进行分类?交叉销售、直销等3关联规则基本模型Apriori是关联规则模型中的经典算法。给定一组事务产生所有的关联规则满足最小支持度和最小可信度4关联规则基本模型设I={i1,…,im}为所有项目的集合，D为事务数据库，事务T是一个项目子集（TI）。每一个事务具有唯一的事务标识TID。设A是一个由项目构成的集合，称为项集。事务T包含项集A，当且仅当AT。如果项集A中包含k个项目，则称其为k项集。项集A在事务数据库D中出现的次数占D中总事务的百分比叫做项集的支持度。如果项集的支持度超过用户给定的最小支持度(阈值)，就称该项集

3、是频繁项集。5关联规则基本模型关联规则是形如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

4、X)。confidence(XY)=P(Y

5、X)=support_count(XY)／support_count(X)6频繁模式和关联规则ItemsetX={x1,…,xk}

6、找出满足最小支持度和置信度的所有规则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%{A:3,B:3,D:4,E:3,F:3,AD:3}关联规则Associationrules:AD(60%,100%)DA(60%,75%)7挖掘关联规则—一个例子规则AC支持度=support({A}{C})=50%置信度=support

7、({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%8第5讲：挖掘关联规则关联规则挖掘事务数据库中关联规则挖掘算法基于限制的关联挖掘9Apriori算法的步骤Apriori算法将发现关联规则的过程分为两个步骤：通过迭代、检索出事务数据库中的所有频繁项集，即支持度不低于用户设定的阈值的项集；利用频繁项集构造出满足用户最小信任度的规则。挖掘或识

8、别出所有频繁项集是该算法的核心，占整个计算量的大部分。10频繁项集为了避免计算所有项集的支持度（实际上频繁项集只占很少一部分），Apriori算法引入潜在频繁项集的概念。若潜在频繁k项集的集合记为Ck，频繁k项集的集合记为Lk，m个项构成的k项集的集合为，则三者之间满足关系LkCk。11关联规则的性质性质1：频繁项集的子集必为频繁项集。性质2：非频繁项集的超集一定是非频繁的。Apriori算法运用性质1，通过已知的频繁项集构成长度更大的项集，并将其称为潜在频繁项集。潜在频繁k项集的集合Ck是指由有可能成为频繁k项集的项集组成的集合。以后只需计算潜在频繁项集的支持

9、度，而不必计算所有不同项集的支持度，因此在一定程度上减少了计算量。12Apriori:一种候选产生-测试方法频繁项集的任何子集必须是频繁的如果{beer,diaper,nuts}是频繁的,{beer,diaper}也是每个包含{beer,diaper,nuts}的事务也包含{beer,diaper}Apriori剪枝原则:（性质2）如果一个项集不是频繁的,将不产生/测试它的超集!方法:由长度为k的频繁项集产生长度为(k+1)的候选项集并且根据D测试这些候选（..）13Apriori算法—一个例子数据库TDB第1次扫描C1L1L2C2C2第2次扫描C3L3第3次扫