并行关联规则挖掘算法研究及其应用

《并行关联规则挖掘算法研究及其应用》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、上海大学2001级硕士研究生毕业论文摘要数据挖掘(DM)和知识发现(KDD)是从数据库中抽取、识别出有效的、新颖的、有潜在作用的、可信的、并能最终被人理解的模式的非平凡处理过程。它适用于所有存在数据积累的领域。关联规则挖掘是数据挖掘的主要模式之一，但是由于当今的数据库的量非常之大，在单机上进行关联规则挖掘显得力不从心，随着机群计算机的出现，为进行并行关联规则挖掘提供了可能.本文将研究并行关联规则挖掘算法，并提出一种无候选集生成的并行关联规则挖掘算法，并将该并行关联规则挖掘算法应用于电梯历史数据领域。并行关联规则的挖掘

2、分为二步:首先挖掘出所有全局频繁项集(根据给定最小支持度);然后生成所有强关联规则(根据给定最小置信度)。己有的并行挖掘算法都集中在对第一步问题的解决上，这些并行算法所采用的都是基于Apriori思想，即各个处理机各自对本地的数据库进行扫描，并利用全局频繁项集Lk一产生候选项集Ck，接着计算各候选项的局部支持数，在各处理机之间交换支持数得到各候选项的全局支持数，最终生成全局频繁K项集Lk。这些算法存在的缺点是有大量的候选项生成，增加了通讯量，同时也需要多次扫描数据库，增加了1/0消耗。本文提出了一种基于频繁模式树的并

3、行挖掘算法，它的思想是:首先每个处理机扫描本地数据库并相互交换所有1一项集的支持数得到全局频繁1一项集Flist，再根据Flist将本地的数据库压缩成一棵频繁模式树;各处理机从各自的FPT中得到每个频繁1一项的局部条件模式基，并通过交换在指定处理机上得到该1一项的全局条件模式基;各处理机对其上的全局条件模式基构造条件频繁模式树并挖掘出以该1一项为尾的所有频繁项集。该算法的优点是无需生成候选项集，这就避免了多次扫描数据库各候选项进行计数，减少了1/0消耗:同时只通过交换各1一项的条件模式基，相应地通讯量也大减少了。实验

4、也证明了该算法的高效性。此外，将该算法注册到基于机群计算机的并行数据挖掘平台的算法库中，并应用到电梯数据集，挖掘出了电梯维护数据之间的有价值的规则，对经营者的分析和决策提供有益的帮助和指导。本研究得到到国家自然科学基金项目‘60275022)和上海市科学技术基金项目(01JC14022)资助。关键字:数据挖掘关联规则机群计算机频繁模式树第V火上海大学2001级硕士研究生毕业论文AbstractDataMiningandKnowledgeDiscoveryinDatabaseisthenontrivialprocess

5、ofidentifyingandextractingvalid,novel,,potentiallyuseful,creditableandultimatelyunderstandablepatterns.Itcanbeappliedinallfieldsthataccumulatedmuchdata.Associationruleisoneofthemostimportantdataminingproblems.Butbecausetoday'sdatabseistremendous,itisimpracticab

6、leonsinglemachinetomineassociationrules.Itispracticaltomineparallellywiththecluster'semerging.Inthepaper,aparallelminingalgorithmwithoutcandidateitemsetsisproposedandappliedtotheelevatorhistorydatafield.Parallelminingrulesisalsodevidedintotwoproblems:first,mine

7、allglobalfrequentitemsetswithminimunsupportdegreegiven;thengenerateallstrongassociationruleswithminimunconfidencedegreegiven.Mostexistparallelminingalogrithmstake呼ideabasedonApriori:eachprocessorgeneratescadidateitemsetsCkthroughcallingalgorithm`AprioriGen(Lk-1

8、)',andscanslocaldatabasetogetloacalcountofeachcadidateitem,andexchangeitscountamongprocessorstogetitsglobalcount,andgenerateglobalfrequentitemsetsLk.Theprocedureisrepeatedun