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

1、关联规则的增量更新算法研究 08-05-01 09:23:00 作者：孙宝友1 姜合2 编辑：studa0714摘 要 随着数据库的不断变化，关联规则的增量更新变得尤为重要。为了更好的对关联规则进行有效的更新，本文对已经提出的经典的关联规则更新算法FUP和IUA算法进行分析，指出其优缺点；最后对另外的改进算法，做一个简单的叙述。 关键词 数据库；关联规则；增量更新 关联规则反映了数据库中数据项目之间有趣的关联关系，而其中发现频繁项目集是关联规则挖掘应用中的关键技术和步骤。关于频繁项目集的挖掘算法研究，人们对此进行了大量的工作，其中以R. Agrawal 等人提出的Apriori 、Aprior

2、iTid 等算法最具有影响力和代表性。而这些算法的提出都是在挖掘数据库和最小支持度不变的条件下进行的。但实际中，遇到的情况可能是：随着时间的推移，挖掘数据库的规模可能不断膨胀或需要删除一部分记录，或者需要对最小支持度进行调整从而逐步聚集到我们感兴趣的频繁项目集上。因而如何从数据发生变动后的数据库中高效地对已经推导出的关联规则进行更新，具有非常重要的应用价值，这就是所谓的增量式挖掘关联规则的问题。1 关联规则 问题描述： 设I=i1，i2，.，im是m个不同项目的集合，给定一个事务数据库D，其中D每一个事务T是I中一组项目的集合，即TI，T有一个惟一的标志符TID。如果对于I中的一个子集X，有X

3、T，我们就说一个事务T包含X。一条关联规则(association rule)就是一个形如X =Y的蕴涵式，其中X，YT，而XY=。关联规则成立的条件是：它具有最小支持度s，即事务数据库D中至少有s%的事务包含XY；它具有最小可信度c，即在事务数据库D中包含X的事务中至少有c%同时也包含Y。给定一个事务集D，挖掘关联规则问题就是产生支持度和可信度分别大于用户给定的最小支持度和最小可信度的关联规则，也就是产生强规则的问题。 关联规则的挖掘问题可以分解为以下两个问题： (1) 找出事务数据库中所有具有用户最小支持度的项目集。具有用户指定最小支持度的项目集称为频繁项目集，反之称为非频繁项目集。一个项

4、目中所含项目的个数称为该项目的长度。 (2) 利用频繁项目集生成关联规则。对于每一个频繁项目集A，若BA，B，且support(A)/support(B)minconf，则有关联规则B= (A-B)。目前大多数的研究主要集中在第一个问题上面。2 Apriori核心算法1 Agrawal等人于1994年提出了一个挖掘顾客交易数据库中项集间的关联规则的重要方法Apriori算法，其核心是基于两个阶段频繁项集思想的递推算法。算法的基本思想是首先找出所有的频集，这些项集出现的频繁性至少和预定义的最小支持度一样。然后由频繁项集产生强关联规则，这些规则必须满足最小支持度和最小可信度。Apriori核心算法

5、思想简要描述如下：该算法中有两个关键步骤连接步和剪枝步。 (1) 连接步：为找出Lk(频繁k一项集)，通过Lk-1与自身连接，产生候选k-项集，该候选项集记作Ck；其中Lk-1的元素是可连接的。 (2) 剪枝步：Ck是Lk的超集，即它的成员可以是也可以不是频繁的，但所有的频繁一项集都包含在Ck中。扫描数据库，确定Ck中每一个候选的计数，从而确定Lk(计数值不小于最小支持度计数的所有候选是频繁的，从而属于Lk)。然而，Ck可能很大，这样所涉及的计算量就很大。为压缩Ck，使用Apriori性质：任何非频繁的(k-1)-项集都不可能是频繁k-项集的子集。因此，如果一个候选k-项集的(k-1)项集不在

6、Lk中，则该候选项也不可能是频繁的，从而可以由Ck中删除。这种子集测试可以使用所有频繁项集的散列树快速完成。 这个方法要求多次扫描可能很大的交易数据库，即如果频集最多包含10个项，那么就需要扫描交易数据库10遍，这需要很大的I/O负载。可能产生大量的候选集，以及可能需要重复扫描数据库，是Apriori算法的两大缺点。3 关联规则增量更新 关联规则反映了数据库中数据项目之间有趣的关联关系，而其中发现频繁项目集是关联规则挖掘应用中的关键技术和步骤。关于频繁项目集的挖掘算法研究，人们对此进行了大量的工作，其中以R. Agrawal 等人提出的Apriori、AprioriTid 等算法最具有影响力和

7、代表性。而这些算法的提出都是在挖掘数据库和最小支持度不变的条件下进行的。实际中，数据库的规模随着时间，可能不断膨胀或需要删除一部分记录，或者需要对最小支持度进行调整从而逐步聚集到我们感兴趣的频繁项目集上。因而如何高效地从更新后的数据库中对已经推导出的关联规则进行更新是具有非常重要的价值的，这就是关联规则增量更新问题。 广义上的关联规则的更新问题就是，在原有数据库DB的基础上，对其加上(或减去)数据库db，在新的数据库DB+上挖掘新关联规则的问题。关联规则的增量式更新问题主要有三个：在给定的最小支持度和最小置信度下，当一个新的数据集db添加到旧的数据库DB中时，如何生成dbDB中的关联规则；在给

8、定的最小支持度和最小置信度下，当从旧的数据库DB中删除数据集db时，如何生成DB-db中的关联规则；给定数据库DB，在最小支持度和最小置信度发生变化时，如何生成数据库DB中的关联规则。文献2中Agrawal R，和Srikant R 提出的FUP算法是一个与Apriori算法相一致的针对第一个问题的更新算法。文献3中，Brin S， Motwani R， 和Silverstein C提出的 FUP2算法是一个同时考虑第一个问题与第二个问题的算法。第三类问题则有冯玉才、冯剑琳提出的算法IUA和PIUA7。 下面给出两个比较经典算法：FUP和IUA算法的基本思想，并分析了各自的优缺点。3.1 FU

9、P算法的基本思想 对任意一个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中的元素是否为dbDB中的频繁项集，并将是dbD

10、B中的频繁项集的元素记入L1中。在第k (k1)此扫描前，先对Lk-1用Apriori_Gen函数生成候选频繁k项集Ck，并除去Lk中的元素，即Ck=Ck - Lk，对Lk进行剪枝，即对于XLk，若存在且Y Lk-1 Lk-1，则X肯定不是dbDB中的频繁k项集，应将其在Lk中删除；然后扫描db，将Lk中的元素仍为dbDB中的频繁项集的元素记入Lk，记录候选频繁k项集Ck中的元素在db中的支持数；最后扫描DB，记录Ck中的元素在DB中的支持数，扫描结束时，将Ck中是dbDB中频繁项集的元素记入Lk中。算法在Lk和Ck均为空时结束。 性能分析 FUP算法利用原数据库集DB的挖掘结果，即频繁项集L

11、，需要对DB和db进行n次扫描(n为L中最大的元素的元素个数)，最后得到DBdb中的频繁项集L，所以FUP算法的效率比使用Apriori算法和DHP算法重新对dbDB进行挖掘的效率要高得多。 不过，FUP算法也存在其缺点，虽然它利用此算法利用了原数据库集DB的挖掘结果，但是在对新的数据库进行更新时，又需要重复的扫描原数据库DB，对候选集进行模式匹配，因为原数据库集DB相对增加的数据集db是很大的，所以在利用FUP算法对关联规则进行更新时，会消耗大量时间处理规模巨大的候选集，浪费了时间。3.2 IUA3算法基本思想 算法IUA采用了一个独特的候选频繁项集生成算法iua_gen，在对每一次对数据库

12、DB扫描之前生成较小的候选频繁项集，从而提高了算法的效率。它也要求上一次对数据库DB进行采掘时发现的频繁项集(n为L中最大元素的元素个数)在本次挖掘时是可使用的。因为人们在发现关联规则时， 常常需要不断地调整最小支持度和最小可信度来聚集到那些真正令其感兴趣的关联规则上， 因而该算法具有很重要的意义。IUA 算法的基本框架也和Apriori 算法一致， 也需要对交易数据库DB 进行多趟扫描. 因为有s s， 所以原来所有的频繁k 项目集(L k ) 在新的最小支持度下仍然是频繁k 项目集， 因此在每一趟中扫描交易数据库D 计算候选k 项目集的支持度计数时， 我们就没有必要再考虑一遍Lk 对应的候

13、选k 项目集。如果更进一步希望避免又重新生成一遍Lk对应的候选k 项目集， 我们可以考虑采取以空间换时间的策略， 只要在Apriori 算法中的每一趟k， 保存相应的(Ck -L k ) 即可。 在第1趟扫描中，IUA 算法只对原来不在L1中的单个项目进行支持度计算，并确定出所有新的频繁1 项目集L1，然后通过L1L1 得到L1。利用一个频繁项目集的任意一个子集必定是频繁项目集这一性质，频繁k项集c的每一单个项目i所对应的频繁1项集i或者从L1中取，或者从L1中取。根据这一特点，IUA算法将具有新支持度s的所有频繁k(k2)项目集分成3类： 对于其中的每一个频繁k 项目集c= i1， i2，.

14、 . .，ik， Pj (1j k )，必有ijL 1； 对于其中的每一个频繁k 项目集c= i1， i2，. . .ik， Pj (1j k )，必有ijL1； 对于其中的每一个频繁k 项目集c= i1， i2，. . . ik， 必有两个非空子集c1 和c2， 使得c1c2= c， c1c2= ， 而且c1 L1， c2 L1。 我们将所有第类频繁k 项目集构成的集合记为L1k， 第类记为L2k， 第类记为L3k. 同时与之相对应的候选k 项目集构成的集合分别记为C1k， C2k， C3k.对于C1k， C2k直接利用Apriori算法分析：算法中的apriori-gen函数生成；对于C3

15、k通过Lj1和Lk-22拼接修剪而成，j从1迭代到k-1。IUA也是采用Apriori框架。IUA 在自底向上的搜索过程中， 依据第k 层频繁项目集来生成第k+ 1 层所有候选频繁项目集， 然后对各候选频繁项目集进行支持度计算， 从而获得第k + 1 层所有频繁项目集， 直到某层候选项目集为空为止。 性能分析： (1)IUA算法与Apriori算法一样，主要是利用了“一个频繁项目集的任一非空子集必定也是频繁项目集”这一性质。根据这一性质可知，对于任一项目i，如果i不是任一j(jk)项目集的元素，则i一定不是k-项目集的元素，而在IUA算法的6-8步的循环中7，每调用一次iua_gen函数，通过该函数的拼接将会使一些已明显不是频繁k-项目集的k-项目集成为候选k-项目集C3k中的元素，从而给iua_gen函数中的修剪增加运算量，增加了算法的时间复杂性。 (2)IUA算法在关联规则更新时，对k-项目集的开采，只是注意到利用已存在的频繁k-项目集的集合Lk，没有注意到基于“一个频繁项目集的任一非空子集必定也是频繁项目集”性质的在本次更新时，对新产生的频繁(k-1)-项目集的集合Lk-1加以利用。 由于IUA 充分利用已挖掘的结果及采用有效的候选频繁项