數據挖掘在計算機等級考試中的應用

摘要:文章闡述如何采用ID3算法對學生計算機等級考試數據進行分類，并對分類結果進行分析，從而得出通過計算機等級考試的規則。以期待學生在學習過程中，借鑒這些規則，有規律、有目的地進行學習，從而提高等級考試合格率，實現優化教學。

關鍵詞:數據挖掘;ID3;分類

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

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

1數據挖掘概念

數據挖掘(Data Ming)是從大量的、不完全的、有噪聲的、模糊的、隨機的數據中，提取隱含在其中的、人們事先不知道的、但又是潛在有用的信息和知識的過程。其一般步驟分為:確定挖掘對象、數據準備、數據挖掘、結果分析和知識的同化[2]。

(1) 確定挖掘對象:通過理解數據和實際的問題，確定挖掘對象。

(2) 數據準備:數據準備是保證數據挖掘得以成功的先決條件，包括數據選擇、數據預處理和數據轉換。數據選擇就是搜索所有與挖掘對象有關的數據信息，獲取原始的數據;數據預處理就是對數據進行初步的整理，清洗不完全的數據;數據轉換是根據數據挖掘的目標和數據的特征，選擇合適的模型。

(3) 數據挖掘:數據挖掘就是對所得到的經過轉換的數據進行挖掘，除了選擇合適的挖掘算法外，其余工作應該能自動地完成。

(4) 結果分析:對挖掘結果進行解釋并評估。

(5) 知識的同化:知識的同化就是將分析所得到的知識集成到挖掘對象的組織結構中去。

數據挖掘通過預測未來趨勢及行為，作出前瞻的、基于知識的決策，其功能用于指定數據挖掘任務中要找的模式類型，它的技術主要有聚類分析、決策樹、神經網絡和粗糙集等。聚類分析就是將待分析數據根據一定的分類規則，合理地劃分數據集合，確定每個數據所在類別。神經網絡是仿照生理神經網絡結構的非線形預測模型，通過學習進行模式識別。決策樹主要應用于分類和預測，從數據中生成分類器的一個特別有效的方法生成一棵決策樹。粗糙集理論主要用于發現不準確數據或噪聲數據內在的結構聯系，其優點是無須提供除問題所需處理的數據集合之外的任何先驗信息并能夠有效地去除冗余。

作者簡介:孔麗英(1964-)，女，廣東封開人，高級實驗師，碩士，研究方向為數據挖掘和粗糙集。

2ID3算法

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

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

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

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

由期望信息和熵值可以得到對應的信息增益值。對于在 上分支將獲得的信息增益可以由此式得到

3實例分析

學校每年都要參加省計算機等級考試，積累了大量的數據。經多次的等級考試發現，有相當一部分學生未能在一次考試中通過，作為教師應當找出教學中存在的問題以及沒有通過等級考試的學生存在的問題，因此，對學生C++語言等級考試的情況進行分析是有必要的。以C++語言等級考試的情況作為挖掘對象，利用決策樹ID3算法運用于等級考試數據中，就會挖掘出一些有用的數據，探討等級考試成績與學生學習過程之間有無必然的聯系? 使學生能夠較好的保持良好的學習態度，從而為教學提供決策支持信息，使老師能更好地開展教學工作，同時使學生能夠有規律、有目的地進行學習，提高等級考試合格率，實現優化教學。

3.1數據準備

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

表1數據集

B對象Ucfghijlmq

1312233331

2322233232

3332222332

4311233332

5313123222

6313332132

7312122212

8311232232

9323233232

10312233331

……

89322323222

3.2數據挖掘

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

ID3算法:Generate_decision_tree由給定的訓練數據產生一棵決策樹[3]

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

輸出:一棵決策樹。

方法:

(1) 創建節點N;

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

(3) 返回N作為葉節點，以類C標記;

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

(5) 返回N作為葉節點，標記為samples中最普通的類;//多數表決

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

(7) 標記節點N為test_attribute;

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

(9) 由節點N長出一個條件為的test_attribute=ai分枝;

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

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

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

(13) 在樣本集samples中去掉屬性test_attribute =ai后，得到的樣本集繼續調用該算法，直到決策樹不再伸長。

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

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

圖1決策樹

3.3結果分析

由等級考試決策樹圖的根結點到葉子結點的每一條路徑都可以是一條規則，即提取分類規則:

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

(2) 如果認真聽課而且課后有復習，則等級考試成績是合格的。

(3) 如果認真聽課，課后不復習，但課前經常預習，則等級考試成績是合格的。

(4) 如果認真聽課，課后不復習，課前又不預習，但實驗興趣大，則等級考試成績是合格的。

(5) 如果認真聽課，課后不復習，課前又不預習，而且實驗興趣不大或沒有興趣，則等級考試成績是不合格的。

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

強對課本知識的理解，教師也要用有代表性的例子作為教學，以提高學生學習興趣和聽課的效果，可以這樣設想，一名學生如果能夠合理地安排學習和實驗，是可以順利一次性地通過等級考試的。

4結語

應用數據挖掘技術對大量數據進行抽取、轉換和分析，能從中提取輔助決策的關鍵性數據，幫助決策者尋找規律和預測未來。對C++語言等級考試數據進行預處理，應用粗糙集理論對屬性進行屬性約簡，去掉了一些無關聯的屬性，節約了空間，運用決策樹技術確定一棵決策樹，并得到一些規則，利用這些規則指導教學，可大大提高學生等級考試通過率，實現優化教學。

參考文獻:

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

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

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

[4] 毛國君，段立娟，王實，等. 數據挖掘原理與算法[M]. 北京:清華大學出版社，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

(編輯:彭遠紅)