資源描述:
《并行關聯(lián)規(guī)則挖掘算法研究及其應用》由會員上傳分享,免費在線閱讀,更多相關內容在學術論文-天天文庫。
1、上海大學2001級碩士研究生畢業(yè)論文摘要數(shù)據(jù)挖掘(DM)和知識發(fā)現(xiàn)(KDD)是從數(shù)據(jù)庫中抽取、識別出有效的、新穎的、有潛在作用的、可信的、并能最終被人理解的模式的非平凡處理過程。它適用于所有存在數(shù)據(jù)積累的領域。關聯(lián)規(guī)則挖掘是數(shù)據(jù)挖掘的主要模式之一,但是由于當今的數(shù)據(jù)庫的量非常之大,在單機上進行關聯(lián)規(guī)則挖掘顯得力不從心,隨著機群計算機的出現(xiàn),為進行并行關聯(lián)規(guī)則挖掘提供了可能.本文將研究并行關聯(lián)規(guī)則挖掘算法,并提出一種無候選集生成的并行關聯(lián)規(guī)則挖掘算法,并將該并行關聯(lián)規(guī)則挖掘算法應用于電梯歷史數(shù)據(jù)領域。并行關聯(lián)規(guī)則的挖掘
2、分為二步:首先挖掘出所有全局頻繁項集(根據(jù)給定最小支持度);然后生成所有強關聯(lián)規(guī)則(根據(jù)給定最小置信度)。己有的并行挖掘算法都集中在對第一步問題的解決上,這些并行算法所采用的都是基于Apriori思想,即各個處理機各自對本地的數(shù)據(jù)庫進行掃描,并利用全局頻繁項集Lk一產生候選項集Ck,接著計算各候選項的局部支持數(shù),在各處理機之間交換支持數(shù)得到各候選項的全局支持數(shù),最終生成全局頻繁K項集Lk。這些算法存在的缺點是有大量的候選項生成,增加了通訊量,同時也需要多次掃描數(shù)據(jù)庫,增加了1/0消耗。本文提出了一種基于頻繁模式樹的并
3、行挖掘算法,它的思想是:首先每個處理機掃描本地數(shù)據(jù)庫并相互交換所有1一項集的支持數(shù)得到全局頻繁1一項集Flist,再根據(jù)Flist將本地的數(shù)據(jù)庫壓縮成一棵頻繁模式樹;各處理機從各自的FPT中得到每個頻繁1一項的局部條件模式基,并通過交換在指定處理機上得到該1一項的全局條件模式基;各處理機對其上的全局條件模式基構造條件頻繁模式樹并挖掘出以該1一項為尾的所有頻繁項集。該算法的優(yōu)點是無需生成候選項集,這就避免了多次掃描數(shù)據(jù)庫各候選項進行計數(shù),減少了1/0消耗:同時只通過交換各1一項的條件模式基,相應地通訊量也大減少了。實驗
4、也證明了該算法的高效性。此外,將該算法注冊到基于機群計算機的并行數(shù)據(jù)挖掘平臺的算法庫中,并應用到電梯數(shù)據(jù)集,挖掘出了電梯維護數(shù)據(jù)之間的有價值的規(guī)則,對經營者的分析和決策提供有益的幫助和指導。本研究得到到國家自然科學基金項目‘60275022)和上海市科學技術基金項目(01JC14022)資助。關鍵字:數(shù)據(jù)挖掘關聯(lián)規(guī)則機群計算機頻繁模式樹第V火上海大學2001級碩士研究生畢業(yè)論文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