关联规则的增量更新算法研究
发布时间：2015-07-11 10:02
摘 要 随着数据库的不断变化，关联规则的增量更新变得尤为重要。为了更好的对关联规则进行有效的更新，本文对已经提出的经典的关联规则更新算法FUP和IUA算法进行分析，指出其优缺点；最后对另外的改进算法，做一个简单的叙述。
关键词 数据库；关联规则；增量更新
关联规则反映了数据库中数据项目之间有趣的关联关系，而其中发现频繁项目集是关联规则挖掘应用中的关键技术和步骤。关于频繁项目集的挖掘算法研究，人们对此进行了大量的工作，其中以R. Agrawal 等人提出的Apriori 、AprioriTid 等算法最具有影响力和代表性。而这些算法的提出都是在挖掘数据库和最小支持度不变的条件下进行的。但实际中，遇到的情况可能是：随着时间的推移，挖掘数据库的规模可能不断膨胀或需要删除一部分记录，或者需要对最小支持度进行调整从而逐步聚集到我们感兴趣的频繁项目集上。因而如何从数据发生变动后的数据库中高效地对已经推导出的关联规则进行更新，具有非常重要的应用价值，这就是所谓的增量式挖掘关联规则的问题。
1 关联规则
问题描述：
设I={i1，i2，...，im}是m个不同项目的集合，给定一个事务数据库D，其中D每一个事务T是I中一组项目的集合，即TI，T有一个惟一的标志符TID。如果对于I中的一个子集X，有XT，我们就说一个事务T包含X。一条关联规则(association rule)就是一个形如X =Y的蕴涵式，其中X，YT，而X∩Y=Φ。关联规则成立的条件是：①它具有最小支持度s，即事务数据库D中至少有s%的事务包含X∪Y；②它具有最小可信度c，即在事务数据库D中包含X的事务中至少有c%同时也包含Y。给定一个事务集D，挖掘关联规则问题就是产生支持度和可信度分别大于用户给定的最小支持度和最小可信度的关联规则，也就是产生强规则的问题。
关联规则的挖掘问题可以分解为以下两个问题：
(1) 找出事务数据库中所有具有用户最小支持度的项目集。具有用户指定最小支持度的项目集称为频繁项目集，反之称为非频繁项目集。一个项目中所含项目的个数称为该项目的长度。
(2) 利用频繁项目集生成关联规则。对于每一个频繁项目集A，若BA，B≠Φ，且support(A)/support(B)minconf，则有关联规则B= (A-B)。目前大多数的研究主要集中在第一个问题上面。
2 Apriori核心算法[1]
Agrawal等人于1994年提出了一个挖掘顾客交易数据库中项集间的关联规则的重要方法Apriori算法，其核心是基于两个阶段频繁项集思想的递推算法。算法的基本思想是首先找出所有的频集，这些项集出现的频繁性至少和预定义的最小支持度一样。然后由频繁项集产生强关联规则，这些规则必须满足最小支持度和最小可信度。Apriori核心算法思想简要描述该算法中有两个关键步骤连接步和剪枝步。
(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)项集不在Lk中，则该候选项也不可能是频繁的，从而可以由Ck中删除。这种子集测试可以使用所有频繁项集的散列树快速完成。
这个方法要求多次扫描可能很大的交易数据库，即如果频集最多包含10个项，那么就需要扫描交易数据库10遍，这需要很大的I/O负载。可能产生大量的候选集，以及可能需要重复扫描数据库，是Apriori算法的两大缺点。
3 关联规则增量更新
关联规则反映了数据库中数据项目之间有趣的关联关系，而其中发现频繁项目集是关联规则挖掘应用中的关键技术和步骤。关于频繁项目集的挖掘算法研究，人们对此进行了大量的工作，其中以R. Agrawal 等人提出的Apriori、AprioriTid 等算法最具有影响力和代表性。而这些算法的提出都是在挖掘数据库和最小支持度不变的条件下进行的。实际中，数据库的规模随着时间，可能不断膨胀或需要删除一部分记录，或者需要对最小支持度进行调整从而逐步聚集到我们感兴趣的频繁项目集上。因而如何高效地从更新后的数据库中对已经推导出的关联规则进行更新是具有非常重要的价值的，这就是关联规则增量更新问题。
广义上的关联规则的更新问题就是，在原有数据库DB的基础上，对其加上(或减去)数据库db，在新的数据库DB+上挖掘新关联规则的问题。关联规则的增量式更新问题主要有三个：①在给定的最小支持度和最小置信度下，当一个新的数据集db添加到旧的数据库DB中时，如何生成db∪DB中的关联规则；②在给定的最小支持度和最小置信度下，当从旧的数据库DB中删除数据集db时，如何生成DB-db中的关联规则；③给定数据库DB，在最小支持度和最小置信度发生变化时，如何生成数据库DB中的关联规则。文献中Agrawal R，和Srikant R 提出的FUP算法是一个与Apriori算法相一致的针对第一个问题的更新算法。文献中，Brin S， Motwani R， 和Silverstein C提出的 FUP2算法是一个同时考虑第一个问题与第二个问题的算法。第三类问题则有冯玉才、冯剑琳提出的算法IUA和PIUA。
下面给出两个比较经典算法：FUP和IUA算法的基本思想，并分析了各自的优缺点。
3.1 FUP算法的基本思想
对任意一个k (k≥1)项集，若其在DB和db中都是频繁项集，则其一定是频繁项集；若其在DB和db中都是非频繁项集，则其一定是非频繁项集；若其仅在DB(db)中是频繁项集，则其支持计数应加上其在db(DB)中的支持数以确定它是否为频繁项集。FUP算法假设在DB中发现的频繁项集(n为L中最大元素的元素个数)已被保存下来。它需要对DB和db进行多次扫描，在第一次扫描中，算法先扫描db，将L1中的元素仍为db∪DB中的频繁项集的元素记入L1′，并生成候选频繁1项集C1，C1中的元素为db中的频繁1项集且不包含在L1中；然后扫描DB以决定C1中的元素是否为db∪DB中的频繁项集，并将是db∪DB中的频繁项集的元素记入L1′中。在第k (k1)此扫描前，先对Lk-1′用Apriori_Gen函数生成候选频繁k项集Ck，并除去Lk中的元素，即Ck=Ck - Lk，对Lk进行剪枝，即对于XÎLk，若存在且YÎ Lk-1 – Lk-1′，则X肯定不是db∪DB中的频繁k项集，应将其在Lk中删除；然后扫描db，将Lk中的元素仍为db∪DB中的频繁项集的元素记入Lk′，记录候选频繁k项集Ck中的元素在db中的支持数；最后扫描DB，记录Ck中的元素在DB中的支持数，扫描结束时，将Ck中是db∪DB中频繁项集的元素记入Lk′中。算法在Lk和Ck均为空时结束。
性能分析
FUP算法利用原数据库集DB的挖掘结果，即频繁项集L，需要对DB和db进行n次扫描(n为L中最大的元素的元素个数)，最后得到DB∪db中的频繁项集L′，所以FUP算法的效率比使用Apriori算法和DHP算法重新对db∪DB进行挖掘的效率要高得多。
不过，FUP算法也存在其缺点，虽然它利用此算法利用了原数据库集DB的挖掘结果，但是在对新的数据库进行更新时，又需要重复的扫描原数据库DB，对候选集进行模式匹配，因为原数据库集DB相对增加的数据集db是很大的，所以在利用FUP算法对关联规则进行更新时，会消耗大量时间处理规模巨大的候选集，浪费了时间。
3.2 IUA算法基本思想
算法IUA采用了一个独特的候选频繁项集生成算法iua_gen，在对每一次对数据库DB扫描之前生成较小的候选频繁项集，从而提高了算法的效率。它也要求上一次对数据库DB进行采掘时发现的频繁项集(n为L中最大元素的元素个数)在本次挖掘时是可使用的。因为人们在发现关联规则时， 常常需要不断地调整最小支持度和最小可信度来聚集到那些真正令其感兴趣的关联规则上， 因而该算法具有很重要的意义。IUA 算法的基本框架也和Apriori 算法一致， 也需要对交易数据库DB 进行多趟扫描. 因为有s′ s， 所以原来所有的频繁k 项目集(L k ) 在新的最小支持度下仍然是频繁k 项目集， 因此在每一趟中扫描交易数据库D 计算候选k 项目集的支持度计数时， 我们就没有必要再考虑一遍Lk 对应的候选k 项目集。如果更进一步希望避免又重新生成一遍Lk对应的候选k 项目集， 我们可以考虑采取以空间换时间的策略， 只要在Apriori 算法中的每一趟k， 保存相应的(Ck -L k ) 即可。
在第1趟扫描中，IUA 算法只对原来不在L1中的单个项目进行支持度计算，并确定出所有新的频繁1 项目集L1″，然后通过L1″∪L1 得到L1′。利用一个频繁项目集的任意一个子集必定是频繁项目集这一性质，频繁k项集c的每一单个项目i所对应的频繁1项集{i}或者从L1中取，或者从L1″中取。根据这一特点，IUA算法将具有新支持度s′的所有频繁k(k≥2)项目集分成3类：
①对于其中的每一个频繁k 项目集c= {i1， i2，. . .，ik}， Pj (1≤j ≤k )，必有{ij}∈L 1；
②对于其中的每一个频繁k 项目集c= {i1， i2，. . .ik}， Pj (1≤j ≤k )，必有{ij}∈L1″；
③对于其中的每一个频繁k 项目集c= {i1， i2，. . . ik}， 必有两个非空子集c1 和c2， 使得c1∪c2= c， c1∩c2= Φ， 而且c1 L1， c2 L1″。
我们将所有第①类频繁k 项目集构成的集合记为L1k， 第②类记为L2k， 第③类记为L3k. 同时与之相对应的候选k 项目集构成的集合分别记为C1k， C2k， C3k.对于C1k， C2k直接利用Apriori算法分析：算法中的apriori-gen函数生成；对于C3k通过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步的循环中，每调用一次iua_gen函数，通过该函数的拼接将会使一些已明显不是频繁k-项目集的k-项目集成为候选k-项目集C3k中的元素，从而给iua_gen函数中的修剪增加运算量，增加了算法的时间复杂性。
(2)IUA算法在关联规则更新时，对k-项目集的开采，只是注意到利用已存在的频繁k-项目集的集合Lk，没有注意到基于“一个频繁项目集的任一非空子集必定也是频繁项目集”性质的在本次更新时，对新产生的频繁(k-1)-项目集的集合Lk-1′加以利用。
由于IUA 充分利用已挖掘的结果及采用有效的候选频繁项目集生成方法，并且采取以空间换时间的策略，这样以来就显着地减少了各层候选频繁项目集数目， 有效地提高了关联规则的更新效率.但IUA 受Apriori 框架的局限， 主要存在着以下不足： ①多遍扫描数据库， 扫描次数取决于新增最大频繁项目集的长度； ②需产生大量的候选项目集。
3.3 其它算法
还有一些关联规则更新算法，也都以IUA算法或者以FUP算法为基础，在此算法的基础上进行分析，在某一方面进行改进，从而提出了一些效率相对更高改造方法，以IUA算法为基础的，例如：宋海生的UA算法[10]，皋军等提出
的My_IUA算法[11]，周海岩提出的NEWIUA算法等；还有以FUP算法为基础的，例如李宝东，宋翰涛的EFUP算法，朱全玉，汪晓刚的NEWFUP算法等。下面简单介绍两种。
1) NEWIUA算法
NEWIUA算法的基本框架与IUA算法和Apriori算法一致，对k=1，2，m，采用某种策略生成候选k-项目集Ck，然后扫描数据库来确定Ck中那些k-项目集是频繁项目集。
NEWIUA算法与传统的增量式更新算法不同之处主要体现在以下两点：
⑴ 因为有s′s，所以，原来所有在旧的最小支持度s下的频繁k-项目集在新的最小支持度s’下仍是频繁k-项目集。因此在每一趟扫描数据库D计算候选k-项目集的支持数时，就没有必要对Lk中的项目重新再计算一次。因此NEWIUA算法在生成候选k-项目集的集合Ck时不含Lk中的项目集。
⑵ NEWIUA算法在生成候选k-项目集Ck时，不但利用了已经存在的频繁k-项目集的集合Lk，而且注意到，基于对本次更新时新产生的频繁k-1-项目集Lk-1′加以充分利用。
与IUA算法相比，NEWIUA算法很好地利用了apriori-gen 函数，不过重复对原来Lk-1的处理，所以算法NEWIUA与重新运行Apriori 算法相比，效率上只是有限地提高。
2) EFUP算法
EFUP算法的基本思想与FUP算法类似，区别是：FUP算法利用原数据库集DB的挖掘结果，即频繁项集L，需要对DB和db进行n次扫描(n为L中最大的元素的元素个数)，最后得到DB∪db中的频繁项集L′；而EFUP算法只需对DB进行一次扫描，对db同样进行n次扫描。因为DB一般远大于db因此对于大数据集，EFUP算法可以通过较少对DB的I/O操作来提高效率。对db采用类似于Apriori的算法，一方面验证L中的元素是否为db∪DB中的频繁项集，另一方面生成其中的频繁项集Ldb，然后对DB 进行一次扫描，验证Ldb中的元素是否为db∪DB中的频繁项集。但EFUP算法的前提是已知元数据库DB中的频繁项集和其中元素的支持数。
总结：现在一些算法有的存在频繁项集的遗漏问题，有的产生较多的候选项集，有的占用较大的空间，例如文献 [12][13]。在文献中所提到的算法可能会造成频繁项集的遗漏问题。在文献[ 12 ]中所提到的算法可能会造成在扫描db时侯选频繁项集的增加而降低挖掘的效率。在文献[13]中所提到的算法虽然简单，但是却没有充分利用LDB中可以确定为非频繁项集的项集，在Apriori算法对db进行扫描产生侯选集Ldb的过程中进行更有效的剪枝；并且若新增的数据库db所产生的局部频繁项集与原频繁都较大且大部分是相同集时，整个过程中空间的浪费也较大。因此提出高效的更新算法是当务之急。
3.4 负关联规则的增量式更新
传统的关联规则用于挖掘顾客事务数据库中项集间的关联关系，而传统的关联规则挖掘算法仅能用来发现强模式，即那些具有高频率和强相关的显式。实际上数据库中还存在着许多采用目前挖掘技术所不能发现的隐式模式，这些重要的隐士模式之一便是负关联规则，即两件事情很少同时出现，但却具有较高的相关度，它具有低频率、强相关的性质，表现了数据项目集间的不容易直接观察到的强相关性质，这些隐式规则告诉我们哪些数据项目较少的一起发生，但它们却包含了非常有价值的信息，因此发现负关联规则具有十分重要的意义。几乎大部分的关联规则挖掘及其算法都只是涉及到项集间的关联规则，即正关联规则，例如“买了尿布的顾客也可能买啤酒”这样的规则。可是形如“买了牛奶的顾客可能不买咖啡”这样的负关联规则，在实际中可以和正关联规则一样提供有价值的信息。例如，负关联规则可以帮助市场监督部门在众多的非公平交易的警报信号中判断哪些是可以忽略的；企业可以通过综合考虑正、负关联规则从而抓住实际上，负关联规则的增量更新与关联规则的增量更新类似，都是在更新后的数据库中挖掘负关联规则。但目前对负关联规则增量更新的研究还处于初始阶段，在以后的学习与研究中，将重点研究负关联规则的增量更新这方面的知识。
4 结束语
本文首先提出了关联规则的经典Apriori算法，并分析了该算法的优点以及存在的不足，接着引入了关联规则的相关知识，并着重讨论关联规则的更新算法，重点对FUP与IUA算法进行分析与总结，最后又简单介绍了两种好的改进算法，希望以后对负关联规则的增量式更新的研究有所帮助。
参考文献
[1]A grawal R， Imielinsk iT， Swam I A. Mining association rules between sets of items in large database [A]. Proceeding of the 1993 ACM S IGMOD International Conference on Management of Data [C ]. New York： ACM Press， 1993. 207- 216
Agrawal R， Srikant R. Fast algorithms for mining association rules in large database [A]. Proceedings of the 1994 International Conference on VLDB [C ]. San Francisco： Morgan Kaufmann Publishers， 1994. 487- 499
Brin S， Motwani R， Silverstein C. Beyond market： Generalizing association rules to correlations [A ]. Processing of the ACMSIGMOD Conference 1997 [C ]. New York： ACM Press， 1997. 265- 276
Wu Xindong， Zhang Chengqi， Zhang Shichao. Mining both positive and negative association rules [A]. Proceedings of the 19th International Conference on Matchine Learning (ICML 22002 ) [C]. San Francisco： Morgan Kaufmann Publishers， 2002. 658- 665
范明，孟小峰等.数据挖掘概念与技术[M].机械工业出版社，2001. 8
l and t， Fast Algorithms for Mining Association Rules in Large Databases， In Research Report RJ 9839， IBM Almaden Research Center， San Jose， California， 1994
冯玉才、冯剑琳，关联规则的增量式更新算法[J].软件学报，1998，4
李宝东、宋翰宗，关联规则增量更新算法研究[J].计算机工程与应用，2002，23
朱玉全，汪晓刚，一种新的关联规则增量式更新算法[J].计算机工程，2002，28(4)，25-27
[10]宋海生，关联规则的增量式更新算法[J].兰州大学学报，2004，40(2)
[11]皋军，王建东，关联规则挖掘算法更新与拓展[J].计算机工程与应用，2003，35
[12]李雄飞等. 二次挖掘相联规则算法[J]. 吉林大学学报， 2002， 32 (2) ： 73 - 77
[13]陈劲松等. 一种增量更新算法[J]. 计算机工程， 2002. 7， 28 (7) ： 106 – 107
上一篇：基于模板的题库平台系统