決策樹(shù)和貝葉斯分類(lèi)算法在學(xué)生專(zhuān)業(yè)錄取數(shù)據(jù)中的應(yīng)用研究

黃雪華

?

決策樹(shù)和貝葉斯分類(lèi)算法在學(xué)生專(zhuān)業(yè)錄取數(shù)據(jù)中的應(yīng)用研究

黃雪華

(湖南城市學(xué)院信息與電子工程學(xué)院，湖南 益陽(yáng) 413000)

分類(lèi)算法是數(shù)據(jù)挖掘中最重要的挖掘理論之一，廣泛應(yīng)用于天氣預(yù)測(cè)、反垃圾郵件、疾病診斷等應(yīng)用中﹒通過(guò)介紹應(yīng)用最廣泛的兩類(lèi)分類(lèi)算法決策樹(shù)和貝葉斯理論及算法，并應(yīng)用于湖南城市學(xué)院專(zhuān)業(yè)招生錄取數(shù)據(jù)中，結(jié)合SQL server及ASP.NET，獲取每個(gè)專(zhuān)業(yè)的學(xué)生性別預(yù)測(cè)，獲取每個(gè)專(zhuān)業(yè)生源省份預(yù)測(cè)，并對(duì)預(yù)測(cè)結(jié)果和實(shí)際結(jié)果進(jìn)行比較，得到誤差率分別在0.01和0.2以?xún)?nèi)﹒

分類(lèi)；決策樹(shù)；樸素貝葉斯；ASP.NET；SQL Server2014；專(zhuān)業(yè)錄取

分類(lèi)算法是預(yù)測(cè)離散數(shù)據(jù)的分類(lèi)標(biāo)號(hào)﹒最著名的例子如韓家煒的AllElectronics郵寄清單數(shù)據(jù)庫(kù)[1]，根據(jù)顧客姓名、年齡、收入、職業(yè)和信譽(yù)度，可對(duì)他們是否購(gòu)買(mǎi)計(jì)算機(jī)建立分類(lèi)模型，并預(yù)測(cè)未知顧客所屬分類(lèi)；再如銀行中預(yù)測(cè)貸款是否存在風(fēng)險(xiǎn)，客戶信用卡等級(jí)劃分，這樣可以降低銀行信貸的風(fēng)險(xiǎn)，減少資金的流失；又如文本分類(lèi)、網(wǎng)絡(luò)異常檢測(cè)、垃圾短信過(guò)濾等應(yīng)用﹒

1 決策樹(shù)相關(guān)理論及算法分析

1.1 決策樹(shù)定義

從數(shù)據(jù)結(jié)構(gòu)來(lái)看，決策樹(shù)是一顆倒立的樹(shù)﹒從樹(shù)的根節(jié)點(diǎn)到葉節(jié)點(diǎn)的路徑實(shí)際就是決策的過(guò)程，確定數(shù)據(jù)樣本所屬類(lèi)標(biāo)號(hào)的過(guò)程，它是一個(gè)遞歸地從上到下確定分支節(jié)點(diǎn)和葉節(jié)點(diǎn)的過(guò)程﹒葉節(jié)點(diǎn)存放的是數(shù)據(jù)樣本所屬的類(lèi)標(biāo)號(hào)；分支節(jié)點(diǎn)根據(jù)數(shù)據(jù)樣本的某個(gè)合適的屬性值進(jìn)行數(shù)據(jù)集劃分﹒

1.2 決策樹(shù)構(gòu)造步驟

決策樹(shù)的構(gòu)造分為2個(gè)步驟：第1步是建立決策樹(shù)階段，通過(guò)樣本數(shù)據(jù)建立決策樹(shù)；第2步是樹(shù)剪枝階段，對(duì)決策樹(shù)減去不必要的分枝以及過(guò)度擬合，主要是處理噪聲數(shù)據(jù)和異常數(shù)據(jù)﹒

1.3 決策樹(shù)算法分析

決策樹(shù)算法有很多種，最為著名的有ID3[1]，C4.5[2]﹒決策樹(shù)建立的差異主要在屬性值的選取上﹒ID3的分支節(jié)點(diǎn)屬性選擇是通過(guò)計(jì)算屬性的信息增益值來(lái)選擇的﹒C4.5算法是對(duì)ID3算法的改進(jìn)﹒ID3算法只能針對(duì)離散數(shù)據(jù)進(jìn)行樣本分類(lèi)，C4.5擴(kuò)充了連續(xù)數(shù)據(jù)的分類(lèi)方法﹒

設(shè)是個(gè)數(shù)據(jù)樣本的集合，假定類(lèi)標(biāo)號(hào)屬性具有個(gè)不同值，定義個(gè)不同類(lèi)C(=1，…，)，又設(shè)S是類(lèi)C中的樣本數(shù)，樣本分類(lèi)期望信息為

P是任意樣本屬于類(lèi)C的概率，用S/估計(jì)﹒設(shè)屬性A具有個(gè)不同值{1，…，a}，屬性A將樣本劃分為個(gè)子集{1，…，S}，S是子集S中類(lèi)C的樣本數(shù)﹒根據(jù)A劃分子集的熵由式(2)和式(3)給出﹒

然后計(jì)算每個(gè)屬性的信息增益，在屬性A上的信息增益為Gain(A)=(S，…，S)－(A)，以具有最高信息增益值的屬性作為劃分屬性，并為每個(gè)值創(chuàng)建分支且迭代劃分樣本﹒

2 貝葉斯定義及算法理論

2.1 貝葉斯定義

貝葉斯分類(lèi)方法是另外一種著名的分類(lèi)算法，它主要是根據(jù)后驗(yàn)概率來(lái)預(yù)測(cè)數(shù)據(jù)所屬的最有可能的分類(lèi)﹒

2.2 樸素貝葉斯概念

貝葉斯分類(lèi)算法有多種，其中比較著名的是樸素貝葉斯分類(lèi)，它假定每個(gè)屬性值對(duì)分類(lèi)的影響是相互獨(dú)立的﹒

2.3 貝葉斯算法[3-5]

假設(shè)A1，A2，…，A是數(shù)據(jù)集的個(gè)屬性，C，C，…，C是數(shù)據(jù)集的個(gè)分類(lèi)，={1，2，…，x}是一個(gè)具體的樣本對(duì)象，這個(gè)樣本對(duì)象屬于類(lèi)C的概率可以利用貝葉斯公式(見(jiàn)式(4))計(jì)算出來(lái)﹒

當(dāng)(C|)大于(C|)時(shí)，認(rèn)為該樣本對(duì)象屬于類(lèi)C，因此需要求出最大的(C|)值，而對(duì)于所有分類(lèi)，樣本的概率()可以視為常數(shù)﹒因此只需(|C)(C)最大，如果類(lèi)的先驗(yàn)概率未知，則通常假定(1)=(2)=…=(C)，否則按(C)=S/計(jì)算，其中S是屬于類(lèi)C中的訓(xùn)練樣本數(shù)，是訓(xùn)練樣本總數(shù)，且假定各屬性之間是相互條件獨(dú)立的，則可得

對(duì)于每個(gè)類(lèi)C，只需求出最大的(|C)(C)值，則樣本屬于該類(lèi)﹒

3 算法應(yīng)用

3.1 學(xué)生專(zhuān)業(yè)錄取數(shù)據(jù)說(shuō)明

我校的招生錄取數(shù)據(jù)，共15 734條數(shù)據(jù)，原始數(shù)據(jù)分散在4張EXCEL表中，包含2013年、2014年、2015年、2016年的新生錄取情況，由考生號(hào)ksh、學(xué)生姓名xm、性別xb、錄取專(zhuān)業(yè)lqzy、高考分?jǐn)?shù)grade、投檔線pass grade及省份sf構(gòu)成﹒部分錄取原始數(shù)據(jù)樣本見(jiàn)表1﹒

表1 學(xué)生專(zhuān)業(yè)錄取原始數(shù)據(jù)

對(duì)這15 000多條數(shù)據(jù)進(jìn)行處理，把4張EXCEL表導(dǎo)入到SQL Server中的表kaoshengdata中，并增加id字段，增加錄取年份start year屬性字段，增加考生分?jǐn)?shù)與投檔線分?jǐn)?shù)差differ score字段﹒通過(guò)T-SQL編程，編寫(xiě)觸發(fā)器等方法對(duì)數(shù)據(jù)進(jìn)行處理，處理之后的部分源數(shù)據(jù)見(jiàn)表2﹒

3.2 決策樹(shù)算法應(yīng)用

在學(xué)校里，男女性別人數(shù)差異的問(wèn)題可能會(huì)造成很多其他的問(wèn)題，如宿舍分配、洗澡堂、衛(wèi)生間等與性別相關(guān)的公共設(shè)施都將產(chǎn)生影響﹒采用決策樹(shù)算法對(duì)每個(gè)專(zhuān)業(yè)學(xué)生性別的情況進(jìn)行預(yù)測(cè)，學(xué)生的性別取值只有男和女兩個(gè)值﹒因此可看做0和1的分類(lèi)問(wèn)題﹒在該考生的錄取數(shù)據(jù)中，與學(xué)生的性別相關(guān)的屬性主要是專(zhuān)業(yè)，專(zhuān)業(yè)本身的屬性將會(huì)對(duì)學(xué)生所屬學(xué)科及興趣愛(ài)好有一定影響，而學(xué)生的分?jǐn)?shù)、學(xué)生的考生號(hào)、投檔線、考生所來(lái)自的省份都與性別無(wú)關(guān)聯(lián)﹒因此對(duì)該數(shù)據(jù)建立決策樹(shù)模型﹒根據(jù)樣本集建立分類(lèi)模型，再對(duì)測(cè)試數(shù)據(jù)進(jìn)行預(yù)測(cè)其所屬的性別標(biāo)號(hào)﹒

表2 學(xué)生專(zhuān)業(yè)錄取處理后的數(shù)據(jù)

在ASP.NET所編寫(xiě)的客戶端應(yīng)用程序中，根據(jù)所選擇的專(zhuān)業(yè)，可以分析出該學(xué)生可能的性別及相應(yīng)的概率﹒圖1挖掘結(jié)果顯示我校經(jīng)濟(jì)統(tǒng)計(jì)學(xué)專(zhuān)業(yè)的學(xué)生大部分是女生，是女生的概率為67.9%﹒對(duì)該預(yù)測(cè)結(jié)果進(jìn)行驗(yàn)證，經(jīng)濟(jì)統(tǒng)計(jì)學(xué)專(zhuān)業(yè)錄取的女生有30人，而該專(zhuān)業(yè)的總?cè)藬?shù)為50人，女生占比為34/50(0.68)，預(yù)測(cè)值與實(shí)際值相差約為0.01；同樣地對(duì)城鄉(xiāng)規(guī)劃專(zhuān)業(yè)進(jìn)行預(yù)測(cè)，為女生的概率為51.2%，該專(zhuān)業(yè)總?cè)藬?shù)為281人，女生為144人，占比為51.2%﹒可見(jiàn)采用決策樹(shù)預(yù)測(cè)算法對(duì)性別的預(yù)測(cè)準(zhǔn)確率非常高﹒

圖1 決策樹(shù)數(shù)據(jù)挖掘結(jié)果

該預(yù)測(cè)涉及到的DMX語(yǔ)句如下：

select kaoshengdata.xb,predictprobability(xb) as [probability] from kaoshengdata natural prediction join (select '" + profession + "' as lqzy)as t

其中profession是要預(yù)測(cè)考生所屬的專(zhuān)業(yè)﹒

ASP.NET中的C#語(yǔ)言通過(guò)連接字符串"Provider=MSOLAP.3;Integrated Security=SSPI;Persist Security Info=True;Initial Catalog=kaosheng;Data Source=."與SSAS建立連接，并顯示出預(yù)測(cè)結(jié)果﹒

利用決策樹(shù)算法預(yù)測(cè)專(zhuān)業(yè)的性別結(jié)果數(shù)據(jù)見(jiàn)表3(由于篇幅原因只給出一部分專(zhuān)業(yè)數(shù)據(jù))﹒表3給出了每個(gè)專(zhuān)業(yè)學(xué)生性別的預(yù)測(cè)和實(shí)際結(jié)果，還給出了預(yù)測(cè)結(jié)果與實(shí)際結(jié)果的誤差率，并得出其誤差率在0.01以?xún)?nèi)，預(yù)測(cè)結(jié)果準(zhǔn)確率非常高﹒

表3 決策樹(shù)算法性別預(yù)測(cè)結(jié)果

3.3 貝葉斯算法應(yīng)用

預(yù)測(cè)專(zhuān)業(yè)招生學(xué)生中最可能來(lái)自的省份，據(jù)此可制定相應(yīng)高校招生策略，增加或減少該專(zhuān)業(yè)在該省的招生人數(shù)，如果在該專(zhuān)業(yè)中沒(méi)有或很少的學(xué)生屬于該省，那么可以減少在該省招生人數(shù)，否則增加招生人數(shù)﹒根據(jù)考生的屬性專(zhuān)業(yè)、年份、分?jǐn)?shù)，對(duì)考生所來(lái)自的省份進(jìn)行預(yù)測(cè)﹒由于各屬性之間對(duì)類(lèi)別所屬省份的影響是相互獨(dú)立的，因此對(duì)考生數(shù)據(jù)建立樸素貝葉斯分類(lèi)模型，并對(duì)測(cè)試數(shù)據(jù)進(jìn)行預(yù)測(cè)﹒建立的貝葉斯模型見(jiàn)圖2﹒

圖2 貝葉斯模型

根據(jù)輸入學(xué)生專(zhuān)業(yè)、錄取年份及高考分?jǐn)?shù)預(yù)測(cè)該專(zhuān)業(yè)錄取的學(xué)生來(lái)自的省份及可能的概率﹒

該預(yù)測(cè)涉及到的DMX語(yǔ)句如下：

select kaoshengdata2.sf,predictprobability(sf) as [probability] from kaoshengdata2 natural prediction join (select '"+profession +"' as lqzy,'"+startyear1 +"' as startyear,'"+grade1 +"' as grade)as t

其中profession為學(xué)生的錄取專(zhuān)業(yè)，變量startyear1為考生的錄取年份，變量grade1為考生的高考成績(jī)，預(yù)測(cè)結(jié)果見(jiàn)圖3﹒2016年城鄉(xiāng)規(guī)劃專(zhuān)業(yè)的學(xué)生，最可能來(lái)自的省份為湖南省，其概率為55.3%﹒而在原始數(shù)據(jù)中城鄉(xiāng)規(guī)劃專(zhuān)業(yè)在2016年總共招收了81人，其中湖南的學(xué)生有54人；同年電子科學(xué)與技術(shù)專(zhuān)業(yè)總共招收了74人，來(lái)自湖南的58人，與預(yù)測(cè)的84%的電子科學(xué)與技術(shù)專(zhuān)業(yè)的學(xué)生來(lái)自湖南情況相吻合﹒

利用貝葉斯算法預(yù)測(cè)每個(gè)專(zhuān)業(yè)每年所來(lái)自的省份結(jié)果數(shù)據(jù)見(jiàn)表4(因篇幅原因只給出2016年部分專(zhuān)業(yè)生源數(shù)據(jù))﹒表4給出了部分專(zhuān)業(yè)學(xué)生所來(lái)自省份的預(yù)測(cè)結(jié)果和實(shí)際結(jié)果，并得出其預(yù)測(cè)誤差率在0.2以?xún)?nèi)，具有比較高的準(zhǔn)確率﹒

圖3 貝葉斯數(shù)據(jù)挖掘結(jié)果

表4 貝葉斯算法生源預(yù)測(cè)結(jié)果

4 總結(jié)

本文研究了決策樹(shù)分類(lèi)和貝葉斯分類(lèi)的相關(guān)理論，包括其定義、相關(guān)概念及算法，用SQL Server2014為湖南城市學(xué)院學(xué)生專(zhuān)業(yè)錄取數(shù)據(jù)建立模型并進(jìn)行挖掘分析，采用DMX語(yǔ)句獲取挖掘結(jié)果，為學(xué)校專(zhuān)業(yè)招生制定相應(yīng)決策提供了數(shù)據(jù)支持，通過(guò)C#語(yǔ)言并采用ADOMD.NET對(duì)挖掘結(jié)果進(jìn)行訪問(wèn)，最終把預(yù)測(cè)的結(jié)果顯示在網(wǎng)頁(yè)中﹒本文采用決策樹(shù)分類(lèi)算法對(duì)所錄取的學(xué)生進(jìn)行性別預(yù)測(cè)，預(yù)測(cè)值與實(shí)際結(jié)果的誤差率大小在0.01以?xún)?nèi)；采用貝葉斯算法對(duì)所錄取的學(xué)生可能來(lái)自的省份進(jìn)行預(yù)測(cè)，預(yù)測(cè)值與實(shí)際結(jié)果的誤差率大小在0.2以?xún)?nèi)﹒兩者都具有較高的準(zhǔn)確率﹒

[1]HAN J W, KAMBER M, PEI J, 等. 數(shù)據(jù)挖掘概念與技術(shù)[M]. 北京: 機(jī)械工業(yè)出版社, 2012.

[2]程斐斐, 王子牛, 侯立鐸. 決策樹(shù)算法在Weka平臺(tái)上的數(shù)據(jù)挖掘應(yīng)用[J]. 微型電腦應(yīng)用, 2015, 31(6): 63-65.

[3]張輪, 楊文臣, 劉拓, 等. 基于樸素貝葉斯分類(lèi)的高速公路交通事件檢測(cè)[J]. 同濟(jì)大學(xué)學(xué)報(bào): 自然科學(xué)版, 2014, 42(4): 558-563.

[4]楊雷, 曹翠玲, 孫建國(guó), 等. 改進(jìn)的樸素貝葉斯算法在垃圾郵件過(guò)濾中的研究[J]. 通信學(xué)報(bào), 2017, 38(4): 140-148.

[5]呂昊, 林君, 曾曉獻(xiàn). 改進(jìn)樸素貝葉斯分類(lèi)算法的研究與應(yīng)用[J]. 湖南大學(xué)學(xué)報(bào): 自然科學(xué)版, 2012, 39(12): 56-61.

(責(zé)任編校：龔倫峰)

Application of Decision Tree and Bayes Classification Algorithm in Student Enrollment Data

HUANG Xuehua

(School of Information and Electronic Engineer, Hunan City University, Yiyang, Hunan 413000, China)

Classification algorithm is one of the most important mining theories in data mining. It is widely used in weather forecasting, anti spam, disease diagnosis and other applications. The theory and algorithm of the most widely used decision tree and Bayes are introduced, and applied to student enrollment data of Hunan City University combining with SQL server and ASP.NET to get gender prediction for each major and predict the province students are from. Compare the predicted results with the actual results, it is found that the error rates are within 0.01 and 0.2 respectively.

classification; decision tree; naive Bayes; ASP.NET; SQL Server2014; student enrollment

TP301.6

A

10.3969/j.issn.1672-7304.2017.04.0014

1672–7304(2017)04–0064–04

2017-06-25

黃雪華(1983- )，女，湖南郴州人，講師，碩士，主要從事數(shù)據(jù)庫(kù)、數(shù)據(jù)挖掘研究﹒E-mail: 107531852@qq.com