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

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

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

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

3、T是I中一组项目的集合，即TI，T有一个惟一的标志符TID。如果对于I中的一个子集X，有XT,我们就说一个事务T包含X。一条关联规则(associatio关联规则的增量更新算法研宄(1)摘要随着数据库的不断变化，关联规则的增量更新变得尤为重要。为了更好的对关联规则进行有效的更新，本文对已经提出的经典的关联规则更新算法FUP和IUA算法进行分析，指出其优缺点；最后对另外的改进算法，做一个简单的叙述。关键词数据库；关联规则；增量更新关联规则反映了数据库中数据项目之间有趣的关联关系，而其中发现频繁项目集是关

4、联规则挖掘应用中的关键技术和步骤。关于频繁项目集的挖掘算法研究，人们对此进行了大量的工作其中以R.Agrawal等人提出的Apriori、AprioriTid等算法最具有影响力和代表性。而这些算法的提出都是在挖掘数据库和最小支持度不变的条件下进行的。但实际中，遇到的情况可能是：随着时间的推移，挖掘数据库的规模可能不断膨胀或需要删除一部分记录，或者需要对最小支持度进行调整从而逐步聚集到我们感兴趣的频繁项目集上。因而如何从数据发生变动后的数据库中高效地对已经推导出的关联规则进行更新，具有非常重要的应用价值

5、，这就是所谓的增量式挖掘关联规则的问题。1关联规则问题描述：设I={il，i2,...，im}是m个不同项目的集合，给定一个事务数据库D，其中D每一个事务T是I中一组项目的集合，即TI，T有一个惟一的标志符TID。如果对于I中的一个子集X，有XT,我们就说一个事务T包含X。一条关联规则(associationrule）就是一个形如X=〉Y的蕴涵式，其中X，YT，而XAY=O。关联规则成立的条件是：①它具有最小支持度s，即事务数据库D中至少有s%的事务包含XUY；②它具有最小可信度c，即在事务数据库D中

6、包含X的事务中至少有c%同时也包含Y。给定一个事务集D，挖掘关联规则问题就是产生支持度和可信度分别大于用户给定的最小支持度和最小可信度的关联规则，也就是产生强规则的问题。关联规则的挖掘问题可以分解为以下两个问题：（1）找出事务数据库中所有具有用户最小支持度的项目集。具有用户指定最小支持度的项目集称为频繁项目集，反之称为非频繁项目集。一个项目中所含项目的个数称为该项目的长度。（2）利用频繁项目集生成关联规则。对于每一个频繁项目集A，若BA,且support（A）/support（B）>minconf,则

7、有关联规则B=〉（A_B）。目前大多数的研究主要集中在第一个问题上面。2Apriori核心算法[1]Agrawal等人于1994年提出了一个挖掘顾客交易数据库中项集间的关联规则的重要方法Apriori算法，其核心是基于两个阶段频繁项集思想的递推算法。算法的基本思想是首先找出所有的频集，这些项集出现的频繁性至少和预定义的最小支持度一样。然后由频繁项集产生强关联规则，这些规则必须满足最小支持度和最小可信度。Apriori核心算法思想筒要描述如下：该算法中有两个关键步骤连接步和剪枝步。（1）连接步：为找出L

8、k（频繁k一项集），通过Lk-1与自身连接，产生候选k-项集，该候选项集记作Ck;其中Lk-1的元素是可连接的。（2）剪枝步：Ck是Lk的超集，即它的成员可以是也可以不是频繁的，但所有的频繁一项集都包含在Ck中。扫描数据库，确定Ck中每一个候选的计数，从而确定Lk（计数值不小于最小支持度计数的所有候选是频繁的，从而属于Lk）。然而，Ck可能很大，这样所涉及的计算量就很大。为压缩Ck,使用Apriori性质：任何非频繁的（k_l）_项集都不可能是频繁k-项