數(shù)據(jù)挖掘中BP神經(jīng)網(wǎng)絡(luò)與決策樹技術(shù)的應(yīng)用研究

董明明 蔣濤 晏婉晨 宋偉航 謝斌

摘 要：大數(shù)據(jù)時代下，處理已知和預(yù)測未知數(shù)據(jù)的數(shù)據(jù)挖據(jù)技術(shù)在社會生活的眾多方面得到了大量應(yīng)用。因此，采用數(shù)據(jù)挖據(jù)中BP神經(jīng)網(wǎng)絡(luò)算法和決策樹技術(shù)對畢業(yè)生就業(yè)偏好進(jìn)行了預(yù)測研究。研究中首先對兩種算法流程進(jìn)行了介紹，其次應(yīng)用兩種算法分別對揚州大學(xué)2017年本科畢業(yè)生就業(yè)情況進(jìn)行模擬預(yù)測研究，并對兩種算法優(yōu)缺點和結(jié)果進(jìn)行了對比分析。通過模擬預(yù)測結(jié)果得知，兩種算法預(yù)測數(shù)據(jù)均與實際吻合，決策樹法更適用于數(shù)據(jù)數(shù)量較少的樣本，而當(dāng)數(shù)據(jù)量較大時，BP神經(jīng)網(wǎng)絡(luò)法得到的預(yù)測數(shù)據(jù)將更準(zhǔn)確。

關(guān)鍵詞：數(shù)據(jù)挖掘；BP神經(jīng)網(wǎng)絡(luò)；決策樹；C4.5算法；機器學(xué)習(xí)

中圖分類號：TP183；TP311.13 文獻(xiàn)標(biāo)志碼：A 文章編號：1673-291X（2018）20-0186-05

引言

隨著信息技術(shù)的高速發(fā)展，人們?nèi)諠u依賴計算機技術(shù)去解決問題。隨著人們對于收集、處理數(shù)據(jù)的的能力漸漸增強，現(xiàn)時的數(shù)據(jù)操作技術(shù)已不能滿足人們的需求，因此數(shù)據(jù)挖掘就應(yīng)運而生。目前，對數(shù)據(jù)挖掘比較公認(rèn)的定義是W.JFrawley，G.Piatetsky-Shapiro等人提出的[1]。

數(shù)據(jù)挖掘自發(fā)展到現(xiàn)在為止已經(jīng)產(chǎn)生了很多種方法[2]，其中以BP神經(jīng)網(wǎng)絡(luò)和決策樹算法為代表。神經(jīng)網(wǎng)絡(luò)算法是一種應(yīng)用廣泛的數(shù)據(jù)挖掘辦法，因其自身自行處理、分布存儲等特性非常適合處理非線性的以及那些以模糊、不完整的知識或數(shù)據(jù)為特征的問題。BP神經(jīng)網(wǎng)絡(luò)即反向傳播網(wǎng)絡(luò)（Back Propation Network）是1986年以Rumelhart為首的專家組提出的一種多層前饋網(wǎng)絡(luò)。它由大量神經(jīng)元構(gòu)成，包括三層結(jié)構(gòu)：輸入層、隱含層和輸出層[3]。神經(jīng)網(wǎng)絡(luò)經(jīng)過學(xué)習(xí)訓(xùn)練，通過網(wǎng)絡(luò)連接權(quán)值以及網(wǎng)絡(luò)函數(shù)，建立起數(shù)學(xué)模型。理論證明含一個隱含層的BP神經(jīng)網(wǎng)絡(luò)能以任意精度逼近任何非線性映射關(guān)系[4，5]。決策樹技術(shù)是機器學(xué)習(xí)中的一種歸納學(xué)習(xí)技術(shù)，它能夠從一組毫無規(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算法通過信息論的方法來進(jìn)行分類，而CART算法、SLIQ算法以及SPRINT算法使用的是Gini指數(shù)的分類方法。本文將著重向讀者介紹C4.5算法。

針對高校畢業(yè)生數(shù)量增加給高校帶來的畢業(yè)生信息整理問題，本文采用BP神經(jīng)網(wǎng)絡(luò)算法和決策樹C4.5算法來得到2017屆揚州大學(xué)數(shù)學(xué)科學(xué)學(xué)院畢業(yè)生就業(yè)模型，并通過比較BP神經(jīng)網(wǎng)絡(luò)模型和C4.5算法得到較為精確的畢業(yè)生就業(yè)模型，利用模型指導(dǎo)大學(xué)生有目標(biāo)、有選擇性的學(xué)習(xí)。

一、數(shù)據(jù)挖掘BP神經(jīng)網(wǎng)絡(luò)技術(shù)

BP神經(jīng)網(wǎng)絡(luò)的建立過程包括兩個過程：正向傳輸和反向傳輸。輸入信號經(jīng)過輸入層、隱含層神經(jīng)元的逐層處理到達(dá)輸出層，如果輸出信號不在預(yù)期的誤差內(nèi)，則轉(zhuǎn)向反向傳輸階段，通過修改各層神經(jīng)元之間的權(quán)值使得誤差減少，再次進(jìn)入正向傳輸過程，再三反復(fù)直至誤差在預(yù)期的范圍之內(nèi)。具體算法步驟如下[13，14]：

再轉(zhuǎn)至步驟4進(jìn)行，直至每一層的均方差處于設(shè)定誤差范圍。

二、數(shù)據(jù)挖掘決策樹技術(shù)

（一）決策樹技術(shù)的定義和結(jié)構(gòu)

決策樹是一種用來預(yù)測模型的方法，樹結(jié)構(gòu)一般由根節(jié)點、中間結(jié)點、葉子結(jié)點組成，其中決策樹中的根節(jié)點和中間結(jié)點存放數(shù)據(jù)的屬性或者屬性集合，葉子節(jié)點存放分類的結(jié)果。

（二）C4.5算法

在ID3的算法中，決策樹分支的決定是由信息增益的大小決定的，因此利用ID3算法進(jìn)行分類時，結(jié)果會傾向于分類結(jié)果多的屬性。因此，J.R.Quinlan提出了C4.5算法，使用了信息增益率來對決策屬性進(jìn)行選擇。

設(shè)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為這一層的結(jié)點。

（5）最后，根據(jù)該屬性將子集再分類，重復(fù)步驟2、3、4，直至到達(dá)葉子結(jié)點即分類結(jié)果，由上而下遞歸下去，則可以得到完整的決策。

三、用人單位對畢業(yè)生的偏好研究

為了研究用人單位對畢業(yè)生的偏好，本文從2017屆揚州大學(xué)數(shù)學(xué)科學(xué)院畢業(yè)生系統(tǒng)中隨機抽取了140份數(shù)據(jù)樣本，數(shù)據(jù)中包含學(xué)生的基本信息、課程成績信息、綜合成績信息、獲獎信息、就業(yè)信息；對于數(shù)據(jù)本文進(jìn)行預(yù)處理，刪去了與挖掘結(jié)果相關(guān)性弱的屬性，最終留下性別、專業(yè)成績、英語水平、計算機水平、政治面貌、獲獎名稱、就業(yè)單位名稱。

（一）BP神經(jīng)網(wǎng)絡(luò)法在用人單位對畢業(yè)生的偏好中的研究

使用BP神經(jīng)網(wǎng)絡(luò)分析用人單位對畢業(yè)生偏好，首先需要將數(shù)據(jù)進(jìn)行歸一化：對于性別，男為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)絡(luò)結(jié)構(gòu)。本文將140個樣本數(shù)據(jù)的前100個數(shù)據(jù)作為學(xué)習(xí)樣本，后40個作為訓(xùn)練樣本，并設(shè)定該網(wǎng)絡(luò)結(jié)構(gòu)為三層，輸入層有6個節(jié)點，輸出層一個節(jié)點。在三層網(wǎng)絡(luò)結(jié)構(gòu)中。輸入層神經(jīng)元個數(shù)m、輸出層神經(jīng)元個數(shù)m和隱含層神經(jīng)元個數(shù)L有以下近似關(guān)系：

其中，a為[0，10]之間的的正整數(shù)。因此，本例中隱含層中神經(jīng)元個數(shù)在區(qū)間[3，12]內(nèi)。運用MATLAB2016a來對樣本中100個數(shù)據(jù)建立神經(jīng)網(wǎng)絡(luò)，通過多次訓(xùn)練比較不同隱含層神經(jīng)元個數(shù)得到的不同MSE（Mean Square Error）即均方差，得到隱含層數(shù)量為8時，訓(xùn)練而得的神經(jīng)網(wǎng)絡(luò)的均方差最小，達(dá)到了，如圖 1。

在迭代次數(shù)為207次時得到最小均方差0.008 811 8

神經(jīng)網(wǎng)絡(luò)訓(xùn)練成功后，利用剩下的40個數(shù)據(jù)對神經(jīng)網(wǎng)絡(luò)數(shù)據(jù)進(jìn)行預(yù)測值檢驗，從表1可以清楚地看到，預(yù)測所得的就業(yè)結(jié)果與實際結(jié)果較為相近，準(zhǔn)確率為84.21%。實驗結(jié)果表明，通過BP神經(jīng)網(wǎng)絡(luò)可以對畢業(yè)生信息中畢業(yè)生就業(yè)情況作出較為準(zhǔn)確的預(yù)測。

（二）決策樹法在用人單位對畢業(yè)生的偏好中的研究

接下來本文使用C4.5的方法建造就業(yè)信息決策樹。首先需要將原畢業(yè)生信息表中”專業(yè)成績”、”英語水平”、”計算機水平”進(jìn)行進(jìn)一步泛化：以70、85為區(qū)間劃分點，將成績泛化為優(yōu)（大于或等于85）、良（大于70小于85）、差（小于70）。“就業(yè)單位等級”是類別標(biāo)識屬性，“英語水平”、“性別”、“專業(yè)成績”、“獲獎情況”、“計算機水平”、“政治面貌”是決策屬性。數(shù)據(jù)挖掘C4.5決策樹算法建造決策樹的方法如下。

共有140個樣本，GN、GP、SP、BP、DY、KY對應(yīng)的樣本數(shù)分別為d1=54，d2=4，d3=23，d4=4，d5=11，d6=44。首先算出總樣本的期望信息，接著算出每個決策屬性對應(yīng)的信息增益率。這里以性別的信息增益率為例：性別分成“男”“女”兩種，統(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，因而“性別”對應(yīng)的信息增益為Gain（性別）=I（d1，d2，d3，d4 d5，d6）-E（性別）=0.040。經(jīng)劃分，性別分裂信息是Split（性別）=0.920，由此得到的性別信息增益率是Ratio（性別）=Gain（性別）/Split（性別）=0.043。

同理，可以得到其他屬性對應(yīng)的信息增益率，專業(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所示。

四、結(jié)論

運用BP神經(jīng)網(wǎng)絡(luò)和決策樹算法分別對用人單位對畢業(yè)生偏好和于本科生借書偏好進(jìn)行模擬預(yù)測，得到用人單位對畢業(yè)生偏好的的神經(jīng)網(wǎng)絡(luò)和決策樹，通過它們的構(gòu)成，可以得到如下結(jié)論。

1.BP神經(jīng)網(wǎng)絡(luò)和決策樹算法對用人單位對畢業(yè)生的偏好和本科生結(jié)束偏好預(yù)測得到的結(jié)論都與實際情況吻合。

2.決策樹適用于數(shù)據(jù)數(shù)量較少的樣本，當(dāng)數(shù)據(jù)數(shù)量比較多時，運用BP神經(jīng)網(wǎng)絡(luò)得到的結(jié)果更為清晰。

3.在處理多個屬性的數(shù)據(jù)樣本時，神經(jīng)網(wǎng)絡(luò)更具優(yōu)勢，結(jié)論也更加直觀。

4.決策樹可以保持屬性的不變性，而神經(jīng)網(wǎng)絡(luò)需要將離散屬性轉(zhuǎn)換為數(shù)值屬性。

參考文獻(xiàn)：

[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)絡(luò)43個案例分析[M].北京：北京航天航空大學(xué)出版社，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ù)挖掘中的應(yīng)用研究[D].重慶：重慶大學(xué)，2014.

[14] 梁棟，張鳳琴，陳大武，等.一種基于決策樹和遺傳算法——BP神經(jīng)網(wǎng)絡(luò)的組合預(yù)測模型[J].中國科技論文2015，10（2）：170-172.

[15] 瞿花斌.數(shù)據(jù)挖掘的決策樹技術(shù)在高校畢業(yè)生管理中的應(yīng)用[D].濟南：山東大學(xué)，2014.