SAS关联规则及相关算法

1关联规则挖掘2关联规则挖掘1、关联规则挖掘的概念2、二值型关联规则挖掘3、并行关联规则挖掘4、数值型关联规则挖掘5、多层次关联规则挖掘6、关联规则的增量挖掘关联规则的类型11~16关联规则相关定义3~10关联规则的应用173什么是关联规则？关联规则：描述数据库中各数据项之间存在的潜在关系，形式为XY，其中XI，YI，且XY=，X称为规则头(antecedent)，Y称为规则尾(consequent)。项集之间的关联表示如果X出现在一条交易中，那么Y在这条交易中同时出现的可能性比较高。关联规则就是希望发现事务数据库中不同商品（项）之间的关联，反映顾客的购买行为模式，比如购买某一商品对购买其他商品的影响。例如，80%的顾客如果买了牛奶，通常也会买面包。应用发现所有*面包的关联规则，促进面包的销售发现所有牛奶*的关联规则，了解终止牛奶的销售的影响发现商场里货架A和货架B上商品之间的关联规则，调整商品的布置，提高销售量4关联规则的基本概念Given:(1)事务/交易数据库

(2)顾客每次购买的商品构成一条事务(3)每种商品是一个数据项（简称项）I={ii，i2，…，im}是全体数据项的集合数据项集(Itemset)，简称为项集是由数据项构成的非空集合。项集X包含的元素个数称为项集的长度，长度为k的项集称为k阶项集(k_itemset)D为事务数据库，每个事务T有唯一的TID标识，对应一个项集T，有T

I。交易T包含项集X当且仅当XT5事务(交易)数据库的例子预处理6支持数(度)、支持阈值与大项集项集X在事务集合D中的支持数(supportcount)是D中包含X的事务数，记作X.sup或者support(X)。X在D中的支持度(support)就是X的支持数与D的总事务数之比，从统计的角度看，X的支持度就是X在D中出现的概率，用符号Pr(X)表示。支持阈值表示项集在统计意义上的最低重要性，用符号s表示。如果事务数据库的事务量是固定的，常用最小支持数（minsup=s|D|，其中|D|是总事务数）代替支持阈值。

事先给定一个minsup（或s），如果项集X的支持数X.supminsup（或项集X的支持度Pr(X)s），则X称为大项集(largeitemset)或者频繁项集(frequentitemset)。7例子令minsup=2，计算项集及其支持数。其中，{果酱面包}、{香蕉}、{酸奶}、{香蕉，果酱面包}的支持数minsup，所以是大项集。

8置信度与置信阈值规则XY的支持度定义为Pr(XY)，表示X，Y同时出现的可能性。规则XY的置信度（confidence）定义为Pr(XY)/Pr(X)=support(XY)/support(X)，表示D中包含X的事务同时也包含Y的可能性，记为conf(XY)。由于这个数值等于在X出现的条件下Y也出现的概率，因此规则的置信度也可以用条件概率符号Pr(Y|X)表示。置信阈值表示规则在统计意义上应该满足的最低置信度，用符号minconf表示。9关联规则挖掘XY是关联规则，给定支持阈值、置信阈值支持度(support),

s：包含{X,Y}的概率置信度(confidence),

c：一条包含{X}的交易也同时包含Y的条件概率支持度和置信度不小于给定阈值强关联规则:对于给定的支持阈值和置信阈值，发现那些置信度和支持度都大于或等于相应阈值的规则称为强关联规则。购买“婴儿尿布”的顾客Customerbuysboth购买“啤酒”的顾客10关联规则挖掘示例规则

A

C:support=support({A,C})=50%confidence=support({A,C})/support({A})=66.6%规则C

A:support=support({A,C})=50%confidence=support({A,C})/support({C})=100%支持阈值50%置信阈值50%11关联规则的类型关联规则按规则的变量类型分按规则中数据的抽象层次分按规则涉及的数据维数分特殊类型的关联规则按应用领域分分二值（布尔）型关联规则数值型关联规则单维关联规则多维关联规则否定关联规则带约束关联规则带权值关联规则空间关联规则时序关联规则单层关联规则多层关联规则12二值（布尔）型关联规则vs数值型(量化)关联规则二值型关联规则处理的数据都是离散的、分类化的，用来显示这些变量之间的关系。buys(x,“面包”)

buys(x,“牛奶”)[0.5%,60%]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%]13单层关联规则vs多层关联规则单层关联规则：所有的变量都是细节数据(原始的商品)，没有层次的区分多层关联规则：体现了数据的层次性（用概念树或者概念图表示），发生关联的数据可能位于同一层次（同层关联规则），也可能位于不同的层次（层间关联规则）。IBM台式机HP打印机（细节层次上的单层关联规则）台式机HP打印机（较高层次和细节层次之间的层间关联规则）台式机打印机（高层次上的同层关联规则）14单维关联规则vs多维关联规则单维关联规则只涉及数据表的一个字段，多维关联规则涉及数据表的多个字段。buys(x,”啤酒“)buys(x,”尿布“)：单维关联规则gender(x,“女”)

job(x,“秘书”)：二维关联规则age(x,“20…30”)

job(x,“学生”)

buys(x,“笔记本电脑”)：三维关联规则根据是否允许同一个字段在规则中重复出现，多维关联规则又可以分为维间关联规则（不允许字段在规则中重复出现）和混合维关联规则（允许字段在规则的左右部分同时出现）。age(x,“20…30”)

buys(x,“笔记本电脑”)buys(x,“打印机”):混合维关联规则15特殊类型的关联规则有约束的关联规则：对关联规则施加语义约束，限制规则左部或者规则右部必需包含某些字段或对规则形式进行约束发现所有规则右部中包含“面包”的关联规则发现单价在100元以上或者购买数量不小于10的商品之间的关联规则否定关联规则：限制某些字段不出现在规则中咖啡茶叶：如果不购买咖啡，那么买茶叶的可能性较大带权值的关联规则：将商品的价格或购买数量作为权值洗涤剂消毒柜

16其它领域的关联规则空间关联规则发现地理位置的关联性85%的靠近高速公路的大城镇与水相邻发现通常与高尔夫球场相邻的对象时态关联规则附加了时间维度，从交易数据集中找出相似的交易关联规则交易序列的关联规则常常带有周期性，如季节性的购物高峰，这样的规则称为循环规则，即在一定时间间隔内周期性出现的规则

17关联规则的应用零售业：安排商品布局，提供购买建议市场营销：分析顾客的购买行为和习惯

识别欺诈：发现异常事件

因特网：提高网络的响应速度，调度网络代理的缓存，发现用户的浏览模式

医学：预测一次手术、药物检验或药物治疗的效果

18关联规则挖掘的算法关联规则挖掘AIS算法Apriori算法Hash算法多层次关联规则抽样算法分区算法分布算法增量算法数值型关联规则提高效率算法关联规则概念扩展其它序列模式模糊关联规则否定关联规则有约束的关联规则SETM算法并行算法带权值的关联规则19关联规则挖掘1、关联规则挖掘的概念2、二值（布尔）型关联规则挖掘3、并行关联规则挖掘4、数值型关联规则挖掘5、多层次关联规则挖掘6、关联规则的增量挖掘20关联规则挖掘的两个步骤大项集的搜索：搜索支持度不小于指定支持阈值的项集需要扫描数据库，是关联规则挖掘的主要步骤根据搜索的方向、范围、目标和数据格式，可以构造不同的搜索算法

关联规则的生成：对每一个大项集L，检查L的每个非空子集X，生成规则XL-X，它的支持度为Pr(L)，置信度为Pr(L)/Pr(X)，只有那些大于或等于用户给定的置信阈值的规则才被保留下来。根据支持度的性质，这个步骤可简化为先检验L的最大子集，只有当生成规则的置信度不小于置信阈值时才检验更小的子集。例如，L={A,B,C,D}，如果规则{ABC}{D}的置信度达不到置信阈值，则{AB}{CD}也达不到置信阈值(因为Pr({AB})≥Pr({ABC}))。

21大项集的搜索策略大项集的搜索按搜索的顺序分按搜索的范围分按搜索的目标分按数据存储格式分由底向上由顶向下混合全搜索最大项集搜索横向搜索纵向搜索完备搜索启发式搜索22关联规则挖掘的第一个算法：AIS过程：AIS算法的基本思想是通过多次循环来计算大项集。Ck:k阶候选项集

Lk:k阶大项集首先，扫描数据库，得到一阶大项集。然后，在第k（k>1）次扫描时，对每条交易t，找到它所包含的所有k-1阶的大项集Lk-1，根据t中出现的数据项，把它们分别扩展成k阶项集，加入到k阶候选项集的集合中，同时对候选项集的支持数进行累加。例如，如果{A,B,C,D}是当前处理的交易，{AB}是它所包含的2阶大项集，由{AB}扩展得到{ABC}，{ABD}，作为3阶候选项集。当完成一遍扫描后，就可以得到k阶候选项集的支持数，那些支持数不小于最小支持数的项集就是k阶大项集。开始下一次扫描，直到候选项集为空时，算法停止。23AIS算法示例事务数据库D扫描DC1L2扫描DL1C2minsup=3C3扫描Dminconf=80%强关联规则是：EB24Apriori算法AIS算法的瓶颈:候选项集是在扫描事务数据库时构造的，产生的候选项集中有很多并不是大项集，这样不仅会浪费计算时间，还会占用大量的存储空间。Apriori算法:利用上次循环产生的大项集构造新的候选项集，然后扫描数据库，计算候选项集的支持数，扫描结束时得到大项集依据：一个项集是大项集当且仅当它的所有子集都是大项集。反之，如果一个项集的某个子集不是大项集，那么这个项集也不可能是大项集。例如，如果{AB}是大项集，

那么{A}，{B}也是大项集25算法过程扫描数据库，计算1阶大项集；从2阶开始，每次循环利用上次循环产生的大项集构造新候选项集，然后计算每个候选项集的支持度，得到下一阶大项集；重复以上步骤，直到某阶大项集为空。26Apriori算法示例事务数据库D扫描DC1C2扫描DC2L1L2minsup=3C3itemset{BCE}27问题(1):如何产生候选数据项集？假设数据项按顺序排列Step1:大项集自连接Ck=Lk-1Lk-1

Step2:削减forallCk

中的每个元素cdoforallc的子集sdoif(s不再大项集Lk-1中)thendeletecfromCk28Apriori_gen示例L3={abc,abd,acd,ace,bcd}自连接:L3L3{abcd}，{abce}，{acde}削减:{acde}isremovedbecause{ade}isnotinL3同理：{abce}也要被删除。C4={abcd}29交易号项集合T100I1，I2，I5T200I2，I4T300I2，I3T400I1，I2，I4T500I1，I3T600I2，I3T700I1，I3T800I1，I2，I3，I5T900I1，I2，I3表1交易数据库D

例：找出频繁项集－－Apriori算法30项集支持度计数｛I1｝6｛I2｝7｛I3｝6｛I4｝2｛I5｝2项集支持度计数｛I1｝6｛I2｝7｛I3｝6｛I4｝2｛I5｝2C1L1扫描D，对每个候选计数比较候选支持度计数与最小支持度计数找出频繁1－项集的集合L1找出频繁项集－－Apriori算法例：最小支持度阈值为231项集支持度计数｛I1｝6｛I2｝7｛I3｝6｛I4｝2｛I5｝2项集｛I1，I2｝｛I1，I3｝｛I1，I4｝｛I1，I5｝｛I2，I3｝｛I2，I4｝｛I2，I5｝｛I3，I4｝｛I3，I5｝｛I4，I5｝L1C2由L1产生候选C2Lk-1用于产生候选Ck

找出频繁项集－－Apriori算法连接&剪枝32项集支持度计数｛I1，I2｝4｛I1，I3｝4｛I1，I4｝1｛I1，I5｝2｛I2，I3｝4｛I2，I4｝2｛I2，I5｝2｛I3，I4｝0｛I3，I5｝1｛I4，I5｝0项集支持度计数｛I1，I2｝4｛I1，I3｝4｛I1，I5｝2｛I2，I3｝4｛I2，I4｝2｛I2，I5｝2C2L2比较候选支持度计数与最小支持度计数扫描D，对每个候选计数33项集支持度计数｛I1，I2｝4｛I1，I3｝4｛I1，I5｝2｛I2，I3｝4｛I2，I4｝2｛I2，I5｝2L2项集｛I1，I2，I3｝｛I1，I2，I5｝由L2产生候选C3C3连接&剪枝34连接：C3＝L2

L2＝{{I1,I2},{I1,I3},{I1,I5},{I2,I3},{I2,I4},{I2,I5}}

{{I1,I2},{I1,I3},{I1,I5},{I2,I3},{I2,I4},{I2,I5}}={{I1,I2,I3},{I1,I2,I5},{I1,I3,I5},{I2,I3,I4},{I2,I3,I4},{I2,I3,I5},{I2,I4,I5}}35剪枝：{I1,I2,I3}的2-项子集是{I1,I2},{I1,I3}和{I2,I3}。{I1,I2,I3}的所有2-项子集都是L2的元素。因此，保留{I1,I2,I3}在C3中。{I2,I3,I5}的2-项子集是{I2,I3},{I2,I5}和{I3,I5}。{I3,I5}不是L2的元素，因而不是频繁的。因此，由C3中删除{I2,I3,I5}。剪枝后C3＝{{I1,I2,I3},{I1,I2,I5}}。

36项集支持度计数｛I1，I2，I3｝2｛I1，I2，I5｝2C3扫描D，对每个候选计数比较候选支持度计数与最小支持度计数项集支持度计数｛I1，I2，I3｝2｛I1，I2，I5｝2L337步骤：a.

对于每个频繁项集l，找出l的所有非空子集；b.对于l的每个非空子集a，如果

support_count(l)/support_count(a)≥min_conf，则输出规则“a＝>（l－a）”。频繁项集产生强关联规则38例：假定数据包含频繁集l＝{I1,I2,I5}，L的非空子集有{I1,I2},{I1,I5},{I2,I5},{I1},{I2},和{I5}。可以由l产生的关联规则：

I1I2I5，confidence＝2/4＝50%；

I1I5I2，confidence＝2/2＝100%；

I2I5I1，confidence＝2/2＝100%；

I1I2I5，confidence＝2/6＝33%；

I2I1I5，confidence＝2/7＝29%；

I5I1I2,confidence＝2/2＝100%；若最小置信度阈值为70%，则只有I1I5I2，I2I5I1，I5I1I2可输出，是强关联规则39Apriori算法—例子数据库D扫描DC1L1L2C2C2扫描DC3L3扫描Ditemset{235}例：最小支持度阈值为240Apriori算法的瓶颈Apriorialgorithm的核心根据频繁(k-1)-itemsets产生候选k-itemsets每次循环扫描数据库，计算候选k-itemsets的支持度Apriori的瓶颈大量的候选项集(尤其是C2)n个大1-itemsetn*(n-1)/2个候选2-itemsets多次扫描数据库需要扫描n+1次，n是大项集的最大长度41Apriori算法的改进策略改进策略减少扫描数据量减少扫描次数减少候选项集利用前缀树提高搜索速度AprioriTidAprioriHybral纵向算法DHP抽样算法SEARSpearFP-treePartitionDIC42AprioriTid算法原理：如果一个事务不包含k阶大项集，那么也必然不包含k+1阶大项集，因此，将这些事务删除后，下一次循环就可减少扫描事务量，而不影响候选项集的支持数43方法：构造一个Tid表，用来记录每条事务包含的候选项集。k阶候选项集的Tid表记作：Ck

，其形式为<t.TID,{CCk|Ct}>，其中TID是事务t的标识，C是事务t中包含的k阶候选项集。如果一个事务不包含任何k阶候选项集，那么这条事务就不会出现在中。由于1阶候选项集就是所有的项，与D相同。当k>1时，由产生。对每个k阶候选项集C，如果C的两个子集都包含在里的某条记录中，那么就添加C到的相应记录中。由Tid表得到k阶候选项集的支持数，避免对事务数据库的重复扫描。当k较大时，Tid表的元素个数远远小于总事务数，且每个事务只包含少量的候选项集，因此随着循环的增加，扫描的数据量逐渐降低。

44AprioriTid算法示例事务数据库DTid1C2L1L2minsup=3Tid245分区算法原理：“分而治之”，先把数据库从逻辑上分成几个不相交的分区，划分的原则是使得每个分区的数据都能够存入内存,并且各分区的支持阈值和全局的支持阈值相同。性质：如果一个项集是全局大项集，那么它至少在一个分区中是大项集。划分算法的过程：首先对每个分区分别计算局部大项集（如果项集在分区中的支持度不小于支持阈值，则称为局部大项集），再将结果合并得到全局大项集（如果项集在整个数据库中的支持度不小于支持阈值，则称为全局大项集）。46Partition算法：每次处理一个分区，利用Apriori算法得到本分区的局部大项集；然后将各分区的局部大项集合并，生成候选项集，扫描整个事务数据库，计算这些项集的支持度，最终得到全局大项集。由于局部大项集的生成在内存中进行，整个过程只需要扫描两次数据库，一次用来读入分区，另一次用来计算全局大项集。Partition算法适用于数据规模较大,不能一次读入内存的情况,而且可以并行地执行，每个处理器处理一个分区的数据，得到局部大项集之后，经过处理器之间的通信，产生全局的候选项集。47分区算法示例事务数据库DCL扫描D支持阈值=50%分区2L1L2itemsetsup{BC}1{BE}1分区1L1L2L3itemsetsup.{A}2{B}2{C}3{E}248关联规则挖掘1、关联规则挖掘的概念2、二值型关联规则挖掘3、并行关联规则挖掘4、数值型关联规则挖掘5、多层次关联规则挖掘6、关联规则的增量挖掘49Count分布(CD)算法过程每个处理器分配一部分数据每个处理器的内存复制全部候选项集每个处理器独立执行Apriori算法，扫描本地数据，计算局部支持度，通过处理器之间的通讯得到全局支持度50Count分布(CD)算法优缺点各处理器独立计算，只在循环结束时交互支持度，降低了通讯量内存利用率低，各处理器存储各自的候选项集，如果候选项集数量很大时，必须分几次装入内存，造成数据库的多次扫描适应于项数小和min_support大的情形51关联规则挖掘1、关联规则挖掘的概念2、二值型关联规则挖掘3、并行关联规则挖掘4、数值型关联规则挖掘5、多层次关联规则挖掘6、关联规则的增量挖掘52数值型关联规则分类型变量有限取值，无序数值型变量连续，有序方法将数据转化为布尔型数据每个分类型数值映射为一个变量对每个连续型变量分段，每段映射为一个变量如何对数值型属性分段？主要问题是区间的划分和合并先对数值型属性细分，计算每个区间的支持度，再合并相邻的区间，直到支持度超过一个指定的阈值为止。54关联规则挖掘1、关联规则挖掘的概念2、二值型关联规则挖掘3、并行关联规则挖掘4、数值型关联规则挖掘5、多层次关联规则挖掘6、关联规则的增量挖掘55概念层次树概念层次树是一棵从一般概念到具体概念的层次关系树，树的根结点是最一般的概念，树的叶结点是最具体的概念即原始数据。设a,b是两个概念，若b是以a为根的子树中的结点，则称b是a的后代或a是b的祖先。如果a是b的直接祖先，则a称是b的父亲，或b是a的儿子。

衣服鞋子

外套衬衫

运动鞋长靴

夹克滑雪衫56多层次关联规则为什么挖掘多层次关联规则？数据项之间经常存在概念层次层次越高，数据项的支持度也越大某些高层次上的规则或许能显示有用的信息57多层关联规则项通常具有层次底层的项通常支持度也低某些特定层的规则可能更有意义食品面包牛奶脱脂奶光明统一酸奶白黄58多层关联规则

支持度不变vs.支持度递减支持度不变:在各层之间使用统一的支持度

一个最小支持度阈值.如果一个项集的父项集不具有最小支持度，那他本身也不可能满足最小支持度。如果支持阈值太高丢失底层关联规则太低生成太多的高层关联规则支持度递减:随着层次的降低支持度递减59支持度不变支持度不变多层挖掘牛奶[support=10%]酸奶

[support=6%]脱脂奶[support=4%]层1min_sup=5%层2min_sup=5%60支持度递减支持度递减多层挖掘酸奶

[support=6%]脱脂奶[support=4%]层1min_sup=5%层2min_sup=3%牛奶[support=10%]61多层关联：冗余过滤由于“祖先”关系的原因，有些规则可能是多余的。例子牛奶白面包[support=8%,confidence=70%]

(1)酸奶白面包[support=2%,confidence=72%](2)我们称第一个规则是第二个规则的祖先参考规则的祖先，如果他的支持度与我们“预期”的支持度近似的话，我们就说这条规则是冗余的。62食品面包牛奶脱脂奶光明统一酸奶白黄63挖掘多层次关联规则同层关联规则处于同概念层的关联规则，挖掘在特定概念层上逐层展开，需对项的每个层次进行处理，一般采用自顶向下的策略。对每一层，可以使用类似于单层关联规则挖掘的发现频繁项集的任何算法；算法：ML-T2、ML_T1LA、ML-SH、ML-T2+等层间关联规则跨越层边界，规则中的项不要求属于同一概念层。算法：ML-CH等64同层关联规则的挖掘步骤对概念层次树进行编码将事务的项用对应的编码代替，构成编码数据库从高到低依次搜索各层的大项集由各层的大项集分别生成关联规则65概念层次树及事务的编码先对根结点编码，再按照从上到下的顺序对每层的结点逐层编码。一个概念的子结点的序号为：1,2,3…。子结点代码=父结点代码+子结点在子树中的序号，依此类推把数据库中的值用其编码代替

66层交叉过滤如果数据项A是非频繁的，那么A的后代也是非频繁的如果某个数据项是非频繁的，那么包含其后代的数据项集也必定是非频繁的利用上层大项集对下层事务进行消减ML_T1L2算法、ML_T1LA算法等

67层交叉过滤体育类商品（支持度＝10％）篮球足球非频繁不考察不考察层2支持阈值＝3%

层1支持阈值＝12%

一个第i层的k－项集被考察，当且仅当它在第（i-1）层的父节点k－项集是频繁的。68ML_T2算法ML_T2算法[32]采用交易削减的方法，减小了扫描的数据量，从而提高算法的效率。该算法按照概念层次从高到低的顺序，搜索每层的大项集。69ML_T2算法步骤：在最高概念层次上，函数get_large_1_itemset扫描T[1]（原始数据库D），得到一阶大项集；由函数get_filtered_table利用一阶大项集对T[1]过滤，删除每条交易中祖先不属于大项集的项，如果某交易所有的项都被删除，那么该交易也被删除，最终得到削减的数据库T[2]。然后，利用Apriori算法通过循环得到各阶大项集。从第2层开始，算法扫描T[2],依次得到每层的大项集。当达到了最大层次数或者某层上的1阶大项集为空时，算法停止。70ML_T2算法示例T[1]L1L2minsup=4T[2]L2L1minsup=3L1L2minsup=3L3itemsetsup.{11*}5{12*}4{21*}4{22*}471ML_T1LA算法ML_T1LA算法与ML_T1算法的过程基本相同，区别是ML_T1LA在每层都执行类似的交易削减。在任意的p层上，得到一阶大项集后，对数据库T[p]进行过滤，得到T[p+1],从而实现逐层减小扫描的数据量，但这种方法只在每层所过滤掉的数据量较大时比较有效.72ML_T1LA算法示例T[1]L1L2minsup=4T[2]L2L1minsup=3T[3]L1L2minsup=3L3itemsetsup.{11*}5{12*}4{21*}4{22*}473层间关联规则的挖掘定义2.17层间关联规则又称为广义关联规则，形式为XY，其中X，Y是任意概念层次上的大项集，满足X∩Y=

，且Y不包括X中的项的祖先。2023/2/4决策量化技术74定义2.18设项集X={x1,x2,…,xk}，Y={y1,y2,…,yk}，其中yj是xj的祖先概念。如果已知Y的支持度为Pr(Y)，那么X的期望支持度等于：EY(Pr(X))=(Pr(X1)/Pr(Y1)*Pr(X2)/Pr(Y2)*…….Pr(XK)/Pr(YK))*Pr(Y)75定义2.19设XY是一条规则，Z是X的祖先，W是Y的祖先。如果已知规则ZW的置信度为Pr(W|Z)，那么规则XY的期望置信度等于：EZW(Pr(XY))

=

(Pr(Y1)/Pr(W1)*Pr(Y2)/Pr(W2)*…….Pr(YK)/Pr(WK))*Pr(W|Z)76如果“衣服”

“鞋子”是一条关联规则，支持度为20%，置信度为60%。假设买衣服的交易中外套占50%，那么根据统计规律，“外套”

“鞋子”的期望支持度应该为10%，期望置信度为60%。如果经过计算发现实际的支持度和置信度与期望值相近，那么这条规则就是冗余的。

衣服鞋子

外套衬衫

运动鞋长靴

夹克滑雪衫77如果项集Y是项集X的祖先，而且不存在其它的项集Z，满足Y是Z的祖先，Z是X的祖先，那么称Y是X的最近祖先或者父项集。78

衣服鞋子

外套衬衫

运动鞋长靴

夹克滑雪衫例如，{外套，长靴}，{夹克，鞋子}都是{夹克，长靴}的父项集.而{衣服，长靴}是{夹克，长靴}的祖先但不是父项集，因为{衣服，长靴}是{外套，长靴}的祖先，而{外套，长靴}又是{夹克，长靴}的祖先。评价规则是否是冗余的，首先要根据其父项集计算规则的期望支持度和期望置信度。79定义2.20给定兴趣阈值R，如果XY没有祖先，或者它的支持度是相对于父项集的期望支持度的R倍，或者置信度是期望置信度的R倍，那么这条规则是有趣的，否则就是冗余的。广义关联规则挖掘就是找到置信度和支持度都大于相应阈值的非冗余规则。80例2.15假设我们从事务数据库中得到以下项集和规则，令兴趣阈值R=2，判断规则的冗余性。

项集 支持度衣服 0.5外套 0.2夹克 0.1规则支持度衣服鞋子

1外套鞋子0.8夹克鞋子0.4

衣服