資源描述：
《一種改進(jìn)的Apriori 算法》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。
1、第9卷%第1期軟件導(dǎo)刊Vol.9No.12010年1月SoftwareGuideJan.2010一種改進(jìn)的Apriori算法李曉林，王建華，廖作文（武漢工程大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，湖北武漢430073）摘要：關(guān)聯(lián)規(guī)則挖掘是數(shù)據(jù)挖掘研究領(lǐng)域中的一個(gè)重要任務(wù)，旨在挖掘事務(wù)數(shù)據(jù)庫中有趣的關(guān)聯(lián)。Apriori算法是關(guān)聯(lián)規(guī)則挖掘中的經(jīng)典算法。然而Apriori算法存在著產(chǎn)生候選項(xiàng)目集效率低和頻繁掃描數(shù)據(jù)等缺點(diǎn)。提出了一種新的Apriori的改進(jìn)算法，該算法在生成k（k＞1）項(xiàng)頻繁集時(shí)，不需要重新掃描數(shù)據(jù)庫，只是在生成1項(xiàng)頻集時(shí)，
2、才需要掃描事務(wù)數(shù)據(jù)庫，有效地減少了對事務(wù)數(shù)據(jù)庫的讀操作，在時(shí)間復(fù)雜度上較經(jīng)典的Apriori算法有更加優(yōu)越的性能。關(guān)鍵詞：關(guān)聯(lián)規(guī)則；頻繁項(xiàng)集；Apriori算法中圖分類號：TP312文獻(xiàn)標(biāo)識碼：A文章編號：1672-7800（2010）01－0055－02標(biāo)識符TID表示某公司銷售數(shù)據(jù)庫中顧客的編號字段，項(xiàng)0引言ID為顧客購買的商品編號字段。9個(gè)顧客編號為｛T1，T2，T3，T4，T5，T6，T7，T8，T9｝；交易的記錄中9個(gè)顧客購買了5種商在許多情況下，Apriori性質(zhì)大幅度壓縮了候選項(xiàng)集的大品，分別為I1，I2，
3、I3，I4，I5；具體的每一個(gè)顧客購買的商品分別小，并產(chǎn)生很好的性能。然而，它有兩種開銷可能是十分巨大為｛｛I1，I2，I5｝，｛I2，I4｝，｛I2，I3｝，｛I1，I2，I4｝，｛I1，I3｝，｛I2，I3｝，的：①數(shù)據(jù)庫掃描的次數(shù)過多，尋找每個(gè)k頻繁項(xiàng)集（k＝1，2，｛I1，I3｝，｛I1，I2，I3，I5｝，｛I1，I2，I3｝｝；具體如表1所示：…，k）都需要掃描數(shù)據(jù)庫一次，共需要掃描k次。因此當(dāng)數(shù)據(jù)庫表1事務(wù)表或者k太大時(shí)，算法的耗時(shí)將太大甚至無法完成。②算法的剪TID購買商品枝步，VC∈Ck，判斷c的k個(gè)（
4、k－1）子集是否都在Lk－1中，若找到T1{I1，I2，I5}一個(gè)（k－1）子集不在Lk－1中就淘汰C。因?yàn)檫@個(gè)過程會多次掃T2{I2，I4}T3{I2，I3}描Lk－1，特別是當(dāng)生成的Ck很大時(shí)，算法的效率并不理想。T4{I1，I2，I4}T5{I1，I3}1改進(jìn)的Apriori算法T6{I2，I3}T7{I1，I3}本文根據(jù)對事務(wù)進(jìn)行壓縮，對Apriori算法進(jìn)行了改進(jìn)。在T8{I1，I2，I3，I5}T9{I1，I2，I3}候選頻繁項(xiàng)目集Ck的產(chǎn)生過程中，刪除其中不必要的掃描事現(xiàn)要找出滿足最小支持度的項(xiàng)集，即頻繁集
5、。假設(shè)務(wù)，壓縮事務(wù)數(shù)據(jù)庫，提高掃描的效率，節(jié)省系統(tǒng)的開銷。min＿sup＝2／9＝22％，即最小支持頻度為2。（1）首先，掃描事務(wù)數(shù)據(jù)庫，同時(shí)記錄包含該項(xiàng)的事務(wù)標(biāo)識1項(xiàng)頻集的候選集為C1＝｛｛I1｝，｛I2｝，｛I3｝，｛I4｝，｛I5｝｝，掃TID，產(chǎn)生1項(xiàng)候選集C1（每個(gè)候選集的結(jié)構(gòu)為：項(xiàng)集item－set，描事務(wù)數(shù)據(jù)庫，同時(shí)記錄包含該項(xiàng)的事務(wù)標(biāo)識TID。得到結(jié)果支持計(jì)數(shù)Count，事務(wù)標(biāo)識符列表Tid－list）；然后，從C1中刪除如表2所示：不滿足最小支持度的項(xiàng)集，則C1中的項(xiàng)集集合即是1項(xiàng)頻繁表21項(xiàng)頻繁集及相
6、關(guān)事務(wù)集的集合L1。item-setCountTid-list是否加入L1中（2）Lk－1與Lk－1連接，生成Ck；其中Ck事務(wù)標(biāo)識符列表等于{I1}6T1，T4，T5，T7，T8，T9√生成它的兩個(gè)Lk－1的事務(wù)標(biāo)識符列表的交集。對Ck的計(jì)數(shù)不{I2}7T1，T2，T3，T4，T6，T8，T9√需要掃描事務(wù)數(shù)據(jù)庫，只需計(jì)算Ck中事務(wù)標(biāo)識符列表中的中的計(jì)數(shù)不滿足最小支持度，則將該項(xiàng){I3}6T3，T5，T6，T7，T8，T9√TID個(gè)數(shù)即可。如果Ck集刪除，這樣可以有效減少K項(xiàng)集項(xiàng)Ck的數(shù)量，提高效率。{I4}2T2，T
7、4√下文是一個(gè)改進(jìn)Apriori算法的實(shí)例分析：{I5}2T1，T8√作者簡介：李曉林（1962－），男，湖北安陸人，武漢工程大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院副教授,現(xiàn)任武漢工程大學(xué)網(wǎng)絡(luò)信息中心主任，研究方向?yàn)橛?jì)算機(jī)網(wǎng)絡(luò)技術(shù)應(yīng)用、計(jì)算機(jī)圖形處理、數(shù)據(jù)庫系統(tǒng)、軟件工程應(yīng)用；王建華（1984－），男，山東兗州人，武漢工程大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院碩士研究生，研究方向?yàn)橛?jì)算機(jī)網(wǎng)絡(luò)技術(shù)應(yīng)用?！?6·軟件導(dǎo)刊2010年由于最小支持頻度為2，因此L1＝C1＝｛｛I1｝，｛I2｝，｛I3｝，｛I4｝，｛I5｝｝；（為方便起見，并沒有把count
8、，Tid－list加入到L2實(shí)驗(yàn)結(jié)果分析中，這些都可以從上表中得出）。使用VC＋＋6.0分別實(shí)現(xiàn)了經(jīng)典Apriori算法和改進(jìn)的Apri-由1項(xiàng)頻集求2項(xiàng)頻集ori算法，并在CPU為2.93G，內(nèi)存為512M的機(jī)器上利用Mi-L1與L1連接結(jié)果如表3所示：crosoftSQLServer2000中的Transacti
