Ai (i∈{1, …,m}）,Bj(j∈{1, …,n})是属性-值对。
关联规则X Y解释为“满足X中条件的数据库元组
多半也满足Y中条件”。
7
一、关联规则相关知识
例1：给Electionics公司的关系数据库，一个数据挖 掘系统可能发现如下形式的关联规则
age(X,“20…29”) ∧income(X,“20K…29K”)
13
二、Apriori算法及举例
1.连接步：
例： L3={abc, abd, acd, ace, bcd} Self-joining: L3 ⊕ L3
abcd from abc and abd acde from acd and ace
14
二、Apriori算法及举例
2.剪枝步：Ck是Lk的超集，它的成员可以是频繁的， 也可以不是频繁的，但所有的频繁k-项集都包含在 Ck中。
扫描数据库，确定Ck中每个候选k-项集的计数， 将计数值≥最小支持度计数的所有候选k-项集确定 到Lk中。然而，Ck可能很大，这样所涉及到的计算 量就很大。这时使用Apriori性质：如果一个候选 k-项集的（k-1）-项集不在Lk-1中，则该候选也不 可能是频繁的，从而可以从Ck中删除。
15
二、Apriori算法及举例
2.剪枝步：
例： L3={abc, abd, acd, ace, bcd}
Pruning:
acde is removed because ade is not in L3
C4={abcd}
16
二、Apriori算法及举例
例2：设有一个Electronics的事务数据库(如图1示)。 数据库中有9个事务，即｜D｜＝9。Apriori假定事务 中的项按字典次序存放。我们使用图2解释Apriori算 法寻找D中的频繁项集。
算法的基本思想: 使用一种称作逐层搜索的迭代方法，K-项
集用于探索（K＋1）-项集。首先，找出频繁1项集的集合，记为l1。l1用于找频繁2-项集的集 合l2，而l2用于找l3，如此下去，直到不能找到 频繁K-项集LK。找每个LK需要一次数据库扫描。 最后由频繁K－项集可直接产生强关联规则。
11
二、Apriori算法及举例
9Leabharlann 一、关联规则相关知识关联规则的挖掘问题，即发现所有的强关联 规则，即发现所有同时满足最小支持度阈值的最 小置信度值的规则。此过程分为两步： 第一步：识别所有的频繁K-项集，并统计其频率; 第二步：由频繁K-项集产生强关联规则。依据搜
索到的频繁K-项集，导出满足给定阈值 条件的关联规则。
10
二、Apriori算法及举例
Apriori的性质： 任何频繁项集的所有非空子集都必须也是频繁的
例：如果｛啤酒，尿布，坚果｝是一个频繁的， 则其子集｛啤酒，尿布｝、｛啤酒，坚果｝、 ｛尿布，坚果｝都是频繁的。
12
二、Apriori算法及举例
1.连接步：为找LK，通过LK-1与自己连接产生 候选K-项集的集合。该候选K-项集的集合记为 CK，CK中包含2K个可能的项集。从LK-1中取出 f1和f2，fj[j]表示fj的第j项。如果两者的前（k-2） 个项相同(如果f1[1]=f2[1]∧f1[2]=f2[2]∧…∧f1[k2] =f2[k-2]∧f1[k-1] <f2[k-1],则LK-1的元素f1和f2 是可以连接的)，则进行连接f1⊕ f2形成: f1[1] f1 [2]… f1 [k-2] f1 [k-1]f2[k-1]。
5
一、关联规则相关知识
Apriori算法是Agrawal等人于 1994年提出的。
该关联规则在分类上属于单维、 单层、布尔关联规则。
6
一、关联规则相关知识
关联分析就是发现关联规则，这些规则展示属性 -值频繁地在给定数据集中一起出现的条件。关联分 析广泛用于购物篮或事务数据分析。
关联规则是形如X Y， 即“A1∧…∧Am B1∧…∧Bn”规则，其中，
buys(X,“CD_player”)[support=2%,confidence=60%] 1.其中X是变量，代表顾客。 2.所研究的Electronics顾客2%在20-29岁，年收入 20K-29K，并且在Electronics公司购买CD机 (2%:支持
度,如：support(A B)=p(A∪B)) 。
1、Apriori算法及其改进 2、频繁模式增长（FP－增长） 3、多层关联规则挖掘 4、多维关联规则挖掘 5、基于约束的挖掘
3
Apriori算法
内容：
一、关联规则相关知识 二、Apriori算法及举例 三、Apriori算法的改进
4
一、关联规则相关知识
关联规则挖掘的典型例子--购物 篮分析。
该过程通过发现顾客放入其购物 篮中不同商品之间的联系，分析顾客 的购买习惯。通过了解哪些商品频繁 地被同时购买，这各关联的发现可以 帮助零售商制定营销策略。
TID 项ID的列表
T100 L1,L2,L5
T200 L2,L4
T300 L2,L3
T400 L1,L2,L4
T500 L1,L3
T600 L2,L3
T700 L1,L3
T800 L1,L2, L3,L5
T900 L1,L2,L3
（图1）
17
C1
项集
扫描D， 对每个 候选计数
关联规则算法－－Apriori算法
讲课人：王艳兵
1
关联规则的类型：
1、根据规则处理的值的类型，分为布尔的和量化的。 2、根据规则中数据的维，分为单维和多维的。 3、根据规则涉及的抽象层，分为单层和多层的。 4、根据对关联挖掘的不同扩充，关联挖掘可以
扩充为相关分析和最大频繁模式。
2
关联规则挖掘包括：
3.这个年龄和收入组的顾客购买CD机的可能性有60%
（ 60%:置信度, support(A B)=p(B|A)）。
8
一、关联规则相关知识
几个概念：
1.项集：包含K个项的项集称为K-项集。如集合 ｛computer,software｝是一个2-项集。
2.项集的频率：包含项集的事务数，即项集的出 现频率。如果项集的出现频率≥min_sup(最小支 持度阈值) * (事务集D中事务总数)，则该项集满 足最小支持度。如果项集满足最小支持度，则称 它为频繁项集。频繁K-项集的集合通常记作LK。