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

胡淑新，李長云，吳岳忠

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

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

1 Apriori算法概述

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

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

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

2 以數組向量為存儲結構改進Apriori算法

2.1 基于數組向量的算法改進

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

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

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

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

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

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

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

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

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

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

7)foreach c∈CAi[j]

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

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

10)return L=UkLk;

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

1)連接操作

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

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

2)修剪操作

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

2.2 改進Apriori算法在高校學生信息系統中的應用

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

表1 原始數據庫Tab.1 Original database

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

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

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

表2 數組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存儲的計數，最后得到頻繁2項集。

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

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

7)由最長的頻繁集L3產生的關聯規則及由次長的頻繁集L2產生的關聯規則如表4所示。

根據已經設定的最小支持度為2/3，置信度為1，可以得到篩選后的較強的關聯規則。

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

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

表 4頻繁3項集關聯規則及頻繁2項集關聯規則Tab.4 Association ru les in frequent item sets of size 3 and Association rules in frequent item sets of size 2

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

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

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

改進后的基于數組的Apriori算法[8]與經典的Apriori算法相比，優點如下：

1)算法對數據庫的掃描次數減少，只需掃描一次，減少了訪問事務的次數，并且采用了合理的結構來表示事務項，尋可以大大減少內存占用率。

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

實驗結果及分析：

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

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

圖2 不同支持度下產生的頻繁項集個數Fig.2 Frequent itemsets in different support

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

4 結束語

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

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

[2]林郎碟,王燦輝.Apriori算法在圖書推薦服務中的應用與研究[J].計算機技術與發展,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]何月順.關聯規則挖掘技術的研究及應用[D].南京：南京航空航天大學,2010.

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

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

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