资源描述:
《《数据挖掘应》ppt课件》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、第12讲数据挖掘应用Chapter12ApplicationsofDataMining徐从富(CongfuXu),PhD,Asso.Professor浙江大学人工智能研究所2005年5月17日第一稿2006年10月30日第二次修改浙江大学研究生《人工智能引论》课件目录关联规则挖掘聚类分析分类与预测Web挖掘流数据挖掘隐私保护数据挖掘关联规则挖掘关联规则挖掘简介关联规则基本模型关联规则价值衡量与发展关联规则简介关联规则反映一个事物与其他事物之间的相互依存性和关联性。如果两个或者多个事物之间存在一定的关联关系,那么,其中一个事物就能够通过其他事物预测到。典型的关联规则发现问题是对超市中的货篮数
2、据(MarketBasket)进行分析。通过发现顾客放入货篮中的不同商品之间的关系来分析顾客的购买习惯。什么是关联规则挖掘关联规则挖掘首先被Agrawal,ImielinskiandSwami在1993年的SIGMOD会议上提出在事务、关系数据库中的项集和对象中发现频繁模式、关联规则、相关性或者因果结构频繁模式:数据库中频繁出现的项集目的:发现数据中的规律超市数据中的什么产品会一起购买?—啤酒和尿布在买了一台PC之后下一步会购买?哪种DNA对这种药物敏感?我们如何自动对Web文档进行分类?频繁模式挖掘的重要性许多重要数据挖掘任务的基础关联、相关性、因果性序列模式、空间模式、时间模式、多维关
3、联分类、聚类分析更加广泛的用处购物篮分析、交叉销售、直销点击流分析、DNA序列分析等等关联规则基本模型关联规则基本模型Apriori算法关联规则基本模型IBM公司Almaden研究中心的R.Agrawal首先提出关联规则模型,并给出求解算法AIS。随后又出现了SETM和Apriori等算法。其中,Apriori是关联规则模型中的经典算法。给定一组事务产生所有的关联规则满足最小支持度和最小可信度关联规则基本模型(续)设I={i1,i2,…,im}为所有项目的集合,D为事务数据库,事务T是一个项目子集(TI)。每一个事务具有唯一的事务标识TID。设A是一个由项目构成的集合,称为项集。事务T包
4、含项集A,当且仅当AT。如果项集A中包含k个项目,则称其为k项集。项集A在事务数据库D中出现的次数占D中总事务的百分比叫做项集的支持度。如果项集的支持度超过用户给定的最小支持度阈值,就称该项集是频繁项集(或大项集)。关联规则基本模型(续)关联规则是形如XY的逻辑蕴含式,其中XI,YI,且XY=。如果事务数据库D中有s%的事务包含XY,则称关联规则XY的支持度为s%,实际上,支持度是一个概率值。若项集X的支持度记为support(X),规则的信任度为support(XY)/support(X)。这是一个条件概率P(Y
5、X)。也就是:support(XY)=P(XY)co
6、nfidence(XY)=P(Y
7、X)规则度量:支持度与可信度查找所有的规则X&YZ具有最小支持度和可信度支持度,s,一次交易中包含{X、Y、Z}的可能性可信度,c,包含{X、Y}的交易中也包含Z的条件概率设最小支持度为50%,最小可信度为50%,则可得到AC(50%,66.6%)CA(50%,100%)买尿布的客户二者都买的客户买啤酒的客户关联规则基本模型(续)关联规则就是支持度和信任度分别满足用户给定阈值的规则。发现关联规则需要经历如下两个步骤:找出所有频繁项集。由频繁项集生成满足最小信任度阈值的规则。Letmin_support=50%,min_conf=50%:AC(50
8、%,66.7%)CA(50%,100%)CustomerbuysdiaperCustomerbuysbothCustomerbuysbeerTransaction-idItemsbought10A,B,C20A,C30A,D40B,E,FForruleAC:support=support({A}{C})=50%confidence=support({A}{C})/support({A})=66.6%Min.support50%Min.confidence50%Transaction-idItemsbought10A,B,C20A,C30A,D40B,E,FFrequentpatte
9、rnSupport{A}75%{B}50%{C}50%{A,C}50%Apriori算法的步骤Apriori算法命名源于算法使用了频繁项集性质的先验(Prior)知识。Apriori算法将发现关联规则的过程分为两个步骤:通过迭代,检索出事务数据库中的所有频繁项集,即支持度不低于用户设定的阈值的项集;利用频繁项集构造出满足用户最小信任度的规则。挖掘或识别出所有频繁项集是该算法的核心,占整个计算量的大部分。频繁项集为了避免计