陰愛英，楊曉花

（福州大學(xué)至誠學(xué)院 計(jì)算機(jī)工程系，福建 福州 350002）

基于決策樹的學(xué)生成績分類研究

陰愛英，楊曉花

（福州大學(xué)至誠學(xué)院 計(jì)算機(jī)工程系，福建 福州 350002）

本文根據(jù)決策樹分類技術(shù)對(duì)福建省計(jì)算機(jī)等級(jí)考試中的成績進(jìn)行分析和挖掘.首先對(duì)成績數(shù)據(jù)進(jìn)行離散化處理，設(shè)置成決策樹分類的屬性數(shù)據(jù)；接著利用ID3改進(jìn)算法構(gòu)建成績分類的決策樹模型，并對(duì)其剪枝；最后根據(jù)模型給出相應(yīng)的規(guī)則和幾個(gè)教學(xué)建議.實(shí)驗(yàn)結(jié)果表明，利用決策樹分類技術(shù)在計(jì)算機(jī)等級(jí)考試中進(jìn)行挖掘分析的方法是有效可行的.

數(shù)據(jù)挖掘；決策樹；信息增益；計(jì)算機(jī)等級(jí)考試

1 引言

隨著數(shù)據(jù)挖掘技術(shù)的發(fā)展，各行各業(yè)均利用數(shù)據(jù)挖掘技術(shù)來為其提供決策支持.數(shù)據(jù)挖掘技術(shù)是從大量的數(shù)據(jù)中，挖掘出人們開始并不知道的但又隱含在數(shù)據(jù)庫中的并且有用的信息[1].隨著高等教育行業(yè)的信息化技術(shù)的發(fā)展，越來越多的管理者或老師更加關(guān)注學(xué)生的學(xué)習(xí)情況，通過對(duì)歷年來的教學(xué)數(shù)據(jù)進(jìn)行分析，挖掘出影響學(xué)生學(xué)習(xí)成績的一些關(guān)鍵信息，以此提高教學(xué)質(zhì)量.

近年來，國內(nèi)外學(xué)者對(duì)數(shù)據(jù)挖掘的應(yīng)用進(jìn)行了深入研究，如：Abeer等[2]根據(jù)現(xiàn)有的教學(xué)數(shù)據(jù)庫，利用決策樹分類技術(shù)預(yù)測學(xué)生的最終成績；Rupp等[3]通過EDM(Education Data Mining)和學(xué)習(xí)分析技術(shù)對(duì)學(xué)生學(xué)習(xí)能力進(jìn)行挖掘；Alejandro[4]通過對(duì)EDM平臺(tái)進(jìn)行維護(hù)和擴(kuò)展，并對(duì)該平臺(tái)利用數(shù)據(jù)挖掘的方法進(jìn)行分析和討論；Abdullah等[5]利用關(guān)聯(lián)規(guī)則對(duì)電子管理系統(tǒng)進(jìn)行挖掘，為教育管理機(jī)構(gòu)提供決策支持；姜永超通過關(guān)聯(lián)規(guī)則和序列模式進(jìn)行挖掘，分別對(duì)學(xué)生選課和學(xué)習(xí)興趣的行為進(jìn)行分析研究[6]；顧輝等[7]利用對(duì)關(guān)聯(lián)規(guī)則Apriori算法的改進(jìn)，并應(yīng)用于《計(jì)算機(jī)基礎(chǔ)》課程的學(xué)生成績進(jìn)行研究與分析；王華等[8]根據(jù)關(guān)聯(lián)規(guī)則技術(shù)對(duì)學(xué)生成績進(jìn)行挖掘，并對(duì)學(xué)生的成績進(jìn)行預(yù)警，及時(shí)找出可能出現(xiàn)不及格的課程，對(duì)部分學(xué)生給出警告.

本文通過在前期工作研究的基礎(chǔ)上[9]，利用決策樹分類挖掘技術(shù)，對(duì)福建省計(jì)算機(jī)等級(jí)考試二級(jí)（C語言）進(jìn)行挖掘，用決策樹分類技術(shù)構(gòu)建學(xué)生成績是否合格與哪些題型得分情況有關(guān)的決策樹分類模型，為老師更好地教授好這門課程提供一些有用信息，也為學(xué)生能更好地通過等級(jí)考試提供了參考資料.

2 相關(guān)知識(shí)

決策樹（Decision Tree）又稱判定樹[10]，是采用樹型結(jié)構(gòu)對(duì)數(shù)據(jù)進(jìn)行分類的.它是從一堆沒有任何規(guī)則且是無序的數(shù)據(jù)中，根據(jù)分類規(guī)則，利用樹的形狀來表示這些數(shù)據(jù)的分類情況.在構(gòu)造的決策樹中，樹的最頂層是根結(jié)點(diǎn)，它是表示第一次選擇分裂的屬性，而樹的其它內(nèi)部結(jié)點(diǎn)（不是葉子結(jié)點(diǎn)）表示對(duì)其它屬性數(shù)據(jù)的測試，葉子結(jié)點(diǎn)表示數(shù)據(jù)屬性的分類情況，而對(duì)于一個(gè)決策樹的分支來說，其代表著某個(gè)測試數(shù)據(jù)屬性的分類情況輸出.

一般來說，利用決策樹進(jìn)行分類挖掘時(shí)，需要經(jīng)歷下面的過程：第一步是構(gòu)建決策樹模型，即利用先知類型的樣本數(shù)據(jù)對(duì)其實(shí)行分類，構(gòu)造一個(gè)決策樹模型.在這個(gè)步驟中要經(jīng)歷兩個(gè)階段，即建樹和剪枝；第二步是通過使用已經(jīng)構(gòu)建好的樹型對(duì)數(shù)據(jù)集進(jìn)行分類挖掘.為了找到輸入數(shù)據(jù)所屬的分類情況，需要對(duì)決策樹進(jìn)行遍歷，即從根結(jié)點(diǎn)到葉子結(jié)點(diǎn)，依次對(duì)輸入數(shù)據(jù)進(jìn)行測試，直到找到該數(shù)據(jù)所屬分類為止.

下面簡要介紹決策樹構(gòu)造的基本方法：

(1)從訓(xùn)練樣本的單個(gè)結(jié)點(diǎn)開始，構(gòu)建決策樹.

(2)假如訓(xùn)練數(shù)據(jù)都是歸屬于某個(gè)類型，則該結(jié)點(diǎn)成為樹葉節(jié)點(diǎn)，并對(duì)該樹葉節(jié)點(diǎn)進(jìn)行類型標(biāo)記.

(3)要不然的話，算法會(huì)繼續(xù)使用各種分裂技術(shù)來對(duì)樣本數(shù)據(jù)進(jìn)行分類，其分類的依據(jù)是采用更好的分類屬性來進(jìn)行的.

(4)為測試數(shù)據(jù)的每個(gè)值建立一個(gè)分支，并以此來劃分樣本.

(5)重復(fù)應(yīng)用上面的步驟，直到整個(gè)決策樹構(gòu)建完成.

3 決策樹的學(xué)生成績分類模型

3.1 改進(jìn)ID3算法

ID3算法是Quinlan于上個(gè)世紀(jì)八十年代后期提出的[1]，是決策樹分類中最為典型的算法之一.它通過對(duì)各個(gè)測試數(shù)據(jù)屬性進(jìn)行計(jì)算它們各自的信息增益值，根據(jù)它們值的大小，來決定選取哪個(gè)數(shù)據(jù)作為分裂節(jié)點(diǎn).在ID3算法中，是通過選擇增益值最大的屬性，作為分裂的屬性.信息增益值的計(jì)算公式如式（1）所示：

上述公式中，數(shù)據(jù)集D根據(jù)類別屬性的值可以分成相互獨(dú)立的類C1，C2，…，Cn，其出現(xiàn)的概率分別為pi，而v表示屬性A具有不同的值.

然而ID3算法存在著一些不足：ID3算法對(duì)于屬性的選擇通常是離散數(shù)據(jù)，而對(duì)連續(xù)值的屬性就無法應(yīng)對(duì)；在對(duì)各個(gè)屬性數(shù)據(jù)進(jìn)行計(jì)算其信息增益時(shí)，往往會(huì)選擇數(shù)據(jù)取值較多的屬性數(shù)據(jù)，但并不是所有屬性值大的屬性就是最優(yōu)屬性；對(duì)于噪聲數(shù)據(jù)較為敏感等問題.

在前期對(duì)ID3算法進(jìn)行改進(jìn)的基礎(chǔ)上[9]，主要思想是(具體算法請(qǐng)查看文獻(xiàn)[9])：一類為正例，一類為反例.假設(shè)，正例的個(gè)數(shù)為n個(gè)，反例的個(gè)數(shù)為m個(gè).在訓(xùn)練集D中，有屬性A，A有v個(gè)不同的值，當(dāng)且有A=ai時(shí)，以屬性A分裂下的元素一共有ni+mi個(gè).其中n為正例，則有ni個(gè)正例.同理，反例個(gè)數(shù)為mi.由此，我們可以得到：

改進(jìn)的新算法是將作為新的信息期望，簡化了原先的計(jì)算方法，得出新的公式結(jié)論，計(jì)算每個(gè)屬性過后，值最小的信息作為分類標(biāo)準(zhǔn).

3.2 數(shù)據(jù)處理

本文是針對(duì)福建省計(jì)算機(jī)等級(jí)考試二級(jí)（C語言）的成績利用決策樹分類模型進(jìn)行分類挖掘.對(duì)于成績是連續(xù)型數(shù)據(jù)，而決策樹分類技術(shù)是需要離散的屬性值，因此就要對(duì)連續(xù)型數(shù)據(jù)轉(zhuǎn)變成離散型數(shù)據(jù).在數(shù)據(jù)處理中所采用的是概念分層技術(shù)，如：將選擇題的得分情況按30～40分、19～29分、0～18分劃分為“高”、“中”、“低”三類，填空題、改錯(cuò)題和編程題都是20分，它們得分情況按15～20分、8～14分、0～7分可以劃分為“高”、“中”和“低”三類，對(duì)于成績來說，我們挖掘的內(nèi)容是成績合格與否，因而將成績按0～59分和60分以上劃分為“不合格”和“合格”兩類數(shù)據(jù).經(jīng)過數(shù)據(jù)預(yù)處理工作后，得到挖掘的數(shù)據(jù)源（共8483條），如表1所示.

表1 數(shù)據(jù)預(yù)處理后的數(shù)據(jù)集

3.3 信息增益的計(jì)算

根據(jù)上述數(shù)據(jù)處理后的數(shù)據(jù)集，利用公式（4）可以計(jì)算出各個(gè)屬性值的信息增益值：

（1）選擇題的信息增益值：

在計(jì)算選擇題的信息增益時(shí)，需要分別計(jì)算選擇題得分情況為高、中、低三種屬性值情況下，它們成績合格人數(shù)和不合格人數(shù).在測試樣本數(shù)據(jù)集中，選擇題得分為高，成績?yōu)楹细竦娜藬?shù)有2545人，成績?yōu)椴缓细竦娜藬?shù)有328人，選擇題得分為中，成績?yōu)楹细竦娜藬?shù)有1193人，成績?yōu)椴缓细竦娜藬?shù)有2656人，而選擇題得分為低，成績?yōu)楹细竦娜藬?shù)有15人，成績?yōu)椴缓细竦娜藬?shù)有1263人.根據(jù)這些信息，我們得到計(jì)算平時(shí)成績的信息增益如下：

（2）改錯(cuò)題的信息增益值：

在測試樣本數(shù)據(jù)集中，改錯(cuò)題的得分情況有三種屬性值，在改錯(cuò)題得分為高下，成績?yōu)楹细竦娜藬?shù)有3074人，成績?yōu)椴缓细竦娜藬?shù)有814人，改錯(cuò)題得分為中，成績?yōu)楹细竦娜藬?shù)有651人，成績?yōu)椴缓系娜藬?shù)有1728人，改錯(cuò)題得分為低，成績?yōu)楹细竦娜藬?shù)有28人，成績?yōu)椴缓系娜藬?shù)有1705人，因此其信息增益值為：

（3）編程題的信息增益值：

編程題有三個(gè)屬性值，在編程題得分為高，成績?yōu)楹细竦娜藬?shù)有589人，成績?yōu)椴缓细竦娜藬?shù)有10人，在編程題得分為中，成績?yōu)楹细竦娜藬?shù)有2625人，成績?yōu)椴缓细竦娜藬?shù)有804人，在編程題得分為低，成績?yōu)楹细竦娜藬?shù)有539人，成績?yōu)椴缓细竦娜藬?shù)有3433人，因此其信息增益值為：

（4）填空題的信息增益值：

填空題有三個(gè)屬性值，在填空題得分為高，成績?yōu)楹细竦娜藬?shù)有2744人，成績?yōu)椴缓细竦娜藬?shù)有371人，在填空題得分為中，成績?yōu)楹细竦娜藬?shù)有893人，成績?yōu)椴缓细竦娜藬?shù)有1419人，在填空題得分為低，成績?yōu)楹细竦娜藬?shù)有116人，成績?yōu)椴缓细竦娜藬?shù)有2457人，因此其信息增益值為：

3.4 成績分類的決策樹構(gòu)建

首先就是創(chuàng)建根節(jié)點(diǎn)，然后選取各個(gè)屬性的信息增益值為最小的屬性作為分裂屬性，根據(jù)上面對(duì)各個(gè)屬性的信息增益值進(jìn)行計(jì)算，填空題的信息增益值最小，因而將填空題作為決策樹的根節(jié)點(diǎn)，建立一個(gè)決策樹，決策樹上的根節(jié)點(diǎn)標(biāo)記為“填空題”.對(duì)于填空題的三種取值，即高、中和低，分別建立相應(yīng)的子集，引出相應(yīng)的分支，如圖1所示.

在圖1種決策樹只有一層，那么在填空題的每個(gè)分支上繼續(xù)按照上面的方法建立相應(yīng)的決策樹，通過遞歸算法，計(jì)算相應(yīng)屬性的信息增益值，確定每個(gè)分支中各個(gè)節(jié)點(diǎn)，直到子集為空或者沒有屬性可以劃分為止，最終可以形成一顆決策樹.

在形成了決策樹中，樹型比較復(fù)雜，樹枝比較繁雜，比較難于理解，因而需要對(duì)生產(chǎn)的決策樹進(jìn)行剪枝，剪枝的目的是使樹型變得更小、復(fù)雜度更低、更容易理解.如在構(gòu)造的等級(jí)考試成績分類的決策樹上，填空題得分為中且改錯(cuò)題得分為中且選擇題得分為中的情況下，編程題得分為高、中、低情況下，其合格的人數(shù)分別為13人、60人和0人，而不及格的人數(shù)分別為1人、168人和354人，從這些情況看基本是不及格占絕大多數(shù)，因此可以把它們合并為不合格，同樣，在填空題得分為高且改錯(cuò)題得分為中且選擇題得分為中的情況下，編程題得分為高、中、低情況下，其分?jǐn)?shù)為合格的人數(shù)分別為15人、128人和5人，而分?jǐn)?shù)為不合格的人數(shù)分別為0人、22人和118人，這樣就可以把編程題得分為高和中合并為“≥中”等等.最終經(jīng)過剪枝后生成的決策樹如圖2所示.

3.5 決策樹分類規(guī)則及建議

根據(jù)圖2生成學(xué)生成績分類決策樹模型，可以得出一些分類規(guī)則，具體的表述如下：

IF填空題=高and改錯(cuò)題=高THEN成績?yōu)楹细竦母怕?5.3%（即：如果填空題得分在15～20分且改錯(cuò)題在15～20分時(shí)，成績?yōu)楹细竦娜藬?shù)為2271，不合格的人數(shù)為111，下面規(guī)則的解釋也是一樣，就不再進(jìn)行詳細(xì)解釋）

IF填空題=高and改錯(cuò)題=低THEN成績?yōu)椴缓细竦母怕?5.8%

IF填空題=高and改錯(cuò)題=中and選擇題=高THEN成績?yōu)楹细竦母怕?6.2%

IF填空題=高and改錯(cuò)題=中and選擇題=低THEN成績?yōu)椴缓细竦母怕?00%

根據(jù)以上得出的分類規(guī)則，我們可以給出以下一些建議：

(1)從學(xué)生角度來說，要想更好地通過福建省計(jì)算機(jī)等級(jí)考試二級(jí)（C語言），那么應(yīng)該在填空題和改錯(cuò)題兩題中得分高些.而省等級(jí)計(jì)算機(jī)考試在考察填空題和改錯(cuò)題的內(nèi)容上，恰恰是考察學(xué)生的閱讀程序和修改程序的能力，因此建議學(xué)生平時(shí)要多注重閱讀程序能力的培養(yǎng)，只有大量的閱讀程序，才能更好的修改程序和編寫程序.

(2)從教師角度來說，要想讓學(xué)生更好地通過省計(jì)算機(jī)等級(jí)考試，則應(yīng)該在課堂授課中注重理論與實(shí)踐相結(jié)合，不關(guān)是簡單地講解基本理論知識(shí)，更應(yīng)該在課堂上機(jī)過程中培養(yǎng)學(xué)生讀和寫程序的能力.

4 結(jié)論

本文針對(duì)現(xiàn)階段福建省計(jì)算機(jī)等級(jí)考試二級(jí)（C語言）的學(xué)生成績，利用決策樹分類技術(shù)，對(duì)等級(jí)考試中的成績建立決策樹模型，為提高教師的教學(xué)質(zhì)量提供決策支持.首先，將等級(jí)考試中連續(xù)型數(shù)據(jù)進(jìn)行離散化處理，構(gòu)建符合決策樹分類的屬性數(shù)據(jù)，接著利用前期提出了ID3改進(jìn)算法，計(jì)算出各個(gè)屬性的增益值，選擇信息增益值最小的屬性作為分類的根節(jié)點(diǎn)，并用遞歸算法完成整個(gè)決策樹的構(gòu)建，然后對(duì)構(gòu)建的決策樹進(jìn)行了剪枝，使其變成較為簡單的決策樹模型，最后根據(jù)決策樹模型得出了一些有關(guān)教學(xué)的規(guī)則，并給出一些相關(guān)的教學(xué)建議.

現(xiàn)階段隨著教學(xué)質(zhì)量的提升，各個(gè)高校對(duì)提高教學(xué)質(zhì)量也投入了大量精力，下一步工作，我們將繼續(xù)采用數(shù)據(jù)挖掘技術(shù)對(duì)教學(xué)數(shù)據(jù)進(jìn)行分析和挖掘，構(gòu)建更為合理的模型，為提高教學(xué)質(zhì)量提供一些建議.

〔1〕范明,孟小峰,等.數(shù)據(jù)挖掘概念與技術(shù)[M].北京:機(jī)械工業(yè)出版社，2010.

〔2〕Abeer B E D A,Sayed Elaraby I.Data Mining:A prediction forStudent'sPerformance Using Classification Method[J].World Journal of Computer Application&Technology,2014,2 (2):43-47.

〔3〕Rupp A A,Leighton J P,Baker R S,et al. Educational Data Mining and Learning Analytics[M].Learning Analytics.2014:379-396.

〔4〕Pena-AyalaA.Educationaldatamining:A survey and a data mining-based analysis of recent works[J].Expert Systems with Applications,2014,41(4):1432–1462.

〔5〕Abdullah Z,Herawan T,Deris M M.Discovering Interesting Association Rules from Student Admission Dataset[J].Lecture Notes in Electrical Engineering,2014,285:135-142.

〔6〕姜永超.基于數(shù)據(jù)挖掘的學(xué)生選課及學(xué)習(xí)行為分析算法研究 [J].現(xiàn)代電子技術(shù),2016,39(13): 145-148.

〔7〕顧輝,楊青,蔣成功,等.關(guān)聯(lián)規(guī)則在成績分析中的研究及應(yīng)用[J].計(jì)算機(jī)應(yīng)用,2015(S1):149-151.

〔8〕王華,劉萍.改進(jìn)的關(guān)聯(lián)規(guī)則算法在學(xué)生成績預(yù)警中的應(yīng)用[J].計(jì)算機(jī)工程與設(shè)計(jì),2015(3):679-682.

〔9〕陰愛英.決策樹ID3算法的一種改進(jìn)[J].電子世界,2014(22):433-434.

〔10〕梁亞聲,徐欣,成小菊,等.數(shù)據(jù)挖掘原理、算法與應(yīng)用[M].北京:機(jī)械工業(yè)出版社,2015.

TP391

A

1673-260X（2017）08-0018-04

2017-05-23

福建省教育廳中青年教師教育科研項(xiàng)目（NO.JAT160658）