基于有向圖的關(guān)聯(lián)規(guī)則挖掘研究與改進(jìn).pdf

1、關(guān)聯(lián)規(guī)則挖掘是數(shù)據(jù)挖掘中的重要方法，目前主流的關(guān)聯(lián)規(guī)則挖掘算法有Apriori算法、Eclat算法、Fp-growth算法等。上述算法存在如下問題:(1) Apriori算法存在大量I/O操作以及生成大量的候選項集;(2)對于Eclat算法，當(dāng)事務(wù)數(shù)據(jù)庫很大時，垂直數(shù)據(jù)結(jié)構(gòu)無法存儲于內(nèi)存。當(dāng)事務(wù)數(shù)據(jù)庫中事務(wù)數(shù)很大時，tid-set長度很大，tid-set求交時間增加，算法性能下降;(3) Fp-growth算

2、法需要頻繁的構(gòu)造條件模式基，且當(dāng)支持度閾值較小時，F(xiàn)p-tree的壓縮能力有所下降，大量的冗余的存在使得算法性能開始下降。本文基于上述問題研究若干新技術(shù)來提升關(guān)聯(lián)規(guī)則挖掘的效率。
　　首先，本文通過閱讀大量文獻(xiàn)，研究已有算法的優(yōu)缺點和思想方法，提出新的數(shù)據(jù)結(jié)構(gòu)PE Graph圖:用有向圖壓縮存儲事務(wù)數(shù)據(jù)庫，能夠用于快速搜索頻繁項集;Tid-tree樹:用類Fp-tree對tid-set重新編碼，實現(xiàn)垂直數(shù)據(jù)結(jié)構(gòu)的高度壓縮，大大減小

3、了tid-set求交時間;MP-tree樹:通過頻繁路徑后綴實現(xiàn)PE_Graph圖路徑擴(kuò)展的高效剪枝。
　　接著，本文提出了頻繁項集挖掘算法并對其進(jìn)行了一系列的改進(jìn):(1)基于FPE_Graph圖和Tid-tree樹提出了兩個新的頻繁項集挖掘算法PF_search算法和PR_search算法。理論分析及實驗結(jié)果表明PF_search算法和PR_search算法存在大量的冗余路徑擴(kuò)展，且PR_search算法采用的逆向深度搜索策略優(yōu)

4、于PF_ search算法采用的正向深度搜索策略，同時提出了FPE_Graph圖的錐形分布假設(shè)。(2)為了對(1)中存在的冗余路徑進(jìn)行有效的剪枝，本文提出了新的數(shù)據(jù)結(jié)構(gòu)MP-tree樹，基于該樹設(shè)計出了K路剪枝Fp-search算法，本文通過頻繁率來刻畫算法的剪枝性能，通過理論分析可以得出K路剪枝的剪枝能力θ的理論值，從而量化了剪枝能力的評估，有效的證明算法剪枝性能和指導(dǎo)算法的改進(jìn)。盡管K路剪枝Fp-search算法的時間性能非常優(yōu)秀，

5、但是它帶來了額外的空間消耗，即MP-tree的空間規(guī)模O（N)（N為所有頻繁項集的個數(shù)），當(dāng)N值較大時，算法剪枝空間復(fù)雜度較高。(3)基于(2)中存在的問題，提出了減小剪枝空間復(fù)雜度的混合剪枝算法Fpmix2_search算法、Fpmixk_search算法，混合剪枝算法在保證時間性能的同時，大大降低了剪枝帶來的額外空間消耗，但混合剪枝存在性能受節(jié)點劃分方式的影響，且不適合并行化等缺點。(4)基于(3)中的問題，本文提出了新的算法FNM

6、P-search算法，該算法剪枝空間復(fù)雜度極小，且能夠?qū)崿F(xiàn)高效的剪枝。(5)最后實現(xiàn)了Fp-search系列算法的并行化算法（本文稱PF_search算法、PR_search算法、K路剪枝Fp-search算法、Fpmix2_search算法、Fpmixk_search算法、FNMP-search算法為Fp-search系列算法）。
　　最后，通過五個經(jīng)典的真實數(shù)據(jù)集對Fp-search系列算法性能有效性和高效性進(jìn)行驗證實驗表明，