一種改進的Apriori算法及在計算機一級等級考試的應用

何云峰

摘要：在介紹了傳統的Apriori算法基礎上，對其生成頻繁2、3項集的方法進行了改進，給出了具體事例及過程，在數據庫消減上也給予了一定的策略，從而減少了數據庫容量和掃描次數。最后通過對計算機一級等級考試的數據進行挖掘和驗證，證明了改進算法的效率優于Apriori算法；挖掘出的關聯規則，對于指導教學有一定的意義。

關鍵詞：Apriori算法 2項集支持度矩陣 計算機一級等級考試

中圖分類號：TP301 文獻標識碼：A 文章編號：1007-9416（2016）06-0000-00

1 關聯規則Apriori算法簡介

關聯規則挖掘（Association Rule Mining）是數據挖掘研究中的一個重要分支，用它可以發現交易數據庫中項目、屬性之間的內在聯系。用于關聯規則數據挖掘的著名算法――Apriori算法由Agramal和srikant提出[1]。它的基本思想是重復掃描數據庫，根據一個頻繁集的任意子集都是頻繁集的原理，可以從長度為k的頻繁集迭代地產生長度為 k+1 的頻繁集，并在第k次掃描時產生出長度為 k的大項集Lk。而在第 k+1 次掃描時，只考慮由Lk 中的k 項集產生長度為 k+1 的候選集 Ck+1，然后再掃描數據庫以驗證其發生的次數。然而，如果是頻繁集很長或最小支持度非常小時，用這種方法產生候選集將會有極大的消耗。如此，則需要大量次數的重復掃描數據庫。

2 Apriori算法的改進

每次都要掃描數據庫，是一項既費時又費力的工作。于是有學者使用以空間換時間的思路，即用生成大量項目的方法來換取僅掃描一次數據庫的方法來改進基本的Apriori算法[2]。但這種方法隨著項目數的巨增使得產生的項目組合可能不能放入機器內存一次處理。于是有這樣一種思想，即：在Apriori 算法每次掃描數據庫時，檢測在每次遍歷的末尾處集合Ck能適合內存時就不再使用掃描數據庫的Apriori 算法而使用把集合Ck放入內存的改進的Apriori 算法。用一種方法來估計下一次遍歷中Ck是否適合內存。如果這次產生的Ck可以小到放入內存，且本次遍歷產生的大型候選比前次要少，那么就轉換算法。有實驗說明這種轉入內存的Apriorii算法和傳統的Apriori算法在生成頻繁2、3項集所費時間最多，幾乎占到該算法的3/5時間，且前者所耗時間遠比Apriori多，于是本文主要對生成頻繁2項集和頻繁3項集部分進行相關改進，同時使用了一些方法對數據庫進行消減。由于已知生成頻繁2、3項集所費時間最多，所以本文在使用改進的Apriori算法生成頻繁3項集后即轉入內存，重新使用傳統的Apriori算法，而無需再設置判斷條件。

2.1改進想法

做一個上三角矩陣用來存儲候選頻繁2項集C2的所有元素[3]。例如有A， B， C，D ，4個項目，則C2可用圖1表示。這個矩陣稱為：2項集支持度矩陣，給A， B， C， D分別賦予順序號1，2，3，4，于是使用下標（i，j）就可以把候選頻繁2項集中的任何一個訪問到，比如AB的坐標，使用（2，3）就可以訪問到。第一邊掃描數據庫時就能確定C2中各項的支持度。先對矩陣清零后，把每一條交易按交易項目排序，生成所有可能的順序2項組合。比如第一條交易項目為{A，B，C，D}，則所有的順序2項組合為{A， B}、{A， C}、{A， D}、{B， C}、{B， D}、{C， D}，那么它們相應的矩陣元素為{2， 3}， {2， 4}， {2， 5}，{3， 4}等等，把這些元素的計數加1，就完成了對第一條交易項目的處理。接著再掃描完數據庫的所有交易，并作相應處理。再設置一個用以記錄事務中項目個數的數組M[i]，以備消減數據庫使用。

使用以上方法獲得候選頻繁2項集的支持度后，接著查找矩陣的第二行，找出所有支持度大于min_sup的項，再用第一項與第二項組合生成3項集，并且記下第一項與第二項分別所在的列號，于是查找由這兩個列號組成的矩陣元素的值，若大于min_sup，則用第一項與第二項組合生成的3項集就是頻繁3項集，其支持度即為第一項和第二項這兩項的2個列號組成的矩陣元素的支持度和第一項及第二項的支持度，三者的最小值。該方法可直接產生頻繁3項集以及其支持度，無需生成候選頻繁3項集。

2.2數據庫的消減

第一，因為由該行任意兩項組成的3項集的支持度不可能大于min_sup。于是在2項集支持度矩陣中，若某行的支持度都小于min_sup，那么就刪去該行表示的事務。第二，若一條事務包含k頻繁項集，則它本身至少要包含k個項目。于是在產生k（>3）的候選頻繁項集時，只需查看數組M[i]的值大于k的事務，如果小于k，則下次不用再查找。

2.3算法描述及挖掘過程

現舉例來說明改進算法的處理過程。例如有項目數據庫第一條事物為ACDF，第二條為BCE，第三條為ABCD，第四條為BE。設定min_sup=2。

（1）定義2項集支持度矩陣，除第一行外，上三角矩陣元素都初始化置0。把數據庫的每條事物逐一掃描后，可以得到2項集的支持度。例如先把第一條事物拆成2項集{{ A C }，{ A D }，{ A F }，{C D}，{C F}，{D F}}，給矩陣相應位置加1，后面的事務使用同樣方法處理。結果如圖2。再用數組M記錄每條事物中的項目個數和。例如第一條事務中有4個項目A，C，D，F，那么M[1]=4。

（2）讀取矩陣中的元素值，取出值大于等于2的就可以得到2項頻繁項集，從圖3中可以查到{{ A C }，{ A D }，{B C}，{B E}，{C D}}和各自的支持度。

（3）生成3項頻繁項集。在矩陣第二行中按順序找出兩個元素值大于等于min_sup的元素，找到AC、AD兩項，再尋找這兩項的列號組成的元素CD的值，等于2，其大于等于min_sup，所以由AC和AD組成的項ACD是頻繁的，其支持度為AC，AD，CD中最小值2。繼續查找該行，找不到元素值大于等于2的項。開始查找第三行及以后各行支持度大于等于min_sup的元素。找到BCE。直到掃描完數據庫。生成3項頻繁項集{{ A C D}、{B C E}}和各自支持度。

（4）轉入改進算法第3步，由3項頻繁項不能再生成4項候選項集。算法結束。

3 改進算法計算機一級等級考試的應用

在全國計算機一級等級考試中，對于學生答錯的題所代表的知識點及學生編號建立事物數據庫[4]。之后，使用改進的Apriori算法進行挖掘。實驗數據是本校2015級學生參加等級考試的試卷處理后的結果。一共涉及48個知識點，即items（48）。學生做錯的知識點用Noi來表示。實驗結果得到了幾條關聯規則。比如，答錯了電子表格中“函數”知識點的同學，其中大部分人同時答錯了電子表格中“公式”知識點試題；答錯了“二進制轉八進制”知識點試題的，幾乎在“二進制轉十六進制”這一知識點上也是全軍覆沒。

4結語

因為采用了2項集支持度矩陣，較好地解決了頻繁2、3項集的求解問題。加之采取了一定的數據庫縮減策略，從而比傳統的Apriori算法節省了更多的時間。同時也在全國計算機一級等級考試的應用中取得了明顯效果。

參考文獻

[1] R.Agrawal and R.Srikant， Fast Algorithms for Mining Association Rules in Large Databases[C]，In Research Report RJ 9839， IBM Almaden Research Center， San Jose， Califomia， 1994.

[2]黃藝坤.Apriori算法在無紙化考試系統中的應用和改進[J].周口師范學院學報，2015，32（2）：129-130.

[3]秦吉勝，宋瀚濤.關聯規則挖掘AprioriHybird算法的研究和改進[J].計算機工程，2004，30（17）：7-9.

[4]申義彩，楊楓，王曉燕.基于基于關聯規則的計算機等級考試答卷分析[J].學術研究，2011，10（20）：128-129.