基于fp-tree的多层关联规则挖掘算法研究

《基于fp-tree的多层关联规则挖掘算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、重庆大学硕士学位论文中文摘要摘要数据挖掘是从大量数据中发现潜在的、有趣的知识的过程，是解决“数据丰富，知识贫乏”状况的有效方法。关联规则挖掘用于从大量数据中揭示项集之间的有趣关联或相关联系，是数据挖掘的一项重要研究内容，在现实生活中有着广泛的应用。根据规则集所涉及的抽象层的多少，关联规则可分为单层关联规则和多层关联规则。与单层关联规则挖掘相比，多层关联规则能够提供更加丰富、更具普遍意义的知识，能够满足更多用户的需求，因此对多层关联规则挖掘进行研究具有较大的实用价值。已有的多层关联规则挖掘算法如Cumulate算法、ML－T2L1算法，都是通过对Apr

2、iori算法进行扩展得到的。这些算法仍采用候选生成并验证的方式得到频繁模式，该方式会在以下两个方面产生较大的开销：(1)需要反复地扫描数据库，这会导致巨大的I/O开销；(2)需要产生大量的候选项集，并通过模式匹配来检查这些候选项集的频繁性，这会产生巨大的计算开销。因此这些算法的效率较低。FP_Growth算法是一个高效的单层关联规则挖掘算法，它不需产生候选项集且只需扫描两遍数据库，有效地克服了Apriori算法的缺点，因此该算法的效率较Apriori算法有了大幅提高。通过对FP_Growth算法进行扩展，本文提出了一个高效的多层关联规则挖掘算法MLA

3、R-FP。MLAR-FP算法采用的扩展措施如下：(1)在扫描数据库的过程中通过把每个项的全部祖先加入到事务中对每条事务进行扩充，该措施能够确保得到多层关联规则；(2)通过及时删除概念层次树中不是频繁项的祖先项来压缩搜索空间，提高挖掘效率；(3)避免产生冗余的频繁模式。为了验证MLAR-FP算法的正确性和高效性，作者在某医药公司的销售数据上对其进行了实验，并和Cumulate算法进行了对比。实验表明MLAR-FP算法是正确的，并继承了FP_Growth算法运行效率高的优点。MLAR-FP算法使用分治策略挖掘频繁模式，因此该算法具有潜在的并行性。根据这个

4、特点本文提出了针对工作站集群环境的并行MLAR-FP算法，此算法采用的并行模型为粗粒度的主/从模型，并行策略为数据并行。考虑到各个计算节点处理能力的不同，算法使用动态分配数据的方式来平衡各个节点的负载。关键词：多层关联规则，FP_Growth算法，MLAR-FP算法，并行计算I重庆大学硕士学位论文英文摘要ABSTRACTDataminingisaprocesstoreaveallatentandinterestingknowledgefrommassivedata,andaneffectiveapproachtosolvetheproblemof“r

5、ichdataandpoorknowledge”.Associationrulesminingcanrevealinterestingcorrelationsbetweenitemsetsfrommassivedata.Itisanimportantsubjectofdataminingandiswidelyusedinreallife.Accordingtothenumberofhierarchiesinvolvedinrules,associationrulescanbeclassifiedintosingle-levelassociationr

6、ulesandmulti-levelassociationrules.Comparedwithsingle-levelassociationrules,multi-levelassociationrulescanprovidericherandmoregeneralizedknowledge,andmeetwithmoreusers’requirements,soitisofgreatpracticalvaluetostudyMulti-levelassociationrulesmining.Theproposedalgorithmsforminin

7、gmulti-levelassociationrulessuchasCumulatealgorithm,ML_T2L1algorithmarebasedonApriorialgorithm.Thesealgorithmsstilladopt“candidategenerateandtest”methodtogetfrequentpatternswhichcauselargecostintwoaspects:(1)I/Ocost.Inthesealgorithms,thedatabaseisneededtoscanktimes(kisthelarges

8、tlengthofthecandidates),whichresultsinlargeI/Ocost;(2)