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

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

關鍵詞：0-1矩陣；統計匹配；剪枝

1 關聯規則[1]挖掘及Apriori算法概述

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

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

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

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

2.1 采用0-1矩陣描述數據庫事務集

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

采用0-1矩陣描述數據庫事務集能帶來如下好處：

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

2.2 改進后的算法 MyApriori描述

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

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

2.3 MyApriori算法性能分析與實驗

對某關于公積金數據庫事務集{{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：

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

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

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

參考文獻

[1]Jiawei Han Micheline Kamber著.范明，孟小峰.數據挖掘概念與技術（加）[M].機械工業出版社，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.