張坤　陳曦　宋云　傅明

摘要：為了改善樹增強樸素貝葉斯（TAN）的分類精度，對TAN結(jié)構(gòu)進行了擴展，提出了一種利用可分解的評分函數(shù)構(gòu)建樹形貝葉斯網(wǎng)絡(luò)分類模型的學(xué)習(xí)方法。在構(gòu)建TAN網(wǎng)絡(luò)時允許屬性沒有父結(jié)點。采用低階CI測試初步剔除無效屬性，再結(jié)合改進的BIC評分函數(shù)利用貪婪搜索獲得每個屬性結(jié)點的父結(jié)點，從而建立分類模型。對比樸素貝葉斯（NB）和TAN，提出的分類算法在分類準確率和AUC面積兩個指標上表現(xiàn)更好，說明本文模型擁有比TAN更好的分類效果。

關(guān)鍵詞：樹增強樸素貝葉斯;分類網(wǎng)絡(luò);評分函數(shù)：

中圖分類號：TP311.1

文獻識別碼：A

分類是一種常見的監(jiān)督學(xué)習(xí)方法，其目標是在訓(xùn)練集上建立分類模型，從而為測試集實例指定合適的類別。貝葉斯網(wǎng)絡(luò)[1]表達了一種因果關(guān)系，它用圖模型理論和統(tǒng)計學(xué)知識來表示屬性之間的概率。在貝葉斯網(wǎng)絡(luò)中，分類是根據(jù)類別的先驗分布計算后驗概率，從而選擇最可能的類。樸素貝葉斯（NB）分類器[2]是一種簡單有效的貝葉斯網(wǎng)絡(luò)，但由于其屬性變量之間存在條件獨立性假設(shè)，分類精度不佳。Friedman等人[3]提出樹增強的樸素貝葉斯（TAN），它允許屬性結(jié)點最多只能依賴于一個非類結(jié)點，綜合性能良好，是學(xué)習(xí)效率與分類精度之間的一種折衷。

目前關(guān)于TAN分類器的研究通常從構(gòu)建合適的貝葉斯網(wǎng)絡(luò)著手：文獻[4]提出一種不確定條件互信息度量方法來學(xué)習(xí)樹形貝葉斯分類網(wǎng)絡(luò)結(jié)構(gòu);文獻[5]根據(jù)條件對數(shù)似然性提出一種平均樹增強樸素貝葉斯;文獻[6]對TAN分類器結(jié)構(gòu)空間和TAN分類器結(jié)構(gòu)等價類空間進行了研究，提出一個不考慮邊重定向的TAN分類器學(xué)習(xí)算法。這類低階或受限（如k-BAN[10]）的貝葉斯分類模型既避免了由高維計算導(dǎo)致的不穩(wěn)定性[7]，同時也增強了網(wǎng)絡(luò)結(jié)構(gòu)中屬性之間的因果關(guān)系。因此，關(guān)于TAN分類器的應(yīng)用研究也較為常見，如高血壓診斷模型[8]、物種豐富度的估計模型[9]等等。然而，TAN模型雖然簡潔高效，但在構(gòu)建網(wǎng)絡(luò)結(jié)構(gòu)時并沒有進行相關(guān)屬性選擇或引入新屬性，這對TAN分類模型的分類精度有所影響本文在保證TAN精簡結(jié)構(gòu)的基礎(chǔ)上，提出擴展的TAN分類器（Extended Tree AugmentedNaive Bayes，簡稱ETAN），額外允許TAN模型中部分屬性沒有父結(jié)點?？紤]到屬性對類貢獻程度差異，采用互信息測試進行屬性選擇，用于確定后續(xù)每個屬性結(jié)點的候選連接。隨后給出了利用可分解的評分函數(shù)來構(gòu)建TAN模型的詳細過程，提出一種利用改進的BIC評分函數(shù)來構(gòu)建樹形貝葉斯網(wǎng)絡(luò)分類模型的學(xué)習(xí)方法（ Extended Tree AugmentedNaive Bayes with the scoring function，簡稱SETAN）.通過與其它同類分類器進行對比實驗，提出的SE-TAN分類模型取得了更好的分類精度。

1 基于BIC評分函數(shù)的SETAN分類器

1.1 TAN模型

1.1.1 TAN模型

由此可知，學(xué)習(xí)TAN結(jié)構(gòu)首先要建立一個無向圖結(jié)構(gòu)，再找到合適的算法來解決最大權(quán)重生成樹問題，其中每條邊的權(quán)重是圖中兩個屬性結(jié)點之間的條件互信息，并且用有向弧代替邊，則無向樹就可以被轉(zhuǎn)化呈有向樹，最后加入類結(jié)點C即可建立所需分類模型。

1.1.2 STAN模型

評分與搜索方法是當前常見的一種貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)方法，它將網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)轉(zhuǎn)化成最優(yōu)化問題，學(xué)習(xí)目標即搜索評分較高的網(wǎng)絡(luò)結(jié)構(gòu)。評分搜索的結(jié)構(gòu)學(xué)習(xí)方法分為兩步：網(wǎng)絡(luò)結(jié)構(gòu)評分函數(shù)和網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)算法的確定。一旦定義好評分函數(shù)，貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)問題就是一個最優(yōu)化搜索問題。

①評分函數(shù)

假設(shè)給定完整訓(xùn)練集D，D= {X1，X2，…，X_n}，G是以X1，X2，…，X_n為結(jié)點的貝葉斯網(wǎng)絡(luò)。假設(shè)數(shù)據(jù)集滿足獨立同分布假設(shè)，則G相對于數(shù)據(jù)D的優(yōu)劣可以用評分函數(shù)來度量。即，探索最佳貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)，就是找到可使得評分函數(shù)最大化的一個有向無環(huán)圖G。即

常見的MDL、BIC、BDe評分函數(shù)都具備可分解性和似然等價性。文獻[12]提出貝葉斯信息標準（ Bayesian information criterion），簡稱BIC評分。BIC評分函數(shù)是在樣本滿足獨立同分布假設(shè)的前提下，用對數(shù)似然度度量結(jié)構(gòu)與數(shù)據(jù)的擬合程度。具體形式為：

②模型描述

下面給出TAN分類模型結(jié)合評分搜索方法的一般性表達式（Tree Augmented Naive Bayes with ascoring function，簡稱STAN）。

TAN分類器基于NB分類器對屬性之間的依賴關(guān)系進行了擴展，將構(gòu)造最大似然樹的問題簡化為構(gòu)造最大權(quán)重跨度樹。當給定評分函數(shù)時，在TAN無向圖中，有

1.2 SETAN模型

1.2.1 理論分析

由TAN的定義和公式（7）可知，TAN結(jié)構(gòu)限制每個屬性結(jié)點對其父結(jié)點有如下兩種連接選擇：1，只有類父結(jié)點C;2，具有類父結(jié)點C和一個屬性父結(jié)點。TAN的學(xué)習(xí)是在完全圖中搜索弧空間，通過這種限制，減小了搜索空間;同時父結(jié)點的數(shù)量受限使得條件概率計算相應(yīng)地減少。

然而，TAN結(jié)構(gòu)并不能充分地表示屬性結(jié)點之間的依賴關(guān)系，而且在構(gòu)建網(wǎng)絡(luò)結(jié)構(gòu)時未能去除冗余的屬性結(jié)點。準確地說，TAN是在維持原始屬性變量集合的基礎(chǔ)上建立低階樹形分類模型，而不是通過引入新的屬性變量來放松條件獨立性假設(shè)。Greiner等人[13]通過實驗證明，與數(shù)據(jù)集實際分布近似或比數(shù)據(jù)集實際分布簡單的網(wǎng)絡(luò)結(jié)構(gòu)都具有一定的局限性。對于前者，文獻[7]已給出證明，限制父結(jié)點的數(shù)量可以有效避免具有指數(shù)復(fù)雜度的高維計算。后者的原因是，即使NB網(wǎng)絡(luò)或TAN網(wǎng)絡(luò)相對簡單，但也可能由于存在冗余的結(jié)點和弧邊而使得網(wǎng)絡(luò)結(jié)構(gòu)復(fù)雜化。因此，在建立TAN結(jié)構(gòu)前進行有效的屬性選擇非常有必要。

另外，TAN結(jié)構(gòu)僅僅強化了屬性之間的因果關(guān)系，而沒有考慮不同屬性對類的貢獻，這同樣也降低了TAN模型的分類準確性。文獻[14][15]的一系列對比實驗證實了這一結(jié)論。

基于上述分析，本文進一步擴展了TAN網(wǎng)絡(luò)結(jié)構(gòu)，該網(wǎng)絡(luò)結(jié)構(gòu)相對于TAN能夠更充分地表示在類約束下屬性之間的依賴關(guān)系，同時嘗試剔除對分類模型沒有貢獻的屬性結(jié)點。

1.2.2 SETAN模型

①CI測試

由香農(nóng)的信息論可知，兩個隨機變量X_i和x_j之間的互信息為：

②改進TAN模型

為了避免貝葉斯網(wǎng)絡(luò)分類器的高維計算，同時為了在構(gòu)建SETAN結(jié)構(gòu)時去除冗余結(jié)點并減少候選父結(jié)點集的搜索空間，增強分類模型的可靠性與健壯性，在TAN結(jié)構(gòu)基礎(chǔ)上，允許屬性結(jié)點沒有父結(jié)點。即具有如下額外兩種選擇：3，只有一個屬性父結(jié)點;4，沒有父結(jié)點。其中符合第4種情況的結(jié)點被視為對分類模型沒有貢獻的冗余結(jié)點。

考慮到SETAN結(jié)構(gòu)中各個屬性結(jié)點X_i和類結(jié)點C的相關(guān)性不同，先對類結(jié)點和屬性結(jié)點進行互信息測試，如圖1（c）（d）所示：

基于上述改動，每個屬性結(jié)點不必將類結(jié)點納入候選父結(jié)點集，則公式（5）中的對稱性無法成立，從而無法在公式（7）中利用最小生成樹算法求得SETAN結(jié)構(gòu)。此時對于經(jīng)過0階CI測試后的無環(huán)圖，采用BIC評分函數(shù)貪婪查找下一個局部無環(huán)圖G，從而得到圖l（d）所示的最終有向無環(huán)圖。則有

1.2.3 算法描述

基于BIC評分函數(shù)的SETAN分類算法主要有如下改進：

1，提出SETAN網(wǎng)絡(luò)結(jié)構(gòu)，在TAN結(jié)構(gòu)基礎(chǔ)上中放松了每個屬性結(jié)點的父結(jié)點選擇條件，允許部分屬性沒有類父結(jié)點，在保證同等計算復(fù)雜度下提高了分類模型的可靠性。

2，采用低階CI測試去除無效結(jié)點，結(jié)合上述屬性依賴關(guān)系，獲得各個屬性的候選父結(jié)點集合，獲得冗余結(jié)點，減小候選父結(jié)點集的搜索空間。

3，利用改進的BIC評分函數(shù)對局部最優(yōu)無環(huán)圖進行貪婪查找，從而獲得最終的SETAN網(wǎng)絡(luò)結(jié)構(gòu)。進一步去除無效結(jié)點，提高算法的分類精度。下面給出構(gòu)建SETAN結(jié)構(gòu)圖的一般性過程。

1.2.4 時間復(fù)雜度分析

SETAN分類器學(xué)習(xí)算法主要分為兩個部分：

第一部分是類結(jié)點與各個屬性結(jié)點之間的0階CI測試。主要的計算耗時是互信息測試/（C;X_i），復(fù)雜度是O（N_n），N是訓(xùn)練集實例數(shù)量，n是屬性結(jié)點數(shù)量。

第二部分是構(gòu)建SETAN網(wǎng)絡(luò)結(jié)構(gòu)，主要是需要比較每個結(jié)點和其候選父結(jié)點集的連接得分，以此確定其父結(jié)點。時間復(fù)雜度是O（Nk1 +Nk1·k2），因為kl+k2≤n，ε一般取值為0.01-0.05，大多數(shù)屬性結(jié)點可符合互信息測試，即k2《k1。因此，SETAN分類器最終可在O（ Nn2）內(nèi)完成，和TAN分類模型的時間復(fù)雜度相同。

2 實驗結(jié)果與分析

2.1 改進的BIC評分函數(shù)評估

本節(jié)實驗的主要目的是確定公式（9）中改進后BIC評分函數(shù)的合適的懲罰系數(shù)ξ。分別采用http：//www.norsys.com提供的Asia網(wǎng)和Alarm網(wǎng)進行仿真實驗。Asia網(wǎng)包含8個變量和8條邊，Alarm網(wǎng)包含33個結(jié)點，46條邊，樣本數(shù)量均為5000。利用常見的K2算法和改進后的BIC評分函數(shù)學(xué)習(xí)貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)，懲罰系數(shù)ξ分別取0.01，0.001，0.0001。實驗結(jié)果如表所示，A為增加邊，D為確實邊，R為正確邊。

從表1的實驗結(jié)果可以看出，ξ= 0.01時，Asia網(wǎng)絡(luò)和Alarm網(wǎng)絡(luò)結(jié)構(gòu)缺式邊數(shù)量相對比較多，沒有增加邊，說明懲罰系數(shù)偏大，導(dǎo)致數(shù)據(jù)和網(wǎng)絡(luò)結(jié)構(gòu)欠擬合;ξ= 0.0001時，網(wǎng)絡(luò)結(jié)構(gòu)增加邊相對較多，導(dǎo)致數(shù)據(jù)和網(wǎng)絡(luò)結(jié)構(gòu)過擬合;而當ξ= 0.001時，各項數(shù)據(jù)比較合理，說明數(shù)據(jù)和網(wǎng)絡(luò)結(jié)構(gòu)擬合較好。

2.2 SETAN分類性能評估

實驗數(shù)據(jù)選取UCI資源庫中6個具有代表性的離散數(shù)據(jù)集，每個數(shù)據(jù)集的數(shù)據(jù)信息如表2所示。實驗環(huán)境在Windows7操作系統(tǒng)上進行，集成開發(fā)環(huán)境Intellij Idea，Weka 3.8，硬件配置為Intel？Core（TM）i5-2410MCPU@2.30GHz，內(nèi)存4GB。實現(xiàn)了NB分類器、TAN分類器和SETAN分類器。

實驗的主要目的是驗證在同等時間復(fù)雜度下SETAN分類算法的有效性，本文采用一組常見的分類指標進行性能評估：準確率（Accuracy）、召回率（ Recall）、精確率（Precision）、F1值（F1 -measure）、AUC面積（AUC）。結(jié)合表3給出如下相關(guān)定義：

所用的CI測試閾值ε一般取值為0.01-0.05，BIC評分函數(shù)的懲罰系數(shù)ξ取0.001。在實驗中采用十折交叉有效性驗證的方法，對于數(shù)據(jù)集中的缺失值，將其作為一個單獨的值來處理，實驗結(jié)果取平均值。表4給出了本文提出的SETAN算法與NB、TAN算法的詳細實驗結(jié)果。

從表4可以看出，5個評價指標所得的結(jié)果大致相同，準確率越高，其它4個指標相應(yīng)越大。從各個評價指標上看，首先，SETAN在多分類或二分類數(shù)據(jù)集上相對有更好的分類效果;對于類別分布不均衡的數(shù)據(jù)集（如Balance、Car、Nursery），SETAN的各項分類指標均明顯優(yōu)于NB和TAN分類器;其次，SETAN分類模型也適用于不同數(shù)據(jù)規(guī)模的數(shù)據(jù)集，但在SPECT、Connect數(shù)據(jù)集上的分類精度較差，說明屬性數(shù)量對分類模型的影響比較明顯。其原因是，對于具有22個屬性的SPECT數(shù)據(jù)集，80個樣本相對于網(wǎng)絡(luò)復(fù)雜度而言數(shù)據(jù)集規(guī)模太小，分類模型欠擬合導(dǎo)致各項分類指標不佳;而對于Connect數(shù)據(jù)集，樣本數(shù)量和屬性數(shù)量均較大，相應(yīng)的計算復(fù)雜度較高，導(dǎo)致評分搜索得到的模型指標不太理想。

總之，在數(shù)據(jù)規(guī)模、類別分布、屬性數(shù)量這三個因素上，數(shù)據(jù)集的規(guī)模和類別分布對3種分類器的影響都比較小，而屬性數(shù)量會明顯影響分類效果。屬性越多，分類準確率相應(yīng)下降，但SETAN相比NB和TAN模型來說仍然占有優(yōu)勢。而且注意到，對于類別分布不均衡的數(shù)據(jù)集（如Balance，Car，Nursery），SETAN的分類準確率有明顯改善。

為了更直觀地看出提出的SETAN算法與TAN、NB算法的分類效果差異，圖2給出了三種算法的AUC面積的polar圖。由于三種算法在Mushroom數(shù)據(jù)集上的AUC面積非常接近，因此圖2沒有給出。在圖2中可以明顯看出SETAN在各個polar圖中面積都是最大的;此外，SPECT屬于二分類的小數(shù)據(jù)集，所以在圖3中給出了三種算法的ROC曲線圖?？梢钥闯觯谔幚韺傩詳?shù)較多的小數(shù)據(jù)集SPECT時，SETAN算法的分類結(jié)果也具有一定的參考價值。

3 結(jié)論

提出一種基于評分搜索的樹增強樸素貝葉斯分類器改進方法?？紤]到屬性對類貢獻程度有所不同，該分類算法在此約束條件下利用低階CI測試獲得候選無效屬性，隨后通過改進的BIC評分函數(shù)結(jié)合K2算法的方式確定網(wǎng)絡(luò)結(jié)構(gòu)中弧邊的方向，并去除無效屬性，進而構(gòu)建分類模型。本方法額外允許屬性沒有父結(jié)點或只有一個屬性父結(jié)點，從而構(gòu)建了一種更好的樹形貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)，去除了冗余屬性，增強了分類模型的可靠性。該算法和TAN分類模型的時間復(fù)雜度相同。實驗結(jié)果表明，與NB、TAN分類器相比，SETAN的分類準確率更高。下一步嘗試在大規(guī)模數(shù)據(jù)集上進行該分類算法的分布式并行化研究。

參考文獻

[1]

PEARL J. Probabilistic reasoning in intelligent systems： networksof plausible inference [J]. Computer Science ArtificialIntelligence， 1991， 70（2）：1022-1027.

[2] MURALIDHARAN V，SUGUMARAN V.A comparative study ofNalve Bayes classifier and Bayes net classifier for fault diagnosisof monoblock centrifugal pump using wavelet analysis [J].Applied Soft Computing， 2012 ， 12（ 8 ）：2023-2029.

[3]

FRIEDMAN N， GEICER D，GOLDSZMIDT M. Bayesian network classifiers [J]. Machine Learning ， 1997 ， 29（ 2-3 ） ：131-163.

[4] CAN H，ZHANC Y ， SONG Q. Bayesian belief network for positiveunlabeled learning with uncertainty [J]. Pattem Recognition Letters ， 2017 ， 90 ： 28-35.

[5]

JIANC L， CAI Z， WANC D ， et al. Improving tree augmented NaiveBayes for class probability estimation [J]. Knowledge -BasedSystems， 2012.26：239-245.

[6]王中鋒，王志海. TAN 分類器結(jié)構(gòu)等價類空間及其在分類器學(xué)習(xí)算法中的應(yīng)用 [J]. 北京郵電大學(xué)學(xué)報 ，2012，35（1）：72- 76.

[7] WONG M L.LEUNG K S. An e～ficient data mining method forlearning bayesian networks using an evolutionary algorithm-basedhyhrid approach [J]. IEEE Transactions on EvolutionaryComputation， 2004 ， 8（4） ：378-404.

[8] OUYANG W W，LIN X Z，REN Y.et al. TCM syndromesdiagnostic model of hypertension： Study based on tree augmentedNaive Bayes.[J]. IEEE ， 2011：834-837.

[9] MALDONADO A D，ROPERO R F，ACUILERA P A，et al.Continuous bayesian networks for the estimation of speciesrichness

[J]. Progress in Artificial Intelligence， 2015 ， 4

（ 3 -4）：49-57.

[10]馮月進，張鳳斌，最大相關(guān)最小冗余限定性貝葉斯網(wǎng)絡(luò)分類器學(xué)習(xí)算法[J].報：自然科學(xué)版 ， 2014，37（6）：71-77.

[11] ROBINSON R W. Counting unlaheled acyclic digraphs [M]//Combinatorial Mathematics V. Springer Berlin Heidelberg， 1977：28-43.

[12] SCHWARZ G. Estimating the dimension of a model[J]. Annals ofStatistics， 1978 ， 6（ 2 ）：15-18.

[13]

GREINER R ， ZHOU W.Structural extension to logistic regression：discriminative parameter learning of belief net classifiers [J].Machine Learning， 2005 ， 59（ 3） ：297-322.

[14] MADDEN M G. On the classification performance of TAN andgeneral Bayesian networks [J]. Knowledge -Based Systems，2009 ， 22（ 7 ） ：489-495.

[15] DRUCAN M M，WIERING M A. Feature selection for Bayesiannetwork classifiers using the MDL -FS score

[J]. IntemationalJournal of Approximate Reasoning， 2010 ， 51（6） ：695-717.