1、第三章第三章 关联规则挖掘理论和算法关联规则挖掘理论和算法 内容提要内容提要n基本概念与解决方法 n经典的频繁项目集生成算法分析 nApriori算法的性能瓶颈问题nApriori的改进算法2022-11-111n关联规则挖掘（Association Rule Mining）是数据挖掘中研究较早而且至今仍活跃的研究方法之一。n最早是由Agrawal等人提出的（1993）。最初提出的动机是针对购物篮分析（Basket Analysis）问题提出的，其目的是为了发现交易数据库（Transaction Database）中不同商品之间的联系规则。n关联规则的挖掘工作成果颇丰。例如，关联规则的挖掘理论
2、、算法设计、算法的性能以及应用推广、并行关联规则挖掘（Parallel Association Rule Mining）以及数量关联规则挖掘（Quantitive Association Rule Mining）等。n关联规则挖掘是数据挖掘的其他研究分支的基础。3.1 基本概念与解决方法2022-11-1123.1 基本概念与解决方法n事务数据库事务数据库n设I=i1，i2，im 是一个项目集合，事务数据库D=t1，t2，tn 是由一系列具有唯一标识TID的事务组成，每个事务ti（i=1，2，n）都对应I上的一个子集。n一个事务数据库可以用来刻画：n购物记录：I是全部物品集合，D是购物清单，每
3、个元组ti是一次购买物品的集合（它当然是I的一个子集）。n其它应用问题2022-11-113支持度与频繁项目集 n定义定义3-13-1（项目集的支持度）（项目集的支持度）.给定一个全局项目集I和数据库D，一个项目集I1I在D上的支持度（Support）是包含I1的事务在D中所占的百分比：support（I1）=|t D|I1 t|/|D|。n定义定义3-23-2（频繁项目集）.给定全局项目集I和数据库D，D中所有满足用户指定的最小支持度（Minsupport）的项目集，即大于或等于minsupport的I的非空子集，称为频繁项目集（频集：Frequent Itemsets）或者大项目集（Lar
4、ge Iitemsets）。在频繁项目集中挑选出所有不被其他元素包含的频繁项目集称为最大频繁项目集（最大频集：Maximum Frequent Itemsets）或最大大项目集（Maximum Large Iitemsets）。2022-11-114可信度与关联规则n定义定义3-33-3（关联规则与可信度）（关联规则与可信度）.给定一个全局项目集I和数据库D，一个定义在I和D上的关联规则形如I1I2，并且它的可信度或信任度或置信度（Confidence）是指包含I1和I2的事务数与包含I1的事务数之比，即Confidence（I1I2）=support（I1I2）/support（I1），其中
5、I1，I2I，I1I2=。n定义定义3-43-4（强关联规则）（强关联规则）.D在I上满足最小支持度和最小信任度（Minconfidence）的关联规则称为强关联规则（Strong Association Rule）。2022-11-115关联规则挖掘基本过程n关联规则挖掘问题可以划分成两个子问题：n1.1.发现频繁项目集发现频繁项目集:通过用户给定Minsupport，寻找所有频繁项目集或者最大频繁项目集。n2 2生成关联规则生成关联规则:通过用户给定Minconfidence，在频繁项目集中，寻找关联规则。n第1个子问题是近年来关联规则挖掘算法研究的重点。2022-11-1163.2 经典
6、的频繁项目集生成算法分析n项目集空间理论n经典的发现频繁项目集算法经典的发现频繁项目集算法n关联规则生成算法关联规则生成算法2022-11-1173.2.1 项目集空间理论 nAgrawal等人建立了用于事务数据库挖掘的项目集格空间理论（1993,Appriori 属性）。n定理定理3-13-1（Appriori 属性1）.如果项目集X 是频繁项目集，那么它的所有非空子集都是频繁项目集。证明 设X是一个项目集，事务数据库T 中支持X 的元组数为s。对X的任一非空子集为Y，设T中支持Y的元组数为s1。根据项目集支持数的定义，很容易知道支持X 的元组一定支持Y，所以s1 s，即support（Y）
7、support（X）。按假设：项目集X 是频繁项目集，即support(X)minsupport，所以support（Y）support（X）minsupport，因此Y是频繁项目集。n定理定理3-23-2（Appriori 属性2）.如果项目集X 是非频繁项目集，那么它的所有超集都是非频繁项目集。证明（略）2022-11-1183.2.2 3.2.2 经典的发现频繁项目集算法经典的发现频繁项目集算法n1994年，Agrawal 等人提出了著名的Apriori 算法。n算法算法3-13-1 Apriori（发现频繁项目集）（1）L1=large 1-itemsets;/所有1-项目频集（2）F
8、OR（k=2;Lk-1;k+）DO BEGIN（3）Ck=apriori-gen（Lk-1）;/Ck是k-候选集（4）FOR all transactions tD DO BEGIN（5）Ct=subset（Ck，t）;/Ct是所有t包含的候选集元素（6）FOR all candidates c Ct DO（7）c.count+;（8）END（9）Lk=cCk|c.countminsup_count（10）END（11）L=Lk;2022-11-119apriori-gen过程n算法apriori中调用了apriori-gen（Lk-1），是为了通过（k-1）-频集产生K-侯选集。nhas_i
9、nfrequent_subset（c，Lk-1），判断c是否加入到k-侯选集中。（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 1）THEN/generate rules with subsets of xm-1 as antecedents（7）genrules（lk，xm-1）;（8）END（9）END；2022-11-1116Rule-generate算法例子nMinconfidence=80%序号lkxm-1confide
10、ncesupport规则（是否是强规则）123523100%50%235（是）2235267%50%235（否）3235367%50%325（否）42352567%50%253（否）5235567%50%523（否）623535100%50%352（是）2022-11-11173.3 Apriori算法的性能瓶颈问题nApriori作为经典的频繁项目集生成算法，在数据挖掘中具有里程碑的作用。nApriori算法有两个致命的性能瓶颈:n1 1多次扫描事务数据库，需要很大的多次扫描事务数据库，需要很大的I/OI/O负载负载n对每次对每次k k循环，侯选集循环，侯选集C Ck k中的每个元素都必须通
11、过扫描中的每个元素都必须通过扫描数据库一次来验证其是否加入数据库一次来验证其是否加入L Lk k。假如有一个频繁大。假如有一个频繁大项目集包含项目集包含1010个项的话，那么就至少需要扫描事务数个项的话，那么就至少需要扫描事务数据库据库1010遍。遍。n2 2可能产生庞大的侯选集可能产生庞大的侯选集n由由L Lk-1k-1产生产生k-k-侯选集侯选集C Ck k是指数增长的，例如是指数增长的，例如10104 4个个1-1-频频繁项目集就有可能产生接近繁项目集就有可能产生接近10107 7个元素的个元素的2-2-侯选集。如侯选集。如此大的侯选集对时间和主存空间都是一种挑战。此大的侯选集对时间和主
12、存空间都是一种挑战。2022-11-11183.4 Apriori的改进算法n基于数据分割的方法基于数据分割的方法n基于散列的方法基于散列的方法2022-11-11193.4 提高Apriori算法效率的技术n一些算法虽然仍然遵循Apriori 属性，但是由于引入了相关技术，在一定程度上改善了Apriori算法适应性和效率。n主要的改进方法有：n基于数据分割（Partition）的方法：基本原理是“在一个划分中的支持度小于最小支持度的k-项集不可能是全局频繁的”。n基于散列（Hash）的方法：基本原理是“在一个hash桶内支持度小于最小支持度的k-项集不可能是全局频繁的”。n基于采样（Samp
13、ling）的方法：基本原理是“通过采样技术，评估被采样的子集中，并依次来估计k-项集的全局频度”。n其他：如，动态删除没有用的事务：“不包含任何Lk的事务对未来的扫描结果不会产生影响，因而可以删除”。2022-11-1120基于数据分割的方法基于数据分割的方法n定理定理3-53-5 设数据集D被分割成分块D1，D2，Dn，全局最小支持数为minsup_count。如果一个数据分块Di 的局部最小支持数minsup_counti（i=1，2，n），按着如下方法生成：minsup_counti=minsup_count*|Di|/|D|则所有的局部频繁项目集涵盖全局频繁项目集。n作用：作用：n1
14、1合理利用主存空间：合理利用主存空间：数据分割将大数据集分成小的块，为块内数据一次性导入主存提供机会。n2 2支持并行挖掘算法：支持并行挖掘算法：每个分块的局部频繁项目集是独立生成的，因此提供了开发并行数据挖掘算法的良好机制。2022-11-1121基于散列的方法基于散列的方法n1995，Park等发现寻找频繁项目集的主要计算是在生成2-频繁项目集上。因此，Park等利用了这个性质引入杂凑技术来改进产生2-频繁项目集的方法。n例子：桶地址桶地址=（10 x+y10 x+y）mod 7mod 7；minsupport_count=3minsupport_count=3 TID Items1 I1
15、，I2，I52 I2，I43 I2，I34 I1，I2，I45 I1，I36 I2，I37 I1，I38 I1，I2，I3，I59 I1，I2，I3桶地址 0 1 2 3 4 5 6桶计数 2 2 4 2 2 4 4桶内 I1，I4 I1，I5 I2，I3 I2，I4 I2，I5 I1，I2 I1，I3 I3，I5 I1，I5 I2，I3 I2，I4 I2，I5 I1，I2 I1，I3 I2，I3 I1，I2 I1，I3 I2，I3 I1，I2 I1，I3L2=I2，I3，I1，I2，I1，I3 2022-11-1122第三章第三章 关联规则挖掘理论和算法关联规则挖掘理论和算法 内容提要内容提
16、要3.5 对项目集格空间理论的发展nCloseClose算法算法nFP-treeFP-tree算法算法2022-11-1123探索新的理论n随着数据库容量的增大，重复访问数据库（外存）将导致性能低下。因此，探索新的理论和算法来减少数据库的扫描次数和侯选集空间占用，已经成为近年来关联规则挖掘研究的热点之一。n两个典型的方法：nClose算法 nFP-tree算法 2022-11-1124CloseClose算法对应的原理算法对应的原理n一个频繁闭合项目集的所有闭合子集一定是频繁的；一个非频繁闭合项目集的所有闭合超集一定是非频繁的。n什么是一个闭合的项目集？n一个项目集C是闭合的，当且仅当对于在C
17、中的任何元素，不可能在C中存在小于或等于它的支持度的子集。n例如，C1=AB3，ABC2是闭合的；C2=AB2，ABC2不是闭合的；2022-11-1125CloseClose算法的例子算法的例子n下面是Close算法作用到表4-1数据集的执行过程（假如minsup_count=3）：n扫描数据库得到L1=(A,3),(B,5),(C,4),(D,3),(E,3)；相应关闭项目集为 Cl(A)=ABC,3，Cl(B)=B,5，Cl(C)=BC,4，Cl(D)=BD,3，Cl(E)=BE,3；nL2=(AB,3),(AC,3),(BC,4),(BD,3),(BE,3)；相应关闭集为C2(AB)=
18、ABC,3；nL3，L4，L5不用测，于是频繁大项集为ABC。样本数据库TIDItemset1 A，B，C，D2B，C，E3A，B，C，E4B，D，E5A，B，C，D2022-11-1126FP-treeFP-tree算法的基本原理算法的基本原理n进行2次数据库扫描：一次对所有1-项目的频度排序；一次将数据库信息转变成紧缩内存结构。n不使用侯选集，直接压缩数据库成一个频繁模式树，通过频繁模式树可以直接得到频集。n基本步骤是：n两次扫描数据库，生成频繁模式树FP-Tree：n扫描数据库一次，得到所有扫描数据库一次，得到所有1-1-项目的频度排序表项目的频度排序表T T；n依照依照T T，再扫描数
19、据库，得到，再扫描数据库，得到FP-TreeFP-Tree。n使用FP-Tree，生成频集：n为为FP-treeFP-tree中的每个节点生成条件模式库；中的每个节点生成条件模式库；n用条件模式库构造对应的条件用条件模式库构造对应的条件FP-treeFP-tree；n递归挖掘条件递归挖掘条件FP-treesFP-trees同时增长其包含的频繁集：同时增长其包含的频繁集：n如果条件FP-tree只包含一个路径，则直接生成所包含的频繁集。2022-11-1127生成频繁模式树FP-Treef:4c:1b:1p:1b:1c:3a:3b:1m:2p:2m:1TItem frequency head f
20、4c4a3b3m3p3min_support=0.5TIDOriginal Items (ordered)frequent items100f,a,c,d,g,i,m,pf,c,a,m,p200a,b,c,f,l,m,of,c,a,b,m300 b,f,h,j,of,b400 b,c,k,s,pc,b,p500 a,f,c,e,l,p,m,nf,c,a,m,p2022-11-1128挖掘频集步骤1：生成条件模式库n为每个节点，寻找它的所有前缀路径并记录其频度，形成CPBCPBitemcond.pattern basecf:3afc:3bfca:1,f:1,c:1mfca:2,fcab:1pfc
21、am:2,cb:1f:4c:1b:1p:1b:1c:3a:3b:1m:2p:2m:1TItem frequency head f4c4a3b3m3p32022-11-1129挖掘频集步骤2：构造C-FP-treen为每一个节点，通过FP-tree构造一个C-FP-treen例如，m节点的C-FP-tree为：m-CPB:fca:2,fcab:1f:3c:3a:3m-conditional FP-treef:4c:1b:1p:1b:1c:3a:3b:1m:2p:2m:1TItem frequency head f4c4a3b3m3p32022-11-1130挖掘频集步骤3：递归构造C-FP-treef:3c:3a:3m-conditional FP-treef:3c:3am-conditional FP-treef:3cm-conditional FP-treef:3cam-conditional FP-tree所有频集：所有频集：m,fm,cm,am,fcm,fam,cam,fcam单路径可以形成频集2022-11-1131
