貝葉斯決策樹(shù)方法在招生數(shù)據(jù)挖掘中的應(yīng)用

黃春華，陳忠偉，李石君

(1.武漢大學(xué) 計(jì)算機(jī)學(xué)院，湖北 武漢 430072；2.廣西英華國(guó)際職業(yè)學(xué)院 工信學(xué)院，廣西 欽州 535000)

貝葉斯決策樹(shù)方法在招生數(shù)據(jù)挖掘中的應(yīng)用

黃春華1,2，陳忠偉2，李石君1

(1.武漢大學(xué) 計(jì)算機(jī)學(xué)院，湖北 武漢 430072；2.廣西英華國(guó)際職業(yè)學(xué)院 工信學(xué)院，廣西 欽州 535000)

文中首先簡(jiǎn)單介紹了貝葉斯決策樹(shù)方法的基本思想，該方法結(jié)合了貝葉斯分類(lèi)的先驗(yàn)信息方法和決策樹(shù)分類(lèi)的信息增益方法的優(yōu)點(diǎn)，加入貝葉斯節(jié)點(diǎn)彌補(bǔ)了決策樹(shù)不能處理具有二義性或存在缺失值數(shù)據(jù)的缺點(diǎn)。在此基礎(chǔ)上，文中設(shè)計(jì)了一種基于樸素貝葉斯方法和ID3算法的貝葉斯決策樹(shù)算法——NBDT-ID3算法，并給出了該算法的設(shè)計(jì)及分析過(guò)程。然后將該算法應(yīng)用到高職招生數(shù)據(jù)挖掘中，對(duì)新生報(bào)到情況進(jìn)行分析與預(yù)測(cè)，并在Matlab環(huán)境下進(jìn)行了實(shí)驗(yàn)驗(yàn)證。實(shí)驗(yàn)結(jié)果表明，NBDT-ID3算法在付出一定時(shí)間代價(jià)的情況下，不僅可以獲得更高的分類(lèi)精度，而且在處理二義性、不完整或不一致數(shù)據(jù)方面具有更好的效果。

數(shù)據(jù)挖掘；貝葉斯決策樹(shù)；分類(lèi)；招生數(shù)據(jù)；報(bào)到預(yù)測(cè)

招生工作一直是民辦高職院校工作的重中之重，因?yàn)樯词瞧渖嬷尽Ｈ绾斡嗅槍?duì)性地開(kāi)展招生工作，既能提高新生的報(bào)到率又能節(jié)省招生成本，一直是民辦高職院校非常關(guān)心的問(wèn)題之一。數(shù)據(jù)挖掘技術(shù)是通過(guò)分析大量不完整的、模糊的、隨機(jī)的數(shù)據(jù)來(lái)發(fā)現(xiàn)隱藏的、潛在有用的知識(shí)和規(guī)則的過(guò)程[1]。學(xué)校可以通過(guò)結(jié)合數(shù)據(jù)挖掘技術(shù)和招生工作經(jīng)驗(yàn)，對(duì)歷年招生數(shù)據(jù)進(jìn)行分析，從中尋找到有價(jià)值的信息，以此指導(dǎo)學(xué)校制定合理的招生計(jì)劃，將有限的人力物力用在能“產(chǎn)出”大量生源的地方，提高新生報(bào)到率，達(dá)到招生效益最大化。

目前用于招生數(shù)據(jù)挖掘的方法有關(guān)聯(lián)規(guī)則、決策樹(shù)分類(lèi)、支持向量機(jī)等[2-3]，但是每一類(lèi)方法都有一定的應(yīng)用局限性。決策樹(shù)分類(lèi)算法是以實(shí)例為基礎(chǔ)的歸納學(xué)習(xí)算法，通過(guò)信息增益來(lái)構(gòu)建決策樹(shù)，只需要在訓(xùn)練和測(cè)試這兩個(gè)階段進(jìn)行簡(jiǎn)單的比較，對(duì)數(shù)據(jù)類(lèi)別的要求不高，計(jì)算過(guò)程簡(jiǎn)單，主要著眼于從一組給定的無(wú)次序、無(wú)規(guī)則樣本數(shù)據(jù)中推理出以決策樹(shù)表示的分類(lèi)規(guī)則，結(jié)果表現(xiàn)直觀[4]。但是該類(lèi)算法的主要缺點(diǎn)是對(duì)缺失或二義性數(shù)據(jù)難以產(chǎn)生正確的分支，以致影響整個(gè)決策樹(shù)的生成，從而降低了分類(lèi)的準(zhǔn)確性[4]。針對(duì)這個(gè)不足之處，可以將貝葉斯分類(lèi)方法引入決策樹(shù)學(xué)習(xí)模型中，前者具有堅(jiān)實(shí)的數(shù)學(xué)基礎(chǔ)且算法具有簡(jiǎn)單直觀、易實(shí)現(xiàn)、時(shí)空開(kāi)銷(xiāo)小、健壯性小等優(yōu)點(diǎn)[5]。這樣不僅可以更好地處理包含不一致性或不完整等非規(guī)律性數(shù)據(jù)的集合，還可以將先驗(yàn)知識(shí)與概率背景融入決策樹(shù)分類(lèi)模型中[6]。

目前基于貝葉斯決策樹(shù)的數(shù)據(jù)挖掘算法已經(jīng)得到許多學(xué)者的研究并被應(yīng)用到不同的領(lǐng)域中。尹婷等[7]將基于貝葉斯決策樹(shù)的方法應(yīng)用到電信企業(yè)客戶(hù)流失分析與預(yù)測(cè)中；徐哲等[8]將貝葉斯決策樹(shù)方法應(yīng)用到識(shí)別英文現(xiàn)在分詞的詞性中；王琦[9]構(gòu)建了一種基于貝葉斯決策樹(shù)算法的垃圾郵件識(shí)別機(jī)制。

在簡(jiǎn)單介紹了貝葉斯決策樹(shù)方法基本思想的基礎(chǔ)之上，文中詳細(xì)給出了一種基于樸素貝葉斯方法和ID3算法的貝葉斯決策樹(shù)分類(lèi)算法，并根據(jù)民辦高職院校招生工作及其數(shù)據(jù)特點(diǎn)，將該算法應(yīng)用到高職招生數(shù)據(jù)挖掘中，主要對(duì)新生報(bào)到情況的分析與預(yù)測(cè)進(jìn)行了初步研究。

1 貝葉斯決策樹(shù)方法

1.1 貝葉斯分類(lèi)方法

貝葉斯分類(lèi)方法基于貝葉斯定理，其關(guān)鍵在于使用概率表示各種形式的不確定性，即通過(guò)變換事件的先驗(yàn)概率及后驗(yàn)概率，配合決定分類(lèi)特性的各屬性彼此間是相互獨(dú)立的假設(shè)來(lái)預(yù)測(cè)分類(lèi)的結(jié)果[10]。下面以樸素貝葉斯(Na?ve Bayesian)分類(lèi)方法為例，給出一個(gè)貝葉斯分類(lèi)方法的工作過(guò)程[11-12]。

(1)設(shè)D是訓(xùn)練元組和它們相關(guān)聯(lián)的類(lèi)標(biāo)號(hào)的集合，通常每個(gè)元組用一個(gè)k維屬性向量X=(x1,x2,…,xk)表示，描述由k個(gè)屬性A1,A2,…,Ak對(duì)元組的k個(gè)測(cè)量。

(2)假定有l(wèi)個(gè)類(lèi)別C1,C2,…,Cl，給定元組X，分類(lèi)法將預(yù)測(cè)X屬于具有最高后驗(yàn)概率的類(lèi)別(在條件X下)。根據(jù)貝葉斯定理的公式可得：

(1)

其中：p(Ci)是先驗(yàn)概率；p(Ci|X)是后驗(yàn)概率。

由此可知，樸素貝葉斯分類(lèi)法預(yù)測(cè)X屬于類(lèi)別Ci當(dāng)且僅當(dāng)p(Ci|X)>p(Cj|X)，其中1≤j≤l，且i≠j。

(4)當(dāng)給定的數(shù)據(jù)集中具有許多屬性時(shí)，計(jì)算p(X|Ci)的開(kāi)銷(xiāo)可能會(huì)很大，可以通過(guò)做類(lèi)條件獨(dú)立的樸素假定來(lái)降低計(jì)算開(kāi)銷(xiāo)。因此有：

(2)

(5)為了預(yù)測(cè)X的類(lèi)別標(biāo)號(hào)，對(duì)每個(gè)類(lèi)別Ci，計(jì)算p(X|Ci)p(Ci)。則樸素貝葉斯分類(lèi)法預(yù)測(cè)X屬于類(lèi)別Ci可最終表述為當(dāng)且僅當(dāng)p(X|Ci)p(Ci)>p(X|Cj)p(Cj)，其中1≤j≤l，i≠j。根據(jù)式(2)可進(jìn)一步得到：

(3)

即被預(yù)測(cè)的類(lèi)別標(biāo)號(hào)是使p(X|Ci)p(Ci)最大的類(lèi)Ci。

1.2 決策樹(shù)

決策樹(shù)(Decision Tree)又稱(chēng)為判定樹(shù)，是一種以樹(shù)狀結(jié)構(gòu)形式來(lái)表達(dá)的預(yù)測(cè)分析模型，是數(shù)據(jù)挖掘技術(shù)中一種重要的分類(lèi)方法。根據(jù)給定的一個(gè)類(lèi)標(biāo)號(hào)未知的實(shí)例，可以在決策樹(shù)上測(cè)試該實(shí)例的屬性值，并跟蹤一條由根到葉子節(jié)點(diǎn)的路徑，則該葉子節(jié)點(diǎn)就存放著該實(shí)例的類(lèi)預(yù)測(cè)。決策樹(shù)的主要優(yōu)點(diǎn)是描述簡(jiǎn)單，分類(lèi)速度快，特別適合大規(guī)模的數(shù)據(jù)處理[4]。圖1是一棵決策樹(shù)。

圖1 決策樹(shù)舉例

1.3 貝葉斯決策樹(shù)方法簡(jiǎn)介

定義：在原有決策樹(shù)的兩個(gè)屬性測(cè)試節(jié)點(diǎn)之間加入一個(gè)能夠根據(jù)貝葉斯原理進(jìn)行函數(shù)計(jì)算[13]的新節(jié)點(diǎn)，該節(jié)點(diǎn)即是貝葉斯節(jié)點(diǎn)(Bayesian Node,BN)。相應(yīng)地將具有貝葉斯節(jié)點(diǎn)的決策樹(shù)稱(chēng)為貝葉斯決策樹(shù)(Bayesian Decision Tree,BDT)，其結(jié)構(gòu)如圖2所示。

圖2 BDT的結(jié)構(gòu)

由圖2可知，BN包含兩個(gè)值：0和f。當(dāng)BN取值為0時(shí)，該節(jié)點(diǎn)只需根據(jù)屬性測(cè)試條件θ直接轉(zhuǎn)向下一個(gè)屬性測(cè)試節(jié)點(diǎn)，不必進(jìn)行任何計(jì)算；當(dāng)BN取值為f時(shí)，該節(jié)點(diǎn)需要計(jì)算函數(shù)f的值，并根據(jù)屬性測(cè)試條件θ轉(zhuǎn)向下一個(gè)屬性測(cè)試節(jié)點(diǎn)，即當(dāng)BN取值為f時(shí)，下一個(gè)屬性節(jié)點(diǎn)的選擇依賴(lài)于兩點(diǎn)：函數(shù)f的值和屬性測(cè)試條件θ。這里的函數(shù)f根據(jù)具體情況可以是樸素貝葉斯公式也可以是其他貝葉斯公式。

需要說(shuō)明的一點(diǎn)是，當(dāng)根據(jù)函數(shù)f和屬性測(cè)試條件θ進(jìn)行下一屬性節(jié)點(diǎn)的選擇時(shí)，都采用IF……THEN……的表達(dá)形式進(jìn)行描述[6]。

2 算法的設(shè)計(jì)及分析

2.1 算法設(shè)計(jì)思路

根據(jù)貝葉斯決策樹(shù)分類(lèi)算法的基本思想，以下給出一種基于樸素貝葉斯方法和ID3算法的貝葉斯決策樹(shù)分類(lèi)算法(NBDT-ID3)的設(shè)計(jì)思路：

(1)當(dāng)使用決策樹(shù)的信息增益方法就可確定選擇某個(gè)屬性的分支時(shí)，BN的取值為0。其中ID3算法信息增益的計(jì)算方法[11]如下所述：

(4)

假設(shè)要按某個(gè)屬性A劃分D中的元組，其中屬性A根據(jù)訓(xùn)練數(shù)據(jù)的觀測(cè)值具有v個(gè)不同值{a1,a2,…,av}。可以用屬性A將D劃分為v個(gè)子集{D1,D2,…,Dv}，其中Dj(j=1,2,…,v)包含D中的元組，它們對(duì)應(yīng)于屬性A的值為aj。如果A作為測(cè)試屬性，那么這些子集對(duì)應(yīng)于由D的節(jié)點(diǎn)生長(zhǎng)出來(lái)的分枝?；诎磳傩訟劃分對(duì)D的元組分類(lèi)所需要的期望信息為：

(5)

信息增益定義為原來(lái)的信息需求(僅基于類(lèi)比例)與新的信息需求(對(duì)A劃分后)之間的差值，即：

Gain(A)=Info(D)-InfoA(D)

(6)

(2)當(dāng)數(shù)據(jù)分類(lèi)具有二義性，即數(shù)據(jù)對(duì)象的分類(lèi)類(lèi)別無(wú)法確定或?qū)傩灾祦G失時(shí)，BN的取值為f。這里的f選擇為樸素貝葉斯公式，即根據(jù)以前的經(jīng)驗(yàn)知識(shí)或?qū)嶒?yàn)結(jié)果得出該數(shù)據(jù)對(duì)象的先驗(yàn)概率值，再以此值來(lái)判斷可以先將其分到某些類(lèi)中，然后運(yùn)用貝葉斯分類(lèi)方法確定這些類(lèi)的后驗(yàn)概率值，最后選擇后驗(yàn)概率值最大的那一類(lèi)作為該數(shù)據(jù)對(duì)象的所屬類(lèi)別[6]。

2.2 算法流程

根據(jù)以上設(shè)計(jì)思路，給出NBDT-ID3算法流程：

輸入：數(shù)據(jù)集{X1,X2,…,Xn}，其中每個(gè)數(shù)據(jù)Xi具有m個(gè)屬性xij(i=1,2,…,n;j=1,2,…,m);

輸出：顯示或打印出對(duì)數(shù)據(jù)集{X1,X2,…,Xn}已劃分到各個(gè)相關(guān)類(lèi)別Ck(k=1,2,…)中的數(shù)據(jù)。

(1)根據(jù)事先給定的類(lèi)別特征或?qū)傩源_定要生成的類(lèi)別集合{C1,C2,…,Cl}，并確定類(lèi)別數(shù)目l。

(2)運(yùn)用2.1節(jié)中信息增益的計(jì)算方法先確定優(yōu)先判斷的屬性，然后確定要進(jìn)行分類(lèi)的數(shù)據(jù)Xi(i=1,2,…)的某個(gè)或某些屬性，屬性值與相應(yīng)的類(lèi)別相關(guān)。

(3)當(dāng)屬性選擇和數(shù)據(jù)分類(lèi)都無(wú)二義性時(shí)，BN的取值為0，直接根據(jù)屬性測(cè)試條件轉(zhuǎn)向下一個(gè)屬性測(cè)試，轉(zhuǎn)到(2)，否則轉(zhuǎn)到(4)。

(4)對(duì)Xi進(jìn)行分類(lèi)。若Xi確定對(duì)應(yīng)某一類(lèi)別Ck，則將Xi劃分到該類(lèi)別中；若Xi不能確定劃分到哪一個(gè)類(lèi)別中，而是與某些類(lèi)別都可能相關(guān)，則根據(jù)1.1中所述的樸素貝葉斯分類(lèi)方法計(jì)算出最大的p(Xi|Ck)p(Ck)值，并將Xi劃分到相應(yīng)類(lèi)別中。

(5)BN的取值為f，且f=max(p(Xi|Ck)p(Ck))，轉(zhuǎn)到(3)。

2.3 算法分析

NBDT-ID3算法仍然具有與決策樹(shù)分類(lèi)算法的產(chǎn)生規(guī)則易于理解、分類(lèi)速度相對(duì)較快等相似的優(yōu)點(diǎn)[6]。該算法主要包括兩項(xiàng)工作：判斷是否要計(jì)算f值和判斷是否要計(jì)算屬性的后驗(yàn)概率值。根據(jù)上述的算法流程，最壞的情況就是需要計(jì)算所有數(shù)據(jù)的后驗(yàn)概率值。假設(shè)共有n個(gè)數(shù)據(jù)待分類(lèi)，且每個(gè)數(shù)據(jù)有m個(gè)屬性，需要把它們劃分到k個(gè)類(lèi)別中，計(jì)算一個(gè)數(shù)據(jù)的后驗(yàn)概率值需要時(shí)間t1，計(jì)算信息增益值需要時(shí)間t2，此時(shí)算法的計(jì)算時(shí)間為：

(t1+mt2)·n·k=nkt1+nmt2

(7)

當(dāng)m=n=k時(shí)，計(jì)算時(shí)間為n2t1+n3t2，則此時(shí)算法的時(shí)間復(fù)雜度為O(n3)。

NBDT-ID3算法自身具有的優(yōu)點(diǎn)如下：

(1)具有更高的分類(lèi)精度和準(zhǔn)確率。分類(lèi)一般按照數(shù)據(jù)的某個(gè)或某些屬性進(jìn)行，假如根據(jù)數(shù)據(jù)集計(jì)算出來(lái)的兩個(gè)不同屬性的信息增益值相等，則屬性的選擇出現(xiàn)了二義性。大量的數(shù)據(jù)二義性必然會(huì)對(duì)數(shù)據(jù)集的分類(lèi)精度和準(zhǔn)確率產(chǎn)生不良影響。而NBDT-ID3算法通過(guò)引入樸素貝葉斯方法，可很好地利用先驗(yàn)信息去處理這些數(shù)據(jù)二義性，提高分類(lèi)的精度和準(zhǔn)確率。

(2)具有更強(qiáng)的分類(lèi)魯棒性。數(shù)據(jù)挖掘一般處理的都是海量數(shù)據(jù)，這些數(shù)據(jù)由于主客觀原因難免會(huì)存在大量不完整、不一致和噪聲等干擾數(shù)據(jù)?？梢酝ㄟ^(guò)預(yù)處理的方法[11]對(duì)這些干擾數(shù)據(jù)進(jìn)行處理，但該解決方法一般較為耗時(shí)耗力。NBDT-ID3算法通過(guò)運(yùn)用樸素貝葉斯方法，可以根據(jù)歷史數(shù)據(jù)的先驗(yàn)信息或經(jīng)驗(yàn)來(lái)消除不一致的數(shù)據(jù)，平滑不完整的數(shù)據(jù)，排除噪聲數(shù)據(jù)等[6]，相對(duì)而言省時(shí)省力，且具有更好的處理效果，從而增強(qiáng)了數(shù)據(jù)分類(lèi)的魯棒性。

3 NBDT-ID3算法的應(yīng)用

3.1 數(shù)據(jù)準(zhǔn)備及預(yù)處理

因?yàn)樵搶W(xué)院的新生來(lái)源主要分為高考統(tǒng)招生和三校生兩類(lèi)，其中三校生通過(guò)中職對(duì)口的招生方式進(jìn)行錄取，招生來(lái)源一般是定向的，因此只對(duì)高考統(tǒng)招生的數(shù)據(jù)進(jìn)行挖掘分析。實(shí)驗(yàn)數(shù)據(jù)來(lái)源于該學(xué)院2012-2014年實(shí)際的高考統(tǒng)招生信息。

因?yàn)椴煌攴菡猩鷶?shù)據(jù)表的格式有所差異，存在著相同含義的屬性用不同字段名稱(chēng)表示的情況。比如在2012年數(shù)據(jù)表中用“入學(xué)成績(jī)”表示高考成績(jī)，在2013年數(shù)據(jù)表中則用“總分”表示高考成績(jī)。為了保證數(shù)據(jù)挖掘的有效性，必須先將這些屬性名稱(chēng)統(tǒng)一表示。經(jīng)過(guò)初步分析，首先刪除掉數(shù)據(jù)集中那些明顯與數(shù)據(jù)挖掘不相關(guān)的字段，比如年份、考生姓名、身份證號(hào)、聯(lián)系地址等，初步保留那些可能與招生數(shù)據(jù)挖掘相關(guān)的字段：考生號(hào)、性別、考生類(lèi)別、高考成績(jī)、報(bào)考科類(lèi)、錄取專(zhuān)業(yè)、錄取專(zhuān)業(yè)代碼和報(bào)到情況。

根據(jù)高職招生業(yè)務(wù)及其數(shù)據(jù)的特點(diǎn)，可以對(duì)招生數(shù)據(jù)做進(jìn)一步的處理以更有利于數(shù)據(jù)挖掘工作的進(jìn)行。依據(jù)全國(guó)高職高專(zhuān)專(zhuān)業(yè)目錄中專(zhuān)業(yè)代碼的含義，可以將錄取專(zhuān)業(yè)進(jìn)行泛化處理[11]；依據(jù)考生號(hào)的組成含義，可以得到每位新生的生源地區(qū)信息；采用合適的數(shù)學(xué)方法[3]對(duì)高考成績(jī)進(jìn)行離散化處理，劃分出每個(gè)考生的成績(jī)等級(jí)。最終處理得到的數(shù)據(jù)如表1所示。

3.2 算法的檢驗(yàn)與性能評(píng)價(jià)

為了驗(yàn)證NBDT-ID3算法在高職新生報(bào)到預(yù)測(cè)

表1 最終處理得到的數(shù)據(jù)示例

中的應(yīng)用性能，在Matlab環(huán)境下分別運(yùn)用ID3決策樹(shù)算法和NBDT-ID3算法對(duì)預(yù)處理后的招生數(shù)據(jù)集進(jìn)行訓(xùn)練和測(cè)試，并對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行對(duì)比說(shuō)明。預(yù)處理后的招生數(shù)據(jù)集共有2 625條新生信息記錄，其中報(bào)到新生人數(shù)1 782人，未報(bào)到新生人數(shù)843人。隨機(jī)抽取其中2/3的數(shù)據(jù)作為訓(xùn)練集建立基于貝葉斯決策樹(shù)預(yù)測(cè)模型得到預(yù)測(cè)結(jié)果，再運(yùn)用該模型對(duì)剩余的1/3數(shù)據(jù)進(jìn)行新生報(bào)到情況的預(yù)測(cè)，然后從覆蓋率和命中率兩個(gè)方面對(duì)預(yù)測(cè)結(jié)果和實(shí)際結(jié)果進(jìn)行對(duì)比分析。

覆蓋率：實(shí)際報(bào)到預(yù)測(cè)也是報(bào)到的新生人數(shù)X占所有實(shí)際報(bào)到的新生人數(shù)的比例，它是描述模型普適性的指標(biāo)[7]，用α表示，其計(jì)算公式為：

(8)

其中，Y為實(shí)際報(bào)到但預(yù)測(cè)是未報(bào)到的新生人數(shù)。

命中率：實(shí)際報(bào)到預(yù)測(cè)也是報(bào)到的新生人數(shù)X占所有預(yù)測(cè)為報(bào)到的新生人數(shù)的比例，它是描述模型精確度的指標(biāo)[7]，用β表示，其計(jì)算公式為：

(9)

其中，Z為預(yù)測(cè)報(bào)到但實(shí)際并未報(bào)到新生人數(shù)。

最后得到僅應(yīng)用ID3決策樹(shù)算法模型與運(yùn)用基于NBDT-ID3算法的貝葉斯決策樹(shù)模型得到的訓(xùn)練結(jié)果和檢驗(yàn)結(jié)果對(duì)比情況，見(jiàn)表2。

表2 兩種決策樹(shù)模型訓(xùn)練結(jié)果和

從表2的對(duì)比結(jié)果可以看出，兩種決策樹(shù)模型的訓(xùn)練結(jié)果在覆蓋率和命中率上都比檢驗(yàn)結(jié)果的好，但基于NBDT-ID3算法的決策樹(shù)模型比ID3決策樹(shù)算法模型無(wú)論是在訓(xùn)練結(jié)果還是檢驗(yàn)結(jié)果上覆蓋率和命中率都高一些，說(shuō)明前者能獲得較好的預(yù)測(cè)效果。

另外，建模規(guī)則和實(shí)施分類(lèi)的時(shí)間也會(huì)對(duì)系統(tǒng)效率和性能產(chǎn)生影響[14]，所以有必要對(duì)算法的訓(xùn)練時(shí)間和分類(lèi)時(shí)間進(jìn)行驗(yàn)證和比較，以進(jìn)一步評(píng)價(jià)算法的性能。同樣在Matlab環(huán)境下，對(duì)NBDT-ID3算法與ID3算法在數(shù)據(jù)集訓(xùn)練執(zhí)行過(guò)程中所需的訓(xùn)練時(shí)間之比和分類(lèi)時(shí)間之比進(jìn)行驗(yàn)證和比較，結(jié)果如圖3所示。

圖3 兩種算法訓(xùn)練時(shí)間和分類(lèi)時(shí)間對(duì)比結(jié)果

從圖中可以看出，NBDT-ID3算法的訓(xùn)練時(shí)間和分類(lèi)時(shí)間都比ID3算法的長(zhǎng)。這是因?yàn)樵跇?gòu)建決策樹(shù)時(shí)NBDT-ID3算法需額外插入BN，在分類(lèi)時(shí)NBDT-ID3算法需對(duì)選擇BN值為f的節(jié)點(diǎn)進(jìn)行后驗(yàn)概率計(jì)算，從而造成了額外的時(shí)間開(kāi)銷(xiāo)，但從整體上看，兩者的訓(xùn)練時(shí)間和分類(lèi)時(shí)間相差不大，時(shí)間比值保持在1.12～1.2，基本符合理想增長(zhǎng)的趨勢(shì)。

為了驗(yàn)證NBDT-ID3算法數(shù)據(jù)分類(lèi)的魯棒性，分別從UCI機(jī)器學(xué)習(xí)數(shù)據(jù)庫(kù)Anneal、Balance-scale、Vowel中隨機(jī)抽取3個(gè)數(shù)據(jù)集進(jìn)行分類(lèi)測(cè)試，同樣在Matlab環(huán)境下運(yùn)用ID3決策樹(shù)和NBDT-ID3算法對(duì)數(shù)據(jù)集進(jìn)行分類(lèi)，比較這兩種算法在建樹(shù)時(shí)間之比和分類(lèi)精度上的情況，結(jié)果如表3所示。

表3 兩種算法數(shù)據(jù)分類(lèi)的魯棒性檢驗(yàn)結(jié)果對(duì)比情況

從表3中可以看出，在樣本缺失率較高的情況下，NBDT-ID3算法因?yàn)橐?jì)算更多選擇BN值為f的節(jié)點(diǎn)的后驗(yàn)概率值,所以比ID3算法需要更長(zhǎng)的建樹(shù)時(shí)間，但在付出時(shí)間代價(jià)的情況下，NBDT-ID3算法能較好地提高分類(lèi)精度。由此說(shuō)明，在付出一定時(shí)間代價(jià)的情況下，NBDT-ID3算法不僅能提高分類(lèi)精度，而且在處理數(shù)據(jù)不完整、不一致等缺失樣本時(shí)具有更強(qiáng)的分類(lèi)魯棒性。

4 結(jié)束語(yǔ)

根據(jù)貝葉斯決策樹(shù)方法的基本思想，設(shè)計(jì)了一種基于樸素貝葉斯方法和ID3算法的貝葉斯決策樹(shù)分類(lèi)算法——NBDT-ID3算法，并詳細(xì)給出了該算法的設(shè)計(jì)及分析過(guò)程。然后將該算法應(yīng)用到高職招生數(shù)據(jù)挖掘中，對(duì)新生報(bào)到情況進(jìn)行預(yù)測(cè)分析。實(shí)驗(yàn)結(jié)果表明，NBDT-ID3算法在付出一定時(shí)間代價(jià)的情況下，可以獲得更好的分類(lèi)效果，并且對(duì)具有二義性、不完整或不一致的數(shù)據(jù)具有更好的處理效果。如何更加有效地將這種基于貝葉斯決策樹(shù)的分類(lèi)方法運(yùn)用到民辦高職院校招生數(shù)據(jù)的挖掘分析中，更好地為學(xué)校招生工作提供科學(xué)而直觀的決策支持，是接下來(lái)需要進(jìn)一步研究的工作。

[1] 朱志勇，徐長(zhǎng)梅，劉志兵，等.基于貝葉斯網(wǎng)絡(luò)的客戶(hù)流失分析研究[J].計(jì)算機(jī)工程與科學(xué)，2013，35(3)：155-158.

[2] 孫曉瑩，郭飛燕.數(shù)據(jù)挖掘在高校招生預(yù)測(cè)中的應(yīng)用研究[J].計(jì)算機(jī)仿真，2012，29(4)：387-391.

[3] 詹柳春.數(shù)據(jù)挖掘技術(shù)在高校招生錄取數(shù)據(jù)中的應(yīng)用研究[D].廣州:華南理工大學(xué)，2012.

[4]QuilanJR.Inductionofdecisiontree[J].MachineLearning,1986,1(1):81-106.

[5]Palacios-AlonsoMA,BrizuelaCA,SucarLE.EvolutionarylearningofdynamicNa?veBayesianclassifiers[J].JournalofAutomatedReasoning,2010,45(1):21-37.

[6] 樊建聰，張問(wèn)銀，梁永全.基于貝葉斯方法的決策樹(shù)分類(lèi)算法[J].計(jì)算機(jī)應(yīng)用，2005，25(12)：2882-2884.

[7] 尹 婷，馬 軍，覃錫忠，等.貝葉斯決策樹(shù)在客戶(hù)流失預(yù)測(cè)中的應(yīng)用[J].計(jì)算機(jī)工程與應(yīng)用，2014，50(7)：125-128.

[8] 徐 哲，劉 循.貝葉斯決策樹(shù)在英文現(xiàn)在分詞詞性識(shí)別中的應(yīng)用[J].計(jì)算機(jī)應(yīng)用，2009，29(9)：2571-2574.

[9] 王 琦.基于貝葉斯決策樹(shù)算法的垃圾郵件識(shí)別機(jī)制[C]//“智慧城市和綠色I(xiàn)T”2011年通信與信息技術(shù)新進(jìn)展——第八屆中國(guó)通信學(xué)會(huì)學(xué)術(shù)年會(huì).湖北,武漢：出版者不詳，2011.

[10] 張依楊，向 陽(yáng)，蔣銳權(quán)，等.樸素貝葉斯算法的MapReduce并行化分析與實(shí)現(xiàn)[J].計(jì)算機(jī)技術(shù)與發(fā)展，2013,23(3)：23-26.

[11]HanJiawei，KamberM，PeiJian.數(shù)據(jù)挖掘概念與技術(shù)[M].北京：機(jī)械工業(yè)出版社，2014：217-218.

[12] 黃宇達(dá)，王迤冉.基于樸素貝葉斯與ID3算法的決策樹(shù)分類(lèi)[J].計(jì)算機(jī)工程，2012，38(14)：41-43.

[13]FriedmanN,GeigerD,GoldszmidtM.Bayesiannetworkclassifiers[J].MachineLearning,1997,29(2-3):131-163.

[14]JingY,PavloviV,RehgJM.BoostedBayesiannetworkclassifiers[J].MachineLearning,2008,73(2):155-184.

Application of Bayesian Decision Tree Method in Admission Data Mining

HUANG Chun-hua1,2,CHEN Zhong-wei2,LI Shi-jun1

(1.School of Computer,Wuhan University,Wuhan 430072,China; 2.Dept. of Industry and Information,Guangxi Talent International College,Qinzhou 535000,China)

It simply introduces the basic thought of Bayesian decision tree method in this paper,which takes advantage of the prior information method for Bayesian classification and the information gain method of decision tree,and makes up for the decision tree cannot handle the ambiguity data and the missing value by adding Bayesian node.On this basis,a Bayesian decision tree algorithm based on Na?ve Bayesian method and ID3 algorithm is presented named NBDT-ID3 algorithm.The algorithm process of the design and analysis is introduced.Then the algorithm is applied to higher vocational admission data mining,which analyzes and forecasts the new student registration.It is tested and verified under the Matlab environment.The experimental results show that NBDT-ID3 algorithm not only can get higher classification accuracy but also behave well in handling the ambiguity,incomplete or incongruous data in the case of paying certain of time.

data mining;Bayesian decision tree;classification;admission data;registration forecasting

2015-07-15

2015-10-21

時(shí)間：2016-03-22

中央高校基本科研業(yè)務(wù)費(fèi)專(zhuān)項(xiàng)基金項(xiàng)目(2042014f0057)；湖北省自然科學(xué)基金項(xiàng)目(2014CFB289)

黃春華(1985-)，女，碩士，講師，研究方向?yàn)閿?shù)據(jù)挖掘、SQL數(shù)據(jù)庫(kù)技術(shù)及應(yīng)用。

http://www.cnki.net/kcms/detail/61.1450.TP.20160322.1521.072.html

TP301.6

A

1673-629X(2016)04-0114-05

10.3969/j.issn.1673-629X.2016.04.025