韋金日　李雪萍

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

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

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

[中圖分類號] G64 [文獻標識碼] A [文章編號] 1007-7723（2013）05-0073-0003

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

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

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

一、決策樹算法

決策樹是一種基本的分類方法，決策樹模型呈樹形結構，在分類問題中，表示基于特征對實例進行分類的過程[4]。

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

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

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

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

（一）信息增益

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

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

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

若屬性A有互不相同的v個值a■，a■，…a■，根據(jù)屬性A將S劃分為v個子集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)生劃分的熵由下式計算：

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

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

利用屬性A對當前分支結點進行樣本集合劃分所獲得的信息增益為：

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

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

（二）信息增益率

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

Split（A）=-■■log■■

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

GainRatio（A）=■

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

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

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

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

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

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

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

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

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

三、結果分析

（一）實驗環(huá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ù)來源于學校學生管理信息系統(tǒng)中的實際數(shù)據(jù)，由于某些數(shù)據(jù)對我們的目標沒有幫助，所以在實驗前必須對所需數(shù)據(jù)進行歸納整理。選取的數(shù)據(jù)集中含有三年的數(shù)據(jù)，因此將前兩年的數(shù)據(jù)作為訓練數(shù)據(jù)，第三年的數(shù)據(jù)作為預測數(shù)據(jù)?？偣驳臉颖敬笮∈?598，其中訓練集大小是6308，測試集大小是3295。

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

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

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

（三）實驗結果

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

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

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

四、結 論

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

[參考文獻]

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

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

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

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

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

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