一種改進(jìn)的Apriori算法及在計(jì)算機(jī)一級(jí)等級(jí)考試的應(yīng)用

何云峰

摘要：在介紹了傳統(tǒng)的Apriori算法基礎(chǔ)上，對(duì)其生成頻繁2、3項(xiàng)集的方法進(jìn)行了改進(jìn)，給出了具體事例及過(guò)程，在數(shù)據(jù)庫(kù)消減上也給予了一定的策略，從而減少了數(shù)據(jù)庫(kù)容量和掃描次數(shù)。最后通過(guò)對(duì)計(jì)算機(jī)一級(jí)等級(jí)考試的數(shù)據(jù)進(jìn)行挖掘和驗(yàn)證，證明了改進(jìn)算法的效率優(yōu)于Apriori算法；挖掘出的關(guān)聯(lián)規(guī)則，對(duì)于指導(dǎo)教學(xué)有一定的意義。

關(guān)鍵詞：Apriori算法 2項(xiàng)集支持度矩陣 計(jì)算機(jī)一級(jí)等級(jí)考試

中圖分類號(hào)：TP301 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1007-9416（2016）06-0000-00

1 關(guān)聯(lián)規(guī)則Apriori算法簡(jiǎn)介

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

2 Apriori算法的改進(jìn)

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

2.1改進(jìn)想法

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

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

2.2數(shù)據(jù)庫(kù)的消減

第一，因?yàn)橛稍撔腥我鈨身?xiàng)組成的3項(xiàng)集的支持度不可能大于min_sup。于是在2項(xiàng)集支持度矩陣中，若某行的支持度都小于min_sup，那么就刪去該行表示的事務(wù)。第二，若一條事務(wù)包含k頻繁項(xiàng)集，則它本身至少要包含k個(gè)項(xiàng)目。于是在產(chǎn)生k（>3）的候選頻繁項(xiàng)集時(shí)，只需查看數(shù)組M[i]的值大于k的事務(wù)，如果小于k，則下次不用再查找。

2.3算法描述及挖掘過(guò)程

現(xiàn)舉例來(lái)說(shuō)明改進(jìn)算法的處理過(guò)程。例如有項(xiàng)目數(shù)據(jù)庫(kù)第一條事物為ACDF，第二條為BCE，第三條為ABCD，第四條為BE。設(shè)定min_sup=2。

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

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

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

（4）轉(zhuǎn)入改進(jìn)算法第3步，由3項(xiàng)頻繁項(xiàng)不能再生成4項(xiàng)候選項(xiàng)集。算法結(jié)束。

3 改進(jìn)算法計(jì)算機(jī)一級(jí)等級(jí)考試的應(yīng)用

在全國(guó)計(jì)算機(jī)一級(jí)等級(jí)考試中，對(duì)于學(xué)生答錯(cuò)的題所代表的知識(shí)點(diǎn)及學(xué)生編號(hào)建立事物數(shù)據(jù)庫(kù)[4]。之后，使用改進(jìn)的Apriori算法進(jìn)行挖掘。實(shí)驗(yàn)數(shù)據(jù)是本校2015級(jí)學(xué)生參加等級(jí)考試的試卷處理后的結(jié)果。一共涉及48個(gè)知識(shí)點(diǎn)，即items（48）。學(xué)生做錯(cuò)的知識(shí)點(diǎn)用Noi來(lái)表示。實(shí)驗(yàn)結(jié)果得到了幾條關(guān)聯(lián)規(guī)則。比如，答錯(cuò)了電子表格中“函數(shù)”知識(shí)點(diǎn)的同學(xué)，其中大部分人同時(shí)答錯(cuò)了電子表格中“公式”知識(shí)點(diǎn)試題；答錯(cuò)了“二進(jìn)制轉(zhuǎn)八進(jìn)制”知識(shí)點(diǎn)試題的，幾乎在“二進(jìn)制轉(zhuǎn)十六進(jìn)制”這一知識(shí)點(diǎn)上也是全軍覆沒(méi)。

4結(jié)語(yǔ)

因?yàn)椴捎昧?項(xiàng)集支持度矩陣，較好地解決了頻繁2、3項(xiàng)集的求解問(wèn)題。加之采取了一定的數(shù)據(jù)庫(kù)縮減策略，從而比傳統(tǒng)的Apriori算法節(jié)省了更多的時(shí)間。同時(shí)也在全國(guó)計(jì)算機(jī)一級(jí)等級(jí)考試的應(yīng)用中取得了明顯效果。

參考文獻(xiàn)

[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]黃藝?yán)?Apriori算法在無(wú)紙化考試系統(tǒng)中的應(yīng)用和改進(jìn)[J].周口師范學(xué)院學(xué)報(bào)，2015，32（2）：129-130.

[3]秦吉?jiǎng)?，宋瀚?關(guān)聯(lián)規(guī)則挖掘AprioriHybird算法的研究和改進(jìn)[J].計(jì)算機(jī)工程，2004，30（17）：7-9.

[4]申義彩，楊楓，王曉燕.基于基于關(guān)聯(lián)規(guī)則的計(jì)算機(jī)等級(jí)考試答卷分析[J].學(xué)術(shù)研究，2011，10（20）：128-129.