《关联规则的增量更新算法研究.docx》由会员分享，可在线阅读，更多相关《关联规则的增量更新算法研究.docx（13页珍藏版）》请在三一文库上搜索。
1、关联规则的增量更新算法研究(1)摘要随着数据库的不断变化，关联规则的增量更新变得尤为重要。为了涟更好的对关联规则进行有效的更新，本文辐对已经提出的经典的关联规则更新算法FUP和IUA算法进行分析，指出其优缺瀹点；最后对另外的改进算法，做一个简单迫的叙述。关键词数据库；关联规则；增量更新关联规则反映了数据库中数据项遣目之间有趣的关联关系，而其中发现频繁项目集是关联规则挖掘应用中的关键技术谫和步骤。关于频繁项目集的挖掘算法研究腱，人们对此进行了大量的工作，其中以R.Agrawal等人提出的Apriori、AprioriTid等算法最具靖有影响力和代表性。而这些算法的提出都骄是在挖掘数据库和最小支持
2、度不变的条件下进行的。但实际中，遇到的情况可能是毹：随着时间的推移，挖掘数据库的规模可廪能不断膨胀或需要删除一部分记录，或者舞需要对最小支持度进行调整从而逐步聚集填到我们感兴趣的频繁项目集上。因而如何若从数据发生变动后的数据库中高效地对已木经推导出的关联规则进行更新，具有非常亠重要的应用价值，这就是所谓的增量式挖缨掘关联规则的问题。1关联规则问题描屿述：设I=i1，i2，.，im苎是m个不同项目的集合，给定一个事务数据库D，其中D每一个事务T是I中一组项目的集合，即TI，T有一个惟一的统标志符TID。如果对于I中的一个子集欷X，有XT，我们就说一个事务T包含X。一条关联规则(associati
3、o扪nrule)就是一个形如X=Y的蕴涵式，其中X，YT，而XY=。关镫联规则成立的条件是：它具有最小支持鬣度s，即事务数据库D中至少有s%的事彤务包含XY；它具有最小可信度c，龄即在事务数据库D中包含X的事务中至少有c%同时也包含Y。给定一个事务集D，挖掘关联规则问题就是产生支持度和可皋信度分别大于用户给定的最小支持度和最小可信度的关联规则，也就是产生强规则菜的问题。关联规则的挖掘问题可以分解为搬以下两个问题：(1)找出事务数据库中妆所有具有用户最小支持度的项目集。具有妇用户指定最小支持度的项目集称为频繁项邹目集，反之称为非频繁项目集。一个项目中所含项目的个数称为该项目的长度。(蠢2)利用频
4、繁项目集生成关联规则。对于睇每一个频繁项目集A，若BA，B，恚且support(A)/suppor入t(B)minconf，则有关联规郫则B=(A-B)。目前大多数的研究主要集中在第一个问题上面。2Apr澍iori核心算法1Agrawal唼等人于1994年提出了一个挖掘顾客交炫易数据库中项集间的关联规则的重要方法熠Apriori算法，其核心是基于两个庖阶段频繁项集思想的递推算法。算法的基命本思想是首先找出所有的频集，这些项集出现的频繁性至少和预定义的最小支持度魂一样。然后由频繁项集产生强关联规则，嫌这些规则必须满足最小支持度和最小可信年度。Apriori核心算法思想简要描述如下：该算法中有两个
5、关键步骤连接步噔和剪枝步。(1)连接步：为找出Lk(竦频繁k一项集)，通过Lk-1与自身连郡接，产生候选k-项集，该候选项集记作圊Ck；其中Lk-1的元素是可连接的。氇(2)剪枝步：Ck是Lk的超集，即它佃的成员可以是也可以不是频繁的，但所有析的频繁一项集都包含在Ck中。扫描数据绻库，确定Ck中每一个候选的计数，从而确定Lk(计数值不小于最小支持度计数遁的所有候选是频繁的，从而属于Lk)。芒然而，Ck可能很大，这样所涉及的计算狼量就很大。为压缩Ck，使用Aprio弧ri性质：任何非频繁的(k-1)-项颗集都不可能是频繁k-项集的子集。因此棘，如果一个候选k-项集的(k-1)项孤集不在Lk中，则
6、该候选项也不可能是频繁的，从而可以由Ck中删除。这种子集瞳测试可以使用所有频繁项集的散列树快速搞完成。这个方法要求多次扫描可能很大的萦交易数据库，即如果频集最多包含10个眦项，那么就需要扫描交易数据库10遍，黍这需要很大的I/O负载。可能产生大量锕的候选集，以及可能需要重复扫描数据库辋，是Apriori算法的两大缺点。3钆关联规则增量更新关联规则反映了数据库中数据项目之间有趣的关联关系，而其颧中发现频繁项目集是关联规则挖掘应用中嘉的关键技术和步骤。关于频繁项目集的挖掘算法研究，人们对此进行了大量的工作次，其中以R.Agrawal等人提出的蘑Apriori、AprioriTid等算法最具有影响力
7、和代表性。而这些算法的提出都是在挖掘数据库和最小支持度兕不变的条件下进行的。实际中，数据库的狮规模随着时间，可能不断膨胀或需要删除循一部分记录，或者需要对最小支持度进行调整从而逐步聚集到我们感兴趣的频繁项氐目集上。因而如何高效地从更新后的数据鲥库中对已经推导出的关联规则进行更新是具有非常重要的价值的，这就是关联规则增量更新问题。广义上的关联规则的更新熵问题就是，在原有数据库DB的基础上，韦对其加上(或减去)数据库db，在新的楷数据库DB+上挖掘新关联规则的问题。概关联规则的增量式更新问题主要有三个：虮在给定的最小支持度和最小置信度下，它当一个新的数据集db添加到旧的数据库脑DB中时，如何生成d
8、bDB中的关联规则；在给定的最小支持度和最小置信度下，当从旧的数据库DB中删除数据集炱db时，如何生成DB-db中的关联规锑则；给定数据库DB，在最小支持度和冠最小置信度发生变化时，如何生成数据库DB中的关联规则。文献2中AgrawalR，和SrikantR提出的西FUP算法是一个与Apriori算法相一致的针对第一个问题的更新算法。文献3中，BrinS，Motwan扎iR，和SilverstEinC提出的FUP2算法是一个同时考虑第一个问苯题与第二个问题的算法。第三类问题则有循冯玉才、冯剑琳提出的算法IUA和PIUA7。下面给出两个比较经典算法：FUP和IUA算法的基本思想，并分霓析了各自的
9、优缺点。FUP算法的基本外思想对任意一个k(k1)项集，若其讣在DB和db中都是频繁项集，则其一定饣是频繁项集；若其在DB和db中都是非孽频繁项集，则其一定是非频繁项集；若其毽仅在DB(db)中是频繁项集，则其支赞持计数应加上其在db(DB)中的支持节数以确定它是否为频繁项集。FUP算法宋假设在DB中发现的频繁项集(n为L中最大元素的元素个数)已被保存下来。它需要对DB和db进行多次扫描，在第一亮次扫描中，算法先扫描db，将L1中的座元素仍为dbDB中的频繁项集的元素燥记入L1，并生成候选频繁1项集C1琐，C1中的元素为db中的频繁1项集且不包含在L1中；然后扫描DB以决定C1中的元素是否为d
10、bDB中的频繁项集，并将是dbDB中的频繁项集的元素记入L1中。在第k(k1)此扫淖描前，先对Lk-1用Apriori湖_Gen函数生成候选频繁k项集Ck，并除去Lk中的元素，即Ck=Ck-L卮k，对Lk进行剪枝，即对于XLk，若存在且YLk-1Lk-1，则柔X肯定不是dbDB中的频繁k项集，应将其在Lk中删除；然后扫描db，将多Lk中的元素仍为dbDB中的频繁项集的元素记入Lk，记录候选频繁k项筱集Ck中的元素在db中的支持数；最后榴扫描DB，记录Ck中的元素在DB中的啵支持数，扫描结束时，将Ck中是dbDB中频繁项集的元素记入Lk中。算吭法在Lk和Ck均为空时结束。性能分析弪FUP算法利用
11、原数据库集DB的挖掘结酣果，即频繁项集L，需要对DB和db进秩行n次扫描(n为L中最大的元素的元素幻个数)，最后得到DBdb中的频繁项术集L，所以FUP算法的效率比使用A勹priori算法和DHP算法重新对d逋bDB进行挖掘的效率要高得多。不过，FUP算法也存在其缺点，虽然它利用此算法利用了原数据库集DB的挖掘结果，但是在对新的数据库进行更新时，又需於要重复的扫描原数据库DB，对候选集进笫行模式匹配，因为原数据库集DB相对增加的数据集db是很大的，所以在利用F刻UP算法对关联规则进行更新时，会消耗镨大量时间处理规模巨大的候选集，浪费了箴时间。IUA3算法基本思想算法马IUA采用了一个独特的候选
12、频繁项集生苓成算法iua_gen，在对每一次对数剿据库DB扫描之前生成较小的候选频繁项菟集，从而提高了算法的效率。它也要求上寂一次对数据库DB进行采掘时发现的频繁弟项集(n为L中最大元素的元素个数)在格本次挖掘时是可使用的。因为人们在发现摈关联规则时，常常需要不断地调整最小支喇持度和最小可信度来聚集到那些真正令其憝感兴趣的关联规则上，因而该算法具有很重要的意义。IUA算法的基本框架也和赓Apriori算法一致，也需要对交易觏数据库DB进行多趟扫描.因为有ss，所以原来所有的频繁k项目集(Lk)淆在新的最小支持度下仍然是频繁k项目集痣，因此在每一趟中扫描交易数据库D计算候选k项目集的支持度计数时
13、，我们就没窀有必要再考虑一遍Lk对应的候选k项目甚集。如果更进一步希望避免又重新生成一嗳遍Lk对应的候选k项目集，我们可以考瘊虑采取以空间换时间的策略，只要在Apriori算法中的每一趟k，保存相应的(Ck-Lk)即可。在第1趟扫描中早，IUA算法只对原来不在L1中的单个碣项目进行支持度计算，并确定出所有新的祛频繁1项目集L1，然后通过L1夔L1得到L1。利用一个频繁项目集的镫任意一个子集必定是频繁项目集这一性质稳，频繁k项集c的每一单个项目i所对应忾的频繁1项集i或者从L1中取，或羊者从L1中取。根据这一特点，IUA唾算法将具有新支持度s的所有频繁k(嫒k2)项目集分成3类：对于其中的震每一
14、个频繁k项目集c=i1，i2，.，ik，Pj(1jk)，懊必有ijL1；对于其中的每一垢个频繁k项目集c=i1，i2，.脖.ik，Pj(1jk)，必有ijL1；对于其中的每一个频嗜繁k项目集c=i1，i2，.ik，必有两个非空子集c1和c2，使轴得c1c2=c，c1c2=，而且c1我们将所有第类频繁k项目集构卮成的集合记为L1k，第类记为L2k醯，第类记为L3k.同时与之相对应的候选k项目集构成的集合分别记为C1k钺，C2k，C3k.对于C1k，C2k直接利用Apriori算法分析：算法碌中的apriori-gen函数生成；珂对于C3k通过Lj1和Lk-22拼接修剪而成，j从1迭代到k-1。I
15、UA叶也是采用Apriori框架。IUA在旮自底向上的搜索过程中，依据第k层频繁馕项目集来生成第k+1层所有候选频繁项目集，然后对各候选频繁项目集进行支持彬度计算，从而获得第k+1层所有频繁项目集，直到某层候选项目集为空为止。性能分析：(1)IUA算法与Aprio贤ri算法一样，主要是利用了“一个频繁底项目集的任一非空子集必定也是频繁项目果集”这一性质。根据这一性质可知，对于蔑任一项目i，如果i不是任一j(j7汪，每调用一次iua_gen函数，通愁过该函数的拼接将会使一些已明显不是频逄繁k-项目集的k-项目集成为候选k-项目集C3k中的元素，从而给iua_袢gen函数中的修剪增加运算量，增加了
16、蘖算法的时间复杂性。(2)IUA算法在軎关联规则更新时，对k-项目集的开采，箝只是注意到利用已存在的频繁k-项目集溲的集合Lk，没有注意到基于“一个频繁轿项目集的任一非空子集必定也是频繁项目窜集”性质的在本次更新时，对新产生的频锕繁(k-1)-项目集的集合Lk-1射加以利用。由于IUA充分利用已挖掘的结果及采用有效的候选频繁项目集生成方裂法，并且采取以空间换时间的策略，这样驸以来就显著地减少了各层候选频繁项目集沸数目，有效地提高了关联规则的更新效率绡.但IUA受Apriori框架的局限，主要存在着以下不足：多遍扫描数据谔库，扫描次数取决于新增最大频繁项目集蔺的长度；需产生大量的候选项目集。搽其
17、它算法还有一些关联规则更新算法，也俊都以IUA算法或者以FUP算法为基础氵，在此算法的基础上进行分析，在某一方面进行改进，从而提出了一些效率相对更高改造方法，以IUA算法为基础的，例如：宋海生的UA算法10，皋军等提出的My_IUA算法11，周海榫岩提出的NEWIUA算法等；还有以F渊UP算法为基础的，例如李宝东，宋翰涛晾的EFUP算法8，朱全玉，汪晓刚薏的NEWFUP算法9等。下面简单介绍两种。1)NEWIUA算法NEW槽IUA算法的基本框架与IUA算法和A茂priori算法一致，对k=1，2，蹋，m，采用某种策略生成候选k-项目集Ck，然后扫描数据库来确定Ck中那嶷些k-项目集是频繁项目集
18、。NEWIU腻A算法与传统的增量式更新算法不同之处俑主要体现在以下两点：因为有sN橥EWIUA算法在生成候选k-项目集Ck时，不但利用了已经存在的频繁k-项删目集的集合Lk，而且注意到，基于对本去次更新时新产生的频繁k-1-项目集L荮k-1加以充分利用。与IUA算法相袢比，NEWIUA算法很好地利用了ap巡riori-gen函数，不过重复对原来Lk-1的处理，所以算法NEWIU袢A与重新运行Apriori算法相比，忻效率上只是有限地提高。2)EFUP算鄯法EFUP算法的基本思想与FUP算法啦类似，区别是：FUP算法利用原数据库桊集DB的挖掘结果，即频繁项集L，需要啭对DB和db进行n次扫描(n
19、为L中最斗大的元素的元素个数)，最后得到DBdb中的频繁项集L；而EFUP算法只需对DB进行一次扫描，对db同样进栲行n次扫描。因为DB一般远大于db因蕤此对于大数据集，EFUP算法可以通过聿较少对DB的I/O操作来提高效率。对毹db采用类似于Apriori的算法，一方面验证L中的元素是否为dbDB绁中的频繁项集，另一方面生成其中的频繁聍项集Ldb，然后对DB进行一次扫描，螨验证Ldb中的元素是否为dbDB中的频繁项集。但EFUP算法的前提是已功知元数据库DB中的频繁项集和其中元素郧的支持数。总结：现在一些算法有的存在曦频繁项集的遗漏问题，有的产生较多的候润选项集，有的占用较大的空间，例如文献
20、81213。在文献8中所提到的算法可能会造成频繁项集的遗菪漏问题。在文献12中所提到的算法玛可能会造成在扫描db时侯选频繁项集的惬增加而降低挖掘的效率。在文献13扰中所提到的算法虽然简单，但是却没有充鹬分利用LDB中可以确定为非频繁项集的茴项集，在Apriori算法对db进行扫描产生侯选集Ldb的过程中进行更有雕效的剪枝；并且若新增的数据库db所产辇生的局部频繁项集与原频繁都较大且大部分是相同集时，整个过程中空间的浪费也槛较大。因此提出高效的更新算法是当务之侏急。负关联规则的增量式更新传统的关联鍪规则用于挖掘顾客事务数据库中项集间的卦关联关系，而传统的关联规则挖掘算法仅庇能用来发现强模式，即那
21、些具有高频率和鸠强相关的显式。实际上数据库中还存在着许多采用目前挖掘技术所不能发现的隐式莆模式，这些重要的隐士模式之一便是负关力联规则，即两件事情很少同时出现，但却低具有较高的相关度，它具有低频率、强相引关的性质，表现了数据项目集间的不容易痉直接观察到的强相关性质，这些隐式规则告诉我们哪些数据项目较少的一起发生，揞但它们却包含了非常有价值的信息，因此发现负关联规则具有十分重要的意义。几雩乎大部分的关联规则挖掘及其算法都只是炼涉及到项集间的关联规则，即正关联规则漆，例如“买了尿布的顾客也可能买啤酒”哜这样的规则。可是形如“买了牛奶的顾客彗可能不买咖啡”这样的负关联规则，在实际中可以和正关联规则一
22、样提供有价值的欤信息。例如，负关联规则可以帮助市场监督部门在众多的非公平交易的警报信号中樾判断哪些是可以忽略的；企业可以通过综罐合考虑正、负关联规则从而抓住更多的商蝙机。实际上，负关联规则的增量更新与关畏联规则的增量更新类似，都是在更新后的蜡数据库中挖掘负关联规则。但目前对负关联规则增量更新的研究还处于初始阶段，纲在以后的学习与研究中，将重点研究负关庆联规则的增量更新这方面的知识。4结惝束语本文首先提出了关联规则的经典Ap獯riori算法，并分析了该算法的优点以及存在的不足，接着引入了关联规则的垫相关知识，并着重讨论关联规则的更新算法，重点对FUP与IUA算法进行分析蘧与总结，最后又简单介绍了
23、两种好的改进妒算法，希望以后对负关联规则的增量式更聃新的研究有所帮助。参考文献1AgrawalR，ImielinskiT绝，SwamIA.Miningasso猴ciationrulesbetweensetsofitemsinlargedatabaseA.Proce瘁edingofthe1993ACMS歌IGMODInternational荑ConferenceonManagementofDataC.NewY渍ork：ACMPress，1993.207-2162AgrawalR刖，SrikantR.Fastalgorithmsforminingass塥ociationrulesinlar呼ged
24、atabaseA.Proc唯eedingsofthe1994InternationalConfere蔗nceonVLDBC.SanFr牾ancisco：MorganKauf蘧mannPublishers，199岗4.487-4993BrinS，槿MotwaniR，SilverstEinC.Beyondmarket：G缮eneralizingassocia垭tionrulestocorrela嘉tionsA.ProcessingoftheACMSIGMODCon鳋ference1997C.New蛑York：ACMPress，1997鲫.265-2764WuXindo砧ng，ZhangChengq
25、i，Zh汶angShichao.Miningb觜othpositiveandnegativeassociationrul檐esA.Proceedingso鸳fthe19thInternatio嶙nalConferenceonMat莱chineLearning(ICML黎22002)C.SanFranc葱isco：MorganKaufman也nPublishers，2002.6臃58-6655范明，孟小峰等.数据挖掘概念与技术M.机械工业出版给社，2001.86and，FastAlgorithmsforMini蔺ngAssociationRules举inLargeDatabases，InRese
26、archReportRJ崭9839，IBMAlmadenRes砉earchCenter，SanJos靼e，California，1994湖7冯玉才、冯剑琳，关联规则的增量式更新算法J.软件学报，1998，刨48李宝东、宋翰宗，关联规则增量更新算法研究J.计算机工程与应用鲮，2002，239朱玉全，汪晓刚导，一种新的关联规则增量式更新算法J滟.计算机工程，2002，28(4)堇，25-2710宋海生，关联规则的增量式更新算法J.兰州大学学报娠，XX，40(2)11皋军，王建慑东，关联规则挖掘算法更新与拓展J螗.计算机工程与应用，XX，3512李雄飞等.二次挖掘相联规则算法J.吉林大学学报，2002，32(2)：73-7713陈劲松等.一种鲕增量更新算法J.计算机工程，20距02.7，28(7)：10610713/13