高效的关联规则挖掘算法研究

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

1、第29卷第24期计算机工程与设计2008年l2月Vo1．29No．24ComputerEngineeringandDesignDec．2008高效的关联规则挖掘算法研究陈波，邵勇，王成华，董鹏(1．大连大学信息工程学院，辽宁大连l16622；2．华能日照发电厂，山东日照276826)摘要：目前已经提出了许多用于高效地发现大规模数据库中的关联规则的算法，但都是对关联规则中满足最小支持度的频繁项集的研究，没有对频繁项集中如何高效地计算得到满足最小置信度的关联规则进行研究。针对这种情况，提出了一种高效关联规则的挖掘算法EA，解

2、决了在挖掘关联规则过程中如何高效挖掘满足最小置信度的关联规则问题关键词：频繁项集；数据挖掘；置信度；关联规则；EA中图法分类号：TP311文献标识码：A文章编号：1000．7024(2008)24—6240—03ResearchonhigheficientalgorithmforminingassociationrulesCHENBo，SHAOYong，WANGCheng—hue，DONGPeng(1．InstituteofInformationEngineering，DalianUniversity,Dalian116

3、622，China；2．RizhaoPowerPlant，Rizhao276826，China)Abstract：Currently,lotsofalgorithmsforeficientlyminingassociationrulesinlargedatabaseareproposed．However，allofthemresearchintofrequentitemsetwhichsatisfytheminimumsupportforminingassociationrules，nooneresearchesinto

4、associationruleshowtoefectivelycalculatetosatisfytheminimumconfidence．Underthiskindofsituation．adataminingalgorithmEA(eficienta1．gorithm)isproposed，whichcanfastcalculatetheconfidenceinassociationrules，itsolutedthequestionhowtoeficientmineassociationruleswhichares

5、atisfiedwithminconfduringmingingassociationrules．_Keywords：frequentitemset；datamining；confidence；associationrules；EA足最小置信度，那么对频繁项集查询的次数也将是一个海量数0引言据。为了解决这个问题，提出了一种高效计算置信度的算法。数据挖掘就是从数据库中发现知识(knowledgediscovery1问题描述indatabase，KDD“)，它是运用某种算法从海量数据中挖掘出知识的过程。由Argrawal等首

6、先在文献中提出了挖掘关联规则关联规则挖掘问题的形式化描述如下：设，={f2，⋯，i}的Apriori算法，这个算法通过对事务数据库TDB的多次扫是项的集合。设与任务相关的数据TDB(transactiondatabase)面来产生频繁项集。针对Apfiofi算法存在的问题，Park等人是数据库事务的集合，其中每个事务71是项的集合，使TC_l。每在文献中提出了基于散列的Hash表快速挖掘算法。朱玉全个事务有一个标识符，称作TID。设A是⋯个项集，事务包含等人提出了基于FP(frequentpattem)增长树的增量挖掘算

7、法，当且仅当AC_T。关联规则是形~NA=B的蕴涵式，其中AC1，还有胡慧蓉的USLIG；高明的MFUP；李健宏的AIUA；宋BCI，并且ANB=。规则在事务TDB中成立，具有支持度海声的UA：皋军的MyIUA：王翔的IUPA“：冯玉才的IUA_S，其中是TDB中事务AuB的百分比，它是概率PUB)。项的和PIUA⋯，所有这些算法都是为了提高在挖掘频繁项集中的集合称为项集(itemset)。包含k个项的项集称为项集。项集效率而进行改进，都没有涉及到置信度的高效计算问题。从前的出现频率是包含项集的事务数，简称为项集的频率支

8、持计对一个频繁项集中的一个关联规则的前件以及(前件u后件)数。如果项集满足最小支持度，则称它为频繁项集。候选支持度都是要多次扫描频繁项集库而得到其置信度，这显然是项集的集合通常记作ck，频繁项集的集合通常记作L，countD低效的。如果一个频繁项集中的项数非常多，就存在组合爆炸表示事务库TDB中的总事务数。设为项集，