一種新的三支擴展TAN貝葉斯分類器

張春英，馮曉澤，劉 洋，馬逸濤，劉鳳春，高瑞艷，任 靜

1(華北理工大學 理學院，河北 唐山 063210) 2(華北理工大學 遷安學院，河北 唐山 063210) 3(河北省數據科學與應用重點實驗室，河北 唐山 063210)

1 引 言

樸素貝葉斯分類器(Naive Bayes classifiers，NB)由Duda和Hart于1973年首次提出，因簡單、高效而被廣泛應用，但樸素貝葉斯分類器基于屬性條件獨立性假設，應用時此假設很難滿足，故人們嘗試對這一假設條件進行一定程度的放松，考慮部分屬性間的相互依賴信息.文獻[1]提出一種樸素貝葉斯分類器的樹擴展—TAN貝葉斯分類器，它允許屬性節點最多只依賴于一個非類節點.目前關于TAN貝葉斯分類器的研究主要是網絡結構的構建，文獻[2]提出了擴展的TAN貝葉斯分類器——SETAN貝葉斯分類器，考慮條件屬性對類屬性的貢獻度差異，允許屬性沒有父節點，增強了分類準確性；文獻[3]利用不確定屬性間的依賴關系進行分類，提出了一種不確定正樹擴展樸素貝葉斯算法；文獻[4]提出了不考慮邊重定向的TAN分類器學習算法，構建時以最大化LCL為優化目標；文獻[5]采用條件對數似然方法增強了TAN貝葉斯分類器的類概率估計性能，提出了擴展的TAN貝葉斯分類器(ATAN)；雖然目前TAN的研究改進了分類模型，但這些分類模型均屬于二支決策——接受或拒絕.實際應用中的數據存在不完整不確定性，簡單的采取二支決策會對結果造成一定的損失.

三支決策[6，7]是Yao在粗糙集理論的研究過程中總結而來的一種理論方法，主要思想是將論域一分為三(正域、負域和邊界域)，對每個論域都制定不同的決策策略，尤其是將延遲決策作為處理信息難以做出決策的決策方式，其符合人類的思想與認知.盡管三支決策在很多領域已取得很多成果，但條件概率的計算面臨些問題[8].Yao 和 Zhou通過樸素貝葉斯模型估計條件概率，提出了一種樸素貝葉斯粗糙集模型，提高了計算效率[9]；文獻[10]將三支決策與樸素貝葉斯分類器結合起來，并用于垃圾郵件的分類，除了把郵件分為正常郵件，垃圾郵件外，允許用戶對于不確定的郵件進行進一步的檢查，通過實驗證明降低了誤分類率.

為了緩解三支樸素貝葉斯分類器屬性條件獨立性假設的問題，本文融合TAN貝葉斯分類器與三支決策，提出一種新的三支擴展TAN貝葉斯分類器：3WD-TAN.在三支分類規則制定時，利用TAN貝葉斯公式估計三支決策中的條件概率P(Cc|xh)，構建了3WD-TAN貝葉斯分類模型，并通過對比實驗驗證了算法有效性.

本文其余部分的結構如下：第2節介紹了TAN貝葉斯分類器的相關工作；第3節融合TAN貝葉斯分類器與三支決策，提出一種新的三支擴展TAN貝葉斯分類器，并制定3WD-TAN貝葉斯分類規則，設計3WD-TAN貝葉斯分類器的分類流程，以及分析該分類器的時間復雜度從理論上驗證可行性；第4節分析閾值(α,β)變化對分類結果的影響，并選取NB、TAN、SETAN算法進行對比實驗，說明該分類器的可行性.

2 TAN貝葉斯分類器

樹擴展樸素貝葉斯分類器(Tree Augmented Naive Bayesian Classification，TAN)由Friedman于1997年提出，是在樸素貝葉斯分類器的基礎上弱化屬性之間獨立性要求而進行的擴展.TAN能有效利用屬性間依賴信息，允許屬性節點最多有兩個父節點，其原理如下：

(1)

(2)

(3)

(4)

TAN貝葉斯分類器模型的詳細構建過程如下：

1) 計算任意兩個屬性之間的條件互信息I(ai,aj|Cc)，i≠j，構建完全無向圖；

(5)

2)構建最大權生成樹；

根據不產生回路的原則，由上步無向圖中邊的權重大小選擇邊，直到選擇n-1條邊為止，構建出最大權生成樹；

3)將無向圖轉換為有向圖；

任意選擇屬性節點為根節點，以根節點為起始其它節點為結束設置邊的方向，將無向圖轉換為有向圖；

4)增加類節點及其指向各個屬性節點的有向邊，構建一個TAN模型.

3 3WD-TAN貝葉斯分類器

約定：給定信息系統S=(U,A∪D,{Va|a∈A},{Ia|a∈A})，其中，U為有限論域；A是屬性集，表示為A={a1,a2,…,an}；D={C1,C2,…,Ck}表示k個不相交的決策類；Va是全部屬性值的集合；Ia:U→Va是信息函數，將U屬性a映射到Va，即Ia(x)∈Va.

本文通過融合TAN貝葉斯分類器與三支決策模型，提出了3WD-TAN貝葉斯分類器.本節將建立3WD-TAN貝葉斯分類規則，設計3WD-TAN貝葉斯分類器的分類流程，以及分析該分類器的時間復雜度從理論上驗證可行性.

3.1 3WD-TAN貝葉斯分類規則

構建3WD-TAN貝葉斯分類模型的關鍵是條件概率的估計以及3WD-TAN貝葉斯分類規則的建立，因為條件概率P(Cc|xh)很難從可觀察到的數值中估計，通常用貝葉斯公式進行變換.因此本文通過構建TAN貝葉斯分類器，利用TAN貝葉斯公式估計條件概率P(Cc|xh)，并考慮了屬性間的部分依賴關系，使之能夠取得較為精確的條件概率值.

(6)

將TAN貝葉斯公式(2)代入到式(6)中，由于在運算過程中，連加運算遠比連乘運算計算量小，故加入后使得運算更簡便[12].以最小風險理論為準則得到3WD-TAN貝葉斯分類規則：

(P)規則：如果：

則xh∈POS(α,β)(Cc)；

(N)規則：如果:

則xh∈NEG(α,β)(Cc)；

(B)規則：如果：

則xh∈BND(α,β)(Cc)；

(7)

其中：

(8)

3.2 3WD-TAN分類器設計及分析

3.2.1 分類器思想

為了解決傳統二支決策TAN貝葉斯分類器在處理不確定性數據時具有較高的錯分率，將三支決策思想與TAN貝葉斯分類器相融合，提出一種新的三支擴展TAN貝葉斯分類器：3WD-TAN.假設有訓練集U={x1,x2,…,xN}和測試集T={t1,t2,…,tP}.首先，根據訓練集U構建TAN貝葉斯分類器，利用式(5)計算任意兩個屬性的條件互信息I(ai,aj|Cc)，構建最大權生成樹，將無向圖轉為有向圖，增加類節點及指向各個屬性節點的有向邊，構建TAN模型；然后，考慮屬性間的部分依賴關系，通過TAN貝葉斯公式估計三支決策中的條件概率P(Cc|xh)，并建立3WD-TAN貝葉斯分類規則；最后，利用3WD-TAN貝葉斯分類器對測試集T進行三支分類.具體的流程如下：

算法.3WD-TAN Bayesian classification

輸入：訓練集U={x1,x2,…,xN}，測試集T={t1,t2,…,tP}，每個類別的閾值(αCc,βCc)

輸出：測試集T的分類結果{POS,NEG,BND}

1.構建TAN貝葉斯分類器

2.forai∈Ado

3.foraj∈Ado

4. 根據式(5)計算條件互信息I(ai,aj|Cc)

5.endfor

6.endfor

7.根據最大權生成樹算法，構建最大權生成樹

8.選擇屬性節點為根節點

9.forai∈Ado

10.以根節點為起始其它節點為結束設置邊的方向，將無向圖轉換為有向圖

11.endfor

12.增加類節點Cc

13.forai∈Ado

14.添加類節點指向各個屬性節點的有向邊

15.endfor

17.利用訓練好的分類器對測試集T進行分類，對測試集T中的樣本根據式(7)計算類Cc的正域、負域和邊界域；

18.fort=1,2,…,pdo:

26.endif

27.endfor

28.return測試集T的三支分類結果{POS,NEG,BND}.

3.2.2 復雜度分析

從整體上考慮，本文提出的3WD-TAN貝葉斯分類器主要分為3個部分：

1)步驟1-步聚15主要是根據訓練集U構建TAN貝葉斯分類器，此步主要耗時的是步驟2-步聚6中的計算任意兩個屬性之間的條件互信息I(ai,aj|Cc)和步驟7中的構建最大權生成樹；

②步驟7中構建最大權生成樹的時間復雜度為O(n2·logn)[13]；

一般情況下，N>logn，故在整個步驟1-步聚15構建TAN貝葉斯分類器的過程中，時間復雜度為O(N·n2)；

3)步驟17-步聚27對測試集T中的P個樣本進行分類，時間復雜度為O(P).

綜上，3WD-TAN貝葉斯器的時間復雜度為O(N·n2)+O(k)+O(P)=O(N·n2)+O(P).與TAN貝葉斯分類器相比，主要的區別在于步驟16-步聚17，故額外的時間復雜度為O(P)，因此本文提出的3WD-TAN分類器是可行的.

4 實驗及結果分析

4.1 實驗環境

為了說明3WD-TAN分類器的性能，實驗選取UCI機器學習數據集中的5個不同規模的數據.數據集基本信息如表 1所示.該實驗在基于Inter Core i7-6700的處理器，RAM為8.00GB的WIN7系統環境下的PyCharm 2018.3.4版本下實現.

表1 數據集基本信息Table 1 Dataset basic information

在實驗的評價標準上，采取了Jia 和Shang提出的基于三支決策分類問題的評價標準[14]，如表 2所示.

表2 基于三支決策分類的混淆矩陣Table 2 Confusion matrix based on the three-way decision classification

其中n*·表示實際為類別·時判別為*的樣本個數.

準確率(Accuracy)是對分類器在測試集上表現的總體評價，表示被正確劃分的樣本占被確定劃分的樣本的比例，如式(9)所示.

(9)

召回率(Recall)表示預測為正類占實際為正類的比例，實際為正類的樣本不僅要考慮劃分到正域、負域的正類樣本，同時也要考慮劃分到邊界域的正類樣本，如式(10)所示.

(10)

4.2 實驗過程及結果分析

本文采用準確率(Accuracy)、召回率(Recall)分類指標進行性能評估，在實驗中采用十折交叉驗證的方法.對數據集的缺失值進行簡單處理，對于條件屬性，數值型用平均值代替，非數值型用眾數代替；決策屬性用眾數代替.

4.2.1 閾值(α,β)變化分析

閾值(α,β)是3WD-TAN分類器的一個重要參數，通常介于0,1之間且α>β，(α,β)的選擇會影響3WD-TAN的結果.為了分析不同的閾值(α,β)對結果的影響情況，本文在(0,1)之間以0.05為步長選取不同的(α,β)對UCI數據集進

圖1 Vote準確率Fig.1 Vote accuracy

圖2 Vote召回率Fig.2 Vote recall

圖3 Car準確率Fig.3 Car accuracy

圖4 Car召回率Fig.4 Car recall

行實驗，并以Vote和Car數據集為代表分析閾值(α,β)變化對結果的影響.由于變化范圍較小，為了更好的分析閾值變化對準確率和召回率的影響，將結果集中的部分展示(只展示了每個數據集的其中一種類別的部分結果情況)，如圖1-圖4所示.表3中列出了不同數據集在分類結果最優時所對應的閾值(α,β).

3WD-TAN分類器要求閾值(α,β)介于0,1之間且α>β.故在圖1-圖4中，當β≤α時，設置準確率和召回率的結果為0，主要討論閾值α>β的情況并以Vote和Car數據集為代表分析閾值(α,β)變化對結果的影響.

圖1與圖2分別為Vote數據集在不同閾值(α,β)下的準確率和召回率的變化情況.由圖1可知，3WD-TAN在數據集Vote下的準確率總體上在97.7%以上.當(αC1，βC1)在(0, 0.50)范圍迭代變化時，準確率基本持平于97.7%；當αC1的迭代范圍為(0.55, 0.90)，βC1的迭代范圍為(0, 0.70)時，準確率增加到100%；當αC1的迭代范圍為(0.95, 1)，βC1的迭代范圍為(0, 0.70)時，準確率又降低到98.0%；當(αC1，βC1)在(0.75, 1)范圍迭代變化時，準確率從97.7%逐漸降低到80.4%.由圖2可知，3WD-TAN在數據集Vote下的召回率總體上在99.0%以上.當(αC1，βC1)在(0,0.55)范圍迭代變化時，召回率基本持平于99.0%；當αC1的迭代范圍為(0.60, 0.65)，βC1的迭代范圍為(0, 0.65)時，召回率增加到100%；當αC1的迭代范圍為(0.70, 1)，βC1的迭代范圍為(0, 1)時，召回率從99.0%逐漸降低到89.3%.當閾值(αC1,βC1)=(0.65,0.40)，(αC2,βC2)=(0.60,0.45)時，準確率和召回率高達100%.故當閾值(α,β)的取值合適時，3WD-TAN的準確率和召回率優于NB、TAN和SETAN.

表3 不同數據集下每個類別的閾值Table 3 Thresholds for each class under different datasets

圖3與圖4分別為Car數據集在不同閾值(α,β)下的準確率和召回率的變化情況.由圖3可知，3WD-TAN在數據集Car(C1類)下的準確率總體上在94.1%以上.當(αC1，βC1)在(0, 0.50)范圍迭代變化時，準確率基本持平于94.1%；當αC1的迭代范圍為(0.55, 0.80)，βC1的迭代范圍為(0, 0.80)時，準確率增加到95.1%；當αC1的迭代范圍為(0.85, 0.95)，βC1的迭代范圍為(0, 0.95)時，準確率增加到98.0%.由圖4可知，3WD-TAN在數據集Car(C1類)下的召回率總體上在99.0%以上.當(αC1，βC1)在(0, 0.55)范圍迭代變化時，召回率基本持平于99.0%；當αC1的迭代范圍為(0.60, 0.70)，βC1的迭代范圍為(0, 0.70)時，召回率增加到100%；當αC1的迭代范圍為(0.75, 0.85)，βC1的迭代范圍為(0, 0.85)時，召回率又降低到99.0%；當αC1的迭代范圍為(0.90, 1)，βC1的迭代范圍為(0, 1)時，召回率從99.0%逐漸降低到81.1%.當閾值(αC1,βC1)=(0.85,0.60)、(αC2,βC2)=(0.80,0.50)、(αC3,βC3)=(0.75,0.55)和(αC4,βC4)=(0.65,0.40)時，3WD-TAN在數據集Car上的準確率為91.9%，略低于SETAN，但高于NB和TAN；召回率為97.0%，優于NB、TAN和SETAN.

綜上，當閾值(α,β)取值合適時，3WD-TAN分類器的準確率和召回率在多數情況下優于NB、TAN和SETAN分類器.

4.2.2 對比實驗

表 4給出了本文提出的3WD-TAN分類器與NB、TAN、SETAN分類器在5種數據集下關于表3所示的閾值參數下的準確率和召回率對比結果.

表4 準確率、召回率對比結果Table 4 Accuracy,recall comparison results

由表4得出，當閾值(α,β)取一定值時，絕大數情況下，本文給出的三支擴展TAN貝葉斯分類器(3WD-TAN)在二分類和多分類數據集上的結果高于SETAN分類器以及傳統的NB、TAN分類器.且3WD-TAN貝葉斯分類模型適用于不同規模的數據集.

由二分類實驗結果可知，3WD-TAN分類器在數據規模較大，屬性較多的Mushroom數據集上的結果優于NB、TAN和SETAN分類器；對于數據規模較小，屬性數目中等的Vote和Breast Cancer數據集，3WD-TAN分類器的準確率高于對比的分類器較多，故在處理數據規模小，屬性數較多的數據集時，3WD-TAN依然效果良好.

由多分類實驗結果可知，3WD-TAN分類器在數據規模中等，屬性數目較小的Balance數據集上的結果優于NB、TAN和SETAN分類器；對于數據規模中等，屬性數目中等的Car數據集，3WD-TAN分類器的準確率高于NB和TAN，略低于SETAN，但3WD-TAN分類器的召回率高于NB、TAN和SETAN.

從數據集的規模、屬性數和類別數3個角度綜合分析.相比較數據規模與類別數目，屬性數量對分類結果的影響較大，但3WD-TAN貝葉斯分類模型的分類效果要優于NB、TAN和SETAN分類模型.

5 結束語

考慮到在分類過程中將不確定的對象強制劃分到某個類中與人們的實際決策并不符合，文中將三支決策思想與TAN貝葉斯分類器相融合，提出了一種新的三支擴展TAN貝葉斯分類器(3WD-TAN)，將傳統的TAN分類器推廣為三支TAN分類模型.考慮屬性間的部分依賴關系，通過構建TAN貝葉斯分類模型計算三支決策中的條件概率，改善了條件概率的計算，并一定程度上提高了TAN貝葉斯分類器的精確率.通過5個數據集的對比實驗，驗證3WD-TAN具有較高的準確率和召回率.然而，該方法是針對靜態數據集進行分類的，下一步將考慮數據的動態特征，研究構建動態的3WD-TAN半樸素貝葉斯分類模型.同時TAN分類器的屬性間依賴存在一定的限制，可考慮進一步研究3WD-貝葉斯網絡模型.