基于最大模式的关联规则挖掘算法研究

《基于最大模式的关联规则挖掘算法研究》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、http://www.elecfans.com电子发烧友http://bbs.elecfans.com电子技术论坛基于最大模式的关联规则挖掘算法研究李超余昭平(解放军信息工程大学电子技术学院，河南郑州450004)E-mail:lichao8141@sina.com摘要：提出了一种基于最大模式的关联规则挖掘算法，探讨了它的实现步骤，最后通过实例说明它是数据挖掘中一种有效的关联规则挖掘算法。关键词：关联规则数据挖掘最大模式中图分类号TP393文献标识码AAMethodofAssociationRulesMiningBasedonMAXItemsetsLiChaoYUZhao-ping(Insti

2、tuteofElectronicTechnology,thePLAInformationEngineeringUniversity,Zhengzhou450004,China)【Abstract】ThepaperintroducesamethodofassociationrulesminingbasedonMAXitemsets.Itputsforwardsomeideasforrealizingsteps.Finally,wefindthatitisaneffectivemethodofassociationrulersminingfromexamples.【keywords】Associa

3、tionrulesDataminingMAXitemsets数据挖掘是从大量数据中提取出可信、新颖、有效并能被人理解的模式的高级处理过程。而关联规则挖掘是数据挖掘中的一个重要课题，其目的是发现大量数据中项集之间有趣的或相关的联系，广泛地应用于商业、金融等多个领域。【1】目前大部分关联规则的挖掘算法都是以Apriori算法为核心。本文提出了一种有效的基于最大频繁项目集的关联规则挖掘算法，较之传统的的Apriori算法，大大提高了算法的效率。1基本概念定义1关联规则设I={i1，i2，…，im}是项的集合，每一个事务有一个标识符，称作TID,设标识符的集合T={1，2，…，n}，则输入的数据库可以

4、看成是一个二元关系π⊆×IT，每个事务X是项的集合，使得X⊆I。设A是一个项集，事务X包含A,当且仅当A⊆X。关联规则是形如A⇒B的蕴涵式，其中AIBI⊂⊂∩，，AB=φ。同时满足最小支持度阈值(min_sup)和最小置信度阈值(min_conf)的规则称作强规则。其中support(A⇒B)=P(A∪B)，表示数据库中事务包含A与B二者的百分比；confidence(A⇒B)=P(BA

5、)，表示数据库中事务包含A的同时也包含B的百分比。定义2频繁项集如果项集满足最小支持度，则称它为频繁项集。频繁项集具有反单调（anti-monotone）的性质，即频繁项集的所有子集都是频繁的，所有真超集都是

6、非频繁的。关联规则的挖掘是一个两步的过程：1）找出所有的频繁项集；2）由频繁项集产生强关联规则。定义3最大模式最大模式是指频繁模式p，使得p的任何真超模式都不是频繁的。q是p的超模式，即q包含p。http://www.elecfans.com电子发烧友http://bbs.elecfans.com电子技术论坛2算法的设计和实现在这一部分，我们采用根据支持度升序排序的方法，并在对项目集进行扩展之前进行剪枝，提出一种高速有效的关联规则挖掘算法（ARuleInductionAlgorithmBasedonFrequentMAXItemsets）。在发现频繁项集的过程中，传统的Apriori算法使用逐

7、层搜索的迭代方法，首先找出频繁1－项集，用于找频繁2－项集，如此下去，直到不能找到频繁k－项集。找每个频繁项集需要扫描一次数据库，它可能需要产生大量的候选项集，也可能需要重复地扫描数据库，通过模式匹配检查一个很大的候选集合。因此如何在搜索过程中对搜索空间进行压缩，成为提高算法效率的一个核心问题。定理设X1×t(X1)和X2×t(X2)是两项目集和事务集对，max为最大项集符，则它们满足下面的性质：（1）若count(t(X1)∩t(X2))>=min_sup，则max(X1∪X2)＝max(X1)＝max(X2)；（2）若count(t(X1)∩t(X2))

8、2)≠max(X1)。证明：如果count(t(X1)∩t(X2))>=min_sup，而t(X1∪X2)＝t(X1)∩t(X2)，从而有count(t(X1∪X2))>=min_sup，故max(X1∪X2)＝max(X1)＝max(X2)。同理可证，（2）也是成立的。2.1算法的设计思想根据定理我们可以发现，如果已经得到项目集X1，需要将其与X2合并，如果它们满足（1），就可以直接用X1∪X2