陰愛英,楊曉花
(福州大學(xué)至誠學(xué)院 計算機(jī)工程系,福建 福州 350002)
基于決策樹的學(xué)生成績分類研究
陰愛英,楊曉花
(福州大學(xué)至誠學(xué)院 計算機(jī)工程系,福建 福州 350002)
本文根據(jù)決策樹分類技術(shù)對福建省計算機(jī)等級考試中的成績進(jìn)行分析和挖掘.首先對成績數(shù)據(jù)進(jìn)行離散化處理,設(shè)置成決策樹分類的屬性數(shù)據(jù);接著利用ID3改進(jìn)算法構(gòu)建成績分類的決策樹模型,并對其剪枝;最后根據(jù)模型給出相應(yīng)的規(guī)則和幾個教學(xué)建議.實驗結(jié)果表明,利用決策樹分類技術(shù)在計算機(jī)等級考試中進(jìn)行挖掘分析的方法是有效可行的.
數(shù)據(jù)挖掘;決策樹;信息增益;計算機(jī)等級考試
隨著數(shù)據(jù)挖掘技術(shù)的發(fā)展,各行各業(yè)均利用數(shù)據(jù)挖掘技術(shù)來為其提供決策支持.數(shù)據(jù)挖掘技術(shù)是從大量的數(shù)據(jù)中,挖掘出人們開始并不知道的但又隱含在數(shù)據(jù)庫中的并且有用的信息[1].隨著高等教育行業(yè)的信息化技術(shù)的發(fā)展,越來越多的管理者或老師更加關(guān)注學(xué)生的學(xué)習(xí)情況,通過對歷年來的教學(xué)數(shù)據(jù)進(jìn)行分析,挖掘出影響學(xué)生學(xué)習(xí)成績的一些關(guān)鍵信息,以此提高教學(xué)質(zhì)量.
近年來,國內(nèi)外學(xué)者對數(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ù)對學(xué)生學(xué)習(xí)能力進(jìn)行挖掘;Alejandro[4]通過對EDM平臺進(jìn)行維護(hù)和擴(kuò)展,并對該平臺利用數(shù)據(jù)挖掘的方法進(jìn)行分析和討論;Abdullah等[5]利用關(guān)聯(lián)規(guī)則對電子管理系統(tǒng)進(jìn)行挖掘,為教育管理機(jī)構(gòu)提供決策支持;姜永超通過關(guān)聯(lián)規(guī)則和序列模式進(jìn)行挖掘,分別對學(xué)生選課和學(xué)習(xí)興趣的行為進(jìn)行分析研究[6];顧輝等[7]利用對關(guān)聯(lián)規(guī)則Apriori算法的改進(jìn),并應(yīng)用于《計算機(jī)基礎(chǔ)》課程的學(xué)生成績進(jìn)行研究與分析;王華等[8]根據(jù)關(guān)聯(lián)規(guī)則技術(shù)對學(xué)生成績進(jìn)行挖掘,并對學(xué)生的成績進(jìn)行預(yù)警,及時找出可能出現(xiàn)不及格的課程,對部分學(xué)生給出警告.
本文通過在前期工作研究的基礎(chǔ)上[9],利用決策樹分類挖掘技術(shù),對福建省計算機(jī)等級考試二級(C語言)進(jìn)行挖掘,用決策樹分類技術(shù)構(gòu)建學(xué)生成績是否合格與哪些題型得分情況有關(guān)的決策樹分類模型,為老師更好地教授好這門課程提供一些有用信息,也為學(xué)生能更好地通過等級考試提供了參考資料.
決策樹(Decision Tree)又稱判定樹[10],是采用樹型結(jié)構(gòu)對數(shù)據(jù)進(jìn)行分類的.它是從一堆沒有任何規(guī)則且是無序的數(shù)據(jù)中,根據(jù)分類規(guī)則,利用樹的形狀來表示這些數(shù)據(jù)的分類情況.在構(gòu)造的決策樹中,樹的最頂層是根結(jié)點,它是表示第一次選擇分裂的屬性,而樹的其它內(nèi)部結(jié)點(不是葉子結(jié)點)表示對其它屬性數(shù)據(jù)的測試,葉子結(jié)點表示數(shù)據(jù)屬性的分類情況,而對于一個決策樹的分支來說,其代表著某個測試數(shù)據(jù)屬性的分類情況輸出.
一般來說,利用決策樹進(jìn)行分類挖掘時,需要經(jīng)歷下面的過程:第一步是構(gòu)建決策樹模型,即利用先知類型的樣本數(shù)據(jù)對其實行分類,構(gòu)造一個決策樹模型.在這個步驟中要經(jīng)歷兩個階段,即建樹和剪枝;第二步是通過使用已經(jīng)構(gòu)建好的樹型對數(shù)據(jù)集進(jìn)行分類挖掘.為了找到輸入數(shù)據(jù)所屬的分類情況,需要對決策樹進(jìn)行遍歷,即從根結(jié)點到葉子結(jié)點,依次對輸入數(shù)據(jù)進(jìn)行測試,直到找到該數(shù)據(jù)所屬分類為止.
下面簡要介紹決策樹構(gòu)造的基本方法:
(1)從訓(xùn)練樣本的單個結(jié)點開始,構(gòu)建決策樹.
(2)假如訓(xùn)練數(shù)據(jù)都是歸屬于某個類型,則該結(jié)點成為樹葉節(jié)點,并對該樹葉節(jié)點進(jìn)行類型標(biāo)記.
(3)要不然的話,算法會繼續(xù)使用各種分裂技術(shù)來對樣本數(shù)據(jù)進(jìn)行分類,其分類的依據(jù)是采用更好的分類屬性來進(jìn)行的.
(4)為測試數(shù)據(jù)的每個值建立一個分支,并以此來劃分樣本.
(5)重復(fù)應(yīng)用上面的步驟,直到整個決策樹構(gòu)建完成.
3.1 改進(jìn)ID3算法
ID3算法是Quinlan于上個世紀(jì)八十年代后期提出的[1],是決策樹分類中最為典型的算法之一.它通過對各個測試數(shù)據(jù)屬性進(jìn)行計算它們各自的信息增益值,根據(jù)它們值的大小,來決定選取哪個數(shù)據(jù)作為分裂節(jié)點.在ID3算法中,是通過選擇增益值最大的屬性,作為分裂的屬性.信息增益值的計算公式如式(1)所示:
上述公式中,數(shù)據(jù)集D根據(jù)類別屬性的值可以分成相互獨立的類C1,C2,…,Cn,其出現(xiàn)的概率分別為pi,而v表示屬性A具有不同的值.
然而ID3算法存在著一些不足:ID3算法對于屬性的選擇通常是離散數(shù)據(jù),而對連續(xù)值的屬性就無法應(yīng)對;在對各個屬性數(shù)據(jù)進(jìn)行計算其信息增益時,往往會選擇數(shù)據(jù)取值較多的屬性數(shù)據(jù),但并不是所有屬性值大的屬性就是最優(yōu)屬性;對于噪聲數(shù)據(jù)較為敏感等問題.
在前期對ID3算法進(jìn)行改進(jìn)的基礎(chǔ)上[9],主要思想是(具體算法請查看文獻(xiàn)[9]):一類為正例,一類為反例.假設(shè),正例的個數(shù)為n個,反例的個數(shù)為m個.在訓(xùn)練集D中,有屬性A,A有v個不同的值,當(dāng)且有A=ai時,以屬性A分裂下的元素一共有ni+mi個.其中n為正例,則有ni個正例.同理,反例個數(shù)為mi.由此,我們可以得到:
改進(jìn)的新算法是將作為新的信息期望,簡化了原先的計算方法,得出新的公式結(jié)論,計算每個屬性過后,值最小的信息作為分類標(biāo)準(zhǔn).
3.2 數(shù)據(jù)處理
本文是針對福建省計算機(jī)等級考試二級(C語言)的成績利用決策樹分類模型進(jìn)行分類挖掘.對于成績是連續(xù)型數(shù)據(jù),而決策樹分類技術(shù)是需要離散的屬性值,因此就要對連續(xù)型數(shù)據(jù)轉(zhuǎn)變成離散型數(shù)據(jù).在數(shù)據(jù)處理中所采用的是概念分層技術(shù),如:將選擇題的得分情況按30~40分、19~29分、0~18分劃分為“高”、“中”、“低”三類,填空題、改錯題和編程題都是20分,它們得分情況按15~20分、8~14分、0~7分可以劃分為“高”、“中”和“低”三類,對于成績來說,我們挖掘的內(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ù)上述數(shù)據(jù)處理后的數(shù)據(jù)集,利用公式(4)可以計算出各個屬性值的信息增益值:
(1)選擇題的信息增益值:
在計算選擇題的信息增益時,需要分別計算選擇題得分情況為高、中、低三種屬性值情況下,它們成績合格人數(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ù)這些信息,我們得到計算平時成績的信息增益如下:
(2)改錯題的信息增益值:
在測試樣本數(shù)據(jù)集中,改錯題的得分情況有三種屬性值,在改錯題得分為高下,成績?yōu)楹细竦娜藬?shù)有3074人,成績?yōu)椴缓细竦娜藬?shù)有814人,改錯題得分為中,成績?yōu)楹细竦娜藬?shù)有651人,成績?yōu)椴缓系娜藬?shù)有1728人,改錯題得分為低,成績?yōu)楹细竦娜藬?shù)有28人,成績?yōu)椴缓系娜藬?shù)有1705人,因此其信息增益值為:
(3)編程題的信息增益值:
編程題有三個屬性值,在編程題得分為高,成績?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)填空題的信息增益值:
填空題有三個屬性值,在填空題得分為高,成績?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é)點,然后選取各個屬性的信息增益值為最小的屬性作為分裂屬性,根據(jù)上面對各個屬性的信息增益值進(jìn)行計算,填空題的信息增益值最小,因而將填空題作為決策樹的根節(jié)點,建立一個決策樹,決策樹上的根節(jié)點標(biāo)記為“填空題”.對于填空題的三種取值,即高、中和低,分別建立相應(yīng)的子集,引出相應(yīng)的分支,如圖1所示.
在圖1種決策樹只有一層,那么在填空題的每個分支上繼續(xù)按照上面的方法建立相應(yīng)的決策樹,通過遞歸算法,計算相應(yīng)屬性的信息增益值,確定每個分支中各個節(jié)點,直到子集為空或者沒有屬性可以劃分為止,最終可以形成一顆決策樹.
在形成了決策樹中,樹型比較復(fù)雜,樹枝比較繁雜,比較難于理解,因而需要對生產(chǎn)的決策樹進(jìn)行剪枝,剪枝的目的是使樹型變得更小、復(fù)雜度更低、更容易理解.如在構(gòu)造的等級考試成績分類的決策樹上,填空題得分為中且改錯題得分為中且選擇題得分為中的情況下,編程題得分為高、中、低情況下,其合格的人數(shù)分別為13人、60人和0人,而不及格的人數(shù)分別為1人、168人和354人,從這些情況看基本是不及格占絕大多數(shù),因此可以把它們合并為不合格,同樣,在填空題得分為高且改錯題得分為中且選擇題得分為中的情況下,編程題得分為高、中、低情況下,其分?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改錯題=高THEN成績?yōu)楹细竦母怕?5.3%(即:如果填空題得分在15~20分且改錯題在15~20分時,成績?yōu)楹细竦娜藬?shù)為2271,不合格的人數(shù)為111,下面規(guī)則的解釋也是一樣,就不再進(jìn)行詳細(xì)解釋)
IF填空題=高and改錯題=低THEN成績?yōu)椴缓细竦母怕?5.8%
IF填空題=高and改錯題=中and選擇題=高THEN成績?yōu)楹细竦母怕?6.2%
IF填空題=高and改錯題=中and選擇題=低THEN成績?yōu)椴缓细竦母怕?00%
根據(jù)以上得出的分類規(guī)則,我們可以給出以下一些建議:
(1)從學(xué)生角度來說,要想更好地通過福建省計算機(jī)等級考試二級(C語言),那么應(yīng)該在填空題和改錯題兩題中得分高些.而省等級計算機(jī)考試在考察填空題和改錯題的內(nèi)容上,恰恰是考察學(xué)生的閱讀程序和修改程序的能力,因此建議學(xué)生平時要多注重閱讀程序能力的培養(yǎng),只有大量的閱讀程序,才能更好的修改程序和編寫程序.
(2)從教師角度來說,要想讓學(xué)生更好地通過省計算機(jī)等級考試,則應(yīng)該在課堂授課中注重理論與實踐相結(jié)合,不關(guān)是簡單地講解基本理論知識,更應(yīng)該在課堂上機(jī)過程中培養(yǎng)學(xué)生讀和寫程序的能力.
本文針對現(xiàn)階段福建省計算機(jī)等級考試二級(C語言)的學(xué)生成績,利用決策樹分類技術(shù),對等級考試中的成績建立決策樹模型,為提高教師的教學(xué)質(zhì)量提供決策支持.首先,將等級考試中連續(xù)型數(shù)據(jù)進(jìn)行離散化處理,構(gòu)建符合決策樹分類的屬性數(shù)據(jù),接著利用前期提出了ID3改進(jìn)算法,計算出各個屬性的增益值,選擇信息增益值最小的屬性作為分類的根節(jié)點,并用遞歸算法完成整個決策樹的構(gòu)建,然后對構(gòu)建的決策樹進(jìn)行了剪枝,使其變成較為簡單的決策樹模型,最后根據(jù)決策樹模型得出了一些有關(guān)教學(xué)的規(guī)則,并給出一些相關(guān)的教學(xué)建議.
現(xiàn)階段隨著教學(xué)質(zhì)量的提升,各個高校對提高教學(xué)質(zhì)量也投入了大量精力,下一步工作,我們將繼續(xù)采用數(shù)據(jù)挖掘技術(shù)對教學(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ī)應(yīng)用,2015(S1):149-151.
〔8〕王華,劉萍.改進(jìn)的關(guān)聯(lián)規(guī)則算法在學(xué)生成績預(yù)警中的應(yīng)用[J].計算機(jī)工程與設(shè)計,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
福建省教育廳中青年教師教育科研項目(NO.JAT160658)