第八章 关联规则
本章目标
?解释关联规则技术的建模特性。
?分析大型数据库的基本特性。
?描述 Apriori算法，并通过示例来解释算法的
所有步骤。
?将频繁模式增长方法同 Apriori算法进行比较。
?概述从频繁集中产生关联规则的方法。
第八章 关联规则
本章目标
?举例说明使用 HITs,LOGSOM和路径遍历
算法来进行 Web挖掘的可行性。
?在指定提炼和萃取阶段的基础上定型文本
挖掘的构架。
?关联规则是数据挖掘的主要技术之一，
也是在无指导学习系统中挖掘本地模
式的最普遍形式。
?本章除了重点介绍关联规则挖掘的
Apriori技术外，还将讨论一些和 Web
挖掘、文本挖掘相关的数据挖掘方法。
8.1 购物篮分析
?购物篮是顾客在一次事务中所购买项的集
合，所谓事务是一个明确定义的商业行为。
?事务数据库研究的一个最普通的例子就是
寻找项的集合，或叫做项集。包含 i个项的
项集被称为 i-项集。包含该项集的事务的百
分数叫做该项集的支持度。支持度超过指
定阈值的项集叫做频繁项集。
?基本概念,
设 I={i1,i2,…i m}是项的集合,DB为事务集合，
其中每个事务 T是项的集合，且有 。 每一
个事务有一个标识符，称作 TID。 设 X为一个
项集，当且仅当 时，即 T包含 X。关联
规则是形如 的蕴涵式，其中,
,且 。 规则 在事务集
DB中成立，具有支持度 s，其中 s是 DB中事
务包含 X和 Y两者的百分比。规则 在
事务集 DB中具有置信度 c，如果 DB中包含 X
的事务同时也包含 Y的百分比是 c。
YX ?
IT?
TX?
IX?
IX? ??YX ? YX ?
YX ?
?支持度是概率 。
?置信度是概率 。
?置信度可以表示规则的可信性，支持度表示
模式在规则中出现的频率。具有高置信度和
强支持度的规则被称为强规则。
?挖掘关联规则的问题可以分两个阶段,
1.发掘大项集，也就是事务支持度 s大于预
先给定的最小阈值的项的集合。
2.使用大项集来产生数据库中置信度 c大于
预先给定的最小阈值的关联规则。
?Apriori算法是解决这个问题的常用方法。
Y)P (X?
X)|P (Y
8.2 APRIORI算法
?Apriori算法利用几次迭代来计算数据库中的
频繁项集。第 i次迭代计算出所有频繁 i项集
(包含 i个元素的项集 )。每一次迭代有两个步
骤：产生候选集；计算和选择候选集。
?在第一次迭代中，产生的候选集包含所有 1-
项集，并计算其支持度 s,s大于阈值的 1-项
集被选为频繁 1-项集。
?第二次迭代时,Apriori算法首先去除非频繁
1-项集，在频繁 1-项集的基础上进行产生频
繁 2-项集。原理是：如果一个项集是频繁，
那么它的所有子集也是频繁的。
?例如，以表 8-1中的数据为例。假设
smin=50%。
?在第一次迭代的第一步中，所有单项集都
作为候选集，产生一个候选集列表。在下
一步中，计算每一项的支持度，然后在 smin
的基础上选择频繁项集。图 8-1中给出第一
次迭代的结果。
?在挖掘 2-项集时，因为 2-项集的任何子集都
是频繁项集，所以 Apriori算法使用 L1*L1来
产生候选集。 *运算通常定义为,
Lk*Lk={X∪ Y 其中 X,Y∈ Lk,|X∩Y|=k+1}
注,|X∩Y|=k+1即 X和 Y合取容量为 k+1
?当 k=1时，因此,C2包含在第二次迭代中作
为候选集由运算 |L1|·|L1-1|/2所产生的 2-项集。
本例中为,4·3/2=6。 用该列表来扫描 DB，
计算每一个候选集的 s，并与 smin比较 2-项
集 L2。图 8-2给出了所有这些步骤和第二次
迭代的结果。
?候选集 C3 运用 L2*L2来产生，运算结果得到
{A,B,C},{A,C,E},{B,C,E}，但只有 {B,C,E}的
所有子集是频繁项集，成为候选的 3-项集。
然后扫描 DB，并且挖掘出频繁 3-项集，见
图 8-3所示。
?因为本例的 L3无法产生候选的 4-项集，所以
算法停止迭代过程。
?该算法不仅计算所有频繁集的 s，也计
算那些没有被删除的非频繁候选集的 s。
所有非频繁但被算法计算 s的候选项集
的集合被称为负边界。因此，如果项
集非频繁的，但它的子集都是频繁的，
那么它就在负边界之中。
?在本例中，负边界由项集 {D},{A,B},{A,E} 组
成。负边界在一些 Apriori的改进算法中更为
重要，例如生成大项集或导出负关联规则
时提高了有效性。
8.3 从频繁项集得到关联规则
?第二阶段的工作是在第一阶段的基础上，
来挖掘关联规则。如果规则为 {x1,x2,x3}→x 4，
那么项集 {x1,x2,x3,x4}和 {x1,x2,x3}都必须是频
繁的。然后，规则置信度 c=
P({x4}|{x1,x2,x3})=s(x1,x2,x3,x4)/s(x1,x2,x3)。
置信度 c大于给定的阈值的规则就是强规则。
?例如，检验表 8-1DB中的关联规则
{B,C}→{E} 是否为强关联规则。
由图 8-2和图 8-3可得支持度,
s(B,C)=2,s(B,C,E)=2
由支持度得置信度,
c({B,C}→{E})=s(B,C,E)/ s(B,C)=2/2=1(100%)
可见，无论阈值为多少，该规则都能通过，
也就是说，如果事务包含 B和 C，那么它也
将包含 E。
?我们现在有目标是在 DB频繁集中得到所有
的强关联规则。
?请注意,并不是所有的强关联规则都是有用
的或者有意义的。例如，一个谷类早餐的
零售商对 5000名学生的调查的案例。数据
表明,60%的学生打篮球,75%的学生吃
这类早餐,40%的学生即打篮球吃这类早
餐。假设支持度阈值 s=0.4，置信度阈值
c=60%。基于上面数据和假设我们可挖掘
出强关联规则,(打篮球 )→( 吃早餐 )”，因为
其 (打篮球 )和 (吃早餐 )的支持度都大于支持
度阈值，都是频繁项，而规则的置信度
c=40%/60%=66.6%也大于置信度阈值。
?然而，以上的关联规则很容易产生误解，因
为吃早餐的比例为 75%，大于 66%。也就是
说，打篮球与吃早餐实际上是负关联的。
?为了消除这种误导的规则，应该在关联规则
A→B 的置信度超过某个特定的度量标准时，
定义它为有意义的。因此挖掘关联规则的正
确方法是,
s(A,B)/s(A)-s(B)>d
或者,
s(A,B)-s(A) ·s(B)>k
式中 d或 k是适当的常量。（计算上例）
8.4 提高 Apriori算法的效率
?因为挖掘频繁项集时所处理的数据量越来
越大，所以很有必要提高算法的效率。
?Apriori算法扫描 DB的次数完全依赖于最大
的频繁项集中项的数量。为了解决这个问
题，该算法作了一些改进。
?基于划分的 Apriori算法只需要对 DB进行两
次扫描。 DB被划分成若干个非重叠的分区，
分区与内存相匹配。
?在第一次扫描时，算法读取每一个分区，
每个分区内计算局部频繁项集。在第二次
扫描时，算法计算整个 DB中所有局部频繁
集的支持度。 如果项集对于整个数据库来
说是频繁的，那么它至少需要在一个分区
中是频繁的 。因此，第二次扫描完成计算
所有潜在的频繁项集的超集。
?随着数据库大小的增加，取样成为数据挖
掘的一个不可多得的有效途径，基于取样
的算法需要以数据库进行两次扫描。
?第一次扫描，从 DB中选择一个样本，并且
产生一个在整个 DB中很可能为频繁的候选
项集的集合。第二次扫描，算法计算这些
项集的实际支持度和它们的负边界的支持
度。如果在负边界中没有项集是频繁的，
那么说明已挖掘出所有频繁项集。否则，
负边界中的项集的一些超集可能就是频繁
的，但它的支持度还没有计算出来。取样
算法在随后的扫描时，会产生并计算所有
这些潜在有频繁项集。
?图 8-4是实际应用的一个例子，该例揭示这
样一个问题，事务数据库中的购买模式在
最低层上不会显示任何规则，但在一些高
的概念层可能会显示一些有意义的规则。
?Apriori算法的一个扩展在 DB项上涉及到 is-a
层次，它包含数据库结构中已经存在的多
抽象层的信息。 is-a层次定义哪些项是其他
项的一般化或专门化。除了明确列出的项
以外，事务还以分类的方式包含了它们的
祖先，这样就可以发掘出高层次的关系。
8.5 频繁模式增长方法 (FP-增长方法）
?一个 Apriori算法的可伸缩的问题。如果生成
一个长度 100的频繁模式，例如
{a1,a2,…,a 100}，那么所产生的候选集的数
量至少为,
?计算的复杂性成指数增长，这是影响一些
新关联规则挖掘算法发展的一个主要因素。
301 0 01 0 0 10121 0 0 ?????
?
???
?
??
i i
?频繁模式增长 (FP-growth)方法是在大型数
据中挖掘频繁项集的一个有效算法。算法
进行中不存在产生候选集的繁琐过程，当
DB很大时,FP-增长算法首先进行数据库
投影，得到频繁集，然后通过构造一个压
缩的数据库结构 ---FP-树再进行挖掘。
?例如，表 8-3给出 DB，它的最小支持度阈值
为 3。
?第一步，扫描 T，得到频繁集的列表 L,
L={(f,4),(c,4),(a,3),(b,3),(m,3),(p,3)}
按支持度大小递减排列。
?第二步，创建树的根部 (ROOT)，第二次扫
描 T。对第一个事务的扫描得树的第一个分
枝,{(f,1),(c,1),(a,1),(b,1),(m,1),(p,1)}。分枝
中节点的计数 (都是 1)代表了树中该节点项
所出现的次数，并按Ｌ中顺序排列。对第
二个事务，与第一事务有相同项 f,c,a，所有
有同一个前缀 (f,c,a)，得到一个新的分枝
{(f,2),(c,2),(a,2),(b,1),(m,1)}，见图 8-5a。
?其他事务按同样的方式插入到 FP-树中，图
8-5b给出了最后的 FP-树。
?按照频繁项的表 L，整个频繁项的集合被划
分为几个没有重叠的子集,1)含有 p的频繁项
集； 2)含有 m但不含有 p的频繁项集； 3)含
有 b但不含有 m,p的频繁项集； … ； 6)只含
有 f的大项集。
?1)有两个路径 {(f,4),(c,3),(a,3),(m,2),(p,2)}和
{(c,1),(b,1),(p,1)},根据阈值产生新的频繁项
集 (c,p)
?2)有两个路径 {(f,4),(c,3),(a,3),(m,2)}和
{(f,4),(c,3),(a,3),(b,1),(m,1)},满足阈值的频
繁项集是 {f,c,a,m}。
?同样地，我们可得到第三到第六个子集，
再挖出满足阈值的频繁项集。它们是 {f,c,a}
和 {f,c}，但这两个都是 {f,c,a,m}的子集，最
终得到频繁集是 {c.p}和 {f,c,a,m}。
?FP-增长算法要比 Apriori算法大约快一个数
据级。它还增加了一些优化技术，并且在
约束条件下挖掘排序和模式时还存在其他
版本的算法。
本章目标
?解释关联规则技术的建模特性。
?分析大型数据库的基本特性。
?描述 Apriori算法，并通过示例来解释算法的
所有步骤。
?将频繁模式增长方法同 Apriori算法进行比较。
?概述从频繁集中产生关联规则的方法。
第八章 关联规则
本章目标
?举例说明使用 HITs,LOGSOM和路径遍历
算法来进行 Web挖掘的可行性。
?在指定提炼和萃取阶段的基础上定型文本
挖掘的构架。
?关联规则是数据挖掘的主要技术之一，
也是在无指导学习系统中挖掘本地模
式的最普遍形式。
?本章除了重点介绍关联规则挖掘的
Apriori技术外，还将讨论一些和 Web
挖掘、文本挖掘相关的数据挖掘方法。
8.1 购物篮分析
?购物篮是顾客在一次事务中所购买项的集
合，所谓事务是一个明确定义的商业行为。
?事务数据库研究的一个最普通的例子就是
寻找项的集合，或叫做项集。包含 i个项的
项集被称为 i-项集。包含该项集的事务的百
分数叫做该项集的支持度。支持度超过指
定阈值的项集叫做频繁项集。
?基本概念,
设 I={i1,i2,…i m}是项的集合,DB为事务集合，
其中每个事务 T是项的集合，且有 。 每一
个事务有一个标识符，称作 TID。 设 X为一个
项集，当且仅当 时，即 T包含 X。关联
规则是形如 的蕴涵式，其中,
,且 。 规则 在事务集
DB中成立，具有支持度 s，其中 s是 DB中事
务包含 X和 Y两者的百分比。规则 在
事务集 DB中具有置信度 c，如果 DB中包含 X
的事务同时也包含 Y的百分比是 c。
YX ?
IT?
TX?
IX?
IX? ??YX ? YX ?
YX ?
?支持度是概率 。
?置信度是概率 。
?置信度可以表示规则的可信性，支持度表示
模式在规则中出现的频率。具有高置信度和
强支持度的规则被称为强规则。
?挖掘关联规则的问题可以分两个阶段,
1.发掘大项集，也就是事务支持度 s大于预
先给定的最小阈值的项的集合。
2.使用大项集来产生数据库中置信度 c大于
预先给定的最小阈值的关联规则。
?Apriori算法是解决这个问题的常用方法。
Y)P (X?
X)|P (Y
8.2 APRIORI算法
?Apriori算法利用几次迭代来计算数据库中的
频繁项集。第 i次迭代计算出所有频繁 i项集
(包含 i个元素的项集 )。每一次迭代有两个步
骤：产生候选集；计算和选择候选集。
?在第一次迭代中，产生的候选集包含所有 1-
项集，并计算其支持度 s,s大于阈值的 1-项
集被选为频繁 1-项集。
?第二次迭代时,Apriori算法首先去除非频繁
1-项集，在频繁 1-项集的基础上进行产生频
繁 2-项集。原理是：如果一个项集是频繁，
那么它的所有子集也是频繁的。
?例如，以表 8-1中的数据为例。假设
smin=50%。
?在第一次迭代的第一步中，所有单项集都
作为候选集，产生一个候选集列表。在下
一步中，计算每一项的支持度，然后在 smin
的基础上选择频繁项集。图 8-1中给出第一
次迭代的结果。
?在挖掘 2-项集时，因为 2-项集的任何子集都
是频繁项集，所以 Apriori算法使用 L1*L1来
产生候选集。 *运算通常定义为,
Lk*Lk={X∪ Y 其中 X,Y∈ Lk,|X∩Y|=k+1}
注,|X∩Y|=k+1即 X和 Y合取容量为 k+1
?当 k=1时，因此,C2包含在第二次迭代中作
为候选集由运算 |L1|·|L1-1|/2所产生的 2-项集。
本例中为,4·3/2=6。 用该列表来扫描 DB，
计算每一个候选集的 s，并与 smin比较 2-项
集 L2。图 8-2给出了所有这些步骤和第二次
迭代的结果。
?候选集 C3 运用 L2*L2来产生，运算结果得到
{A,B,C},{A,C,E},{B,C,E}，但只有 {B,C,E}的
所有子集是频繁项集，成为候选的 3-项集。
然后扫描 DB，并且挖掘出频繁 3-项集，见
图 8-3所示。
?因为本例的 L3无法产生候选的 4-项集，所以
算法停止迭代过程。
?该算法不仅计算所有频繁集的 s，也计
算那些没有被删除的非频繁候选集的 s。
所有非频繁但被算法计算 s的候选项集
的集合被称为负边界。因此，如果项
集非频繁的，但它的子集都是频繁的，
那么它就在负边界之中。
?在本例中，负边界由项集 {D},{A,B},{A,E} 组
成。负边界在一些 Apriori的改进算法中更为
重要，例如生成大项集或导出负关联规则
时提高了有效性。
8.3 从频繁项集得到关联规则
?第二阶段的工作是在第一阶段的基础上，
来挖掘关联规则。如果规则为 {x1,x2,x3}→x 4，
那么项集 {x1,x2,x3,x4}和 {x1,x2,x3}都必须是频
繁的。然后，规则置信度 c=
P({x4}|{x1,x2,x3})=s(x1,x2,x3,x4)/s(x1,x2,x3)。
置信度 c大于给定的阈值的规则就是强规则。
?例如，检验表 8-1DB中的关联规则
{B,C}→{E} 是否为强关联规则。
由图 8-2和图 8-3可得支持度,
s(B,C)=2,s(B,C,E)=2
由支持度得置信度,
c({B,C}→{E})=s(B,C,E)/ s(B,C)=2/2=1(100%)
可见，无论阈值为多少，该规则都能通过，
也就是说，如果事务包含 B和 C，那么它也
将包含 E。
?我们现在有目标是在 DB频繁集中得到所有
的强关联规则。
?请注意,并不是所有的强关联规则都是有用
的或者有意义的。例如，一个谷类早餐的
零售商对 5000名学生的调查的案例。数据
表明,60%的学生打篮球,75%的学生吃
这类早餐,40%的学生即打篮球吃这类早
餐。假设支持度阈值 s=0.4，置信度阈值
c=60%。基于上面数据和假设我们可挖掘
出强关联规则,(打篮球 )→( 吃早餐 )”，因为
其 (打篮球 )和 (吃早餐 )的支持度都大于支持
度阈值，都是频繁项，而规则的置信度
c=40%/60%=66.6%也大于置信度阈值。
?然而，以上的关联规则很容易产生误解，因
为吃早餐的比例为 75%，大于 66%。也就是
说，打篮球与吃早餐实际上是负关联的。
?为了消除这种误导的规则，应该在关联规则
A→B 的置信度超过某个特定的度量标准时，
定义它为有意义的。因此挖掘关联规则的正
确方法是,
s(A,B)/s(A)-s(B)>d
或者,
s(A,B)-s(A) ·s(B)>k
式中 d或 k是适当的常量。（计算上例）
8.4 提高 Apriori算法的效率
?因为挖掘频繁项集时所处理的数据量越来
越大，所以很有必要提高算法的效率。
?Apriori算法扫描 DB的次数完全依赖于最大
的频繁项集中项的数量。为了解决这个问
题，该算法作了一些改进。
?基于划分的 Apriori算法只需要对 DB进行两
次扫描。 DB被划分成若干个非重叠的分区，
分区与内存相匹配。
?在第一次扫描时，算法读取每一个分区，
每个分区内计算局部频繁项集。在第二次
扫描时，算法计算整个 DB中所有局部频繁
集的支持度。 如果项集对于整个数据库来
说是频繁的，那么它至少需要在一个分区
中是频繁的 。因此，第二次扫描完成计算
所有潜在的频繁项集的超集。
?随着数据库大小的增加，取样成为数据挖
掘的一个不可多得的有效途径，基于取样
的算法需要以数据库进行两次扫描。
?第一次扫描，从 DB中选择一个样本，并且
产生一个在整个 DB中很可能为频繁的候选
项集的集合。第二次扫描，算法计算这些
项集的实际支持度和它们的负边界的支持
度。如果在负边界中没有项集是频繁的，
那么说明已挖掘出所有频繁项集。否则，
负边界中的项集的一些超集可能就是频繁
的，但它的支持度还没有计算出来。取样
算法在随后的扫描时，会产生并计算所有
这些潜在有频繁项集。
?图 8-4是实际应用的一个例子，该例揭示这
样一个问题，事务数据库中的购买模式在
最低层上不会显示任何规则，但在一些高
的概念层可能会显示一些有意义的规则。
?Apriori算法的一个扩展在 DB项上涉及到 is-a
层次，它包含数据库结构中已经存在的多
抽象层的信息。 is-a层次定义哪些项是其他
项的一般化或专门化。除了明确列出的项
以外，事务还以分类的方式包含了它们的
祖先，这样就可以发掘出高层次的关系。
8.5 频繁模式增长方法 (FP-增长方法）
?一个 Apriori算法的可伸缩的问题。如果生成
一个长度 100的频繁模式，例如
{a1,a2,…,a 100}，那么所产生的候选集的数
量至少为,
?计算的复杂性成指数增长，这是影响一些
新关联规则挖掘算法发展的一个主要因素。
301 0 01 0 0 10121 0 0 ?????
?
???
?
??
i i
?频繁模式增长 (FP-growth)方法是在大型数
据中挖掘频繁项集的一个有效算法。算法
进行中不存在产生候选集的繁琐过程，当
DB很大时,FP-增长算法首先进行数据库
投影，得到频繁集，然后通过构造一个压
缩的数据库结构 ---FP-树再进行挖掘。
?例如，表 8-3给出 DB，它的最小支持度阈值
为 3。
?第一步，扫描 T，得到频繁集的列表 L,
L={(f,4),(c,4),(a,3),(b,3),(m,3),(p,3)}
按支持度大小递减排列。
?第二步，创建树的根部 (ROOT)，第二次扫
描 T。对第一个事务的扫描得树的第一个分
枝,{(f,1),(c,1),(a,1),(b,1),(m,1),(p,1)}。分枝
中节点的计数 (都是 1)代表了树中该节点项
所出现的次数，并按Ｌ中顺序排列。对第
二个事务，与第一事务有相同项 f,c,a，所有
有同一个前缀 (f,c,a)，得到一个新的分枝
{(f,2),(c,2),(a,2),(b,1),(m,1)}，见图 8-5a。
?其他事务按同样的方式插入到 FP-树中，图
8-5b给出了最后的 FP-树。
?按照频繁项的表 L，整个频繁项的集合被划
分为几个没有重叠的子集,1)含有 p的频繁项
集； 2)含有 m但不含有 p的频繁项集； 3)含
有 b但不含有 m,p的频繁项集； … ； 6)只含
有 f的大项集。
?1)有两个路径 {(f,4),(c,3),(a,3),(m,2),(p,2)}和
{(c,1),(b,1),(p,1)},根据阈值产生新的频繁项
集 (c,p)
?2)有两个路径 {(f,4),(c,3),(a,3),(m,2)}和
{(f,4),(c,3),(a,3),(b,1),(m,1)},满足阈值的频
繁项集是 {f,c,a,m}。
?同样地，我们可得到第三到第六个子集，
再挖出满足阈值的频繁项集。它们是 {f,c,a}
和 {f,c}，但这两个都是 {f,c,a,m}的子集，最
终得到频繁集是 {c.p}和 {f,c,a,m}。
?FP-增长算法要比 Apriori算法大约快一个数
据级。它还增加了一些优化技术，并且在
约束条件下挖掘排序和模式时还存在其他
版本的算法。
