数据挖掘原理与算法03改

1、2022年2月2日星期三1第三章第三章 关联规则挖掘理论和算法关联规则挖掘理论和算法 内容提要内容提要n基本概念与解决方法 n经典的频繁项目集生成算法分析 nApriori算法的性能瓶颈问题nApriori的改进算法2022-2-22啤酒与尿布的故事说起 n按常规思维，尿布与啤酒风马牛不相及，若不是借助数据挖掘技术对海量交易数据进行挖掘和分析，沃尔玛是不可能发现数据内在这一有价值的规律的。 2022-2-23n在一家超市里，有一个有趣的现象：尿布和啤酒赫然摆在一起出售。但是这个奇怪的举措却使尿布和啤酒的销量双双增加了。这不是一个笑话，而是发生在美国沃尔玛连锁店超市的真实案例，并一直为商家所津津

2、乐道。沃尔玛拥有世界上最大的数据仓库系统，为了能够准确了解顾客在其门店的购买习惯，沃尔玛对其顾客的购物行为进行购物篮分析，想知道顾客经常一起购买的商品有哪些。沃尔玛数据仓库里集中了其各门店的详细原始交易数据。在这些原始交易数据的基础上，沃尔玛利用数据挖掘方法对这些数据进行分析和挖掘。一个意外的发现是：跟尿布一起购买最多的商品竟是啤酒！经过大量实际调查和分析，揭示了一个隐藏在尿布与啤酒背后的美国人的一种行为模式：在美国，一些年轻的父亲下班后经常要到超市去买婴儿尿布，而他们中有30%40%的人同时也为自己买一些啤酒。产生这一现象的原因是：美国的太太们常叮嘱她们的丈夫下班后为小孩买尿布，而丈夫们在买

3、尿布后又随手带回了他们喜欢的啤酒。2022-2-2数据仓库与数据挖掘43.1 概述n关联规则(Association Rule Mining)挖掘是数据挖掘中最活跃的研究方法之一n最早是由R.Agrawal等人提出的n其目的是为了发现超市交易数据库中不同商品之间的关联关系。n一个典型的关联规则的例子是：70%购买了牛奶的顾客将倾向于同时购买面包。n经典的关联规则挖掘算法：Apriori算法和FP-growth算法 2022-2-253.2 引例n假定某超市销售的商品包括：bread、bear、cake、cream、milk和tea 交易号交易号TID顾顾 客客 购购 买买 商商 品品Items

4、T1bread cream milk teaT2bread cream milkT3cake milkT4milk teaT5bread cake milkT6bread teaT7beer milk teaT8bread teaT9bread cream milk teaT10bread milk tea2022-2-2数据仓库与数据挖掘63.2 引例n定义3.1 项目与项集n设I=i1,i2,im是m个不同项目的集合，每个ik(k=1，2，m)称为一个项目(Item)。n项目的集合I称为项目集合(Itemset)，简称为项集。其元素个数称为项集的长度，长度为k的项集称为k-项集(k-Ite

5、mset)。2022-2-2数据仓库与数据挖掘73.2 引例n定义3.2 交易n每笔交易T(Transaction)是项集I上的一个子集，即TI，但通常TI。n对应每一个交易有一个唯一的标识交易号，记作TIDn交易的全体构成了交易数据库D，或称交易记录集D，简称交易集D。n交易集D中包含交易的个数记为|D|。 2022-2-283.2 引例n定义3.3 项集的支持度n对于项集X，XI，设定count(XT)为交易集D中包含X的交易的数量n项集X的支持度support(X)就是项集X出现的概率，从而描述了X的重要性。 |D|T)count(Xsupport(X)2022-2-293.2 引例n定

6、义3.4 项集的最小支持度与频繁集n发现关联规则要求项集必须满足的最小支持阈值，称为项集的最小支持度(Minimum Support)，记为supmin。从统计意义上讲，它表示用户关心的关联规则必须满足的最低重要性。只有满足最小支持度的项集才能产生关联规则。n支持度大于或等于supmin的项集称为频繁项集，简称频繁集，反之则称为非频繁集。通常k-项集如果满足supmin，称为k-频繁集，记作Lk。2022-2-2103.2 引例n定义3.5 关联规则n关联规则(Association Rule)可以表示为一个蕴含式：n R：XY 2022-2-2113.2 引例n定义3.6 关联规则的支持度n

7、对于关联规则R：XY，其中XI,YI，并且XY=，规则R的的支持度(Support)是交易集中同时包含X和Y的交易数与所有交易数之比。 |D|Y)count(XY)support(X2022-2-2123.2 引例n定义3.8 关联规则的最小支持度和最小可信度n关联规则的最小支持度也就是衡量频繁集的最小支持度(Minimum Support)，记为supmin，它用于衡量规则需要满足的最低重要性。规则的最小可信度(Minimum Confidence)记为confmin，它表示关联规则需要满足的最低可靠性。2022-2-2133.2 引例n定义3.7 关联规则的可信度n对于关联规则R：XY，其

8、中XI,YI，并且XY=，规则R的可信度(Confidence)是指包含X和Y的交易数与包含X的交易数之比 support(X)Y)support(XY)(X confidence2022-2-214关联规则的简单例子 2022-2-215n顾客购买记录的数据库D，包含6个事务。项集I=网球拍,网球,运动鞋,羽毛球。考虑关联规则（频繁二项集）：网球拍与网球，事务1,2,3,4,6包含网球拍，事务1,2,6同时包含网球拍和网球，支持度(XY)/D=0.5，置信度(XY)/X=0.6。若给定最小支持度 = 0.5，最小置信度 = 0.6，认为购买网球拍和购买网球之间存在关联。 2022-2-216

9、3.2 引例n定义3.9 强关联规则n如果规则XY满足：s u p p o r t ( X Y ) s u p m i n 且confidence(XY)confmin，称关联规则XY为强关联规则，否则称关联规则XY为弱关联规则。在挖掘关联规则时，产生的关联规则要经过supmin和confmin的衡量，筛选出来的强关联规则才能用于指导商家的决策。2022年2月2日星期三17关联规则挖掘基本过程n关联规则挖掘问题可以划分成两个子问题：n1. 1. 发现频繁项目集发现频繁项目集: :通过用户给定Minsupport ，寻找所有频繁项目集或者最大频繁项目集。n2 2生成关联规则生成关联规则: :通过

10、用户给定Minconfidence ，在频繁项目集中，寻找关联规则。n第1个子问题是近年来关联规则挖掘算法研究的重点。2022年2月2日星期三183.2 经典的频繁项目集生成算法分析n项目集空间理论n经典的发现频繁项目集算法经典的发现频繁项目集算法n关联规则生成算法关联规则生成算法2022年2月2日星期三193.2.1 项目集空间理论 nAgrawal等人建立了用于事务数据库挖掘的项目集格空间理论（1993, Appriori 属性）。n定理定理3-13-1（ Appriori 属性1）. . 如果项目集X 是频繁项目集，那么它的所有非空子集都是频繁项目集。证明 设X是一个项目集，事务数据库T

11、 中支持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是频繁项目集。n定理定理3-23-2（ Appriori 属性2）. .如果项目集X 是非频繁项目集，那么它的所有超集都是非频繁项目集。证明 （略）2022年2月2日星期三203.2.2 3.2.2 经典的发现频繁项目集算法经典的发现频繁项目集算法

12、n1994年，Agrawal 等人提出了著名的Apriori 算法。n算法算法3-13-1 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） Ct=subset（Ck，t）; / Ct是所有t包含的候选集元素（6） FOR all candidates c Ct DO（7） c.count+;（8） END（9） Lk=cCk

13、|c.countminsup_count（10） END（11） L= Lk; 2022年2月2日星期三21apriori-gen过程n算法apriori中调用了apriori-gen（Lk-1），是为了通过（k-1）-频集产生K-侯选集。nhas_infrequent_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

14、 rules with subsets of xm-1 as antecedents（7） genrules（lk， xm-1）;（8） END（9）END； 2022年2月2日星期三28Rule-generate算法例子nMinconfidence=80%序号lkxm-1confidencesupport规则（是否是强规则）123523100%50%235（是）2235267%50%235（否）3235367%50%325（否）42352567%50%253（否）5235567%50%523（否） 623535100%50%352（是）2022年2月2日星期三293.3 Apriori算法的

15、性能瓶颈问题nApriori作为经典的频繁项目集生成算法，在数据挖掘中具有里程碑的作用。nApriori算法有两个致命的性能瓶颈:n1 1多次扫描事务数据库，需要很大的多次扫描事务数据库，需要很大的I/OI/O负载负载n对每次对每次k k循环，侯选集循环，侯选集C Ck k中的每个元素都必须通过扫描中的每个元素都必须通过扫描数据库一次来验证其是否加入数据库一次来验证其是否加入L Lk k。假如有一个频繁大。假如有一个频繁大项目集包含项目集包含1010个项的话，那么就至少需要扫描事务数个项的话，那么就至少需要扫描事务数据库据库1010遍。遍。n2 2可能产生庞大的侯选集可能产生庞大的侯选集n由由

16、L Lk-1k-1产生产生k-k-侯选集侯选集C Ck k是指数增长的，例如是指数增长的，例如10104 4个个1-1-频频繁项目集就有可能产生接近繁项目集就有可能产生接近10107 7个元素的个元素的2-2-侯选集。如侯选集。如此大的侯选集对时间和主存空间都是一种挑战。此大的侯选集对时间和主存空间都是一种挑战。2022年2月2日星期三303.4 Apriori的改进算法n基于数据分割的方法基于数据分割的方法n基于散列的方法基于散列的方法2022年2月2日星期三313.4 提高Apriori算法效率的技术n一些算法虽然仍然遵循Apriori 属性，但是由于引入了相关技术，在一定程度上改善了Ap

17、riori算法适应性和效率。n主要的改进方法有：n基于数据分割（Partition）的方法：基本原理是“在一个划分中的支持度小于最小支持度的k-项集不可能是全局频繁的”。n基于散列（Hash）的方法：基本原理是“在一个hash桶内支持度小于最小支持度的k-项集不可能是全局频繁的”。n基于采样（Sampling）的方法：基本原理是“通过采样技术，评估被采样的子集中，并依次来估计k-项集的全局频度”。n其他：如，动态删除没有用的事务：“不包含任何Lk的事务对未来的扫描结果不会产生影响，因而可以删除”。2022年2月2日星期三32基于数据分割的方法基于数据分割的方法n定理定理3-53-5 设数据集D

18、被分割成分块D1， D2， ， Dn，全局最小支持数为minsup_count。如果一个数据分块Di 的局部最小支持数minsup_counti （i=1，2，n），按着如下方法生成：minsup_counti= minsup_count *|Di| / |D|则所有的局部频繁项目集涵盖全局频繁项目集。n作用：作用：n1 1合理利用主存空间：合理利用主存空间：数据分割将大数据集分成小的块，为块内数据一次性导入主存提供机会。n2 2支持并行挖掘算法：支持并行挖掘算法：每个分块的局部频繁项目集是独立生成的，因此提供了开发并行数据挖掘算法的良好机制。2022年2月2日星期三33基于散列的方法基于散列

19、的方法n1995，Park等发现寻找频繁项目集的主要计算是在生成2-频繁项目集上。因此，Park等利用了这个性质引入杂凑技术来改进产生2-频繁项目集的方法。n例子：桶地址桶地址 =（10 x+y10 x+y）mod 7mod 7；minsupport_count=3minsupport_count=3 TID Items1 I1，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

20、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年2月2日星期三34第三章第三章 关联规则挖掘理论和算法关联规则挖掘理论和算法 内容提要内容提要3.5 对项目集格空间理论的发展nCloseClose算法算法nFP-treeFP-tree算法算法2022年2月2日星期三35探索新的理论n随着数据库容量的增大，重复访问数据库（外存）将导致性能低下。因此，探索新的理论和算法来减少数据库的扫描次数和侯选集

21、空间占用，已经成为近年来关联规则挖掘研究的热点之一。n两个典型的方法：nClose算法 nFP-tree算法 2022年2月2日星期三36CloseClose算法对应的原理算法对应的原理n一个频繁闭合项目集的所有闭合子集一定是频繁的；一个非频繁闭合项目集的所有闭合超集一定是非频繁的。n什么是一个闭合的项目集？n一个项目集C是闭合的，当且仅当对于在C中的任何元素，不可能在C中存在小于或等于它的支持度的子集。n例如，C1=AB3，ABC2是闭合的； C2=AB2，ABC2不是闭合的； 2022年2月2日星期三37CloseClose算法的例子算法的例子n下面是Close算法作用到表4-1数据集的执

22、行过程（假如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)=ABC,3； nL3，L4，L5不用测，于是频繁大项集为ABC 。样本数据库TIDItemset1 A，B，C，D2B，C，E3A，B，C，E4B，D，E5A ， B ， C ， D2022年2月2日星期三38FP

23、-treeFP-tree算法的基本原理算法的基本原理n进行2次数据库扫描：一次对所有1-项目的频度排序；一次将数据库信息转变成紧缩内存结构。n不使用侯选集，直接压缩数据库成一个频繁模式树，通过频繁模式树可以直接得到频集。n基本步骤是：n两次扫描数据库，生成频繁模式树FP-Tree：n扫描数据库一次，得到所有扫描数据库一次，得到所有1-1-项目的频度排序表项目的频度排序表T T；n依照依照T T，再扫描数据库，得到，再扫描数据库，得到FP-TreeFP-Tree。n使用FP-Tree，生成频集：n为为FP-treeFP-tree中的每个节点生成条件模式库；中的每个节点生成条件模式库；n用条件模式库构造对应的条件用条件模式库构造对应的条件FP-treeFP-tree；n递归挖掘条件递归挖掘条件FP-treesFP-trees同时增长其包含的频繁集：同时增长其包含的频繁集：n如果条件FP-tree只包含一个路径，则直接生成所包含的频繁集。 2022年2月2日星期三39生成频繁模式树FP-Treef:4c:1b:1p:1b:1c:3a:3b:1m:2p:2m:1TItem frequency head f4c4a3b3m3p3min_support = 0.5TID