基于前綴樹Tire的關聯(lián)規(guī)則挖掘算法研究.pdf

1、關聯(lián)規(guī)則挖掘是數(shù)據(jù)挖掘領域中的一個重要問題，它在商業(yè)領域的成功應用，使它成為數(shù)據(jù)挖掘中最成熟、最主要的研究內(nèi)容之一．要發(fā)現(xiàn)關聯(lián)規(guī)則，首先需要挖掘頻繁項集，而Tire這種前綴樹數(shù)據(jù)結構能夠高效的存儲頻繁項集.為了加快事務數(shù)據(jù)庫訪問效率，且隨著計算機硬件性能的不斷發(fā)展，計算機主存容量的不斷提升，可以考慮把事務數(shù)據(jù)庫壓縮到內(nèi)存中去.另外，對候選頻繁項集的剪枝一直是提升關聯(lián)規(guī)則挖掘算法效率的重要方式．從這兩個方面圍繞Tire數(shù)據(jù)結構進行的關聯(lián)規(guī)

2、則算法研究對目前和將來的研究工作具有重要的實際意義和廣泛的應用前景.
　　 本文首先介紹了關聯(lián)規(guī)則的基本概念和關聯(lián)規(guī)則挖掘算法一般分類，寬度優(yōu)先挖掘算法和深度優(yōu)先挖掘算法．并以具體事務數(shù)據(jù)庫為例，將其中經(jīng)典的Apriori算法和FP-growth算法從數(shù)據(jù)結構至算法描述作出詳細闡釋，分析比較了兩種算法各自的優(yōu)缺點.
　　 其次，在闡釋了事務數(shù)據(jù)庫的二維數(shù)組壓縮存儲和Tire前綴樹的數(shù)據(jù)結構的基礎上，論文提出了采用壓縮數(shù)據(jù)

3、庫和動態(tài)剪枝的關聯(lián)規(guī)則挖掘算法CDDP，該算法使用一種二維數(shù)組壓縮原數(shù)據(jù)庫，同時借鑒了頻繁項集挖掘算法DF中的頻繁項集Tire樹存儲思想，在Tire樹構建過程中，利用Tire樹性質(zhì)進行動態(tài)剪枝，縮減候選頻繁項集數(shù)量.在關聯(lián)規(guī)則挖掘階段，提出了Tire樹中頻繁項集的查找算法．討論了算法實現(xiàn)過程中的一些細節(jié)問題，對算法的時空復雜度分析結果表明算法在長模式數(shù)據(jù)集上具有良好的時空效率．
　　 最后，在詳細介紹了關聯(lián)規(guī)則算法實驗人工數(shù)據(jù)合

4、成器的基礎上，選取兩個人工合成數(shù)據(jù)集和兩個自然世界中的真實數(shù)據(jù)集，將CDDP算法與DF算法和Apriori算法一起進行對比實驗，實驗結果表明CDDP算法有自己擅長數(shù)據(jù)集類型．與DF算法相比，CDDP的動態(tài)剪枝算法在處理頻繁單項集穩(wěn)定，以長模式為主的數(shù)據(jù)集時，效率極高；而DF算法的剪枝方法在超市型的數(shù)據(jù)集時(也就是存在很多短模式和大量頻繁單項集的數(shù)據(jù)庫)，具有一定的優(yōu)勢．而與Apriori算法相比，CDDP算法在任何類型的數(shù)據(jù)集上具有明顯