数据挖掘原理与算法03

2020年3月17日星期二1第三章关联规则挖掘理论和算法内容提要基本概念与解决方法经典的频繁项目集生成算法分析Apriori算法的性能瓶颈问题Apriori的改进算法2020年3月17日星期二2关联规则挖掘（AssociationRuleMining）是数据挖掘中研究较早而且至今仍活跃的研究方法之一。最早是由Agrawal等人提出的（1993）。最初提出的动机是针对购物篮分析（BasketAnalysis）问题提出的，其目的是为了发现交易数据库（TransactionDatabase）中不同商品之间的联系规则。关联规则的挖掘工作成果颇丰。例如，关联规则的挖掘理论、算法设计、算法的性能以及应用推广、并行关联规则挖掘（ParallelAssociationRuleMining）以及数量关联规则挖掘（QuantitiveAssociationRuleMining）等。关联规则挖掘是数据挖掘的其他研究分支的基础。3.1基本概念与解决方法2020年3月17日星期二33.1基本概念与解决方法事务数据库设I={i1，i2，…，im}是一个项目集合，事务数据库D={t1，t2，…，tn}是由一系列具有唯一标识TID的事务组成，每个事务ti（i=1，2，…，n）都对应I上的一个子集。一个事务数据库可以用来刻画：购物记录：I是全部物品集合，D是购物清单，每个元组ti是一次购买物品的集合（它当然是I的一个子集）。其它应用问题2020年3月17日星期二4支持度与频繁项目集定义3-1（项目集的支持度）.给定一个全局项目集I和数据库D，一个项目集I1I在D上的支持度（Support）是包含I1的事务在D中所占的百分比：support（I1）=||{tD|I1t}||/||D||。定义3-2（频繁项目集）.给定全局项目集I和数据库D，D中所有满足用户指定的最小支持度（Minsupport）的项目集，即大于或等于minsupport的I的非空子集，称为频繁项目集（频集：FrequentItemsets）或者大项目集（LargeIitemsets）。在频繁项目集中挑选出所有不被其他元素包含的频繁项目集称为最大频繁项目集（最大频集：MaximumFrequentItemsets）或最大大项目集（MaximumLargeIitemsets）。2020年3月17日星期二5可信度与关联规则定义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-4（强关联规则）.D在I上满足最小支持度和最小信任度（Minconfidence）的关联规则称为强关联规则（StrongAssociationRule）。2020年3月17日星期二6关联规则挖掘基本过程关联规则挖掘问题可以划分成两个子问题：1.发现频繁项目集:通过用户给定Minsupport，寻找所有频繁项目集或者最大频繁项目集。2．生成关联规则:通过用户给定Minconfidence，在频繁项目集中，寻找关联规则。第1个子问题是近年来关联规则挖掘算法研究的重点。2020年3月17日星期二73.2经典的频繁项目集生成算法分析项目集空间理论经典的发现频繁项目集算法关联规则生成算法2020年3月17日星期二83.2.1项目集空间理论Agrawal等人建立了用于事务数据库挖掘的项目集格空间理论（1993,Appriori属性）。定理3-1（Appriori属性1）.如果项目集X是频繁项目集，那么它的所有非空子集都是频繁项目集。证明设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是频繁项目集。□定理3-2（Appriori属性2）.如果项目集X是非频繁项目集，那么它的所有超集都是非频繁项目集。证明（略）2020年3月17日星期二93.2.2经典的发现频繁项目集算法1994年，Agrawal等人提出了著名的Apriori算法。算法3-1Apriori（发现频繁项目集）（1）L1={large1-itemsets};//所有1-项目频集（2）FOR（k=2;Lk-1;k++）DOBEGIN（3）Ck=apriori-gen（Lk-1）;//Ck是k-候选集（4）FORalltransactionstDDOBEGIN（5）Ct=subset（Ck，t）;//Ct是所有t包含的候选集元素（6）FORallcandidatescCtDO（7）c.count++;（8）END（9）Lk={cCk|c.countminsup_count}（10）END（11）L=Lk;2020年3月17日星期二10apriori-gen过程算法apriori中调用了apriori-gen（Lk-1），是为了通过（k-1）-频集产生K-侯选集。has_infrequent_subset（c，Lk-1），判断c是否加入到k-侯选集中。（1）FORallitemsetpLk-1DO（2）FORallitemsetqLk-1DO（3）IFp.item1=q.item1，…，p.itemk-2=q.itemk-2，p.itemk-1q.itemk-1THENBEGIN（4）c=p∞q;//把q的第k-1个元素连到p后（5）IFhas_infrequent_subset（c，Lk-1）THEN（6）deletec;//删除含有非频繁项目子集的侯选元素（7）ELSEaddctoCk;（8）END（9）ReturnCk;2020年3月17日星期二11发现算法解决的是关联规则挖掘的第一个问题关联规则分为布尔关联规则和多值规则多值关联规则都转化为布尔关联规则来解决，因此先介绍布尔关联规则算法Apriori，AprioriTid2020年3月17日星期二12Apriori算法分析分为第一次遍历和第k次遍历第一次遍历计算每个项目的具体值，确定大项目集1项目集L1第k次遍历利用前一次找到的大项集Lk-1和Apriori-gen函数产生候选集Ck，然后扫描数据库，得到Ck中候选的支持度，剔除了不合格的候选后Ck作为Lk2020年3月17日星期二13例3-1下表给出一个样本事务数据库，并对它实施Apriori算法。TIDItemsetTIDItemset123A,B,C,DB,C,EA,B,C,E45B,D,EA,B,C,D2020年3月17日星期二14Apriori算法例子Minsupport=40%TIDItems100134200235300123540025DatabaseDitemsetsup.{1}2{2}3{3}3{4}1{5}3itemsetsup.{1}2{2}3{3}3{5}3ScanDC1L1itemset{12}{13}{15}{23}{25}{35}itemsetsup{12}1{13}2{15}1{23}2{25}3{35}2itemsetsup{13}2{23}2{25}3{35}2L2C2C2ScanDC3L3itemset{235}ScanDitemsetsup{235}22020年3月17日星期二153.2.3关联规则生成算法根据上面介绍的关联规则挖掘的两个步骤，在得到了所有频繁项目集后，可以按照下面的步骤生成关联规则：对于每一个频繁项目集l，生成其所有的非空子集；对于l的每一个非空子集x，计算Conference（x），如果Confidence（x）≥minconfidence，那么“x（l-x）”成立。算法3-4从给定的频繁项目集中生成强关联规则算法3-4的核心是genrules递归过程，它实现一个频繁项目集中所有强关联规则的生成。Rule-generate（L，minconf）（1）FOReachfrequentitemsetlkinL（2）genrules（lk，lk）;2020年3月17日星期二16算法-递归测试一个频集中的关联规则算法3-5递归测试一个频集中的关联规则genrules（lk:frequentk-itemset，xm:frequentm-itemset）（1）X={（m-1）-itemsetsxm-1|xm-1inxm}；（2）FOReachxm-1inXBEGIN（3）conf=support（lk）/support（xm-1）;（4）IF（conf≥minconf）THENBEGIN（5）printtherule“xm-1（lk-xm-1），withsupport=support（lk），confidence=conf”;（6）IF（m-11）THEN//generateruleswithsubsetsofxm-1asantecedents（7）genrules（lk，xm-1）;（8）END（9）END；2020年3月17日星期二17Rule-generate算法例子Minconfidence=80%序号lkxm-1confidencesupport规则（是否是强规则）123523100%50%235（是）2235267%50%235（否）3235367%50%325（否）42352567%50%253（否）5235567%50%523（否）623535100%50%352（是）2020年3月17日星期二183.3Apriori算法的性能瓶颈问题Apriori作为经典的频繁项目集生成算法，在数据挖掘中具有里程碑的作用。Apriori算法有两个致命的性能瓶颈:1．多次扫描事务数据库，需要很大的I/O负载对每次k循环，侯选集Ck中的每个元素都必须通过扫描数据库一次来验证其是否加入Lk。假如有一个频繁大项目集包含10个项的话，那么就至少需要扫描事务数据库10遍。2．可能产生庞大的侯选集由Lk-1产生k-侯选集Ck是指数增长的，例如104个1-频繁项目集就有可能产生接近107个元素的2-侯选集。如此大的侯选集对时间和主存空间都是一种挑战。2020年3月17日星期二193.4Apriori的改进算法基于数据分割的方法基于散列的方法2020年3月17日星期二203.4提高Apriori算法效率的技术一些算法虽然仍然遵循Apriori属性，但是由于引入了相关技术，在一定程度上改善了Apriori算法适应性和效率。主要的改进方法有：基于数据分割（Partition）的方法：基本原理是“在一个划分中的支持度小于最小支持度的k-项集不可能是全局频繁的”。基于散列（Hash）的方法：基本原理是“在一个hash桶内支持度小于最小支持度的k-项集不可能是全局频繁的”。基于采样（Sampling）的方法：基本原理是“通过采样技术，评估被采样的子集中，并依次来估计k-项集的全局频度”。其他：如，动态删除没有用的事务：“不包含任何Lk的事务对未来的扫描结果不会产生影响，因而可以删除”。2020年3月17日星期二21基于数据分割的方法定理3-5设数据集D被分割成分块D1，D2，…，Dn，全局最小支持数为minsup_count。如果一个数据分块Di的局部最小支持数minsup_counti（i=1，2，…，n），按着如下方法生成：minsup_counti=minsup_count*||Di||/||D||则所有的局部频繁项目集涵盖全局频繁项目集。作用：1．合理利用主存