興趣度在基于關(guān)聯(lián)分析的選課指導(dǎo)系統(tǒng)中的研究與應(yīng)用

摘 要：簡(jiǎn)要地介紹了數(shù)據(jù)挖掘技術(shù)，通過對(duì)關(guān)聯(lián)分析的經(jīng)典算法Apriori在學(xué)生選課指導(dǎo)系統(tǒng)中的應(yīng)用分析，發(fā)現(xiàn)了Apriori不適合學(xué)生選課指導(dǎo)系統(tǒng)的缺陷。提出了增加興趣度閾值以減少產(chǎn)生的無用規(guī)則，提高挖掘精度，克服原系統(tǒng)缺陷的新算法，為學(xué)生選課輔助決策提供了良好的理論依據(jù)和實(shí)現(xiàn)方法。

關(guān)鍵詞：數(shù)據(jù)挖掘；關(guān)聯(lián)規(guī)則；興趣度；選課指導(dǎo)

中圖法分類號(hào)：TP391文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1001—3695(2007)02—0246—03

隨著高校教育體制的改革，學(xué)分制的推廣，學(xué)生選課的自主性越來越大。但是學(xué)生在選課的過程中，由于對(duì)所選課程需要的基礎(chǔ)知識(shí)認(rèn)識(shí)不足，導(dǎo)致選課具有一定的盲目性。對(duì)此，通過對(duì)高校教學(xué)管理系統(tǒng)中學(xué)生歷史成績(jī)數(shù)據(jù)庫(kù)進(jìn)行基于關(guān)聯(lián)規(guī)則的分析，得出課程之間的關(guān)聯(lián)程度，進(jìn)而獲得所選課程的相關(guān)先修課程，使學(xué)生在選課過程中得到一些有意義的指導(dǎo)信息，在一定程度上避免其選課的盲目性。傳統(tǒng)的關(guān)聯(lián)規(guī)則主要是考慮稱作可信度和支持度的閾值，但在學(xué)生選課指導(dǎo)系統(tǒng)的實(shí)際應(yīng)用中發(fā)現(xiàn)僅考慮可信度和支持度時(shí)，存在挖掘出來規(guī)則數(shù)量過多；有些規(guī)則具有誤導(dǎo)性和欺騙性；同時(shí)無法明確表示一門課程是另外一門課程的先修課程還是后繼課程；只能得出兩門課程之間有相關(guān)性；不利于學(xué)生根據(jù)情況判斷自己是否已經(jīng)學(xué)習(xí)過某門課程的先修課程等問題。本文引入另外一個(gè)閾值即興趣度，來實(shí)現(xiàn)過濾這些無用甚至有誤導(dǎo)性的規(guī)則，同時(shí)使挖掘出的規(guī)則能夠體現(xiàn)出課程的先后關(guān)系。

1 學(xué)生選課指導(dǎo)系統(tǒng)

學(xué)生選課指導(dǎo)系統(tǒng)就是指對(duì)高校教學(xué)管理系統(tǒng)中的學(xué)生成績(jī)數(shù)據(jù)庫(kù)進(jìn)行關(guān)聯(lián)規(guī)則挖掘，從中挖掘出滿足最小支持度和最小可信度的規(guī)則。其系統(tǒng)框架如圖1所示。

圖1中成績(jī)數(shù)據(jù)庫(kù)為學(xué)校的學(xué)生成績(jī)數(shù)據(jù)庫(kù)。系統(tǒng)首先對(duì)原始的成績(jī)數(shù)據(jù)庫(kù)進(jìn)行數(shù)據(jù)的選擇、凈化、轉(zhuǎn)換等預(yù)處理，建立起基于園區(qū)網(wǎng)絡(luò)教務(wù)平臺(tái)的數(shù)據(jù)倉(cāng)庫(kù)[1]，然后在此數(shù)據(jù)倉(cāng)庫(kù)的基礎(chǔ)上進(jìn)行數(shù)據(jù)挖掘，通過對(duì)結(jié)果的評(píng)估，即可得出有效規(guī)則，用于輔助決策。當(dāng)決策者對(duì)于評(píng)估結(jié)果不滿意時(shí)，可以回溯到數(shù)據(jù)挖掘階段，重新進(jìn)行挖掘。

在學(xué)生選課指導(dǎo)系統(tǒng)[2，3]中用到了數(shù)據(jù)挖掘技術(shù)中的關(guān)聯(lián)規(guī)則分析。以下對(duì)關(guān)聯(lián)規(guī)則作簡(jiǎn)單的介紹。

2 數(shù)據(jù)挖掘及關(guān)聯(lián)規(guī)則

2.1 數(shù)據(jù)挖掘

數(shù)據(jù)挖掘[4]是20世紀(jì)80年代后期興起的學(xué)科，指從大型數(shù)據(jù)庫(kù)或數(shù)據(jù)倉(cāng)庫(kù)中提取隱含的、先前未知的、對(duì)決策有潛在價(jià)值的知識(shí)和規(guī)則。

2.2 關(guān)聯(lián)規(guī)則

關(guān)聯(lián)規(guī)則[5]是數(shù)據(jù)挖據(jù)的一個(gè)重要分支，發(fā)現(xiàn)形如“如果〈條件〉，那么〈結(jié)論〉”的規(guī)則的方法。在關(guān)聯(lián)規(guī)則中，D是所有事務(wù)的集合，相當(dāng)于數(shù)據(jù)庫(kù)中的記錄集合，假設(shè)X，Y是數(shù)據(jù)項(xiàng)集，則關(guān)聯(lián)規(guī)則表示為(T中包含X)(T 中包含Y)。其意義在于一次交易中（數(shù)據(jù)庫(kù)中的一條記錄）存在X項(xiàng)目，則該交易中也存在Y項(xiàng)目。通常簡(jiǎn)寫為XY， X稱為關(guān)聯(lián)規(guī)則的前件， Y稱為關(guān)聯(lián)規(guī)則的后件，稱為關(guān)聯(lián)操作。

關(guān)聯(lián)規(guī)則的挖掘?qū)嶋H上就是首先找出事務(wù)數(shù)據(jù)集D中所有大于等于用戶指定最小支持度的頻集，然后在頻集上根據(jù)用戶指定的最小可信度確定規(guī)則的取舍，最后得到關(guān)聯(lián)規(guī)則。

學(xué)生選課指導(dǎo)系統(tǒng)就是用經(jīng)典的關(guān)聯(lián)規(guī)則算法——Apriori[6]算法，對(duì)基于學(xué)生成績(jī)數(shù)據(jù)庫(kù)的數(shù)據(jù)倉(cāng)庫(kù)進(jìn)行挖掘來得到課程之間的關(guān)聯(lián)規(guī)則。

3 引入興趣度閾值的關(guān)聯(lián)規(guī)則挖掘方法

3.1 興趣度提出的背景

在實(shí)際的學(xué)生選課指導(dǎo)系統(tǒng)應(yīng)用中，發(fā)現(xiàn)僅考慮可信度c和支持度s是不夠的，并且還可能會(huì)引起誤導(dǎo)。例如：在學(xué)生成績(jī)庫(kù)中有20%的學(xué)生《離散數(shù)學(xué)》和《數(shù)據(jù)結(jié)構(gòu)》成績(jī)均為優(yōu)，而《離散數(shù)學(xué)》成績(jī)?yōu)閮?yōu)的學(xué)生中40%的人《數(shù)據(jù)結(jié)構(gòu)》成績(jī)?yōu)閮?yōu)，由這兩個(gè)足夠大的支持度和可信度我們推出“加強(qiáng)《離散數(shù)學(xué)》的教學(xué)有助于《數(shù)據(jù)結(jié)構(gòu)》成績(jī)的提高”這條看似有用的規(guī)則。但實(shí)際情況是原始記錄顯示選修《數(shù)據(jù)結(jié)構(gòu)》的學(xué)生50%成績(jī)?yōu)閮?yōu)，換句話說，其中有30%的學(xué)生《離散數(shù)學(xué)》成績(jī)非優(yōu)。任意一個(gè)我們不知道是否選修《離散數(shù)學(xué)》的學(xué)生的《數(shù)據(jù)結(jié)構(gòu)》成績(jī)優(yōu)秀的概率(50%)高于已知選修《離散數(shù)學(xué)》成績(jī)?yōu)閮?yōu)秀的學(xué)生的概率(40%)。很顯然，上面推出的這條規(guī)則是誤導(dǎo)性的。由于用傳統(tǒng)關(guān)聯(lián)規(guī)則Apriori算法推導(dǎo)，會(huì)得出很多類似“加強(qiáng)《離散數(shù)學(xué)》的教學(xué)有助于《數(shù)據(jù)結(jié)構(gòu)》成績(jī)的提高”這樣有誤導(dǎo)性的規(guī)則，使規(guī)則數(shù)量大大增加，而且由于此規(guī)則有一定的誤導(dǎo)性，對(duì)學(xué)生選課的指導(dǎo)意義大大降低，所以應(yīng)該過濾掉此類規(guī)則。但是傳統(tǒng)的關(guān)聯(lián)規(guī)則算法無法過濾此類規(guī)則，所以本文在傳統(tǒng)的關(guān)聯(lián)規(guī)則算法中增加第三個(gè)閾值即興趣度[7]。在研究了興趣度的形式化定義和計(jì)算方法后，本文最后討論了引入興趣度后的實(shí)際效果。

3.2 興趣度的定義

在定義興趣度之前，先給出幾個(gè)有關(guān)的定義。

P(X)表示交易中X發(fā)生的概率，P(XY)表示交易中X與Y同時(shí)發(fā)生的概率。若P(XY)= P(X) P(Y)，則定義交易中X與Y相互獨(dú)立；若P(XY)≠ P(X) P(Y)，則定義交易中X與Y不相互獨(dú)立；如果P(XY)≠ P(X) P(Y)，則定義X，Y相關(guān)。

其中，corr(x，y)是規(guī)則的相關(guān)程度。當(dāng)corr(x，y)>1時(shí)，P(XY)>P(X) P(Y)，則說明X的出現(xiàn)與Y的出現(xiàn)正相關(guān)；當(dāng)corr(x，y)<1時(shí)，X與Y負(fù)相關(guān)；當(dāng)corr(x，y)=1時(shí)，X與Y獨(dú)立。所以，利用RI可以判斷出規(guī)則的三種情況，然后再按照用戶的需求只保留感興趣的規(guī)則。

3.3 算法描述

我們對(duì)傳統(tǒng)的只考慮可信度和支持度閾值的關(guān)聯(lián)規(guī)則挖掘方法進(jìn)行改進(jìn)，將它們運(yùn)用到引入了有趣度閾值以后的系統(tǒng)。我們對(duì)大項(xiàng)目集內(nèi)的每一個(gè)可能生成的規(guī)則均計(jì)算它的可信度和有趣度，可能出現(xiàn)以下四種情況（minconfidence代表最小可信度閾值，RI表示有趣度閾值）：

用價(jià)值，因本文不討論項(xiàng)目取非的情況，所以這里認(rèn)為它不是我們需要的，淘汰。

整個(gè)興趣度關(guān)聯(lián)挖掘算法描述如下：

輸入 最小支持度、最小可信度、有趣度閾值：minsupport，minconfidence，ri

輸出 所有有趣的強(qiáng)關(guān)聯(lián)規(guī)則

首先利用上面已經(jīng)介紹的經(jīng)典Apriori產(chǎn)生出大項(xiàng)目集。

再利用大項(xiàng)目集產(chǎn)生有興趣度約束的關(guān)聯(lián)規(guī)則:

其算法流程為：首先在交易數(shù)據(jù)庫(kù)中計(jì)算出支持度大于最小支持度的大項(xiàng)目集，然后檢查規(guī)則的可信度和興趣度，輸出符合規(guī)則的興趣規(guī)則。

3.4 應(yīng)用結(jié)果表述

根據(jù)上述算法來驗(yàn)證如上《離散數(shù)學(xué)》和《數(shù)據(jù)結(jié)構(gòu)》課程的例子，在學(xué)生成績(jī)庫(kù)中離散數(shù)學(xué)成績(jī)是優(yōu)的為50%，數(shù)據(jù)結(jié)構(gòu)是優(yōu)的為50%，而兩項(xiàng)均是優(yōu)的為20%，由此corr=0.20.5×0.5=0.8<1，所以《離散數(shù)學(xué)》和《數(shù)據(jù)結(jié)構(gòu)》是負(fù)相關(guān)的，是否定的，根據(jù)興趣度定義，算法既不會(huì)產(chǎn)生規(guī)則《離散數(shù)學(xué)》《數(shù)據(jù)結(jié)構(gòu)》，也不會(huì)產(chǎn)生規(guī)則《數(shù)據(jù)結(jié)構(gòu)》《離散數(shù)學(xué)》。這樣就過濾掉了類似的無用規(guī)則，同時(shí)由于直接得出規(guī)則的前后件關(guān)系，有利于學(xué)生根據(jù)自己的情況判斷自己是否已學(xué)習(xí)過要選修的課程的先修課程，來確定是否選擇某門課程。

在用引入興趣度閾值的關(guān)聯(lián)規(guī)則挖掘方法對(duì)局部的學(xué)生成績(jī)數(shù)據(jù)庫(kù)挖掘后，得出了如表1所示的興趣度閾值和挖掘出的規(guī)則數(shù)目的關(guān)系。

根據(jù)表1可以看出，隨著興趣度閾值的提高，挖掘出的規(guī)則的數(shù)量急劇減少，成功地實(shí)現(xiàn)了無用規(guī)則的過濾。

4 結(jié)束語

隨著高校數(shù)據(jù)庫(kù)的不斷增大，如何將數(shù)據(jù)挖掘技術(shù)更好地應(yīng)用到高校教學(xué)系統(tǒng)中，成為一個(gè)擺在我們面前的實(shí)際問題。本文通過對(duì)傳統(tǒng)關(guān)聯(lián)規(guī)則的分析，找出其不適合于學(xué)生選課系統(tǒng)的缺陷，提出了通過使用興趣度閾值的方法來改進(jìn)。學(xué)生可以通過參考從加入興趣度閾值后的選課指導(dǎo)系統(tǒng)中挖掘出來的規(guī)則作為輔助手段，來選擇自己感興趣的課程。下一步的工作就是對(duì)經(jīng)典的Apriori算法進(jìn)行改進(jìn)，使得挖掘的效率更高。

本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文。