關(guān)聯(lián)規(guī)則挖掘中Apriori算法的研究.pdf

1、目前，隨著數(shù)據(jù)規(guī)模的急劇增長(zhǎng)，如何在這些海量的數(shù)據(jù)中挖掘出有效的信息已經(jīng)成為了全世界備受矚目的話題，因此，數(shù)據(jù)挖掘成為了極其熱門的研究領(lǐng)域。關(guān)聯(lián)規(guī)則挖掘作為數(shù)據(jù)挖掘領(lǐng)域中非常重要的研究方向之一，國(guó)內(nèi)外許多學(xué)者對(duì)關(guān)聯(lián)規(guī)則挖掘技術(shù)進(jìn)行了諸多的研究，但仍有很多問(wèn)題需要完善。
　　作為關(guān)聯(lián)規(guī)則挖掘最經(jīng)典的算法，Apriori算法能夠有效地挖掘出事務(wù)數(shù)據(jù)庫(kù)的頻繁項(xiàng)集，根據(jù)挖掘出的頻繁項(xiàng)集可以快速準(zhǔn)確地找出關(guān)聯(lián)規(guī)則。然而，Apriori算法具

2、有兩大顯著的缺陷，該算法需要多次掃描數(shù)據(jù)庫(kù)和產(chǎn)生大量無(wú)用的候選項(xiàng)集，也正是因?yàn)檫@兩大缺點(diǎn)，給關(guān)聯(lián)規(guī)則挖掘技術(shù)的發(fā)展帶來(lái)了極大的挑戰(zhàn)。
　　在對(duì)Apriori算法深入研究和分析的基礎(chǔ)上，本課題的主要研究工作集中在對(duì)Apriori算法的改進(jìn)，主要體現(xiàn)在以下幾個(gè)方面:
　　1)針對(duì)傳統(tǒng)Apriori算法I/O開(kāi)銷大，產(chǎn)生大量多余的候選項(xiàng)集和運(yùn)行效率低等問(wèn)題，改進(jìn)了一種基于映射的Apriori改進(jìn)算法—Mapping_Apriori

3、。該算法首先采用映射結(jié)構(gòu)來(lái)存儲(chǔ)數(shù)據(jù)庫(kù)中的事務(wù)，對(duì)事務(wù)數(shù)據(jù)庫(kù)進(jìn)行有效壓縮，降低大量的I/O負(fù)擔(dān)，提出一種新的降低映射維度的策略;同時(shí)，通過(guò)映射這種數(shù)據(jù)結(jié)構(gòu)可以快速地計(jì)算出候選項(xiàng)集的支持度，降低計(jì)算復(fù)雜度;最后，根據(jù)頻繁項(xiàng)集的相關(guān)性質(zhì)，可以對(duì)頻繁項(xiàng)集Lk-1實(shí)現(xiàn)預(yù)先瘦身的效果，有效地避免無(wú)用的候選項(xiàng)集的產(chǎn)生。通過(guò)實(shí)驗(yàn)，驗(yàn)證該算法的有效性，提高了算法的運(yùn)行效率。
　　2)通過(guò)對(duì)頻繁模式增長(zhǎng)算法FP-Growth的深入研究，該算法可以通過(guò)

4、不產(chǎn)生候選項(xiàng)集來(lái)找出頻繁項(xiàng)集，該算法的核心是頻繁模式樹(shù)FP-tree可以對(duì)事務(wù)數(shù)據(jù)庫(kù)進(jìn)行高效壓縮?；贔P-tree的優(yōu)勢(shì)，改進(jìn)了一種基于頻繁模式樹(shù)的Apriori的改進(jìn)算法—FP_Apriori。該算法將整個(gè)事務(wù)數(shù)據(jù)庫(kù)投影到FP-tree上，避免大量的I/O開(kāi)銷;同時(shí)，提出一種更加有方向和有針對(duì)性地對(duì)FP-tree的搜索策略，降低了算法的運(yùn)行時(shí)間;最后同樣采用Mapping_Apriori算法的原理對(duì)頻繁項(xiàng)集Lk-1進(jìn)行預(yù)先瘦身。通過(guò)