賀愛(ài)香，袁雪松

（1.安徽新華學(xué)院，合肥 230088；2.安徽合力股份有限公司，合肥 230601）

C4.5決策樹(shù)算法在應(yīng)用型本科高校就業(yè)管理中的應(yīng)用研究

賀愛(ài)香1，袁雪松2

（1.安徽新華學(xué)院，合肥 230088；2.安徽合力股份有限公司，合肥 230601）

將數(shù)據(jù)挖掘中的C4.5算法應(yīng)用于應(yīng)用型本科院校的就業(yè)管理信息系統(tǒng)中，有利于發(fā)掘出應(yīng)用型畢業(yè)生就業(yè)中隱藏的有用因素和內(nèi)在聯(lián)系，對(duì)促進(jìn)學(xué)校進(jìn)行教學(xué)改革，指導(dǎo)學(xué)生提高自身素質(zhì)和知識(shí)結(jié)構(gòu)，從而最大程度的提高畢業(yè)生的就業(yè)率。

數(shù)據(jù)挖掘；決策樹(shù)；C4.5算法；應(yīng)用型本科；就業(yè)

數(shù)據(jù)挖掘（Data Mining，DM）來(lái)源于數(shù)據(jù)庫(kù)中的知識(shí)發(fā)現(xiàn)（Knowledge Discovery in Database，KDD），它是一門(mén)綜合性學(xué)科，涉及很多的學(xué)科領(lǐng)域，其中包括了數(shù)據(jù)庫(kù)技術(shù)、人工智能、統(tǒng)計(jì)分析、機(jī)器學(xué)習(xí)、模糊數(shù)學(xué)等多個(gè)領(lǐng)域的理論和技術(shù)［1］。而決策樹(shù)分類(lèi)法就是從機(jī)器學(xué)習(xí)中引出的一種很實(shí)用的非參數(shù)型歸納學(xué)習(xí)技術(shù)，適用于數(shù)據(jù)集較小的情況，它將實(shí)例為基礎(chǔ)進(jìn)行歸納，把從海量數(shù)據(jù)中提取出來(lái)的信息，用樹(shù)狀結(jié)構(gòu)的形式進(jìn)行分類(lèi)［2］。在本文中，以安徽新華學(xué)院2011屆安徽新華學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)專(zhuān)業(yè)就業(yè)情況作為實(shí)例數(shù)據(jù)，運(yùn)用決策樹(shù)分類(lèi)法中典型的C4.5算法，實(shí)現(xiàn)了應(yīng)用型高等院校畢業(yè)生就業(yè)模型。

1 決策樹(shù)算法的描述

決策樹(shù) （Decision Tree）是分類(lèi)和預(yù)測(cè)的挖掘方法中應(yīng)用較為廣泛的模式之一，是一種由內(nèi)部結(jié)點(diǎn)、分叉及葉結(jié)點(diǎn)構(gòu)成的，用來(lái)表示決策規(guī)則的樹(shù)結(jié)構(gòu)，其中，內(nèi)部結(jié)點(diǎn)表示某種檢驗(yàn)屬性，分叉表示檢驗(yàn)的結(jié)果，葉結(jié)點(diǎn)表示類(lèi)或某一類(lèi)的分類(lèi)，而頂點(diǎn)稱為根結(jié)點(diǎn)［3］。在構(gòu)建的決策樹(shù)中，從根節(jié)點(diǎn)到葉結(jié)點(diǎn)的一條路徑就對(duì)應(yīng)著一條分類(lèi)規(guī)則，其構(gòu)建的過(guò)程，取決于檢驗(yàn)屬性的選擇以及分叉點(diǎn)的確定。不同的決策樹(shù)算法采用的屬性分割方法不同，常用的決策樹(shù)算法主要有：ID3，C4.5，SLIQ，SPRINT，RainForest， CLS， CHAID， CART， FACT， GINT，SEE5等［3］。

2 C4.5算法的描述

香農(nóng)（C.E.Shannon）在信息論中對(duì)信息量（Information）和熵（Entropy）有明確定義：

C4.5算法就是結(jié)點(diǎn)上最大程度的壓縮熵，使所含的信息熵最小化；與著名的ID3算法相比，在作為度量標(biāo)準(zhǔn)的屬性選擇上，C4.5算法采用的信息增益率比ID3算法采用的信息增益要更好［4］。決策屬性信息增益率的計(jì)算通過(guò)以下步驟實(shí)現(xiàn)：

設(shè)S是訓(xùn)練樣本數(shù)據(jù)集，S中類(lèi)別標(biāo)識(shí)屬性有m個(gè)獨(dú)立的取值，也就是說(shuō)定義了m個(gè)類(lèi)ci，i＝1，2，…，m；Ri為數(shù)據(jù)集S中屬于ci類(lèi)的子集，用ri表示子集Ri中元組的數(shù)量［5］。

集合S在分類(lèi)中的期望信息量可以由以下公式給出

式中：pi表示任意樣本屬于ci類(lèi)的概率；pi＝ri／｜S｜，｜S｜為訓(xùn)練樣本數(shù)據(jù)集中的元組數(shù)量。

假設(shè)屬性A共有υ個(gè)不同的取值｛a1，a2，…，aυ｝，則通過(guò)屬性A的取值可將數(shù)據(jù)集S劃分為υ個(gè)子集，其中，Sj表示在數(shù)據(jù)集S中屬性A的取值為aj的子集，j＝1，2，…，υ［6］。

如果A被選為決策屬性，則這些子集將對(duì)應(yīng)該節(jié)點(diǎn)的不同分枝。

如果sij表示Sj子集中屬于ci類(lèi)的元組的數(shù)量，則屬性A對(duì)于分類(lèi)ci（i＝1，2，…，m）的熵可由下式計(jì)算。

屬性A的每個(gè)取值對(duì)分類(lèi)cj的期望信息量I（s1j，…，smj），可由下式給出

式中：pi＝sij／｜Sj｜，它表示在Sj子集中屬于ci類(lèi)的比重。

由此可得到對(duì)屬性A作為決策分類(lèi)屬性的度量值（稱為信息增益）為

信息增益率為

3 根據(jù)C4.5算法構(gòu)建決策樹(shù)

在本文中，我們選取了83名本科畢業(yè)生的就業(yè)信息作為樣本集，將其中73份調(diào)查表作為訓(xùn)練數(shù)據(jù)集，另外10份是測(cè)試數(shù)據(jù)集。這份就業(yè)信息表是由畢業(yè)生的基本信息表、成績(jī)信息表、就業(yè)信息表等通過(guò)預(yù)處理后匯總而成，如表1所示，表中“就業(yè)情況”是類(lèi)別標(biāo)識(shí)屬性，而與就業(yè)相關(guān)的特征屬性，如 “實(shí)踐能力”、“專(zhuān)業(yè)課成績(jī)”、“性別”、“英語(yǔ)水平”、“計(jì)算機(jī)水平”則作為決策屬性。

為方便進(jìn)行算法分析和描述，我們分別對(duì)對(duì)這些屬性進(jìn)行泛化。單位性質(zhì)分為三種：國(guó)企（A）、外企（B）和私企（C）；單位好壞分為兩類(lèi)：效益好（1）和效益差（2）。這樣我們就可以把畢業(yè)生的就業(yè)單位分成了六個(gè)檔次：好國(guó)企（A1）、差國(guó)企（A2）、好外企（Bl）、差外企（B2）、好私企（Cl）、差私企（C2）。在這里我們將政府部門(mén)、事業(yè)單位和國(guó)家控股企業(yè)等劃分分為國(guó)企，合資和外商獨(dú)資企業(yè)等我們劃為外企、民營(yíng)和鄉(xiāng)鎮(zhèn)企業(yè)等我們劃為私企。

實(shí)踐能力分為：“優(yōu)”、“良”、“差”三類(lèi)，專(zhuān)業(yè)課成績(jī)?nèi)〉氖菍W(xué)生專(zhuān)業(yè)課成績(jī)的平均數(shù)，一百分為滿分，其泛化為三類(lèi)：優(yōu)（平均成績(jī)≥80分）、良（60分≦平均成績(jī)＜80分）、差（平均成績(jī)＜60分），性別分為“男”、“女”兩種人，英語(yǔ)水平分為兩類(lèi)：優(yōu)（六級(jí)以上或者有口語(yǔ)證等）、一般（四級(jí)及四級(jí)以下），計(jì)算機(jī)水平分為兩類(lèi)：優(yōu)（三級(jí)及三級(jí)以上）、一般（二級(jí)以下）。通過(guò)這些屬性泛化，我們得到泛化后的“2011年計(jì)算機(jī)科學(xué)與技術(shù)專(zhuān)業(yè)就業(yè)信息表”，如表1所示。

表1 2011年計(jì)算機(jī)科學(xué)與技術(shù)專(zhuān)業(yè)就業(yè)信息表

為了方便計(jì)算和構(gòu)建決策樹(shù)，我們將抽取的73份就業(yè)信息作為樣本集S，根據(jù)標(biāo)識(shí)屬性和決策屬性進(jìn)行統(tǒng)計(jì)分類(lèi)，得到表2的樣本集統(tǒng)計(jì)分析表。

這73個(gè)元組，其中A1、A2、B1、B2、C1、C2分別對(duì)應(yīng)的子集元組數(shù)，統(tǒng)計(jì)后記錄r1＝6、r2＝8、r3＝7、r4＝12、r5＝11、r6＝29。根據(jù)公式，首先需要計(jì)算集合S的期望信息量：

表2 就業(yè)信息樣本集統(tǒng)計(jì)分析表

在對(duì)每一個(gè)決策屬性計(jì)算期望信息量（既熵值）

對(duì)屬性“實(shí)踐能力”，當(dāng)實(shí)踐能力為“優(yōu)”時(shí)

當(dāng)實(shí)踐能力為“良”時(shí)

當(dāng)實(shí)踐能力為“差”時(shí)

所以“實(shí)踐能力”的熵值為：

因此屬性“實(shí)踐能力”的信息增益是：

屬性“實(shí)踐能力”的分裂信息是：SplitI（實(shí)踐能力）

因此屬性“實(shí)踐能力”的信息增益率是

Ratio（實(shí)踐能力）＝ Gain（實(shí)踐能力）／SplitI（實(shí)踐能力）＝0.445744

同理我們可以計(jì)算出屬性“專(zhuān)業(yè)課成績(jī)”“性別”“英語(yǔ)水平”“計(jì)算機(jī)水平”的信息增益：Ratio（專(zhuān)業(yè)課成績(jī)）＝0.260208，Ratio（性別）＝0.015839，Ratio（英語(yǔ)水平）＝0.388886，Ratio（計(jì)算機(jī)水平）＝0.380068。

由此可見(jiàn)，具有最大增益率的屬性是“實(shí)踐能力”，所以將它作為決策樹(shù)的根結(jié)點(diǎn)。對(duì)于每個(gè)分支，將剩下的屬性重新列表，重復(fù)上述步驟，生成決策樹(shù)。

圖1 C4.5算法構(gòu)造的就業(yè)決策樹(shù)

4 分類(lèi)規(guī)則描述

根據(jù)決策樹(shù)可以提取出分類(lèi)規(guī)則，規(guī)則如下：

1）IF實(shí)踐能力＝優(yōu)＋專(zhuān)業(yè)課成績(jī)＝優(yōu)THEN在好外企就業(yè)；

2）IF實(shí)踐能力＝優(yōu)＋專(zhuān)業(yè)課成績(jī)＝優(yōu)THEN在好私企就業(yè)；

3）IF實(shí)踐能力＝優(yōu)＋專(zhuān)業(yè)課成績(jī)＝良＋英語(yǔ)水平＝優(yōu)THEN在好外企就業(yè)；……

得出上述26條規(guī)則后，將10份測(cè)試數(shù)據(jù)帶入測(cè)試，正確率是90%，可見(jiàn)，分類(lèi)預(yù)測(cè)準(zhǔn)確性較高，同時(shí)，從以上結(jié)果中看出，提高應(yīng)用型本科院校的就業(yè)層次，實(shí)踐能力的培養(yǎng)是最重要的，其次是英語(yǔ)水平、計(jì)算機(jī)水平等。例如，實(shí)踐能力優(yōu)的學(xué)生，就業(yè)層次可選性較寬；如果只是英語(yǔ)水平優(yōu)的學(xué)生，進(jìn)入外企的可能性較大；如果英語(yǔ)水平和計(jì)算機(jī)水平都一般的，可能就要先就業(yè)再擇業(yè)了。

5 結(jié)束語(yǔ)

本文展示了決策樹(shù)在應(yīng)用型本科院校畢業(yè)生就業(yè)信息中的應(yīng)用，挖掘出對(duì)就業(yè)具有指導(dǎo)性的潛在規(guī)律，實(shí)用性很強(qiáng)，對(duì)學(xué)生就業(yè)時(shí)的自我定位，以及學(xué)校領(lǐng)導(dǎo)在提高就業(yè)率、提高就業(yè)層次、改進(jìn)現(xiàn)在實(shí)行的培養(yǎng)機(jī)制等方面提供決策支持。

［1］邵峰晶，于忠清，汪金龍.數(shù)據(jù)挖掘原理與算法［M］（第2版）.北京：科技出版社，2009.

［2］Jiawei Han，Micheline Kamber，著.數(shù)據(jù)挖掘概念與技術(shù)［M］.范明，孟小峰，譯.北京：機(jī)械工業(yè)出版社，2007.

［3］紀(jì)希禹.數(shù)據(jù)挖掘技術(shù)應(yīng)用實(shí)例［M］.北京：機(jī)械工業(yè)出版社，2009.

［4］劉美玲，李 熹，李永勝.數(shù)據(jù)挖掘技術(shù)在高校教學(xué)與管理中的應(yīng)用［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2010（5）：1130－1133.

［5］吳 陳，林炎鐘.C4.5算法在高校教師評(píng)價(jià)中的應(yīng)用研究［J］.信息技術(shù)，2011（1）：133－136.

［6］黃海霞，徐相林.基于C4.5算法的學(xué)生成績(jī)的研究與分析［J］.電腦知識(shí)與技術(shù)，2011（14）：3405－3409.

［7］許旌瑩.決策樹(shù)算法在圖書(shū)館個(gè)性化服務(wù)中的應(yīng)用研究［J］.科技信息，2011，（14）：114－115.

［8］黃愛(ài)輝.決策樹(shù)C4.5算法的改進(jìn)及應(yīng)用［J］.科學(xué)技術(shù)與工程，2009（1）：34－36，42.

The Application of C4.5 Decision Tree Algorithm in the Employment Management for University Graduates

He Aixiang， Yuan Xuesong

By applying C4.5decision tree algorithm in the employment management for University Graduates，it will benefit to find out some hidden useful factors and interior relations in the employment of applied graduates，which may boost universities to innovate education，and guide students to improve self－quality and knowledge structure so that the employment rate of graduates will be increased.

data mining；decision tree；C4.5arithmetic；application－oriented university；employment

TP311

A

1673-1794（2012）05-0062-03

賀愛(ài)香（1978－），女，安徽宿松人，碩士，講師，研究方向：數(shù)據(jù)挖掘；袁雪松（1978－），男，安徽巢湖人，碩士，助理工程師，研究方向：控制工程。

2012-05-11