K-均值聚類與決策樹C4.5算法在成績分析中的應用研究

(重慶工商大學數學與統計學院 重慶 400067)

引言

學生的成績分析是高校管理中的最重要一環，是進行綜合素質測評的依據，但目前各高校采取的是比較簡單淺層次的分析，且不重視各科之間和各科與總成績之間的種種關聯，只以總成績的高低來作為劃分成績等級的依據，忽略了各科目的難易程度、重要程度、教學水平的差異程度等因素。所以，為幫助老師合理地開展和改善教學工作，更好地找到影響成績的相關因素，制定科學有效的成績分析模型是非常必要且不可忽視的重中之重。

一、決策樹原理及其經典算法

(一)決策樹原理

決策樹(Decision Tree)是機器學習中最基礎且應用最廣泛的算法模型，也是最經常使用的數據挖掘算法，是一種有監督的學習方法。具體來講它是通過一系列規則對數據進行分類的過程，關鍵步驟在于找到對劃分數據分類時起決定性作用的某種特征。它通常的表現形式為附加概率結果的樹狀結構決策圖，以最直觀的表示形態來展現結果。決策樹的原理和算法相對直觀簡單，再加上它效率高可反復利用等特點，被越來越多的讀者使用。

(二)ID3算法簡介

ID3算法是決策樹的一種，ID3算法的核心思想就是以信息增益來度量屬性的選擇，選擇分裂后信息增益最大的屬性進行分裂。該算法的缺點在于處理大型數據速度較慢，不可以并行和不可以處理數值型數據，只適用于非增量數據集。它的基本步驟為：(1)計算分類系統信息熵(2)計算條件熵(3)計算信息增益量。

(三)C4.5算法簡介

C4.5算法可以看成是ID3算法的后續算法，但它是基于信息增益比的分類決策方法，即其根本區別就在于C4.5算法在選取決斷特征時選擇信息增益比最大的，即分類決策的依據有些不同，但都是貪心算法的運用，且在遞歸和結構上大致相同。在C4.5算法的決策樹中，每個節點都保存了可以用于計算某值屬性的信息。

(四)ID3算法與C4.5算法的比較和選取

在決策樹算法中，C4.5算法可以看做是ID3算法的一個后續發展，在分類決策的依據和處理的廣泛性問題上均有所優化。其具體優勢如下幾點：(1)用信息增益率來選擇屬性：在ID3算法中使用信息增益來選擇屬性，這無疑會造成會偏向于選擇值多的屬性。(2)對非離散數據即連續數值型數據也能處理。(3)在決策樹的構造過程中對樹進行剪枝：這就改進了在ID3算法中樹的高度無節制地增長和過度擬合數據的出現。(4)能夠對不完整數據也能夠進行處理。

綜上看來，C4.5算法在算法的效率和性能程度上較優于ID3算法。為選取C4.5算法運用于下文的實例分析，下面具體闡述C4.5算法的實際計算步驟：

設訓練樣本數據集X={X1,X2,…Xn}，屬性集Q={Q1,Q2,…Qm}，Qm的值域為{q1,q2,…qt}，則：

第1步：求得不同類別的信息熵為

①

第2步：屬性Qm的信息熵為

②

第3步：屬性Qm的信息增益為

gain(X,Qm)=M(X)-B(X,Qm)

③

第4步：屬性Qm的信息增益率為

ratio(X,Qm)=gain(X,Qm)/split(X,Qm)

④

其中對屬性Qm的分割信息量定義為

數據集對Qm的條件熵為

M(X,Qm=qj)=∑(-P(Xi|Qm=qj)log2P(Xi|Qm=qj)

二、K-Means聚類算法

K均值聚類算法屬于聚類分析方法中一種較為基本的且應用廣泛的劃分方法，是一種無監督的學習算法，它將相似的數據歸納到同一簇中，即在無類標號數據中發現簇和簇中心的方法，在SPSS中即可完成。首先算法以K個初始點作為質心，然后將N個數據對象劃分為K個聚類，最后再根據距離中心點的最短距離不斷調整質心，利用各聚類中對象的均值所獲得的一個中心對象來計算并定義“相似度”。此算法要求滿足，分類對象在同一聚類中的相似度較高，而在不同聚類中的相似度較低。整個流程圖如下圖1所示：

圖1 模型流程圖

三、基于K均值聚類和決策樹C4.5算法的實例分析

(一)數據的預處理與聚類

本文選取的數據樣本來源于某高校大三年級統計學專業學生的期末考試成績。在原始數據中，個別學生有缺考、休學等情況，在進行聚類分析和決策樹的構造之前可以將此類數據看成無效數據給予清除，此例中無效數據只有2個，最終可處理的樣本數為48個，預處理后得到表1：

表1 大三上統計學專業(1)班期末成績

表2 各等級的聚類中心點(分)

首先運用SPSS將進行K-均值聚類，將期末成績分為“優、良、中”三個等級。聚類后的結果包括各等級的聚類中心和各等級相對應的人數，分別見表2、表3。由于篇幅問題，這里僅將“多元統計分析“這個科目與總成績的等級人數細分情況給予展示，具體見表4：

表3 各等級的人數(人)

表4 多元統計分析成績與總成績等級對應人數

通過K均值聚類后就可以更加清楚直觀地看到，各個科目成績的重心點、各科成績在三種等級下的人數分配、總成績在三種等級下的人數分配，對這個班學生成績水平的大致情況有了個直觀了解。

(二)決策樹的構建

首先，根據表3中總分在各等級下的人數情況，根據公式(可算得不同類別的信息熵為：

然后，針對“多元統計分析”進行信息熵。

如表4所示，在此成績為“優”的情況下，其中總成績為“優”的有6人，總成績為“良”的有2人，總成績為“中”的有0人。根據公式(可得該科目成績在等級為“優”的情況下的子集信息熵：

B(X,Qm)1=-6/8*log2(6/8)-2/8*log2(2/8)

同理，該科目成績在等級為“良”的情況下的子集信息熵：

B(X,Qm)2=-9/25*log2(9/25)-12/25*log2(12/25)-4/25*log2(4/25)

該科目成績在等級為“中”的情況下的子集信息熵：

B(X,Qm)3=-3/15*log2(3/15)-9/15*log2(9/15)-3/15*log2(3/15)

其次，根據公式(和44求得“多元統計分析”的信息熵和信息增益率。

gain(X,Qm)=8/48*B(X,Qm)1+25/48*B(X,Qm)2+15/48*B(X,Qm)3

ratio(X,Qm)1=gain(X,Qm)/split(X,Qm)=gain(X,Qm)/-8/48*log2(8/48)-25/48*log2(25/48)-15/48*log2(15/48)=0.444

同理可求出“國民經濟、統計軟件應用、英語、社會實踐報告”的信息熵和信息增益率，由于篇幅問題這里就不一一列出，直接列出其余課程的信息增益率：

ratio(X,Qm)2=0.376ratio(X,Qm)3=0.402ratio(X,Qm)4=0.362ratio(X,Qm)5=0.195

由此可見，“多元統計分析”的信息增益率最大，可選作首個節點以C4.5算法分裂其“優、良、中”3個屬性。

(三)規則提取和規則結果分析

總評為“優”的規則提取如下：1.若“多元統計分析”成績為“優”且“統計軟件應用”成績為“優”，則可直接判定為“優”。2.若“多元統計分析”成績為“良”且“統計軟件應用”、“英語”、“國民經濟”成績均為“優”，則可判定為“優”。

總評為“中”的規則提取如下：若“多元統計分析”成績為“中”且“國民經濟”成績為“良”或“中”。相對于那些學位公共課，“國民經濟”課程相對較通俗易懂，取得高分的幾率應該在所有學科中比較大；若像“多元統計分析”這樣的必須掌握的學位專業課為“中”，且“國民經濟”這樣的公共課為“良”或“中”，這著實反應出該類學生對必須掌握的課程以及最簡單的課程都沒有好的成績，從一定程度上可以說明該學生的學習態度不太端正，才會導致總體情況不容樂觀。其余具體情況見下圖2所示(為簡明書寫，各學科以最前面的兩個字表示)：

圖2 決策樹規則展示

由上分析可知，單憑總成績的高低來分析成績是不太科學合理的，其中的“多元統計分析”和“統計軟件應用”為統計學專業學生的學位專業課，學生想要學習好專業技能以便更好地找工作，那么學好這兩門課是必要的。當然，這兩門學科的學科難度是相對較大的，能在期末考試中取得高分的同學在一定程度上可以說明是比較優秀的。在今后的教學中，對此類學科的教學管理方法也應該加以重視。一般來講，專業課成績比較好的其他課程成績也相對較不錯，而連學位公共課成績都不太好的學生其他成績也更是不容樂觀，這一點也符合常理。

四、結論

由于K均值聚類法的“算法簡單快速，具有較高的效率且可收縮”等優點，首先選取了此類無監督的學習算法將數據進行合理地分類。再考慮到目前比較流行的決策樹算法易于理解較為直觀，對ID3和C4.5算法綜合比較，優選出基于C4.5算法的決策樹來進行規制的構造。通過對實例“學生期末考試成績的評定”的分析，摒棄了原始的按總分成績來劃分等級的不合理規制，將K均值聚類法和決策樹的C4.5算法引入其中，得出了全新的成績評定規則，從分析的過程和結果上看，此類算法更加科學合理。

[1]饒秀琪，張國基.基于KPCA的決策樹的方法及其應用[J].計算機工程與設計，2007

[2]葛宏偉，楊鏡非.決策樹在短期電氣負荷預測中的應用.[J].華中電力，2009

[3]Han Jiawei,Kamber M.數據挖掘：概念與技術[M].北京:機械工業出版社，2005

[4]姚雙良.數據挖掘在高校課程相關性中的應用研究[J].科技通報，2012

[5]高陽，廖家平，吳偉.基于決策樹的ID3算法與C4.5算法[J].湖北工業大學學報，2011

[6]哈申花，張春生.基于C4.5決策樹學生成績數據挖掘方法[J].內蒙古民族大學學報，2010