數(shù)據(jù)挖掘在計(jì)算機(jī)等級(jí)考試中的應(yīng)用

摘要:文章闡述如何采用ID3算法對(duì)學(xué)生計(jì)算機(jī)等級(jí)考試數(shù)據(jù)進(jìn)行分類，并對(duì)分類結(jié)果進(jìn)行分析，從而得出通過計(jì)算機(jī)等級(jí)考試的規(guī)則。以期待學(xué)生在學(xué)習(xí)過程中，借鑒這些規(guī)則，有規(guī)律、有目的地進(jìn)行學(xué)習(xí)，從而提高等級(jí)考試合格率，實(shí)現(xiàn)優(yōu)化教學(xué)。

關(guān)鍵詞:數(shù)據(jù)挖掘;ID3;分類

目前，從大量數(shù)據(jù)中搜尋有價(jià)值的信息并利用這些信息去預(yù)測未知的或未來值的過程變得愈加重要，數(shù)據(jù)挖掘就能完成這樣的過程。隨著教育信息化進(jìn)程的推進(jìn)，將數(shù)據(jù)挖掘技術(shù)應(yīng)用于教育中，從大量的教育數(shù)據(jù)中發(fā)現(xiàn)隱藏的、有用的知識(shí)來指導(dǎo)教育、發(fā)展教育，成為當(dāng)今勢在必行的重要的研究課題[1]。

本學(xué)校的計(jì)算機(jī)等級(jí)考試是廣東省教育廳推出的一種高校考試，具有權(quán)威性、科學(xué)性和公平性，是大部分高校的學(xué)生都要參與的考試，如何在有效的教學(xué)時(shí)間通過等級(jí)考試是值得教師要思考的問題。目前，對(duì)等級(jí)考試相關(guān)數(shù)據(jù)的分析和利用還多停留在初級(jí)查詢、簡單統(tǒng)計(jì)階段，停留在傳統(tǒng)教學(xué)的認(rèn)識(shí)上，缺乏科學(xué)依據(jù)，而且對(duì)這些數(shù)據(jù)未能挖掘潛在的規(guī)則。“C++語言”課程不但教學(xué)時(shí)間短，而且內(nèi)容多，如何讓學(xué)生通過C++等級(jí)考試將面臨著嚴(yán)峻考驗(yàn)，因此，通過數(shù)據(jù)挖掘技術(shù)，從往年等級(jí)考試的數(shù)據(jù)中挖掘出對(duì)學(xué)生通過等級(jí)考試最有影響的因素以及潛在的分類規(guī)則，來制定相應(yīng)措施并指導(dǎo)教學(xué)，提高學(xué)生等級(jí)考試通過率。

1數(shù)據(jù)挖掘概念

數(shù)據(jù)挖掘(Data Ming)是從大量的、不完全的、有噪聲的、模糊的、隨機(jī)的數(shù)據(jù)中，提取隱含在其中的、人們事先不知道的、但又是潛在有用的信息和知識(shí)的過程。其一般步驟分為:確定挖掘?qū)ο蟆?shù)據(jù)準(zhǔn)備、數(shù)據(jù)挖掘、結(jié)果分析和知識(shí)的同化[2]。

(1) 確定挖掘?qū)ο?通過理解數(shù)據(jù)和實(shí)際的問題，確定挖掘?qū)ο蟆?/p>

(2) 數(shù)據(jù)準(zhǔn)備:數(shù)據(jù)準(zhǔn)備是保證數(shù)據(jù)挖掘得以成功的先決條件，包括數(shù)據(jù)選擇、數(shù)據(jù)預(yù)處理和數(shù)據(jù)轉(zhuǎn)換。數(shù)據(jù)選擇就是搜索所有與挖掘?qū)ο笥嘘P(guān)的數(shù)據(jù)信息，獲取原始的數(shù)據(jù);數(shù)據(jù)預(yù)處理就是對(duì)數(shù)據(jù)進(jìn)行初步的整理，清洗不完全的數(shù)據(jù);數(shù)據(jù)轉(zhuǎn)換是根據(jù)數(shù)據(jù)挖掘的目標(biāo)和數(shù)據(jù)的特征，選擇合適的模型。

(3) 數(shù)據(jù)挖掘:數(shù)據(jù)挖掘就是對(duì)所得到的經(jīng)過轉(zhuǎn)換的數(shù)據(jù)進(jìn)行挖掘，除了選擇合適的挖掘算法外，其余工作應(yīng)該能自動(dòng)地完成。

(4) 結(jié)果分析:對(duì)挖掘結(jié)果進(jìn)行解釋并評(píng)估。

(5) 知識(shí)的同化:知識(shí)的同化就是將分析所得到的知識(shí)集成到挖掘?qū)ο蟮慕M織結(jié)構(gòu)中去。

數(shù)據(jù)挖掘通過預(yù)測未來趨勢及行為，作出前瞻的、基于知識(shí)的決策，其功能用于指定數(shù)據(jù)挖掘任務(wù)中要找的模式類型，它的技術(shù)主要有聚類分析、決策樹、神經(jīng)網(wǎng)絡(luò)和粗糙集等。聚類分析就是將待分析數(shù)據(jù)根據(jù)一定的分類規(guī)則，合理地劃分?jǐn)?shù)據(jù)集合，確定每個(gè)數(shù)據(jù)所在類別。神經(jīng)網(wǎng)絡(luò)是仿照生理神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)的非線形預(yù)測模型，通過學(xué)習(xí)進(jìn)行模式識(shí)別。決策樹主要應(yīng)用于分類和預(yù)測，從數(shù)據(jù)中生成分類器的一個(gè)特別有效的方法生成一棵決策樹。粗糙集理論主要用于發(fā)現(xiàn)不準(zhǔn)確數(shù)據(jù)或噪聲數(shù)據(jù)內(nèi)在的結(jié)構(gòu)聯(lián)系，其優(yōu)點(diǎn)是無須提供除問題所需處理的數(shù)據(jù)集合之外的任何先驗(yàn)信息并能夠有效地去除冗余。

作者簡介:孔麗英(1964-)，女，廣東封開人，高級(jí)實(shí)驗(yàn)師，碩士，研究方向?yàn)閿?shù)據(jù)挖掘和粗糙集。

2ID3算法

決策樹采用的是自頂向下的遞歸方法，它的每一層結(jié)點(diǎn)依照某一屬性值向下分為子結(jié)點(diǎn)，待分類的實(shí)例在每一結(jié)點(diǎn)處與該結(jié)點(diǎn)相關(guān)的屬性值進(jìn)行比較，根據(jù)不同的比較結(jié)果向相應(yīng)的子結(jié)點(diǎn)擴(kuò)展，這一過程在到達(dá)決策樹葉點(diǎn)時(shí)結(jié)束，此時(shí)得到結(jié)論。因此，從根結(jié)點(diǎn)到葉結(jié)點(diǎn)的每一條路徑都對(duì)應(yīng)著一條合理的規(guī)則。決策樹法又分為 ID3 算法、CLS 算法、IBLE 算法等。ID3算法在數(shù)據(jù)挖掘中占有非常重要的地位，它是從CLS算法發(fā)展而來的，它是由Quinlan提出的一個(gè)著名決策樹生成方法，它的基本思路是:計(jì)算所有屬性的信息增益，選擇信息增益最大的屬性產(chǎn)生決策樹根結(jié)點(diǎn)，由該屬性的不同取值建立分支，再對(duì)各分支的子集遞歸調(diào)用建立決策樹結(jié)點(diǎn)的分支，直到所有子集合僅包含同一類或者數(shù)據(jù)不可再分割為止。

設(shè)S是s個(gè)數(shù)據(jù)樣本的集合，假定類標(biāo)號(hào)屬性具有m個(gè)不同值，定義m個(gè)不同類Ci(i=1，2，…，m)。設(shè)si是類Ci中的樣本數(shù)。對(duì)一個(gè)給定的樣本分類所需的期望信息由此式給出

其中 是任意樣本屬于Ci的概率，一般可 來估計(jì)，對(duì)數(shù)函數(shù)以2為底。

設(shè)屬性 具有 個(gè)不同值 。可以用屬性 將 劃分為 個(gè)子集 ，其中 包含 中這樣一些樣本，它們?cè)贏上具有值 。設(shè) 是子集 中類 的樣本數(shù)。根據(jù)A劃分成子集的熵由下式給出

由期望信息和熵值可以得到對(duì)應(yīng)的信息增益值。對(duì)于在 上分支將獲得的信息增益可以由此式得到

3實(shí)例分析

學(xué)校每年都要參加省計(jì)算機(jī)等級(jí)考試，積累了大量的數(shù)據(jù)。經(jīng)多次的等級(jí)考試發(fā)現(xiàn)，有相當(dāng)一部分學(xué)生未能在一次考試中通過，作為教師應(yīng)當(dāng)找出教學(xué)中存在的問題以及沒有通過等級(jí)考試的學(xué)生存在的問題，因此，對(duì)學(xué)生C++語言等級(jí)考試的情況進(jìn)行分析是有必要的。以C++語言等級(jí)考試的情況作為挖掘?qū)ο螅脹Q策樹ID3算法運(yùn)用于等級(jí)考試數(shù)據(jù)中，就會(huì)挖掘出一些有用的數(shù)據(jù)，探討等級(jí)考試成績與學(xué)生學(xué)習(xí)過程之間有無必然的聯(lián)系? 使學(xué)生能夠較好的保持良好的學(xué)習(xí)態(tài)度，從而為教學(xué)提供決策支持信息，使老師能更好地開展教學(xué)工作，同時(shí)使學(xué)生能夠有規(guī)律、有目的地進(jìn)行學(xué)習(xí)，提高等級(jí)考試合格率，實(shí)現(xiàn)優(yōu)化教學(xué)。

3.1數(shù)據(jù)準(zhǔn)備

通過多年的教學(xué)經(jīng)驗(yàn)，制定與計(jì)算機(jī)等級(jí)考試成績相關(guān)的數(shù)據(jù)調(diào)查表，并對(duì)2005級(jí)信息與計(jì)算科學(xué)班級(jí)的C++語言等級(jí)考試情況作調(diào)查，共收取有效調(diào)查表89份，根據(jù)粗糙集理論對(duì)數(shù)據(jù)進(jìn)行預(yù)處理后，教學(xué)中最能體現(xiàn)與等級(jí)考試相關(guān)的屬性有:聽課(c)，預(yù)習(xí)(f)，復(fù)習(xí)(g)，上課做筆記(h)，理論興趣(i)，實(shí)驗(yàn)興趣(j)， 課后練習(xí)(l)，自學(xué)能力(m)，等級(jí)考試成績(q)，其中等級(jí)考試成績是決策屬性b，其余作為條件屬性。數(shù)據(jù)集見表1。

表1數(shù)據(jù)集

B對(duì)象Ucfghijlmq

1312233331

2322233232

3332222332

4311233332

5313123222

6313332132

7312122212

8311232232

9323233232

10312233331

……

89322323222

3.2數(shù)據(jù)挖掘

分類是數(shù)據(jù)挖掘的任務(wù)之一，分類主要用于提取描述重要數(shù)據(jù)類型的模型，決策樹是數(shù)據(jù)挖掘中非常有效的分類方法，ID3算法是建立決策樹的有效算法。

ID3算法:Generate_decision_tree由給定的訓(xùn)練數(shù)據(jù)產(chǎn)生一棵決策樹[3]

輸入:訓(xùn)練樣本samples，由離散值屬性表示;候選屬性的集合attribute_list。

輸出:一棵決策樹。

方法:

(1) 創(chuàng)建節(jié)點(diǎn)N;

(2)if samples 都在同一個(gè)類C then goto (3); else goto (4);

(3) 返回N作為葉節(jié)點(diǎn)，以類C標(biāo)記;

(4)if samples為空 then goto (5); else goto (6);

(5) 返回N作為葉節(jié)點(diǎn)，標(biāo)記為samples中最普通的類;//多數(shù)表決

(6) 選擇attribute_list中具有最高信息增益的屬性test_attribute;

(7) 標(biāo)記節(jié)點(diǎn)N為test_attribute;

(8)for each test_attribute中的已知值ai //劃分samples

(9) 由節(jié)點(diǎn)N長出一個(gè)條件為的test_attribute=ai分枝;

(10) 設(shè)si是samples中的test_attribute=ai樣本的集合;//一個(gè)劃分

(11)if si為空then goto (12);else goto(13);

(12) 加上一個(gè)樹葉，標(biāo)記為samples中最普通的類;

(13) 在樣本集samples中去掉屬性test_attribute =ai后，得到的樣本集繼續(xù)調(diào)用該算法，直到?jīng)Q策樹不再伸長。

在構(gòu)造決策樹時(shí)，許多分枝可能反映的是訓(xùn)練集數(shù)據(jù)中的噪聲或孤立點(diǎn)，在有噪聲情況下，完全擬合將導(dǎo)致過分?jǐn)M合，即對(duì)訓(xùn)練數(shù)據(jù)的完全擬合反而使對(duì)現(xiàn)實(shí)數(shù)據(jù)的分類預(yù)測性能下降。剪枝是一種克服噪聲的基本技術(shù)，同時(shí)它也能使樹得到簡化而變得更容易理解。也就是說，對(duì)決策樹進(jìn)行剪枝就是要提高在未知數(shù)據(jù)上分類的準(zhǔn)確性，剪枝有預(yù)先剪枝和后剪枝。預(yù)先剪枝是在生成樹的同時(shí)決定是繼續(xù)對(duì)不純的訓(xùn)練子集進(jìn)行劃分還是停機(jī);后剪枝是先生成與訓(xùn)練數(shù)據(jù)完全擬合的一棵決策樹，然后從樹的葉子開始剪枝，逐步向根的方向剪。剪枝時(shí)要用到一個(gè)測試數(shù)據(jù)集合，如果存在某個(gè)葉子剪去后使得在測試集上的準(zhǔn)確度或其他測度不降低，則剪去該葉子;否則停機(jī)[4]。因此，在建立判定樹時(shí)要根據(jù)實(shí)際數(shù)據(jù)給出控制過分?jǐn)M合的條件，如當(dāng)類別的分類個(gè)數(shù)達(dá)到閾值時(shí)，判定樹不再分枝，避免分類預(yù)測性能下降。

在本實(shí)例中，根據(jù)ID3算法，計(jì)算表1各屬性的信息增益，得“聽課”具有最大的信息增益，因此選“聽課”屬性為根節(jié)點(diǎn)，表1分為“聽課”=1時(shí)的子集F1，“聽課”=2時(shí)的子集F2，“聽課”=3時(shí)的子集F3;為了避免訓(xùn)練集數(shù)據(jù)在建立決策樹時(shí)產(chǎn)生噪聲或孤立點(diǎn)或過分?jǐn)M合，在建立樹的過程中要進(jìn)行修剪，由于F1中有9/12=75%的學(xué)生等級(jí)考試成績?yōu)?，故“聽課”=1時(shí)可以分別出類別為1的一類，對(duì)于F2中有10/13=76.9%的學(xué)生等級(jí)考試成績?yōu)?，故“聽課”=2時(shí)可分別出類別為1的一類;對(duì)于子集F3，繼續(xù)計(jì)算各屬性的信息增益，得“復(fù)習(xí)” 具有最大的信息增益，子集F3劃分為“復(fù)習(xí)”=1時(shí)的子集F31，“復(fù)習(xí)”=2時(shí)的子集F32，“復(fù)習(xí)”=3時(shí)的子集F33，子集F33中全部記錄的類別是2，故“復(fù)習(xí)”=3時(shí)可以標(biāo)識(shí)類別為2的一類;類似方法，得到表1的一棵決策樹，見圖1。

圖1決策樹

3.3結(jié)果分析

由等級(jí)考試決策樹圖的根結(jié)點(diǎn)到葉子結(jié)點(diǎn)的每一條路徑都可以是一條規(guī)則，即提取分類規(guī)則:

(1) 如果不聽課或不認(rèn)真聽課，則等級(jí)考試成績是不合格的。

(2) 如果認(rèn)真聽課而且課后有復(fù)習(xí)，則等級(jí)考試成績是合格的。

(3) 如果認(rèn)真聽課，課后不復(fù)習(xí)，但課前經(jīng)常預(yù)習(xí)，則等級(jí)考試成績是合格的。

(4) 如果認(rèn)真聽課，課后不復(fù)習(xí)，課前又不預(yù)習(xí)，但實(shí)驗(yàn)興趣大，則等級(jí)考試成績是合格的。

(5) 如果認(rèn)真聽課，課后不復(fù)習(xí)，課前又不預(yù)習(xí)，而且實(shí)驗(yàn)興趣不大或沒有興趣，則等級(jí)考試成績是不合格的。

二級(jí)考試的考試方式是機(jī)試，考試過程中會(huì)出現(xiàn)各類情況，采集的數(shù)據(jù)集難以反映學(xué)生的真實(shí)情況，因此決策樹會(huì)出現(xiàn)不確定因素或噪聲和孤立點(diǎn)，而造成有錯(cuò)誤率存在。本例用89個(gè)學(xué)生的數(shù)據(jù)集對(duì)分類規(guī)則進(jìn)行測試，其準(zhǔn)確率為80.9%，這表明用數(shù)據(jù)挖掘技術(shù)對(duì)等級(jí)考試進(jìn)行評(píng)估的方法是可行的，用所得到的知識(shí)規(guī)則對(duì)未知樣本進(jìn)行預(yù)測是可靠的，而且這些規(guī)則都反映一般學(xué)習(xí)的規(guī)則。那就是要求學(xué)生不但要認(rèn)真聽課，而且要加強(qiáng)課后復(fù)習(xí)或課前預(yù)習(xí)，還要通過實(shí)驗(yàn)提高計(jì)算機(jī)操作能力和設(shè)計(jì)程序能力，以加

強(qiáng)對(duì)課本知識(shí)的理解，教師也要用有代表性的例子作為教學(xué)，以提高學(xué)生學(xué)習(xí)興趣和聽課的效果，可以這樣設(shè)想，一名學(xué)生如果能夠合理地安排學(xué)習(xí)和實(shí)驗(yàn)，是可以順利一次性地通過等級(jí)考試的。

4結(jié)語

應(yīng)用數(shù)據(jù)挖掘技術(shù)對(duì)大量數(shù)據(jù)進(jìn)行抽取、轉(zhuǎn)換和分析，能從中提取輔助決策的關(guān)鍵性數(shù)據(jù)，幫助決策者尋找規(guī)律和預(yù)測未來。對(duì)C++語言等級(jí)考試數(shù)據(jù)進(jìn)行預(yù)處理，應(yīng)用粗糙集理論對(duì)屬性進(jìn)行屬性約簡，去掉了一些無關(guān)聯(lián)的屬性，節(jié)約了空間，運(yùn)用決策樹技術(shù)確定一棵決策樹，并得到一些規(guī)則，利用這些規(guī)則指導(dǎo)教學(xué)，可大大提高學(xué)生等級(jí)考試通過率，實(shí)現(xiàn)優(yōu)化教學(xué)。

參考文獻(xiàn):

[1] 楊永斌. 數(shù)據(jù)挖掘技術(shù)在教育中的應(yīng)用研究[J]. 計(jì)算機(jī)科學(xué)，2006(12):284-286.

[2] 安淑芝. 數(shù)據(jù)倉庫與數(shù)據(jù)挖掘[M]. 北京:清華大學(xué)出版社，2005:1-11.

[3]Jiawei Han，Micheline Kamber. 數(shù)據(jù)挖掘概念與技術(shù)[M]. 范明，孟小峰，譯. 北京:機(jī)械工業(yè)出版社，2005:188-196.

[4] 毛國君，段立娟，王實(shí)，等. 數(shù)據(jù)挖掘原理與算法[M]. 北京:清華大學(xué)出版社，2007:26-128.

Application of Data Mining to Computer Grade Test

KONG Li-ying

(College of Mathematics and Information Sciences， Zhaoqing University， Zhaoqing 526061， China)

Abstract: How to class data of computer grade test of students by the ID3 algorithm is elaborated， and results of the classification are analyzed in the article， thus rules of passing computer grade test are obtained. In order to raise percent of pass of the grade test， students must have the destination to study from these rules， then optimization teaching is realized.

Key words: Data Mining; ID3; classification

(編輯:彭遠(yuǎn)紅)