数据挖掘概念和技术Cha

,Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,2001-11-6,数据挖掘：概念和技术,*,数据挖掘:概念和技术,Chapter 6,张晓辉,复旦大学（国际）数据库研究中心,2001-11-6,1,数据挖掘：概念和技术,第6章：从大数据库中挖掘关联规则,关联规则挖掘,从交易数据库中挖掘一维的布尔形关联规则,从交易数据库中挖掘多层次关联规则,在交易数据库和数据仓库中挖掘多维关联规则,从关联挖掘到相关性分析,基于约束的关联挖掘,小结,2001-11-6,2,数据挖掘：概念和技术,什么是关联挖掘?,关联规则挖掘：,在交易数据、关系数据或其他信息载体中，查找存在于项目集合或对象集合之间的频繁模式、关联、相关性、或因果结构。,应用：,购物篮分析,、,交叉销售、产品目录设计,、loss-leader analysis、,聚集、分类等。,举例：,规则形式：“,Body,H,ead support,confidence”.,buys(x,“diapers”),buys(x,“beers”)0.5%,60%,major(x,“CS”)takes(x,“DB”),grade(x,“A”)1%,75%,2001-11-6,3,数据挖掘：概念和技术,关联规则：基本概念,给定:(1)交易数据库,(2),每笔交易是,：,一个项目列表(消费者一次购买活动中购买的商品),查找:,所有,描述一个项目集合与其他项目集合相关性的规则,E.g.,98%of people who purchase tires and auto accessories also get automotive services done,应用,*,护理用品,(商店应该怎样提高护理用品的销售？,),家用电器,*,(其他商品的库存有什么影响,?),在产品直销中使用,附加邮寄,Detecting,“ping-pong”ing of patients,faulty“collisions”,2001-11-6,4,数据挖掘：概念和技术,规则度量：支持度与可信度,查找所有的规则,X&Y,Z,具有最小支持度和可信度,支持度,s,一次交易中包含,X、Y、Z,的,可能性,可信度,c,包含,X、Y,的交易中也包含,Z,的,条件概率,设最小支持度为,50%,最小可信度为,50%,则可得到,A,C,(50%,66.6%),C,A,(50%,100%),买尿布的客户,二者都买的客户,买啤酒的客户,2001-11-6,5,数据挖掘：概念和技术,关联规则挖掘：路线图,布尔,vs.,定量,关联,(基于,处理数据的类型),buys(x,“SQLServer”)buys(x,“DMBook”),buys(x,“DBMiner”)0.2%,60%,age(x,“30.39”)income(x,“42.48K”),buys(x,“PC”)1%,75%,单维,vs.,多维,关联,(例子同上),单层,vs.,多层,分析,那个品种牌子的啤酒与那个牌子的尿布有关系,?,各种扩展,相关性、因果分析,关联并不一定意味着相关或因果,最大模式和闭合相集,添加约束,如,哪些“小东西”的销售促发了“大家伙”的买卖？,2001-11-6,6,数据挖掘：概念和技术,第6章：从大数据库中挖掘关联规则,关联规则挖掘,从交易数据库中挖掘一维的布尔形关联规则,从交易数据库中挖掘多层次关联规则,在交易数据库和数据仓库中挖掘多维关联规则,从关联挖掘到相关性分析,基于约束的关联挖掘,小结,2001-11-6,7,数据挖掘：概念和技术,关联规则挖掘一个例子,对于,A,C：,support=support(,A,、,C,)=50%,confidence=support(,A,、,C,)/support(,A,)=66.6%,Apriori,的基本思想:,频繁项集的任何子集也一定是频繁的,最小值尺度 50%,最小可信度 50%,2001-11-6,8,数据挖掘：概念和技术,关键步骤：挖掘频繁集,频繁集,:是指满足最小支持度的项目集合,频繁集的子集也一定是频繁的,如,如果,AB,是频繁集，则,A,B,也一定是频繁集,从1到,k（k-,频繁集）递归查找频繁集,用得到的频繁集生成关联规则,2001-11-6,9,数据挖掘：概念和技术,Apriori,算法,连接,:,用,L,k-1,自连接得到,C,k,修剪,:,一个,k-,项集，如果他的一个,k-1,项集（他的子集）不是频繁的，那他本身也不可能是频繁的。,伪代码,:,C,k,:Candidate itemset of size k,L,k,:frequent itemset of size k,L,1,=frequent items;,for,(,k,=1;,L,k,!=,;,k,+),do begin,C,k+1,=candidates generated from,L,k,;,for each,transaction,t,in database do,increment the count of all candidates in,C,k+1,that are contained in,t,L,k+1,=candidates in,C,k+1,with min_support,end,return,k,L,k,;,2001-11-6,10,数据挖掘：概念和技术,Apriori,算法 例子,数据库,D,扫描,D,C,1,L,1,L,2,C,2,C,2,扫描,D,C,3,L,3,扫描,D,2001-11-6,11,数据挖掘：概念和技术,如何生成候选集,假定,L,k-1,中的项按顺序排列,第一步:自连接,L,k-1,insert into,C,k,select,p.item,1,p.item,2,p.item,k-1,q.item,k-1,from,L,k-1,p,L,k-1,q,where,p.item,1,=q.item,1,p.item,k-2,=q.item,k-2,p.item,k-1,=10,用,Apriori,提高,执行,冰山查询的效率,先计算低维,只有当,所有的,低维都满足预制时才计算高维,2001-11-6,36,数据挖掘：概念和技术,