馬偉杰

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

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

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

1 C4. 5決策樹算法

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

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

(1)

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

(2)

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

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

(3)

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

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

(4)

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

/*參數(shù)：R表示判定對(duì)象屬性，C表示目標(biāo)屬性，S表示訓(xùn)練集*/

DecisionTree C45(R,C,S)

{

if(S為空) return NULL；

if(S包含目標(biāo)屬性的值都相同) return 具有該值的結(jié)點(diǎn)；

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

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

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

{s[j]|j=1，2，…，m}為與S相對(duì)應(yīng)的包含屬性D相應(yīng)取值d[j]的訓(xùn)練集；

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

/*遞歸得到包含屬性D相應(yīng)取值d[j]的各個(gè)子決策樹*/

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

}

2 C4. 5算法在高校獎(jiǎng)學(xué)金評(píng)定中的應(yīng)用

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

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

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

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

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

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

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

2.2 構(gòu)造決策樹

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

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

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

然后計(jì)算每一個(gè)決策屬性的期望信息熵.

對(duì)屬性體育成績(jī)，當(dāng)體育成績(jī)=“合格”時(shí)：

當(dāng)體育成績(jī)=“不合格”時(shí)：

由此，得出體育成績(jī)的熵值為:

因此,體育成績(jī)的信息增益為：

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

屬性體育成績(jī)的信息增益率為：

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

同理,得到屬性德育成績(jī)和平均績(jī)點(diǎn)的信息增益律分別為：

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

圖1 C4.5算法構(gòu)造獎(jiǎng)學(xué)金評(píng)定決策樹Fig.1 C4.5 algorithm structured scholarship assessment decision tree

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

2.3 分類規(guī)則提取

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

(1)if體育成績(jī)=“合格” and 德育成績(jī)=“A” and 平均績(jī)點(diǎn)>=3.35 then 一等獎(jiǎng)學(xué)金；

(2)if體育成績(jī)=“合格” and 德育成績(jī)=“A” and平均績(jī)點(diǎn)>=3.10 then 二等獎(jiǎng)學(xué)金；

(3)if體育成績(jī)=“合格” and 德育成績(jī)=“B” and平均績(jī)點(diǎn)>=2.29 then 三等獎(jiǎng)學(xué)金.

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

3 結(jié)束語

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

參考文獻(xiàn)：

[1] 顧曉春.高校獎(jiǎng)學(xué)金評(píng)定系統(tǒng)的設(shè)計(jì)研究[D].大連：大連理工大學(xué)，2008．

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

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

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

[5] 鄒競(jìng),謝鯤.C4.5 算法在移動(dòng)通信行業(yè)客戶流失分析中的應(yīng)用[J].計(jì)算機(jī)技術(shù)與自動(dòng)化，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ù)挖掘在教育信息化中的應(yīng)用空間分析[EB/OL] .http:// www. Zjedu.org/ xdjyjs/ 107/64781thm，2008-01-08.

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