关联规则数据挖掘中经典频集算法改进的研究

《关联规则数据挖掘中经典频集算法改进的研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、天津大学硕士学位论文关联规则数据挖掘中经典频集算法改进的研究姓名：王烁申请学位级别：硕士专业：计算机应用指导教师：孟昭鹏20030501摘要本文从关联规则的现实意义谈起，充分说明了关联规则研究的必要性以及巨大的社会和商业意义。关联规则的频集算法自从1993由RakeshAgrawal和RamakrishnanSkrikant提出之后，已经经历了十年的研究历程，并已成为数据挖掘的重要分支之一。为了知识的关联性，本文对KDD(KnowledgeDiscoveryinDatabases，数据库中的知识发现)、数据挖掘(DataMining)和关联规则(AssociationRules)等概念也作

2、了阐述，为深入讨论作了充分的准备。本文的重点在于对经典频集算法改进的研究上。因此，通过对经典频集算法(Apriori算法)作了详细的阐述之后，重点研究了两方面的改进策略，并采用了面向对象的JAvA技术来实现了改进中的具体细节。一方面，从理论上论证了减小候选集Ck的大小对提高整个算法效率有着明显的贡献。另一方面，利用哈希树来存储数据项集，以实现对候选项目集的快速计数。首先从理论上阐述了利用哈希树这一传统数据结构在新的具体问题中的应用。然后把抽象的理论问题转化为了面向对象编程中的实际问题来解决：分别从哈希树的构建、元素(中间节点和叶节点)的添加、以及哈希树遍历等方面把整体问题进行分化解决。为了

3、验证我们的改进是行之有效的。我们选择了两个数据库作为测试试验床。一方面，我们采用了一种行之有效的人工合成测试数据的算法，自行产生了一个测试数据库来模拟真实的数据库试验床。另一方面，我们选择了来自www．microsoft．com的匿名用户访问日志作为真实的测试数据源。通过将该数据库进行了有效的改进(例如，删去无用数据项和调整试验数据与算法程序的应用接口等。)使其满足我们的试验要求。基于不同的数据试验床，我们针对多种不同的情况对改进后的算法进行了测试。在挖掘关联规则的同时，还得到了一系列重要的测试数据。比如，当固定信任度的时候，在支持度不断增加的情况下，会得到一系列的不同的频集、关联规则、以

4、及不同的运行时间。通过对这些试验数据的分析，得出了改进算法的稳定收敛的结论。并在这一前提下，我们还将老算法和改进算法进行了比较，充分的说明了改进算法的性能优势。关键字：关联规则，Apriori算法，频集，候选集——』迎!r兰!AbstractThepaperbeginswiththepracticalmeaningoftheAR(AssociationRules)．WefullydiscussthenecessaryoftheresearchinARandtalkabouttheimportantinfluenceofARinthesocietyandthecommerce．ARhassp

5、ent10一yearresearchsinceitwasputfo九ⅣardbyRakeshAgrawalandRamakrishnanSkrikantandhasbecomeoneofimportantbranchesintheDataMingworld。Fortheknowledge’Srelationship，wehaveadeepdiscussionontheKDD(KnowledgeDiscoveryinDatabases)，DataMiningandAssociationRules．Theyarethebaseforthefurtherwork．Thehighlightofth

6、epaperistheresearchoftheimprovedclassicFrequentSetAlgorithm．AftertalkingaboutthedetailsinclassicFrequentSetAlgorithm(AprioriAlgorithm)．wefocusonthetwoimprovedstrategiesandemploythejAvAOOPtechniquetoachievethedetailsinthealgorithm．Ononeside，wetheoreticallyprovethemethodthatreducingtheCandidateSet(c

7、k)Canbehigh-powered．Ontheotherside，employtheHashtreetostorethefrequentitems，toachievefastnumbercountofthefrequentitems．First，theoreticallyprovehowtheHashtreecanbeusedinthenewproblems．Then，changetheabstracttheoret