单调和反单调约束条件下关联规则的挖掘算法分析

《单调和反单调约束条件下关联规则的挖掘算法分析》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、万方数据计算机科学2005Voi．32N9．6单调和反单调约束条件下关联规则的挖掘算法分析¨杜剑峰李宏陈松乔陈建二(中南大学信息科学与工程学院长沙410083)摘要本文充分利用了Eclat算法的概念格理论和等价类划分方法，将约束冬件融入基于垂直数据分布的关联规则挖掘算法中。提出了一种新的反单调和单调约束条件下关联规则的挖掘算法，分别为EclatA算法和EclatM算法。算法采用自底向上的搜索方法，在发现频繁项集的同时进行约束条件的检验。数据库的扫描次数较少，无需对候选项集进行剪枝，占用内存较小。实验证明：该算法的执行效率

2、比已有算法有显著提高。关键词数据挖掘，约束性关联规则，概念格，等价类AlgorithmAnalysisforAnti-monotoneandMonotoneConstraintsAssociationRulesMiningDUJian——FengLIHongCHENSong—-QiaoCHENJian。-Er(CollegeofInformationEngineering，CentralSouthUniversity，Changsha410083)AbstractAnti—monotoneandmonotoneconst

3、raintsareintegratedintothealgorithmofassociationrulesminingbasedOnverticaldatalayoutbyutilizingthelatticestheoryandthedecomposingmethodofequivalenceclassessuffi—ciently．Twonewalgorithmsarealsopresented．Oneisbasedonanti—monotoneconstraintnamedEclatA．Theotherisbase

4、donmonotoneconstraintnamedEclatM．Abottom～upsearchmethodisputforwardandtheconstraintsarecheckedattheprocessofcalculatingfrequentitemsets．Thenewalgorithmsscanthedatabasefewtimesandhavenoneedofpruningcandidateitemsets．Atthesametime，theycaD-besolvedinmemory．Resultsfr

5、omourexperimentsshowthattheperformanceofthenewalgorithmsisunmatchedbyanypreviousalgorithmsKeywordsDatamining，Associationruleswithconstraints，Lattices，Equivalenceclasses1引言近几年来，随着关联规则的理论与实际相结合的不断发展，基于约束的关联规则挖掘算法成为了研究的热点。约束关联规则挖掘算法能够从大量的频繁项集中筛选出有用的规则，提高挖掘效率。目前，应用最广

6、泛的约束主要包括反单调约束和单调约束。典型的基于单调和反单调约束条件下的关联规则挖掘算法是基于Apriori算法[2]的CAP算法“3和基于FP—growth算法[3]的约束关联规则挖掘架构CFG一约束频繁模式增长[5。](constrainedfrequentpatterngrowth)。CAP算法将反单调约束分为2种情况：(1)约束条件既是反单调约束，又是简洁性约束，如min(S)≥可；(2)约束条件是反单调约束，但不是简洁性约束，如sum(5)≤口。对于第一种情况，CAP算法仅仅是将Apriori算法中的C，替换为

7、G。C。指候选1一项集，Ci一{ele∈C。8Le∈以(Item)}，即G指满足约束条件c的所有候选1一项集；对于第二种情况，令巴为Apri—ori算法中的候选^一项集，约束条件为C，对于任一项集S￡cl，如果S不满足约束条件C，则将s从c^中删除。也就是说，在扫描数据库进行支持度计数之前，就进行约束条件的检验。在CAP算法中，没有明确提出单调约束的概念。根据Apriori类算法的特点，可以通过一个后处理的步骤对Apri—ori算法的结果进行过滤，也可以通过定义一个弱约束C’的方法解决。CAP算法能够产生完备的满足约束条

8、件的频繁项集，但存在Apriori算法生成的候选频繁项集数目较大和需要重复扫描数据库等缺陷。CFG架构能够根据约束条件将数据库中的项集划分为多个前缀条件数据库，按照频繁模式增长的方法递归发现频繁项集。条件数据库具有下列性质：如果模式a在厂的条件数据库TDBI厂中是频繁的，则ClUf在TDBlf中也一定是频繁的。对于反