数据挖掘6章关联1ppt课件

1、第第6章：发掘大型数据库中的关章：发掘大型数据库中的关联规那么联规那么n6.1 关联规那么发掘关联规那么发掘n6.2由事务数据库发掘单维布尔关联规那么由事务数据库发掘单维布尔关联规那么n6.3由事务数据库发掘多层关联规那么由事务数据库发掘多层关联规那么n6.4由关系数据库和数据仓库发掘多维关联规那由关系数据库和数据仓库发掘多维关联规那么么n6.5由关联发掘到相关性分析由关联发掘到相关性分析n6.6基于约束的关联发掘基于约束的关联发掘n6.7小结小结什么是关联发掘什么是关联发掘?n关联规那么发掘：关联规那么发掘：n在买卖数据、关系数据或其他信息载体中，查找存在于工在买卖数据、关系数据或其他信息载

2、体中，查找存在于工程集合或对象集合之间的频繁方式、关联、相关性、或因程集合或对象集合之间的频繁方式、关联、相关性、或因果构造。果构造。n运用：运用：n购物篮分析、交叉销售、产品目录设计、购物篮分析、交叉销售、产品目录设计、 loss-leader analysis、聚集、分类等。、聚集、分类等。n举例：举例： n规那么方式：规那么方式： “Body Head support, confidence.nbuys(x, “diapers) buys(x, “beers) 0.5%, 60%nmajor(x, “CS) takes(x, “DB) grade(x, “A) 1%, 75%关联规那么：

3、根本概念关联规那么：根本概念n给定给定: (1)买卖数据库买卖数据库 (2)每笔买卖是：一个工程列表每笔买卖是：一个工程列表 (消费消费者一次购买活动中购买的商品者一次购买活动中购买的商品)n查找查找: 一切描画一个工程集合与其他工程集合相关性的规那一切描画一个工程集合与其他工程集合相关性的规那么么nE.g., 98% of people who purchase tires and auto accessories also get automotive services donen运用运用n* 护理用品护理用品 (商店应该怎样提高护理用品的销售？商店应该怎样提高护理用品的销售？)n家用电器

4、家用电器 * (其他商品的库存有什么影响其他商品的库存有什么影响?)n在产品直销中运用附加邮寄在产品直销中运用附加邮寄规那么度量：支持度与可信度规那么度量：支持度与可信度n查找一切的规那么查找一切的规那么 X & Y Z 具有最小支持度和可信度具有最小支持度和可信度n支持度支持度, s, 一次买卖中包含一次买卖中包含X 、 Y 、 Z的能够性的能够性n置信度置信度, c, 包含包含X 、 Y的买的买卖中也包含卖中也包含Z的条件概率的条件概率交易ID购买的商品2000A,B,C1000A,C4000A,D5000B,E,F设最小支持度为设最小支持度为50%, 最小可信最小可信度为度为 5

5、0%, 那么可得到那么可得到A C (50%, 66.6%)C A (50%, 100%)买尿布的客买尿布的客户户二者都买二者都买的客户的客户买啤酒的客户买啤酒的客户关联规那么发掘：道路图关联规那么发掘：道路图n布尔布尔 vs. 定量定量 关联关联 (基于规那么中所处置数据的值类型基于规那么中所处置数据的值类型)nbuys(x, “SQLServer) buys(x, “DMBook) buys(x, “DBMiner) 0.2%, 60%nage(x, “30.39) income(x, “42.48K) buys(x, “PC) 1%, 75%n单维单维 vs. 多维多维 关联关联 (基于

6、规那么中涉及的数据维基于规那么中涉及的数据维)(例子同上例子同上)n单层单层 vs. 多层多层 分析分析(基于规那么集所涉及的笼统层基于规那么集所涉及的笼统层)n那个种类牌子的啤酒与那个牌子的尿布有关系那个种类牌子的啤酒与那个牌子的尿布有关系?n各种扩展各种扩展n相关性、因果分析相关性、因果分析n关联并不一定意味着相关或因果关联并不一定意味着相关或因果n最大方式和闭合项集最大方式和闭合项集第第6章：从大数据库中发掘关联章：从大数据库中发掘关联规那么规那么n6.1 关联规那么发掘关联规那么发掘n6.2由事务数据库发掘单维布尔关联规那么由事务数据库发掘单维布尔关联规那么n6.3由事务数据库发掘多层

7、关联规那么由事务数据库发掘多层关联规那么n6.4由关系数据库和数据仓库发掘多维关联规那由关系数据库和数据仓库发掘多维关联规那么么n6.5由关联发掘到相关性分析由关联发掘到相关性分析n6.6基于约束的关联发掘基于约束的关联发掘n6.7小结小结关联规那么发掘关联规那么发掘一个例子一个例子对于对于 A C：support = support(A 、C) = 50%confidence = support(A 、C)/support(A) = 66.6%Apriori的根本思想的根本思想:频繁项集的任何子集也一定是频繁的频繁项集的任何子集也一定是频繁的交易ID购买商品2000A,B,C1000A,C4

8、000A,D5000B,E,F频繁项集支持度A75%B50%C50%A,C50%最小值尺度 50%最小可信度 50%关键步骤：发掘频繁集关键步骤：发掘频繁集n频繁集频繁集:是指满足最小支持度的工程集合是指满足最小支持度的工程集合n频繁集的子集也一定是频繁的频繁集的子集也一定是频繁的n如如, 假设假设AB 是频繁集，那么是频繁集，那么 A B 也一也一定是频繁集定是频繁集n从从1到到kk-频繁集递归查找频繁集频繁集递归查找频繁集n用得到的频繁集生成关联规那么用得到的频繁集生成关联规那么Apriori算法算法n衔接衔接: 用用 Lk-1自衔接得到候选自衔接得到候选k-项集项集Ckn修剪修剪: 一个

9、一个k-项集，假设他的一个项集，假设他的一个k-1项集他的子集项集他的子集 不是频繁的，那他本身也不能够是频繁的。不是频繁的，那他本身也不能够是频繁的。n伪代码伪代码:nCk: Candidate itemset of size knLk : frequent itemset of size knL1 = frequent items;nfor (k = 2; Lk-1 !=; k+) do beginn Ck = candidates generated from Lk-1;n for each transaction t in database don increment the coun

10、t of all candidates in Ck that are contained in tn Lk = candidates in Ck with min_supportn endnreturn k Lk;Apriori算法算法 例子例子TID Items100 1 3 4200 2 3 5300 1 2 3 5400 2 5数据库 Ditemset sup.1223334153itemset sup.12233353扫描 DC1L1itemset1 21 31 52 32 53 5itemset sup1 211 321 512 322 533 52itemset sup1 322

11、322 533 52L2C2C2扫描 DC3L3itemset2 3 5扫描 Ditemset sup2 3 52如何生成候选集如何生成候选集n假定假定 Lk-1 中的项按顺序陈列中的项按顺序陈列n第一步第一步: 自衔接自衔接 Lk-1 ninsert into Cknselect p.item1, p.item2, , p.itemk-1, q.itemk-1nfrom Lk-1 p, Lk-1 qnwhere p.item1=q.item1, , p.itemk-2=q.itemk-2, p.itemk-1 q.itemk-1n第二步第二步: 修剪修剪nFor all itemsets c

12、 in Ck donFor all (k-1)-subsets s of c donif (s is not in Lk-1) then delete c from Ckn计算支持度为什么会成为一个问题？计算支持度为什么会成为一个问题？n候选集的个数非常宏大候选集的个数非常宏大n 一笔买卖能够包含多个候选集一笔买卖能够包含多个候选集生成候选集的例子生成候选集的例子nL3=abc, abd, acd, ace, bcdn自衔接自衔接 : L3*L3nabc 和和 abd 得到得到 abcd nacd 和和 ace 得到得到 acden修剪修剪:nade 不在不在 L3中，删除中，删除 acden

13、C4=abcd提高提高Apriori效率的方法效率的方法1.基于基于Hash的项集计数的项集计数: 假设假设 k-项集在项集在hash-tree的途径上的一个的途径上的一个计数值低于阈值，那他本身也不能够是频繁的。计数值低于阈值，那他本身也不能够是频繁的。(157页图页图6-6)2.减少买卖记录减少买卖记录: 不包含任何频繁不包含任何频繁k-项集的买卖也不能够包含任何项集的买卖也不能够包含任何大于大于k的频繁集，下一步计算时删除这些记录。的频繁集，下一步计算时删除这些记录。3.划分划分: 一个项集要想在整个数据库中是频繁的，那么他至少在数一个项集要想在整个数据库中是频繁的，那么他至少在数据库的

14、一个分割上是频繁的。据库的一个分割上是频繁的。 两次扫描数据。两次扫描数据。(157页图页图5-6)4.抽样抽样: 运用小的支持度运用小的支持度+完好性验证方法。在小的抽样集上找到完好性验证方法。在小的抽样集上找到部分频繁项集，然后在全部数据集找频繁项集。部分频繁项集，然后在全部数据集找频繁项集。5.动态项集计数动态项集计数: 在添加一个新的候选集之前，先估计一下是不是在添加一个新的候选集之前，先估计一下是不是他的一切子集都是频繁的。他的一切子集都是频繁的。Apriori 够快了吗够快了吗? 性能瓶颈性能瓶颈nApriori算法的中心算法的中心:n用频繁的用频繁的(k 1)-项集生成候选的频繁

15、项集生成候选的频繁 k-项集项集n用数据库扫描和方式匹配计算候选集的支持度用数据库扫描和方式匹配计算候选集的支持度nApriori 的瓶颈的瓶颈: 候选集生成候选集生成n宏大的候选集宏大的候选集:n104 个频繁个频繁1-项集要生成项集要生成 107 个候选个候选 2-项集项集n要找尺寸为要找尺寸为100的频繁方式，如的频繁方式，如 a1, a2, , a100, 他必需先产生他必需先产生2100 1030 个候选集个候选集n多次扫描数据库：多次扫描数据库： n假设最长的方式是假设最长的方式是n的话，那么需求的话，那么需求 (n +1 ) 次数次数据库扫描据库扫描发掘频繁集发掘频繁集 不用生成

16、候选集不用生成候选集n频繁方式增长频繁方式增长 (FP-增长增长)用用Frequent-Pattern tree (FP-tree) 构造紧缩数据库构造紧缩数据库, n高度浓缩，同时对频繁集的发掘又完备的高度浓缩，同时对频繁集的发掘又完备的n防止代价较高的数据库扫描防止代价较高的数据库扫描n 开发一种高效的基于开发一种高效的基于FP-tree的频繁集发掘算法的频繁集发掘算法n采用分而治之的方法学：分解数据发掘义务为小采用分而治之的方法学：分解数据发掘义务为小义务义务n防止生成关联规那么防止生成关联规那么: 分别发掘条件数据库分别发掘条件数据库用用 FP-tree发掘频繁集发掘频繁集n根本思想根

17、本思想 (分而治之分而治之)n用用FP-tree地归增长频繁集地归增长频繁集n方法方法 n对每个项，生成它的对每个项，生成它的 条件方式库条件方式库, 然后是它的然后是它的 条条件件 FP-treen对每个新生成的条件对每个新生成的条件FP-tree，反复这个步骤，反复这个步骤n直到结果直到结果FP-tree为空为空, 或只含维一的一个途径或只含维一的一个途径 (此途径的每个子途径对应的相集都是频繁集此途径的每个子途径对应的相集都是频繁集)发掘发掘 FP-tree的主要步骤的主要步骤n为为FP-tree中的每个节点生成条件方式库中的每个节点生成条件方式库n用条件方式库构造对应的条件用条件方式库

18、构造对应的条件FP-treen递归构造条件递归构造条件 FP-trees 同时增长其包含的频繁同时增长其包含的频繁集集n假设条件假设条件FP-tree直包含一个途径，那么直接生直包含一个途径，那么直接生成所包含的频繁集。成所包含的频繁集。步骤步骤1: 1: 建立建立 FP-tree FP-tree 159159页图页图6-86-8n从从FP-tree的头表开场的头表开场n按照每个频繁项的衔接遍历按照每个频繁项的衔接遍历 FP-treen列出可以到达此项的一切前缀途径，得到条件方式库列出可以到达此项的一切前缀途径，得到条件方式库步骤步骤2:2:建立条件建立条件FP-treeFP-tree进展发掘

19、进展发掘159159页图页图6-96-9n对每个方式库对每个方式库n计算库中每个项的支持度计算库中每个项的支持度n用方式库中的频繁项建立用方式库中的频繁项建立FP-tree为什么为什么 频繁集增长频繁集增长 速度快？速度快？n我们的性能研讨显示我们的性能研讨显示nFP-growth 比比Apriori快一个数量级快一个数量级, 同样也比同样也比 tree-projection 快。快。n缘由缘由n不生成候选集，不用候选测试。不生成候选集，不用候选测试。n运用紧缩的数据构造运用紧缩的数据构造n防止反复数据库扫描防止反复数据库扫描n根本操作是计数和建立根本操作是计数和建立 FP-tree 树树FP

20、-growth vs. Apriori: 相对于支持度相对于支持度的扩展性的扩展性010203040506070809010000.511.522.53Support threshold(%)Run time(sec.)D1 FP-grow th runtimeD1 Apriori runtimeData set T25I20D10KFP-growth vs. Tree-Projection:相对于相对于支持度的扩展性支持度的扩展性02040608010012014000.511.52Support threshold (%)Runtime (sec.)D2 FP-growthD2 TreeP

21、rojectionData set T25I20D100K关联规那么结果显示关联规那么结果显示 (Table Form )关联规那么可视化关联规那么可视化Using Plane Graph关联规那么可视化关联规那么可视化Using Rule Graph第6章：从大数据库中发掘关联规那么n6.1 关联规那么发掘关联规那么发掘n6.2由事务数据库发掘单维布尔关联规那么由事务数据库发掘单维布尔关联规那么n6.3由事务数据库发掘多层关联规那么由事务数据库发掘多层关联规那么n6.4由关系数据库和数据仓库发掘多维关联规那由关系数据库和数据仓库发掘多维关联规那么么n6.5由关联发掘到相关性分析由关联发掘到相

22、关性分析n6.6基于约束的关联发掘基于约束的关联发掘n6.7小结小结多层关联规那么多层关联规那么n项通常具有层次项通常具有层次n底层的项通常支持度也低底层的项通常支持度也低n某些特定层的规那么能够某些特定层的规那么能够更有意义更有意义n买卖数据库可以按照维或买卖数据库可以按照维或层编码层编码n可以进展共享的多维发掘可以进展共享的多维发掘食品面包牛奶脱脂奶光明一致酸奶白黄TID ItemsT1111, 121, 211, 221T2111, 211, 222, 323T3112, 122, 221, 411T4111, 121T5111, 122, 211, 221, 413发掘多层关联规那么发

23、掘多层关联规那么n自上而下，深度优先的方法：自上而下，深度优先的方法：n先找高层的先找高层的“强规那么：强规那么：n牛奶牛奶 面包面包 20%, 60%. 20%, 60%.n再找他们底层的再找他们底层的“弱规那么：弱规那么：n酸奶酸奶 黄面包黄面包 6%, 50%. 6%, 50%.n多层关联规那么的变种多层关联规那么的变种n1 1 支持度不变支持度不变: : 在各层之间运用一致的支持度在各层之间运用一致的支持度n+ + 一个最小支持度阈值一个最小支持度阈值. . 假设一个项集的父项集不具有最小支假设一个项集的父项集不具有最小支持度，那他本身也不能够满足最小支持度。持度，那他本身也不能够满足

24、最小支持度。n 底层项不会成为频繁集，假设支持度底层项不会成为频繁集，假设支持度n太高太高 丧失底层关联规那么丧失底层关联规那么n太低太低 生成太多的高层关联规那么生成太多的高层关联规那么n2 2 支持度递减支持度递减: : 随着层次的降低支持度递减随着层次的降低支持度递减多层关联规那么多层关联规那么: 支持度不变支持度不变 vs. 支支持度递减持度递减3层次交叉单项过滤：层次交叉单项过滤： 4层次交叉层次交叉K-项过滤：项过滤：4种搜索战略：种搜索战略：层与层独立层与层独立用用k-项集跨层过滤项集跨层过滤用项跨层过滤用项跨层过滤用项进展可控跨层过滤用项进展可控跨层过滤支持度不变支持度不变支持

25、度不变多层发掘支持度不变多层发掘牛奶牛奶support = 10%酸奶酸奶 support = 6%脱脂奶脱脂奶support = 4%层层 1min_sup = 5%层层 2min_sup = 5%支持度递减支持度递减支持度递减多层发掘支持度递减多层发掘酸奶酸奶 support = 6%脱脂奶脱脂奶 support = 4%层层 1min_sup = 5%层层 2min_sup = 3%牛奶牛奶support = 10%多层关联：冗余过滤n由于由于“祖先关系的缘由，有些规那么能够是多余的。祖先关系的缘由，有些规那么能够是多余的。n例子例子n奶制品奶制品 白面包白面包 support = 8%

26、, confidence = 70%n酸奶酸奶 白面包白面包 support = 2%, confidence = 72%n酸奶占奶制品酸奶占奶制品25%n我们称第一个规那么是第二个规那么的祖先我们称第一个规那么是第二个规那么的祖先n参考规那么的祖先，假设他的支持度与我们参考规那么的祖先，假设他的支持度与我们“预期的支持度预期的支持度近似的话，我们就说这条规那么是冗余的。近似的话，我们就说这条规那么是冗余的。数据发掘查询的逐渐精化数据发掘查询的逐渐精化n为什么要逐渐精化为什么要逐渐精化n发掘操作的代价能够高或低，结果能够过细致或粗糙发掘操作的代价能够高或低，结果能够过细致或粗糙n在速度和质量之

27、间折衷：逐渐精化在速度和质量之间折衷：逐渐精化n超集覆盖特征：超集覆盖特征：n预存储一切正面答案预存储一切正面答案允许进一步正确性验证，而不用验证允许进一步正确性验证，而不用验证曾经错误的曾经错误的n2或多步发掘：或多步发掘：n先执行粗糙的、容易的操作先执行粗糙的、容易的操作 (超集覆盖超集覆盖)n然后在减少后的候选集上进展计算量大的算法然后在减少后的候选集上进展计算量大的算法 (Koperski & Han, SSD95).第6章：从大数据库中发掘关联规那么n6.1 关联规那么发掘关联规那么发掘n6.2由事务数据库发掘单维布尔关联规那么由事务数据库发掘单维布尔关联规那么n6.3由事务

28、数据库发掘多层关联规那么由事务数据库发掘多层关联规那么n6.4由关系数据库和数据仓库发掘多维关联规那由关系数据库和数据仓库发掘多维关联规那么么n6.5由关联发掘到相关性分析由关联发掘到相关性分析n6.6基于约束的关联发掘基于约束的关联发掘n6.7小结小结多维关联规那么：多维关联规那么： 概念概念n单维规那么：单维规那么：nbuys(X, “milk) buys(X, “bread)n多维规那么：多维规那么： 2个以上维个以上维/谓词谓词n维间关联规那么维间关联规那么 (维词不反复维词不反复)nage(X,19-25) occupation(X,“student) buys(X,“coke)n混

29、合维关联规那么混合维关联规那么 (维词反复维词反复)nage(X,19-25) buys(X, “popcorn) buys(X, “coke)n类别属性类别属性n有限个值有限个值, 值之间无顺序关系值之间无顺序关系n数量属性数量属性n数字的，值之间隐含了顺序关系数字的，值之间隐含了顺序关系发掘多维关联的技术发掘多维关联的技术n搜索频繁搜索频繁k-维词集合：维词集合：n如如: age, occupation, buys 是一个是一个3-维词集合。维词集合。n按照对按照对 age 处置方式的不同，分为：处置方式的不同，分为：n1. 用静态方法把数值属性离散化用静态方法把数值属性离散化n数值属性可

30、用预定义的概念层次加以离散化。数值属性可用预定义的概念层次加以离散化。n2. 带数量的关联规那么带数量的关联规那么n根据数据的分布，动态的把数值属性离散化到不同的根据数据的分布，动态的把数值属性离散化到不同的“箱箱。n3. 基于间隔的关联规那么基于间隔的关联规那么n用数据点之间的间隔动态的离散化用数据点之间的间隔动态的离散化数值属性的静态离散化数值属性的静态离散化n在发掘之前用概念层次先离散化在发掘之前用概念层次先离散化n数值被交换为区间范围数值被交换为区间范围n关系数据库中，要找到一切频繁关系数据库中，要找到一切频繁k-维词需求维词需求k或或k+1次表扫次表扫描。描。n适宜运用数据立方体适宜

31、运用数据立方体nN维立方体的每个单元维立方体的每个单元 对应一个维词集合对应一个维词集合n运用数据立方体速度更快运用数据立方体速度更快(income)(age)()(buys)(age, income)(age,buys) (income,buys)(age,income,buys)带数量的关联规那么带数量的关联规那么age(X,30-34) income(X,24K - 48K) buys(X,high resolution TV)n动态动态 离散化数值属性离散化数值属性n使满足某种发掘规范，如最大化发掘规那么的置信度紧凑使满足某种发掘规范，如最大化发掘规那么的置信度紧凑性性.n2-维数量关

32、联规那么：维数量关联规那么： Aquan1 Aquan2 Acatn用用2-维表格把维表格把“临近的临近的关联规那么组合起来关联规那么组合起来n例子例子 ARCS (关联规那么聚集系统关联规那么聚集系统) ARCS 流程流程1. 分箱分箱2. 查找频繁维词查找频繁维词 集合集合3. 关联规那么聚类关联规那么聚类4. 优化优化ARCS的局限性的局限性n数值属性只能出如今规那么的左侧数值属性只能出如今规那么的左侧n左侧只能有两个属性左侧只能有两个属性 (2维维)nARCS 的改良的改良n不用基于栅格的方法不用基于栅格的方法n等深分箱等深分箱n基于部分完好性基于部分完好性 测度的聚集测度的聚集n“M

33、ining Quantitative Association Rules in Large Relational Tables by R. Srikant and R. Agrawal.发掘基于间隔的关联规那么发掘基于间隔的关联规那么n分箱的方法没有表达数据间隔的语义分箱的方法没有表达数据间隔的语义n基于间隔的分割是更有基于间隔的分割是更有“意义的离散化方法，思索：意义的离散化方法，思索：n区间内密度或点的个数区间内密度或点的个数n区间内点的区间内点的“严密程度严密程度价格（$）等宽( 宽度$10)等深(深度 2)基于距离70,107,207,72011,2022,5020,222221,30

34、51,5350,535031,405141,505351,60第第6章：从大数据库中发掘关联章：从大数据库中发掘关联规那么规那么n6.1 关联规那么发掘关联规那么发掘n6.2由事务数据库发掘单维布尔关联规那么由事务数据库发掘单维布尔关联规那么n6.3由事务数据库发掘多层关联规那么由事务数据库发掘多层关联规那么n6.4由关系数据库和数据仓库发掘多维关联规那由关系数据库和数据仓库发掘多维关联规那么么n6.5由关联发掘到相关性分析由关联发掘到相关性分析n6.6基于约束的关联发掘基于约束的关联发掘n6.7小结小结n强关联规那么不一定是有趣的强关联规那么不一定是有趣的168页例页例5.8n由关联分析到相

35、关分析由关联分析到相关分析n 项集项集A与项集与项集B独立独立 n P(AB)=P(A)P(B)n 项集项集A、B的相关性的相关性n corrAB=P(AB)/P(A)P(B)n 第第6章：从大数据库中发掘关联章：从大数据库中发掘关联规那么规那么n6.1 关联规那么发掘关联规那么发掘n6.2由事务数据库发掘单维布尔关联规那么由事务数据库发掘单维布尔关联规那么n6.3由事务数据库发掘多层关联规那么由事务数据库发掘多层关联规那么n6.4由关系数据库和数据仓库发掘多维关联规那由关系数据库和数据仓库发掘多维关联规那么么n6.5由关联发掘到相关性分析由关联发掘到相关性分析n6.6基于约束的关联发掘基于约

36、束的关联发掘n6.7小结小结6.6.1 基于约束的发掘基于约束的发掘n运用约束的必要性运用约束的必要性n在数据发掘中常运用的几种约束：在数据发掘中常运用的几种约束：n知识类型约束：指定要发掘的知识类型知识类型约束：指定要发掘的知识类型n 如关联规那么如关联规那么n数据约束：数据约束： 指定与义务相关的数据集指定与义务相关的数据集 nFind product pairs sold together in Vancouver in Dec.98.n维维/层次约束层次约束:指定所用的维或概念构造中的层指定所用的维或概念构造中的层nin relevance to region, price, brand, customer category.n规那么约束：指定要发掘的规那么方式规那么