改進Apriori算法在高校學生信息系統(tǒng)中的應用研究

胡淑新，李長云，吳岳忠

（湖南工業(yè)大學 計算機與通信學院，湖南 株洲 412007）

隨著近年來大數(shù)據(jù)的興起，一個熱點問題便是數(shù)據(jù)挖掘，數(shù)據(jù)挖掘其實是一種決策支持過程，在高度自動化的分析大量數(shù)據(jù)后，可以做出歸納性的推理，繼而從中挖掘出潛在的模式，之后可以給予決策者有效判斷的依據(jù)。其中，作為非常重要的研究方法之一，關聯(lián)規(guī)則主要反映的是事物之間的依存和關聯(lián)問題，如果幾個事物之間存在一定的關聯(lián)性，那么，可以通過其他事物預測到之中的某個事物[1]。找出關聯(lián)規(guī)則的關鍵步驟：1)找出所有頻繁項集。2)分析頻繁項集從而得出滿足最小信任度閾值的規(guī)則。1993年由Agrawal等人提出了挖掘算法，之后又進一步提出了Apriori算法，該算法是一種挖掘關聯(lián)規(guī)則的頻繁項集算法，其思想是通過候選集生成和情結(jié)的向下封閉檢測兩個階段來挖掘頻繁項集[2]。

1 Apriori算法概述

Apriori算法是一種最有影響的挖掘布爾關聯(lián)規(guī)則頻繁項集的算法。該算法的核心是基于兩階段頻集思想的遞推算法，使用一種逐層迭代的方法通過低維頻繁項集得到高維頻繁項集，因而在使用中會有很多的不足之處[3]。

Apriori算法的計算復雜度4個因素的限制：1）最小支持度閾值和最小置信度閾值；2）項數(shù)（維度）；3）事務數(shù)；4）事務的平均寬度[4]。該算法存在一些缺陷：1）候選項集的逐層產(chǎn)生需要頻繁掃描整個數(shù)據(jù)庫，直到無法再產(chǎn)生候選集為止。2）可能產(chǎn)生大量候選集。Apriori算法應用十分廣泛，圖書館系統(tǒng)，高校管理系統(tǒng)等，并且在近年來像移動通信領域的應用也呈現(xiàn)出強勁的發(fā)展勢頭，將該算法應用與各種數(shù)據(jù)的相關挖掘處理從而得到用戶的行為特征和一些動態(tài)的信息作為決策參考[5]。

由于Apriori算法的一些明顯缺陷，研究者們不斷地提出各種改進方案，常見的有3種優(yōu)化方法：1）基于矩陣的優(yōu)化方法，在算法中運用矩陣的思想，將事務數(shù)據(jù)用矩陣的形式來表示。2）基于劃分的優(yōu)化方法，在算法中運用分塊的思想，將數(shù)據(jù)庫邏輯上分成幾個相對獨立的塊單獨考慮，最后合并頻集。3）基于采樣的優(yōu)化方法，在前一遍掃描的基礎上來組合分析[6]。

2 以數(shù)組向量為存儲結(jié)構(gòu)改進Apriori算法

2.1 基于數(shù)組向量的算法改進

對傳統(tǒng)的Apriori算法進行改進，借鑒文獻[7]的思想，在此基礎上，更改數(shù)組向量的數(shù)據(jù)結(jié)構(gòu)，每個數(shù)組向量多設定一列來記錄事務數(shù)組的數(shù)目，將事務數(shù)據(jù)庫的每個事務數(shù)據(jù)映射到事務數(shù)組向量中，根據(jù)長度的不同存入不同列大小的二維數(shù)組中，行代表事務，列代表項，這樣就可以將數(shù)據(jù)庫的信息投影到內(nèi)存中，降低了訪問時間。相同的事務項只在數(shù)組中存儲一次，壓縮了相同事務在內(nèi)存中的數(shù)目，每一行的最后一列記錄該行事務數(shù)組數(shù)目，這樣對數(shù)據(jù)庫掃描一次以后就在內(nèi)存中建立了一個投影的數(shù)組向量，之后的掃描都只需掃描改數(shù)組向量即可，降低了掃描次數(shù)和I/O負載。約定各事務項目、頻繁項集以及候選項集中的各項都是按照其代表的項目的字典次序排列。

改進的Apriori算法在高校學生信息管理系統(tǒng)中應用的算法框架如下：

輸入：事務數(shù)據(jù)庫D，最小支持度supmin;輸出：數(shù)據(jù)庫中的頻繁項集L。

二維數(shù)組Ai(i=2,3…,n+1); //將事務根據(jù)長度不同放入不同列大小的數(shù)組中

步驟 1：1)L1=find_frequent_1_itemset(D); //掃描事務數(shù)據(jù)庫D，將每個事務數(shù)據(jù)庫按照長度不同存儲在數(shù)組向量A中，數(shù)組A的最后一列記錄對應的該行事務的數(shù)目，再根據(jù)最小支持度supmin找到頻繁1項集L1。

步驟2 2)for(k=2;Lk-1≠0.;k++)

3){Ck=apriori_gen(Lk-1,supmin); //根據(jù)頻繁（k-1）項集Lk-1生成候選K項集Ck。

4) {for(i=k+1;i＜n+1;i++) //掃描數(shù)組向量 A，n為A包含數(shù)組向量的個數(shù)。

5)for(j=0;j+1＜ni;j++) //掃描每個事務除事務數(shù)組向量的最后一列記錄的數(shù)目以外

6){CAi[j]=subset(Ck,Ai[j]);

7)foreach c∈CAi[j]

8)c.count+=Ai[j+1]}} //讀 取 Ai[j]事 務 的數(shù)目記錄到Ai[j+1]中

9)Lk={c∈Ck∣c.count≥supmin};}

10)return L=UkLk;

apriori_gen(Lk-1,supmin)函數(shù)主要完成兩個目標：

1)連接操作

根據(jù)頻繁（k-1）項集Lk-1生成候選k項集Ck。

Apriori算法性質(zhì)：對于k項集Mk，頻繁k項集包含的頻繁k-1項集出現(xiàn)的次數(shù)應該大于等于k。根據(jù)該性質(zhì)頻繁（k-1）項集與自身連接生成候選k項集之前，需要先計算出頻繁項集Lk-1(j)的所有項目的頻度，如果Lk-1(j）的頻度＜k-1,記錄下來，然后在頻繁項集Lk-1中刪除掉包含剛才記錄的頻繁項目集中任一元素的項目集。就可以得到一個更小的頻繁(k-1)項集的集合，在對該集合中的頻繁項集自身連接之前先對它進行判斷，如果它的數(shù)目小于等于1時，得出結(jié)論候選K項集Ck為空。否則，根據(jù)有序的頻繁項集的項，包含于該集合中的任意兩項不同的頻繁(k-1)項集X與Y連接進行比較，如果不能連接，即兩項之后的所有頻繁(k-1)項集都不能滿足連接條件，所以不用再判斷X與Y以后的所有頻繁(k-1)項集，該操作減少了連接中比較的次數(shù)，縮短了時間。

2)修剪操作

修剪的功能與Apriori算法相同，根據(jù)Apriori算法的性質(zhì)：對于k項頻繁項集Lk，如果事務的長度小于k時，計算候選k項集Ck的頻度時，改事務項不必再掃描。最終可以得到候選K項集Ck。

2.2 改進Apriori算法在高校學生信息系統(tǒng)中的應用

1)使用計算機專業(yè)12級部分本科生的部分成績作為原始數(shù)據(jù)庫事務集進行舉例說明

表1 原始數(shù)據(jù)庫Tab.1 Original database

2)對原數(shù)據(jù)進行預處理得到事務集D

對數(shù)據(jù)進行格式轉(zhuǎn)換，采用邏輯型數(shù)據(jù)，將成績數(shù)據(jù)用布爾型數(shù)據(jù)表來表示，80分以上的用 “1”來表示，80分以下的用“0”來表示，將學號用 S1…S12 來表示，課程用 B、C、D、E、F、G分別表示計算機網(wǎng)絡、數(shù)字電路、操作系統(tǒng)、鄧小平理論、計算機組成原理、數(shù)據(jù)結(jié)構(gòu)，這樣存儲可以大大節(jié)省存儲空間。

3)采用改進后的Apriori算法對事務集D進行掃描后得到數(shù)組向量A（表2所示）以及候選1項集C1、支持度supmin和頻繁1項集L1（表3所示）。數(shù)組A的最后一列用來記錄各事務的數(shù)目。設定最小支持度為2/12。

表2 數(shù)組ATab.2 Array A

表3 候選1項集以及頻繁1項集Tab.3 Candidate item sets and Frequent item sets

4)通過頻繁1項集得到候選2項集C2以及頻繁2項集L2在計算支持度的時候，對于有相同事務的項集只需要掃描一次，通過找到對應的A2[0][2]=2,A2[2][2]=2,A2[3][2]=2,A3[0][3]=3存儲的計數(shù)，最后得到頻繁2項集。

5)根據(jù)頻繁2項集可以求得候選3項集,首先分析頻繁2項集中 B的頻度為3，D的頻度為 4，E的頻度為2，F(xiàn)的頻度為2，G的頻度為1，因為G的頻度＜2=3-1，所以根據(jù)前邊所訴Apriori算法的性質(zhì)，刪掉頻繁2項集中包含G的頻繁項目，從而得到刪減后的頻繁過度2項集，然后與自身相連接，根據(jù)前邊所講解的連接判斷得到候選3項集C3={{B，D，E}，{B，D，F(xiàn)}}。

6)重復以上第5步的方法，得到頻繁3項集L3={{B，D，F(xiàn)}}。連接獲得候選4項集，但由于頻度均小于3，所以候選4項集為空，所以算法結(jié)束。

7)由最長的頻繁集L3產(chǎn)生的關聯(lián)規(guī)則及由次長的頻繁集L2產(chǎn)生的關聯(lián)規(guī)則如表4所示。

根據(jù)已經(jīng)設定的最小支持度為2/3，置信度為1，可以得到篩選后的較強的關聯(lián)規(guī)則。

選出規(guī)則{{G}}==＞{{D}}[support=3/12，confidence=1]分析

可知數(shù)據(jù)結(jié)構(gòu)為“優(yōu)”操作系統(tǒng)為“優(yōu)”的置信度為1。分析關聯(lián)規(guī)則，從來理論上來講，部分規(guī)則是有實用價值的，最后的規(guī)則仍需根據(jù)現(xiàn)實意義進行刪減。G表示的是數(shù)據(jù)結(jié)構(gòu)成績，D表示的是操作系統(tǒng)成績，那么它的意義就是當數(shù)據(jù)結(jié)構(gòu)的成績處于優(yōu)秀，相應的操作系統(tǒng)的成績也應該處于優(yōu)秀水平，現(xiàn)實中，數(shù)據(jù)結(jié)構(gòu)作為操作系統(tǒng)的一門必修先行課程，說明數(shù)據(jù)結(jié)構(gòu)確實是學習操作系統(tǒng)的一門必要的先修課程。不可否認，Apriori算法給出了很多現(xiàn)實中我們認為是無用關聯(lián)的信息，一方面是由誤差引起的，當然也與數(shù)據(jù)集的大小有關，這是以后算法改進時需要考慮的問題。

表 4頻繁3項集關聯(lián)規(guī)則及頻繁2項集關聯(lián)規(guī)則Tab.4 Association ru les in frequent item sets of size 3 and Association rules in frequent item sets of size 2

3 可信度算法性能分析及實驗

找數(shù)據(jù)的時間效率提高，只需訪問數(shù)組中記錄該事務數(shù)目的項，時間復雜度為O（1）。原Apriori算法的掃描數(shù)據(jù)庫的次數(shù)為為候選K項集的大?。?。改進算法相比原算法在一定程度上減少了運算量。

2)空間復雜度方面，原算法會產(chǎn)生大量的候選項占用內(nèi)存，并且會頻繁的進行I/O訪問，改進的Apriori算法相同的事務項在數(shù)組中只存儲一次，占用了很少的內(nèi)存空間，也減少了進行I/O訪問的次數(shù)。采用改進后的算法進行數(shù)據(jù)挖掘?qū)?/p>

改進后的基于數(shù)組的Apriori算法[8]與經(jīng)典的Apriori算法相比，優(yōu)點如下：

1)算法對數(shù)據(jù)庫的掃描次數(shù)減少，只需掃描一次，減少了訪問事務的次數(shù)，并且采用了合理的結(jié)構(gòu)來表示事務項，尋可以大大減少內(nèi)存占用率。

3)改進的Apriori算法的數(shù)據(jù)結(jié)構(gòu)相比原算法大大簡化，使用簡單的數(shù)組來訪問以及存儲可以節(jié)省時間，并且掃描一次數(shù)組的效率遠高于原算法的掃描一次事務數(shù)據(jù)庫的效率。

實驗結(jié)果及分析：

為了驗證改進算法的效率，對原Apriori算法和改進算法進行對比試驗，數(shù)據(jù)集為計算機專業(yè)12級部分本科生成績，數(shù)據(jù)集包含了300名學生的21門課程，共6 300條記錄，對預處理后的數(shù)據(jù)集進行測試。試驗環(huán)境為：Inter(R)2.40GHz CPU，1G內(nèi)存，操作系統(tǒng)為Windows7，算法在matlab 2010b下實現(xiàn)。多次測試，取其穩(wěn)定后的試驗結(jié)果。兩種算法的性能比較如圖1所示。

圖1 圖1同一最小支持度下的時間性能比較Fig.1 Time performance comparison on sameminimum support

圖2 不同支持度下產(chǎn)生的頻繁項集個數(shù)Fig.2 Frequent itemsets in different support

由圖1可以看出原Apriori算法與基于數(shù)組向量改進后的算法在同一最小支持下的時間性能。從仿真的試驗結(jié)果中可以看出，當最小支持度的值增大的時候，傳統(tǒng)的Apriori算法與改進后的算法相比，時間開銷相差不是很大，主要是因為較高的支持度會使得候選項集大大減少，所以減少了算法掃描數(shù)據(jù)庫時的時間開銷。由圖2可以看出在不同支持度下的原Apriori算法與改進后的算法產(chǎn)生的頻繁項集的個數(shù)不同，隨著支持度的增大，產(chǎn)生的頻繁項集的個數(shù)相差減小，當支持度較小時，可以很明顯的看出改進后的算法產(chǎn)生的頻繁項集的個數(shù)遠遠少于原算法產(chǎn)生的個數(shù)。

4 結(jié)束語

文中對于Apriori算法進行了分析，對于其復雜性以及缺陷提出了一種改進方案，主要是從減少掃描事務數(shù)據(jù)庫的頻度、提高算法對于內(nèi)存的利用率方面改進，通過實驗分析驗證了改進算法的有效性。將改進后的Apriori算法應用于高校學生信息系統(tǒng)中，將對課程建設的合理性和教學水平的提高有很大的實用價值，對于課程開設的順序以及要開設哪些課程如果還是像以往一樣單憑經(jīng)驗去決定，無法科學準確的給予學生開設最需要的課程，通過挖掘?qū)W科之間的關聯(lián)規(guī)則，可以客觀的去了解它們的關系，有助于今后的課程安排，關聯(lián)規(guī)則挖掘在高校中的應用將會越來越多。

[1]Han J,Pei J,Yin Y.Mining frequent patternswithout candidate generation[C]//Acm Sigmod Record,2000,29(2):1-12.

[2]林郎碟,王燦輝.Apriori算法在圖書推薦服務中的應用與研究[J].計算機技術與發(fā)展,2011(5):22-24，28.

[3]Agrawal R,Imieliński T,Swami A.Mining association rules between sets of items in large databases[C]//ACM SIGMOD Record.ACM,1993,22(2):207-216.

[4]Toivonen H.Sampling large databases forassociation rules[C]//VLDB,1996(96):134-145.

[5]何月順.關聯(lián)規(guī)則挖掘技術的研究及應用[D].南京：南京航空航天大學,2010.

[6]陳偉.Apriori算法的優(yōu)化方法[J].計算機技術與發(fā)展,2009(6):80-83.

[7]林佳雄,黃戰(zhàn).基于數(shù)組向量的Apriori算法改進[J].計算機應用與軟件,2011(5):268-271.

[8]劉宗成，張忠林，田苗鳳.基于關聯(lián)規(guī)則的網(wǎng)絡行為分析[J].電子科技,2015(9):16-18.