ID3算法在程序設計類課程成績分析中的應用研究

劉敏娜

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

ID3算法在程序設計類課程成績分析中的應用研究

劉敏娜1，2

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

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

ID3算法；MATLAB；決策樹；數據挖掘

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

1　數據處理流程

數據預處理過程通常包含數據集成，數據清理，轉換和規約4個步驟［2］。

1.1數據集成

數掘集成是將多個表中數據整理后存放在一個統一的數據表中。本文中，將數據分別放入“學生調查統計表”和“老師調查統計表”中。“學生調查統計表”的包含：學號、性別、年齡、班級、課外練習時間、對本課程的興趣等屬性。

1.2數據清理

在數據中存在一些不符合現實情況的數據，為了提高數據的準確性，需要把不符合實際的數據人為的去除。比如學生的數據某些信息存在空缺，對于這種情況，可以將存在空串的記錄刪除。

1.3數據轉換

將數據轉換成離散的值。如1表示上課考勤 “差”，用2表示“一般”，用3表示“好”；用1表示上機練習時間“少”，用2表示“一般”，用3表示“多”；用1表示課程 “不感興趣”，用2表示“一般”，用3表示“感興趣”；試卷難度用1表示“低”，用2表示“中”，用3表示“高”；1表示成績 “差”，用2表示“良好”，用3表示“優秀”。

1.4數據歸約

數據歸約是在不影響最終結果的情況下對數據集中的數據進行劃分，縮小數據規模的過程。根據得到的數據集，經過觀察后使用數值壓縮方法，得到對學習成績影響最大的屬性。

2　決策樹算法

2.1ID3算法

1986年J.R.Quinlan在 Machine Learning Journal發表了題為《Inductionof Decision Trees》的論文，首次提出ID3算法［3］。ID3算法是通過計算每個屬性的信息增益，選取具有最高增益的屬性作為給定數據集合的測試屬性。對被選取的測試屬性創建一個結點，并以該屬性標記，對該屬性的每個取值創建一個分支，并據此劃分樣本［3-4］。

算法描述

ID3算法具體的偽代碼描述（T，C）如下。其中，假設T代表當前樣本集，候選屬性集用C表示，侯選屬性集中的所有屬性都為離散型，連續型必需事先經過預處理轉化為離散型［3］。

1）創建根節點N：

2）IFT都屬于同一個類Cthen返回N作為葉節點，以類C標記；

3）IFC為空

則返回N作為葉節點，標記為T中出現最多的類；

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

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

6）ForeachTest_C的取值

｛

由節點N長出一個新葉節點：

IF新葉節點對應的樣本子集T'為空

則不再分裂此葉節點，將其標記為T中出現最多的類；

ELSE

在該葉節點上執行ID3算法（T'，T'_C），對它繼續分裂；

｝

ID3算法優點

ID3算法是通過計算每個屬性的信息增益，算法理論清晰簡單；每一個結點對應一個分類規則，易于理解；使用ID3算法構建的決策樹深度小，分類速度快。

ID3算法缺點

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

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

3）ID3算法沒有考慮訓練集中的缺值問題。

4）ID3在建樹時，需要對數據集進行多次的順序掃描和排序，因而導致算法的低效。

2.2C4.5算法

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

3　系統設計與實現

系統采用MATLAB平臺開發，MATLAB是三大數學軟件之一，它在算法開發、數據分析方面有很高的實用性。文中在MATLAB中實現ID3算法，由于ID3算法是單變量決策樹，更容易反映出每個屬性對成績的影響，因此確定ID3算法作為建立決策樹的算法。

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

3.1數據采集

以軟件工程專業2012級1班的學生的 《JAVA程序設計》課程期末考試成績為基礎，挖掘出如學生上課考勤，每周上機練習時間，對本課程的興趣，試卷難度等因素對學生成績的影響。

數據采集的內容包括：1）學生的基本情況信息（主要包括學號，性別，年齡，班級）；2）學生對課程是否感興趣、每周上機練習時間等；3）上課考勤記錄、期末考試試卷難度、期末考試成績。

3.2數據處理

通過數據集成，數據清理，轉換和規約4個步驟之后學生信息表如表1。

表1　學生信息統計表

3.3決策樹模型構建

1）計算分類屬性的信息熵。

對成績進行分類，在23個樣本中成績為1的有4個樣本，為2的有5個樣本，為3的有14個樣本。計算給定樣本成績分類所需的期望信息：

2）計算屬性的信息熵。

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

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

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

上機作業時間：

因此，如果樣本按照每周上機練習時間劃分，對一個給定的樣本分類對應的熵為：

每周上機練習時間劃分的信息增益：Gain（每周上機練習時間）=I-E（每周上機練習時間）=1.353-0.969=0.384。

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

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

計算得到相應的信息增益值分別是：

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

Gain（每周上機練習時間）=I-E（每周上機練習時間）= 1.353-0.969=0.384。

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

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

圖1　學生成績分析決策樹

3.4決策樹修剪

對已經繪制好的決策樹進行剪枝，用剪枝來解決數據匹配問題。剪枝有兩種基本策略，一種是預先剪枝，另一種是后剪枝。預先剪枝在生成樹的過程中對數據進行判斷，以決定下一步是繼續劃分還是停止；后剪枝是生成一個與數據集相同的一棵樹，然后從葉子結點開始一個一個慢慢向樹根剪枝［8］。如果剪去某個葉子節點對數據準確度沒有影響就剪去該葉子節點，如果有影響就馬上停止。圖2為使用后剪枝所繪制出來的決策樹。可以明顯看到只保留對學習成績影響最大的屬性值。

圖2　修正后的決策樹

3.5模型準確性評估

通過已經構建完成的學習成績決策樹，選擇了軟件工程專業2012級2班的學生的成績作為測試數據，通過決策樹，分析出學生期末考試成績等級，然后與實際情況相比較來判斷該決策樹是否有效。經過調研及分析，確定準確率最小值是84%。經過實際測試，該決策樹準確率為90%，超過了預定的準確率，能夠滿足用戶需求，該決策樹模型符合要求。

4　結束語

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

［1］趙紅艷.決策樹技術在學生成績分析中的應用研究［D］.濟南：山東師范大學，2007.

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

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

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

［5］毛國君.數據挖掘原理與算法［M］.北京：清華大學出版社，2007：122-128.

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

［7］白雪.決策樹分類算法的研究及其在教學評估中的應用［J］.電腦開發與應用，2007，20（2）：24-26.

［8］胡江洪.基于決策樹的分類算法研究［D］.武漢：武漢理工大學，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稿件編號：201510131

陜西省教育廳專項基金資助項目（15JK1803）；陜西省科學技術研究發展計劃項目（2013JM8037）；咸陽師范學院專項科研基金項目（14XSYK036）

劉敏娜（1981—），女，陜西榆林人，碩士，講師。研究方向：CUDA并行計算，機器學習。