最大頻繁項(xiàng)集挖掘算法的研究.pdf

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

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

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

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