第三章 关联规则挖掘理论和算法
内容提要 基本概念与解决方法 经典的频繁项目集生成算法分析 Apriori算法的性能瓶颈问题 Apriori的改进算法
2012年2月16日星期四
1
3.1 基本概念与解决方法
关联规则挖掘（Association Rule Mining）是数据挖掘中研究较早而 且至今仍活跃的研究方法之一。 最早是由Agrawal等人提出的（1993）。最初提出的动机是针对购物 篮分析（Basket Analysis）问题提出的，其目的是为了发现交易数据 库（Transaction Database）中不同商品之间的联系规则。 关联规则的挖掘工作成果颇丰。例如，关联规则的挖掘理论、算法 设计、算法的性能以及应用推广、并行关联规则挖掘（Parallel Association Rule Mining）以及数量关联规则挖掘（Quantitive Association Rule Mining）等。 关联规则挖掘是数据挖掘的其他研究分支的基础。
（1） （2） （3） （4） （5） （6） （7） （8） （9） （10） （11） L1 = {large 1-itemsets}; //所有1-项目频集 FOR （k=2; Lk-1≠Φ; k++） DO BEGIN Ck=apriori-gen（Lk-1）; // Ck是k-候选集 FOR all transactions t∈D DO BEGIN Ct=subset（Ck，t）; // Ct是所有t包含的候选集元素 FOR all candidates c∈ Ct DO c.count++; END Lk={c∈Ck |c.count≥minsup_count} END L= ∪Lk;
证明 设X是一个项目集，事务数据库T 中支持X 的元组数为s。对X 的任一非空子集为Y，设T中支持Y的元组数为s1。 根据项目集支持数的定义，很容易知道支持X 的元组一定支持Y， 所以s1 ≥s，即support（Y） ≥ support（X）。 按假设：项目集X 是频繁项目集，即support(X)≥ minsupport， 所以support（Y）≥ support（X）≥ minsupport，因此Y是频繁 项目集。□
2012年2月16日星期四
3
支持度与频繁项目集
定义3 定义3-1（项目集的支持度）. 给定一个全局项目集I和数据 项目集的支持度） 库D，一个项目集I1⊆I在D上的支持度（Support）是包含I1 的事务在D中所占的百分比：support（ I1 ）=|| {t∈ D | I1 ⊆t}|| / || D||。 定义3 定义3-2（频繁项目集）.给定全局项目集I和数据库D ，D ） 中所有满足用户指定的最小支持度（Minsupport）的项目 集，即大于或等于minsupport的I的非空子集，称为频繁项 目集（频集：Frequent Itemsets）或者大项目集（Large Iitemsets）。在频繁项目集中挑选出所有不被其他元素包 含的频繁项目集称为最大频繁项目集（最大频集： Maximum Frequent Itemsets）或最大大项目集 （Maximum Large Iitemsets）。
第1个子问题是近年来关联规则挖掘算法研究的重 点。
2012年2月繁项目集生成算法分析
项目集空间理论 经典的发现频繁项目集算法 关联规则生成算法
2012年2月16日星期四
7
3.2.1 项目集空间理论
Agrawal等人建立了用于事务数据库挖掘的项目集格空 间理论（1993, Appriori 属性）。 定理3 定理3-1（ Appriori 属性1）. 如果项目集X 是频繁项目集， ） 那么它的所有非空子集都是频繁项目集。
2012年2月16日星期四
12
例3-1
下表给出一个样本事务数据库，并对它实施Apriori算法。
TID 1 2 3
Itemset A,B,C,D B,C,E A,B,C,E
TID 4 5
Itemset B,D,E A,B,C,D
2012年2月16日星期四
13
Apriori算法例子
Minsupport=40%
算法3-4 从给定的频繁项目集中生成强关联规则 算法3
Rule-generate（L，minconf） （1） FOR each frequent itemset lk in L （2） genrules（ lk ， lk）;
算法3-4的核心是genrules递归过程，它实现一个 频繁项目集中所有强关联规则的生成。
2012年2月16日星期四
16
Rule-generate算法例子
Minconfidence=80%
序号 1 2 3 4 5 6 lk 235 235 235 235 235 235 xm-1 23 2 3 25 5 35 confidence 100% 67% 67% 67% 67% 100% support 50% 50% 50% 50% 50% 50% 规则（是否是强规则） 23 5（是） 2 35（否） 3 25（否） 25 3（否） 5 23（否） 35 2（是）
{1 3} {2 3} {2 5} {3 5} 2 2 3 2
itemset sup {1 2} 1 {1 3} 2 {1 5} 1 {2 3} 2 {2 5} 3 {3 5} 2
C2 itemset {1 2} Scan D
{1 {1 {2 {2 {3 3} 5} 3} 5} 5}
C3 itemset
2012年2月16日星期四
9
apriori-gen过程
算法apriori中调用了apriori-gen（Lk-1），是为了 通过（k-1）-频集产生K-侯选集。
（1） FOR all itemset p∈ Lk-1 DO （2） FOR all itemset q∈Lk-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后 （5） IF has_infrequent_subset（c， Lk-1） THEN （6） delete c;//删除含有非频繁项目子集的侯选元素 （7） ELSE add c to Ck; （8） END （9） Return Ck;
{2 3 5}
2012年2月16日星期四
Scan D
L3 itemset sup {2 3 5} 2
14
3.2.3 关联规则生成算法
根据上面介绍的关联规则挖掘的两个步骤，在得 到了所有频繁项目集后，可以按照下面的步骤生 成关联规则：
对于每一个频繁项目集l，生成其所有的非空子集； 对于l 的每一个非空子集x，计算Conference（x），如 果Confidence（x）≥minconfidence，那么“x （lx）”成立。
2012年2月16日星期四
5
关联规则挖掘基本过程
关联规则挖掘问题可以划分成两个子问题：
发现频繁项目集: 1. 发现频繁项目集:通过用户给定Minsupport ，寻找所 有频繁项目集或者最大频繁项目集。 生成关联规则: 2．生成关联规则:通过用户给定Minconfidence ，在频 繁项目集中，寻找关联规则。
2012年2月16日星期四
4
可信度与关联规则
定义3 定义3-3（关联规则与可信度）.给定一个全局项目 关联规则与可信度） 集I和数据库D，一个定义在I和D上的关联规则形 如I1⇒I2，并且它的可信度或信任度或置信度 （Confidence）是指包含I1和I2的事务数与包含I1的 事务数之比，即 Confidence（I1⇒I2）= support（I1∪I2）/ support（I1）， 其中I1，I2⊆I，I1∩I2=Ф。 定义3 强关联规则） 定义3-4（强关联规则）. D在I上满足最小支持度 和最小信任度（Minconfidence）的关联规则称为 强关联规则（Strong Association Rule）。
定理3-2（ Appriori 属性2）.如果项目集X 是非频繁项目 定理3 ） 集，那么它的所有超集都是非频繁项目集。
证明 （略）
2012年2月16日星期四
8
3.2.2 经典的发现频繁项目集算法
1994年，Agrawal 等人提出了著名的Apriori 算 法。 算法3 算法3-1 Apriori（发现频繁项目集）
has_infrequent_subset（c， Lk-1），判断c是否加入
到k-侯选集中。
2012年2月16日星期四
10
发现算法解决的是关联规则挖掘的第一个问题 关联规则分为布尔关联规则和多值规则 多值关联规则都转化为布尔关联规则来解决，因 此先介绍布尔关联规则算法 Apriori，AprioriTid
2012年2月16日星期四
15
算法算法-递归测试一个频集中的关联规则 算法3-5 递归测试一个频集中的关联规则
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；