第3章关联规则挖掘理论和算法(new) 数据挖掘课件_868

support（ I1 ）=|| { t D | I1 t }|| / || D||
定义（频繁项目集） 给定全局项目集I和数据库D ，D中 所有满足用户指定的最小支持度（Minsupport）的项目集， 即大于或等于最小支持度的 I 的非空子集，称为频繁项目 集（Frequent Itemsets）。在频繁项目集中挑选出所有不 被其他元素包含的频繁项目集称为最大频繁项目集 （ Maximum Frequent Itemsets）。
400 2，5
Apriori算法例子
TID Items 100 1 3 4 200 2 3 5 300 1 2 3 5 400 2 5
Database D
Minsupport=50%
C1：1-候选集 C2：2-候选集 C3：3-候选集 C4：4-候选集
L1：1-频繁项目集 L2：2-频繁项目集 L3：3-频繁项目集 L4：4-频繁项目集
Apriori算法是通过项目集元素数目不断增长来完成频繁项 目集发现的。首先产生1_频繁项目集L1，然后产生2_频 繁项目集L2，直到不能再扩展频繁项目集的元素数目为 止。
下面给出一个样本事务数据库，并对它实施Apriori算法。
TID Itemset
100 1，3，4
200
2，3，5
300 1，2，3，5
经典的发现频繁项目集算法
• 1994年，Agrawal 等人提出了著名的Apriori 算法。 • Apriori算法（发现频繁项目集）
（1） L1 = {large 1-itemsets}; //所有1-项目频集 （2） FOR （k=2; Lk-1; k++） DO BEGIN （3） Ck=apriori-gen（Lk-1）; // Ck是k-候选集 （4） FOR all transactions tD DO BEGIN
（5） （6）
IF has_infrequent_subset（c， Lk-1） THEN delete c;//删除含有非频繁项目子集的侯选元素
（7）
ELSE add c to Ck;
（8） END
（9） Return Ck; – has_infrequent_subset（c， Lk-1），判断c是否加入到k-侯选集中。
定义（强关联规则）。D 在 I 上满足最小支持度和最小可 信度的关联规则称为强关联规则。
通常所说的关联规则一般指上面定义的强关联规则。
关联规则挖掘基本过程
• 关联规则挖掘问题就是根据用户指定的最小支持度 和最小可信度来寻找强关联规则。
• 关联规则挖掘问题可以划分成两个子问题：
1.发现频繁项目集:通过用户给定最小支持度，寻找所有频 繁项目集或者最大频繁项目集。
（5） （6） （7）
Ct=subset（Ck，t）; // Ct是所有t包含的候选集元素 FOR all candidates c Ct DO
c.count++;
（8） END
（9） Lk={cCk |c.countminsup_count} （10） END
（11） L= ∪Lk;
Apriori-gen过程
{3}
{2 5} 75%
{3 5}
{5} 75%
{5}
{3 5} 50%
Scan D
Scan D
C源自文库
L4
Ø
4 itemset sup
L3
itemset
C3
itemset {1 2 3}
sup 25%
{1 2 3 5} 25% Scan D {2 3 5} {1 3 5} 25%
L3是最大频繁项目集
{2 3 5} 50%
• 算集法产A生pKri-o侯ri选中集调。用了Apriori-gen(Lk-1)，是为了通过(k-1)-频
（1） FOR all itemset p Lk-1 DO （2） FOR all itemset qLk-1 DO （3） IF p.item1=q.item1， …， p.itemk-2=q.itemk-2， p.itemk-1 < q.itemk-1 THEN BEGIN （4） c= p∞q;//把q的第k-1个元素连到p后
定义（规则的可信度） 一个定义在I和D上的形如 I1I2 的关联规则通过满足一定的可信度(Confidence)来给出。 所谓规则的可信度是指包含 I1 和I2的事务与包含 I1 的事务 之比：
Confidence(I1I2)=|| Support(I1∪I2) / Support(I1) 其中I1 ,I2 I ; I1∩I2=Ø
Scan D
C1 itemset sup.
{1} 50% {2} 75%
L1 itemset {1}
C2
itemset {1 2}
sup 25%
L2 itemset {1 3}
{1 3} 50%
{1 5} 25%
{2 3}
{3} 75%
{2} Scan D {2 3} 50%
{2 5}
{4} 25%
2.生成关联规则:通过用户给定最小可信度，在频繁项目集 中，寻找关联规则。
第1个子问题是近年来关联规则挖掘算法研究的重点。
经典的频繁项目集生成算法分析
项目集格空间理论
Agrawal等人建立了用于事务数据库挖掘的项目集格空间理 论（1993, Appriori 属性）。 其理论核心的原理是： ➢频繁项目集的所有非空子集都是频繁项目集 ➢非频繁项目集的所有超集都是非频繁项目集 （相关定理及其证明略。）
关联规则的生成问题
根据上面介绍的关联规则挖掘的两个步骤，在得到了 所有频繁项目集后，可以按照下面的步骤生成关联规则： – 对于每一个频繁项目集 l ，生成其所有的非空子集； – 对于l 的每一个非空子集x，计算Conference（x），如
果Confidence（x）≥minconfidence，那么“ x(l-x) ” 成立。 • 关联规则生成算法: 从给定的频繁项目集中生成强关联规 则
第三章 关联规则挖掘理论和算法
基本概念与解决方法 经典的频繁项目集生成算法分析 Apriori算法的性能瓶颈问题 Apriori的改进算法 对项目集格空间理论的发展 关联规则挖掘中的一些更深入的问题
支持度、频繁项目集、可信度、强关联规则
定义（项目集的支持度） 给定一个全局项目集I和数据库 D，一个项目集 I1I 在D上的支持度（Support）是包含 I1 的事务在D中所占的百分比：