最大頻繁項集挖掘算法的研究.pdf

1、數(shù)據(jù)挖掘技術(shù)自誕生以來就致力于發(fā)現(xiàn)隱藏在數(shù)據(jù)中有價值的信息。隨著大數(shù)據(jù)時代的到來，數(shù)據(jù)挖掘可以將豐富的數(shù)據(jù)變?yōu)橐环N寶貴的資源，其地位變得更是不可小覷。發(fā)現(xiàn)關(guān)聯(lián)規(guī)則是數(shù)據(jù)挖掘工作的重中之重，而挖掘頻繁項集又是尋找關(guān)聯(lián)規(guī)則的主要步驟。但是頻繁項集不僅數(shù)量龐大，還存在信息冗余的問題，因此挖掘最大頻繁項集的任務(wù)應(yīng)運而生。在壓縮頻繁項集的同時，最大頻繁項集也緩解了數(shù)據(jù)存儲的壓力。另外，在Web挖掘、DNA分析等一些應(yīng)用領(lǐng)域內(nèi)，挖掘最大頻繁項集的重

2、要性也是顯而易見的。因此如何提高最大頻繁項集的挖掘效率成為了一個重要的研究方向。
　　本文闡述了挖掘最大頻繁項集的研究背景及意義。通過國內(nèi)外研究現(xiàn)狀發(fā)現(xiàn)，挖掘最大頻繁項集的算法通常是在Apriori和FP-Tree這兩種思想的基礎(chǔ)上進行改進。但是，基于Apriori改進的算法在自底向上逐漸產(chǎn)生頻繁項集的過程中會產(chǎn)生多余的候選項集，為了計算項集的支持度，多次掃描數(shù)據(jù)庫是對時間和資源的一種浪費。另外，隨著挖掘?qū)挾群蜕疃鹊脑黾樱現(xiàn)P-T

3、ree的構(gòu)建將會消耗巨大的時空資源?；谏鲜鰡栴}，對最大頻繁項集挖掘過程中的相關(guān)問題進行了深入研究。除了基礎(chǔ)概念和理論，本文還綜述了挖掘最大頻繁項集的過程中所用到的搜索策略和剪枝策略，同時分析了最大頻繁項集挖掘的四種經(jīng)典算法，為后續(xù)最大頻繁項集的挖掘算法奠定了理論基礎(chǔ)。
　　本文提出了一種基于回溯的最大頻繁項集挖掘算法GBMFI(Go-Back Maximal Frequent Itemsets)。它以枚舉樹為搜索空間，通過深度優(yōu)

4、先搜索克服了自底向上和自頂向下搜索策略的不足，采用垂直表示數(shù)據(jù)庫的方法降低了項集支持度計算的復(fù)雜性，并融入非頻繁子集、頻繁超集以及利用父子關(guān)系的剪枝策略，針對不同情況，使用恰當(dāng)?shù)募糁Ψ椒ǎ岣吡怂惴ㄐ省ｋS后，在四種標準數(shù)據(jù)集下進行了實驗。與DepthProject算法對比可得，在相同環(huán)境下，GBMFI算法運行速度較快，并對不同數(shù)據(jù)集下的最大頻繁項集的結(jié)果數(shù)與分布情況進行了研究。另外，本文還提出了一種分布式并行挖掘最大頻繁項集的算法AM