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

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

劉思宏

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

摘要：隨著高校生源質(zhì)量的下降，提高高?？忌膱?bào)到率是當(dāng)務(wù)之急.分析影響報(bào)到率的條件，預(yù)測報(bào)到結(jié)果，能夠?yàn)樵盒Ｕ猩虒W(xué)等工作提供有價(jià)值的參考依據(jù).結(jié)合數(shù)據(jù)挖掘技術(shù)中決策樹ID3算法建立決策樹模型，并結(jié)合BMH模式匹配算法及樸素貝葉斯方法對ID3模型結(jié)論進(jìn)行驗(yàn)證，對提高報(bào)到率具有一定的實(shí)用價(jià)值.

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

中圖分類號(hào)：TP391文獻(xiàn)標(biāo)志碼：A

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

收稿日期：2015-04-01

作者簡介：肖丹妮(1983—)，女，陜西戶縣人，中國兵器裝備集團(tuán)摩托車檢測技術(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)實(shí)情況下，即使高校自1999年開始擴(kuò)大普高計(jì)劃，但是依然呈現(xiàn)出報(bào)到率較低的現(xiàn)象.部分農(nóng)村考生因地區(qū)、專業(yè)、家庭經(jīng)濟(jì)等原因放棄入學(xué)，同時(shí)選擇打工和出國的考生也日趨增加.利用決策樹技術(shù)，分析影響報(bào)到率的條件，預(yù)測報(bào)到結(jié)果，能夠?yàn)樵盒Ｕ猩?、教學(xué)等工作提供有價(jià)值的參考依據(jù).

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

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

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

ID3算法描述如下：

算法：(ID3buide_dt)生成決策樹

輸入：訓(xùn)練樣本集，所有屬性歸納為屬性集

輸出：決策樹

①創(chuàng)建一個(gè)節(jié)點(diǎn)N；

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

③返回節(jié)點(diǎn)N作為葉子節(jié)點(diǎn)，類C為標(biāo)記；

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

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

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

⑦標(biāo)記節(jié)點(diǎn)N為測試屬性；

⑧劃分訓(xùn)練樣本集，對每個(gè)測試屬性中的值a進(jìn)行劃分；

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

⑩如果s為空，那么

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

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

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

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

2.2建模分析

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

2.3建立決策模型原型

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

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

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

(1)

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

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

(2)

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

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財(cái)經(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

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

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

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

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

(3)

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

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

圖1　決策樹模型原型

2.4得出分類規(guī)則

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

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

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

3.1模式匹配算法

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

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

3.2樸素貝葉斯分類方法

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

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

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

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

驗(yàn)證結(jié)論={是否報(bào)到=“是”}

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

3.3驗(yàn)證結(jié)果分析

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

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

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

4結(jié)語

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

[參考文獻(xiàn)]

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

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

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

[4]劉勝飛，張?jiān)迫?一種改進(jìn)的BMH模式匹配算法[J].計(jì)算機(jī)科學(xué)，2008，35(11):164-173.

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

[責(zé)任編輯王新奇]

Vol.18No.3Jul.2015