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

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

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

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

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

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

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