基于決策樹算法在高校招生決策系統(tǒng)的應(yīng)用與研究

劉思宏

(安徽電子信息職業(yè)技術(shù)學院 軟件學院,安徽 蚌埠 233060)

摘要：隨著高校生源質(zhì)量的下降，提高高?？忌膱蟮铰适钱攧?wù)之急.分析影響報到率的條件，預(yù)測報到結(jié)果，能夠為院校招生教學等工作提供有價值的參考依據(jù).結(jié)合數(shù)據(jù)挖掘技術(shù)中決策樹ID3算法建立決策樹模型，并結(jié)合BMH模式匹配算法及樸素貝葉斯方法對ID3模型結(jié)論進行驗證，對提高報到率具有一定的實用價值.

關(guān)鍵詞：決策樹；ID3算法；模式匹配算法；樸素貝葉斯方法

中圖分類號：TP391文獻標志碼：A

文章編號：1008-5564(2015)03-0071-03

收稿日期：2015-04-01

作者簡介：肖丹妮(1983—)，女，陜西戶縣人，中國兵器裝備集團摩托車檢測技術(shù)研究所助理工程師，碩士，主要從事催化轉(zhuǎn)化器貴金屬檢測研究.

ApplicationandStudyofEnrollmentDecisionSysteminCollegeBasedontheDecisionTreeAlgorithm

LIUSi-hong

(SchoolofSoftware,AnhuiVocationalCollegeofElectronics&InformationTechnology,Bengbu233060,China)

Abstract：With the decrease of college students’ quality, it is a task of top priority to improve the registration rate of college examinees. Analyzing influence factors of the registration rate and predicting the results of the registration could provide a valuable reference for enrollment and teaching work in colleges. The decision tree model was constructed based on the ID3 algorithm of decision tree of data mining technology, and the conclusions of ID3 model were verified based on BMH pattern matching algorithm and naive Bayesian method, all of above have important significance and practical application value in improving the registration rate.

Keywords：decisiontree;ID3algorithm；patternmatchingalgorithm;naiveBayesianmethod

隨著現(xiàn)代高等教育的全面普及，在適齡生源數(shù)量逐年下降的現(xiàn)實情況下，即使高校自1999年開始擴大普高計劃，但是依然呈現(xiàn)出報到率較低的現(xiàn)象.部分農(nóng)村考生因地區(qū)、專業(yè)、家庭經(jīng)濟等原因放棄入學，同時選擇打工和出國的考生也日趨增加.利用決策樹技術(shù)，分析影響報到率的條件，預(yù)測報到結(jié)果，能夠為院校招生、教學等工作提供有價值的參考依據(jù).

1數(shù)據(jù)挖掘和決策樹

數(shù)據(jù)挖掘(DataMining)從技術(shù)角度定義，是從大量的、不完全的、有噪聲的、模糊的、隨機的實際數(shù)據(jù)中提取隱含在其中的、人們事先不知道的、但又是潛在有用的信息和知識的過程[1].目前數(shù)據(jù)挖掘已經(jīng)充分應(yīng)用的方法包括：概念/類描述、關(guān)聯(lián)分析、分類預(yù)測、聚類、孤立點分析、演變分析等[2].

決策樹(Decisiontree),又稱判定樹，是數(shù)據(jù)挖掘中常用的建模方法以實現(xiàn)分類的功能.20世紀60年代Hunt首次提出這個概念，后由Quinlan等人根據(jù)信息論中的信息熵(Entropy)的思想提出決策樹的經(jīng)典ID3算法，其基本思想是根據(jù)信息熵以及信息增益的概念，將含有最高信息增益的屬性作為當前結(jié)點的訓練測試屬性，建立二叉樹決策模型[3].信息熵值的大小直接決定決策樹建樹分枝的判定條件.信息熵值越小，訓練子集劃分時的純度越高.當所有數(shù)據(jù)記錄均劃分于相同類別時，或所有數(shù)據(jù)記錄均具有相同屬性時，則停止分類.

ID3算法描述如下：

算法：(ID3buide_dt)生成決策樹

輸入：訓練樣本集，所有屬性歸納為屬性集

輸出：決策樹

①創(chuàng)建一個節(jié)點N；

②如果所有訓練樣本集均屬于相同的類C，那么

③返回節(jié)點N作為葉子節(jié)點，類C為標記；

④如果屬性集A為空，那么

⑤返回節(jié)點N作為葉子節(jié)點，記為訓練樣本集中的類；

⑥選擇屬性集A中計算為最高信息增益的屬性Sa；

⑦標記節(jié)點N為測試屬性；

⑧劃分訓練樣本集，對每個測試屬性中的值a進行劃分；

⑨建立測試屬性值=a的子樹s，s為訓練樣本集中測試屬性=a的樣本集；

⑩如果s為空，那么

2建立決策樹系統(tǒng)原型

2008年至今，高校平均報到率一直維持在80%～85%左右，部分熱門地區(qū)熱門專業(yè)近年招生趨勢穩(wěn)定，但是不同地市考生的報到率卻每況愈下，且申請調(diào)換專業(yè)的考生較多.為了能夠真正的招到分數(shù)高、生源質(zhì)量好且滿足招生院校專業(yè)計劃的生源，著實能夠提高報到率，現(xiàn)利用決策樹ID3算法建立招生決策系統(tǒng)模型原型.

2.1數(shù)據(jù)的收集與預(yù)處理

以安徽某高校近年招生錄取數(shù)據(jù)作為訓練樣本集.該校招生的生源對象以安徽省內(nèi)為主，現(xiàn)將數(shù)據(jù)訓練樣本集對省內(nèi)地市作分析.在數(shù)據(jù)庫中隨機抽取錄取信息500條記錄，將錄取數(shù)據(jù)庫和實際報到數(shù)據(jù)庫進行聯(lián)接，得到“新生信息表”，定義條件屬性字段包括：性別、戶口類別、考生類別、歸屬地區(qū)、專業(yè)類別、成績類型、錄取批次.將成績做概化處理400分以上(含400分)概化為“好”；300～399概化為“較好”；200～299概化為“一般”.

2.2建模分析

分別對考生成績(好、較好、一般)、考生類別(應(yīng)屆生、歷屆生)、考生科類(文科、理科)、考生戶口(城鎮(zhèn)、農(nóng)村)、生源地(本市、皖北、皖南)等多個條件進行分類.

2.3建立決策模型原型

利用ID3算法及其改進方法將決策樹的根節(jié)點和分支屬性節(jié)點分別計算.

建立根節(jié)點：已知訓練樣本集E是n維有窮向量空間，包含了i個不同的屬性類，將E劃分為i個類的信息熵，有：

Entropy(E)=∑-p(i)log2p(i)

(1)

在錄取數(shù)據(jù)庫中隨機抽取的500條數(shù)據(jù)中，得到452條考生記錄已報到，利用式(1)計算熵可得：Entropy(A,學生報到)=-(452/500)log2(452/500)-(48/500)log2(48/500)= 0.456 1.

計算條件屬性熵：若選擇屬性A的每一分支節(jié)點上，選擇A導致的期望熵值定義為每個子集E的加權(quán)和，有

(2)

以專業(yè)節(jié)點屬性為例，計算“專業(yè)”條件屬性熵，利用式(1)計算屬性值熵:

Entropy(A制造)=-(58 /70)log2(58 /70)-(12 /70)log2(12 /70)=0.660 9

Entropy(A電子信息)=-(236/272)log2(236/272)-(36/272)log2(36/272)=0.563 8

Entropy(A材料與能源)=-(43/50)log2(43/50)-(7/50)log2(7/50)=0.584 2

Entropy(A財經(jīng))=-(40/48)log2(40/48)-(8/48)log2(8/48)=0.650 0

Entropy(A文化教育)=-(57/60)log2(57/60)-(3/60)log2(3/60)=0.286 3

將上述計算數(shù)值代入式(2)計算屬性熵：

Entropy(A，專業(yè))=(專業(yè)子集數(shù)/500)*Entropy(A|專業(yè)名稱=…)=(70/500)*0.660 9+(272/500)*0.563 8+(50/500)*0.584 2+(48/500)*0.65+(60/500)*0.286 3=0.554 4

計算條件屬性增益：屬性A相對訓練樣本集E的信息增益Gain(E,A)定義為：

Gain(E,A)=Entropy(E)-Entropy(E,A)

(3)

利用式(3)計算條件屬性增益：Gain(A,專業(yè))= 0.562 8-0.554 4=0.008 4

依次按照上述公式進行決策屬性計算，最終得到?jīng)Q策樹模型原型如圖1所示：

圖1　決策樹模型原型

2.4得出分類規(guī)則

根據(jù)決策樹模型原型得到分類規(guī)則，采用IF…THEN的形式將各個分類條件下，考生是否報到的結(jié)果直觀顯示出來，如圖2所示.

圖2　分類規(guī)則結(jié)論

3建立決策驗證系統(tǒng)

3.1模式匹配算法

模式匹配算法是指將兩個模式作為輸入，計算模式元素之間語義上的對應(yīng)關(guān)系的過程.字符串模式匹配算法是在給定的字符集中，判斷一個模式串(字符串)是否在給定的文本串(文本)中出現(xiàn)[4].在上述招生錄取數(shù)據(jù)庫中可以認定整個錄取數(shù)據(jù)庫作為一個完整的長字符串，通過行的順序逐一連續(xù)起來，利用模式匹配算法中的匹配次數(shù)作為統(tǒng)計數(shù)量的結(jié)果，將統(tǒng)計數(shù)字的所占的比例作為下次匹配計算的值.所得到的計算結(jié)果可以讓決策者更加直觀的看到各個條件下學生的報到率,如圖3所示.

圖3　模式匹配算法分條件報到率統(tǒng)計

3.2樸素貝葉斯分類方法

樸素貝葉斯分類(NaiveBayesClassifier，簡稱NBC)在貝葉斯統(tǒng)計的基礎(chǔ)上建立了分類模型，利用概率計算的思想，在統(tǒng)計學等諸多領(lǐng)域?qū)崿F(xiàn)預(yù)測的功能.

貝葉斯定理[5]設(shè)S是類標號未知的數(shù)據(jù)樣本，設(shè)H為某假設(shè)，若數(shù)據(jù)樣本S屬于某特定類C.在分類問題中，我們希望確定P(H|S)，即給定測試樣本X假設(shè)H成立的概率.在此驗證系統(tǒng)中，利用模式匹配算法作為分條件匹配統(tǒng)計結(jié)論，結(jié)合樸素貝葉斯方法將上述分類規(guī)則進行驗證.

圖4　樸素貝葉斯方法驗證結(jié)果

驗證分類規(guī)則：取條件={IF地區(qū)=“皖南”AND專業(yè)=“文化教育”AND戶口類別=“農(nóng)村”AND性別=“女”}

驗證結(jié)論={是否報到=“是”}

驗證結(jié)果如圖4所示.

3.3驗證結(jié)果分析

從上述模式匹配算法和樸素貝葉斯方法相結(jié)合的計算中，我們得出以下結(jié)論：

①當前測試訓練樣本集中，利用決策樹方法ID3建立模型得到分類規(guī)則的條件與結(jié)論與樸素貝葉斯方法驗證較一致.在驗證過程中，根據(jù)判定條件得出的決策屬性個數(shù)，統(tǒng)計分條件下的考生報到率.根據(jù)已知條件預(yù)測出較為準確的結(jié)論是能夠幫助決策者做出決策的重要方法.

②模式匹配算法較為有效、準確地統(tǒng)計出分條件報到人數(shù)，對分專業(yè)報到率，分地區(qū)報到率，分批次報到率等做出詳盡統(tǒng)計，統(tǒng)計結(jié)果能夠得出直觀的結(jié)論.同時，統(tǒng)計值可作為樸素貝葉斯的先驗概率，避免了手工計算的繁雜.

4結(jié)語

本文研究數(shù)據(jù)挖掘中的決策樹技術(shù)，針對決策樹技術(shù)和樸素貝葉斯的分類方法進行討論，結(jié)合實際高校的招生錄取報到數(shù)據(jù)，提出利用ID3算法生成決策樹模型原型，根據(jù)分類規(guī)則產(chǎn)生的結(jié)果分析影響高校考生報到的關(guān)鍵條件，并將模式匹配算法和樸素貝葉斯方法相結(jié)合進行驗證，輔助決策者對于招生宣傳、專業(yè)制定、課程設(shè)置等相關(guān)工作的預(yù)測，能夠更有利于應(yīng)對市場變化，提高報到率，為高校決策提供一定的輔助作用.

[參考文獻]

[1]HANJia-wei,KANBERM.Dataminingconceptsandtechniques[M].MorganKaufinannPress,2001:186-201.

[2]成平廣.ID3算法在高校招生決策中的應(yīng)用研究[J].重慶教育學院學報，2008,21(3):44-46.

[3]黃文.決策樹的經(jīng)典算法：ID3與C4.5[J].四川文理學院學報(自然科學版)，2007，17(5)：16-18.

[4]劉勝飛，張云泉.一種改進的BMH模式匹配算法[J].計算機科學，2008，35(11):164-173.

[5]葉丹，劉坤.基于樸素貝葉斯分類的高校招生宣傳決策系統(tǒng)[J].井岡山學院學報(自然科學版)，2008,29(8):27-29.

[責任編輯王新奇]

Vol.18No.3Jul.2015