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