【摘要】高校教務(wù)管理系統(tǒng)將產(chǎn)生海量數(shù)據(jù)，這些數(shù)據(jù)中可能隱藏著一些我們以前不知道的大量有用信息。文章采用Apriori算法，對(duì)高校學(xué)生成績(jī)數(shù)據(jù)進(jìn)行關(guān)聯(lián)規(guī)則分析，通過(guò)學(xué)生成績(jī)是否優(yōu)秀來(lái)找到各對(duì)應(yīng)課程之間的相關(guān)性，從而科學(xué)地安排教學(xué)和輔助教學(xué)管理決策。

【關(guān)鍵詞】數(shù)據(jù)挖掘;關(guān)聯(lián)規(guī)則;成績(jī);Apriori

【中圖分類(lèi)號(hào)】G420 【文獻(xiàn)標(biāo)識(shí)碼】A 【論文編號(hào)】1009—8097(2010)05—0082—03

引言

當(dāng)前，大多高校已采用基于Web的教務(wù)管理系統(tǒng)來(lái)開(kāi)展教務(wù)管理工作。在教務(wù)管理過(guò)程中，將產(chǎn)生海量數(shù)據(jù)，其中也隱含著大量的信息和知識(shí)。如何發(fā)掘及利用這些信息和知識(shí)是當(dāng)前高校教務(wù)管理過(guò)程中的新課題。

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

一 關(guān)聯(lián)規(guī)則的基本概念

設(shè)I=是二進(jìn)制文字的集合，其中的元素稱為項(xiàng)(item)。記D為交易(transaction)T的集合，這里交易T是項(xiàng)的集合，并且T I。對(duì)應(yīng)每一個(gè)交易有惟一的標(biāo)識(shí)，如交易號(hào)，記作TID。設(shè)X是一個(gè)I中項(xiàng)的集合，如果X T，那么稱交易T包含X。

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

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

項(xiàng)的集合稱為項(xiàng)集(itemset)。包含k個(gè)項(xiàng)的項(xiàng)集稱為k—項(xiàng)集。項(xiàng)集的出現(xiàn)頻率是包含項(xiàng)集的事務(wù)數(shù)，簡(jiǎn)稱為項(xiàng)集的頻率、支持度或計(jì)數(shù)。如果項(xiàng)集滿足最小支持度(由用戶或領(lǐng)域?qū)＜以O(shè)定)，則稱它為頻繁項(xiàng)集。給定一個(gè)交易集D，挖掘關(guān)聯(lián)規(guī)則問(wèn)題就是產(chǎn)生支持度和可信度分別大于最小支持度(minsupp)和最小可信度(minconf)的關(guān)聯(lián)規(guī)則[2]。

二 Apriori算法介紹

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

性質(zhì)1 任何頻集的子集必定是頻集。

性質(zhì)2 任何非頻繁項(xiàng)集的超集必定是非頻繁項(xiàng)集。

算法的基本思想:首先找出所有的頻集，然后由頻集產(chǎn)生強(qiáng)關(guān)聯(lián)規(guī)則[3，4]。

Apriori核心算法分析:

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

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); ∥事務(wù)t中包含的候選集do

for all candidates c∈Ct

c.count ++ ;

end

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

end

Answer=∪k Lk ;

三 基于Apriori算法的學(xué)生成績(jī)關(guān)聯(lián)分析

1 數(shù)據(jù)預(yù)處理

首先進(jìn)行維規(guī)約，將與最終關(guān)聯(lián)分析無(wú)關(guān)的維度清除;然后將關(guān)系數(shù)據(jù)庫(kù)中的數(shù)值屬性離散化，以便能應(yīng)用到算法中?？紤]到最終的規(guī)則希望體現(xiàn)高分課程之間的關(guān)聯(lián)關(guān)系，故采用如下離散方法:將相關(guān)課程的課程名簡(jiǎn)化為A、B、C等，同時(shí)，將成績(jī)?cè)?0分以上記為1，其余記為0[5，6，7，8]。

原始數(shù)據(jù)表如表1，通過(guò)存儲(chǔ)過(guò)程將成績(jī)離散化后如表2:

2 使用Apriori算法挖掘課程之間的關(guān)聯(lián)關(guān)系

實(shí)驗(yàn)環(huán)境:

操作系統(tǒng):WinXP

數(shù)據(jù)庫(kù):SQL SERVER2000(由于僅僅考慮課程之間的關(guān)聯(lián)關(guān)系，數(shù)據(jù)來(lái)源單一，故未考慮再構(gòu)建數(shù)據(jù)倉(cāng)庫(kù))

開(kāi)發(fā)工具:JSP

實(shí)驗(yàn)過(guò)程:

(1) 直接使用存儲(chǔ)過(guò)程將數(shù)據(jù)庫(kù)中的成績(jī)數(shù)據(jù)進(jìn)行處理，得到離散化數(shù)據(jù)，存入表candidate_1中;

(2) 設(shè)計(jì)用戶交互界面，用于設(shè)置關(guān)聯(lián)規(guī)則挖掘的最小可信度和最小支持度;

(3) 采用Apriori算法，實(shí)現(xiàn)對(duì)學(xué)生高分成績(jī)的關(guān)聯(lián)性分析，以此推斷課程之間的關(guān)聯(lián)關(guān)系。具體步驟如下:

①掃描表candidate_1，根據(jù)最小設(shè)置的可信度和支持度閾值，將候選集項(xiàng)目進(jìn)行過(guò)濾，得到頻繁1-項(xiàng)集;

②產(chǎn)生新的候選項(xiàng)集:將相應(yīng)的頻繁(n-1)-項(xiàng)集(n>1)進(jìn)行自然連接，產(chǎn)生n的候選項(xiàng)集，存于candidate_n中;

③計(jì)算候選n-項(xiàng)集的可信度和支持度，根據(jù)設(shè)置的可信度和支持度閾值進(jìn)行過(guò)濾，得到頻繁n-項(xiàng)集。

④若發(fā)現(xiàn)某候選集數(shù)目為零，停止計(jì)算。

⑤生成關(guān)聯(lián)規(guī)則，同時(shí)將頻繁項(xiàng)及其支持度、可信度在頁(yè)面中顯示。

3 實(shí)驗(yàn)結(jié)果

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

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

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

4 規(guī)則理解

根據(jù)圖2，我們可以得到兩條關(guān)聯(lián)規(guī)則:

(1) C語(yǔ)言 管理信息系統(tǒng)，其支持度為0.36，說(shuō)明在所有的成績(jī)數(shù)據(jù)中，這兩門(mén)課程成績(jī)均超過(guò)90分的記錄所占比率為36%(大于設(shè)置的最小支持度0.3);而所有C語(yǔ)言成績(jī)超過(guò)90分的記錄中，管理信息系統(tǒng)成績(jī)超過(guò)90分的記錄占67%(大于設(shè)置的最小置信度0.6)。

(2) 同樣，面向?qū)ο蟪绦蛟O(shè)計(jì) JSP技術(shù)及應(yīng)用，其支持度為0.31，置信度為0.61，均大于設(shè)置的最小支持度和最小置信度。

5 規(guī)則應(yīng)用

根據(jù)規(guī)則1，可以認(rèn)為課程C語(yǔ)言與課程管理信息系統(tǒng)具有一定的關(guān)聯(lián)性，我們可以根據(jù)此規(guī)則更好的促進(jìn)教學(xué)效果，如:

(1) 如果加強(qiáng)對(duì)先修課程C語(yǔ)言的能使后續(xù)課程管理信息系統(tǒng)的學(xué)習(xí)效果更好;

(2) 對(duì)先修課程C語(yǔ)言安排教學(xué)經(jīng)驗(yàn)豐富的教師授課;

(3) 對(duì)先修課程C語(yǔ)言安排教學(xué)條件更好的教室授課。

如果得到的關(guān)聯(lián)規(guī)則涉及到專(zhuān)業(yè)核心課，則更應(yīng)該強(qiáng)調(diào)規(guī)則中的先修課的學(xué)習(xí)。規(guī)則2的應(yīng)用同樣類(lèi)似。

四 結(jié)束語(yǔ)

通過(guò)Apriori算法能夠挖掘出課程之間的關(guān)聯(lián)關(guān)系，為高校培養(yǎng)計(jì)劃及課程設(shè)置提供決策基礎(chǔ)，但Apriori方法一些固有的缺陷還是無(wú)法克服:(1)Apriori可能產(chǎn)生大量的候選集;(2)生成候選項(xiàng)目時(shí)由于模式匹配引起巨大時(shí)空開(kāi)銷(xiāo)。在后續(xù)的工作中，筆者將致力于對(duì)此改進(jìn)并進(jìn)一步研究:

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

(2) 除對(duì)高分課程進(jìn)行關(guān)聯(lián)分析之外，再考慮對(duì)低分課程進(jìn)行關(guān)聯(lián)分析，已發(fā)現(xiàn)更多的規(guī)則;

(3) 除考慮用關(guān)聯(lián)規(guī)則之外，后續(xù)將使用分類(lèi)、聚類(lèi)等方法對(duì)教務(wù)數(shù)據(jù)進(jìn)行多方面分析，更好地為高校教學(xué)服務(wù)。

參考文獻(xiàn)

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

[2] 翁敬農(nóng)譯.數(shù)據(jù)挖掘教程[M].北京:清華大學(xué)出版社， 2003:53-61.

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

[4] 康曉東.基于數(shù)據(jù)倉(cāng)庫(kù)的數(shù)據(jù)挖掘技術(shù)[M].北京:機(jī)械工業(yè)出版社，2004:131-175.

[5] 黃鵬鶴.關(guān)聯(lián)規(guī)則挖掘及其在教務(wù)管理中的應(yīng)用[D].大連:大連交通大學(xué)，2005.

[6] 季順寧.關(guān)聯(lián)規(guī)則在課程建設(shè)中的應(yīng)用研究[D].上海:華東師范大學(xué)，2006.

[7] 王婷婷.數(shù)據(jù)倉(cāng)庫(kù)和數(shù)據(jù)挖掘在學(xué)生成績(jī)分析中的應(yīng)用研究[D].武漢:武漢科技大學(xué)，2007.

[8] 符開(kāi)耀，朱文湘，朱建軍.關(guān)聯(lián)規(guī)則分析及其在教務(wù)管理系統(tǒng)中的應(yīng)用[J].微計(jì)算機(jī)應(yīng)用，2008，28(7).

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

[10] 易彤，徐寶文，吳方君.一種基于FP樹(shù)的挖掘關(guān)聯(lián)規(guī)則的增量更新算法[J].計(jì)算機(jī)學(xué)報(bào)，2004，(5).

[11] 胡向前.基于FP-Tree的多層關(guān)聯(lián)規(guī)則挖掘算法研究[D].重慶:重慶大學(xué)，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] 鄧硯谷，王麗珍.對(duì)FP-Tree頭表結(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)的改進(jìn)[J].計(jì)算機(jī)工程與應(yīng)用，2004，40(25).