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

《关联规则的增量更新算法研究》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、关联规则的增量更新算法研究摘要随着数据库的不断变化，关联规则的增量更新变得尤为重要。为了更好的对关联规则进行有效的更新，本文对已经提出的经典的关联规则更新算法FUP和IUA算法进行分析，指出其优缺点；最后对另外的改进算法，做一个简单的叙述。关键词数据库；关联规则；增量更新关联规则反映了数据库中数据项目之间有趣的关联关系，而其中发现频繁项目集是关联规则挖掘应用中的关键技术和步骤。关于频繁项目集的挖掘算法研究，人们对此进行了大量的工作，其中以R.Agra}是m个不同项目的集合，给定一个事务数据库D，其中D每一个事务T是I中一组项目的集合，即TI，T

2、有一个惟一的标志符TID。如果对于I中的一个子集X，有XT，我们就说一个事务T包含X。一条关联规则(associationrule)就是一个形如X=>Y的蕴涵式，其中X，YT，而X∩Y=Φ。关联规则成立的条件是：①它具有最小支持度s，即事务数据库D中至少有s%的事务包含X∪Y；②它具有最小可信度c，即在事务数据库D中包含X的事务中至少有c%同时也包含Y。给定一个事务集D，挖掘关联规则问题就是产生支持度和可信度分别大于用户给定的最小支持度和最小可信度的关联规则，也就是产生强规则的问题。关联规则的挖掘问题可以分解为以下两个问题：(1)找出事务

3、数据库中所有具有用户最小支持度的项目集。具有用户指定最小支持度的项目集称为频繁项目集，反之称为非频繁项目集。一个项目中所含项目的个数称为该项目的长度。(2)利用频繁项目集生成关联规则。对于每一个频繁项目集A，若BA，B≠Φ，且support(A)/support(B)>minconf，则有关联规则B=>(A-B)。目前大多数的研究主要集中在第一个问题上面。2Apriori核心算法[1]AgraotwaniR，和SilversteinC提出的FUP2算法是一个同时考虑第一个问题与第二个问题的算法。第三类问题则有冯玉才、冯剑琳提出的算法

4、IUA和PIUA[7]。下面给出两个比较经典算法：FUP和IUA算法的基本思想，并分析了各自的优缺点。3.1FUP算法的基本思想对任意一个k(k≥1)项集，若其在DB和db中都是频繁项集，则其一定是频繁项集；若其在DB和db中都是非频繁项集，则其一定是非频繁项集；若其仅在DB(db)中是频繁项集，则其支持计数应加上其在db(DB)中的支持数以确定它是否为频繁项集。FUP算法假设在DB中发现的频繁项集(n为L中最大元素的元素个数)已被保存下来。它需要对DB和db进行多次扫描，在第一次扫描中，算法先扫描db，将L1中的元素仍为db∪DB中的频繁项集

5、的元素记入L1′，并生成候选频繁1项集C1，C1中的元素为db中的频繁1项集且不包含在L1中；然后扫描DB以决定C1中的元素是否为db∪DB中的频繁项集，并将是db∪DB中的频繁项集的元素记入L1′中。在第k(k>1)此扫描前，先对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中的频繁项集的元素记

6、入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的挖掘结果，但是在对新的数据库

7、进行更新时，又需要重复的扫描原数据库DB，对候选集进行模式匹配，因为原数据库集DB相对增加的数据集db是很大的，所以在利用FUP算法对关联规则进行更新时，会消耗大量时间处理规模巨大的候选集，浪费了时间。3.2IUA[3]算法基本思想算法IUA采用了一个独特的候选频繁项集生成算法iua_gen，在对每一次对数据库DB扫描之前生成较小的候选频繁项集，从而提高了算法的效率。它也要求上一次对数据库DB进行采掘时发现的频繁项集(n为L中最大元素的元素个数)在本次挖掘时是可使用的。因为人们在发现关联规则时，常常需要不断地调整最小支持度和最小可信度来聚集到那

8、些真正令其感兴趣的关联规则上，因而该算法具有很重要的意义。IUA算法的基本框架也和Apriori算法一致，也需要对交易数据库DB进行多趟扫描.因为有s