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

1、數(shù)據(jù)挖掘是從大量數(shù)據(jù)中發(fā)現(xiàn)潛在的、有趣的知識的過程，是解決“數(shù)據(jù)豐富，知識貧乏”狀況的有效方法。關聯(lián)規(guī)則挖掘用于從大量數(shù)據(jù)中揭示項集之間的有趣關聯(lián)或相關聯(lián)系，是數(shù)據(jù)挖掘的一項重要研究內容，在現(xiàn)實生活中有著廣泛的應用。根據(jù)規(guī)則集所涉及的抽象層的多少，關聯(lián)規(guī)則可分為單層關聯(lián)規(guī)則和多層關聯(lián)規(guī)則。與單層關聯(lián)規(guī)則挖掘相比，多層關聯(lián)規(guī)則能夠提供更加豐富、更具普遍意義的知識，能夠滿足更多用戶的需求，因此對多層關聯(lián)規(guī)則挖掘進行研究具有較大的實用價值。

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

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

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