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

(重慶工商大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院 重慶 400067)

引言

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

一、決策樹原理及其經(jīng)典算法

(一)決策樹原理

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

(二)ID3算法簡介

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

(三)C4.5算法簡介

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

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

在決策樹算法中，C4.5算法可以看做是ID3算法的一個(gè)后續(xù)發(fā)展，在分類決策的依據(jù)和處理的廣泛性問題上均有所優(yōu)化。其具體優(yōu)勢如下幾點(diǎn)：(1)用信息增益率來選擇屬性：在ID3算法中使用信息增益來選擇屬性，這無疑會(huì)造成會(huì)偏向于選擇值多的屬性。(2)對非離散數(shù)據(jù)即連續(xù)數(shù)值型數(shù)據(jù)也能處理。(3)在決策樹的構(gòu)造過程中對樹進(jìn)行剪枝：這就改進(jìn)了在ID3算法中樹的高度無節(jié)制地增長和過度擬合數(shù)據(jù)的出現(xiàn)。(4)能夠?qū)Σ煌暾麛?shù)據(jù)也能夠進(jìn)行處理。

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

設(shè)訓(xùn)練樣本數(shù)據(jù)集X={X1,X2,…Xn}，屬性集Q={Q1,Q2,…Qm}，Qm的值域?yàn)閧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的分割信息量定義為

數(shù)據(jù)集對Qm的條件熵為

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

二、K-Means聚類算法

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

圖1 模型流程圖

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

(一)數(shù)據(jù)的預(yù)處理與聚類

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

表1 大三上統(tǒng)計(jì)學(xué)專業(yè)(1)班期末成績

表2 各等級(jí)的聚類中心點(diǎn)(分)

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

表3 各等級(jí)的人數(shù)(人)

表4 多元統(tǒng)計(jì)分析成績與總成績等級(jí)對應(yīng)人數(shù)

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

(二)決策樹的構(gòu)建

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

然后，針對“多元統(tǒng)計(jì)分析”進(jìn)行信息熵。

如表4所示，在此成績?yōu)椤皟?yōu)”的情況下，其中總成績?yōu)椤皟?yōu)”的有6人，總成績?yōu)椤傲肌钡挠?人，總成績?yōu)椤爸小钡挠?人。根據(jù)公式(可得該科目成績在等級(jí)為“優(yōu)”的情況下的子集信息熵：

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

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

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

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

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

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

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

同理可求出“國民經(jīng)濟(jì)、統(tǒng)計(jì)軟件應(yīng)用、英語、社會(huì)實(shí)踐報(bào)告”的信息熵和信息增益率，由于篇幅問題這里就不一一列出，直接列出其余課程的信息增益率：

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

由此可見，“多元統(tǒng)計(jì)分析”的信息增益率最大，可選作首個(gè)節(jié)點(diǎn)以C4.5算法分裂其“優(yōu)、良、中”3個(gè)屬性。

(三)規(guī)則提取和規(guī)則結(jié)果分析

總評為“優(yōu)”的規(guī)則提取如下：1.若“多元統(tǒng)計(jì)分析”成績?yōu)椤皟?yōu)”且“統(tǒng)計(jì)軟件應(yīng)用”成績?yōu)椤皟?yōu)”，則可直接判定為“優(yōu)”。2.若“多元統(tǒng)計(jì)分析”成績?yōu)椤傲肌鼻摇敖y(tǒng)計(jì)軟件應(yīng)用”、“英語”、“國民經(jīng)濟(jì)”成績均為“優(yōu)”，則可判定為“優(yōu)”。

總評為“中”的規(guī)則提取如下：若“多元統(tǒng)計(jì)分析”成績?yōu)椤爸小鼻摇皣窠?jīng)濟(jì)”成績?yōu)椤傲肌被颉爸小?。相對于那些學(xué)位公共課，“國民經(jīng)濟(jì)”課程相對較通俗易懂，取得高分的幾率應(yīng)該在所有學(xué)科中比較大；若像“多元統(tǒng)計(jì)分析”這樣的必須掌握的學(xué)位專業(yè)課為“中”，且“國民經(jīng)濟(jì)”這樣的公共課為“良”或“中”，這著實(shí)反應(yīng)出該類學(xué)生對必須掌握的課程以及最簡單的課程都沒有好的成績，從一定程度上可以說明該學(xué)生的學(xué)習(xí)態(tài)度不太端正，才會(huì)導(dǎo)致總體情況不容樂觀。其余具體情況見下圖2所示(為簡明書寫，各學(xué)科以最前面的兩個(gè)字表示)：

圖2 決策樹規(guī)則展示

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

四、結(jié)論

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

[1]饒秀琪，張國基.基于KPCA的決策樹的方法及其應(yīng)用[J].計(jì)算機(jī)工程與設(shè)計(jì)，2007

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

[3]Han Jiawei,Kamber M.數(shù)據(jù)挖掘：概念與技術(shù)[M].北京:機(jī)械工業(yè)出版社，2005

[4]姚雙良.數(shù)據(jù)挖掘在高校課程相關(guān)性中的應(yīng)用研究[J].科技通報(bào)，2012

[5]高陽，廖家平，吳偉.基于決策樹的ID3算法與C4.5算法[J].湖北工業(yè)大學(xué)學(xué)報(bào)，2011

[6]哈申花，張春生.基于C4.5決策樹學(xué)生成績數(shù)據(jù)挖掘方法[J].內(nèi)蒙古民族大學(xué)學(xué)報(bào)，2010