基于抽样的分布式关联规则挖掘算法

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

1、郑州大学硕士学位论文基于抽样的分布式关联规则挖掘算法姓名：李梅花申请学位级别：硕士专业：计算机软件与理论指导教师：王黎明20060501郑州人学坝I‘学位论史摘要数据挖掘是指从巨量数据中获取有效的、新颖的、潜在有用的、最终可理解的模式的非平凡过程，其目的就是要从大量数据中找出有意义的模式，因此具有』“泛的应用价值。在数据挖掘的研究中，如何高效的发现满足用户要求的关联规则已经成为⋯个核心问题。抽样是指选取给定数据库D的随机样本s，在s中而不是在D中进行数据挖掘。抽样方法比较适合于对大型数据库的挖掘。分布式情况下，各站点拥有的数据量较大时，可以采用抽样方法在

2、各站点随机抽样获得样本集，将这些随机样本的挖掘结果作为对整个分布式数据库挖掘的结果．提高挖掘的效率。动态项集计数技术将数据库划分为标记开始点的块，不像A谢。州又在每次扫描之前确定新的候选，在这种变形中，可以在任何开始点添加新的候选集。该技术动态地评估已被计数的所有项集的支持度，如果一个项集的所有子集已被确定为频繁的，则添加它作为新的候选，结果算法需要的数据库扫描比Apriori少，减轻了I／o负载，提高了挖掘的效率。影响分布式数据挖掘效率的主要因素是分布式数据库中各节点问的通信量。元学习的概念是由Prodromidis等人于2000年首先提出的，该方法采

3、用集成学习(eIlselIlbleleanlin曲的方式来生成最终的全局预测模型。其优点在于：在基学习阶段，各个结点可以自主地选择合适的学习算法来生成局部的基分类器(basedassmcrs)与此同时各结点问不存在任何通讯与同步开销，因此系统中各结点问的通信量较少，效率较高。山二元关系导出的概念格作为～种非常有用的形式化工具，体现了概念内涵和外延的统一，反映了对象和特征嵋J的联系以及概念的泛化与例化关系。在挖掘规则知识过程中，规则本身是用内涵集之间的关系来描述，而体现于相应外延集之删的包含关系。而由于概念格节点之问的关系体现了概念之间泛化和例化关系，因此

4、非常适合作为规则发现的纂础性数据结构。本文详细介绍了关联规则挖掘的基本概念和相关技术，结合动态项集计数和抽样的思想，利用元学习策略来产，之频繁项集，提出了一个分布式关联规则挖掘郑州人学颂J．学位论文算法DAsM；引进了相似度的概念，并用之提高了挖掘结果的精确度。理论分析以及实验均表明，DASM算法具有较高的挖掘效率和较低的通信量，适用于对效率要求较高的应用领域。此外，介绍了概念格和关联规则发现之间的关系，描述了对于分布式环境下利用概念格理论、抽样方法进行关联规则提取的解决方法，并给出了一个利用概念格提取无冗余关联规则的分布式算法DSCL算法。我们的创新点

5、在于：1．将动态项集计数方法和抽样方法相结合，解决了关联规则挖掘算法I／o负载过重的问题，可以很好地满足对效率比完备性要求更高的应用领域的需要。2．在分布式算法中，使用元学习分布式策略，使分布式挖掘规则的过程中的通信量仅和产生的频繁项集个数相关，减少了分布式系统中各站点问的通信量，解决了目前分布式算法通信量较大的问题。3．将概念格和抽样方法相结合，利用概念格的特性避免了在发现规则的过程中需要多次扫描数据库的问题，并使用抽样方法减少了数据量，进一步减少了I，o负载，提高了算法的挖掘效率。另外，应用概念格内涵缩减的性质可以得到无冗余的关联规则，解决了分布式算

6、法生成规则冗余较大的问题。4．引入了相似度的定义，并且用之提高了使用抽样进行关联规则挖掘的精确度。关键词：分布式关联规则挖掘，抽样，元学习，相似度，概念格II郑州人学坝I‘学位论文ABSTRACTDataMiningisanonmvialpmcessingoffindingpattemsf硒mverylargedal，lbase．111eSepattemsarce毹diVe，noVel，potentialusc彻and印prehensible．TheobjectofDMisto矗ndsi嘶ficativepattemsinlargcdatacollect

7、ions，soithasextensiVeapplicdcost．InthesttldyofDataMin舀ithaSbeenacorcisSuehowtofindtheasSociate九Ilest11砒satjs母tlsefs’necde伍cjentlyChoosingtherandoms姐IpleS舶mmedatab船eD，s锄plingistheprocessionofminmgintlles锄plesinsteadofinthedatab器eD．S枷plingmemodissuitablef-ortlleminingtola唱edatab船e．

8、hldis砸butiVecase，wh饥thedataVolumepossess