第5章数据挖掘

1、2021-7-252021-7-25数据挖掘数据挖掘1第五章第五章 挖掘频繁模式、关联和相关挖掘频繁模式、关联和相关l基本概念基本概念l频繁项集挖掘方法和模式评估方法频繁项集挖掘方法和模式评估方法l多层和多维空间中的模式挖掘多层和多维空间中的模式挖掘l基于约束的频繁模式挖掘基于约束的频繁模式挖掘l模式探索与应用模式探索与应用l小结小结2021-7-252021-7-25数据挖掘数据挖掘2基本概念和方法基本概念和方法l关联规则挖掘关联规则挖掘l在交易数据、关系数据或其他信息载体中，查找存在于项目集合或对象集合之间的频繁模式、关联、相关性、或因果结构。l频繁模式频繁模式l频繁地出现在数据集中的模式

2、（如项集、子序列或子结构）2021-7-252021-7-25数据挖掘数据挖掘3基本概念基本概念l应用应用l购物篮分析、交叉销售、产品目录设计、赔本销售分析（loss-leader analysis）、聚集、分类等。l举例：购物篮分析举例：购物篮分析l规则形式： “Body Head support, confidence”.lbuys(x, “diapers”) buys(x, “beers”) 0.5%, 60%lmajor(x, “CS”) takes(x, “DB”) grade(x, “A”) 1%, 75%变量，代表一变量，代表一个交易的集合个交易的集合2021-7-252021-

3、7-25数据挖掘数据挖掘42021-7-252021-7-25数据挖掘数据挖掘5l给定给定: (1)交易数据库交易数据库 (2)每笔交易是：一个项每笔交易是：一个项目列表目列表 (消费者一次购买活动中购买的商品消费者一次购买活动中购买的商品)l查找查找: 所有所有描述一个项目集合与其他项目集描述一个项目集合与其他项目集合相关性的规则合相关性的规则lE.g., 98% of people who purchase tires and auto accessories also get automotive services donel应用应用l* 护理用品护理用品 (商店应该怎样提高护理用品的销

4、商店应该怎样提高护理用品的销售？售？)l家用电器家用电器 * (其他商品的库存有什么影响其他商品的库存有什么影响?)l在产品直销中使用附加邮寄在产品直销中使用附加邮寄2021-7-252021-7-25数据挖掘数据挖掘6规则度量：支持度与可信度规则度量：支持度与可信度l查找所有的规则查找所有的规则 X & Y Z 具有最具有最小支持度和可信度小支持度和可信度l支持度支持度, s, 一次交易中包含一次交易中包含X 、 Y 、 Z的的可能性可能性l置信度置信度, c, 包含包含X 、 Y的交易中的交易中也包含也包含Z的的条件概率条件概率交易ID购买的商品2000A,B,C1000A,C4000A,

5、D5000B,E,F设最小支持度为设最小支持度为50%, 最小可信最小可信度为度为 50%, 则可得到则可得到nA C (50%, 66.6%)nC A (50%, 100%)买尿布的客买尿布的客户户二者都买二者都买的客户的客户买啤酒的客户买啤酒的客户2021-7-252021-7-25数据挖掘数据挖掘7频繁项集、闭项集和关联规则频繁项集、闭项集和关联规则l假定某超市销售的商品包括：假定某超市销售的商品包括：bread、beer、cake、cream、milk和和tea 交易号交易号TID顾顾 客客 购购 买买 商商 品品ItemsT1bread cream milk teaT2bread c

6、ream milkT3cake milkT4milk teaT5bread cake milkT6bread teaT7beer milk teaT8bread teaT9bread cream milk teaT10bread milk tea2021-7-252021-7-25数据挖掘数据挖掘8l项目与项集项目与项集l设设I=i1,i2,im是是m个不同项目的集合，个不同项目的集合，每个每个ik(k=1，2，m)称为一个项称为一个项目目(Item)。l项目的集合项目的集合I称为项目集合称为项目集合(Itemset)，简称为项集。其元素个数称为项集的简称为项集。其元素个数称为项集的长度，长度

7、为长度，长度为k的项集称为的项集称为k-项集项集(k-Itemset)。2021-7-252021-7-25数据挖掘数据挖掘9l交易交易l每笔交易每笔交易T(Transaction)是项集是项集I上的一个上的一个子集，即子集，即T I，但通常，但通常T I。l对应每一个交易有一个唯一的标识对应每一个交易有一个唯一的标识交交易号，记作易号，记作TIDl交易的全体构成了交易数据库交易的全体构成了交易数据库D，或称交易，或称交易记录集记录集D，简称交易集，简称交易集D。l交易集交易集D中包含交易的个数记为中包含交易的个数记为|D|。 2021-7-252021-7-25数据挖掘数据挖掘10l定义定义

8、4.3 项集的支持度项集的支持度l对于项集对于项集X，X I，设定，设定count(X T)为为交易集交易集D中包含中包含X的交易的数量的交易的数量l项集项集X的支持度的支持度support(X)就是就是项集项集X出现的概率出现的概率，从而从而描述了描述了X的重要性。的重要性。 |D|T)count(Xsupport(X)2021-7-252021-7-25数据挖掘数据挖掘11l项集的最小支持度与频繁集项集的最小支持度与频繁集l发现关联规则要求项集必须满足的最小发现关联规则要求项集必须满足的最小支 持 阈 值 ， 称 为 项 集 的 最 小 支 持 度支 持 阈 值 ， 称 为 项 集 的 最

9、 小 支 持 度(Minimum Support)，记为，记为supmin。从。从统计意义上讲，它表示用户关心的关联统计意义上讲，它表示用户关心的关联规则必须满足的最低重要性。只有满足规则必须满足的最低重要性。只有满足最小支持度的项集才能产生关联规则。最小支持度的项集才能产生关联规则。l支持度大于或等于支持度大于或等于supmin的项集称为频的项集称为频繁项集，简称频繁集，反之则称为非频繁项集，简称频繁集，反之则称为非频繁集。通常繁集。通常k-项集如果满足项集如果满足supmin，称，称为为k-频繁集，记作频繁集，记作Lk。2021-7-252021-7-25数据挖掘数据挖掘12l关联规则关联

10、规则l关联规则关联规则(Association Rule)可以表示可以表示为一个蕴含式：为一个蕴含式：l R：XY 2021-7-252021-7-25数据挖掘数据挖掘13l关联规则的支持度关联规则的支持度l对于关联规则对于关联规则R：XY，其中，其中X I,Y I，并 且并 且 X Y = ， 规 则， 规 则 R 的 支 持 度的 支 持 度(Support)是交易集中同时包含是交易集中同时包含X和和Y的交易数与所有交易数之比。的交易数与所有交易数之比。 |D|Y)count(XY)support(X2021-7-252021-7-25数据挖掘数据挖掘14l关联规则的可信度关联规则的可信度

11、l对于关联规则对于关联规则R：XY，其中，其中X I,Y I，并 且并 且 X Y = ， 规 则， 规 则 R 的 可 信 度的 可 信 度(Confidence)是指包含是指包含X和和Y的交易数的交易数与包含与包含X的交易数之比的交易数之比 support(X)Y)support(XY)(X confidence2021-7-252021-7-25数据挖掘数据挖掘15l关联规则的最小支持度和最小可信度关联规则的最小支持度和最小可信度l关联规则的最小支持度也就是衡量频关联规则的最小支持度也就是衡量频繁 集 的 最 小 支 持 度繁 集 的 最 小 支 持 度 ( M i n i m u m

12、Support)，记为，记为supmin，它用于衡量，它用于衡量规则需要满足的最低重要性。规则的规则需要满足的最低重要性。规则的最小可信度最小可信度(Minimum Confidence)记记为为confmin，它表示关联规则需要满，它表示关联规则需要满足的最低可靠性。足的最低可靠性。2021-7-252021-7-25数据挖掘数据挖掘16l强关联规则强关联规则l如果规则如果规则XY满足：满足：s u p p o r t ( X Y ) s u p m i n 且且confidence(XY) confmin，称关联，称关联规则规则XY为强关联规则，否则称关联为强关联规则，否则称关联规则规则X

13、Y为弱关联规则。在挖掘关联为弱关联规则。在挖掘关联规 则 时 ， 产 生 的 关 联 规 则 要 经 过规 则 时 ， 产 生 的 关 联 规 则 要 经 过supmin和和confmin的衡量，筛选出来的衡量，筛选出来的强关联规则才能用于指导商家的决策。的强关联规则才能用于指导商家的决策。2021-7-252021-7-25数据挖掘数据挖掘17l关联规则挖掘步骤关联规则挖掘步骤l找出所有频繁项集找出所有频繁项集：这些项集的每一个出现：这些项集的每一个出现的频繁性至少与预定义的最小支持计数一样的频繁性至少与预定义的最小支持计数一样l由频繁项集产生强关联规则由频繁项集产生强关联规则：这些规则必须

14、：这些规则必须满足最小支持度和最小置信度满足最小支持度和最小置信度l闭频繁项集闭频繁项集：如果不存在真超项集：如果不存在真超项集Y使得使得Y与与X在在S中有相同的支持度计数，则称中有相同的支持度计数，则称项集项集X在数据集在数据集S中是闭的，如果中是闭的，如果X在在S中中是闭的和频繁的，就称是闭的和频繁的，就称X是是S中的中的闭频繁闭频繁项集项集l极大频繁项集：极大频繁项集：如果如果X是频繁的，并且不存在是频繁的，并且不存在超项集超项集Y使得使得X Y并且并且Y在在S中是频繁的。中是频繁的。2021-7-252021-7-25数据挖掘数据挖掘18Apriori算法：使用候选产生发现频繁项集算法

15、：使用候选产生发现频繁项集对于 A C：support = support(A 、C) = 50%confidence = support(A 、C)/support(A) = 66.6%Apriori的基本思想:频繁项集的任何非空子集也一定是频繁的频繁项集的任何非空子集也一定是频繁的交易ID购买商品2000A,B,C1000A,C4000A,D5000B,E,F频繁项集支持度A75%B50%C50%A,C50%最小支持度 50%最小可信度 50%2021-7-252021-7-25数据挖掘数据挖掘19关键步骤：挖掘频繁集关键步骤：挖掘频繁集l频繁集频繁集:是指满足最小支持度的项目集合是指满足

16、最小支持度的项目集合l频繁集的子集也一定是频繁的频繁集的子集也一定是频繁的l如如, 如果如果AB 是频繁集，则是频繁集，则 A B 也一定是频繁集也一定是频繁集l从从1到到k（k-频繁集）递归查找频繁集频繁集）递归查找频繁集l用得到的频繁集生成关联规则用得到的频繁集生成关联规则2021-7-252021-7-25数据挖掘数据挖掘20Apriori算法算法l连接连接: 用用 Lk-1自连接得到候选自连接得到候选k-项集项集Ck，连接时只能将只差连接时只能将只差最后一个项目不同的项集进行连接最后一个项目不同的项集进行连接l修剪修剪: 一个一个k-项集，如果他的一个项集，如果他的一个k-1项集（他的

17、子集项集（他的子集 ）不）不是频繁的，那他本身也不可能是频繁的。是频繁的，那他本身也不可能是频繁的。l伪代码伪代码:Ck: Candidate itemset of size kLk : frequent itemset of size kL1 = frequent items;for (k = 2; Lk-1 !=; k+) do begin Ck = candidates generated from Lk-1; for each transaction t in database do increment the count of all candidates in Ck that ar

18、e contained in t Lk = candidates in Ck with min_support endreturn k Lk;2021-7-252021-7-25数据挖掘数据挖掘21如何生成候选集如何生成候选集l假定假定 Lk-1 中的项按顺序排列中的项按顺序排列l第一步第一步: 自连接自连接 Lk-1 insert into Ckselect p.item1, p.item2, , p.itemk-1, q.itemk-1from Lk-1 p, Lk-1 qwhere p.item1=q.item1, , p.itemk-2=q.itemk-2, p.itemk-1 q.i

19、temk-1l第二步第二步: 修剪修剪For all itemsets c in Ck doFor all (k-1)-subsets s of c doif (s is not in Lk-1) then delete c from Ck2021-7-252021-7-25数据挖掘数据挖掘22生成候选集的例子生成候选集的例子lL3=abc, abd, acd, ace, bcdl自连接自连接 : L3*L3labc 和和 abd 得到得到 abcd lacd 和和 ace 得到得到 acdel修剪修剪:lade 不在不在 L3中，删除中，删除 acdelC4=abcd2021-7-25202

20、1-7-25数据挖掘数据挖掘23Apriori算法算法 例子例子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 322 533 52L2C2C2扫描 DC3L3itemset2 3 5扫描 Ditemset sup2 3 522021-7-252021-7-25数据挖掘数据挖掘24由频繁项集产

21、生强关联规则由频繁项集产生强关联规则l产生步骤如下：产生步骤如下：l对于每个频繁项集对于每个频繁项集l,产生产生l的所有非空子集的所有非空子集l对于对于l的每个非空子集的每个非空子集s，如果条件概率大于，如果条件概率大于最小置信度阈值，则输出规则最小置信度阈值，则输出规则“s(l-s)”2021-7-252021-7-25数据挖掘数据挖掘25l计算支持度为什么会成为一个问题？计算支持度为什么会成为一个问题？l候选集的个数非常巨大候选集的个数非常巨大l 一笔交易可能包含多个候选集一笔交易可能包含多个候选集2021-7-252021-7-25数据挖掘数据挖掘26提高提高Apriori效率的方法效率

22、的方法l基于基于Hash的项集计数的项集计数: 若若 k-项集在项集在hash-tree的路径上的路径上的一个计数值低于阈值，那它本身也不可能是频繁的。的一个计数值低于阈值，那它本身也不可能是频繁的。l减少交易记录减少交易记录: 不包含任何频繁不包含任何频繁k-项集的交易也不可能项集的交易也不可能包含任何大于包含任何大于k的频繁集，下一步计算时删除这些记录。的频繁集，下一步计算时删除这些记录。l划分划分: 一个项集要想在整个数据库中是频繁的，那么它一个项集要想在整个数据库中是频繁的，那么它至少在数据库的一个分割上是频繁的。至少在数据库的一个分割上是频繁的。 两次扫描数据。两次扫描数据。2021

23、-7-252021-7-25数据挖掘数据挖掘27l抽样抽样: 使用小的支持度使用小的支持度+完整性验证方法。完整性验证方法。在小的抽样集上找到局部频繁项集，然后在小的抽样集上找到局部频繁项集，然后在全部数据集找频繁项集。在全部数据集找频繁项集。l动态项集计数动态项集计数: 在添加一个新的候选集之前，在添加一个新的候选集之前，先估计一下是不是他的所有子集都是频繁先估计一下是不是他的所有子集都是频繁的。的。2021-7-252021-7-25数据挖掘数据挖掘28Apriori 够快了吗够快了吗? 性能瓶颈性能瓶颈lApriori算法的核心算法的核心:l用频繁的用频繁的(k 1)-项集生成项集生成候

24、选候选的频繁的频繁 k-项集项集l用数据库扫描和模式匹配计算候选集的支持度用数据库扫描和模式匹配计算候选集的支持度lApriori 的瓶颈的瓶颈: 候选集生成候选集生成l巨大的候选集巨大的候选集:l104 个频繁个频繁1-项集要生成项集要生成 107 个候选个候选 2-项集项集l要找尺寸为要找尺寸为100的频繁模式，如的频繁模式，如 a1, a2, , a100, 你你必须先产生必须先产生2100 1030 个候选集个候选集l多次扫描数据库：多次扫描数据库： l如果最长的模式是如果最长的模式是n的话，则需要的话，则需要 (n +1 ) 次数据库次数据库扫描扫描2021-7-252021-7-2

25、5数据挖掘数据挖掘29挖掘频繁集挖掘频繁集 不用生成候选集不用生成候选集l频繁模式增长频繁模式增长 (FP-增长增长)用用Frequent-Pattern tree (FP-tree) 结构压缩数据库结构压缩数据库, l高度浓缩，同时对频繁集的挖掘又完备的高度浓缩，同时对频繁集的挖掘又完备的l避免代价较高的数据库扫描避免代价较高的数据库扫描l开发一种高效的基于开发一种高效的基于FP-tree的频繁集挖掘算法的频繁集挖掘算法l采用分而治之的方法学：分解数据挖掘任务为小任采用分而治之的方法学：分解数据挖掘任务为小任务务l避免生成太多关联避免生成太多关联2021-7-252021-7-25数据挖掘数

26、据挖掘30用用 FP-tree挖掘频繁集挖掘频繁集l基本思想基本思想 (分而治之分而治之)l用用FP-tree递归增长频繁集递归增长频繁集l频繁模式树：频繁模式树：l条件数据库（条件模式库）条件数据库（条件模式库）l条件模式基条件模式基l条件模式树条件模式树l 2021-7-252021-7-25数据挖掘数据挖掘31挖掘挖掘 FP-tree的主要步骤的主要步骤l 为为FP-tree中的每个节点生成条件模式库中的每个节点生成条件模式库l 用条件模式库构造对应的条件用条件模式库构造对应的条件FP-treel 递归构造条件递归构造条件 FP-trees 同时增长其包含的同时增长其包含的频繁集频繁集l

27、 如果条件如果条件FP-tree只包含一个路径，则直接生只包含一个路径，则直接生成所包含的频繁集。成所包含的频繁集。2021-7-252021-7-25数据挖掘数据挖掘32项头表项头表2021-7-252021-7-25数据挖掘数据挖掘332021-7-252021-7-25数据挖掘数据挖掘342021-7-252021-7-25数据挖掘数据挖掘35为什么为什么 频繁集增长频繁集增长 速度快？速度快？l性能研究显示性能研究显示lFP-growth 比比Apriori快一个数量级。快一个数量级。l原因原因l不生成候选集，不用候选测试。不生成候选集，不用候选测试。l使用紧缩的数据结构使用紧缩的数据

28、结构l避免重复数据库扫描避免重复数据库扫描l基本操作是计数和建立基本操作是计数和建立 FP-tree 树树2021-7-252021-7-25数据挖掘数据挖掘36挖掘闭频繁项集：剪枝策略挖掘闭频繁项集：剪枝策略l项合并：项合并：如果包含频繁项集如果包含频繁项集X的每个事务都包含项集的每个事务都包含项集Y，但不包含但不包含Y的任何真超集，则的任何真超集，则XY形成一个闭频繁项形成一个闭频繁项集，并且不必再搜索包含集，并且不必再搜索包含X但不包含但不包含Y的任何项集的任何项集l子项集剪枝：子项集剪枝：如果频繁项集如果频繁项集X是一个已经发现的闭频是一个已经发现的闭频繁项集繁项集Y的真子集，并且的真

29、子集，并且support_count(X)=support_count(Y)，则，则X和和X在集合枚举在集合枚举树中的所有后代都不可能是闭频繁项集，因此可以剪枝树中的所有后代都不可能是闭频繁项集，因此可以剪枝l项跳过：项跳过：在深度优先挖掘闭项集时，每一层都有一个在深度优先挖掘闭项集时，每一层都有一个与头表和投影数据库相关联的前缀项集与头表和投影数据库相关联的前缀项集X。如果一个局。如果一个局部频繁项部频繁项P在不同层的多个头表中都具有相同的支持度，在不同层的多个头表中都具有相同的支持度，则可以将则可以将P安全地从较高层头表中剪裁掉安全地从较高层头表中剪裁掉2021-7-252021-7-25

30、数据挖掘数据挖掘37支持度支持度-置信度框架的缺点置信度框架的缺点l强关联规则也有可能是无趣的强关联规则也有可能是无趣的2021-7-252021-7-25数据挖掘数据挖掘38相关分析相关分析l相关分析可以用来分析项集间的关联程度相关分析可以用来分析项集间的关联程度 规则 A Csupport, confidence,correlationl关联规则A B的提升度定义如下：如果P(AB)=P(A)P(B)，则项集A的出现独立于项集B的出现l使用卡方进行相关分析：使用卡方进行相关分析：l全置信度：全置信度：l最大置信度最大置信度2021-7-252021-7-25数据挖掘数据挖掘392-=2(观

31、测值 期望值)期望值sup()_( , )min (|), (|)maxsup( ),sup( )ABallconf A BP A B P B AABmax_( , )max (|), (|)conf A BP A B P B AlKluc度量：度量：l余弦度量：余弦度量：2021-7-252021-7-25数据挖掘数据挖掘401kluc(A,B)=( (|)(|)2P A BP B A()sup()cos( , )(|)(|)( )( )sup( ) sup( )P ABABin A BP A BP B AP AP BABl零事务：零不变性是一种度量大型事零事务：零不变性是一种度量大型事务数

32、据库中的关联模式的重要性质务数据库中的关联模式的重要性质l不平衡比：评估规则蕴含式中两个项不平衡比：评估规则蕴含式中两个项集集A和和B的不平衡程度的不平衡程度2021-7-252021-7-25数据挖掘数据挖掘41sup( )sup( )( , )sup( )sup( )sup()ABIR A BABAB2021-7-252021-7-25数据挖掘数据挖掘42频繁模式挖掘路线图频繁模式挖掘路线图l根据挖掘的模式的完全性：给定最小的支持度阈值根据挖掘的模式的完全性：给定最小的支持度阈值l频繁项集的完全集频繁项集的完全集l闭频繁项集闭频繁项集l极大频繁项集极大频繁项集l被约束的频繁项集被约束的频繁

33、项集：满足用户指定的一组约束的频繁项集l近似的频繁项集：近似的频繁项集：只推导被挖掘的频繁项集的近似支持度计数l接近匹配的频繁项集：接近匹配的频繁项集：与接近或几乎匹配的项集的支持度计数相符合的项集l最频繁的最频繁的K个项集：个项集：用户指定的K个最频繁的项集2021-7-252021-7-25数据挖掘数据挖掘44l根据规则所涉及的抽象层：根据规则所涉及的抽象层：l多层关联规则多层关联规则 VS. 单层关联规则单层关联规则l根据规则中所涉及的数据维数：根据规则中所涉及的数据维数：l多维关联规则多维关联规则 VS.单维关联规则单维关联规则lage(x, “30.39”) income(x, “4

34、2.48K”) buys(x, “PC”) 1%, 75%(,)(,int)(,_)(,_int)buys Xcomputerbuys Xprerbuys Xlaptopcomputerbuys Xcolorlaserprer2021-7-252021-7-25数据挖掘数据挖掘45l根据规则中所处理的值类型：根据规则中所处理的值类型：l布尔关联规则布尔关联规则 VS. 量化关联规则量化关联规则l根据挖掘选择性模式的约束或标准根据挖掘选择性模式的约束或标准l基于约束的、近似的、压缩的、近似匹配的或基于约束的、近似的、压缩的、近似匹配的或top-kl根据所挖掘的模式类型：根据所挖掘的模式类型：l频

35、繁项集挖掘频繁项集挖掘：从事务或关系数据集挖掘频繁项集：从事务或关系数据集挖掘频繁项集l序列模式挖掘序列模式挖掘：从序列数据集中搜索频繁子序列，：从序列数据集中搜索频繁子序列，其中序列记录了事件的次序其中序列记录了事件的次序l结构模式挖掘结构模式挖掘：在结构化数据集中搜索频繁子结构：在结构化数据集中搜索频繁子结构l基于应用领域的特定语义：基于应用领域的特定语义：l所挖掘的模式可能因为其特定领域的语义而差所挖掘的模式可能因为其特定领域的语义而差别很大别很大l基于数据分析的使用方法：基于数据分析的使用方法：l频繁模式挖掘常常充当中间步骤，改善对数据频繁模式挖掘常常充当中间步骤，改善对数据的理解进行

36、更大的数据分析的理解进行更大的数据分析（基于模式的分类（基于模式的分类和聚类）和聚类）2021-7-252021-7-25数据挖掘数据挖掘462021-7-252021-7-25数据挖掘数据挖掘47多层关联规则多层关联规则l项通常具有层次项通常具有层次l底层的项通常支持度也底层的项通常支持度也低低l某些特定层的规则可能某些特定层的规则可能更有意义更有意义l交易数据库可以按照维交易数据库可以按照维或层编码或层编码l可以进行共享的多维挖可以进行共享的多维挖掘掘食品面包牛奶脱脂奶光明统一酸奶白黄TID Items T1 111, 121, 211, 221 T2 111, 211, 222, 323

37、 T3 112, 122, 221, 411 T4 111, 121 T5 111, 122, 211, 221, 413 2021-7-252021-7-25数据挖掘数据挖掘48挖掘多层关联规则挖掘多层关联规则l自上而下，深度优先的方法：自上而下，深度优先的方法：l先找高层的先找高层的“强强”规则：规则：牛奶牛奶 面包面包 20%, 60%.20%, 60%.l再找他们底层的再找他们底层的“弱弱”规则：规则：酸奶酸奶 黄面包黄面包 6%, 50%.6%, 50%.l多层关联规则的变种多层关联规则的变种1 1 支持度不变支持度不变: : 在各层之间使用统一的支持度在各层之间使用统一的支持度l一

38、个最小支持度阈值一个最小支持度阈值. . 如果一个项集的父项集不具有最小支持度，如果一个项集的父项集不具有最小支持度，那他本身也不可能满足最小支持度。那他本身也不可能满足最小支持度。l底层项不会成为频繁集，如果支持度底层项不会成为频繁集，如果支持度l太高太高 丢失底层关联规则丢失底层关联规则l太低太低 生成太多的高层关联规则生成太多的高层关联规则2 2 支持度递减支持度递减: : 随着层次的降低支持度递减随着层次的降低支持度递减3 3 使用基于项或基于分组的最小支持度：由用户或专家对特使用基于项或基于分组的最小支持度：由用户或专家对特别关注的商品进行指定别关注的商品进行指定2021-7-252

39、021-7-25数据挖掘数据挖掘49多层关联规则多层关联规则: 支持度不变支持度不变 vs. 支持度递减支持度递减4 层交叉单项过滤：一个第层交叉单项过滤：一个第i层的项被考察，当且仅层的项被考察，当且仅当它在第（当它在第（i-1）层的父节点是频繁的。）层的父节点是频繁的。5 层交叉层交叉K-项过滤：一个第项过滤：一个第i层的层的k-项集被考察，当项集被考察，当且仅当它在第（且仅当它在第（i-1）层的对应父节点）层的对应父节点k-项集是频项集是频繁的繁的6 受控的层交叉单项过滤策略：设置一个层传递阈值，用于向较低层传递相对频繁的项7 交叉层关联规则：应当使用较低层的最小支持度阈值，使得较低层的

40、项可以包含在分析中规则中的项不要规则中的项不要求属于同一概念求属于同一概念层层2021-7-252021-7-25数据挖掘数据挖掘50支持度不变支持度不变支持度不变多层挖掘支持度不变多层挖掘牛奶牛奶support = 10%酸奶酸奶 support = 6%脱脂奶脱脂奶support = 4%层层 1min_sup = 5%层层 2min_sup = 5%2021-7-252021-7-25数据挖掘数据挖掘51支持度递减支持度递减支持度递减多层挖掘支持度递减多层挖掘酸奶酸奶 support = 6%脱脂奶脱脂奶 support = 4%层层 1min_sup = 5%层层 2min_sup =

41、 3%牛奶牛奶support = 10%2021-7-252021-7-25数据挖掘数据挖掘52层交叉单层交叉单项过滤项过滤层交叉层交叉k-项过滤项过滤2021-7-252021-7-25数据挖掘数据挖掘53受控的层交叉受控的层交叉单项过滤单项过滤2021-7-252021-7-25数据挖掘数据挖掘54多层关联：冗余过滤多层关联：冗余过滤l由于“祖先”关系的原因，有些规则可能是多余的。l例子l奶制品 白面包 support = 8%, confidence = 70%l酸奶 白面包 support = 2%, confidence = 72%l酸奶占奶制品25%l我们称第一个规则是第二个规则的

42、祖先l参考规则的祖先，如果他的支持度与我们“预期”的支持度近似的话，我们就说这条规则是冗余的。2021-7-252021-7-25数据挖掘数据挖掘55多维关联规则：多维关联规则： 概念概念l单维规则（维内关联规则）：单维规则（维内关联规则）：buys(X, “milk”) buys(X, “bread”)l多维规则：多维规则： 2个以上维个以上维/谓词谓词l维间关联规则维间关联规则 (谓词谓词不重复不重复)age(X,”19-25”) occupation(X,“student”) buys(X,“coke”)l混合维关联规则混合维关联规则 (谓词重复谓词重复)age(X,”19-25”) b

43、uys(X, “popcorn”) buys(X, “coke”)l类别属性（标称属性）类别属性（标称属性）l有限个值有限个值, 值之间无顺序关系值之间无顺序关系l量化属性量化属性l数值的，值之间隐含了顺序关系数值的，值之间隐含了顺序关系2021-7-252021-7-25数据挖掘数据挖掘56挖掘多维关联的技术挖掘多维关联的技术(针对量化属性针对量化属性)l搜索频繁k-谓词集合：l如: age, occupation, buys 是一个3-谓词集合。l按照对 age 处理方式的不同，分为：1. 用静态方法把数值属性离散化l数值属性可用预定义的概念层次加以离散化。2. 带数量的关联规则l根据数据

44、的分布，动态的把数值属性离散化到不同的“箱”。3. 基于距离的关联规则l用数据点之间的距离动态的离散化2021-7-252021-7-25数据挖掘数据挖掘57数值属性的静态离散化数值属性的静态离散化l在挖掘之前用概念层次先离散化在挖掘之前用概念层次先离散化l数值被替换为区间标号数值被替换为区间标号l关系数据库中，要找到所有频繁关系数据库中，要找到所有频繁k-谓词需要谓词需要k或或k+1次表扫次表扫描。描。l适宜使用数据立方体适宜使用数据立方体lN维立方体的每个单元维立方体的每个单元 对应一个谓词集合对应一个谓词集合l使用数据立方体速度更快使用数据立方体速度更快(income)(age)()(b

45、uys)(age, income)(age,buys) (income,buys)(age,income,buys)2021-7-252021-7-25数据挖掘数据挖掘58挖掘量化关联规则：数值属性的动态离散化挖掘量化关联规则：数值属性的动态离散化l将量化属性对映射到满足给定分类属性条件的将量化属性对映射到满足给定分类属性条件的2-D元组栅格上，然后搜索栅格发现点簇，由元组栅格上，然后搜索栅格发现点簇，由此产生关联规则此产生关联规则lStep1分箱：将量化属性的范围划分为区间，这些分箱：将量化属性的范围划分为区间，这些区间是动态的，在挖掘期间它们可以进一步合并区间是动态的，在挖掘期间它们可以进

46、一步合并lStep2找频繁谓词集：一旦建立了包含每个分类计找频繁谓词集：一旦建立了包含每个分类计数分布的数分布的2-D数组，就可以扫描它，找出满足最小数组，就可以扫描它，找出满足最小置信度和支持度的频繁谓词集置信度和支持度的频繁谓词集lStep3关联规则聚类：将上一步得到的强关联规则关联规则聚类：将上一步得到的强关联规则映射到映射到2-D栅格上，在栅格上形成规则簇，簇中的栅格上，在栅格上形成规则簇，簇中的规则应相当接近规则应相当接近2021-7-252021-7-25数据挖掘数据挖掘592021-7-252021-7-25数据挖掘数据挖掘60ARCS的局限性的局限性l数值属性只能出现在规则的左

47、侧数值属性只能出现在规则的左侧l左侧只能有两个属性左侧只能有两个属性 (2维维)lARCS 的改进的改进l不用基于栅格的方法不用基于栅格的方法l等频分箱等频分箱l基于基于局部完整性局部完整性 测度的聚集测度的聚集l“Mining Quantitative Association Rules in Large Relational Tables” by R. Srikant and R. Agrawal.2021-7-252021-7-25数据挖掘数据挖掘61基于约束的挖掘基于约束的挖掘l使用约束的必要性l在数据挖掘中常使用的几种约束：l知识类型约束：指定要挖掘的知识类型 如关联规则l数据约束： 指定与任务相关的数据集 lFind product pairs sold together in Vancouver in Dec.98.