关联规则的增量更新算法研究

1、关联规矩的增量更新算法研究摘要随着数据库的不竭变革，关联规矩的增量更新变得尤为紧张。为了更好的对关联规矩举行有效的更新，本文对已经提出的经典的关联规矩更新算法FUP和IUA算法举行阐发，指出其优缺点；末了对别的的革新算法，做一个简朴的表达。关键词数据库；关联规矩；增量更新关联规矩反响了数据库中数据工程之间幽默的关联干系，而此中创造频仍工程集是关联规矩开掘应用中的关键技能和步调。关于频仍工程集的开掘算法研究，人们对此举行了大量的事变，此中以R.Agraal等人提出的Apriri、ApririTid等算法最具有影响力和代表性。而这些算法的提出都是在开掘数据库和最小支持度稳定的条件下举行的。但现实中

2、，碰到的环境大概是：随着时间的推移，开掘数据库的范围大概不竭膨胀或必要删除一局部记载，大概必要对最小支持度举行调解从而渐渐聚拢到我们感爱好的频仍工程集上。因此怎样从数据产生变更后的数据库中高效地对已经推导出的关联规矩举行更新，具有非常紧张的应用代价，这就是所谓的增量式开掘关联规矩的题目。题目形貌：设I=i1，i2，.，i是个差异工程标聚拢，给定一个事件数据库D，此中D每一个事件T是I中一组工程标聚拢，即TI，T有一个惟一的标记符TID。假设对付I中的一个子集X，有XT，我们就说一个事件T包罗X。一条关联规矩(assiatinrule)就是一个形如X=Y的蕴涵式，此中X，YT，而XY=。关联规矩

3、建立的条件是：它具有最小支持度s，即事件数据库D中至少有s%的事件包罗XY；它具有最小可信度，即在事件数据库D中包罗X的事件中至少有%同时也包罗Y。给定一个事件集D，开掘关联规矩题目就是产生支持度和可信度别离大于用户给定的最小支持度和最小可信度的关联规矩，也就是产生强规矩的题目。关联规矩的开掘题目可以剖析为以下两个题目：(1)寻失事件数据库中全部具有效户最小支持度的工程集。具有效户指定最小支持度的工程集称为频仍工程集，反之称为非频仍工程集。一个工程中所含工程标个数称为该工程标长度。(2)利用频仍工程集天生关联规矩。对付每一个频仍工程集A，假设BA，B，且supprt(A)/supprt(B)i

4、nnf，那么有关联规矩B=(A-B)。如今大多数的研究重要会合在第一个题目上面。Agraal等人于1994年提出了一个开掘主顾生意业务数据库中项集间的关联规矩的紧张要领Apriri算法，其焦点是基于两个阶段频仍项集头脑的递推算法。算法的根本头脑是起首寻出全部的频集，这些项集出现的频仍性至少和预界说的最小支持度一样。然后由频仍项集产生强关联规矩，这些规矩必需满意最小支持度和最小可信度。Apriri焦点算法头脑扼要形貌如下：该算法中有两个关键步调毗连步和剪枝步。(1)毗连步：为寻出Lk(频仍k一项集)，通过Lk-1与自身毗连，产生候选k-项集，该候选项集记作k；此中Lk-1的元素是可毗连的。(2)

5、剪枝步：k是Lk的超集，即它的成员可以是也可以不是频仍的，但全部的频仍一项集都包罗在k中。扫描数据库，确定k中每一个候选的计数，从而确定Lk(计数值不小于最小支持度计数的全部候选是频仍的，从而属于Lk)。然而，k大概很大，如许所涉及的盘算量就很大。为压缩k，利用Apriri性子：任何非频仍的(k-1)-项集都不成能是频仍k-项集的子集。因此，假设一个候选k-项集的(k-1)项集不在Lk中，那么该候选项也不成能是频仍的，从而可以由k中删除。这种子集测试可以利用全部频仍项集的散列树快速完成。这个要领要求屡次扫描大概很大的生意业务数据库，即假设频集最多包罗10个项，那么就必要扫描生意业务数据库10遍

6、，这必要很大的I/负载。大概产生大量的候选集，以及大概必要重复扫描数据库，是Apriri算法的两大缺点。关联规矩反响了数据库中数据工程之间幽默的关联干系，而此中创造频仍工程集是关联规矩开掘应用中的关键技能和步调。关于频仍工程集的开掘算法研究，人们对此举行了大量的事变，此中以R.Agraal等人提出的Apriri、ApririTid等算法最具有影响力和代表性。而这些算法的提出都是在开掘数据库和最小支持度稳定的条件下举行的。现实中，数据库的范围随着时间，大概不竭膨胀或必要删除一局部记载，大概必要对最小支持度举行调解从而渐渐聚拢到我们感爱好的频仍工程集上。因此怎样高效地从更新后的数据库中对已经推导出

7、的关联规矩举行更新是具有非常紧张的代价的，这就是关联规矩增量更新题目。广义上的关联规矩的更新题目就是，在原有数据库DB的底子上，对其加上(或减去)数据库db，在新的数据库DB+上开掘新关联规矩的题目。关联规矩的增量式更新题目重要有三个：在给定的最小支持度和最小置信度下，当一个新的数据集db添加到旧的数据库DB中时，怎样天生dbDB中的关联规矩；在给定的最小支持度和最小置信度下，当从旧的数据库DB中删除数据集db时，怎样天生DB-db中的关联规矩；给定命据库DB，在最小支持度和最小置信度产生变革时，怎样天生数据库DB中的关联规矩。文献2中AgraalR，和SrikantR提出的FUP算法是一个与

8、Apriri算法一样等的针对第一个题目的更新算法。文献3中，BrinS，taniR，和SilverstEin提出的FUP2算法是一个同时思量第一个题目与第二个题目的算法。第三类题目那么有冯玉才、冯剑琳提出的算法IUA和PIUA7。下面给出两个比力经典算法：FUP和IUA算法的根本头脑，并阐发了各自的优缺点。3.1FUP算法的根本头脑对恣意一个k(k1)项集，假设其在DB和db中都是频仍项集，那么其必然是频仍项集；假设其在DB和db中都黑白频仍项集，那么其必然黑白频仍项集；假设其仅在DB(db)中是频仍项集，那么其支持计数应加上其在db(DB)中的支持数以确定它是否为频仍项集。FUP算法假设在D

9、B中创造的频仍项集(n为L中最大元素的元素个数)已被保存下来。它必要对DB和db举行屡次扫描，在第一次扫描中，算法先扫描db，将L1中的元素仍为dbDB中的频仍项集的元素记入L1，并天生候选频仍1项集1，1中的元素为db中的频仍1项集且不包罗在L1中；然后扫描DB以决定1中的元素是否为dbDB中的频仍项集，并将是dbDB中的频仍项集的元素记入L1中。在第k(k1)此扫描前，先对Lk-1用Apriri_Gen函数天生候选频仍k项集k，并撤除Lk中的元素，即k=k-Lk，对Lk举行剪枝，即对付XLk，假设存在且YLk-1Lk-1，那么X肯定不是dbDB中的频仍k项集，应将其在Lk中删除；然后扫描d

10、b，将Lk中的元素仍为dbDB中的频仍项集的元素记入Lk，记载候选频仍k项集k中的元素在db中的支持数；末了扫描DB，记载k中的元素在DB中的支持数，扫描竣事时，将k中是dbDB中频仍项集的元素记入Lk中。算法在Lk和k均为空时竣事。性能阐发FUP算法利用原数据库集DB的开掘效果，即频仍项集L，必要对DB和db举行n次扫描(n为L中最大的元素的元素个数)，末了得到DBdb中的频仍项集L，以是FUP算法的服从比利用Apriri算法和DHP算法重新对dbDB举行开掘的服从要高得多。不外，FUP算法也存在其缺点，固然它利用此算法利用了原数据库集DB的开掘效果，但是在对新的数据库举行更新时，又必要重复

11、的扫描原数据库DB，对候选集举行形式匹配，由于原数据库集DB相对增长的数据集db是很大的，以是在利用FUP算法对关联规矩举行更新时，会斲丧大量时间处置惩罚范围宏大的候选集，白费了时间。3.2IUA3算法根本头脑算法IUA接纳了一个奇特的候选频仍项集天生算法iua_gen，在对每一次对数据库DB扫描之宿世成较小的候选频仍项集，从而进步了算法的服从。它也要求上一次对数据库DB举行采掘时创造的频仍项集(n为L中最大元素的元素个数)在本次开掘时是可利用的。由于人们在创造关联规矩时，经常必要不竭地调解最小支持度和最小可信度来聚拢到那些真正令其感爱好的关联规矩上，因此该算法具有很紧张的意义。IUA算法的根

12、本框架也和Apriri算法同等，也必要对生意业务数据库DB举行多趟扫描.由于有ss，以是本来全部的频仍k工程集(Lk)在新的最小支持度下仍旧是频仍k工程集，因此在每一趟中扫描生意业务数据库D盘算候选k工程集的支持度计数时，我们就没有需要再思量一遍Lk对应的候选k工程集。假设更进一步盼望制止又重新天生一遍Lk对应的候选k工程集，我们可以思量接纳以空间换时间的计谋，只要在Apriri算法中的每一趟k，保存相应的(k-Lk)即可。在第1趟扫描中，IUA算法只对本来不在L1中的单个工程举行支持度盘算，并确定出全部新的频仍1工程集L1，然后通过L1L1得到L1。利用一个频仍工程集的恣意一个子集肯定是频仍

13、工程集这一性子，频仍k项集的每一单个工程i所对应的频仍1项集i大概从L1中取，大概从L1中龋按照这一特点，IUA算法将具有新支持度s的全部频仍k(k2)工程集分成3类：对付此中的每一个频仍k工程集=i1，i2，.，ik，Pj(1jk)，必有ijL1；对付此中的每一个频仍k工程集=i1，i2，.ik，Pj(1jk)，必有ijL1；对付此中的每一个频仍k工程集=i1，i2，.ik，必有两个非空子集1和2，使得12=，12=，而且1L1，2L1。我们将全部第类频仍k工程集组成的聚拢记为L1k，第类记为L2k，第类记为L3k.同时与之相对应的候选k工程集组成的聚拢别离记为1k，2k，3k.对付1k，2

14、k直接利用Apriri算法阐发：算法中的apriri-gen函数天生；对付3k通过Lj1和Lk-22拼接修剪而成，j从1迭代到k-1。IUA也是接纳Apriri框架。IUA在自底向上的搜刮历程中，根据第k层频仍工程集来天生第k+1层全部候选频仍工程集，然后对各候选频仍工程集举行支持度盘算，从而得到第k+1层全部频仍工程集，直到某层候选工程集为空为止。性能阐发：(1)IUA算法与Apriri算法一样，重要是利用了“一个频仍工程集的任一非空子集肯定也是频仍工程集这一性子。按照这一性子可知，对付任一工程i，假设i不是任一j(jk)工程集的元素，那么i必然不是k-工程集的元素，而在IUA算法的6-8步

15、的循环中7，每调用一次iua_gen函数，通过该函数的拼接将会使一些已显着不是频仍k-工程集的k-工程集成为候选k-工程集3k中的元素，从而给iua_gen函数中的修剪增长运算量，增长了算法的时间庞大性。(2)IUA算法在关联规矩更新时，对k-工程集的开采，只是留意到利用已存在的频仍k-工程集的聚拢Lk，没有留意到基于“一个频仍工程集的任一非空子集肯定也是频仍工程集性子的在本次更新时，对新产生的频仍(k-1)-工程集的聚拢Lk-1加以利用。由于IUA充实利用已开掘的效果及接纳有效的候选频仍工程集天生要领，而且接纳以空间换时间的计谋，如许以来就明显地淘汰了各层候选频仍工程集数量，有效地进步了关联

16、规矩的更新服从.但IUA受Apriri框架的范围，重要存在着以下不敷：多遍扫描数据库，扫描次数取决于新增最大频仍工程集的长度；需产生大量的候选工程集。3.3别的算法另有一些关联规矩更新算法，也都以IUA算法大概以FUP算法为底子，在此算法的底子上举行阐发，在某一方面举行革新，从而提出了一些服从相对更高改革要领，以IUA算法为底子的，比方：宋海生的UA算法10，皋军等提出的y_IUA算法11，周海岩提出的NEIUA算法等；另有以FUP算法为底子的，比方李宝东，宋翰涛的EFUP算法8，朱全玉，汪晓刚的NEFUP算法9等。下面简朴先容两种。1)NEIUA算法NEIUA算法的根本框架与IUA算法和Ap

17、riri算法同等，对k=1，2，接纳某种计谋天生候选k-工程集k，然后扫描数据库来确定k中那些k-工程集是频仍工程集。NEIUA算法与传统的增量式更新算法差异之处重要表如今以下两点：由于有ss，以是，本来全部在旧的最小支持度s下的频仍k-工程集在新的最小支持度s下还是频仍k-工程集。因此在每一趟扫描数据库D盘算候选k-工程集的支持数时，就没有需要对Lk中的工程重新再盘算一次。因此NEIUA算法在天生候选k-工程集的聚拢k时不含Lk中的工程集。NEIUA算法在天生候选k-工程集k时，不单利用了已经存在的频仍k-工程集的聚拢Lk，而且留意到，基于对本次更新时新产生的频仍k-1-工程集Lk-1加以充

18、实利用。与IUA算法比拟，NEIUA算法很好地利用了apriri-gen函数，不外重复对本来Lk-1的处置惩罚，以是算法NEIUA与重新运行Apriri算法比拟，服从上只是有限地进步。2)EFUP算法EFUP算法的根本头脑与FUP算法雷同，区别是：FUP算法利用原数据库集DB的开掘效果，即频仍项集L，必要对DB和db举行n次扫描(n为L中最大的元素的元素个数)，末了得到DBdb中的频仍项集L；而EFUP算法只需对DB举行一次扫描，对db同样举行n次扫描。由于DB一样平常宏大于db因此对付大数据集，EFUP算法可以通过较少对DB的I/操纵来进步服从。对db接纳雷同于Apriri的算法，一方面验证

19、L中的元素是否为dbDB中的频仍项集，另一方面天生此中的频仍项集Ldb，然后对DB举行一次扫描，验证Ldb中的元素是否为dbDB中的频仍项集。但EFUP算法的条件是元数据库DB中的频仍项集和此中元素的支持数。总结：如今一些算法有的存在频仍项集的遗漏题目，有的产生较多的候选项集，有的占用较大的空间，比方文献81213。在文献8中所提到的算法大概会造成频仍项集的遗漏题目。在文献12中所提到的算法大概会造成在扫描db时侯选频仍项集的增长而低落开掘的服从。在文献13中所提到的算法固然简朴，但是却没有充实利用LDB中可以确定为非频仍项集的项集，在Apriri算法对db举行扫描产生侯选集Ldb的历程中举行

20、更有效的剪枝；而且假设新增的数据库db所产生的局部频仍项集与原频仍都较大且大局部是雷同集时，整个历程中空间的白费也较大。因此提出高效的更新算法是当务之急。3.4负关联规矩的增量式更新传统的关联规矩用于开掘主顾事件数据库中项集间的关联干系，而传统的关联规矩开掘算法仅能用来创造强形式，即那些具有高频率和强相干的显式。现实上数据库中还存在着很多接纳如今开掘技能所不克不及创造的隐式形式，这些紧张的隐士形式之一便是负关联规矩，即两件事变很少同时出现，但却具有较高的相干度，它具有低频率、强相干的性子，表示了数据工程集间的不轻易直接不雅察到的强相干性子，这些隐式规矩报告我们哪些数据工程较少的一起产生，但它们

21、却包罗了非常有代价的信息，因此创造负关联规矩具有非常紧张的意义。险些大局部的关联规矩开掘及其算法都只是涉及到项集间的关联规矩，即正关联规矩，比方“买了尿布的主顾也大概买啤酒如许的规矩。但是形如“买了牛奶的主顾大概不买咖啡如许的负关联规矩，在现实中可以和正关联规矩一样提供有代价的信息。比方，负关联规矩可以帮助市场监视局部在浩繁的非公正生意业务的警报信号中断定哪些是可以忽略的；企业可以通过综合思量正、负关联规矩从而捉住更多的商机。现实上，负关联规矩的增量更新与关联规矩的增量更新雷同，都是在更新后的数据库中开掘负关联规矩。但如今对负关联规矩增量更新的研究还处于初始阶段，在以后的学习与研究中，将重点研

22、究负关联规矩的增量更新这方面的知识。本文起首提出了关联规矩的经典Apriri算法，并阐发了该算法的长处以及存在的不敷，接着引入了关联规矩的相干知识，并侧重讨论关联规矩的更新算法，重点对FUP与IUA算法举行阐发与总结，末了又简朴先容了两种好的革新算法，盼望以后对负关联规矩的增量式更新的研究有所帮助。1AgraalR，IielinskiT，SaIA.iningassiatinrulesbeteensetsfitesinlargedatabaseA.Preedingfthe1993ASIGDInternatinalnferenenanageentfData.NeYrk：APress，1993.207-2162AgraalR，SrikantR.Fastalgrithsfrinin