一種TAN分類器改進方法

張坤　陳曦　宋云　傅明

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

關鍵詞：樹增強樸素貝葉斯;分類網絡;評分函數：

中圖分類號：TP311.1

文獻識別碼：A

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

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

1 基于BIC評分函數的SETAN分類器

1.1 TAN模型

1.1.1 TAN模型

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

1.1.2 STAN模型

評分與搜索方法是當前常見的一種貝葉斯網絡結構學習方法，它將網絡結構學習轉化成最優化問題，學習目標即搜索評分較高的網絡結構。評分搜索的結構學習方法分為兩步：網絡結構評分函數和網絡結構學習算法的確定。一旦定義好評分函數，貝葉斯網絡結構學習問題就是一個最優化搜索問題。

①評分函數

假設給定完整訓練集D，D= {X1，X2，…，X_n}，G是以X1，X2，…，X_n為結點的貝葉斯網絡。假設數據集滿足獨立同分布假設，則G相對于數據D的優劣可以用評分函數來度量。即，探索最佳貝葉斯網絡結構，就是找到可使得評分函數最大化的一個有向無環圖G。即

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

②模型描述

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

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

1.2 SETAN模型

1.2.1 理論分析

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

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

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

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

1.2.2 SETAN模型

①CI測試

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

②改進TAN模型

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

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

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

1.2.3 算法描述

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

1，提出SETAN網絡結構，在TAN結構基礎上中放松了每個屬性結點的父結點選擇條件，允許部分屬性沒有類父結點，在保證同等計算復雜度下提高了分類模型的可靠性。

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

3，利用改進的BIC評分函數對局部最優無環圖進行貪婪查找，從而獲得最終的SETAN網絡結構。進一步去除無效結點，提高算法的分類精度。下面給出構建SETAN結構圖的一般性過程。

1.2.4 時間復雜度分析

SETAN分類器學習算法主要分為兩個部分：

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

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

2 實驗結果與分析

2.1 改進的BIC評分函數評估

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

從表1的實驗結果可以看出，ξ= 0.01時，Asia網絡和Alarm網絡結構缺式邊數量相對比較多，沒有增加邊，說明懲罰系數偏大，導致數據和網絡結構欠擬合;ξ= 0.0001時，網絡結構增加邊相對較多，導致數據和網絡結構過擬合;而當ξ= 0.001時，各項數據比較合理，說明數據和網絡結構擬合較好。

2.2 SETAN分類性能評估

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

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

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

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

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

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

3 結論

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

參考文獻

[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 分類器結構等價類空間及其在分類器學習算法中的應用 [J]. 北京郵電大學學報 ，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]馮月進，張鳳斌，最大相關最小冗余限定性貝葉斯網絡分類器學習算法[J].報：自然科學版 ， 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.