数据挖掘课件.ppt

1、数据挖掘,概念与技术 第六章 滕少华 编 JiaweiHan （加）著 Micheline Kamber http:/www.cs.sfu.ca,第六章 挖掘大型数据库中的关联规则,关联规则挖掘 由事务数据库挖掘单维布尔关联规则 由事务数据库挖掘多层关联规则 由事务数据库和数据仓库挖掘多维关联规则 有关联挖掘到相关分析 基于约束的关联规则 小结,什么是关联挖掘?,关联规则挖掘: 从事务数据库,关系数据库和其他信息数据库中找出项目集和对象集中的频繁模式,关连,相关联系 应用: 购物篮数据分析,交差营销,价目表设置,聚类分类等等 例子: 规则形式: “Body Head 支持度,置信度”. buy

2、s(x, “diapers”) buys(x, “beers”) 0.5%, 60% major(x, “CS”) takes(x, “DB”) grade(x, “A”) 1%, 75%,关联规则:基本概念,假设: (1) 事务数据库, (2) 每一个事务是一个项目集列表(顾客一次购买的商品集) 找出:所有的使目前的项集与另一个项集相关联的规则 例如, 98% 的人们买了轮胎和汽车附件也会需要汽车的维修服务 应用 * 维修协议(商店应该怎样做才能提升维修协议的销售) 家电*(商店应该增加其它那些产品的存储量?) 直接买卖的附加邮递,规则度量: 支持度和置信度,关联规则挖掘:一个路线图,布尔关

3、联和量化关联(根据规则中所处理的值类型) 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% 单维关连和多维关联(见以上例子) 单层和多层关联 什么牌子的啤酒和什么牌子的尿布相关联？ 各种扩充 相关性和因果关系分析 关联并不一定必须意味着相关性和因果性 最大模式和闭项集 强制的约束 E.g., 小销售(sum 1,000)?,第六章 挖掘大型数据库中的关联规则,关联规则挖掘 由事务数据库挖掘单维布

4、尔关联规则 由事务数据库挖掘多层关联规则 由事务数据库和数据仓库挖掘多维关联规则 有关联挖掘到相关分析 基于约束的关联规则 小结,挖掘关联规则的一个例子,挖掘频繁项集:关键步,找出频繁相集:具有最小支持度的项目集 一个频繁项集的子集必定是频繁项集 如:如果AB是频繁项集,那么A,B都是频繁项集. 使用从1到k的候选集交互式的产生频繁项集 由频繁项集产生关联规则,Apriori算法,连接步: 通过连接产生Ck 剪枝步: 如果一个候选k-项集的(k-1)-子集不在(k-1)-的频繁项集中,则该候选集也不可能是频繁的,从而由Ck删除 Pseudo-code: Ck: 大小为k的候选集 Lk: 大小为

5、k的频繁项集 L1= 频繁项集; for(k= 1; Lk!=; k+) do begin Ck+1= 从Lk中产生的候选集; for each transactiontD do 对于包含在t中的属于Ck+1的所有候选集的计数加一 Lk+1= Ck+1中具有最小支持度的候选集 end returnkLk;,Apriori算法例子,怎样产生候选集?,假设Lk-1中的项是按顺序列出的 第一步: 自我连接Lk-1 Insert into Ck select p.item1, p.item2, , p.itemk-1, q.itemk-1 from Lk-1p, Lk-1 q where p.item

6、1=q.item1, , p.itemk-2=q.itemk-2, p.itemk-1 q.itemk-1 第二步: 剪枝步 对于Ck中的所有项集cdo 对于c 的所有(k-1)子集s do if (s 不在Lk-1中) then 从Ck中删除c,怎样计算候选集的支持度?,为什麽计算候选集的支持度是一个问题? 候选集的总数目可能非常大 一个事务可以包含许多的候选集 方法: 候选集存储在哈希树中 包含项集和计数列表 内部结点包含了一个哈希表 子集函数: 找出包含在一个事务中的所有候选集,产生候选集的例子,L3=abc, abd, acd, ace, bcd 自我连接: L3*L3 由abc和ab

7、d产生abcd 由acd和ace产生acde 剪枝: 删除acde因为ade不在L3 C4=abcd,提高Apriori的有效性的方法,散列项集计数: 如果一个k-项集对应的哈希桶计数低于支持度阈值,则它不可能是频繁的 事务压缩: 不包含任何k-项集的事务在以后的扫描中是无用的 划分:任何项集如果在DB中是潜在频繁的,那么它至少在DB中的一个划分中是频繁的 选样: 在给定数据的一个子集上进行挖掘,低支持阈值+好的策略可以得到完整的频繁项集 动态项集计数: 如果一个项集的所有子集已被确定为频繁的,则添加大作为新的候选,Apriori算法足够的快吗?瓶颈问题的产生,Apriori算法的核心: 使用

8、频繁(k-1)-项集产生候选k-项集 使用数据库扫描和模式匹配为候选项集收集计数 Apriori算法中的瓶颈问题: 候选集的产生 大量的候选集: 104 个频繁1-项集将生成107个候选2-项集 为了发现一个大小为100的频繁模式, 如, a1, a2, , a100, 需要产生2100 1030个候选集 数据库的多遍扫描: 需要(n+1)遍扫描,n是最长项集的长度,不产生候选挖掘频繁项集,把一个大型的数据库压缩到一棵频繁模式树(FP-树) 高浓缩,但对频繁项集挖掘是完整的 避免了高花销的数据库扫描 产生了一个高效的,基于FP-树的频繁模式挖掘方法 分治策略:把挖掘任务分解成小的任务 避免候选

9、集的产生:只检测子数据库,从事务数据库中构造一个FP-树,FP-树结构的优点,完整性: 不会破坏任何交易的长模式 为频繁模式挖掘保存了完整的信息 简洁性 减少了不相关的信息非频繁项集被删掉 频繁项集按支持度递减顺序排列:越是频繁的项集越有可能被共享 不会比原数据库大(如果不算节点链和计数) 例如:对相联的4个数据库，压缩率将超过100,使用FP-树挖掘频繁模式,基本思想(分治策略）： 使用FP-树循环的产生频繁模式路径 方法 对于每一个项,先构造它的条件模式基,然后构造它的条件FP-树 在每一个新创建的条件FP-树上重复此过程 直到结果FP树为空,或它只包含一条路径(单路径将产生所有的它的子路

10、径的结合,每一条子路径都是一个频繁模式),挖掘FP-树的主要步骤,1)为FP-树中的每一个节点构造条件模式基 2)为每一个条件模式基条件FP-树 3)循环的挖掘条件FP-树，生成至今为止获得的频繁模式 如果条件FP-树只包含单条路径，简单的列举所有的模式,第一步:从FP-树到条件模式基,用于条件模式基构造的FP-树的属性,节点链属性 对任意的频繁项ai ,包含ai 的所有可能的频繁模式可以通过追随ai 的节点链获得, 这个节点链从FP-树项头的ai 头开始 前缀路径属性 计算节点ai在路径P上的频繁模式，只需聚集P中ai 的前缀子路径，其频繁计数与节点ai 的计数相同,第二步:构造一个条件FP

11、-树,通过构造条件模式基挖掘频繁模式,第三步:循环挖掘条件FP-树,单一FP-树路径的产生,频繁模式增长原理,频繁增长属性 假设是DB中的一个频繁项集, B是的条件模式基, 且是B中的一个项集. 那么是DB中的一个频繁项集当且仅当在B中是频繁的. “abcdef”是一个频繁模式, 当且仅当 “abcde”是一个频繁模式, 并且 “f”在包含“abcde”的交易集中是频繁的,为什么频繁模式增长是快速的?,我们的性能研究表明 FP-树比Apriori算法快一个数量级, 也比树-投影算法快 原因 没有候选集的产生，没有候选测试 使用简洁的数据结构 除去了重复的数据库扫描 基本操作是计数和FP-树构造

12、,关联规则的表示(表的形式),使用平面图可视化关联规则,使用规则图可视化关联规则,冰山查询,冰山查询: 在一个属性或属性集上计算一个聚集函数,以找出大于某个指定阈值的聚集值 例如: select P.custID, P.itemID, sum(P.qty) from purchase P group by P.custID, P.itemID having sum(P.qty) = 10 用Apriori算法有效的计算冰山查询: 首先计算较低维的聚集值 接着计算较高维的聚集值，当其所有较低维的聚集值在指定阈值之上,第六章 挖掘大型数据库中的关联规则,关联规则挖掘 由事务数据库挖掘单维布尔关联规

13、则 由事务数据库挖掘多层关联规则 由事务数据库和数据仓库挖掘多维关联规则 有关联挖掘到相关分析 基于约束的关联规则 小结,多层关联规则,挖掘多层关联规则,自顶向下,逐步加深的方法: 首先找出高层的强关联规则: milk bread 20%, 60%. 接着找出低层的弱关联规则: 2% milk wheat bread 6%, 50%. 挖掘多层关联规则的变量 层交叉关联规则: 2% milk Wonderwheatbread Association rules with multiple, alternative hierarchies: 2% milk Wonderbread,多层关联:统一

14、支持度和递减支持度,统一支持度:对所有层使用相同的最小支持度 优点:只有一个最小的支持度阈值.不需要考查这样的项集,它包含其祖先不具有最小支持度的项 缺点:较低层次抽象的项不大可能像较高层次抽象的项出现的那么频繁 太高会遗失低层的关联规则 太低会产生太多的高层关联规则 递减支持度:在较低层使用较小的最小支持度 有四种搜索策略: 逐层独立 层交叉k-项集过滤 层交叉单项过滤 受控的层交叉单项过滤,统一支持度,递减支持度,多层关联规则的冗余过滤,由于项之间的“祖先”关系,有些发现的规则将是冗余的 例如: milk wheat bread support = 8%, confidence = 70%

15、 2% milk wheat bread support = 2%, confidence = 72% 我们说第一个规则是第二个规则的祖先 一个规则被认为是冗余的,如果根据规则的祖先,它的支持度和置信度都接近于“期望值”,多层挖掘：逐步加深,一个自顶向下，逐步加深的方法: 首先挖掘高层频繁项: milk (15%), bread (10%) 接着挖掘低层“弱”频繁项: 2% milk (5%), wheat bread (4%) 关于多层次上不同的最小支持度阈值的设置导致了不同的算法: 如果对于所有层采取相同的最小支持度阈值 那么如果t的任意祖先是非频繁的则丢弃t 如果在较低层采用递减的最小支

16、持度 那么只检查那些支持度是频繁或不容忽视的祖先的后代,逐步精化数据挖掘质量,什么要逐步精化数据挖掘质量？ 挖掘操作可以是昂贵的或廉价的，精细的或粗糙的 用速度的降低来交换质量的提高：一步一步的精化. 超集覆盖属性: 保留所有的正面回答允许正面错误的测试但不允许错误负面的测试 两步或多步挖掘: 首先应用粗糙/廉价操作(超集覆盖) 接着在一个充分递减的候选集上应用昂贵的算法(Koperski 和 置信度 主观度量 一个规则(模式)是有趣的,如果 它是非预期的(令用户吃惊的)和/或 可控制的(用户可以用它来做一些事情),支持度和置信度的缺点,支持度和置信度的缺点(续),其它的兴趣度量: 兴趣度,第

17、六章挖掘大型数据库中的关联规则,关联规则挖掘 由事务数据库挖掘单维布尔关联规则 由事务数据库挖掘多层关联规则 由事务数据库和数据仓库挖掘多维关联规则 有关联挖掘到相关分析 基于约束的关联规则 小结,基于约束的挖掘,交互式探测挖掘数十亿字节的数据? 能成为现实吗? 好好利用约束! 什么样的约束能用在挖掘中呢? 知识类型约束: 分类,关联等 数据约束: 类SQL查询 找出98年12月份Vancouver成对出售的产品 维/层约束: 与region, price, brand, customer category相关. 规则约束 小的交易(price $200). 兴趣度约束: 强关联规则(min_

18、support 3%, min_confidence 60%).,关联挖掘中的规则约束,两种类型的规则约束: 规则形式约束: 元规则制导挖掘. P(x, y) Q(x, w) takes(x, “database systems”). 规则(内容)约束: 基于约束的查询优化(Ng, et al., SIGMOD98). sum(LHS) 20 count(LHS) 3 sum(RHS) 1000 1-变量和2-变量约束(Lakshmanan, et al. SIGMOD99): 1-变量:只局限于规则的一边(左/右),如:以上所列 2-变量:限制了两边的约束(左和右) sum(LHS) min

19、(RHS) max(RHS) 5* sum(LHS),基于约束的关联查询,数据库: (1) trans (TID,Itemset),(2)itemInfo(Item, Type, Price) 一个约束的关联查询(CAQ)的形式为(S1, S2)|C , 这里C是指S1, S2的约束集,包括频繁约束(frequency constraint) 单变量约束分类: 类约束: S A. e.g. S Item 域约束: Sv, =, , , . e.g. S.Price , . e.g. count(S1.Type) =1 ,avg(S2.Price) 100,约束关联查询优化问题,给定一个CAQ=

20、 (S1, S2)| C , 算法应该: 合理性: 它只找出满足给定限制C的频繁集 完整性: 找出了所有满足给定限制C的频繁集 朴素方法: 应用Apriori算法找出所有的频繁集接着一个一个测试他们是否满足限制约束 我们的方法: 全面分析限制的属性，试着把它尽可能的应用到频繁集的计算中,反单调和单调约束,一个约束Ca是反单调的 当且仅当对于任何不满足Ca的模式S ,它的任何超集也不能满足Ca 一个约束Cm是单调的 当且仅当对于满足Cm任何项集S,它的每一个超集也满足Cm,简洁约束,一个项集Is 的子集是一个简洁集 , 如果它能对一些选择谓词p用p(I)表示,这里是一个选择操作符 SP 2I 是

21、一个简洁幂集 , 如果存在一个固定数目的简洁集I1, , Ik I, 使得SP 可以根据严格幂集I1, , Ik使用并和减来表示 一个Cs是简洁的 ，倘若SAT Cs(I) 是一个简洁的幂集,可转变的约束,假设项集中的所有项用一个全序集R列出 一个约束C 是可转变反单调的 当且仅当满足约束C的模式S蕴含着S的每一个后缀R也满足C 一个约束C 是可转变单调的 当且仅当满足约束C的模式S蕴含着任意以C为后缀的模式R也满足C,约束类别的联系,反单调约束的性质,反单调约束: 如果一个集合S违反了约束,那么S的任何超集也违反了此约束 例子: sum(S.Price)v 是反单调的 sum(S.Price

22、) v 不是反单调的 sum(S.Price) = v 是 部分反单调 应用: 把“sum(S.price)1000”应用到迭代的频繁集计算中,反单调约束的特性,可转变约束的例子: Avg(S) V,假设R是项目集上的值下降序列 E.g. I=9, 8, 6, 4, 3, 1 Avg(S) v 是可转变单调的w.r.t. R 如果S 是S1的后缀, avg(S1) avg(S) 8, 4, 3 是9, 8, 4, 3的后缀 avg(9, 8, 4, 3)=6 avg(8, 4, 3)=5 如果S 满足avg(S) v, 则S1也满足 8, 4, 3 满足约束avg(S) 4, 9, 8, 4,

23、 3也满足此约束,约束的特征：简洁性,简洁性: 对于任意满足C的集合S1和S2, S1 S2满足C 给定A1是满足C大小为1的集合, 那么满足C的任意集合S是基于A1 的，也就是说它包含了属于A1 ,的一个自己 例子: sum(S.Price )v不是简洁的 min(S.Price ) v是简洁的 最优化: 如果C是简洁的，那么C是预计算可剪枝的。仅满足约束的条件将不会被迭代的支持度计数所影响,简洁性约束的特征,第六章挖掘大型数据库中的关联规则,关联规则挖掘 由事务数据库挖掘单维布尔关联规则 由事务数据库挖掘多层关联规则 由事务数据库和数据仓库挖掘多维关联规则 有关联挖掘到相关分析 基于约束的

24、关联规则 小结,更多有关基于约束的关联规则的挖掘,更多有关基于约束的关联规则的挖掘 布尔和量化关联 在离散和连续数据上的关联 从关联到相关和因果结果分析 关联不必定蕴含相关或因果关系 从交易内部关联到交易外部关联 E.g., 打破交易的障碍(Lu, et al. TOIS99). 从关联分析到分类和聚类分析 E.g, 聚类关联规则,第六章挖掘大型数据库中的关联规则,关联规则挖掘 由事务数据库挖掘单维布尔关联规则 由事务数据库挖掘多层关联规则 由事务数据库和数据仓库挖掘多维关联规则 有关联挖掘到相关分析 基于约束的关联规则 小结,小结,关联规则挖掘 可能是KDD数据库集中最重要的贡献 发表了大量

25、的研究论文 许多有趣的问题已经被探讨研究 一个有趣的研究方向 其他数据类型的关联分析:空间数据.多媒体数据,时间序列数据等等,References,R. Agarwal, C. Aggarwal, and V. V. V. Prasad. A tree projection algorithm for generation of frequent itemsets. In Journal of Parallel and Distributed Computing (Special Issue on High Performance Data Mining), 2000. R. Agrawal,

26、 T. Imielinski, and A. Swami. Mining association rules between sets of items in large databases. SIGMOD93, 207-216, Washington, D.C. R. Agrawaland R. Srikant. Fast algorithms for mining association rules. VLDB94 487-499, Santiago, Chile. R. Agrawaland R. Srikant. Mining sequential patterns. ICDE95,

27、3-14, Taipei, Taiwan. R. J. Bayardo. Efficiently mining long patterns from databases. SIGMOD98, 85-93, Seattle, Washington. S. Brin, R. Motwani, and C. Silverstein. Beyond market basket: Generalizing association rules to correlations. SIGMOD97, 265-276, Tucson, Arizona. S. Brin, R. Motwani, J. D. Ul

28、lman, and S. Tsur. Dynamic itemsetcounting and implication rules for market basket analysis. SIGMOD97, 255-264, Tucson, Arizona, May 1997. K. Beyer and R. Ramakrishnan. Bottom-up computation of sparse and iceberg cubes. SIGMOD99, 359-370, Philadelphia, PA, June 1999. D.W. Cheung, J. Han, V. Ng, and

29、C.Y. Wong. Maintenance of discovered association rules in large databases: An incremental updating technique. ICDE96, 106-114, New Orleans, LA. M. Fang, N. Shivakumar, H. Garcia-Molina, R. Motwani, and J. D. Ullman. Computing iceberg queries efficiently. VLDB98, 299-310, New York, NY, Aug. 1998.,Ref

30、erences (2),G. Grahne, L. Lakshmanan, and X. Wang. Efficient mining of constrained correlated sets. ICDE00, 512-521, San Diego, CA, Feb. 2000. Y. Fu and J. Han. Meta-rule-guided mining of association rules in relational databases. KDOOD95, 39-46, Singapore, Dec. 1995. T. Fukuda, Y. Morimoto, S. Mori

31、shita, and T. Tokuyama. Data mining using two-dimensional optimized association rules: Scheme, algorithms, andvisualization. SIGMOD96, 13-23, Montreal, Canada. E.-H. Han, G. Karypis, and V. Kumar. Scalable parallel data mining for association rules. SIGMOD97, 277-288, Tucson, Arizona. J. Han, G. Don

32、g, and Y. Yin. Efficient mining of partial periodic patterns in time series database. ICDE99, Sydney, Australia. J. Han and Y. Fu. Discovery of multiple-level association rules from large databases. VLDB95, 420-431, Zurich, Switzerland. J. Han, J. Pei, and Y. Yin. Mining frequent patterns without ca

33、ndidate generation. SIGMOD00, 1-12, Dallas, TX, May 2000. T. Imielinskiand H. Mannila. A database perspective on knowledge discovery. Communications of ACM, 39:58-64, 1996. M. Kamber, J. Han, and J. Y. Chiang. Metarule-guided mining of multi-dimensional association rules using data cubes. KDD97, 207

34、-210, Newport Beach, California. M. Klemettinen, H. Mannila, P. Ronkainen, H. Toivonen, and A.I. Verkamo. Finding interesting rules from large sets of discovered association rules. CIKM94, 401-408, Gaithersburg, Maryland.,References (3),F. Korn, A. Labrinidis, Y. Kotidis, and C. Faloutsos. Ratio rul

35、es: A new paradigm for fast, quantifiable data mining. VLDB98, 582-593, New York, NY. B. Lent, A. Swami, and J. Widom. Clustering association rules. ICDE97, 220-231, Birmingham, England. H. Lu, J. Han, and L. Feng. Stock movement and n-dimensional inter-transaction association rules. SIGMOD Workshop

36、 on Research Issues on Data Mining and Knowledge Discovery (DMKD98), 12:1-12:7, Seattle, Washington. H. Mannila, H. Toivonen, and A. I. Verkamo. Efficient algorithms for discovering association rules. KDD94, 181-192, Seattle, WA, July 1994. H. Mannila, H Toivonen, and A. I. Verkamo. Discovery of fre

37、quent episodes in event sequences. Data Mining and Knowledge Discovery, 1:259-289, 1997. R. Meo, G. Psaila, and S. Ceri. A new SQL-like operator for mining association rules. VLDB96, 122-133, Bombay, India. R.J. Miller and Y. Yang. Association rules over interval data. SIGMOD97, 452-461, Tucson, Ari

38、zona. R. Ng, L. V. S. Lakshmanan, J. Han, and A. Pang. Exploratory mining and pruning optimizations of constrained associations rules. SIGMOD98, 13-24, Seattle, Washington. N. Pasquier, Y. Bastide, R. Taouil, and L. Lakhal. Discovering frequent closed itemsetsfor association rules. ICDT99, 398-416,

39、Jerusalem, Israel, Jan. 1999.,References (4),J.S. Park, M.S. Chen, and P.S. Yu. An effective hash-based algorithm for mining association rules. SIGMOD95, 175-186, San Jose, CA, May 1995. J. Pei, J. Han, and R. Mao. CLOSET: An Efficient Algorithm for Mining Frequent Closed Itemsets. DMKD00, Dallas, T

40、X, 11-20, May 2000. J. Pei and J. Han. Can We Push More Constraints into Frequent Pattern Mining? KDD00. Boston, MA. Aug. 2000. G. Piatetsky-Shapiro. Discovery, analysis, and presentation of strong rules. In G. Piatetsky-Shapiro and W. J. Frawley, editors, Knowledge Discovery in Databases, 229-238.

41、AAAI/MIT Press, 1991. B. Ozden, S. Ramaswamy, and A. Silberschatz. Cyclic association rules. ICDE98, 412-421, Orlando, FL. J.S. Park, M.S. Chen, and P.S. Yu. An effective hash-based algorithm for mining association rules. SIGMOD95, 175-186, San Jose, CA. S. Ramaswamy, S. Mahajan, and A. Silberschatz

42、. On the discovery of interesting patterns in association rules. VLDB98, 368-379, New York, NY. S. Sarawagi, S. Thomas, and R. Agrawal. Integrating association rule mining with relational database systems: Alternatives and implications. SIGMOD98, 343-354, Seattle, WA. A. Savasere, E. Omiecinski, and S. Navathe. An efficient algorithm for mining association rules in large databases. VLDB95, 432-443, Zurich, Switzerland. A. Savasere, E. Omiecinski, and S. Navathe. Mining for strong negative associations in a large database of customer transactions. ICDE