資源描述：
《基于fp-tree的多層關(guān)聯(lián)規(guī)則挖掘算法研究》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。
1、重慶大學(xué)碩士學(xué)位論文中文摘要摘要數(shù)據(jù)挖掘是從大量數(shù)據(jù)中發(fā)現(xiàn)潛在的、有趣的知識的過程，是解決“數(shù)據(jù)豐富，知識貧乏”狀況的有效方法。關(guān)聯(lián)規(guī)則挖掘用于從大量數(shù)據(jù)中揭示項(xiàng)集之間的有趣關(guān)聯(lián)或相關(guān)聯(lián)系，是數(shù)據(jù)挖掘的一項(xiàng)重要研究內(nèi)容，在現(xiàn)實(shí)生活中有著廣泛的應(yīng)用。根據(jù)規(guī)則集所涉及的抽象層的多少，關(guān)聯(lián)規(guī)則可分為單層關(guān)聯(lián)規(guī)則和多層關(guān)聯(lián)規(guī)則。與單層關(guān)聯(lián)規(guī)則挖掘相比，多層關(guān)聯(lián)規(guī)則能夠提供更加豐富、更具普遍意義的知識，能夠滿足更多用戶的需求，因此對多層關(guān)聯(lián)規(guī)則挖掘進(jìn)行研究具有較大的實(shí)用價(jià)值。已有的多層關(guān)聯(lián)規(guī)則挖掘算法如Cumulate算法、ML－T2L1算法，都是通過對Apr
2、iori算法進(jìn)行擴(kuò)展得到的。這些算法仍采用候選生成并驗(yàn)證的方式得到頻繁模式，該方式會在以下兩個方面產(chǎn)生較大的開銷：(1)需要反復(fù)地掃描數(shù)據(jù)庫，這會導(dǎo)致巨大的I/O開銷；(2)需要產(chǎn)生大量的候選項(xiàng)集，并通過模式匹配來檢查這些候選項(xiàng)集的頻繁性，這會產(chǎn)生巨大的計(jì)算開銷。因此這些算法的效率較低。FP_Growth算法是一個高效的單層關(guān)聯(lián)規(guī)則挖掘算法，它不需產(chǎn)生候選項(xiàng)集且只需掃描兩遍數(shù)據(jù)庫，有效地克服了Apriori算法的缺點(diǎn)，因此該算法的效率較Apriori算法有了大幅提高。通過對FP_Growth算法進(jìn)行擴(kuò)展，本文提出了一個高效的多層關(guān)聯(lián)規(guī)則挖掘算法MLA
3、R-FP。MLAR-FP算法采用的擴(kuò)展措施如下：(1)在掃描數(shù)據(jù)庫的過程中通過把每個項(xiàng)的全部祖先加入到事務(wù)中對每條事務(wù)進(jìn)行擴(kuò)充，該措施能夠確保得到多層關(guān)聯(lián)規(guī)則；(2)通過及時(shí)刪除概念層次樹中不是頻繁項(xiàng)的祖先項(xiàng)來壓縮搜索空間，提高挖掘效率；(3)避免產(chǎn)生冗余的頻繁模式。為了驗(yàn)證MLAR-FP算法的正確性和高效性，作者在某醫(yī)藥公司的銷售數(shù)據(jù)上對其進(jìn)行了實(shí)驗(yàn)，并和Cumulate算法進(jìn)行了對比。實(shí)驗(yàn)表明MLAR-FP算法是正確的，并繼承了FP_Growth算法運(yùn)行效率高的優(yōu)點(diǎn)。MLAR-FP算法使用分治策略挖掘頻繁模式，因此該算法具有潛在的并行性。根據(jù)這個
4、特點(diǎn)本文提出了針對工作站集群環(huán)境的并行MLAR-FP算法，此算法采用的并行模型為粗粒度的主/從模型，并行策略為數(shù)據(jù)并行?？紤]到各個計(jì)算節(jié)點(diǎn)處理能力的不同，算法使用動態(tài)分配數(shù)據(jù)的方式來平衡各個節(jié)點(diǎn)的負(fù)載。關(guān)鍵詞：多層關(guān)聯(lián)規(guī)則，F(xiàn)P_Growth算法，MLAR-FP算法，并行計(jì)算I重慶大學(xué)碩士學(xué)位論文英文摘要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)
