董明明 蔣濤 晏婉晨 宋偉航 謝斌
摘 要:大數(shù)據(jù)時代下,處理已知和預測未知數(shù)據(jù)的數(shù)據(jù)挖據(jù)技術在社會生活的眾多方面得到了大量應用。因此,采用數(shù)據(jù)挖據(jù)中BP神經(jīng)網(wǎng)絡算法和決策樹技術對畢業(yè)生就業(yè)偏好進行了預測研究。研究中首先對兩種算法流程進行了介紹,其次應用兩種算法分別對揚州大學2017年本科畢業(yè)生就業(yè)情況進行模擬預測研究,并對兩種算法優(yōu)缺點和結果進行了對比分析。通過模擬預測結果得知,兩種算法預測數(shù)據(jù)均與實際吻合,決策樹法更適用于數(shù)據(jù)數(shù)量較少的樣本,而當數(shù)據(jù)量較大時,BP神經(jīng)網(wǎng)絡法得到的預測數(shù)據(jù)將更準確。
關鍵詞:數(shù)據(jù)挖掘;BP神經(jīng)網(wǎng)絡;決策樹;C4.5算法;機器學習
中圖分類號:TP183;TP311.13 文獻標志碼:A 文章編號:1673-291X(2018)20-0186-05
引言
隨著信息技術的高速發(fā)展,人們?nèi)諠u依賴計算機技術去解決問題。隨著人們對于收集、處理數(shù)據(jù)的的能力漸漸增強,現(xiàn)時的數(shù)據(jù)操作技術已不能滿足人們的需求,因此數(shù)據(jù)挖掘就應運而生。目前,對數(shù)據(jù)挖掘比較公認的定義是W.JFrawley,G.Piatetsky-Shapiro等人提出的[1]。
數(shù)據(jù)挖掘自發(fā)展到現(xiàn)在為止已經(jīng)產(chǎn)生了很多種方法[2],其中以BP神經(jīng)網(wǎng)絡和決策樹算法為代表。神經(jīng)網(wǎng)絡算法是一種應用廣泛的數(shù)據(jù)挖掘辦法,因其自身自行處理、分布存儲等特性非常適合處理非線性的以及那些以模糊、不完整的知識或數(shù)據(jù)為特征的問題。BP神經(jīng)網(wǎng)絡即反向傳播網(wǎng)絡(Back Propation Network)是1986年以Rumelhart為首的專家組提出的一種多層前饋網(wǎng)絡。它由大量神經(jīng)元構成,包括三層結構:輸入層、隱含層和輸出層[3]。神經(jīng)網(wǎng)絡經(jīng)過學習訓練,通過網(wǎng)絡連接權值以及網(wǎng)絡函數(shù),建立起數(shù)學模型。理論證明含一個隱含層的BP神經(jīng)網(wǎng)絡能以任意精度逼近任何非線性映射關系[4,5]。決策樹技術是機器學習中的一種歸納學習技術,它能夠從一組毫無規(guī)律的的數(shù)據(jù)樣本集合中推斷出決策樹[6]。歷史上人們先后提出了ID3算法、C4.5算法[7]、分類與回歸樹CART算法[8]、快速可伸縮的分類方法(Supervised Learning In Quest,SLIQ)[9,10]、可伸縮的并行歸納決策樹(Scalable PaRallelizable Introduction of decision tree,SPRINT)分類方法[11]、隨機映射隨機離散化連續(xù)型數(shù)據(jù)(Random Projection Random Discretization Ensembles)的算法[12]。其中,ID3算法和C4.5算法通過信息論的方法來進行分類,而CART算法、SLIQ算法以及SPRINT算法使用的是Gini指數(shù)的分類方法。本文將著重向讀者介紹C4.5算法。
針對高校畢業(yè)生數(shù)量增加給高校帶來的畢業(yè)生信息整理問題,本文采用BP神經(jīng)網(wǎng)絡算法和決策樹C4.5算法來得到2017屆揚州大學數(shù)學科學學院畢業(yè)生就業(yè)模型,并通過比較BP神經(jīng)網(wǎng)絡模型和C4.5算法得到較為精確的畢業(yè)生就業(yè)模型,利用模型指導大學生有目標、有選擇性的學習。
一、數(shù)據(jù)挖掘BP神經(jīng)網(wǎng)絡技術
BP神經(jīng)網(wǎng)絡的建立過程包括兩個過程:正向傳輸和反向傳輸。輸入信號經(jīng)過輸入層、隱含層神經(jīng)元的逐層處理到達輸出層,如果輸出信號不在預期的誤差內(nèi),則轉向反向傳輸階段,通過修改各層神經(jīng)元之間的權值使得誤差減少,再次進入正向傳輸過程,再三反復直至誤差在預期的范圍之內(nèi)。具體算法步驟如下[13,14]:
再轉至步驟4進行,直至每一層的均方差處于設定誤差范圍。
二、數(shù)據(jù)挖掘決策樹技術
(一)決策樹技術的定義和結構
決策樹是一種用來預測模型的方法,樹結構一般由根節(jié)點、中間結點、葉子結點組成,其中決策樹中的根節(jié)點和中間結點存放數(shù)據(jù)的屬性或者屬性集合,葉子節(jié)點存放分類的結果。
(二)C4.5算法
在ID3的算法中,決策樹分支的決定是由信息增益的大小決定的,因此利用ID3算法進行分類時,結果會傾向于分類結果多的屬性。因此,J.R.Quinlan提出了C4.5算法,使用了信息增益率來對決策屬性進行選擇。
設S是一個包含n個數(shù)據(jù)樣本的集合,該數(shù)據(jù)集合有l(wèi)個屬性D={d1,d2,…,dl},則C4.5的算法步驟為[15]:
其中,ti是子集中屬性值為i的個數(shù),i=1,2,...,b;nw是數(shù)據(jù)屬性為j的個數(shù),并由此推出信息增益率,其定義為Radio(dj)=Gain(dj)/Split(dj),至此選出信息增益最大的屬性dj,則dj為這一層的結點。
(5)最后,根據(jù)該屬性將子集再分類,重復步驟2、3、4,直至到達葉子結點即分類結果,由上而下遞歸下去,則可以得到完整的決策。
三、用人單位對畢業(yè)生的偏好研究
為了研究用人單位對畢業(yè)生的偏好,本文從2017屆揚州大學數(shù)學科學院畢業(yè)生系統(tǒng)中隨機抽取了140份數(shù)據(jù)樣本,數(shù)據(jù)中包含學生的基本信息、課程成績信息、綜合成績信息、獲獎信息、就業(yè)信息;對于數(shù)據(jù)本文進行預處理,刪去了與挖掘結果相關性弱的屬性,最終留下性別、專業(yè)成績、英語水平、計算機水平、政治面貌、獲獎名稱、就業(yè)單位名稱。
(一)BP神經(jīng)網(wǎng)絡法在用人單位對畢業(yè)生的偏好中的研究
使用BP神經(jīng)網(wǎng)絡分析用人單位對畢業(yè)生偏好,首先需要將數(shù)據(jù)進行歸一化:對于性別,男為1,女為0;對于獲獎情況,有為1,無為0;對于政治面貌,黨員為1,非黨員為0;對于就業(yè)情況:KY、GN、GP、SP、NP分別為0.8、0.7、0.6、0.5、0.4、0.3;對于專業(yè)成績、英語水平、計算機水平,則采用歸一化公式:
接著建立BP網(wǎng)絡結構。本文將140個樣本數(shù)據(jù)的前100個數(shù)據(jù)作為學習樣本,后40個作為訓練樣本,并設定該網(wǎng)絡結構為三層,輸入層有6個節(jié)點,輸出層一個節(jié)點。在三層網(wǎng)絡結構中。輸入層神經(jīng)元個數(shù)m、輸出層神經(jīng)元個數(shù)m和隱含層神經(jīng)元個數(shù)L有以下近似關系:
其中,a為[0,10]之間的的正整數(shù)。因此,本例中隱含層中神經(jīng)元個數(shù)在區(qū)間[3,12]內(nèi)。運用MATLAB2016a來對樣本中100個數(shù)據(jù)建立神經(jīng)網(wǎng)絡,通過多次訓練比較不同隱含層神經(jīng)元個數(shù)得到的不同MSE(Mean Square Error)即均方差,得到隱含層數(shù)量為8時,訓練而得的神經(jīng)網(wǎng)絡的均方差最小,達到了,如圖 1。
在迭代次數(shù)為207次時得到最小均方差0.008 811 8
神經(jīng)網(wǎng)絡訓練成功后,利用剩下的40個數(shù)據(jù)對神經(jīng)網(wǎng)絡數(shù)據(jù)進行預測值檢驗,從表1可以清楚地看到,預測所得的就業(yè)結果與實際結果較為相近,準確率為84.21%。實驗結果表明,通過BP神經(jīng)網(wǎng)絡可以對畢業(yè)生信息中畢業(yè)生就業(yè)情況作出較為準確的預測。
(二)決策樹法在用人單位對畢業(yè)生的偏好中的研究
接下來本文使用C4.5的方法建造就業(yè)信息決策樹。首先需要將原畢業(yè)生信息表中”專業(yè)成績”、”英語水平”、”計算機水平”進行進一步泛化:以70、85為區(qū)間劃分點,將成績泛化為優(yōu)(大于或等于85)、良(大于70小于85)、差(小于70)?!熬蜆I(yè)單位等級”是類別標識屬性,“英語水平”、“性別”、“專業(yè)成績”、“獲獎情況”、“計算機水平”、“政治面貌”是決策屬性。數(shù)據(jù)挖掘C4.5決策樹算法建造決策樹的方法如下。
共有140個樣本,GN、GP、SP、BP、DY、KY對應的樣本數(shù)分別為d1=54,d2=4,d3=23,d4=4,d5=11,d6=44。首先算出總樣本的期望信息,接著算出每個決策屬性對應的信息增益率。這里以性別的信息增益率為例:性別分成“男”“女”兩種,統(tǒng)計男生的就業(yè)情況,GN為13人、GP為2人、SP為8人、BP為3人、DY為6人、KY為15人;統(tǒng)計女生的就業(yè)情況,GN為41人、GP為2人、SP為15人、BP為1人、DY為5人、KY為29人。則性別是“男”的期望信息為I(d11,d21,d31,d41,d51,d61) = I(13,2,8,3,6,15)=2.299;性別是“女”的期望信息為 I(d12,d22,d32,d42,d52,d62)= I(41,2,15, 1,5,29) =1.885。
下面算出性別的信息期望是E(性別)=47/140×I(c11,c21,c31.c41,c51,c61)+93/140×I(c12,c22,c32,c42,c52,c62)=2.024,因而“性別”對應的信息增益為Gain(性別)=I(d1,d2,d3,d4 d5,d6)-E(性別)=0.040。經(jīng)劃分,性別分裂信息是Split(性別)=0.920,由此得到的性別信息增益率是Ratio(性別)=Gain(性別)/Split(性別)=0.043。
同理,可以得到其他屬性對應的信息增益率,專業(yè)成績?yōu)?0.198,政治面貌為0.057,英語水平為0.119,計算機水平為0.062,獲獎情況為0.064。至此,由于專業(yè)成績最高,為0.198,因此得到?jīng)Q策樹的根節(jié)點是專業(yè)成績。
同理,經(jīng)過Matlab編程,可得決策樹每一分枝的屬性增益率,并根據(jù)得到的屬性增益率得到?jīng)Q策樹,如圖4—7所示。
四、結論
運用BP神經(jīng)網(wǎng)絡和決策樹算法分別對用人單位對畢業(yè)生偏好和于本科生借書偏好進行模擬預測,得到用人單位對畢業(yè)生偏好的的神經(jīng)網(wǎng)絡和決策樹,通過它們的構成,可以得到如下結論。
1.BP神經(jīng)網(wǎng)絡和決策樹算法對用人單位對畢業(yè)生的偏好和本科生結束偏好預測得到的結論都與實際情況吻合。
2.決策樹適用于數(shù)據(jù)數(shù)量較少的樣本,當數(shù)據(jù)數(shù)量比較多時,運用BP神經(jīng)網(wǎng)絡得到的結果更為清晰。
3.在處理多個屬性的數(shù)據(jù)樣本時,神經(jīng)網(wǎng)絡更具優(yōu)勢,結論也更加直觀。
4.決策樹可以保持屬性的不變性,而神經(jīng)網(wǎng)絡需要將離散屬性轉換為數(shù)值屬性。
參考文獻:
[1] AGRAWAL R,PSAILA G,WIMMERS EL,et al.·Querying shapes of histories.·In Proc.of the VLDB Conference[M].1995.
[2] 邵峰晶,于忠清.數(shù)據(jù)挖掘原理與算法[M].北京:中國水利水電出版社.
[3] M OLLER MF.A Scaled Conjugate Gradiential Gorithm for Fast Supervised Learning[J].Neural Networks,1993,(6):525-533.
[4] 王小川,史峰,郁磊,等.MATLAB神經(jīng)網(wǎng)絡43個案例分析[M].北京:北京航天航空大學出版社,2013.
[5] KARDAN A A,SADEGH.H,GHIDARY.S.S,et al.Prediction of student course selection in online higher education institutes using neural network[J].Computer&Education;,2013,65;1-11.DOL;10.1016/j.compedu.2013.001.015.
[6] IQBALl M R A,RAHMAN S,NABILl S I,et al.Knowledge based decision tree construction with feature importance domain knowledge [C].International Conference on Electrical & Computer Engineering.IEEE,2013:659-622.
[7] QUINLAN J.R.Discovering rules by induction from large collections of examples[J].In Expert System in the Micro Electronic Age,1979:27-37.
[8] BREIMAN L,F(xiàn)RIEDMAN J,OLSHEN R A,et al.Classification and regression trees [M].Belmont Wadsworth,1984.
[9] METHA M,RISSANEN J,ARAWAL R.SLIQ:A fast scalable classifier for data mining [A].In EDBT96 Avignon,F(xiàn)rance [C],1996.
[10] CHANDRA B and PAUL P VALGHESE.Fuzzy SLIQ Decision Tree Algorithm.IEEE Trans on systems,2008,38(5):1294-1301.
[11] SHAFER J,RAWAL R,METHA M.SPRINT:A scalable parallel classifier for Data Mining [A].International Conference on Very Large Data Base [C].1996.
[12] AMIR AHMAD,GAVIN BROWM.Random Projection Random Discretization Ensembles—Ensembles of Linear Multivariate Decision Trees.IEEE Trans on Knowledge and Data Engineering,2014,(5):1225-1275.
[13] 胡月.BP算法并行化及在數(shù)據(jù)挖掘中的應用研究[D].重慶:重慶大學,2014.
[14] 梁棟,張鳳琴,陳大武,等.一種基于決策樹和遺傳算法——BP神經(jīng)網(wǎng)絡的組合預測模型[J].中國科技論文2015,10(2):170-172.
[15] 瞿花斌.數(shù)據(jù)挖掘的決策樹技術在高校畢業(yè)生管理中的應用[D].濟南:山東大學,2014.