第三章关联规则挖掘理论和算法1.ppt

文档介绍：第三章关联规则挖掘理论和算法1
可信度与关联规则
定义（关联规则与可信度）.
给定一个全局项目集I和数据库D，一个定义在I和D上的关联规则形如I1I2，并且它的可信度或信任度或置信度（Confidence）-1 < -1 THEN BEGIN
（4） c= p∞q;//把q的第k-1个元素连到p后
（5） IF has_infrequent_subset（c， Lk-1） THEN
（6） delete c;//删除含有非频繁项目子集的侯选元素
（7） ELSE add c to Ck;
（8） END
（9） Return Ck;
14
Chinese Academy of Science
Apriori算法例子
Minsupport=50%（即挑选minsup_count=50%*4=2的项目集）
Database D
Scan D
C1
L2
C2
C2
Scan D
C3
L3
Scan D
L1
15
Chinese Academy of Science
关联规则的生成问题
根据上面介绍的关联规则挖掘的两个步骤，在得到了所有频繁项目集后，可以按照下面的步骤生成关联规则：
对于每一个频繁项目集l，生成其所有的非空子集；
对于l 的每一个非空子集x，计算Conference（x），如果Confidence（x）≥minconfidence，那么“x（l-x）”成立。
16
Chinese Academy of Science
关联规则的生成问题
算法3-4 从给定的频繁项目集中生成强关联规则
算法3-4的核心是genrules递归过程，它实现一个频繁项目集中所有强关联规则的生成。
Rule-generate（L，minconf）
（1） FOR each frequent itemset lk in L
（2） genrules（ lk ， lk）;
17
Chinese Academy of Science
算法-递归测试一个频集中的关联规则
genrules（lk: frequent k-itemset， xm: frequent m-itemset）
（1）X={（m-1）-itemsets xm-1 | xm-1 in xm }；
（2）FOR each xm-1 in X BEGIN
（3） conf = support（lk）/support（xm-1）;
（4） IF （conf ≥minconf） THEN BEGIN
（5） print the rule “xm-1（ lk-xm-1），with support = support（lk）， confidence=conf”;
（6） IF （m-1 > 1） THEN //generate rules with subsets of xm-1 as antecedents
（7） genrules（lk， xm-1）;
（8） END
（9）END；
18
Chinese Academy of Science
Rule-generate算法例子
序号 lk xm-1 confidence support 规则（是否是强规则）
1 235 23 100% 50% 235（是）
2 235 2 67% 50% 235（否）
3 235 3 67% 50% 325（否）
4 235 25 67% 50% 253（否）
5 235 5 67% 50% 523（否）
6 235 35 100% 50% 352（是）
Database D
前面的例子最大频繁项目集为{2 3 5}
conf = support（lk）/support（xm-1）
Minconfidence=80%
19
Chinese Academy of Science
第三章 关联规则挖掘理论和算法
基本概念与解决方法
经典的频繁项目集生成算法分析
Apriori算法的性能瓶颈问题
Apriori的改进算法
对项目集格空间理论的发展
项目集格空间和它的操作
基于项目序列集操作的关联规则挖掘算法
改善关联规则挖掘质量问题
约束数据挖掘问题
关联规则挖掘中的一些更深入的问题

20
Chinese Academy of Scien