關(guān)聯(lián)規(guī)則挖掘算法在選課系統(tǒng)中的應(yīng)用研究

［摘要］ 針對(duì)高校網(wǎng)上選課工作中遇到的一些實(shí)際矛盾，本文將關(guān)聯(lián)規(guī)則挖掘算法應(yīng)用于選課指導(dǎo)系統(tǒng)中，對(duì)系統(tǒng)中存儲(chǔ)的大量數(shù)據(jù)進(jìn)行挖掘，從中提取出潛在的有用的信息，為高校選修課的開(kāi)設(shè)及學(xué)生選課行為提供決策支持。

［關(guān)鍵詞］ 數(shù)據(jù)挖掘； 關(guān)聯(lián)規(guī)則挖掘； 選課系統(tǒng)； FP-growth算法

doi : 10 . 3969 / j . issn . 1673 - 0194 . 2011 . 14. 042

［中圖分類號(hào)］G473.4；TP311.13 ［文獻(xiàn)標(biāo)識(shí)碼］A ［文章編號(hào)］1673 - 0194（2011）14- 0072- 02

１引言

目前，普通高校已廣泛采用計(jì)算機(jī)信息系統(tǒng)對(duì)學(xué)生選課活動(dòng)進(jìn)行管理，學(xué)生可根據(jù)自己專業(yè)特點(diǎn)、興趣愛(ài)好以及未來(lái)的職業(yè)規(guī)劃，在網(wǎng)上進(jìn)行選修課的選擇。在選課過(guò)程中，經(jīng)常出現(xiàn)選課傾向不均衡，也就是選擇一些課程的人數(shù)過(guò)多，而另一些課程無(wú)人選的現(xiàn)象。

選課系統(tǒng)在運(yùn)行中積累了大量的數(shù)據(jù)，這些數(shù)據(jù)中隱含著一些無(wú)法辨識(shí)的信息，利用數(shù)據(jù)挖掘技術(shù)，挖掘選課系統(tǒng)中積累的潛在的、有用的信息，可以指導(dǎo)教務(wù)部門(mén)調(diào)整熱門(mén)課程和冷門(mén)課程的數(shù)量和學(xué)分設(shè)置，從而提高教學(xué)管理水平，使教學(xué)資源得到合理分配，滿足學(xué)生的個(gè)性化選課需求。

２關(guān)聯(lián)規(guī)則及其算法分析

２．１數(shù)據(jù)挖掘定義

數(shù)據(jù)挖掘［１］是從數(shù)據(jù)中識(shí)別出有效的、新穎的、潛在有用的、以及最終可理解的模式的高級(jí)過(guò)程。簡(jiǎn)單地說(shuō)，數(shù)據(jù)挖掘是從大量數(shù)據(jù)中提取或“挖掘”知識(shí)。它是一個(gè)融合多種技術(shù)的交叉學(xué)科，包括數(shù)據(jù)庫(kù)技術(shù)、統(tǒng)計(jì)學(xué)、機(jī)器學(xué)習(xí)、可視化和信息科學(xué)以及其他相關(guān)學(xué)科。

２．２關(guān)聯(lián)規(guī)則算法分析

關(guān)聯(lián)規(guī)則（Ａｓｓｏｃｉａｔｉｏｎ Ｒｕｌｅ）挖掘就是從大量的數(shù)據(jù)集中去尋找數(shù)據(jù)之間的關(guān)聯(lián)關(guān)系，為決策系統(tǒng)服務(wù)。人們可以利用手中沒(méi)有規(guī)律的數(shù)據(jù)，找出物與物之間的規(guī)律，利用這些規(guī)律已給商業(yè)界帶來(lái)了驚人的利潤(rùn)。目前，關(guān)聯(lián)規(guī)則挖掘已經(jīng)成為數(shù)據(jù)挖掘領(lǐng)域中的重要研究方向。

關(guān)聯(lián)規(guī)則的挖掘算法主要有循環(huán)式掃描算法、增量式更新算法、并行挖掘算法、元模式制導(dǎo)、基于約束挖掘等。其中比較典型的有Ａｐｒｉｏｒｉ算法和ＦＰ－ｇｒｏｗｔｈ算法。楊克松［２］用Ａｐｒｉｏｒｉ算法對(duì)選課系統(tǒng)進(jìn)行數(shù)據(jù)挖掘，但由于Ａｐｒｉｏｒｉ算法在每次尋找頻繁項(xiàng)集的時(shí)候，都需要掃描數(shù)據(jù)庫(kù)一次，因此隨著數(shù)據(jù)庫(kù)的增大，尋找頻繁項(xiàng)集的時(shí)間會(huì)越長(zhǎng)，系統(tǒng)的效率受到很大的影響。針對(duì)Ａｐｒｉｏｒｉ算法框架的缺陷，Ｈａｎ．ＪＷ（韓家煒）［１］等人提出了ＦＰ－ｔｒｅｅ結(jié)構(gòu)和相應(yīng)的ＦＰ－ｇｒｏｗｔｈ算法。實(shí)驗(yàn)表明，ＦＰ－ｇｒｏｗｔｈ對(duì)不同長(zhǎng)度的規(guī)則都有很好的適應(yīng)性，同時(shí)在效率上較之Ａｐｒｉｏｒｉ算法有巨大的提高。由于高校多年來(lái)存儲(chǔ)的選課數(shù)據(jù)量較大，故選用ＦＰ－ｇｒｏｗｔｈ方法實(shí)現(xiàn)高校選課系統(tǒng)的關(guān)聯(lián)規(guī)則挖掘較合適。

３關(guān)聯(lián)規(guī)則挖掘在選課指導(dǎo)系統(tǒng)中的應(yīng)用

數(shù)據(jù)挖掘過(guò)程可以分為3個(gè)步驟：數(shù)據(jù)預(yù)處理、數(shù)據(jù)挖掘、挖掘結(jié)果的解釋與評(píng)估。

３．１數(shù)據(jù)預(yù)處理

數(shù)據(jù)預(yù)處理是要對(duì)數(shù)據(jù)進(jìn)行清洗、集成、轉(zhuǎn)換和消減。清除冗余數(shù)據(jù)，降噪，填充缺失的數(shù)據(jù)，消除重復(fù)記錄，從而提高數(shù)據(jù)挖掘?qū)ο蟮馁|(zhì)量，達(dá)到提高數(shù)據(jù)挖掘所獲知識(shí)質(zhì)量的目的。本文結(jié)合選課系統(tǒng)的應(yīng)用來(lái)研究數(shù)據(jù)預(yù)處理的4個(gè)步驟：

（１） 數(shù)據(jù)清洗。現(xiàn)實(shí)世界的數(shù)據(jù)常常是有噪聲、不完全的和不一致的。數(shù)據(jù)清洗過(guò)程一般包括平滑噪聲數(shù)據(jù)、補(bǔ)充缺失數(shù)據(jù)、消除異常數(shù)據(jù)，以及糾正不一致的數(shù)據(jù)。在系統(tǒng)中，對(duì)數(shù)據(jù)庫(kù)中空缺的數(shù)據(jù)項(xiàng)進(jìn)行關(guān)聯(lián)查找對(duì)照，用最“近似”的數(shù)據(jù)填充。對(duì)于冗余數(shù)據(jù)（如同時(shí)選取兩門(mén)同樣課程的學(xué)生數(shù)據(jù)）進(jìn)行刪除。

（２） 數(shù)據(jù)集成。將來(lái)自多個(gè)數(shù)據(jù)源（數(shù)據(jù)庫(kù)、數(shù)據(jù)立方、普通文件等）的數(shù)據(jù)結(jié)合在一起并形成一個(gè)統(tǒng)一數(shù)據(jù)集合，以便為數(shù)據(jù)挖掘工作的順利完成提供完整的數(shù)據(jù)基礎(chǔ)［１］。在選課系統(tǒng)的存儲(chǔ)設(shè)計(jì)中，要為將來(lái)的數(shù)據(jù)挖掘做準(zhǔn)備，同時(shí)考慮不同專業(yè)的偏好程度、課程的冷熱程度、學(xué)生對(duì)教師的要求等因素，將數(shù)據(jù)存儲(chǔ)在ＳＱＬ Ｓｅｒｖｅｒ ２０００中。

（３） 數(shù)據(jù)轉(zhuǎn)換。將數(shù)據(jù)按劃分的主題進(jìn)行轉(zhuǎn)換，同時(shí)使數(shù)據(jù)離散化。例如：將“網(wǎng)絡(luò)20０９－０１”分解成“網(wǎng)絡(luò)”專業(yè)、“20０９”級(jí)、“０１”班，為數(shù)據(jù)挖掘做準(zhǔn)備。

（４） 數(shù)據(jù)消減。數(shù)據(jù)消減是使原來(lái)龐大復(fù)雜的數(shù)據(jù)精簡(jiǎn)化，去除挖掘工作不需要的屬性，同時(shí)保證數(shù)據(jù)的完整性。例如：去除課程信息中的學(xué)期、課程序號(hào)等；去除教師信息中的年齡、性別等；學(xué)生信息中只保留學(xué)號(hào)、姓名、專業(yè)、院系、年級(jí)，其他信息去除；成績(jī)信息中只保留課程編號(hào)、學(xué)號(hào)、成績(jī)。

３．２數(shù)據(jù)挖掘

本文選擇關(guān)聯(lián)規(guī)則挖掘方法來(lái)研究課程、學(xué)生、教師之間的相關(guān)聯(lián)系，在關(guān)聯(lián)規(guī)則挖掘的各種算法中，經(jīng)過(guò)前文比較，我們選用效率較高的ＦＰ－ｔｒｅｅ增量模式算法，具體算法如下。

表１中數(shù)據(jù)是部分選課情況，以該數(shù)據(jù)為例，可以挖掘出若干關(guān)聯(lián)規(guī)則。下面僅從技術(shù)角度討論3條選擇關(guān)聯(lián)規(guī)則的標(biāo)準(zhǔn)：支持度（也稱廣泛度，普遍度）、置信度（也稱預(yù)測(cè)度）、增益。

３．２．１支持度ｓｕｐ（）

表示在選課系統(tǒng)中同時(shí)包含關(guān)聯(lián)規(guī)則左右兩邊教師職稱和課程科目的選擇次數(shù)百分比。即支持這個(gè)選擇的次數(shù)百分比，相當(dāng)于聯(lián)合概率。

ｓｕｐ（Ｘ２２ → Ｙ１１） ＝ Ｐ（Ｘ２２Ｙ１１） ＝ ４００／１ ０００ ＝ ４０％

３．２．２置信度ｃｏｎ（）

是指在所有的選擇了左邊的教師，同時(shí)又選擇了右邊的課程的選擇概率，是一個(gè)條件概率。

ｃｏｎ（Ｘ２２ → Ｙ１１） ＝ Ｐ（Ｙ１１ ｜Ｘ２２） ＝ Ｐ（Ｘ２２Ｙ１１）／Ｐ（Ｘ２２） ＝ ４００／５４０ ＝ ７４．１％

３．２．３增益ｌｉｆ（）

增益是兩種可能性的比較。一種是在已知選擇了左邊教師的情況下選擇右邊課程的可能性，另一種是在任意情況下選擇右邊課程的可能性。

ｌｉｆ（Ｘ２２ → Ｙ１１） ＝ Ｐ（Ｙ１１ ｜ Ｘ２２） － Ｐ（Ｙ１１） ＝ ７４．１％ － ５０％ ＝ ２４．１％

這個(gè)標(biāo)準(zhǔn)和數(shù)據(jù)挖掘中其他模型的選擇標(biāo)準(zhǔn)一樣，通過(guò)與“原有”規(guī)則的比較，來(lái)測(cè)量該規(guī)則提高預(yù)測(cè)準(zhǔn)確性的程度。指定標(biāo)準(zhǔn)的最小值：ｍｉｎ＿ｓｕｐ ＝ １０％，ｍｉｎ＿ｃｏｎ ＝ ４０％，ｍｉｎ＿ｌｉｆ ＝ １０％。取值都大于標(biāo)準(zhǔn)臨界值的關(guān)聯(lián)規(guī)則被列出。

３．３對(duì)結(jié)果的評(píng)估

從表２中挖掘的有效規(guī)則可以看出，Ｒ１規(guī)則說(shuō)明20０９級(jí)學(xué)生偏愛(ài)文史類課程，并且多數(shù)學(xué)生選擇職稱為副教授的教師；Ｒ２規(guī)則說(shuō)明20１０級(jí)學(xué)生對(duì)經(jīng)濟(jì)類課程感興趣，并且對(duì)教授職稱的老師非常認(rèn)可；Ｒ３規(guī)則說(shuō)明各年級(jí)學(xué)生都對(duì)藝體類課程有興趣，而且對(duì)老師的職稱沒(méi)有要求；Ｒ４規(guī)則說(shuō)明學(xué)生對(duì)學(xué)分比較高的課程有興趣，等等。根據(jù)表2中的結(jié)果，可以建議下學(xué)期廣泛開(kāi)展藝體類選修課，鍛煉體魄陶冶情操，向20０９級(jí)學(xué)生增開(kāi)文史類課程，向20１０級(jí)學(xué)生增開(kāi)經(jīng)濟(jì)類課程，等等。

４結(jié)論

數(shù)據(jù)挖掘技術(shù)已經(jīng)成功地應(yīng)用于銀行、大型超市等營(yíng)利性領(lǐng)域中，在高校、政府等非營(yíng)利性機(jī)構(gòu)中應(yīng)用很少。本文采用ＦＰ－ｇｒｏｗｔｈ算法對(duì)高校學(xué)生選課信息進(jìn)行數(shù)據(jù)挖掘，輔助教務(wù)處完成下學(xué)期選修課程和教師資源的合理安排，提高教學(xué)管理效率。此問(wèn)題還需進(jìn)一步深入研究，從多層次和多維度對(duì)系統(tǒng)中的數(shù)據(jù)進(jìn)行挖掘。

主要參考文獻(xiàn)

［１］ ［加］Ｊｉａｗｅｉ Ｈａｎ，Ｍｉｃｈｅｌｉｎｅ Ｋａｍｂｅｒ． 數(shù)據(jù)挖掘概念與技術(shù)［Ｍ］． 范明，孟小峰，譯． 北京：機(jī)械工業(yè)出版社，２００１．

［２］ 楊克松． 論關(guān)聯(lián)規(guī)則在高校選課系統(tǒng)中的應(yīng)用［Ｊ］． 福建電腦，２００７（１０）．

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