黃春華，陳忠偉，李石君

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

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

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

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

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

數(shù)據(jù)挖掘；貝葉斯決策樹；分類；招生數(shù)據(jù)；報到預測

招生工作一直是民辦高職院校工作的重中之重，因為生源是其生存之本。如何有針對性地開展招生工作，既能提高新生的報到率又能節(jié)省招生成本，一直是民辦高職院校非常關心的問題之一。數(shù)據(jù)挖掘技術是通過分析大量不完整的、模糊的、隨機的數(shù)據(jù)來發(fā)現(xiàn)隱藏的、潛在有用的知識和規(guī)則的過程[1]。學?？梢酝ㄟ^結合數(shù)據(jù)挖掘技術和招生工作經(jīng)驗，對歷年招生數(shù)據(jù)進行分析，從中尋找到有價值的信息，以此指導學校制定合理的招生計劃，將有限的人力物力用在能“產(chǎn)出”大量生源的地方，提高新生報到率，達到招生效益最大化。

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

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

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

1 貝葉斯決策樹方法

1.1 貝葉斯分類方法

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

(1)設D是訓練元組和它們相關聯(lián)的類標號的集合，通常每個元組用一個k維屬性向量X=(x1,x2,…,xk)表示，描述由k個屬性A1,A2,…,Ak對元組的k個測量。

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

(1)

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

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

(4)當給定的數(shù)據(jù)集中具有許多屬性時，計算p(X|Ci)的開銷可能會很大，可以通過做類條件獨立的樸素假定來降低計算開銷。因此有：

(2)

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

(3)

即被預測的類別標號是使p(X|Ci)p(Ci)最大的類Ci。

1.2 決策樹

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

圖1 決策樹舉例

1.3 貝葉斯決策樹方法簡介

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

圖2 BDT的結構

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

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

2 算法的設計及分析

2.1 算法設計思路

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

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

(4)

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

(5)

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

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

(6)

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

2.2 算法流程

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

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

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

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

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

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

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

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

2.3 算法分析

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

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

(7)

當m=n=k時，計算時間為n2t1+n3t2，則此時算法的時間復雜度為O(n3)。

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

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

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

3 NBDT-ID3算法的應用

3.1 數(shù)據(jù)準備及預處理

因為該學院的新生來源主要分為高考統(tǒng)招生和三校生兩類，其中三校生通過中職對口的招生方式進行錄取，招生來源一般是定向的，因此只對高考統(tǒng)招生的數(shù)據(jù)進行挖掘分析。實驗數(shù)據(jù)來源于該學院2012-2014年實際的高考統(tǒng)招生信息。

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

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

3.2 算法的檢驗與性能評價

為了驗證NBDT-ID3算法在高職新生報到預測

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

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

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

(8)

其中，Y為實際報到但預測是未報到的新生人數(shù)。

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

(9)

其中，Z為預測報到但實際并未報到新生人數(shù)。

最后得到僅應用ID3決策樹算法模型與運用基于NBDT-ID3算法的貝葉斯決策樹模型得到的訓練結果和檢驗結果對比情況，見表2。

表2 兩種決策樹模型訓練結果和

從表2的對比結果可以看出，兩種決策樹模型的訓練結果在覆蓋率和命中率上都比檢驗結果的好，但基于NBDT-ID3算法的決策樹模型比ID3決策樹算法模型無論是在訓練結果還是檢驗結果上覆蓋率和命中率都高一些，說明前者能獲得較好的預測效果。

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

圖3 兩種算法訓練時間和分類時間對比結果

從圖中可以看出，NBDT-ID3算法的訓練時間和分類時間都比ID3算法的長。這是因為在構建決策樹時NBDT-ID3算法需額外插入BN，在分類時NBDT-ID3算法需對選擇BN值為f的節(jié)點進行后驗概率計算，從而造成了額外的時間開銷，但從整體上看，兩者的訓練時間和分類時間相差不大，時間比值保持在1.12～1.2，基本符合理想增長的趨勢。

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

表3 兩種算法數(shù)據(jù)分類的魯棒性檢驗結果對比情況

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

4 結束語

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

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

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

[3] 詹柳春.數(shù)據(jù)挖掘技術在高校招生錄取數(shù)據(jù)中的應用研究[D].廣州:華南理工大學，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] 樊建聰，張問銀，梁永全.基于貝葉斯方法的決策樹分類算法[J].計算機應用，2005，25(12)：2882-2884.

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

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

[9] 王 琦.基于貝葉斯決策樹算法的垃圾郵件識別機制[C]//“智慧城市和綠色IT”2011年通信與信息技術新進展——第八屆中國通信學會學術年會.湖北,武漢：出版者不詳，2011.

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

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

[12] 黃宇達，王迤冉.基于樸素貝葉斯與ID3算法的決策樹分類[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

時間：2016-03-22

中央高校基本科研業(yè)務費專項基金項目(2042014f0057)；湖北省自然科學基金項目(2014CFB289)

黃春華(1985-)，女，碩士，講師，研究方向為數(shù)據(jù)挖掘、SQL數(shù)據(jù)庫技術及應用。

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