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

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

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

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

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