基于FP-Tree的多層關(guān)聯(lián)規(guī)則挖掘算法研究.pdf

1、數(shù)據(jù)挖掘是從大量數(shù)據(jù)中發(fā)現(xiàn)潛在的、有趣的知識(shí)的過程，是解決“數(shù)據(jù)豐富，知識(shí)貧乏”狀況的有效方法。關(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ī)則能夠提供更加豐富、更具普遍意義的知識(shí)，能夠滿足更多用戶的需求，因此對(duì)多層關(guān)聯(lián)規(guī)則挖掘進(jìn)行研究具有較大的實(shí)用價(jià)值。

2、 已有的多層關(guān)聯(lián)規(guī)則挖掘算法如Cumulate算法、ML－T2L1算法，都是通過對(duì)Apriori算法進(jìn)行擴(kuò)展得到的。這些算法仍采用候選生成并驗(yàn)證的方式得到頻繁模式，該方式會(huì)在以下兩個(gè)方面產(chǎn)生較大的開銷：(1)需要反復(fù)地掃描數(shù)據(jù)庫，這會(huì)導(dǎo)致巨大的I/O開銷；(2)需要產(chǎn)生大量的候選項(xiàng)集，并通過模式匹配來檢查這些候選項(xiàng)集的頻繁性，這會(huì)產(chǎn)生巨大的計(jì)算開銷。因此這些算法的效率較低。 FP_Growth算法是一個(gè)高效的單層關(guān)聯(lián)規(guī)則挖

3、掘算法，它不需產(chǎn)生候選項(xiàng)集且只需掃描兩遍數(shù)據(jù)庫，有效地克服了Apriori算法的缺點(diǎn)，因此該算法的效率較Apriori算法有了大幅提高。 通過對(duì)FP_Growth算法進(jìn)行擴(kuò)展，本文提出了一個(gè)高效的多層關(guān)聯(lián)規(guī)則挖掘算法MLAR-FP。MLAR-FP算法采用的擴(kuò)展措施如下：(1)在掃描數(shù)據(jù)庫的過程中通過把每個(gè)項(xiàng)的全部祖先加入到事務(wù)中對(duì)每條事務(wù)進(jìn)行擴(kuò)充，該措施能夠確保得到多層關(guān)聯(lián)規(guī)則；(2)通過及時(shí)刪除概念層次樹中不是頻繁項(xiàng)的祖先項(xiàng)來

4、壓縮搜索空間，提高挖掘效率；(3)避免產(chǎn)生冗余的頻繁模式。為了驗(yàn)證MLAR-FP算法的正確性和高效性，作者在某醫(yī)藥公司的銷售數(shù)據(jù)上對(duì)其進(jìn)行了實(shí)驗(yàn)，并和Cumulate算法進(jìn)行了對(duì)比。實(shí)驗(yàn)表明MLAR-FP算法是正確的，并繼承了FP_Growth算法運(yùn)行效率高的優(yōu)點(diǎn)。 MLAR-FP算法使用分治策略挖掘頻繁模式，因此該算法具有潛在的并行性。根據(jù)這個(gè)特點(diǎn)本文提出了針對(duì)工作站集群環(huán)境的并行MLAR-FP算法，此算法采用的并行模型為粗粒