基于有向圖的關(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算法等。上述算法存在如下問(wèn)題:(1) Apriori算法存在大量I/O操作以及生成大量的候選項(xiàng)集;(2)對(duì)于Eclat算法，當(dāng)事務(wù)數(shù)據(jù)庫(kù)很大時(shí)，垂直數(shù)據(jù)結(jié)構(gòu)無(wú)法存儲(chǔ)于內(nèi)存。當(dāng)事務(wù)數(shù)據(jù)庫(kù)中事務(wù)數(shù)很大時(shí)，tid-set長(zhǎng)度很大，tid-set求交時(shí)間增加，算法性能下降;(3) Fp-growth算

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

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

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

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

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