基于K近鄰相似的決策樹算法在學(xué)生就業(yè)管理中的應(yīng)用

韋金日　李雪萍

[摘 要] 由于現(xiàn)在的就業(yè)形勢越來越嚴(yán)峻，就業(yè)壓力越來越大，因此需要學(xué)校對大量歷屆學(xué)生就業(yè)的歷史數(shù)據(jù)進(jìn)行挖掘，發(fā)現(xiàn)內(nèi)在的規(guī)律和聯(lián)系，為就業(yè)指導(dǎo)提供決策依據(jù)，對學(xué)生做出針對性的指導(dǎo)，以提高學(xué)生的就業(yè)率和就業(yè)質(zhì)量。文章基于K近鄰相似的決策樹算法可以較好地根據(jù)學(xué)生的基本信息進(jìn)行挖掘，對學(xué)生潛在的工作做出預(yù)測，使不同的學(xué)生可以根據(jù)自己的情況對工作進(jìn)行針對性的準(zhǔn)備，從而可以更好的就業(yè)。

[關(guān)鍵詞] 決策樹；K近鄰；就業(yè)管理；就業(yè)預(yù)測

[作者簡介] 韋金日， 廣西工業(yè)職業(yè)技術(shù)學(xué)院講師，廣西大學(xué)計(jì)算機(jī)與電子信息學(xué)院在職研究生學(xué)歷，研究方向：計(jì)算機(jī)網(wǎng)絡(luò)與并行分布式計(jì)算，廣西 南寧，530003；李雪萍，廣西工業(yè)職業(yè)技術(shù)學(xué)院講師，碩士研究生，研究方向：網(wǎng)絡(luò)與并行計(jì)算，廣西 南寧，530003

[中圖分類號] G64 [文獻(xiàn)標(biāo)識碼] A [文章編號] 1007-7723（2013）05-0073-0003

隨著我國高等教育由精英教育向大眾教育的轉(zhuǎn)變，高等學(xué)校的招生規(guī)模不斷擴(kuò)大，各高校紛紛開始利用信息化手段對教學(xué)、就業(yè)工作進(jìn)行管理，并收到良好的效果。但是，由于招生人數(shù)的擴(kuò)大使得學(xué)生信息系統(tǒng)數(shù)據(jù)庫存儲(chǔ)的數(shù)據(jù)量急劇擴(kuò)增，面對巨大的數(shù)據(jù)集合，傳統(tǒng)的數(shù)據(jù)分析手段已經(jīng)日漸力不從心。這是因?yàn)閭鹘y(tǒng)的信息系統(tǒng)是基于查詢的，數(shù)據(jù)庫可以很好地實(shí)現(xiàn)對數(shù)據(jù)的存儲(chǔ)和查詢等功能，但是這些數(shù)據(jù)之間的內(nèi)在關(guān)系和隱含的有用信息無法被獲取，數(shù)據(jù)中存在的關(guān)系和規(guī)則無法被發(fā)現(xiàn)，無法利用現(xiàn)在的數(shù)據(jù)預(yù)測未來的發(fā)展趨勢，缺乏挖掘數(shù)據(jù)背后隱藏知識的手 段[1]。

數(shù)據(jù)挖掘技術(shù)就是從大量的、不完全的、有噪聲的、模糊的、隨機(jī)的數(shù)據(jù)中，提取隱含在其中的、人們事先未知的但又是潛在有用的信息和知識的過程[2]。對于存在著的龐大的歷史信息，可以使用數(shù)據(jù)挖掘技術(shù)挖掘出畢業(yè)生就業(yè)信息中隱藏的有用因素和內(nèi)在聯(lián)系，從而促進(jìn)學(xué)校進(jìn)行教學(xué)改革，指導(dǎo)學(xué)生提高自身素質(zhì)和知識結(jié)構(gòu)，從而最大程度地提高畢業(yè)生的就業(yè)率和就業(yè)質(zhì)量[3]。

本文將以從某高校學(xué)生管理信息系統(tǒng)中獲取的實(shí)際數(shù)據(jù)作為樣本數(shù)據(jù)集，利用K近鄰相似的決策樹算法進(jìn)行挖掘和分析，從而預(yù)測出學(xué)生可能的就業(yè)情況。

一、決策樹算法

決策樹是一種基本的分類方法，決策樹模型呈樹形結(jié)構(gòu)，在分類問題中，表示基于特征對實(shí)例進(jìn)行分類的過程[4]。

決策樹的建樹過程是從根節(jié)點(diǎn)開始，對每個(gè)非葉子節(jié)點(diǎn)，找出其對應(yīng)樣本集中的一個(gè)屬性，稱為測試屬性，對樣本集進(jìn)行測試，根據(jù)不同的測試結(jié)果將訓(xùn)練樣本集劃分成若干個(gè)子樣本集，每個(gè)子樣本集構(gòu)成一個(gè)新葉節(jié)點(diǎn)，對新葉節(jié)點(diǎn)再重復(fù)上述劃分過程，這樣不斷循環(huán)，直至達(dá)到特定的終止條件。其中，測試屬性的選擇和如何劃分樣本集是構(gòu)建決策樹的關(guān)鍵環(huán)節(jié)。不同的決策樹算法使用不同的技術(shù)。從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的路徑描述了各種分類規(guī)則，可以認(rèn)為是if-then規(guī)則的集合。因此，決策樹模型具有良好的可讀性且分類速度快，是一種簡單易行的分類方法[5]。

決策樹學(xué)習(xí)通常包括三個(gè)步驟：特征選擇、決策樹的生成和決策樹的剪枝。根據(jù)屬性選擇度量方法的不同，可以給出不同的決策樹算法。建樹的過程通常分為兩個(gè)階段：建樹階段和剪枝階段。修剪按其進(jìn)行的時(shí)間順序可分為先剪枝和后剪枝。先剪枝是在決策樹的構(gòu)建過程中利用一定的技術(shù)進(jìn)行判斷，比如可以設(shè)置一定的閥值，若可能生成異常分枝，則停止此分枝的生成，即將此生成的分枝剪去；后剪枝則是待決策樹完全生成后，運(yùn)用特定的剪枝算法對整棵樹進(jìn)行修剪。

構(gòu)建決策樹模型大致可以分為兩步，第一步是利用訓(xùn)練集建立決策樹模型。這個(gè)過程實(shí)際上是一個(gè)從訓(xùn)練集中獲取知識，進(jìn)行機(jī)器學(xué)習(xí)的過程。第二步是利用生成的決策樹對輸入數(shù)據(jù)進(jìn)行分類。對輸入的紀(jì)錄，從根節(jié)點(diǎn)依次測試記錄的屬性值，直到到達(dá)某個(gè)葉子節(jié)點(diǎn)，從而找到該記錄所屬的類。

常用的屬性選擇度量有：信息增益、信息增益率和Gini指標(biāo)。信息增益來自于信息論中的概念，表示已知特征的信息使得類的信息不確定性減小的程度[6]。

（一）信息增益

設(shè)數(shù)據(jù)集S包含n個(gè)數(shù)據(jù)樣本，類別集合為 C■，C■…，C■。記Si為類別Ci中的樣本個(gè)數(shù)，顯然有■S■=n 。對一個(gè)給定數(shù)據(jù)對象進(jìn)行分類的期望信息為：

I（s■，s■，…s■）=-■p■log■（p■）

其中p■是類別Ci發(fā)生的概率，可以由式子Si/n估計(jì)。

若屬性A有互不相同的v個(gè)值a■，a■，…a■，根據(jù)屬性A將S劃分為v個(gè)子集S■，S■，…S■ ，Sj中數(shù)據(jù)樣本取值均為aj，記Sj的樣本數(shù)為Sj=n■，則S■（a■）的發(fā)生概率為nj/n。記子集S■中屬于Ci類的樣本數(shù)為S■，則集合S■中具有類別Ci的條件概率為Sij/n。如果A被選做測試屬性，根據(jù)A產(chǎn)生劃分的熵由下式計(jì)算：

E（A）=■■I（S■，…，S■）=■■n■I（S■，…，S■）

其中I（S■，…，S■）=-■P■log■■（P■） =-■■log■■。

利用屬性A對當(dāng)前分支結(jié)點(diǎn)進(jìn)行樣本集合劃分所獲得的信息增益為：

Gain（A）=I（S■，S■，…，S■）-E（A）

本文選擇具有最高信息增益Gain（A）的屬性A作為節(jié)點(diǎn)的分裂屬性。

（二）信息增益率

信息增益率是在信息增益的基礎(chǔ)上，引入屬性 的信息熵Split（A）：

Split（A）=-■■log■■

并定義屬性的信息增益率為：

GainRatio（A）=■

本文選擇具有最大信息增益率GainRatio（A）的屬性A作為節(jié)點(diǎn)的分裂屬性。

信息增益偏向于多值屬性，信息增益率在此基礎(chǔ)上調(diào)整了多值屬性，但是傾向于不平衡的分裂，而Gini指標(biāo)不僅偏向于多值屬性，而且當(dāng)類的數(shù)量很大時(shí)會(huì)有困難，并且還傾向于導(dǎo)致相等大小的劃分和純度?？紤]到數(shù)據(jù)集的實(shí)際情況，本文采用信息增益率作為屬性度量選擇方法。

二、K近鄰相似的決策樹算法

（一）數(shù)據(jù)的預(yù)處理

在數(shù)據(jù)挖掘中，數(shù)據(jù)集的數(shù)據(jù)好壞對最后的結(jié)果有很大的影響，因此很大的一部分精力都要用于數(shù)據(jù)的預(yù)處理。從數(shù)據(jù)庫中導(dǎo)出的原始數(shù)據(jù)有62個(gè)維度，這其中有很多的維度與我們最終要分析的結(jié)果無關(guān)，為了不讓這些數(shù)據(jù)影響到最終處理結(jié)果，因此要手動(dòng)進(jìn)行降維，最后要分析的維度為30個(gè)維度。其中的類標(biāo)識是就業(yè)單位性質(zhì)，為了進(jìn)行數(shù)據(jù)的處理，將這些不同的類別分別用數(shù)字表示，總共有九個(gè)類別，分別是無業(yè)、自主創(chuàng)業(yè)、營企業(yè)、國有企業(yè)、讀書深造、公務(wù)員、部隊(duì)、事業(yè)單位與合資企業(yè)，分別對應(yīng)著0～8這八個(gè)數(shù)字。

由于選擇的剩余29個(gè)維度都是分類屬性的數(shù)據(jù)，因此不需要進(jìn)行數(shù)據(jù)的離散化，但是需要對這些數(shù)據(jù)進(jìn)行數(shù)值化的處理，每個(gè)屬性的值為P■（i=1...n），其中n是每個(gè)屬性含有的不同的分類屬性值。

（二）K近鄰相似的決策樹算法

數(shù)據(jù)集中有一些缺失的數(shù)據(jù)，因此需要對這些缺失數(shù)據(jù)進(jìn)行填充，通常處理缺失數(shù)據(jù)的方式是設(shè)定一些默認(rèn)值或者取某個(gè)屬性的眾數(shù)，但是這樣會(huì)造成最終數(shù)據(jù)的失真率比較高，因此本文采用一種近鄰填充缺失值的方法：對于特征空間中的每個(gè)訓(xùn)練實(shí)例xi，距離該點(diǎn)比其他點(diǎn)更近的所有點(diǎn)組成一個(gè)區(qū)域，叫作單元。每個(gè)訓(xùn)練實(shí)例點(diǎn)擁有一個(gè)單元，所有訓(xùn)練實(shí)例點(diǎn)的單元構(gòu)成特征空間的一個(gè)劃分。最近鄰法將實(shí)例xi的類yi作為其單元中所有點(diǎn)的類標(biāo)記，其中每個(gè)區(qū)域中有k個(gè)實(shí)例。

采用余弦相似函數(shù)作為兩個(gè)不同實(shí)例的距離度量，將每個(gè)實(shí)例看作是一個(gè)向量，將每個(gè)屬性的值看作向量的一個(gè)元素，兩個(gè)向量分別記作X和Y，X和Y的距離為 ，其中 和 分別是向量X和Y的范數(shù)，取與每個(gè)向量最接近的k個(gè)向量，本文中k設(shè)為100，對缺失值做以下的處理：找出k個(gè)向量中當(dāng)前屬性下有值的n個(gè)向量，缺失值填充為這n個(gè)向量當(dāng)前屬性的和的n分之一。當(dāng)填充完所有的缺失值之后，就進(jìn)行決策樹的構(gòu)建。采用經(jīng)典的C4.5算法來構(gòu)建決策樹，并通過信息增益率進(jìn)行每次的分裂屬性選擇。

三、結(jié)果分析

（一）實(shí)驗(yàn)環(huán)境及軟件

本文的實(shí)驗(yàn)環(huán)境如下：Intel（R） Core（TM） i7 CPU，4G內(nèi)存，500G硬盤；開發(fā)語言為Java，環(huán)境為JDK 1.6，編程工具為Eclipse；所用數(shù)據(jù)庫為：MySQL 5.5.10。

（二）數(shù)據(jù)屬性和數(shù)據(jù)集

數(shù)據(jù)來源于學(xué)校學(xué)生管理信息系統(tǒng)中的實(shí)際數(shù)據(jù)，由于某些數(shù)據(jù)對我們的目標(biāo)沒有幫助，所以在實(shí)驗(yàn)前必須對所需數(shù)據(jù)進(jìn)行歸納整理。選取的數(shù)據(jù)集中含有三年的數(shù)據(jù)，因此將前兩年的數(shù)據(jù)作為訓(xùn)練數(shù)據(jù)，第三年的數(shù)據(jù)作為預(yù)測數(shù)據(jù)。總共的樣本大小是9598，其中訓(xùn)練集大小是6308，測試集大小是3295。

樣本的維度總共有25個(gè)，分別是學(xué)號、入學(xué)時(shí)間、畢業(yè)時(shí)間、性別、民族、政治面貌、考生類別、生源地、系部名稱、班級、專業(yè)方向、家庭經(jīng)濟(jì)情況、個(gè)人身高、個(gè)人特長、在校任職、所獲獎(jiǎng)勵(lì)、能力證書、就業(yè)意向、意向月薪、學(xué)籍變動(dòng)、就業(yè)時(shí)間、就業(yè)形式、就業(yè)區(qū)域、派遣單位名稱和就業(yè)單位性質(zhì)。

其中的個(gè)人身高需要進(jìn)行離散化的處理，將具體的身高劃分為150～155、156～160、161～165、166～170、171～175、176～180以及180以上這七個(gè)類別，由于其中有些數(shù)據(jù)在統(tǒng)計(jì)時(shí)缺失了，因此使用本文提出的K近鄰相似進(jìn)行缺失值的填充。對于就業(yè)意向和意向月薪也進(jìn)行類似的處理。

通過程序分別計(jì)算每個(gè)屬性的信息增益率，由每個(gè)屬性的信息增益率大小可知，專業(yè)方向的信息增益率最大，從而將專業(yè)方向作為決策樹的根節(jié)點(diǎn)。分別進(jìn)行迭代計(jì)算可以構(gòu)建出整個(gè)決策樹。

（三）實(shí)驗(yàn)結(jié)果

通過采用眾數(shù)進(jìn)行缺失值填充和采用最近鄰法進(jìn)行填充的預(yù)測效果進(jìn)行比較，如表所示：

通過數(shù)據(jù)可以發(fā)現(xiàn)，使用了最近鄰填充缺失數(shù)據(jù)的方法精度有了比較大的提高，因此證明本方法是切實(shí)有效的。

不過，由于進(jìn)行k近鄰比較的時(shí)候需要兩層掃描訓(xùn)練集，其復(fù)雜度達(dá)到了O（n■） ，因此需要借助于MapReduce進(jìn)行并行化的操作。

四、結(jié) 論

在目前就業(yè)形勢嚴(yán)峻的環(huán)境下，本文將K近鄰相似的決策樹算法應(yīng)用于高校就業(yè)，挖掘?qū)W生數(shù)據(jù)與就業(yè)有關(guān)的關(guān)系，為就業(yè)指導(dǎo)提供決策依據(jù)。利用這些預(yù)測信息，學(xué)生可以合理規(guī)劃就業(yè)方向，學(xué)校就業(yè)指導(dǎo)者可以在畢業(yè)生就業(yè)宣傳，就業(yè)計(jì)劃投放等方面做出正確的決策，提高學(xué)生的就業(yè)率、增強(qiáng)學(xué)校競爭力。

[參考文獻(xiàn)]

[1]金瑩.決策樹算法在高校學(xué)生就業(yè)中的應(yīng)用研究[D].合肥工業(yè)大學(xué)計(jì)算機(jī)與信息學(xué)院，2009.

[2]張嘉贏.基于數(shù)據(jù)挖掘技術(shù)的高校畢業(yè)生就業(yè)管理信息系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[D].東北大學(xué)信息科學(xué)與工程學(xué)院，2009.

[3]賀愛香，袁雪松.C4.5決策樹算法在應(yīng)用型本科高校就業(yè)管理中的應(yīng)用研究[J].滁州學(xué)院學(xué)報(bào)，2012，14（5）.

[4]李航.統(tǒng)計(jì)學(xué)習(xí)方法[M].北京：清華大學(xué)出版社，2012.

[5]Jiawei Han， Micheline Kamber. Data Mining Concepts and Techniques， Second Edition[M].范明，孟小峰，譯.北京：機(jī)械工業(yè)出版社，2007.

[6]S. B. Kotsiantis. Decision trees： a recent overview[J]. Artificial Intelligence Review， 2013， 39， 261-283.