基于多尺度粗糙集模型的決策樹在高校就業(yè)數(shù)據(jù)分析中的應用

麥曉冬 ，賈 萍，翁建榮，彭凌西

(1.廣東輕工職業(yè)技術學院電子通信工程系，廣州510300;2.廣東輕工職業(yè)技術學院實訓實驗中心，廣州510300;3.廣州大學計算機科學與教育軟件學院，廣州510006)

目前，積累在高校學生管理信息系統(tǒng)里面的海量數(shù)據(jù)尤其是歷史就業(yè)數(shù)據(jù)，沒有得到應有的重視.按照《國家中長期教育改革和發(fā)展規(guī)劃綱要(2010—2020年)》［1］對教育信息化建設提出的目標:“整合各級各類教育管理資源，為宏觀決策提供科學依據(jù)”，分析歷史就業(yè)數(shù)據(jù)，挖掘出影響就業(yè)的主要因素，為決策者改進學校就業(yè)指導工作、提高就業(yè)率和就業(yè)質量提供決策支持.

對就業(yè)數(shù)據(jù)進行分析主要是希望找出數(shù)據(jù)背后隱藏著的一些重要的模式和知識.近年來，有學者提出把數(shù)據(jù)挖掘應用到該問題中，主要是將決策樹這種應用廣泛的數(shù)據(jù)挖掘分類方法應用到實際的決策分類問題中.文獻［2］、［3］采用了C4.5 算法進行決策分類樹的生成，該算法是由Quinlan 研制的國際上最早和最有影響的ID3 決策樹生成算法［4］的改進算法，但該方法不能很好地處理就業(yè)數(shù)據(jù)中存在的模糊性和不確定問題;文獻［5］采用的模糊決策樹算法［6］是對傳統(tǒng)決策樹的擴充和完善，使得決策樹學習的應用范圍擴大到了能處理數(shù)據(jù)的不確定性;文獻［7］提出基于變精度粗糙集算法［8］的決策樹模型，從而解決了就業(yè)數(shù)據(jù)中不一致信息的處理.由于實際就業(yè)情況的多樣性和復雜性，學校歷史就業(yè)數(shù)據(jù)一般都是噪聲比較大的數(shù)據(jù)集，而且各級機構對決策精度的要求也有所區(qū)別，上述方法在處理決策精度需求不同和噪聲適應能力等問題上均無法很好的解決，而基于多尺度粗糙集模型的決策樹算法，借鑒了變精度粗糙集的思想，將多尺度概念引入粗糙集理論中，可以很好地解決此問題［9］. 基于此，文中提出將基于多尺度粗糙集模型的決策樹算法應用于高校就業(yè)數(shù)據(jù)分析，并以實際就業(yè)數(shù)據(jù)為例進行分析，同時將分析結果與C4.5 算法和基于粗糙集的決策樹生成算法的分析結果進行比較.

1 基于多尺度粗糙集模型(MRSM)的決策樹生成算法

基于多尺度粗糙集模型(MRSM)的決策樹生成算法是在變精度粗糙集理論的基礎上結合尺度變量和尺度函數(shù)，利用變量在不同尺度中呈現(xiàn)不同決策規(guī)則的特點，生成決策樹.

要構建多尺度粗糙集決策樹，首先要選擇每個節(jié)點處的分類屬性. 如果選擇某一分類屬性對節(jié)點處樣本數(shù)據(jù)進行分類，它能為決策規(guī)則提供最多的確定信息，那么就可以選擇它作為分類屬性.由于近似邊界域的存在，信息的確定性會出現(xiàn)某種程度上的近似包含問題，即不確定的信息也可能會提供有用的決策規(guī)則［10］. 文獻［9］提出的MRSM 算法，定義了近似分類精度dci(D)來界定這種近似包含的范圍，近似分類屬性值越大，可以為決策分析提供更多的確定信息和一些可能起作用的不確定信息部分，因此選擇近似分類精度最大的屬性作為根節(jié)點的擴展屬性.

設多尺度決策信息系統(tǒng)S = (U，C ∪D，V，f(s))，全域U，條件屬性集C，決策屬性集D，決策函數(shù)f(s)，Ci為C 的一個條件屬性，{X1，X2，…，Xn}是Ci在全域U 的一個子域，{Y1，Y2，…，Yn}是決策屬性D 在全域U 的一個子域，條件屬性Ci對決策屬性D 關于決策函數(shù)f(s)的近似分類精度為dci(D).

近似分類精度的計算公式如下:

在具體生成決策樹的過程中，通過引入抑制因子在決策樹生成過程中對決策樹進行修剪，可以減少決策樹生成后還需要剪枝的步驟，提高了決策樹生成的速度.同時，生成出來的決策樹沒那么復雜，也便于決策者理解.

文獻［9］給出的抑制因子的定義為:對決策表信息系統(tǒng)S=(U，C，D，V，f)，C 和D 分別稱為條件屬性集和決策屬性集，分類U/C ={x1，x2，…，xn}，U/D ={y1，y2，…，ym}，決策規(guī)則為rij:des(xi)?des(yi).

設kij為決策規(guī)則rij的可能性因子，kij=且0≤kij≤1，其中是滿足決策規(guī)則xi→yj的總樣本條數(shù)是滿足決策規(guī)則的前件的樣本數(shù).

從抑制因子的定義可知，若全域U 的抑制因子大于某一個給定的閾值λ(0 ＜λ ≤1)，則說明某個決策規(guī)則前往取值des(Xi)=f(a，Xi)(aC)時至少有100 λ%的實例在決策屬性上取相同的值D0，這時，保留條件屬性值f(a，Xi)，不再需要往下生成決策樹，并直接用D0標記葉子，這樣屏蔽了少數(shù)噪聲數(shù)據(jù)對決策樹造成的不良影響，減少生成的決策樹的復雜度［9］.

由上述分析，給出基于多尺度粗糙集模型的決策樹生成算法:

輸入:多尺度決策信息系統(tǒng)S =(U，C∪D，V，f(s))，對象集U，條件屬性集C，決策屬性集D，決策函數(shù)f(s)，閾值λ(λ ＞0.5);

輸出:一棵決策樹.

Step1:生成一個節(jié)點N;

Step2:計算出每個條件屬性C 對應決策屬性D關于尺度函數(shù)f(s)的近似分類精度dci(D)，并選取其最大值對應的條件屬性值來標記其根節(jié)點N，若存在dci(D)值相同的情況，則選取對應的等價類最小的那個值;

Step3:如果dci(D)≥f(s)，則轉到Step4，否則轉到Step6;

Step4:計算出當前條件屬性C 對應的可能性因子kij和抑制因子yci(Xi)的值，并轉到Step5;

Step5:根據(jù)計算出的抑制因子yci(Xi)的值與閾值λ 進行對比，若yci(Xi)≥λ，則保留當前條件屬性值f(a，Xi)用D0標記葉子節(jié)點，并結束該子集的計算;若yci(Xi)＜λ，則選取條件屬性值為f(a，Xi)時劃分的子集作為新的對象集，并返回Step2;

Step6:根據(jù)選擇的條件屬性節(jié)點將對象集分成若干個子集，并計算子集所對應的決策屬性值，如果屬性值相同，則直接用決策屬性值標記葉子節(jié)點，結束該子集的計算，直到所有子集運算結束;否則選取這些子集作為新的對象集，返回Step2.

2 基于MRSM 的決策樹生成算法在就業(yè)數(shù)據(jù)分析中的應用

2.1 數(shù)據(jù)收集及處理

對就業(yè)數(shù)據(jù)進行挖掘分析，首先要有明確的數(shù)據(jù)分析對象.本文的數(shù)據(jù)選自某學院2012 屆畢業(yè)生的數(shù)據(jù)，抽取出與就業(yè)有關的屬性，如性別、專業(yè)成績、外語等級、計算機等級、技能等級和就業(yè)單位等，并取其中20 條實例作為就業(yè)訓練樣本集，條件屬性集為C={e1，e2，e3，e4}，決策屬性為D=(d)，如表1所示［11］.其中條件屬性專業(yè)成績e1根據(jù)學生專業(yè)成績的加權平均分并分成3 類:中等(加權平均分＜70)、良好(70≤加權平均分＜85)、優(yōu)秀(加權平均分≥85 分)，并分別取值(1 表示中等，2 表示良好，3 表示優(yōu)秀)，外語等級e2根據(jù)學生考取的英語證書等級取值(1 表示A 級，2 表示四級，3 表示六級)，計算機等級e3根據(jù)學生考取的計算機證書等級取值(1 表示1 級，2 表示2 級)，技能等級e4根據(jù)學生考取的技能證書等級取值(1 表示初級，2 表示中級，3 表示高級).對于決策屬性就業(yè)單位d，首先根據(jù)學生就業(yè)單位的單位性質將就業(yè)單位分成事業(yè)單位(A)、民營企業(yè)(B)、外資企業(yè)(C)三類，事業(yè)單位大體上包括政府單位、國有企業(yè)、大中專院校等，民營企業(yè)大體上包括民間個人或組織經(jīng)營的企業(yè)，外資企業(yè)大體上包括外國獨資或中外合資的企業(yè)，并按各類企業(yè)所提供的待遇效益、地理位置等進行梯隊劃分，量化取值為好事業(yè)單位(A1)、一般事業(yè)單位(A2)、好民營企業(yè)(B1)、一般民營企業(yè)(B2)、好外資企業(yè)(C1)、一般外資企業(yè)(C2). 數(shù)據(jù)量化后的結果見表1.

表1 學生就業(yè)數(shù)據(jù)Table 1 The employment data of students

2.2 構造決策樹

根據(jù)上述給出的基于MRSM 的決策樹生成算法，我們首先設定尺度函數(shù)f(s)=0.6 和閾值λ =0.8，用該算法構造決策樹過程如下:

(1)根據(jù)式(1)計算每個條件屬性相對決策屬性關于尺度函數(shù)f(s)的近似精度，得到de1(D)=0.74，de2(D)=0.15，de3(D)=0.32，de4(D)=0.32.

(2)根據(jù)算法Step2，選取屬性e1即專業(yè)成績標記為根節(jié)點e1.

(3)de1(D)=0.74≥0.6，所以轉到算法Step4.

(4)由屬性e1有3 種可能值(1，2，3)可知形成的樹有3個不同分支，其中在e1=1 的情況，得到抑制因子的值為1 ＞λ，因此將屬性e1標識為葉子;在e1=2 和e1=3 的2 種情況中，得到的抑制因子的值不滿足yci(Xi)≥λ 的條件，則取當前子集返回Step2進行計算.

(5)再次根據(jù)式(1)計算近似精度值，得出de4=1 的值最大，因此選擇屬性即技能等級為樹的節(jié)點.以此類推，最終得到1個復雜度為8、深度為3和葉子數(shù)為5 的決策樹(圖1).

圖1 f(s)=0.6 時生成的決策樹Figure 1 Generated decision tree of f(s)=0.6

MRSM 決策樹生成算法可基于不同的尺度函數(shù)f(s)獲得不同角度、不同尺度的決策樹，因此，我們分別再取f(s)=0.8 進行計算分析.完成如上運算過程后，得到一棵復雜度為10、深度為3、葉子數(shù)為6 的決策樹(圖2).

圖2 f(s)=0.8 時生成的決策樹Figure 2 Generated decision tree of f(s)=0.8

2.3 尺度的討論

分析本文實驗結果，隨著尺度變量的增加，f(s)變大，對知識的表達就更詳細，決策規(guī)則的數(shù)目逐漸變多，但是生成的決策樹結構的復雜度也越高.這是因為在MRSM 決策樹生成算法中，由于尺度變量增加，決策屬性所對應的近似邊界的范圍會逐漸變窄，決策規(guī)則的覆蓋度提高. 但是，要說明的是，在噪聲較多的情況下，決策規(guī)則的覆蓋度提高有時候得出的一些規(guī)則是一些不確定的規(guī)則［10］. 所以，要充分考慮不同用戶對決策精度的要求，尺度函數(shù)f(s)參數(shù)的選擇，要根據(jù)決策分析時面對的數(shù)據(jù)集和用戶對研究問題的精確程度，合理選擇參數(shù).

2.4 規(guī)則知識描述

根據(jù)基于MSRM 的決策樹生成算法，從根節(jié)點到葉子節(jié)點可得到一條決策規(guī)則. 結合本文就業(yè)訓練集進行分析的結果，通過圖1 可以得出當f(s)=0.6 時的決策規(guī)則:

Rules1:If 專業(yè)成績=“中”then 在一般民企就業(yè);

Rules2:If 專業(yè)成績=“良”and 技能等級=“中級”then 在一般民企單位就業(yè);

Rules3:If 專業(yè)成績=“良”and 技能等級=“高級”then 在一般事業(yè)單位就業(yè);

Rules4:If 專業(yè)成績=“優(yōu)”and 技能等級=“中”then 在好的民企單位就業(yè);

Rules5:If 專業(yè)成績=“優(yōu)”and 技能等級=“高級”then 在好的事業(yè)單位就業(yè).

通過圖2 也可以得出在決策函數(shù)f(s)=0.8 時的決策規(guī)則，在這里不再詳細列出具體規(guī)則.

由以上2 種決策函數(shù)不同取值所得出的規(guī)則分析，要提高畢業(yè)生的就業(yè)質量，都應該在人才培養(yǎng)方案中加大對學生的專業(yè)素養(yǎng)的培養(yǎng)，專業(yè)課程的設置必須貼近工作實際;針對畢業(yè)生就業(yè)方向主要集中的民營單位和事業(yè)單位，學生應該要考取更高級的技能證書，尤其是事業(yè)單位更加認可的等級證書.

2.5 結果與分析

為驗證基于MRSM 決策樹生成算法對就業(yè)數(shù)據(jù)挖掘的有效性，采用實驗環(huán)境如下:硬件:Intel(R)Core(TM)2 Duo CPU 2.93 GHz，2G 內存;軟件:Windows XP(SP3)和Matlab 6.5. 實驗訓練集為表1 的就業(yè)數(shù)據(jù)，將本算法與C4.5 和基于粗糙集(Rough Set)的決策樹生成算法［12］進行比較，其結果如表2所示.可見，采用基于多尺度粗糙集模型的決策樹生成算法對就業(yè)數(shù)據(jù)進行分析，樹形結構的規(guī)模和深度都不大，所以產(chǎn)生的規(guī)則數(shù)量也比較簡潔，但不存在不可分的數(shù)據(jù)集. 而其他2 種算法對就業(yè)數(shù)據(jù)進行分析，得出的決策樹相對復雜，產(chǎn)生的規(guī)則數(shù)目較多，且存在不可預測的數(shù)據(jù)集.

表2 不同算法生成決策樹的比較Table 2 Comparison of decision trees generated by different algorithms

3 基于MRSM 的決策樹生成算法的性能評價

評價每一種決策樹生成算法的性能，決策樹的復雜度和分類準確度是2個比較重要的因素. 復雜度是指根據(jù)分類發(fā)現(xiàn)模型對問題的規(guī)則描述的簡潔性和運算復雜性，規(guī)則描述越簡潔就越容易理解，如決策樹的規(guī)模和深度以及運算耗時等指標;分類準確度是指根據(jù)所得的分類模型準確預測新的或未知的數(shù)據(jù)類的能力，準確度高意味著可以在處理巨量數(shù)據(jù)時可以得到更精準的分類數(shù)據(jù)［13］.

按決策樹運用的2個階段:學習階段和測試階段，實驗選取1 000 條就業(yè)數(shù)據(jù)作為測試集，對上述利用訓練集建立的決策樹模型進行測試實驗，即運用生成的決策模型對輸入的測試集數(shù)據(jù)進行分類.實驗按不同尺度函數(shù)f(s)=0.6 和f(s)=0.8 分別進行實驗，從決策樹的分類準確度和運行時間這2個決策樹性能方面將本算法與C4.5 以及RS 算法進行了比較，實驗比較結果見表3. 結果顯示，基于多尺度粗糙集模型的決策樹生成算法在分類準確度和運行速度上都優(yōu)于C4.5 算法，雖然在不同尺度函數(shù)取值情況下其分類準確度要低于或等于RS 算法的分類準確度，但在運行速度上都要優(yōu)于對方.需要注明，實驗樣本集數(shù)據(jù)會對決策樹性能產(chǎn)生影響，且結合上文分析得知，基于多尺度粗糙集模型的決策樹生成算法中尺度函數(shù)的取值也對決策樹性能具有重要的影響. 因此，在進行決策分析時應該根據(jù)數(shù)據(jù)集和用戶對研究問題的精確程度，注重參數(shù)的選擇.

表3 不同算法決策樹性能的比較Table 3 Comparison of decision tree performance by different algorithms

4 結語

當前，就業(yè)形勢日趨嚴峻，高校應該加大整合資源、提高科學決策工作的力度，依靠科學手段，有效地提高本校畢業(yè)生的就業(yè)率和就業(yè)質量. 本文提出了將基于多尺度粗糙集模型的決策樹算法運用到對高校就業(yè)數(shù)據(jù)的挖掘分析，以此挖掘出海量就業(yè)數(shù)據(jù)背后有用的模式和知識. 基于多尺度粗糙集模型的決策樹算法，引入了尺度變量和尺度函數(shù)，使得生成的決策樹能夠滿足不同用戶對決策精度的需求，并使用抑制因子對決策樹進行修剪，使得生成的決策樹結構簡單，決策規(guī)則易于理解.將基于多尺度粗糙集模型的決策樹算法應用到高校就業(yè)數(shù)據(jù)分析，挖掘出來的規(guī)則可以滿足學校不同決策者的精度需求，可以有效地幫助學校各級管理層對學校的各項就業(yè)工作、人才培養(yǎng)方案的制訂等方面提供更準確科學的決策.

［1］國家中長期教育改革和發(fā)展規(guī)劃綱要工作小組辦公室. 國家中長期教育改革和發(fā)展規(guī)劃綱要(2010～2020年)［EB/OL］. (2010－ 07－ 29)［2013－ 10－16］. http://www. moe. gov. cn/publicfiles/business/htmlfiles/moe/A01_zcwj/201008/xxgk_93785.html.

［2］雷松澤，郝艷.基于決策樹的就業(yè)數(shù)據(jù)挖掘［J］.西安工業(yè)學院學報，2005(5):24－27.Lei S Z，Hao Y.Data mining in employment based on decision tree［J］. Journal of Xi'an Institute of Technology，2005(5):24－27.

［3］Quinlan J R. Induction of decision trees［J］. Machine Learning，1986，1(1):81－106.

［4］韓曉穎.基于決策樹的數(shù)據(jù)挖掘技術在學生就業(yè)指導中的應用［J］. 科協(xié)論壇:下半月，2011(12):172－173.Han X Y. Based on the decision tree data mining technology in the students career guidance［J］.Science ＆ Technology Association Forum:Second half，2011(12):172－173.

［5］楊斷利，張銳，王文顯.基于模糊決策樹的高校就業(yè)數(shù)據(jù)挖掘研究［J］.河北農(nóng)業(yè)大學學報，2012(2):111－114.Yang D L，Zhang R，Wang W X.Data mining in student’s employment base on fuzzy decision tree［J］. Journal of Agricultural University of Hebei，2012(2):111－114.

［6］Janikow C Z. Fuzzy decision trees:Issues and methods［J］.IEEE Transactions on Systems，Man，and Cybernetics:Part B，1998，28(1):1－14.

［7］常志玲，王嵐. 一種新的決策樹模型在就業(yè)分析中的應用［J］.計算機工程與科學，2011(5):141－145.Chang Z L，Wang L.Data mining in employment based on a new decision tree ［J］. Computer Engineering ＆ Science，2011(5):141－145.

［8］孫士保，秦克云. 變精度覆蓋粗糙集模型的推廣研究［J］.計算機科學，2008(11):210－213.Sun S B，Qin K Y. On the generalization of variable precision covering rough set model［J］. Computer Science，2008(11):210－213.

［9］陳家俊，蘇守寶，徐華麗.基于多尺度粗糙集模型的決策樹優(yōu)化算法［J］. 計算機應用，2011(12):3243－3246.Chen J J，Su S B，Xu H L. Decision tree optimization algorithm based on multiscale rough set model［J］. Journal of Computer Application，2011(12):3243－3246.

［10］翟敬梅，劉海濤，徐曉.面向噪聲數(shù)據(jù)的多尺度粗糙集模型研究［J］.計算機工程與應用，2011(6):12－14;18.Zhai J M，Liu H T，Xu X. Research of multiscale rough set model for noise data［J］. Computer Engineering and Applications，2011(6):12－14;18.

［11］鄧自洋.改進決策樹算法在高校就業(yè)管理中的應用研究［D］.上海:華東理工大學，2013.Deng Z Y.An improved decision tree algorithm and its application on university employment management［D］.Shanghai:East China University of Science and Technology，2013.

［12］常志玲，周慶敏，楊清蓮.基于粗糙集理論的決策樹構造算法［J］. 南京工業(yè)大學學報:自然科學版，2005(4):80－83.Chang Z L，Zhou Q M，Yang Q L. Decision tree algorithm based on rough set［J］. Journal of Nanjing University of Technology，2005(4):80－83.

［13］丁苗. 決策樹技術在畢業(yè)生就業(yè)數(shù)據(jù)中的應用研究［D］.吉林:遼寧工程技術大學，2012.Ding M.Research on the decision tree applied in the employment data of undergraduate student［D］. Jilin:Liaoning Technology University，2012.