Apriori算法描述


L1={Large 1-itemsets} //扫描所有事务，计算每项出现次数，产生频繁1-项集集合L1 for (k=2; Lk-1; k++) do //进行迭代循环，根据前一次的Lk-1得到频繁k-项集集合Lk begin Ck’=join(Lkm,Lkn) // join对每两个有k-1个共同项目的长度为k的模式Lkm和Lkn进行连接 Ck =prune(Ck’)// prune根据频繁项集的反单调性，对Ck’进行减枝，得到Ck Ck= apriori-gen(Lk-1) //产生k项候选项集Ck for all transactions tD do //扫描数据库一遍 begin Ct=subset(Ck,t) // 确定每个事务t所含k-候选项集的subset(Ck，t) for all candidates c Ct do c.count++ //对候选项集的计数存放在hash表中 end Lk={c Ct | c.count min_sup} //删除候选项集中小于最小支持度的,得到k-频繁项集Lk end for all subset sLk //对于每个频繁项集Lk，产生Lk的所有非空子集s If conf(s Lk -s )>=min_conf //可信度大于最小可信度的强项集为关联规则 Then Output ( s Lk -s) //由频繁项集产生关联规则 end end //得到所有的关联规则
{I2,I3,I5}
I2,I3→I5 I2,I5→I3
Apriori算法
Apriori性质
频繁项集的所有非空子集都必须也是频繁的。
方法
首先找出所有的频繁1-项集，记为L1；然后利用
L1来产生候选2-项集组成的集合C2，对C2中的2项集进行判定挖掘出频繁2-项集组成的集合L2； 不断如此循环下去直到无法发现更多的频繁k-项 集为止。每挖掘一层Lk就需要扫描整个数据库一 遍。 一个生成的规则是否最终被保留下来，要看它是 否满足评估准则 。
3
2 1 2 4 3 3 2 3 0
30
20 10 20 40 30 30 20 30 0
{I1,I2}
{I1,I3} {I1,I5} {I2,I3} {I2,I4} {I2,I5} {I3,I4} {I3,I5}
3
2 2 4 3 3 2 3
30
20 20 40 30 30 20 30
事务数据库 TID T1 T2 T3 T4 T5 T6 T7 T8 T9 T10 项目列表 事务数据库 I1,I2,I5 I2,I4 I2,I3 I1,I2,I4 I3,I4 I1,I3 I1,I2,I3,I5 I2,I3,I4 I2,I3,I5 I3,I5
Apriori算法生成频繁项集的过程
Lk * Lk {X Y，X与Y Lk , | X Y | K 1}

第2次迭代，产生频繁2-项集
在Apriori算法中，使用L1*L1产生候选项集。“*”运算定
义为： 当k=1时，该运算为单连接。设C2为在第2次迭代中产生 的2-项集。|C2|=|L1|· （|L1|-1）/2。在此例中为： 5· 4/2=10。因此，产生10项候选2-项集C2（产生阶段） 。 然后，计算每一个候选集的出现次数并计算支持度（计 算阶段）。 最后，选择支持度s≥50%的大2-项集L2（选择阶段）。

第二步相对容易些，因为它只需要在已经
找出的频繁项目集的基础上列出所有可能 的关联规则，同时，满足支持度和可信度 阈值要求的规则被认为是有趣的关联规则。 第一个步骤是挖掘关联规则的关键步骤， 挖掘关联规则的总体性能由第一个步骤决 定，因此，所有挖掘关联规则的算法都是 着重于研究第一个步骤。
事务数据库 TID T1 T2 T3 T4 T5 T6 T7 T8 T9 T10 项目列表 事务数据库 I1,I2,I5 I2,I4 I2,I3 I1,I2,I4 I3,I4 I1,I3 I1,I2,I3,I5 I2,I3,I4 I2,I3,I5 I3,I5
候选2项集C2
候选2-项 集
计数 S[%]
“Apriori”节点-------Model选项卡
“Apriori”节点-------Expert选项卡
浏览模型
Setting选项卡
网状图节点---------Web
频繁2-项集L2
计数 S[%]
{I1,I2}
{I1,I3} {I1,I4} {I1,I5} {I2,I3} {I2,I4} {I2,I5} {I3,I4} {I3,I5} {I4,I5}
{I1,I2}
{I1,I3} {I1,I4} {I1,I5} {I2,I3} {I2,I4} {I2,I5} {I3,I4} {I3,I5} {I4,I5}
频繁1-项集为
L1={{牛奶}，{果冻}，{啤酒}，{面包}，{花生酱}}
频繁2-项集为
L2={{牛奶,果冻},{牛奶,啤酒},{牛奶,花生酱},{果冻,
啤酒},{果冻, 面包},{果冻, 花生酱}}
频繁3-项集为
L3={{牛奶,果冻,啤酒},{牛奶,果冻,花生酱}}
关联规则挖掘过程主要包含两个阶段
confidence ( X Y ) P(Y | X )
频繁项集
用户预先定义最小支持度阈值（min_sup）
和最小置信度阈值（min_conf）。 如果某个项集的支持度大于等于设定的最小 支持度阈值min_sup，称这个项集为“频繁 项集”（也称为“大项集”， LargeItemsets），所有的“频繁k-项集”组 成的集合通常记作Lk。
X Y

s, c
X和Y是项集 X称为规则前项（或者前件，antecedent） Y称为规则后项（或者后件，consequent）

支持度s是数据库中包含 X Y 的事务占全部事务的百分比
support( X Y ) P( X Y )

置信度c是包含 X Y 的事务数与包含X的事务数的比值
例子：
Apriori算法生成频繁项集的过程
例：某数据库D中包含有项目{I1}、{I2}、{I3}
、{I4}和{I5}，用户要求的最小支持度阀值 事务数据库 s=20%。
TID T1 T2 T3 T4 T5 T6 T7 T8 T9 T10 项目列表 事务数据库 I1,I2,I5 I2,I4 I2,I3 I1,I2,I4 I3,I4 I1,I3 I1,I2,I3,I5 I2,I3,I4 I2,I3,I5 I3,I5
Apriori算法生成频繁项集的过程

第1次迭代，产生频繁1-项集
产生候选1-项集C1（生成阶段 然后，计算每一个候选集的出现次数并计算支
持度（计算阶段）。 最后，选择支持度s≥20%的项目，生成频繁1项集L1（选择阶段）。
事务数据库 TID T1 T2 T3 T4 T5 T6 T7 T8 T9 T10 项目列表 事务数据库 I1,I2,I5 I2,I4 I2,I3 I1,I2,I4 I3,I4 I1,I3 I1,I2,I3,I5 I2,I3,I4 I2,I3,I5 I3,I5源自第3次迭代，产生大3-项集
候选3-项集C3 {I1,I2,I3} {I1,I2,I5} {I1,I3,I5}
候选3-项集 计数 S[%] {I1,I2,I3} {I1,I2,I5} {I1,I3,I5} 1 2 1 10 20 10
频繁3-项集L3 计数 S[%]
{I1,I2,I5}
2
20
{I2,I3,I4}
5.2.2 在Clementine中应用Apriori算法
利用超市顾客个人信息和他们的一次购买商
品数据为例，讲解Aprioir算法的具体操作。
数据源为 BASKETS.txt ，为文本格式文件。
数据包括两大部分的内容，第一部分是顾客的个
人信息，第二部分是顾客的一次购买商品的信息。
数据源
“Apriori”节点-------Field选项卡
频繁项集 {I1,I2} {I1,I3} {I1,I5} {I2,I3}
产生的规则 I1→I2 I2→I1 I1→I3
置信度 3/4 3/7 2/4
强关联规则 I1→I2
置信度 3/4
I3→I1
I1→I5 I5→I1 I2→I3 I3→I2 {I2,I4} {I2,I5} I2→I4 I4→I2 I2→I5 I5→I2
基本概念



一个样本称为一个“事务” 每个事务由多个属性来确定，这里的属性我们称为“项” 多个项组成的集合称为“项集”
k-项集
由k个项构成的集合
{牛奶}、{啤酒}都是1-项集； {牛奶，果冻}是2-项集； {啤酒，面包，牛奶}是3-项集。
每个事务其实就是一个项集
关联规则的表示
深度优先算法
FP-growth Eclat H-Mine
5.2 Apriori算法
R.Agrawal 等人在 1993 年设计了一个 Apriori 算法 是一种最有影响力的挖掘布尔关联规则频繁项集 的算法。其核心是基于两阶段的频集思想的递推 算法。该关联规则在分类上属于单维、单层、布 尔关联规则。 该算法将关联规则挖掘分解为两个子问题： （1）找出存在于事务数据库中所有的频繁项目集。 即那些支持度大于用户给定支持度阈值的项目集。 （2）在找出的频繁项目集的基础上产生强关联规 则。即产生那些支持度和可信度分别大于或等于 用户给定的支持度和可信度阈值的关联规则。
第5章
关联规则
主要内容
关联规则概述 Apriori算法
序列模式
5.1 关联规则概述
数据关联是数据库中存在的一类重要的可被发现的 知识。若两个或多个变量的取值之间存在某种规律 性，就称为关联。 关联规则挖掘的一个典型例子是购物篮分析。