劉敏娜

（1.咸陽師范學(xué)院 信息工程學(xué)院，陜西 咸陽　712000；2.咸陽師范學(xué)院 圖形圖像處理研究所，陜西 咸陽　712000）

ID3算法在程序設(shè)計(jì)類課程成績(jī)分析中的應(yīng)用研究

劉敏娜1，2

（1.咸陽師范學(xué)院 信息工程學(xué)院，陜西 咸陽712000；2.咸陽師范學(xué)院 圖形圖像處理研究所，陜西 咸陽712000）

基于分析學(xué)生成績(jī)主要影響因素的目的，采用了ID3算法完成決策樹的生成。算法包括數(shù)據(jù)采集、數(shù)據(jù)處理、繪制決策樹、決策樹剪枝、去噪和模型準(zhǔn)確性評(píng)估等階段。模型選取軟件工程專業(yè)2012級(jí)1班的學(xué)生的《JAVA程序設(shè)計(jì)》課程期末考試成績(jī)和學(xué)生的基本情況信息等數(shù)據(jù)作為訓(xùn)練數(shù)據(jù)。經(jīng)過反復(fù)訓(xùn)練，模型能夠根據(jù)輸入學(xué)生的基本信息分析出學(xué)生的學(xué)習(xí)成績(jī)優(yōu)，良，差的概率。該決策樹準(zhǔn)確率為90%，能夠滿足用戶需求，決策樹模型符合要求。

ID3算法；MATLAB；決策樹；數(shù)據(jù)挖掘

隨著無紙化辦公的推進(jìn)，教務(wù)部門積累了大量的學(xué)生的電子信息，如學(xué)生的學(xué)籍信息，學(xué)習(xí)成績(jī)等數(shù)據(jù)，但是這些數(shù)據(jù)主要還是以各種形式的表格保存在存儲(chǔ)介質(zhì)中，沒有被充分挖掘背后隱藏的規(guī)律。比如，在對(duì)學(xué)生學(xué)習(xí)成績(jī)的分析處理僅僅停留在統(tǒng)計(jì)成績(jī)優(yōu)秀、良好、及格、不及格各個(gè)等級(jí)的人數(shù)，而對(duì)于學(xué)生取得這樣成績(jī)的原因沒有進(jìn)行過深究。本次研究中采用數(shù)據(jù)挖掘中的決策樹技術(shù)分析影響學(xué)生程序設(shè)計(jì)課程成績(jī)的主要因素，對(duì)教學(xué)環(huán)節(jié)進(jìn)行相應(yīng)的改進(jìn)，及時(shí)糾正學(xué)生在學(xué)習(xí)中的不良行為，減輕教師工作量，從而提高學(xué)生的學(xué)習(xí)效率，提升學(xué)校的教育教學(xué)質(zhì)量［1］。

1　數(shù)據(jù)處理流程

數(shù)據(jù)預(yù)處理過程通常包含數(shù)據(jù)集成，數(shù)據(jù)清理，轉(zhuǎn)換和規(guī)約4個(gè)步驟［2］。

1.1數(shù)據(jù)集成

數(shù)掘集成是將多個(gè)表中數(shù)據(jù)整理后存放在一個(gè)統(tǒng)一的數(shù)據(jù)表中。本文中，將數(shù)據(jù)分別放入“學(xué)生調(diào)查統(tǒng)計(jì)表”和“老師調(diào)查統(tǒng)計(jì)表”中?！皩W(xué)生調(diào)查統(tǒng)計(jì)表”的包含：學(xué)號(hào)、性別、年齡、班級(jí)、課外練習(xí)時(shí)間、對(duì)本課程的興趣等屬性。

1.2數(shù)據(jù)清理

在數(shù)據(jù)中存在一些不符合現(xiàn)實(shí)情況的數(shù)據(jù)，為了提高數(shù)據(jù)的準(zhǔn)確性，需要把不符合實(shí)際的數(shù)據(jù)人為的去除。比如學(xué)生的數(shù)據(jù)某些信息存在空缺，對(duì)于這種情況，可以將存在空串的記錄刪除。

1.3數(shù)據(jù)轉(zhuǎn)換

將數(shù)據(jù)轉(zhuǎn)換成離散的值。如1表示上課考勤 “差”，用2表示“一般”，用3表示“好”；用1表示上機(jī)練習(xí)時(shí)間“少”，用2表示“一般”，用3表示“多”；用1表示課程 “不感興趣”，用2表示“一般”，用3表示“感興趣”；試卷難度用1表示“低”，用2表示“中”，用3表示“高”；1表示成績(jī) “差”，用2表示“良好”，用3表示“優(yōu)秀”。

1.4數(shù)據(jù)歸約

數(shù)據(jù)歸約是在不影響最終結(jié)果的情況下對(duì)數(shù)據(jù)集中的數(shù)據(jù)進(jìn)行劃分，縮小數(shù)據(jù)規(guī)模的過程。根據(jù)得到的數(shù)據(jù)集，經(jīng)過觀察后使用數(shù)值壓縮方法，得到對(duì)學(xué)習(xí)成績(jī)影響最大的屬性。

2　決策樹算法

2.1ID3算法

1986年J.R.Quinlan在 Machine Learning Journal發(fā)表了題為《Inductionof Decision Trees》的論文，首次提出ID3算法［3］。ID3算法是通過計(jì)算每個(gè)屬性的信息增益，選取具有最高增益的屬性作為給定數(shù)據(jù)集合的測(cè)試屬性。對(duì)被選取的測(cè)試屬性創(chuàng)建一個(gè)結(jié)點(diǎn)，并以該屬性標(biāo)記，對(duì)該屬性的每個(gè)取值創(chuàng)建一個(gè)分支，并據(jù)此劃分樣本［3-4］。

算法描述

ID3算法具體的偽代碼描述（T，C）如下。其中，假設(shè)T代表當(dāng)前樣本集，候選屬性集用C表示，侯選屬性集中的所有屬性都為離散型，連續(xù)型必需事先經(jīng)過預(yù)處理轉(zhuǎn)化為離散型［3］。

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

2）IFT都屬于同一個(gè)類Cthen返回N作為葉節(jié)點(diǎn)，以類C標(biāo)記；

3）IFC為空

則返回N作為葉節(jié)點(diǎn)，標(biāo)記為T中出現(xiàn)最多的類；

4）ForeachC中的屬性，計(jì)算信息增益gain；

5）N的測(cè)試屬性Test_C=C中具有最高信息增益的屬性；

6）ForeachTest_C的取值

｛

由節(jié)點(diǎn)N長(zhǎng)出一個(gè)新葉節(jié)點(diǎn)：

IF新葉節(jié)點(diǎn)對(duì)應(yīng)的樣本子集T'為空

則不再分裂此葉節(jié)點(diǎn)，將其標(biāo)記為T中出現(xiàn)最多的類；

ELSE

在該葉節(jié)點(diǎn)上執(zhí)行ID3算法（T'，T'_C），對(duì)它繼續(xù)分裂；

｝

ID3算法優(yōu)點(diǎn)

ID3算法是通過計(jì)算每個(gè)屬性的信息增益，算法理論清晰簡(jiǎn)單；每一個(gè)結(jié)點(diǎn)對(duì)應(yīng)一個(gè)分類規(guī)則，易于理解；使用ID3算法構(gòu)建的決策樹深度小，分類速度快。

ID3算法缺點(diǎn)

1）該算法的注意力集中在特征的選擇上，且計(jì)算方法偏向于屬性取值數(shù)目較多的特征，而這一屬性不一定是最優(yōu)的。

2）ID3只能處理具有離散值的屬性，對(duì)連續(xù)值屬性無能為力。如對(duì)連續(xù)值的屬性，必須先對(duì)其離散化、取樣，而為了這種處理大數(shù)據(jù)集的算法，不僅增加了分類算法的額外開銷，還降低了分類的準(zhǔn)確性。

3）ID3算法沒有考慮訓(xùn)練集中的缺值問題。

4）ID3在建樹時(shí)，需要對(duì)數(shù)據(jù)集進(jìn)行多次的順序掃描和排序，因而導(dǎo)致算法的低效。

2.2C4.5算法

J.R.Quinlan通過對(duì)ID3算法的研究發(fā)現(xiàn)ID3算法存在很多不足，在1993年提出了C4.5算法，它是ID3算法的改進(jìn)算法［5］。由于ID3算法利用信息增益作為分類規(guī)則來選取影響最大屬性，這將導(dǎo)致該算法容易傾向于選擇取值較多的屬性。針對(duì)這種缺陷，C4．5算法修改了分類規(guī)則，用計(jì)算信息增益率來取代信息增益作為分類規(guī)則［6］。

3　系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)

系統(tǒng)采用MATLAB平臺(tái)開發(fā)，MATLAB是三大數(shù)學(xué)軟件之一，它在算法開發(fā)、數(shù)據(jù)分析方面有很高的實(shí)用性。文中在MATLAB中實(shí)現(xiàn)ID3算法，由于ID3算法是單變量決策樹，更容易反映出每個(gè)屬性對(duì)成績(jī)的影響，因此確定ID3算法作為建立決策樹的算法。

決策樹的建立過程主要由兩個(gè)階段組成：第一階段根據(jù)數(shù)據(jù)集繪制決策樹階段。對(duì)數(shù)據(jù)集中的每個(gè)屬性分別計(jì)算的信息增益，然后依次確定每層樹中最主要的影響因素，最后采用自頂向下的遞歸方式來繪制出決策樹。第二階段是根據(jù)繪制好的決策樹，去掉無效數(shù)據(jù)，對(duì)決策樹進(jìn)行剪枝、去噪聲階段［7］。

3.1數(shù)據(jù)采集

以軟件工程專業(yè)2012級(jí)1班的學(xué)生的 《JAVA程序設(shè)計(jì)》課程期末考試成績(jī)?yōu)榛A(chǔ)，挖掘出如學(xué)生上課考勤，每周上機(jī)練習(xí)時(shí)間，對(duì)本課程的興趣，試卷難度等因素對(duì)學(xué)生成績(jī)的影響。

數(shù)據(jù)采集的內(nèi)容包括：1）學(xué)生的基本情況信息（主要包括學(xué)號(hào)，性別，年齡，班級(jí)）；2）學(xué)生對(duì)課程是否感興趣、每周上機(jī)練習(xí)時(shí)間等；3）上課考勤記錄、期末考試試卷難度、期末考試成績(jī)。

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

通過數(shù)據(jù)集成，數(shù)據(jù)清理，轉(zhuǎn)換和規(guī)約4個(gè)步驟之后學(xué)生信息表如表1。

表1　學(xué)生信息統(tǒng)計(jì)表

3.3決策樹模型構(gòu)建

1）計(jì)算分類屬性的信息熵。

對(duì)成績(jī)進(jìn)行分類，在23個(gè)樣本中成績(jī)?yōu)?的有4個(gè)樣本，為2的有5個(gè)樣本，為3的有14個(gè)樣本。計(jì)算給定樣本成績(jī)分類所需的期望信息：

2）計(jì)算屬性的信息熵。

計(jì)算上課考勤屬性，它的屬性值分別是3、2、1。

上課考勤劃分的信息增益：

Gain（上課考勤）=I-E（上課考勤）=1.353-0.667= 0.686。

上機(jī)作業(yè)時(shí)間：

因此，如果樣本按照每周上機(jī)練習(xí)時(shí)間劃分，對(duì)一個(gè)給定的樣本分類對(duì)應(yīng)的熵為：

每周上機(jī)練習(xí)時(shí)間劃分的信息增益：Gain（每周上機(jī)練習(xí)時(shí)間）=I-E（每周上機(jī)練習(xí)時(shí)間）=1.353-0.969=0.384。

以對(duì)本課程的興趣劃分的信息增益是：

Gain（對(duì)本課程的興趣）=I-E（對(duì)本課程的興趣）=1.353-1.151=0.202。

計(jì)算得到相應(yīng)的信息增益值分別是：

Gain（上課考勤）=I-E（上課考勤）=1.353-0.667=0.686。

Gain（每周上機(jī)練習(xí)時(shí)間）=I-E（每周上機(jī)練習(xí)時(shí)間）= 1.353-0.969=0.384。

Gain（對(duì)本課程的興趣）=I-E（對(duì)本課程的興趣）=1.353-1.151=0.202。

對(duì)本課程的興趣為“感興趣”，“一般”，“不感興趣”進(jìn)行信息增益計(jì)算，得到學(xué)生成績(jī)分析決策樹，如圖1所示。

圖1　學(xué)生成績(jī)分析決策樹

3.4決策樹修剪

對(duì)已經(jīng)繪制好的決策樹進(jìn)行剪枝，用剪枝來解決數(shù)據(jù)匹配問題。剪枝有兩種基本策略，一種是預(yù)先剪枝，另一種是后剪枝。預(yù)先剪枝在生成樹的過程中對(duì)數(shù)據(jù)進(jìn)行判斷，以決定下一步是繼續(xù)劃分還是停止；后剪枝是生成一個(gè)與數(shù)據(jù)集相同的一棵樹，然后從葉子結(jié)點(diǎn)開始一個(gè)一個(gè)慢慢向樹根剪枝［8］。如果剪去某個(gè)葉子節(jié)點(diǎn)對(duì)數(shù)據(jù)準(zhǔn)確度沒有影響就剪去該葉子節(jié)點(diǎn)，如果有影響就馬上停止。圖2為使用后剪枝所繪制出來的決策樹?？梢悦黠@看到只保留對(duì)學(xué)習(xí)成績(jī)影響最大的屬性值。

圖2　修正后的決策樹

3.5模型準(zhǔn)確性評(píng)估

通過已經(jīng)構(gòu)建完成的學(xué)習(xí)成績(jī)決策樹，選擇了軟件工程專業(yè)2012級(jí)2班的學(xué)生的成績(jī)作為測(cè)試數(shù)據(jù)，通過決策樹，分析出學(xué)生期末考試成績(jī)等級(jí)，然后與實(shí)際情況相比較來判斷該決策樹是否有效。經(jīng)過調(diào)研及分析，確定準(zhǔn)確率最小值是84%。經(jīng)過實(shí)際測(cè)試，該決策樹準(zhǔn)確率為90%，超過了預(yù)定的準(zhǔn)確率，能夠滿足用戶需求，該決策樹模型符合要求。

4　結(jié)束語

對(duì)決策樹技術(shù)在高校學(xué)生成績(jī)分析中的應(yīng)用研究中，使用了ID3算法建立模型。在算法實(shí)現(xiàn)中經(jīng)歷了數(shù)據(jù)的采集與處理，決策樹模型的建立等過程。建立模型時(shí)，通過分析上課考勤，每周上機(jī)練習(xí)時(shí)間，對(duì)本課程的興趣以及試卷難度四個(gè)因素，選擇具有最大信息熵的屬性作為根節(jié)點(diǎn)，每確定一個(gè)根節(jié)點(diǎn)就必須再次計(jì)算最大信息熵，從而再次確定新的根節(jié)點(diǎn)，經(jīng)過多次計(jì)算和遞歸調(diào)用，生成學(xué)生成績(jī)分析決策樹。通過測(cè)試數(shù)據(jù)的驗(yàn)證，該模型能根據(jù)學(xué)生的學(xué)習(xí)興趣，考勤情況，上機(jī)練習(xí)時(shí)間和試卷難度預(yù)測(cè)出學(xué)生學(xué)習(xí)成績(jī)。

［1］趙紅艷.決策樹技術(shù)在學(xué)生成績(jī)分析中的應(yīng)用研究［D］.濟(jì)南：山東師范大學(xué)，2007.

［2］邵峰晶，于忠清.數(shù)據(jù)挖掘原理與算法［M］.北京：中國(guó)水利水電出版社，2003.

［3］Quinlan J R.Induction of decision trees［J］.Machine Learn-

［4］林向陽.數(shù)據(jù)挖掘中的決策樹算法比較研究［J］.中國(guó)科技信息，2010（2）：94-95.

［5］毛國(guó)君.數(shù)據(jù)挖掘原理與算法［M］.北京：清華大學(xué)出版社，2007：122-128.

［6］Quinlan J R.C4.5：Programs for Machine Learning［J］.Machine Learning，1993（16）：235-240.

［7］白雪.決策樹分類算法的研究及其在教學(xué)評(píng)估中的應(yīng)用［J］.電腦開發(fā)與應(yīng)用，2007，20（2）：24-26.

［8］胡江洪.基于決策樹的分類算法研究［D］.武漢：武漢理工大學(xué)，2006.

Application of the decision tree analysis technique in scores of programming course

LIU Min-na1，2
（1.Xianyang Normal University，College of Information Engineering，Xianyang 712000，China；2.Xianyang Normal University Institute of Graphics and Image Processing，Xianyang 712000，China）

Based on the analysis of the main influence factors of students'performance，the ID3 algorithm is used to accomplish the decision tree.Algorithm consists of data acquisition，data processing，drawing decision tree，decision tree pruning，to noise and the accuracy of the model evaluation.Model selection of software engineering 1 class 2012 students of the"JAVA program design"course final exam results and students'basic information and other data as training data.After repeated training，the model can be based on the basic information of the students to analyze the students'learning performance，good，poor probability.The accuracy rate of the decision tree is 90%，which can satisfy the needs of users，and the decision tree model meets the requirements.

ID3 algorithm；MATLAB；decision tree；data mining

TN-9

A

1674－6236（2016）09-0042-03

2015-10-20稿件編號(hào)：201510131

陜西省教育廳專項(xiàng)基金資助項(xiàng)目（15JK1803）；陜西省科學(xué)技術(shù)研究發(fā)展計(jì)劃項(xiàng)目（2013JM8037）；咸陽師范學(xué)院專項(xiàng)科研基金項(xiàng)目（14XSYK036）

劉敏娜（1981—），女，陜西榆林人，碩士，講師。研究方向：CUDA并行計(jì)算，機(jī)器學(xué)習(xí)。