Apriori算法中頻繁項集求法的改進

摘 要：分析傳統(tǒng)Apriori效率較低的原因，采用0-1矩陣改進數(shù)據(jù)庫事務(wù)集的描述，提高Apriori中統(tǒng)計匹配的時間效率；分析各頻繁項集的計數(shù)，改進傳統(tǒng)Apriori算法完全從低維頻繁項集產(chǎn)生高維頻繁項集的方式，通過先求出1項頻繁集和最大頻繁項集，減少中間的頻繁項集剪枝數(shù)量，從而達到提高算法效率的目的。

關(guān)鍵詞：0-1矩陣；統(tǒng)計匹配；剪枝

1 關(guān)聯(lián)規(guī)則[1]挖掘及Apriori算法概述

一提到關(guān)聯(lián)規(guī)則挖掘就會令人聯(lián)想到“尿布與啤酒”的故事，這是借助數(shù)據(jù)挖掘技術(shù)對大量原始交易數(shù)據(jù)進行分析揭示的一條規(guī)律。Apriori[2]算法是由美國學者R. Agrawal等在1993年提出的一種從大規(guī)模商業(yè)數(shù)據(jù)中挖掘關(guān)聯(lián)規(guī)則的有效方法。現(xiàn)在已經(jīng)被廣泛用于商業(yè)決策、社會科學、科學數(shù)據(jù)處理等各種各樣的數(shù)據(jù)挖掘領(lǐng)域之中。使用基于支持度的剪枝技術(shù)，系統(tǒng)地控制候選項集指數(shù)增長。其核心是使用候選項集找頻繁項集。算法具體的執(zhí)行步驟如下：

（1）根據(jù)用戶的要求確定最小支持度和最小置信度；（2）找出所有的頻繁項集：先由數(shù)據(jù)庫讀入所有的數(shù)據(jù)項，得出候選1項集C1，然后根據(jù)最小支持度要求確定頻繁1項集L1；使用L1與L1自連接產(chǎn)生候選2項集C2，繼續(xù)對數(shù)據(jù)庫掃描，得出候選2項集C2的支持度，確定頻繁2項集L2；繼續(xù)執(zhí)行上述的步驟，不斷進行連接與剪枝，重復對數(shù)據(jù)庫的掃描，并和最小支持度進行比較，產(chǎn)生更高層次的頻繁項集，直到不再產(chǎn)生新的候選頻繁項集為止；（3） 根據(jù)頻繁項集產(chǎn)生強關(guān)聯(lián)規(guī)則。

2 Apriori算法的缺點及改進方法

Apriori算法能夠有效地進行數(shù)據(jù)關(guān)聯(lián)規(guī)則挖掘，但該算法存在效率不高的問題。該算法使用迭代方法，通過低維頻繁項集產(chǎn)生高維頻繁項集，該算法存在兩個比較明顯的缺點：一個是可能產(chǎn)生大量的候選集，時間開銷和空間開銷都很大；另一個是需要多次掃描數(shù)據(jù)庫，需要很大的 I/O開銷。

2.1 采用0-1矩陣描述數(shù)據(jù)庫事務(wù)集

設(shè)I={i1，i2，…，in}是項的集合，D是數(shù)據(jù)庫事務(wù)集，其中每個事務(wù)T是項的集合，使得T？哿I。按如下規(guī)則用0-1矩陣描述數(shù)據(jù)庫事務(wù)集：如果I中某一項ik在事務(wù)T中存在，用“1”表示，否則就用“0”表示。數(shù)據(jù)庫事務(wù)集D就轉(zhuǎn)化為m*n矩陣的0-1矩陣，其中m為數(shù)據(jù)庫事務(wù)集D的大小，即包含多少個事務(wù)，n為集合I的計數(shù)。

采用0-1矩陣描述數(shù)據(jù)庫事務(wù)集能帶來如下好處：

（1）運算簡單；便于統(tǒng)計，橫向統(tǒng)計“1”的個數(shù)就是事務(wù)T包含的項數(shù)，縱向統(tǒng)計“1”的個數(shù)就是1項集的統(tǒng)計數(shù)；（2）使用0-1矩陣算法，提高統(tǒng)計項集時候的匹配效率，傳統(tǒng)的統(tǒng)計匹配效率正比于n^2，采用0-1矩陣匹配時間效率正比于n；（3）減少對數(shù)據(jù)庫的掃描，排序后，求頻繁k項集的時候，統(tǒng)計項集時不需要掃描數(shù)據(jù)庫，只需要統(tǒng)計包含大于等于k個項目數(shù)的事務(wù)；（4）易于對數(shù)據(jù)庫事務(wù)集按事務(wù)包含的項目數(shù)大小降序排序；（5）易于求出最大頻繁項集。

2.2 改進后的算法 MyApriori描述

要提高Apriori算法的效率，一般來說就是要考慮兩個方面的問題：一是減少對數(shù)據(jù)庫的掃描，二是在剪枝的時候減少統(tǒng)計項集的次數(shù)。采用0-1矩陣，并排序以后，可以減少對數(shù)據(jù)庫的掃描，在求k項頻繁項集時候，只需要掃描包含大于等于k個項目的項集，不需要掃描全部的數(shù)據(jù)庫。傳統(tǒng)Apriori算法采用從頻繁1項集開始，由頻繁k-1項集產(chǎn)生頻繁k項集，中間產(chǎn)生大量候選集，對這些候選集要進行統(tǒng)計并剪枝，運算量大；通過多次試驗發(fā)現(xiàn)：對于1項頻繁集，2項頻繁集，……，m-1項頻繁集，m項頻繁集（m項頻繁集為最大頻繁項集），其數(shù)量分布有一定規(guī)律，就是兩頭的數(shù)量相對較少，尤其是最大頻繁項集數(shù)量不多，中間頻繁項集的數(shù)量較多，數(shù)量分布整體呈現(xiàn)為“紡錘狀”。可以先通過統(tǒng)計的方法求出最大頻繁項集，然后利用“頻繁項集的所有非空子集一定也是頻繁的”這一定理，再由k-1項頻繁項集產(chǎn)生k項頻繁項集時，剔除最大頻繁項集的子集的項集，只需要統(tǒng)計分析剩余的項集是否為頻繁項集即可，減少了剪枝的運算量，優(yōu)化算法。算法MyApriori：輸入原始數(shù)據(jù)庫事務(wù)集矩陣A，輸出0-1矩陣FI表示的各項頻繁項集。

上述算法的優(yōu)點：在減少了剪枝的運算量，減少了數(shù)據(jù)庫的掃描次數(shù)；缺點是對原始數(shù)據(jù)庫0-1化處理、排序和統(tǒng)計產(chǎn)生最大頻繁MAXFI增加了額外開銷，其中0-1化處理、排序要對數(shù)據(jù)庫各掃描1次，統(tǒng)計產(chǎn)生最大頻繁MAXFI也需要對數(shù)據(jù)庫進行掃描；其中0-1化處理、排序增加的開銷并不是很大，統(tǒng)計產(chǎn)生最大頻繁MAXFI可能會帶來較大的開銷。總體來說，從時間效率上來講，改進的算法優(yōu)于傳統(tǒng)的算法，尤其在MAXFI比較容易求取的情況下；從空間效率來講，改進后的算法要用到countA01、CCA01、SA01等矩陣，效率會有所降低。

2.3 MyApriori算法性能分析與實驗

對某關(guān)于公積金數(shù)據(jù)庫事務(wù)集{{T1：I1，I3，I4，I6}；{T2：I2，I3，I4}；{T3：I1，I2，I3；}；{T4：I2，I6}；{T5：I2，I3，I4，I5}；{T6：I2，I3，I5}；{T7：I1，I2，I3，I4，I6}；{T8：I1，I3，I4，I5，I6}；{T9：I1}；{T10：I1，I5}，令sup=0.3：

采用傳統(tǒng)Apriori算法，求1項頻繁集時，有6個候選頻繁項集，每個項集需要與原數(shù)據(jù)庫匹配1次，原始數(shù)據(jù)庫大小為10項，要匹配6*10=60次，得到6個1項頻繁集；求2項頻繁集時，產(chǎn)生C62=15個候選頻繁項集，每個項集需要與原數(shù)據(jù)庫匹配1次，原始數(shù)據(jù)庫大小為10項，要匹配15*10=150次，得2項頻繁集有9項；求3項頻繁集時，產(chǎn)生13個候選頻繁項集，每個項集需要與原數(shù)據(jù)庫匹配1次，原始數(shù)據(jù)庫大小為10項，要匹配13*10=130次，得3項頻繁集有5項；求4項頻繁集時，產(chǎn)生3個候選頻繁項集，每個項集需要與原數(shù)據(jù)庫匹配1次，原始數(shù)據(jù)庫大小為10項，要匹配3*10=30次，得4項頻繁集有1項，4項頻繁集即為最大頻繁項集。在上述過程中，共計需要匹配的次數(shù)為：60+150+130+30=370。

采用改進后的算法MyApriori算法，求1項頻繁項集匹配60次，2項頻繁項集匹配96次，3項頻繁項集匹配76次，4項頻繁項集匹配4次，共計匹配236次，加上掃描2遍數(shù)據(jù)庫，可近似計為2*10次=20次，總計為236+20=256次，小于傳統(tǒng)Apriori算法的370次；減少了對數(shù)據(jù)庫的掃描和剪枝的運算量。

實驗驗證：采用MatLab編程，2G內(nèi)存，2.5G雙核CPU， Windows XP環(huán)境；使用gjj數(shù)據(jù)庫，采用傳統(tǒng)Apriori算法和改進后的MyApriori算法各運行10000次，時間分別為0.3440ms和0.2950ms，可以得出改進后的算法更快。

參考文獻

[1]Jiawei Han Micheline Kamber著.范明，孟小峰.數(shù)據(jù)挖掘概念與技術(shù)（加）[M].機械工業(yè)出版社，2008年12月.

[2]Agrawal R，ImielinskiT， Swami A.Mining association rules between sets of items in large databases. Proceedings of ACMSIGMOD Conference on Management of Data，1993：207-216.