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

趙高長(zhǎng)，王 欣,2，張仲華，韓 苗，魏 嵬

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

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

趙高長(zhǎng)1，王 欣1,2，張仲華1，韓 苗1，魏 嵬3

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

針對(duì)K2算法在構(gòu)建貝葉斯分類器時(shí)節(jié)點(diǎn)排序不同影響分類準(zhǔn)確率的問(wèn)題，提出了一種MWST+T- K2結(jié)構(gòu)學(xué)習(xí)算法，運(yùn)用Matlab軟件的BNT工具箱構(gòu)建了MWST+T- K2分類器，并經(jīng)過(guò)NBC、TANC、MWST和MWST+T- K2分類器對(duì)UCI數(shù)據(jù)庫(kù)的24個(gè)分類數(shù)據(jù)集進(jìn)行分類檢驗(yàn).結(jié)果表明，對(duì)4種分類器在24個(gè)數(shù)據(jù)集上的分類水平進(jìn)行整體與兩兩比較時(shí)，MWST+T- K2分類器的分類水平均最優(yōu)；在小數(shù)據(jù)集上比較時(shí)，MWST+T- K2分類器的分類水平取得全局最優(yōu)，未取得局部最優(yōu)；在大數(shù)據(jù)集上比較時(shí)，未取得全局或局部最優(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)生成樹(shù)[4](Maximum Weight Spanning Tree, MWST)的基礎(chǔ)上，利用條件互信息函數(shù)構(gòu)造出樹(shù)擴(kuò)展的樸素貝葉斯分類器(Tree Augmented Navie Bayes Classifier, TANC)，TANC在NBC的結(jié)構(gòu)基礎(chǔ)上允許各屬性節(jié)點(diǎn)間構(gòu)成一棵樹(shù)，但規(guī)定各屬性節(jié)點(diǎn)最多只能有一個(gè)非類父節(jié)點(diǎn)[5].這種結(jié)構(gòu)充分應(yīng)用了各屬性節(jié)點(diǎn)間的信息，使TANC在一些數(shù)據(jù)集上的分類準(zhǔn)確率有所提升[6].近年來(lái)一些學(xué)者提出使用K2算法構(gòu)建貝葉斯分類器[7，8].K2算法在正確的節(jié)點(diǎn)排序下能夠獲得較好的網(wǎng)絡(luò)結(jié)構(gòu)，但是獲得一個(gè)正確的節(jié)點(diǎn)排序是困難的[9].對(duì)該問(wèn)題研究的進(jìn)展比較緩慢,早期的研究學(xué)者使用遺傳算法或啟發(fā)式算法確定節(jié)點(diǎn)排序，在獲得節(jié)點(diǎn)排序的同時(shí)往往伴隨著局部最優(yōu)、計(jì)算代價(jià)大等問(wèn)題[10]；2008年Chen 提出使用信息熵確定節(jié)點(diǎn)排序，使K2算法的結(jié)構(gòu)學(xué)習(xí)獲得了較好效果[11]，同時(shí)簡(jiǎn)要提及使用該方法后K2分類器的性能[12]；2014年Ko利用狄利克雷分布提出新的評(píng)分函數(shù)改進(jìn)了Chen的方法，并通過(guò)實(shí)驗(yàn)表明所提方法在結(jié)構(gòu)學(xué)習(xí)上的優(yōu)勢(shì)[13]，但沒(méi)有涉及分類問(wèn)題.目前K2算法的節(jié)點(diǎn)排序問(wèn)題仍未完善解決，這增加了使用K2算法構(gòu)建貝葉斯分類器的難度.

MWST+T- K2算法是一種混合結(jié)構(gòu)學(xué)習(xí)算法，“+T”代表選擇MWST的正序排序.該算法首先利用MWST算法構(gòu)建有向樹(shù)，然后獲得該有向樹(shù)的正序排序(+T)，之后將正序排序作為K2算法的節(jié)點(diǎn)排序，最后使用K2算法進(jìn)行結(jié)構(gòu)學(xué)習(xí).MWST+T- K2算法可以保證類節(jié)點(diǎn)指向?qū)傩怨?jié)點(diǎn)，這對(duì)構(gòu)建貝葉斯分類器提供了條件，但也限制了其學(xué)習(xí)基準(zhǔn)網(wǎng)絡(luò)結(jié)構(gòu)時(shí)的準(zhǔn)確性.該算法構(gòu)建基準(zhǔn)網(wǎng)絡(luò)時(shí)錯(cuò)誤較多，所以一直沒(méi)有得到多數(shù)研究學(xué)者的重視，只有極少數(shù)研究學(xué)者應(yīng)用過(guò)該算法，但也沒(méi)有分析該算法作為分類器使用時(shí)的理論依據(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算法主要由兩個(gè)結(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分類器為樹(shù)形結(jié)構(gòu)，具有結(jié)構(gòu)簡(jiǎn)潔的特點(diǎn)，并且該算法在運(yùn)行時(shí)只需要設(shè)定類節(jié)點(diǎn).MWST算法首先計(jì)算出各節(jié)點(diǎn)變量間的聯(lián)合概率分布，之后使用互信息函數(shù)來(lái)表示各節(jié)點(diǎn)間的相互依賴程度，對(duì)相應(yīng)的邊分配權(quán)重.互信息函數(shù)的計(jì)算方法如下：

(1)

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

K2算法是一種經(jīng)典的基于評(pí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個(gè)內(nèi)積最大即可.為此式(2)可以分解出式(4)：

(4)

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

對(duì)第二個(gè)假設(shè)，K2算法自身使用了一個(gè)包含式(4)的貪心算法來(lái)解決父節(jié)點(diǎn)最大上限u的取值問(wèn)題.因此u的取值對(duì)K2算法的結(jié)構(gòu)學(xué)習(xí)結(jié)果只產(chǎn)生次要影響，并且u的取值也可以設(shè)置，最大值和默認(rèn)值均為屬性節(jié)點(diǎn)的個(gè)數(shù)，當(dāng)設(shè)置值超過(guò)最大值時(shí)，將按照最大值來(lái)計(jì)算.對(duì)第一個(gè)假設(shè)，K2算法自身不能解決，而節(jié)點(diǎn)排序又對(duì)K2算法的結(jié)構(gòu)學(xué)習(xí)結(jié)果產(chǎn)生主要影響，理論上要求前一個(gè)節(jié)點(diǎn)是后一個(gè)節(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)逐步添加邊，直到最后一個(gè)節(jié)點(diǎn)時(shí)K2算法結(jié)束.至此MWST+T- K2算法結(jié)束，其偽代碼可參看表1(見(jiàn)第50頁(yè)).

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

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

選用UCI(University of California Irvine)數(shù)據(jù)庫(kù)的24個(gè)數(shù)據(jù)集作為實(shí)驗(yàn)數(shù)據(jù)集，在Matlab(版本號(hào)： 2014b)軟件平臺(tái)下，對(duì)NBC、TANC、MWST分類器和MWST+T- K2分類器進(jìn)行分類準(zhǔn)確率檢驗(yàn).各數(shù)據(jù)集概況見(jiàn)表2.選擇Matlab軟件作為實(shí)驗(yàn)平臺(tái)的原因在于貝葉斯網(wǎng)絡(luò)工具箱(Bayes Net Toolbox for Matlab, BNT)開(kāi)源且開(kāi)發(fā)已較為完善，具有從數(shù)據(jù)中進(jìn)行結(jié)構(gòu)學(xué)習(xí)、操作方式簡(jiǎn)單且靈活度高等特點(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中，序號(hào)為1～15的數(shù)據(jù)集，F(xiàn)riedman曾做過(guò)NBC、TANC、MWST分類器及其他分類器的分類檢驗(yàn)，并得到TANC對(duì)大多數(shù)數(shù)據(jù)集的適應(yīng)性是最好的結(jié)論[16]；序號(hào)為3，5，15～18的數(shù)據(jù)集，Cheng等曾做過(guò)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)的個(gè)數(shù)；“連續(xù)”代表該數(shù)據(jù)集屬性節(jié)點(diǎn)中連續(xù)節(jié)點(diǎn)的個(gè)數(shù)；“總計(jì)”代表該數(shù)據(jù)集屬性節(jié)點(diǎn)的總個(gè)數(shù).連續(xù)節(jié)點(diǎn)需要離散化處理，各數(shù)據(jù)集是否需要離散化可參見(jiàn)表2中的“離散化”.離散化方法選用熵最小的離散化方法，即Fayyad等的MDL(Minimum Description Length)算法[18].使用該離散化方法的原因： 1) 該方法能利用最小的數(shù)據(jù)壓縮量刻畫數(shù)據(jù)中的變化規(guī)律，同時(shí)避免過(guò)擬合現(xiàn)象；2) Friedman等同樣對(duì)數(shù)據(jù)集使用了MDL算法，可說(shuō)明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次，再取其平均值來(lái)評(píng)估該分類器在各數(shù)據(jù)集上的分類準(zhǔn)確率，分類準(zhǔn)確率誤差則采用100次檢驗(yàn)結(jié)果的標(biāo)準(zhǔn)差來(lái)表示.

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

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

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

圖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分類器沒(méi)有使用屬性節(jié)點(diǎn)“sw”，而其他3種貝葉斯分類器使用了全部的屬性節(jié)點(diǎn).造成這一現(xiàn)象的原因在于K2算法的評(píng)分機(jī)制，對(duì)此可以參看偽代碼.類似地，MWST+T- K2只在10個(gè)數(shù)據(jù)集上使用了全部的屬性節(jié)點(diǎn)，而在14個(gè)數(shù)據(jù)集上只使用部分屬性節(jié)點(diǎn).這說(shuō)明MWST+T- K2分類器在4種分類器中所使用的節(jié)點(diǎn)數(shù)量是最低的

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

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

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

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

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

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

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

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

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

進(jìn)一步討論4種貝葉斯分類器對(duì)數(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(見(jiàn)第54頁(yè))所示.

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

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

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

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

通過(guò)以上分析可知，MWST+T- K2分類器與NBC、TANC、MWST分類器在整體比較與兩兩比較時(shí)，均優(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é) 語(yǔ)

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

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

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

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

[2] 洪海燕.基于貝葉斯分類器的簡(jiǎn)歷篩選模型[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)平臺(tái)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

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

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