基于關聯規則的高校課程關聯性分析

【摘要】高校教務管理系統將產生海量數據，這些數據中可能隱藏著一些我們以前不知道的大量有用信息。文章采用Apriori算法，對高校學生成績數據進行關聯規則分析，通過學生成績是否優秀來找到各對應課程之間的相關性，從而科學地安排教學和輔助教學管理決策。

【關鍵詞】數據挖掘;關聯規則;成績;Apriori

【中圖分類號】G420 【文獻標識碼】A 【論文編號】1009—8097(2010)05—0082—03

引言

當前，大多高校已采用基于Web的教務管理系統來開展教務管理工作。在教務管理過程中，將產生海量數據，其中也隱含著大量的信息和知識。如何發掘及利用這些信息和知識是當前高校教務管理過程中的新課題。

數據挖掘(Date Mining，簡稱DM)是一種決策支持過程，它是從大量的、不完全的、有噪聲的、模糊的、隨機的實際應用數據中，提取隱含在其中的但又是潛在有用的信息和知識的過程[1]。它涉及到對數據庫中大量數據進行抽取、轉換、分析以及模型化處理，從中提取輔助決策的關鍵性數據。數據挖掘，可以幫助決策者尋找規律，發現被忽略的要素，預測趨勢，進行決策。關聯規則(Association Rule，簡稱AR)是當前數據挖掘研究的主要模式之一，側重于確定數據中不同領域之間的聯系，找出滿足給定支持度和可信度閾值的多個域之間的依賴關系。我們可以考慮使用關聯規則來挖掘教務信息中隱含的知識。

一 關聯規則的基本概念

設I=是二進制文字的集合，其中的元素稱為項(item)。記D為交易(transaction)T的集合，這里交易T是項的集合，并且T I。對應每一個交易有惟一的標識，如交易號，記作TID。設X是一個I中項的集合，如果X T，那么稱交易T包含X。

一個關聯規則是形如X Y的蘊涵式，這里X I，Y I，并且X∩Y= 。規則X Y在交易數據庫D中的支持度(support)是交易集中包含X和Y的交易數與所有交易數之比，記為support(X Y)，即support(X Y)= {T:X∪Y T，T∈D}|/|D|。

規則X Y在交易集中的可信度(confidence)是指包含X和Y的交易數與包含X的交易數之比，記為confidence(X Y)，即confidence (X Y)= |{T:X∪Y T，T∈D}|/|{T:X T，T∈D}|。

項的集合稱為項集(itemset)。包含k個項的項集稱為k—項集。項集的出現頻率是包含項集的事務數，簡稱為項集的頻率、支持度或計數。如果項集滿足最小支持度(由用戶或領域專家設定)，則稱它為頻繁項集。給定一個交易集D，挖掘關聯規則問題就是產生支持度和可信度分別大于最小支持度(minsupp)和最小可信度(minconf)的關聯規則[2]。

二 Apriori算法介紹

Agrawal等人于1993年首先提出了挖掘顧客交易數據庫中項集間的關聯規則[1]，并設計了一個基本算法，其核心是基于頻集理論的遞推方法，即基于兩階段頻集思想的方法，將關聯規則的設計分解為兩個子問題:(1)發現頻集。這個子問題是最重要的，開銷最大，因此，各種算法主要致力于提高發現頻集的效率。(2)根據所獲得的頻繁項集，產生強關聯規則。根據定義這些規則必須滿足信任度閾值。由于步驟(2)中的操作極為簡單，因此挖掘關聯規則的整個性能就由步驟(1)中的操作處理所決定。該算法利用了如下兩個基本性質:

性質1 任何頻集的子集必定是頻集。

性質2 任何非頻繁項集的超集必定是非頻繁項集。

算法的基本思想:首先找出所有的頻集，然后由頻集產生強關聯規則[3，4]。

Apriori核心算法分析:

Apriori算法是由Agrawal等于1994年提出的[2]，其基本思路是重復掃描數據庫。其核心程序簡要描述如下:

L1={large1-itemsets};

for(k = 2;Lk - 1 ≠;k ++ ) do begin

Ck=apriori_gen (Lk - 1 ); ∥新的候選集

for all transactions t∈D do begin

Ct=subset (Ck，t); ∥事務t中包含的候選集do

for all candidates c∈Ct

c.count ++ ;

end

Lk={c∈Ck|c.count minsup}

end

Answer=∪k Lk ;

三 基于Apriori算法的學生成績關聯分析

1 數據預處理

首先進行維規約，將與最終關聯分析無關的維度清除;然后將關系數據庫中的數值屬性離散化，以便能應用到算法中。考慮到最終的規則希望體現高分課程之間的關聯關系，故采用如下離散方法:將相關課程的課程名簡化為A、B、C等，同時，將成績在90分以上記為1，其余記為0[5，6，7，8]。

原始數據表如表1，通過存儲過程將成績離散化后如表2:

2 使用Apriori算法挖掘課程之間的關聯關系

實驗環境:

操作系統:WinXP

數據庫:SQL SERVER2000(由于僅僅考慮課程之間的關聯關系，數據來源單一，故未考慮再構建數據倉庫)

開發工具:JSP

實驗過程:

(1) 直接使用存儲過程將數據庫中的成績數據進行處理，得到離散化數據，存入表candidate_1中;

(2) 設計用戶交互界面，用于設置關聯規則挖掘的最小可信度和最小支持度;

(3) 采用Apriori算法，實現對學生高分成績的關聯性分析，以此推斷課程之間的關聯關系。具體步驟如下:

①掃描表candidate_1，根據最小設置的可信度和支持度閾值，將候選集項目進行過濾，得到頻繁1-項集;

②產生新的候選項集:將相應的頻繁(n-1)-項集(n>1)進行自然連接，產生n的候選項集，存于candidate_n中;

③計算候選n-項集的可信度和支持度，根據設置的可信度和支持度閾值進行過濾，得到頻繁n-項集。

④若發現某候選集數目為零，停止計算。

⑤生成關聯規則，同時將頻繁項及其支持度、可信度在頁面中顯示。

3 實驗結果

(1) 設置支持度及置信度:

說明:維度選擇主要是控制頻繁n-項集中n的數目。(設置最小支持度:0.3，最小置信度:0.6，選擇生成頻繁2-項集)

(2) 分析結果如圖2所示:

4 規則理解

根據圖2，我們可以得到兩條關聯規則:

(1) C語言 管理信息系統，其支持度為0.36，說明在所有的成績數據中，這兩門課程成績均超過90分的記錄所占比率為36%(大于設置的最小支持度0.3);而所有C語言成績超過90分的記錄中，管理信息系統成績超過90分的記錄占67%(大于設置的最小置信度0.6)。

(2) 同樣，面向對象程序設計 JSP技術及應用，其支持度為0.31，置信度為0.61，均大于設置的最小支持度和最小置信度。

5 規則應用

根據規則1，可以認為課程C語言與課程管理信息系統具有一定的關聯性，我們可以根據此規則更好的促進教學效果，如:

(1) 如果加強對先修課程C語言的能使后續課程管理信息系統的學習效果更好;

(2) 對先修課程C語言安排教學經驗豐富的教師授課;

(3) 對先修課程C語言安排教學條件更好的教室授課。

如果得到的關聯規則涉及到專業核心課，則更應該強調規則中的先修課的學習。規則2的應用同樣類似。

四 結束語

通過Apriori算法能夠挖掘出課程之間的關聯關系，為高校培養計劃及課程設置提供決策基礎，但Apriori方法一些固有的缺陷還是無法克服:(1)Apriori可能產生大量的候選集;(2)生成候選項目時由于模式匹配引起巨大時空開銷。在后續的工作中，筆者將致力于對此改進并進一步研究:

(1) 使用不產生候選集的FP-增量算法及其改進算法[9，10，11，12，13]對教務信息進行挖掘;

(2) 除對高分課程進行關聯分析之外，再考慮對低分課程進行關聯分析，已發現更多的規則;

(3) 除考慮用關聯規則之外，后續將使用分類、聚類等方法對教務數據進行多方面分析，更好地為高校教學服務。

參考文獻

[1] [加] JIAWEI HAN，MICHLINE KAMBER，范明，孟小峰等譯.數據挖掘概念與技術[M].北京:機械工業出版社，2001.

[2] 翁敬農譯.數據挖掘教程[M].北京:清華大學出版社， 2003:53-61.

[3] 林杰斌，劉明德，陳湘等.數據挖掘與OLAP理論與實務[M].北京:清華大學出版社，2002:58-65.

[4] 康曉東.基于數據倉庫的數據挖掘技術[M].北京:機械工業出版社，2004:131-175.

[5] 黃鵬鶴.關聯規則挖掘及其在教務管理中的應用[D].大連:大連交通大學，2005.

[6] 季順寧.關聯規則在課程建設中的應用研究[D].上海:華東師范大學，2006.

[7] 王婷婷.數據倉庫和數據挖掘在學生成績分析中的應用研究[D].武漢:武漢科技大學，2007.

[8] 符開耀，朱文湘，朱建軍.關聯規則分析及其在教務管理系統中的應用[J].微計算機應用，2008，28(7).

[9] 顏躍進，李舟軍，陳火旺.基于FP-Tree有效挖掘最大頻繁項集[J].軟件學報，2005，16(2):215-222.

[10] 易彤，徐寶文，吳方君.一種基于FP樹的挖掘關聯規則的增量更新算法[J].計算機學報，2004，(5).

[11] 胡向前.基于FP-Tree的多層關聯規則挖掘算法研究[D].重慶:重慶大學，2005.

[12] AGRAWAL R， IMIELINSKI T， SWAMI A. Mining association rules between sets of items in large Databases[C].In Proc of the ACM SIGMOD International conference on Management of Data， Washington DC，1993:207~216.

[13] 鄧硯谷，王麗珍.對FP-Tree頭表結點數據結構的改進[J].計算機工程與應用，2004，40(25).