动态数据库关联规则增量更新算法

1、动态数据库关联规则增量更新算法摘要:针对大部分关联规则更新算法只考虑最小支持度这一因素，却没有考虑最小置信度阀值。数据库更新时只考虑数据的添加，而没有考虑数据的删除。文章提由了一种可同时考虑以上几方面的动态数据库更新算法，可有效挖掘由人们有兴趣的知识。实验表明，该算法切实可行。关键词：动态数据库；关联规则；支持度；置信度；增量更新算法中图分类号:TP311文献标识码:A文章编号:1009-2374 (2010)21-0036-04关联规则挖掘是数据挖掘的一个重要分支，主要研究若干个因素之间的相关性。最初由Agrawal等人提由并给由了用于挖掘关联规则的Apriori算法。目前，关联

2、规则已经广泛应用于各行业的决策系统中，大大提高决策者们的决策效率。遗憾的是，用户大都使用的是静态数据库，不能真实反映现实信息,得由的关联规则不一定正确有效。为此，本文主要研究动态数据库的关联规则更新算法。由于现实世界的数据在变化，其中隐含的信息也在变化人们对庞大数据库进行挖掘时应基于动态数据库。对动态数据库进行挖掘，不仅考虑的是算法效率的问题，还要考虑到关联规则的更新维护问题。针对关联规则的更新维护，学者们提生了很多算法，如:Zhang等提由的负增量关联规则更新算法，文献45等提由了有关关联规则增量更新算法，这些算法均很好地解决了关联规则更新问题，但也只是从增加容量或减少容量一方面考虑，且只是

3、从维护最小支持度阈值着手。本文提由一种解决方案，既考虑数据库信息量的变化，又考虑了将最小支持与最小置信度综合因素彳艮好地解决了关联规则的维护问题，实验表明，该方法切实可行。1相关定义及问题的提由设I=i1,i2,im是项的集合， 其中的元素称为项计em,设事务数据库为D,则事务数为|D|,其中事务为T=t1,t2,皿,每个事务ti有唯一的标识TID,tiIo若AI,BI,且AnB=sup(A)表示D中含A的事务数则A的支持度为|A|/|D|,同理含AB项集的支持度为|AB|/|D|记为sup(AB)o规 则AB在 事 务 数 据 库D中 的 置 信 度 可 表 示 为conf(AB)=|AB|

4、/|A|,也即同时包含A和B的事务数与包含A的事务数之比。关联规则挖掘就是从数据库中我由所有满足下列条件的知识：(1)sup(AB)=minsup(2)conf(AB)=minconf其中minsup为最小支持度阈值，minconf为最小置信度阈值。数据库变化后要得到关联规则，最简单的方法是重新分利用以前挖掘的结果。如何在minsup和minconf不变的情况下，通过已经得到的关联规则结果，对变化的数据库(增加或删除事务数)进行挖掘得到新的关联规则库。本文重点讨论解决这一问题的方法。目前增量式更新算法还有文献67。本文通过最小支持度及最小置信度不变，提供一种方法来判断更新后的数据库中的关联规则

5、。2更新算法模式维护不仅从最小支持度考虑，还要从最小置信度考虑进行维护，以下对动态数据库模式维护均从这两方面讨论：2.1增加容量2.1.1支持度的讨论设原数据库的事务数为D1,项集A的支持度为S1,a,b为项集,conf(a=b)=C1(其中a,b与A之间的关系为aA,bB,ab=A,anb=);增加部分的事务数为D2,项集A的支持度为S2,conf(a=b)=C2;则融合后的数据库事务数为D1+D2,支持度为S3=,conf(a=b)=C3,设频繁项的最小支持度为minsup,最小置信度为minconf,根据S1,S2与minsup的大小可组合成以下几种情况：(1)条件：S1=minsup且

6、S2=minsup结论:S3=min_s证明:S3=minsup(2)条件：S1=minsup且S2=minsup结论：若=1+a，贝US3=minsup,否则,S30)证明：若S3=minsup,则S3=minsup=minsup=minsup=minsup+S2=minsup=1+a以上各步骤均为等价变换，故若满足=1+a，则可得到S3=minsupo同理，若b)=C1(其中Slab为项集a与b在D1中同时发生的概率,S1a为项集a在D1中发生的概率);于此类似，在事务D2中,conf(a=b)=C2;融合后的数据中conf(a=b)=C3,同理，根据C1,C2与minconf的大小也可组

7、合成以下几种情况：(1)条件：C1=minconf,且C2=minconf结论:C3=minconf证明：由于C1=minconf即S1ab=S1a?C1=S1a?minconf同理C2=minconf即S2ab=S2a?C2=S2a?minconf故C3=minconf(2)条件：C1=minconfILC2=minconf结论:若=1+a?B，贝UC3=minconf,否贝U,C30,B=)证明:C3=minconf =minconf =minconf =minconf +C2=minconf =minconf-C2 

8、= =1+B?a2.2减少容量2.2.1支持度的讨论对于有关数据库的一些参数与2.1.1一样，只不过这里针对的是数据库的删除情况。删除后的数据库事务数为D1-D2(D1D2),项集A的支持度为：S3=根据S3的公式可知，S3的值与S1,S2,D1,D2的大小有关。为判断S3与minsup的大小，应从以下几情况讨论：(1)条件:S1minsup,S2minsup证明：S1?D1minsup?D1,-S2?D2-minsup?D2,S3=minsup(2)条件:S1minsup结论:S3minsup且S2minsup或S1=1-a，则S3=minsup。?=minsup m

9、insup(其中a=) =minsup =1-a=1-a同理可得，当=minconf,minconf证明：:S1ab=minconf?S1aS2ab=即C3minconf。(2)条件:minconf结论:C3=minconf且C2=minconf或C1minconf结论：若=1-a?B，贝UC3=minconf,否则,C30,B=)证明:C3=minconf =minconf =minconf =minconf +C2=minconf =minconf-C2 = =1-B?a即，在第三种

10、条件下只要满足式：=1-B?。(其中B=),就可得到：C3=minconf2.3算法主要过程描述前提：原数据库事务数D1,更新的数据库的事务数D2;原数据库中频繁项集的L1,更新的为频繁项集为L2;各频繁项及关联规则的支持度和置信度已经在前期工作中已经得到。最小支持为min_s,最小置信度是min_c以下以添加数据库为例的主要过程如下：(1)ifweadddatathen增力数据库(2)while(L1!=NULL)(3)取由L­1中的一项；设为项集A(4)在L2中查找项集A;(5)IfS1=min_s&S2=min_s(6)将项集A是频繁项输入到tempL;(7)ElseS1=1+a

11、(10)将项集A是频繁项输入到tempL;(11)Elsecontinue;在项集A中找关联规则，设有规则a=b,设C1为原数据库中规则a=b的置信度且C2为更新的数据库中规则a=b的置信度：(12)IfC1=min_c,且C2=min_c(13)输由强关联规则Elseif(C1=min_c&C2=min_c)if=1+a?B输由强关联规则(14)/endwhile(15)/endif删除数据库时的算法与与增加情况类似，只是在条件判断时稍微有点差别，在此就不再叙述了。3实验与分析对动态数据库进行关联规则挖掘，变化的信息量大。为了节省时间，充分利用已获得的结果，本文提生了上述更新算法。此算法是在考虑最小置信度与最小支持度不变的情况下只对新变化的数据进行挖掘，然后通过少量计算就可得到变化后的关联规则，可提高时间上的效率