趙高長，王 欣,2，張仲華，韓 苗，魏 嵬

(1. 西安科技大學(xué) 理學(xué)院，西安 710054；2. 養(yǎng)生堂有限公司，杭州 310007；3. 西安理工大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，西安 710048)

基于MWST+T-K2結(jié)構(gòu)學(xué)習(xí)算法的貝葉斯分類器

趙高長1，王 欣1,2，張仲華1，韓 苗1，魏 嵬3

(1. 西安科技大學(xué) 理學(xué)院，西安 710054；2. 養(yǎng)生堂有限公司，杭州 310007；3. 西安理工大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，西安 710048)

針對K2算法在構(gòu)建貝葉斯分類器時節(jié)點(diǎn)排序不同影響分類準(zhǔn)確率的問題，提出了一種MWST+T- K2結(jié)構(gòu)學(xué)習(xí)算法，運(yùn)用Matlab軟件的BNT工具箱構(gòu)建了MWST+T- K2分類器，并經(jīng)過NBC、TANC、MWST和MWST+T- K2分類器對UCI數(shù)據(jù)庫的24個分類數(shù)據(jù)集進(jìn)行分類檢驗(yàn).結(jié)果表明，對4種分類器在24個數(shù)據(jù)集上的分類水平進(jìn)行整體與兩兩比較時，MWST+T- K2分類器的分類水平均最優(yōu)；在小數(shù)據(jù)集上比較時，MWST+T- K2分類器的分類水平取得全局最優(yōu)，未取得局部最優(yōu)；在大數(shù)據(jù)集上比較時，未取得全局或局部最優(yōu)，低于TANC的分類水平.所以，MWST+T- K2結(jié)構(gòu)學(xué)習(xí)算法是一種適合構(gòu)建小數(shù)據(jù)集貝葉斯分類器的方法.

貝葉斯網(wǎng)絡(luò)； 貝葉斯分類器； MWST+T- K2算法； 分類檢驗(yàn)

將貝葉斯網(wǎng)絡(luò)(Bayesian network)[1]中代表類別的節(jié)點(diǎn)作為類節(jié)點(diǎn),其余節(jié)點(diǎn)作為屬性節(jié)點(diǎn),貝葉斯網(wǎng)絡(luò)就成為了貝葉斯分類器[2]，其分類準(zhǔn)確率受網(wǎng)絡(luò)結(jié)構(gòu)的影響.早期的樸素貝葉斯分類器(Navie Bayes Classifier, NBC)假定各屬性節(jié)點(diǎn)相互獨(dú)立，雖然在初期取得了一定的分類精度，但卻并不適合一些研究領(lǐng)域[3].Friedman在NBC與最大加權(quán)生成樹[4](Maximum Weight Spanning Tree, MWST)的基礎(chǔ)上，利用條件互信息函數(shù)構(gòu)造出樹擴(kuò)展的樸素貝葉斯分類器(Tree Augmented Navie Bayes Classifier, TANC)，TANC在NBC的結(jié)構(gòu)基礎(chǔ)上允許各屬性節(jié)點(diǎn)間構(gòu)成一棵樹，但規(guī)定各屬性節(jié)點(diǎn)最多只能有一個非類父節(jié)點(diǎn)[5].這種結(jié)構(gòu)充分應(yīng)用了各屬性節(jié)點(diǎn)間的信息，使TANC在一些數(shù)據(jù)集上的分類準(zhǔn)確率有所提升[6].近年來一些學(xué)者提出使用K2算法構(gòu)建貝葉斯分類器[7，8].K2算法在正確的節(jié)點(diǎn)排序下能夠獲得較好的網(wǎng)絡(luò)結(jié)構(gòu)，但是獲得一個正確的節(jié)點(diǎn)排序是困難的[9].對該問題研究的進(jìn)展比較緩慢,早期的研究學(xué)者使用遺傳算法或啟發(fā)式算法確定節(jié)點(diǎn)排序，在獲得節(jié)點(diǎn)排序的同時往往伴隨著局部最優(yōu)、計(jì)算代價大等問題[10]；2008年Chen 提出使用信息熵確定節(jié)點(diǎn)排序，使K2算法的結(jié)構(gòu)學(xué)習(xí)獲得了較好效果[11]，同時簡要提及使用該方法后K2分類器的性能[12]；2014年Ko利用狄利克雷分布提出新的評分函數(shù)改進(jìn)了Chen的方法，并通過實(shí)驗(yàn)表明所提方法在結(jié)構(gòu)學(xué)習(xí)上的優(yōu)勢[13]，但沒有涉及分類問題.目前K2算法的節(jié)點(diǎn)排序問題仍未完善解決，這增加了使用K2算法構(gòu)建貝葉斯分類器的難度.

MWST+T- K2算法是一種混合結(jié)構(gòu)學(xué)習(xí)算法，“+T”代表選擇MWST的正序排序.該算法首先利用MWST算法構(gòu)建有向樹，然后獲得該有向樹的正序排序(+T)，之后將正序排序作為K2算法的節(jié)點(diǎn)排序，最后使用K2算法進(jìn)行結(jié)構(gòu)學(xué)習(xí).MWST+T- K2算法可以保證類節(jié)點(diǎn)指向?qū)傩怨?jié)點(diǎn)，這對構(gòu)建貝葉斯分類器提供了條件，但也限制了其學(xué)習(xí)基準(zhǔn)網(wǎng)絡(luò)結(jié)構(gòu)時的準(zhǔn)確性.該算法構(gòu)建基準(zhǔn)網(wǎng)絡(luò)時錯誤較多，所以一直沒有得到多數(shù)研究學(xué)者的重視，只有極少數(shù)研究學(xué)者應(yīng)用過該算法，但也沒有分析該算法作為分類器使用時的理論依據(jù)和適用范圍[14].

實(shí)驗(yàn)證明，MWST+T- K2算法是一種有效的使用K2算法構(gòu)建貝葉斯分類器的方法.MWST+T- K2分類器與NBC、TANC和MWST分類器3種貝葉斯分類器相比，取得了實(shí)驗(yàn)數(shù)據(jù)集上的全局最優(yōu)，并且在小數(shù)據(jù)集上取得了全局最優(yōu)，但在大數(shù)據(jù)集上的表現(xiàn)不及TANC.

1 MWST+T- K2算法

MWST+T- K2算法主要由兩個結(jié)構(gòu)學(xué)習(xí)算法組成： MWST結(jié)構(gòu)學(xué)習(xí)算法與K2結(jié)構(gòu)學(xué)習(xí)算法.

MWST算法是一種早期的結(jié)構(gòu)學(xué)習(xí)算法，其構(gòu)建的MWST分類器為樹形結(jié)構(gòu)，具有結(jié)構(gòu)簡潔的特點(diǎn)，并且該算法在運(yùn)行時只需要設(shè)定類節(jié)點(diǎn).MWST算法首先計(jì)算出各節(jié)點(diǎn)變量間的聯(lián)合概率分布，之后使用互信息函數(shù)來表示各節(jié)點(diǎn)間的相互依賴程度，對相應(yīng)的邊分配權(quán)重.互信息函數(shù)的計(jì)算方法如下：

(1)

在確定各邊權(quán)重后，將權(quán)重從大到小排序，并從類節(jié)點(diǎn)出發(fā)添加權(quán)重最大的一條邊，然后按照有向無環(huán)圖(Directed Acyclic Graph, DAG)原則逐步添加剩余邊中權(quán)重最大的邊，直到建立一棵具有n-1條邊的生成樹.至此MWST算法結(jié)束，此時可以通過拓?fù)渑判蛩惴╗15]獲得該生成樹的拓?fù)渑判颉?+T)或逆序(-T)，這兩個排序完全相反.使用K2算法建立貝葉斯分類器時需要保證類節(jié)點(diǎn)優(yōu)先被使用，所以指定正序?yàn)镵2算法的節(jié)點(diǎn)排序，再開始K2算法.

K2算法是一種經(jīng)典的基于評分的結(jié)構(gòu)學(xué)習(xí)算法[9].該算法的思想在于選擇數(shù)據(jù)集D所構(gòu)建網(wǎng)絡(luò)結(jié)構(gòu)中后驗(yàn)概率最大的網(wǎng)絡(luò)結(jié)構(gòu)，即有式(2)：

(2)

其中：BS代表網(wǎng)絡(luò)結(jié)構(gòu)；πi代表節(jié)點(diǎn)Xi的父節(jié)點(diǎn)集合；qi代表節(jié)點(diǎn)Xi的父節(jié)點(diǎn)Xj的可能數(shù)目；ri代表節(jié)點(diǎn)Xi的類別數(shù)；Nijk代表節(jié)點(diǎn)Xi的父節(jié)點(diǎn)Xj中第k類的樣本數(shù)目；Nij代表Xi的父節(jié)點(diǎn)Xj所有類別的樣本數(shù)目之和.Nij與Nijk的關(guān)系為：

(3)

為了讓式(2)的后驗(yàn)概率最大，只需要使式(2)中第2個內(nèi)積最大即可.為此式(2)可以分解出式(4)：

(4)

只要保證式(4)的值最大就能夠保證式(2)的后驗(yàn)概率最大.但式(4)能夠被計(jì)算的前提是滿足3個假設(shè)： 1) 節(jié)點(diǎn)排序；2) 合適的父節(jié)點(diǎn)上限u；3) 當(dāng)i≠j時，P(πi→xi)和P(πj→xj)邊緣獨(dú)立且先驗(yàn)概率能夠被有效計(jì)算.實(shí)際上前兩個假設(shè)都很難給定，這兩個假設(shè)也是該算法在實(shí)現(xiàn)時需要設(shè)定的兩個參數(shù).

對第二個假設(shè)，K2算法自身使用了一個包含式(4)的貪心算法來解決父節(jié)點(diǎn)最大上限u的取值問題.因此u的取值對K2算法的結(jié)構(gòu)學(xué)習(xí)結(jié)果只產(chǎn)生次要影響，并且u的取值也可以設(shè)置，最大值和默認(rèn)值均為屬性節(jié)點(diǎn)的個數(shù)，當(dāng)設(shè)置值超過最大值時，將按照最大值來計(jì)算.對第一個假設(shè)，K2算法自身不能解決，而節(jié)點(diǎn)排序又對K2算法的結(jié)構(gòu)學(xué)習(xí)結(jié)果產(chǎn)生主要影響，理論上要求前一個節(jié)點(diǎn)是后一個節(jié)點(diǎn)的父節(jié)點(diǎn)，才能獲得較好的網(wǎng)絡(luò)結(jié)構(gòu)，這在實(shí)際中是難以實(shí)現(xiàn)的.采用MWST的正序排序作為K2算法的節(jié)點(diǎn)排序，可以彌補(bǔ)K2算法在節(jié)點(diǎn)排序上的不足，并且保證所建立的網(wǎng)絡(luò)一定是貝葉斯分類器.在確定節(jié)點(diǎn)排序后，K2算法將按照節(jié)點(diǎn)排序和式(4)逐步添加邊，直到最后一個節(jié)點(diǎn)時K2算法結(jié)束.至此MWST+T- K2算法結(jié)束，其偽代碼可參看表1(見第50頁).

表1 MWST+T- K2算法偽代碼

2 實(shí)驗(yàn)準(zhǔn)備

選用UCI(University of California Irvine)數(shù)據(jù)庫的24個數(shù)據(jù)集作為實(shí)驗(yàn)數(shù)據(jù)集，在Matlab(版本號： 2014b)軟件平臺下，對NBC、TANC、MWST分類器和MWST+T- K2分類器進(jìn)行分類準(zhǔn)確率檢驗(yàn).各數(shù)據(jù)集概況見表2.選擇Matlab軟件作為實(shí)驗(yàn)平臺的原因在于貝葉斯網(wǎng)絡(luò)工具箱(Bayes Net Toolbox for Matlab, BNT)開源且開發(fā)已較為完善，具有從數(shù)據(jù)中進(jìn)行結(jié)構(gòu)學(xué)習(xí)、操作方式簡單且靈活度高等特點(diǎn).所有實(shí)驗(yàn)均在操作系統(tǒng)為XP系統(tǒng)(32位)，CPU為i3 2120，內(nèi)存容量為2G的硬件環(huán)境下進(jìn)行.

表2 數(shù)據(jù)集概況

表2中，序號為1～15的數(shù)據(jù)集，F(xiàn)riedman曾做過NBC、TANC、MWST分類器及其他分類器的分類檢驗(yàn)，并得到TANC對大多數(shù)數(shù)據(jù)集的適應(yīng)性是最好的結(jié)論[16]；序號為3，5，15～18的數(shù)據(jù)集，Cheng等曾做過NBC、TANC與其他分類器的分類檢驗(yàn)，其結(jié)果可以借鑒[17]；其余數(shù)據(jù)集為自選數(shù)據(jù)集.

表2中“分類數(shù)”代表類節(jié)點(diǎn)的分類數(shù)目.“屬性節(jié)點(diǎn)”由“離散”、“連續(xù)”、“總計(jì)”3部分組成： “離散”代表該數(shù)據(jù)集屬性節(jié)點(diǎn)中離散節(jié)點(diǎn)的個數(shù)；“連續(xù)”代表該數(shù)據(jù)集屬性節(jié)點(diǎn)中連續(xù)節(jié)點(diǎn)的個數(shù)；“總計(jì)”代表該數(shù)據(jù)集屬性節(jié)點(diǎn)的總個數(shù).連續(xù)節(jié)點(diǎn)需要離散化處理，各數(shù)據(jù)集是否需要離散化可參見表2中的“離散化”.離散化方法選用熵最小的離散化方法，即Fayyad等的MDL(Minimum Description Length)算法[18].使用該離散化方法的原因： 1) 該方法能利用最小的數(shù)據(jù)壓縮量刻畫數(shù)據(jù)中的變化規(guī)律，同時避免過擬合現(xiàn)象；2) Friedman等同樣對數(shù)據(jù)集使用了MDL算法，可說明BNT工具箱下NBC、TANC、MWST分類器分類結(jié)果的信度.數(shù)據(jù)離散化之前剔除了缺失項(xiàng)數(shù)據(jù)，并剔除了缺失項(xiàng)較多的節(jié)點(diǎn).“檢驗(yàn)方法”代表分類準(zhǔn)確率檢驗(yàn)的方法，依數(shù)據(jù)集大小分為兩種方法.一種方法是適用于小數(shù)據(jù)集的“5折交叉驗(yàn)證”檢驗(yàn)法[6]，記為“CV- 5”；另一種方法是適用于大數(shù)據(jù)的“保留驗(yàn)證”檢驗(yàn)法[19].表2中未使用“CV- 5”檢驗(yàn)法的數(shù)據(jù)集都采用該方法，該方法一般要求訓(xùn)練數(shù)據(jù)的數(shù)量多于檢驗(yàn)數(shù)據(jù).

各數(shù)據(jù)集分別使用各自的檢驗(yàn)方法重復(fù)檢驗(yàn)100次，再取其平均值來評估該分類器在各數(shù)據(jù)集上的分類準(zhǔn)確率，分類準(zhǔn)確率誤差則采用100次檢驗(yàn)結(jié)果的標(biāo)準(zhǔn)差來表示.

3 實(shí)驗(yàn)結(jié)果及分析

3.1實(shí)驗(yàn)結(jié)果

4種貝葉斯分類器利用數(shù)據(jù)集“iris”構(gòu)建的分類器結(jié)構(gòu)如圖1(見第52頁)所示.

圖1 Iris數(shù)據(jù)集構(gòu)建的4種貝葉斯分類器Fig.1 Four Bayes classifiers learned for the dataset iris

圖1從左往右依次是NBC、TANC、MWST和MWST+T- K2分類器，圖中“class”代表類節(jié)點(diǎn)，“sl”、“sw”、“pl”、“pw”代表屬性節(jié)點(diǎn).從圖1可以看出，MWST+T- K2分類器沒有使用屬性節(jié)點(diǎn)“sw”，而其他3種貝葉斯分類器使用了全部的屬性節(jié)點(diǎn).造成這一現(xiàn)象的原因在于K2算法的評分機(jī)制，對此可以參看偽代碼.類似地，MWST+T- K2只在10個數(shù)據(jù)集上使用了全部的屬性節(jié)點(diǎn)，而在14個數(shù)據(jù)集上只使用部分屬性節(jié)點(diǎn).這說明MWST+T- K2分類器在4種分類器中所使用的節(jié)點(diǎn)數(shù)量是最低的

4種貝葉斯分類器在24個數(shù)據(jù)集上的分類準(zhǔn)確率見表3，并引用參考文獻(xiàn)[16，17]的實(shí)驗(yàn)結(jié)果作為比較，相關(guān)數(shù)據(jù)也見表3.序號為3，5，15的數(shù)據(jù)集取參考文獻(xiàn)[16]的結(jié)果.

表3 4種貝葉斯分類器的分類準(zhǔn)確率

注： 加黑的數(shù)字為該數(shù)據(jù)集的最優(yōu)分類結(jié)果.

表3中，分類準(zhǔn)確率只保留了兩位小數(shù).序號1～18的多數(shù)數(shù)據(jù)集分類準(zhǔn)確率與參考文獻(xiàn)[16，17]所得結(jié)果接近，說明表3中的分類準(zhǔn)確率有一定信度，但也可以發(fā)現(xiàn)誤差水平存在較大差異且在一些數(shù)據(jù)集上分類準(zhǔn)確率也存在一定差異.造成差異的原因主要在于試驗(yàn)次數(shù)，同時也與硬件水平、實(shí)驗(yàn)平臺等因素有關(guān).

在24個數(shù)據(jù)集的分類結(jié)果中，NBC有6個最優(yōu)分類結(jié)果，TANC有8個最優(yōu)分類結(jié)果，MWST分類器有6個最優(yōu)分類結(jié)果，MWST+T- K2分類器有9個最優(yōu)分類結(jié)果.這說明MWST+T- K2分類器的分類水平具有一定優(yōu)勢，分別高出NBC 3個數(shù)據(jù)集，TANC 1個數(shù)據(jù)集，MWST分類器3個數(shù)據(jù)集.

3.2實(shí)驗(yàn)結(jié)果比較

將4種貝葉斯分類器的分類結(jié)果進(jìn)行比較，繪制了MWST+T- K2分類器與其他3種分類器的分類錯誤率比較圖，如圖2所示.

圖2 4種貝葉斯分類器分類錯誤率比較Fig.2 Compared error rate of four Bayes classifiers

圖2中，從左往右的3幅子圖中，橫軸坐標(biāo)都為MWST+T- K2分類器的分類錯誤率，縱軸坐標(biāo)則分別代表NBC、TANC、MWST分類器的分類錯誤率.結(jié)合表3數(shù)據(jù)與圖2可以統(tǒng)計(jì)出，MWST+T- K2分類器在12個數(shù)據(jù)集上分類水平優(yōu)于NBC，在2個數(shù)據(jù)集上兩者分類水平相同，在10個數(shù)據(jù)集上分類水平劣于NBC；在12個數(shù)據(jù)集上分類水平優(yōu)于TANC，在1個數(shù)據(jù)集上兩者分類水平相同，在11個數(shù)據(jù)集上分類水平劣于TANC；在17個數(shù)據(jù)集上分類水平優(yōu)于MWST分類器，在7個數(shù)據(jù)集上分類水平劣于MWST分類器.即單獨(dú)比較MWST+T- K2分類器與其他3種分類器的分類水平時，MWST+T- K2分類器優(yōu)于NBC 2個數(shù)據(jù)集，優(yōu)于TANC 1個數(shù)據(jù)集，優(yōu)于MWST分類器10個數(shù)據(jù)集.

進(jìn)一步討論4種貝葉斯分類器對數(shù)據(jù)集的適應(yīng)性.根據(jù)表3數(shù)據(jù)繪制各分類器在各數(shù)據(jù)集上的誤差棒，考慮到分類準(zhǔn)確率誤差采用單倍標(biāo)準(zhǔn)差的繪圖效果并不理想，故這里采用5倍標(biāo)準(zhǔn)差進(jìn)行繪圖，繪圖結(jié)果如圖3(見第54頁)所示.

圖3 4種貝葉斯分類器誤差棒比較Fig.3 Compared error bar of four Bayes classifiers

圖3的3幅子圖，從上往下依次為MWST+T- K2分類器與NBC、TANC、MWST分類器的誤差棒比較.橫軸坐標(biāo)代表各數(shù)據(jù)集序號，按分類檢驗(yàn)方法的不同分類，即數(shù)據(jù)集的大小分類： 前17個數(shù)據(jù)集為小數(shù)據(jù)集，后7個數(shù)據(jù)集為大數(shù)據(jù)集，在圖3中以豎線分開.

結(jié)合圖3和表3數(shù)據(jù)統(tǒng)計(jì)出，在17個小數(shù)據(jù)集中，分類水平全局最優(yōu)的分類器是NBC、MWST分類器與MWST+T- K2分類器，都在6個小數(shù)據(jù)集上取得了最高的分類準(zhǔn)確率；TANC只在3個小數(shù)據(jù)集上取得了最高的分類準(zhǔn)確率.單獨(dú)比較小數(shù)據(jù)集的分類準(zhǔn)確率時，MWST+T- K2分類器在6個數(shù)據(jù)集上分類水平優(yōu)于NBC，在2個數(shù)據(jù)集上兩者分類水平相同，在9個數(shù)據(jù)集上分類水平劣于NBC；在10個數(shù)據(jù)集上分類水平優(yōu)于TANC，在7個數(shù)據(jù)集上分類水平劣于TANC；在10個數(shù)據(jù)集上分類水平優(yōu)于MWST分類器，在1個數(shù)據(jù)集上兩者分類水平相同，在6個數(shù)據(jù)集上分類水平劣于MWST.即MWST+T- K2分類器在小數(shù)據(jù)集上的分類水平低于NBC 3個數(shù)據(jù)集，各高出TANC 3個、MWST分類器4個數(shù)據(jù)集.

在7個大數(shù)據(jù)集中，最優(yōu)分類器依次為TANC、MWST+T- K2分類器，各在5個和3個大數(shù)據(jù)集上取得了最高分類準(zhǔn)確率，NBC和MWST分類器沒有在任何大數(shù)據(jù)集上取得最高分類準(zhǔn)確率.單獨(dú)比較時，MWST+T- K2分類器在6個數(shù)據(jù)集上分類水平優(yōu)于NBC，在1個數(shù)據(jù)集上的分類水平劣于NBC；在2個數(shù)據(jù)集上分類水平優(yōu)于TANC，在1個數(shù)據(jù)集上兩者分類水平相同，在4個數(shù)據(jù)集上分類水平劣于TANC；在所有的大數(shù)據(jù)集上分類水平都優(yōu)于MWST分類器.即MWST+T- K2分類器在大數(shù)據(jù)集上低于TANC 2個數(shù)據(jù)集，高出NBC 5個數(shù)據(jù)集，高出MWST分類器7個數(shù)據(jù)集.

通過以上分析可知，MWST+T- K2分類器與NBC、TANC、MWST分類器在整體比較與兩兩比較時，均優(yōu)于其他3種分類器；在小數(shù)據(jù)集上，其分類水平高于TANC和MWST分類器，低于NBC，但該分類器在小數(shù)據(jù)集全局上取得了最優(yōu)，所以MWST+T- K2分類器是一種較為適合小數(shù)據(jù)集的分類器；但該分類器在大數(shù)據(jù)集上的分類水平雖高于NBC和MWST分類器，但低于TANC，且在全局上劣于TANC，所以MWST+T- K2分類器并不是一種理想的大數(shù)據(jù)集分類器.

4 結(jié) 語

本文提出了一種基于MWST+T- K2結(jié)構(gòu)學(xué)習(xí)算法構(gòu)建貝葉斯分類器的方法.實(shí)驗(yàn)證明，該算法是一種有效使用K2算法構(gòu)建分類器的方式，并且所構(gòu)建的MWST+T- K2分類器在UCI數(shù)據(jù)庫的24個數(shù)據(jù)集中，分類準(zhǔn)確率最高的數(shù)據(jù)集有9個，高于其他3種貝葉斯分類器；在兩兩比較分類準(zhǔn)確率時占有較大的優(yōu)勢，優(yōu)于NBC 2個數(shù)據(jù)集，優(yōu)于TANC 1個數(shù)據(jù)集，優(yōu)于MWST分類器10個數(shù)據(jù)集；在小數(shù)據(jù)集上的分類水平取得了全局最優(yōu)，單獨(dú)比較其與NBC的分類準(zhǔn)確率時，雖然低于NBC 3個數(shù)據(jù)集，但仍不失為一種適合小數(shù)據(jù)集的貝葉斯分類器；在大數(shù)據(jù)集上的分類水平劣于TANC，雖然對NBC和MWST分類器有一定的優(yōu)勢，但卻不是理想的大數(shù)據(jù)集分類器.同時該分類器能夠使用最少的屬性節(jié)點(diǎn)數(shù)目來得到一個不錯的分類效果，這是其他3種貝葉斯分類器都不具備的.

MWST+T- K2分類器并不能取得大數(shù)據(jù)集上的全局最優(yōu)或局部最優(yōu)，故其適用范圍受到了一定的限制.

感謝西安科技大學(xué)理學(xué)院張磊博士對本論文的幫助！

[1] 張連文,郭海鵬.貝葉斯網(wǎng)引論[M].北京: 科學(xué)出版社,2006.

[2] 洪海燕.基于貝葉斯分類器的簡歷篩選模型[J].計(jì)算機(jī)技術(shù)與發(fā)展，2012,22(7): 85- 87.

[3] DUDA R O, HART P E. Pattern classification and scene analysis[M]. New York: John Wiley & Sons, 1973.

[4] CHOW C K, LIU C N. Approximating discrete probability distributions with dependence trees[J].IEEETransactiononInformationTheory, 1968,14(3): 462- 467.

[5] 周顏君,王雙成,王 輝.基于貝葉斯網(wǎng)絡(luò)的分類器研究[J].東北師大學(xué)報(bào)(自然科學(xué)版),2003,35(2): 21- 27.

[6] FRIEDMAN N, GOLDSZMIDT M. Buliding classifiers using Bayesian network [C]∥Thirteenth Nation Conference on Artificial Intelligence. CA: AAAI Press, 1996： 1227- 1284.

[7] HRUSCHKA E R, EBECKEN N F. Towards efficient variables ordering for Bayesian networks classifier[J].Data&KnowledgeEngineering, 2007,63(2): 258- 269.

[8] LERNER B, MALKA R. Investigation of the K2 algorithm in learing Bayesian Network Classifiers[J].AppliedArtificialIntelligence, 2011，25(1): 74- 96.

[9] COOPER G F, HERSKOVITS E. A Bayesian method for the induction of probabilistic networks from data[J].MachineLearning, 1992,9(4): 309- 347.

[10] LARRAFIAGA P, KUIJPERS C M, MURGA T H，etal. Learning Bayesian network structures by searching for the best ordering with genetic algorithms[J].IEEETransactionsonSystems,Man,andCybernetics-pakta:SystemsandHumans, 1996,26(4): 487- 493.

[11] CHEN X, ANANTHA G, WANG X. An effective structure learning method for constructing gene networks[J].Bioinformatics, 2006,22(11): 1367- 1374.

[12] CHEN X, ANANTHA G, LIN X. Improving Bayesian network structure learning with mutual information- based node ordering in the K2 algorithm[J].IEEETransactionsonKnowledgeandDataEngineering, 2008，20(5): 628- 640.

[13] KO S, KIM D. An efficient node ordering method using the conditional frequency for the K2 algorithm[J].PatternRecognitionLetters, 2014,40(4): 81- 87.

[14] 王 強(qiáng),彭思龍.基于貝葉斯網(wǎng)絡(luò)模型的紋理分析及分類[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào),2007,19(12): 1564- 1568.

[15] 楊薇薇,王 方,秦 明，等.數(shù)據(jù)結(jié)構(gòu)[M].北京: 清華大學(xué)出版社.2011.

[16] FRIEDMAN N, GEIGER D, GOLDSZMIDT M. Bayesian network classifiers[J].MachineLearning, 1997,29(2): 131- 163.

[17] CHENG J, GREINER R. Comparing Bayesian network classifiers[C]∥Proceedings of the 15th Conference on Uncertainty in Artificial Intelligence. San Francisco: Morgan Kaufmann, 1999： 101- 108.

[18] FAYYAD U, IRANI K. Multi- interval discretization of continuous- valued attributes for classification learning [C]∥Proceedings of Thirteenth International Joint Conference on Artificial Intelligence. CA: Morgan Kaufmann，1993： 1022- 1027.

[19] 程澤凱,林士敏,陸玉昌，等.基于Matlab的貝葉斯分類器實(shí)驗(yàn)平臺MBNC[J].復(fù)旦學(xué)報(bào)(自然科學(xué)版),2004,43(5): 729- 732.

Abstract： The node ordering heavily affects the classified accuracy when one constructs Bayes classifier by K2 algorithm. Based on this problem, a kind of MWST+T- K2 structure learning algorithm is proposed, then this algorithm is applied to construct the MWST+T- K2 classifier through the BNT toolbox of MATLAB. At last, the classified test is carried out on the 24 data sets in the UCI database. The results imply that the classified level of the MWST+T- K2 classifier is globally optimal when the four classified levels is compared together or one is compared with anther on the 24 data sets; It is globally (not locally) optimal when the classifier level is compared with the others on all of the small data sets. The result, which is lower than the classified level of TANC, is neither globally nor locally optimal on all of the large data sets. Therefore, the proposed MWST+T- K2 structure learning algorithm is suitable to construct the Bayes classifier on small data sets.

Keywords： Bayesian network; Bayes classifier; MWST+T- K2 algorithm; classified test

BasedonMWST+T-K2AlgorithmtoBuildBayesClassifier

ZHAO Gaochang1, WANG Xin1，2, ZHANG Zhonghua1, HAN Miao1, WEI Wei3

(1.CollegeofSciences,Xi’anUniversityofScienceandTechnology,Xi’an710054,China；2.YangshengtangCO.,Ltd.,Hangzhou310007,China；3.SchoolofComputerScienceandEngineering,Xi’anUniversityofTechnology,Xi’an710048,China)

TP39

A

0427- 7104(2017)01- 0048- 09

2015- 12- 08

國家自然科學(xué)基金(41271518)；陜西省教育廳科研計(jì)劃項(xiàng)目(2013JK0583,14JK1474)；陜西省自然科學(xué)基金(2016JM1025)

趙高長(1965—)，男，教授；王 欣(1989—)，男，碩士研究生，通信聯(lián)系人，E- mail： 394315185@qq.com.