馬偉杰

(鄭州航空工業(yè)管理學院 計算機科學與應用系，河南 鄭州 450015)

高校獎學金評定是一項每年必須重復的繁瑣而又重要的工作，涉及范圍很廣，它要根據(jù)不同情況評定出不同的獎學金獲得者，需要記錄和處理的數(shù)據(jù)量也很龐大.如何對獎學金獲得者做出科學、有效的評價已成為高校學生管理者關注的焦點問題之一[1].

決策樹是判斷給定樣本與某種屬性相關聯(lián)的決策過程的一種表示方法,該方法廣泛應用于數(shù)據(jù)挖掘和機器學習等領域，用來解決與分類相關的問題[2]，是應用最廣泛的邏輯方法.目前，生成決策樹方法的算法主要有3種：CART算法、ID3算法和C4.5算法，其中C4.5算法具有分類速度快且精度高的特點，是發(fā)展得比較完善的一種決策樹算法[3].

1 C4. 5決策樹算法

C4.5算法是構造決策樹分類器的一種有效算法,最終可以形成產(chǎn)生式規(guī)則.C4.5算法的輸入是一張關系表,由若干不同的屬性及若干數(shù)據(jù)元組(稱為訓練樣本)組成.屬性分為兩部分,一部分作為判定對象屬性(判定樹中的非葉節(jié)點),另一部分作為分類對象屬性(判定樹中的葉節(jié)點).C4.5算法采用信息熵的方法,比較各個判定對象屬性的信息增益率的大小,選擇信息增益率最大的屬性進行分類,遞歸生成一個判定樹[4-5].

設|S|為訓練集S的樣本總數(shù)，一共有m類樣本Ci(i=1，2，3，…，m),|Ci|為類Ci中的樣本數(shù)，設Pi=|Ci|/|S|是任意樣本屬于Ci的概率，訓練樣本分類屬性的總信息熵E(S1，S2，…，Sm)的計算公式為：

(1)

設屬性A具有v個不同值{a1，a2，…，av}，可以用屬性A將S劃分為v個子集{S1，S2，…，Sv}，其中Sj包含S中這樣一些樣本，它們在A上具有值aj(j=1，2，…，v).設|Sij|為Si類中Cj的樣本數(shù)，以屬性A為分類所需的期望熵E(A)的計算公式為：

(2)

屬性A相對于類別集合C的信息增益Gain(C，A)的計算公式為：

Gain(C，A)=E(S1，S2，…，Sm)-E(A).

(3)

屬性A相對于類別集合C的信息增益率GainRatio(C，A)的計算公式為：

GainRatio(C，A)=Gain(C，A)/E(S1，S2，…，Sm).

(4)

C4.5算法是一個循環(huán)、遞歸的過程，核心部分的描述如下：

/*參數(shù)：R表示判定對象屬性，C表示目標屬性，S表示訓練集*/

DecisionTree C45(R,C,S)

{

if(S為空) return NULL；

if(S包含目標屬性的值都相同) return 具有該值的結點；

if(R為空) return 具有S中出現(xiàn)最頻繁的目標屬性值的結點；

獲取R中最大增益Gain(D，S)的屬性D；

{d[j]|j=1，2，…，m}為屬性D的取值；

{s[j]|j=1，2，…，m}為與S相對應的包含屬性D相應取值d[j]的訓練集；

Return(以D為根，D射出的弧為d[1]，d[2]，…，d[m]的決策樹)；

/*遞歸得到包含屬性D相應取值d[j]的各個子決策樹*/

for(i-1；i<=m；i++)C45(R-D，C，S[i])；

}

2 C4. 5算法在高校獎學金評定中的應用

2.1 問題定義與數(shù)據(jù)預處理

獎學金的評定，一方面要根據(jù)學生各個科目的學習成績，另一方面還要結合每位學生的具體表現(xiàn)和實際情況，包括學生的德育、體育及某方面的突出表現(xiàn)等.根據(jù)學生各個科目的學習成績的平均績點、德育成績(把某方面的突出表現(xiàn)轉(zhuǎn)換為德育成績)以及體育成績，建立C4.5決策樹的分類預測模型，對獎學金等級進行評價,其實質(zhì)是運用C4.5算法進行數(shù)據(jù)挖掘，獲得分類規(guī)律，即成績與獎學金等級之間的關系,推導出分類規(guī)則，即獎學金等級智能評價模型.

以計算機系2009級216名學生2010—2011學年的成績?yōu)槔?shù)據(jù)表，包括字段學號、平均績點、體育成績、德育成績和獎學金等級.通過數(shù)據(jù)清洗、數(shù)據(jù)轉(zhuǎn)換、數(shù)據(jù)集成及數(shù)據(jù)規(guī)約等技術,去掉數(shù)據(jù)集中的噪聲和不相關信息,將數(shù)據(jù)源的數(shù)據(jù)類型與值轉(zhuǎn)換成統(tǒng)一的格式.對獎學金等級的屬性作處理：①全年級前10%的學生獲得一等獎學金；②排名在11%～20%的學生獲得二等獎學金；③排名在21%～40%的學生獲得三等獎學金；④剩下的學生不能獲得獎學金，獎學金等級為無.

定義德育成績：根據(jù)系部情況，將德育成績轉(zhuǎn)換為A,B,C三等，其中A表示排名在全年級的前40%，B表示排名在41%～70%，剩余學生的德育成績?yōu)镃.

定義體育成績：根據(jù)系部情況，將體育成績劃分為合格與不合格兩類.

數(shù)據(jù)預處理完成后得到轉(zhuǎn)換后的學生成績信息表,見表1.由于記錄太多,表1僅顯示部分記錄[6].

隨機抽取預處理后2/3的數(shù)據(jù)即144個數(shù)據(jù)樣本作為C4.5算法的訓練集,剩下1/3的數(shù)據(jù)即72個數(shù)據(jù)樣本作為測試集.

2.2 構造決策樹

數(shù)據(jù)預處理后，開始歸納決策樹，此過程使用數(shù)據(jù)預處理得到的訓練集.根據(jù)前述的C4.5算法,將屬性平均績點、體育成績與德育成績作為算法的對象屬性, 將屬性獎學金等級作為目標屬性,利用信息增益率的定義將屬性進行排列,具有最高信息增益率的屬性選作給定集合的測試屬性.創(chuàng)建一個根結點,以該屬性標記對屬性的每個值創(chuàng)建分枝,然后遞歸建樹,可構造一棵決策樹,算法具體處理過程如下[7]:

表1 數(shù)據(jù)轉(zhuǎn)換后的學生成績信息特征集(部分)Tab.1 The information feature set of students achievement after data transformed(partly)

訓練樣本數(shù)據(jù)集S中共有144個元組,其中獎學金等級屬性(屬性值為一等、二等、三等和無)的每個屬性值所對應的子集中元組個數(shù)分別為S1=6,S2=10,S3=20,S4= 108.為了計算每一個決策屬性的信息增益,首先利用公式計算集合S分類的總信息熵:

然后計算每一個決策屬性的期望信息熵.

對屬性體育成績，當體育成績=“合格”時：

當體育成績=“不合格”時：

由此，得出體育成績的熵值為:

因此,體育成績的信息增益為：

Gain(TY)=E(S1，S2，S3，S4)-E(TY)=0.063.

屬性體育成績的信息增益率為：

GainRatio(TY)=Gain(TY)/E(S1，S2，S3，S4)=0.055.

同理,得到屬性德育成績和平均績點的信息增益律分別為：

GainRatio(DY)=0.051，GainRatio(PJ)=0.039.

圖1 C4.5算法構造獎學金評定決策樹Fig.1 C4.5 algorithm structured scholarship assessment decision tree

由于屬性體育成績具有最大的信息增益率值，故選擇該屬性作為決策樹的根節(jié)點.對于每一個分支，重復上述步驟生成決策樹,如圖1所示.因篇幅有限，只畫出第一層次單位的決策樹.

2.3 分類規(guī)則提取

從決策樹中提取一等、二等、三等類的規(guī)則，分類規(guī)則如下：

(1)if體育成績=“合格” and 德育成績=“A” and 平均績點>=3.35 then 一等獎學金；

(2)if體育成績=“合格” and 德育成績=“A” and平均績點>=3.10 then 二等獎學金；

(3)if體育成績=“合格” and 德育成績=“B” and平均績點>=2.29 then 三等獎學金.

由以上規(guī)則可以看出，學生要想獲得獎學金，必須要按時參加體育鍛煉，同時要積極地參加學校的活動以提高自己的德育分，還要努力學習提高自己的專業(yè)課成績[8].

3 結束語

在目前以手工方式進行獎學金評定的低效率的情況下，提出了關于獎學金評定的數(shù)據(jù)挖掘模型，引入了數(shù)據(jù)挖掘理論中的決策樹算法，對高校獎學金評定系統(tǒng)中的數(shù)據(jù)進行了分析.實驗表明，此數(shù)據(jù)挖掘算法構造簡單，能正確分類，處理速度較快.

參考文獻：

[1] 顧曉春.高校獎學金評定系統(tǒng)的設計研究[D].大連：大連理工大學，2008．

[2] 吳陳,林炎鐘.C4.5算法在高校教師評價中的應用研究[J].信息技術，2010(1)：17-19．

[3] 云玉屏,林克正.C4.5算法在冠狀造影數(shù)據(jù)處理中的應用[J].計算機工程與應用，2008，44(10)：25-27．

[4] 宋暉,張良均.C4.5決策樹法在空氣質(zhì)量評價中的應用[J].科學技術與工程，2011(7)：16-18．

[5] 鄒競,謝鯤.C4.5 算法在移動通信行業(yè)客戶流失分析中的應用[J].計算機技術與自動化，2009(9)：33-35．

[6] David B.Style System Overview[DB/OL].http: / /www.mozilla.org /newlayout /doc /style- techtalk.html, 2002-06.

[7] 邵興江.數(shù)據(jù)挖掘在教育信息化中的應用空間分析[EB/OL] .http:// www. Zjedu.org/ xdjyjs/ 107/64781thm，2008-01-08.

[8] 李楠,段隆振,陳萌.決策樹C4.5算法在數(shù)據(jù)挖掘中的分析及其應用[J].計算機與現(xiàn)代化，2008(12)：160-163．