13-14
王 灿
数据挖掘
sjwj@dlc.zju.edu.cn
0703004
大型数据库中的关联规则
挖掘
什么是关联规则挖掘？
? 关联规则挖掘,
? 从事务数据库，关系数据库和其他信息存储中的大
量数据的项集之间发现有趣的、频繁出现的模式、
关联和相关性。
? 应用,
? 购物篮分析、分类设计、捆绑销售等
“尿布与啤酒, ——典型关联分析案例
? 采用关联模型比较典型的案例是“尿布与啤酒”
的故事。在美国，一些年轻的父亲下班后经常
要到超市去买婴儿尿布，超市也因此发现了一
个规律，在购买婴儿尿布的年轻父亲们中，有
30%～ 40%的人同时要买一些啤酒。超市随后
调整了货架的摆放，把尿布和啤酒放在一起，
明显增加了销售额。同样的，我们还可以根据
关联规则在商品销售方面做各种促销活动。
购物篮分析
? 如果问题的全域是商店中所有商品的集合，则对每种
商品都可以用一个布尔量来表示该商品是否被顾客购
买，则每个购物篮都可以用一个布尔向量表示；而通
过分析布尔向量则可以得到商品被频繁关联或被同时
购买的模式，这些模式就可以用关联规则表示
（ 0001001100，这种方法丢失了什么信息？ ）
? 关联规则的两个兴趣度度量
? 支持度
? 置信度
%]60%,2[ s u p
)"",( )"",(
??
?
c o n fid e n c ep o r t
s o ft w a r eXb u y sc o m p u te rXb u y s
关联规则：基本概念
? 给定,
? 项的集合,I={i1,i2,...,in}
? 任务相关数据 D是数据库事务的集合，每个事务 T则
是项的集合，使得
? 每个事务由事务标识符 TID标识；
? A,B为两个项集，事务 T包含 A当且仅当
? 则关联规则是如下蕴涵式,
? 其中 并且,规则 在事
务集 D中成立，并且具有支持度 s和置信度 c
IT ?
TA?
],[ csBA ?
IBIA ??,??? BA BA ?
基本概念 ——示例
? 项的集合 I={A,B,C,D,E,F}
? 每个事务 T由事务标识符 TID标识，它是项的集合
? 比如,TID(2000)={A,B,C}
? 任务相关数据 D是数据库事务的集合
T I D 购买的 it e m
2000 A,B,C
1000 A,C
4000 A,D
5000 B,E,F
规则度量：支持度和置信度
T I D 购买的 it e m
2000 A,B,C
1000 A,C
4000 A,D
5000 B,E,F
Customer
buys diaper
Customer
buys both
Customer
buys beer
? 对所有满足最小支持度和
置信度的关联规则
? 支持度 s是指事务集 D中包
含 的百分比
? 置信度 c是指 D中包含 A的事
务同时也包含 B的百分比
? 假设最小支持度为 50%，
最小置信度为 50%，则有
如下关联规则
? A ? C (50%,66.6%)
? C ? A (50%,100%)
BA?
)( )(s u p BAPBAp o r t ???
)(/)()|( )( APBAPABPBAc o n f i d e n c e ????
大型数据库关联规则挖掘 (1)
? 基本概念
? k－项集,包含 k个项的集合
? {牛奶，面包，黄油 }是个 3－项集
? 项集的频率 是指包含项集的事务数
? 如果项集的频率大于（最小支持度 × D中的事务总
数），则称该项集为 频繁项集
大型数据库关联规则挖掘 (2)
? 大型数据库中的关联规则挖掘包含两个过程,
? 找出所有频繁项集
? 大部分的计算都集中在这一步
? 由频繁项集产生强关联规则
? 即满足最小支持度和最小置信度的规则
关联规则挖掘分类 (1)
? 关联规则有多种分类,
? 根据规则中所处理的值类型
? 布尔关联规则
? 量化关联规则（规则描述的是量化的项或属性间的关联性）
? 根据规则中涉及的数据维
? 单维关联规则
? （仅涉及 buys这个维）
? 多维关联规则
)"",( )"48...42",( )"39...30",( c o m p u t e rXb u y skkXi n c o m eXa g e ??
)"",( )"",( s o f t w a r eXb u y sc o m p u t e rXb u y s ?
s o f t w a r em a n a g e m e n tf i n a n c i a lc o m p u t e r __?
关联规则挖掘分类 (2)
? 根据规则集所涉及的抽象层
? 单层关联规则
? 多层关联规则 （在不同的抽象层发现关联规则）
? 根据关联挖掘的各种扩充
? 挖掘最大的频繁模式（该模式的任何真超模式都是非频繁的）
? 挖掘频繁闭项集（一个项集 c是频繁闭项集，如果不存在其真超
集 c’，使得每个包含 c的事务也包含 c’）
? （最大的频繁模式和频繁闭项集可以用来减少挖掘中产生的频
繁项集）
)"_",( )"39...30",( c o m p u t e rl a p t o pXb u y sXage ?
)"",( )"39...30",( c o m p u t e rXb u y sXa g e ?
由事务数据库挖掘单维布尔关联规则
? 最简单的关联规则挖掘，即单维、单层、布尔关联规
则的挖掘。
T r a n s a ct i o n I D I t e m s B o u g h t
2000 A,B,C
1000 A,C
4000 A,D
5000 B,E,F
F r e q u e n t I te m s e t S u p p o r t
{ A } 75%
{ B } 50%
{ C} 50%
{ A,C} 50%
最小支持度 50%
最小置信度 50%
? 对规则 A ? C,其支持度 =50%
? 置信度
%6.66)(s u p/)(s u p)(/)()|( )( ??????? Ap o r tCAp o r tAPCAPACPCAc o n f i d e n c e
)( )(s u p CAPCAp o r t ???
Apriori算法 (1)
? Apriori算法是挖掘布尔关联规则频繁项集的算法
? Apriori算法利用的是 Apriori性质：频繁项集的所有非
空子集也必须是频繁的。
? 模式不可能比 A更频繁的出现
? Apriori算法是反单调的，即一个集合如果不能通过测试，则
该集合的所有超集也不能通过相同的测试。
? Apriori性质通过减少搜索空间，来提高频繁项集逐层产生的
效率
BA ?
Apriori算法 (2)
? Apriori算法利用频繁项集性质的先验知识
（ prior knowledge），通过逐层搜索的迭代方
法，即将 k-项集用于探察 (k+1)-项集，来穷尽
数据集中的所有频繁项集。
? 先找到频繁 1-项集集合 L1,然后用 L1找到频繁 2-项集
集合 L2，接着用 L2找 L3，直到找不到频繁 k-项集，
找每个 Lk需要一次数据库扫描。
Apriori算法步骤
? Apriori算法由 连接 和 剪枝 两个步骤组成。
? 连接,为了找 Lk，通过 Lk-1与自己连接产生候选 k-项集
的集合，该 候选 k项集 记为 Ck。
? Lk-1中的两个元素 L1和 L2可以执行连接操作 的条件是
? Ck是 Lk的超集，即它的成员可能不是频繁的，但是所
有频繁的 k-项集都在 Ck中（为什么？）。因此可以通
过扫描数据库，通过计算每个 k-项集的支持度来得到
Lk 。
? 为了减少计算量，可以使用 Apriori性质，即如果一个 k-项集
的 (k-1)-子集不在 Lk-1中，则该候选不可能是频繁的，可以直
接从 Ck删除。
])1[]1[(])2[]2[(...])2[]2[(])1[]1[( 21212121 ???????????? klklklklllll
21 ll ??
Apriori算法 ——示例
Database TDB
1st scan
C1 L1
L2
C2 C2
2nd scan
C3 L3 3rd scan
Tid Items
10 A,C,D
20 B,C,E
30 A,B,C,E
40 B,E
Itemset sup
{A} 2
{B} 3
{C} 3
{D} 1
{E} 3
Itemset sup
{A} 2
{B} 3
{C} 3
{E} 3
Itemset
{A,B}
{A,C}
{A,E}
{B,C}
{B,E}
{C,E}
Itemset sup
{A,B} 1
{A,C} 2
{A,E} 1
{B,C} 2
{B,E} 3
{C,E} 2
Itemset sup
{A,C} 2
{B,C} 2
{B,E} 3
{C,E} 2
Itemset
{B,C,E}
Itemset sup
{B,C,E} 2
最小支持计数,2
使用 Apiori性质由 L2产生 C3
? 1,连接,
? C3=L2 L2= {{A,C},{B,C},{B,E}{C,E}}
{{A,C},{B,C},{B,E}{C,E}} = {{A,B,C},{A,C,E},{B,C,E}}
? 2．使用 Apriori性质剪枝：频繁项集的所有子集必须是频繁的，
对候选项 C3，我们可以删除其子集为非频繁的选项,
? {A,B,C}的 2项子集是 {A,B},{A,C},{B,C}，其中 {A,B}不是 L2的元素，
所以删除这个选项；
? {A,C,E}的 2项子集是 {A,C},{A,E},{C,E}，其中 {A,E} 不是 L2的元素，
所以删除这个选项；
? {B,C,E}的 2项子集是 {B,C},{B,E},{C,E}，它的所有 2－项子集都是
L2的元素，因此保留这个选项。
? 3．这样，剪枝后得到 C3={{B,C,E}}
????
由频繁项集产生关联规则
? 同时满足最小支持度和最小置信度的才是强关
联规则，从频繁项集产生的规则都满足支持度
要求，而其置信度则可由一下公式计算,
? 每个关联规则可由如下过程产生,
? 对于每个频繁项集 l，产生 l的所有非空子集；
? 对于每个非空子集 s，如果
则输出规则,”
)(_s u p
)(_s u p)|()(
Ac o u n tp o r t
BAc o u n tp o r tBAPBAc o n fi d e n c e ????
c o n fsc o u n tp o r t lc o u n tp o r t m in _)(_s u p )(_s u p ?
)( sls ??
多层关联规则 (1)
? 数据项中经常会形成
概念分层
? 底层的数据项，其支
持度往往也较低
? 这意味着挖掘底层数据
项之间的关联规则必须
定义不同的支持度
All
Computer
accessory software
laptop financial mouse color
printer computer
desktop
IBM
edu,
Microsoft
b/w
HP Sony
wrist
pad
Logitech
TID Items
T1 {IBM D/C,Sony b/w}
T2 {Ms,edu,Sw.,Ms,fin,Sw.}
T3 {Logi,mouse,Ergoway wrist pad}
T4 {IBM D/C,Ms,Fin,Sw.}
T5 {IBM D/C}
Ergoway
多层关联规则 (2)
? 在适当的等级挖掘出来的数据项间的关联规则
可能是非常有用的
? 通常，事务数据库中的数据也是根据维和概念
分层来进行储存的
? 这为从事务数据库中挖掘不同层次的关联规则提供了
可能。
? 在多个抽象层挖掘关联规则，并在不同的抽象
层进行转化，是数据挖掘系统应该提供的能力
挖掘多层关联规则的方法
? 通常，多层关联规则的挖掘还是使用置信度－支持度
框架，可以采用自顶向下策略
? 请注意：概念分层中，一个节点的支持度肯定不小于该节点
的任何子节点的支持度
? 由概念层 1开始向下，到较低的更特定的概念层，对每个概
念层的频繁项计算累加计数
? 每一层的关联规则挖掘可以使用 Apriori等多种方法
? 例如,
? 先找高层的关联规则,computer -> printer [20%,60%]
? 再找较低层的关联规则,laptop -> color printer [10%,
50%]
多层关联 ——一致支持度
? 一致支持度：对所有层都使用一致的最小支持度
? 优点：搜索时容易采用优化策略，即一个项如果不满足
最小支持度，它的所有子项都可以不用搜索
? 缺点：最小支持度值设置困难
? 太高：将丢掉出现在较低抽象层中有意义的关联规则
? 太低：会在较高层产生太多的无兴趣的规则
多层关联 ——递减支持度
? 使用递减支持度，可以
解决使用一致支持度时
在最小支持度值上设定
的困难
? 递减支持度：在较低层
使用递减的最小支持度
? 每一层都有自己的一个
独立的最小支持度
? 抽象层越低，对应的最
小支持度越小
Computer
[support=10%]
Laptop
[support=6%]
Desktop
[support=4%]
min_sup = 5%
min_sup = 5% 3%
多层关联 ——搜索策略 (1)
? 具有递减支持度的多层关联规则的搜索策略
? 逐层独立：完全的宽度搜索，没有频繁项集的背景知识用于
剪枝
? 层交叉单项过滤：一个第 i层的项被考察，当且仅当它在第
（ i-1）层的父节点是频繁的（ P165,图 6-14）
? (computer)?( laptop computer,desktop computer)
? 层交叉 k项集过滤：一个第 i层的 k项集被考察，当且仅当它在
第 (i-1)层的对应父节点 k-项集是频繁的（ P165,图 6-15）
? (computer,printer)?(( laptop computer,color printer),
(desktop computer,b/w printer) …)
多层关联 ——搜索策略 (2)
? 搜索策略比较
? 逐层独立策略条件松，可能导致底层考察大量非频
繁项
? 层交叉 k项集过滤策略限制太强，仅允许考察频繁 k-
项集的子女
? 层交叉单项过滤策略是上述两者的折中，但仍可能
丢失低层频繁项（图 6-14)
受控的层交叉单项过滤策略
? 层交叉单项过滤策略的改进版本
? 设置一个层传递临界值，用于向较低层传递相对频繁的项。
? 即如果满足层传递临界值，则允许考察不满足最小支持度临界值
的项的子女
? 用户对进一步控制多概念层上的挖掘过程有了更多的灵活性，同
时减少无意义关联的考察和产生
Computer [support=10%]
Laptop [support=6%] Desktop [support=4%]
min_sup = 12%
level_passage_support = 8%
min_sup = 3%
检查冗余的多层关联规则
? 挖掘多层关联规则时，由于项间的“祖先”关系，有
些发现的规则将是冗余的
? 例如,
? desktop computer => b/w printer [sup=8%,con=70%] (1)
? IBM desktop computer => b/w printer [sup=2%,con=72%] (2)
? 上例中，我们说第一个规则是第二个规则的“祖先”
? 如果规则 (2)中的项用它在概念分层中的“祖先”代替，
能得到 (1)，而且 (1)的支持度和置信度都接近“期望”
值，则 (1)是冗余的。
多维关联规则 ——概念
? 单维关联规则,
? buys(X,“milk”) ＝ buys(X,“bread”)
? 多维关联规则：涉及两个或多个维或谓词的关联规则
? 维间关联规则：不包含重复的谓词
? age(X,”19-25”) ∧ occupation(X,“student”) =>
buys(X,“coke”)
? 混合维关联规则：包含某些谓词的多次出现
? age(X,”19-25”) ∧ buys(X,“popcorn”) => buys(X,“coke”)
? 在多维关联规则挖掘中，我们搜索的不是频繁项集，而是频繁谓词集。 k-谓词集是包含 k个合取谓词的集
合。
? 例如,{age,occupation,buys}是一个 3-谓词集
挖掘多维关联规则的技术
? 数据属性可以分为分类属性和量化属性
? 分类属性
? 具有有限个不同值，值之间无序
? 量化属性
? 数值类型的值，并且值之间有一个隐含的序
? 挖掘多维关联规则的技术可以根据量化属性的处理分
为三种基本方法,
? 1,量化属性的静态离散化
? 使用预定义的概念分层对量化属性进行静态地离散化
? 2,量化关联规则
? 根据数据的分布，将量化属性离散化到“箱”
? 3,基于距离的关联规则
? 考虑数据点之间的距离，动态地离散化量化属性
多维关联规则挖掘 ——使用量化属性
的静态离散化
? 量化属性使用预定义的概念分层，在挖掘前
进行离散化
? 数值属性的值用区间代替
? 如果任务相关数据存在关系数据库中，则找
出所有频繁的 k-谓词集将需要 k或 k+1次表扫
描
? 数据立方体技术非常适合挖掘多维关联规则
? n-维方体的单元用于存放对应 n-谓词集的 计
数或支持度, 0-D方体用于存放任务相关数
据的事务总数
? 如果包含感兴趣的维的数据立方体已经存在
并物化，挖掘将会很快，同时可以利用
Apriori性质,频繁谓词集的每个子集也必须
是频繁的
(income) (age)
()
(buys)
(age,income) (age,buys) (income,buys)
(age,income,buys)
挖掘量化关联规则 (1)
? 量化关联规则中，数值属性将根据某种挖掘标准，进
行动态的离散化
? 例如：最大化挖掘规则的置信度和紧凑性
? 为了简化量化关联规则挖掘的讨论，我们将聚焦于类
似以下形式的 2-维量化关联规则, Aquan1 ? Aquan2 ? Acat
? （两个量化属性和一个分类属性间的关联）
? 例如,age(X,”30-39”) ? income(X,”42K - 48K”) ? buys(X,”high
resolution TV”)
挖掘量化关联规则 (2)
? 找出这类 2-维量化关联规则的方
法：关联规则聚类系统 (ARCS)
? 一种源于图像处理的技术，该技
术将量化属性对映射到满足给定
分类属性条件的 2-D栅格上，然
后通过搜索栅格点的聚类而产生
关联规则
关联规则聚类系统 (ARCS) (1)
? ARCS过程中的步骤包括
? 1,分箱（根据不同分箱方法创建一个 2-D数组），本步骤的
目的在于减少量化属性相对应的巨大的值个数，使得 2-D栅
格的大小可控
? 等宽分箱
? 等深分箱
? 基于同质的分箱（每个箱中元组一致分布）
? 2,找出频繁谓词集
? 扫描分箱后形成的 2-D数组，找出满足最小支持度和置信度的频
繁谓词集
关联规则聚类系统 (ARCS) (2)
? 3,关联规则聚类
? 将上一步得到的强关联规则映射到 2-D栅格上，使用聚类算法，扫描栅
格，搜索规则的矩形聚类
)"__",()"40...31",()34,( TVr e s o l u t i o nh i g hXb u y sKKXi n c o m eXage ??
)"__",()"40...31",()35,( TVr e s o l u t i o nh i g hXb u y sKKXi n c o m eXage ??
)"__",()"50...41",()34,( TVr e s o l u t i o nh i g hXb u y sKKXi n c o m eXage ??
)"__",()"50...41",()35,( TVr e s o l u t i o nh i g hXb u y sKKXi n c o m eXage ??
)"__",(
)"50.,,31",()35.,,34,(
TVr e s o l u ti o nh ig hXb u y s
KKXin c o m eXa g e
?
?
ARCS的局限性
? 所挖掘的关联规则左手边只能是量化属性
? 规则的左手边只能有两个量化属性（ 2-D栅格
的限制）
? 一种不基于栅格的，可以发现更一般关联规则
的技术，其中任意个数的量化属性和分类属性
可以出现在规则的两端
? 等深分箱动态划分
? 根据 部分完全性 的度量进行聚类
挖掘基于距离的关联规则
? 等宽划分将很近的值分开，并创建没有数据的区间
? 等深划分将很远的值放在一组
? 基于距离的关联规则挖掘考虑属性值的接近性，紧扣区间数据的语义，并允许值的类似
? 基于距离的关联规则挖掘的两遍算法,
? 1,使用聚类找出区间或簇
? 2,搜索频繁的一起出现的簇组，得到基于距离的关联规则
P ric e($ )
Eq ui-w idt h
(w idt h $1 0)
Eq ui-d ep t h
(de pt h 2)
D is t an c e-
ba s ed
7 [ 0,1 0 ] [ 7,2 0 ] [ 7,7 ]
20 [ 1 1,2 0 ] [ 2 2,5 0 ] [ 2 0,2 2 ]
22 [ 2 1,3 0 ] [ 5 1,5 3 ] [ 5 0,5 3 ]
50 [ 3 1,4 0 ]
51 [ 4 1,5 0 ]
53 [ 5 1,6 0 ]
? 因为未考虑数据点之间或区间的相对距离，分箱方法不是总能
紧扣区间数据的语义
关联规则的兴趣度度量
? 客观度量
? 两个流行的度量指标
? 支持度
? 置信度
? 主观度量
? 最终，只有用户才能确定一个规则是否有趣的，而且这种判
断是主观的，因不同的用户而异；通常认为一个规则（模式）
是有趣的，如果,
? 它是出人意料的
? 可行动的（用户可以使用该规则做某些事情）
? 挖掘了关联规则后，哪些规则是用户感兴趣的？强关
联规则是否就是有趣的？
对强关联规则的批评（ 1）
? 例 1,(Aggarwal & Yu,PODS98)
? 在 5000个学生中
? 3000个打篮球
? 3750个喝麦片粥
? 2000个学生既打篮球又喝麦片粥
? 然而，打篮球 => 喝麦片粥 [40%,66.7%]是错误的，因为全部学生
中喝麦片粥的比率是 75%，比打篮球学生的 66.7%要高
? 打篮球 => 不喝麦片粥 [20%,33.3%]这个规则远比上面那个要精确，
尽管支持度和置信度都要低的多
打篮球 不打篮球 合计
喝麦片 2000 1750 3750
不喝麦片 1000 250 1250
合计 3000 2000 5000
对强关联规则的批评（ 2）
? 例 1,(书 P172，表 6-4)
? 上述数据可以得出
buys(X,“computer games”) => buys(X,“videos”) [40%,60%]
? 但其实全部人中购买录像带的人数是 75%，比 60%多；事实
上录像带和游戏是负相关的。
? 由此可见 A => B的置信度有欺骗性，它只是给出 A,B条件概
率的估计，而不度量 A,B间蕴涵的实际强度。
买游戏 不买游戏 合计
买录像 4000 3500 7500
不买录像 2000 500 2500
合计 6000 4000 10000
由关联分析到相关分析
? 我们需要一种度量事件间的相关性或者是依赖性的指标
? 当项集 A的出现独立于项集 B的出现时,P(A∪ B)=P(A)P(B)，即
corrA,B＝ 1，表明 A与 B无关,corrA,B >1表明 A与 B正相关,corrA,B
<1表明 A与 B负相关
? 将相关性指标用于前面的例子，可以得出录像带和游戏将的相关性
为,
? P({game,video})/(P({game})× P({video}))=0.4/(0.75× 0.6)=0.89
? 结论：录像带和游戏之间存在负相关
)(/)|(P ( A ) P ( B ))(,BPABPBAPc o r rBA BA ???间的相关性：和
王 灿
数据挖掘
sjwj@dlc.zju.edu.cn
0703004
大型数据库中的关联规则
挖掘
什么是关联规则挖掘？
? 关联规则挖掘,
? 从事务数据库，关系数据库和其他信息存储中的大
量数据的项集之间发现有趣的、频繁出现的模式、
关联和相关性。
? 应用,
? 购物篮分析、分类设计、捆绑销售等
“尿布与啤酒, ——典型关联分析案例
? 采用关联模型比较典型的案例是“尿布与啤酒”
的故事。在美国，一些年轻的父亲下班后经常
要到超市去买婴儿尿布，超市也因此发现了一
个规律，在购买婴儿尿布的年轻父亲们中，有
30%～ 40%的人同时要买一些啤酒。超市随后
调整了货架的摆放，把尿布和啤酒放在一起，
明显增加了销售额。同样的，我们还可以根据
关联规则在商品销售方面做各种促销活动。
购物篮分析
? 如果问题的全域是商店中所有商品的集合，则对每种
商品都可以用一个布尔量来表示该商品是否被顾客购
买，则每个购物篮都可以用一个布尔向量表示；而通
过分析布尔向量则可以得到商品被频繁关联或被同时
购买的模式，这些模式就可以用关联规则表示
（ 0001001100，这种方法丢失了什么信息？ ）
? 关联规则的两个兴趣度度量
? 支持度
? 置信度
%]60%,2[ s u p
)"",( )"",(
??
?
c o n fid e n c ep o r t
s o ft w a r eXb u y sc o m p u te rXb u y s
关联规则：基本概念
? 给定,
? 项的集合,I={i1,i2,...,in}
? 任务相关数据 D是数据库事务的集合，每个事务 T则
是项的集合，使得
? 每个事务由事务标识符 TID标识；
? A,B为两个项集，事务 T包含 A当且仅当
? 则关联规则是如下蕴涵式,
? 其中 并且,规则 在事
务集 D中成立，并且具有支持度 s和置信度 c
IT ?
TA?
],[ csBA ?
IBIA ??,??? BA BA ?
基本概念 ——示例
? 项的集合 I={A,B,C,D,E,F}
? 每个事务 T由事务标识符 TID标识，它是项的集合
? 比如,TID(2000)={A,B,C}
? 任务相关数据 D是数据库事务的集合
T I D 购买的 it e m
2000 A,B,C
1000 A,C
4000 A,D
5000 B,E,F
规则度量：支持度和置信度
T I D 购买的 it e m
2000 A,B,C
1000 A,C
4000 A,D
5000 B,E,F
Customer
buys diaper
Customer
buys both
Customer
buys beer
? 对所有满足最小支持度和
置信度的关联规则
? 支持度 s是指事务集 D中包
含 的百分比
? 置信度 c是指 D中包含 A的事
务同时也包含 B的百分比
? 假设最小支持度为 50%，
最小置信度为 50%，则有
如下关联规则
? A ? C (50%,66.6%)
? C ? A (50%,100%)
BA?
)( )(s u p BAPBAp o r t ???
)(/)()|( )( APBAPABPBAc o n f i d e n c e ????
大型数据库关联规则挖掘 (1)
? 基本概念
? k－项集,包含 k个项的集合
? {牛奶，面包，黄油 }是个 3－项集
? 项集的频率 是指包含项集的事务数
? 如果项集的频率大于（最小支持度 × D中的事务总
数），则称该项集为 频繁项集
大型数据库关联规则挖掘 (2)
? 大型数据库中的关联规则挖掘包含两个过程,
? 找出所有频繁项集
? 大部分的计算都集中在这一步
? 由频繁项集产生强关联规则
? 即满足最小支持度和最小置信度的规则
关联规则挖掘分类 (1)
? 关联规则有多种分类,
? 根据规则中所处理的值类型
? 布尔关联规则
? 量化关联规则（规则描述的是量化的项或属性间的关联性）
? 根据规则中涉及的数据维
? 单维关联规则
? （仅涉及 buys这个维）
? 多维关联规则
)"",( )"48...42",( )"39...30",( c o m p u t e rXb u y skkXi n c o m eXa g e ??
)"",( )"",( s o f t w a r eXb u y sc o m p u t e rXb u y s ?
s o f t w a r em a n a g e m e n tf i n a n c i a lc o m p u t e r __?
关联规则挖掘分类 (2)
? 根据规则集所涉及的抽象层
? 单层关联规则
? 多层关联规则 （在不同的抽象层发现关联规则）
? 根据关联挖掘的各种扩充
? 挖掘最大的频繁模式（该模式的任何真超模式都是非频繁的）
? 挖掘频繁闭项集（一个项集 c是频繁闭项集，如果不存在其真超
集 c’，使得每个包含 c的事务也包含 c’）
? （最大的频繁模式和频繁闭项集可以用来减少挖掘中产生的频
繁项集）
)"_",( )"39...30",( c o m p u t e rl a p t o pXb u y sXage ?
)"",( )"39...30",( c o m p u t e rXb u y sXa g e ?
由事务数据库挖掘单维布尔关联规则
? 最简单的关联规则挖掘，即单维、单层、布尔关联规
则的挖掘。
T r a n s a ct i o n I D I t e m s B o u g h t
2000 A,B,C
1000 A,C
4000 A,D
5000 B,E,F
F r e q u e n t I te m s e t S u p p o r t
{ A } 75%
{ B } 50%
{ C} 50%
{ A,C} 50%
最小支持度 50%
最小置信度 50%
? 对规则 A ? C,其支持度 =50%
? 置信度
%6.66)(s u p/)(s u p)(/)()|( )( ??????? Ap o r tCAp o r tAPCAPACPCAc o n f i d e n c e
)( )(s u p CAPCAp o r t ???
Apriori算法 (1)
? Apriori算法是挖掘布尔关联规则频繁项集的算法
? Apriori算法利用的是 Apriori性质：频繁项集的所有非
空子集也必须是频繁的。
? 模式不可能比 A更频繁的出现
? Apriori算法是反单调的，即一个集合如果不能通过测试，则
该集合的所有超集也不能通过相同的测试。
? Apriori性质通过减少搜索空间，来提高频繁项集逐层产生的
效率
BA ?
Apriori算法 (2)
? Apriori算法利用频繁项集性质的先验知识
（ prior knowledge），通过逐层搜索的迭代方
法，即将 k-项集用于探察 (k+1)-项集，来穷尽
数据集中的所有频繁项集。
? 先找到频繁 1-项集集合 L1,然后用 L1找到频繁 2-项集
集合 L2，接着用 L2找 L3，直到找不到频繁 k-项集，
找每个 Lk需要一次数据库扫描。
Apriori算法步骤
? Apriori算法由 连接 和 剪枝 两个步骤组成。
? 连接,为了找 Lk，通过 Lk-1与自己连接产生候选 k-项集
的集合，该 候选 k项集 记为 Ck。
? Lk-1中的两个元素 L1和 L2可以执行连接操作 的条件是
? Ck是 Lk的超集，即它的成员可能不是频繁的，但是所
有频繁的 k-项集都在 Ck中（为什么？）。因此可以通
过扫描数据库，通过计算每个 k-项集的支持度来得到
Lk 。
? 为了减少计算量，可以使用 Apriori性质，即如果一个 k-项集
的 (k-1)-子集不在 Lk-1中，则该候选不可能是频繁的，可以直
接从 Ck删除。
])1[]1[(])2[]2[(...])2[]2[(])1[]1[( 21212121 ???????????? klklklklllll
21 ll ??
Apriori算法 ——示例
Database TDB
1st scan
C1 L1
L2
C2 C2
2nd scan
C3 L3 3rd scan
Tid Items
10 A,C,D
20 B,C,E
30 A,B,C,E
40 B,E
Itemset sup
{A} 2
{B} 3
{C} 3
{D} 1
{E} 3
Itemset sup
{A} 2
{B} 3
{C} 3
{E} 3
Itemset
{A,B}
{A,C}
{A,E}
{B,C}
{B,E}
{C,E}
Itemset sup
{A,B} 1
{A,C} 2
{A,E} 1
{B,C} 2
{B,E} 3
{C,E} 2
Itemset sup
{A,C} 2
{B,C} 2
{B,E} 3
{C,E} 2
Itemset
{B,C,E}
Itemset sup
{B,C,E} 2
最小支持计数,2
使用 Apiori性质由 L2产生 C3
? 1,连接,
? C3=L2 L2= {{A,C},{B,C},{B,E}{C,E}}
{{A,C},{B,C},{B,E}{C,E}} = {{A,B,C},{A,C,E},{B,C,E}}
? 2．使用 Apriori性质剪枝：频繁项集的所有子集必须是频繁的，
对候选项 C3，我们可以删除其子集为非频繁的选项,
? {A,B,C}的 2项子集是 {A,B},{A,C},{B,C}，其中 {A,B}不是 L2的元素，
所以删除这个选项；
? {A,C,E}的 2项子集是 {A,C},{A,E},{C,E}，其中 {A,E} 不是 L2的元素，
所以删除这个选项；
? {B,C,E}的 2项子集是 {B,C},{B,E},{C,E}，它的所有 2－项子集都是
L2的元素，因此保留这个选项。
? 3．这样，剪枝后得到 C3={{B,C,E}}
????
由频繁项集产生关联规则
? 同时满足最小支持度和最小置信度的才是强关
联规则，从频繁项集产生的规则都满足支持度
要求，而其置信度则可由一下公式计算,
? 每个关联规则可由如下过程产生,
? 对于每个频繁项集 l，产生 l的所有非空子集；
? 对于每个非空子集 s，如果
则输出规则,”
)(_s u p
)(_s u p)|()(
Ac o u n tp o r t
BAc o u n tp o r tBAPBAc o n fi d e n c e ????
c o n fsc o u n tp o r t lc o u n tp o r t m in _)(_s u p )(_s u p ?
)( sls ??
多层关联规则 (1)
? 数据项中经常会形成
概念分层
? 底层的数据项，其支
持度往往也较低
? 这意味着挖掘底层数据
项之间的关联规则必须
定义不同的支持度
All
Computer
accessory software
laptop financial mouse color
printer computer
desktop
IBM
edu,
Microsoft
b/w
HP Sony
wrist
pad
Logitech
TID Items
T1 {IBM D/C,Sony b/w}
T2 {Ms,edu,Sw.,Ms,fin,Sw.}
T3 {Logi,mouse,Ergoway wrist pad}
T4 {IBM D/C,Ms,Fin,Sw.}
T5 {IBM D/C}
Ergoway
多层关联规则 (2)
? 在适当的等级挖掘出来的数据项间的关联规则
可能是非常有用的
? 通常，事务数据库中的数据也是根据维和概念
分层来进行储存的
? 这为从事务数据库中挖掘不同层次的关联规则提供了
可能。
? 在多个抽象层挖掘关联规则，并在不同的抽象
层进行转化，是数据挖掘系统应该提供的能力
挖掘多层关联规则的方法
? 通常，多层关联规则的挖掘还是使用置信度－支持度
框架，可以采用自顶向下策略
? 请注意：概念分层中，一个节点的支持度肯定不小于该节点
的任何子节点的支持度
? 由概念层 1开始向下，到较低的更特定的概念层，对每个概
念层的频繁项计算累加计数
? 每一层的关联规则挖掘可以使用 Apriori等多种方法
? 例如,
? 先找高层的关联规则,computer -> printer [20%,60%]
? 再找较低层的关联规则,laptop -> color printer [10%,
50%]
多层关联 ——一致支持度
? 一致支持度：对所有层都使用一致的最小支持度
? 优点：搜索时容易采用优化策略，即一个项如果不满足
最小支持度，它的所有子项都可以不用搜索
? 缺点：最小支持度值设置困难
? 太高：将丢掉出现在较低抽象层中有意义的关联规则
? 太低：会在较高层产生太多的无兴趣的规则
多层关联 ——递减支持度
? 使用递减支持度，可以
解决使用一致支持度时
在最小支持度值上设定
的困难
? 递减支持度：在较低层
使用递减的最小支持度
? 每一层都有自己的一个
独立的最小支持度
? 抽象层越低，对应的最
小支持度越小
Computer
[support=10%]
Laptop
[support=6%]
Desktop
[support=4%]
min_sup = 5%
min_sup = 5% 3%
多层关联 ——搜索策略 (1)
? 具有递减支持度的多层关联规则的搜索策略
? 逐层独立：完全的宽度搜索，没有频繁项集的背景知识用于
剪枝
? 层交叉单项过滤：一个第 i层的项被考察，当且仅当它在第
（ i-1）层的父节点是频繁的（ P165,图 6-14）
? (computer)?( laptop computer,desktop computer)
? 层交叉 k项集过滤：一个第 i层的 k项集被考察，当且仅当它在
第 (i-1)层的对应父节点 k-项集是频繁的（ P165,图 6-15）
? (computer,printer)?(( laptop computer,color printer),
(desktop computer,b/w printer) …)
多层关联 ——搜索策略 (2)
? 搜索策略比较
? 逐层独立策略条件松，可能导致底层考察大量非频
繁项
? 层交叉 k项集过滤策略限制太强，仅允许考察频繁 k-
项集的子女
? 层交叉单项过滤策略是上述两者的折中，但仍可能
丢失低层频繁项（图 6-14)
受控的层交叉单项过滤策略
? 层交叉单项过滤策略的改进版本
? 设置一个层传递临界值，用于向较低层传递相对频繁的项。
? 即如果满足层传递临界值，则允许考察不满足最小支持度临界值
的项的子女
? 用户对进一步控制多概念层上的挖掘过程有了更多的灵活性，同
时减少无意义关联的考察和产生
Computer [support=10%]
Laptop [support=6%] Desktop [support=4%]
min_sup = 12%
level_passage_support = 8%
min_sup = 3%
检查冗余的多层关联规则
? 挖掘多层关联规则时，由于项间的“祖先”关系，有
些发现的规则将是冗余的
? 例如,
? desktop computer => b/w printer [sup=8%,con=70%] (1)
? IBM desktop computer => b/w printer [sup=2%,con=72%] (2)
? 上例中，我们说第一个规则是第二个规则的“祖先”
? 如果规则 (2)中的项用它在概念分层中的“祖先”代替，
能得到 (1)，而且 (1)的支持度和置信度都接近“期望”
值，则 (1)是冗余的。
多维关联规则 ——概念
? 单维关联规则,
? buys(X,“milk”) ＝ buys(X,“bread”)
? 多维关联规则：涉及两个或多个维或谓词的关联规则
? 维间关联规则：不包含重复的谓词
? age(X,”19-25”) ∧ occupation(X,“student”) =>
buys(X,“coke”)
? 混合维关联规则：包含某些谓词的多次出现
? age(X,”19-25”) ∧ buys(X,“popcorn”) => buys(X,“coke”)
? 在多维关联规则挖掘中，我们搜索的不是频繁项集，而是频繁谓词集。 k-谓词集是包含 k个合取谓词的集
合。
? 例如,{age,occupation,buys}是一个 3-谓词集
挖掘多维关联规则的技术
? 数据属性可以分为分类属性和量化属性
? 分类属性
? 具有有限个不同值，值之间无序
? 量化属性
? 数值类型的值，并且值之间有一个隐含的序
? 挖掘多维关联规则的技术可以根据量化属性的处理分
为三种基本方法,
? 1,量化属性的静态离散化
? 使用预定义的概念分层对量化属性进行静态地离散化
? 2,量化关联规则
? 根据数据的分布，将量化属性离散化到“箱”
? 3,基于距离的关联规则
? 考虑数据点之间的距离，动态地离散化量化属性
多维关联规则挖掘 ——使用量化属性
的静态离散化
? 量化属性使用预定义的概念分层，在挖掘前
进行离散化
? 数值属性的值用区间代替
? 如果任务相关数据存在关系数据库中，则找
出所有频繁的 k-谓词集将需要 k或 k+1次表扫
描
? 数据立方体技术非常适合挖掘多维关联规则
? n-维方体的单元用于存放对应 n-谓词集的 计
数或支持度, 0-D方体用于存放任务相关数
据的事务总数
? 如果包含感兴趣的维的数据立方体已经存在
并物化，挖掘将会很快，同时可以利用
Apriori性质,频繁谓词集的每个子集也必须
是频繁的
(income) (age)
()
(buys)
(age,income) (age,buys) (income,buys)
(age,income,buys)
挖掘量化关联规则 (1)
? 量化关联规则中，数值属性将根据某种挖掘标准，进
行动态的离散化
? 例如：最大化挖掘规则的置信度和紧凑性
? 为了简化量化关联规则挖掘的讨论，我们将聚焦于类
似以下形式的 2-维量化关联规则, Aquan1 ? Aquan2 ? Acat
? （两个量化属性和一个分类属性间的关联）
? 例如,age(X,”30-39”) ? income(X,”42K - 48K”) ? buys(X,”high
resolution TV”)
挖掘量化关联规则 (2)
? 找出这类 2-维量化关联规则的方
法：关联规则聚类系统 (ARCS)
? 一种源于图像处理的技术，该技
术将量化属性对映射到满足给定
分类属性条件的 2-D栅格上，然
后通过搜索栅格点的聚类而产生
关联规则
关联规则聚类系统 (ARCS) (1)
? ARCS过程中的步骤包括
? 1,分箱（根据不同分箱方法创建一个 2-D数组），本步骤的
目的在于减少量化属性相对应的巨大的值个数，使得 2-D栅
格的大小可控
? 等宽分箱
? 等深分箱
? 基于同质的分箱（每个箱中元组一致分布）
? 2,找出频繁谓词集
? 扫描分箱后形成的 2-D数组，找出满足最小支持度和置信度的频
繁谓词集
关联规则聚类系统 (ARCS) (2)
? 3,关联规则聚类
? 将上一步得到的强关联规则映射到 2-D栅格上，使用聚类算法，扫描栅
格，搜索规则的矩形聚类
)"__",()"40...31",()34,( TVr e s o l u t i o nh i g hXb u y sKKXi n c o m eXage ??
)"__",()"40...31",()35,( TVr e s o l u t i o nh i g hXb u y sKKXi n c o m eXage ??
)"__",()"50...41",()34,( TVr e s o l u t i o nh i g hXb u y sKKXi n c o m eXage ??
)"__",()"50...41",()35,( TVr e s o l u t i o nh i g hXb u y sKKXi n c o m eXage ??
)"__",(
)"50.,,31",()35.,,34,(
TVr e s o l u ti o nh ig hXb u y s
KKXin c o m eXa g e
?
?
ARCS的局限性
? 所挖掘的关联规则左手边只能是量化属性
? 规则的左手边只能有两个量化属性（ 2-D栅格
的限制）
? 一种不基于栅格的，可以发现更一般关联规则
的技术，其中任意个数的量化属性和分类属性
可以出现在规则的两端
? 等深分箱动态划分
? 根据 部分完全性 的度量进行聚类
挖掘基于距离的关联规则
? 等宽划分将很近的值分开，并创建没有数据的区间
? 等深划分将很远的值放在一组
? 基于距离的关联规则挖掘考虑属性值的接近性，紧扣区间数据的语义，并允许值的类似
? 基于距离的关联规则挖掘的两遍算法,
? 1,使用聚类找出区间或簇
? 2,搜索频繁的一起出现的簇组，得到基于距离的关联规则
P ric e($ )
Eq ui-w idt h
(w idt h $1 0)
Eq ui-d ep t h
(de pt h 2)
D is t an c e-
ba s ed
7 [ 0,1 0 ] [ 7,2 0 ] [ 7,7 ]
20 [ 1 1,2 0 ] [ 2 2,5 0 ] [ 2 0,2 2 ]
22 [ 2 1,3 0 ] [ 5 1,5 3 ] [ 5 0,5 3 ]
50 [ 3 1,4 0 ]
51 [ 4 1,5 0 ]
53 [ 5 1,6 0 ]
? 因为未考虑数据点之间或区间的相对距离，分箱方法不是总能
紧扣区间数据的语义
关联规则的兴趣度度量
? 客观度量
? 两个流行的度量指标
? 支持度
? 置信度
? 主观度量
? 最终，只有用户才能确定一个规则是否有趣的，而且这种判
断是主观的，因不同的用户而异；通常认为一个规则（模式）
是有趣的，如果,
? 它是出人意料的
? 可行动的（用户可以使用该规则做某些事情）
? 挖掘了关联规则后，哪些规则是用户感兴趣的？强关
联规则是否就是有趣的？
对强关联规则的批评（ 1）
? 例 1,(Aggarwal & Yu,PODS98)
? 在 5000个学生中
? 3000个打篮球
? 3750个喝麦片粥
? 2000个学生既打篮球又喝麦片粥
? 然而，打篮球 => 喝麦片粥 [40%,66.7%]是错误的，因为全部学生
中喝麦片粥的比率是 75%，比打篮球学生的 66.7%要高
? 打篮球 => 不喝麦片粥 [20%,33.3%]这个规则远比上面那个要精确，
尽管支持度和置信度都要低的多
打篮球 不打篮球 合计
喝麦片 2000 1750 3750
不喝麦片 1000 250 1250
合计 3000 2000 5000
对强关联规则的批评（ 2）
? 例 1,(书 P172，表 6-4)
? 上述数据可以得出
buys(X,“computer games”) => buys(X,“videos”) [40%,60%]
? 但其实全部人中购买录像带的人数是 75%，比 60%多；事实
上录像带和游戏是负相关的。
? 由此可见 A => B的置信度有欺骗性，它只是给出 A,B条件概
率的估计，而不度量 A,B间蕴涵的实际强度。
买游戏 不买游戏 合计
买录像 4000 3500 7500
不买录像 2000 500 2500
合计 6000 4000 10000
由关联分析到相关分析
? 我们需要一种度量事件间的相关性或者是依赖性的指标
? 当项集 A的出现独立于项集 B的出现时,P(A∪ B)=P(A)P(B)，即
corrA,B＝ 1，表明 A与 B无关,corrA,B >1表明 A与 B正相关,corrA,B
<1表明 A与 B负相关
? 将相关性指标用于前面的例子，可以得出录像带和游戏将的相关性
为,
? P({game,video})/(P({game})× P({video}))=0.4/(0.75× 0.6)=0.89
? 结论：录像带和游戏之间存在负相关
)(/)|(P ( A ) P ( B ))(,BPABPBAPc o r rBA BA ???间的相关性：和
