基于多屬性聯合的樸素貝葉斯分類算法

謝小軍，陳光喜

(1.桂林電子科技大學 數學與計算科學學院，廣西 桂林 541004；2.桂林電子科技大學 廣西高校圖像處理實驗室，廣西 桂林 541004)

基于多屬性聯合的樸素貝葉斯分類算法

謝小軍1，陳光喜2

(1.桂林電子科技大學 數學與計算科學學院，廣西 桂林 541004；2.桂林電子科技大學 廣西高校圖像處理實驗室，廣西 桂林 541004)

樸素貝葉斯分類算法由于條件獨立性假設對屬性施加了一定的限制，這可能會降低分類性能。針對此問題，為了削弱條件獨立性假設對分類結果帶來的負面影響，從結構擴展的角度提出了一種基于多屬性聯合的樸素貝葉斯分類算法。該算法通過計算條件屬性組合相對于決策屬性依賴度的大小，選擇最大相對屬性依賴度的屬性組合進行聯合作為新的條件屬性。通過實驗仿真，結果表明該方法可行而且有效，特別是對一些屬性之間關聯性比較強的數據集，分類效果提高尤為明顯。

樸素貝葉斯；分類；粗糙集理論；相對屬性依賴度；屬性聯合

0 引 言

樸素貝葉斯分類器是一種基于貝葉斯統計理論的有監督學習方法，對已標記訓練樣本進行分類時，基于一個強有力的假設，即訓練樣本中的所有屬性均獨立于訓練樣本。然而此假設在現實中往往不成立，因此，研究人員做了大量工作來削弱樸素貝葉斯獨立性假設。Jiang等[1]對改進樸素貝葉斯的方法做了綜述，這些改進方法粗略分為：結構擴展、特征選擇、數據擴展、局部學習和屬性加權五大類。基于屬性加權的思想，國內許多研究人員做了大量研究工作。文獻[2-5]分別使用粗糙集屬性重要度、屬性之間互信息、屬性之間相關系數、分類概率等建立了加權樸素貝葉斯分類模型。Wu Jia等[6]提出了一種自適應屬性加權的樸素貝葉斯算法(AISWNB)，該算法通過使用人工免疫系統里的免疫理論來搜索最優權重值，并能夠自我調整權重值，從而得到更精確的條件概率。Lee C H等[7]提出了一種梯度下降的特征值加權的樸素貝葉斯分類學習方法(VWNB)，該算法通過梯度下降法計算特征值的最優權重，為每一個特征值分配不同的權重。Tütüncü G Y等[8]提出一種聚合的模糊樸素貝葉斯分類。從結構擴展的角度，Kononenko[9]于1991年提出的半樸素貝葉斯分類模型就是一種經典的通過結構擴展改進樸素貝葉斯算法，該算法將獨立性放寬到了屬性的子集之間，從而有效減少了屬性的獨立性假設對分類性能的不良影響。Friedman[10]于1997年提出樹增強樸素貝葉斯分類模型(TAN)，它要求屬性節點除了類節點可以作為父節點外，至多只能擁有一個其他的非類屬性作為其父節點，故保留了其結構的特點，并放松了獨立性假設，從而使屬性之間有著簡單的依賴關系。Webb等[11]提出了一種平均單依賴估計(AODE)的方法來削弱屬性獨立性假設，該方法為分類器的所有屬性平均分配同一個約束類，弱化了獨立性假設，擴充了算法結構，而且大多數情況下具有較好的綜合性能。但是存在如下缺陷：

(1)在AODE模型中,所有的結構擴展的樸素貝葉斯分類模型中，所有的屬性節點對分類的影響是相同的,這往往并不成立，使用不同的屬性節點為父節點的擴展樸素貝葉斯分類模型在分類測試中的影響程度應該是不同的。

(2)AODE算法屬于組合學習的分類算法,在進行訓練時需要訓練出多個模型,然后將訓練得到的多個模型對測試實例進行分類。故該算法在時間和簡潔性方面要遜色于單個模型的分類算法。

針對問題(1)，文獻[12]提出一種加權平均的單依賴估計模型(WAODE)，并設計了四種加權的方法；針對問題(2),文中提出一種多屬性聯合的樸素貝葉斯分類算法，該算法也是從結構上擴充了樸素貝葉斯分類算法，削弱了條件獨立性假設，并且結構擴展更加靈活，最終只要學習一個模型進行分類測試。

基于粗糙集理論[13-14]，通過計算條件屬性組合相對于決策屬性的依賴度大小，給出了一種基于屬性最大依賴度的聯合屬性組的方法。通過實驗證明，該方法在一定程度上能夠有效提高分類效果。

1 樸素貝葉斯分類模型研究

樸素貝葉斯分類模型是貝葉斯分類模型中結構最為簡單的模型。由一個父節點和多個子節點構成的樹狀結構，如圖1所示。

圖1 樸素貝葉斯分類模型

它假設在類屬性變量已知時，各條件屬性變量是相互獨立的。然而現實生活中，此假設在很多情況下并不成立，即當屬性之間有很強的依賴時，這個假設會對樸素貝葉斯分類模型的分類準確率產生負面影響，但另一方面也大大簡化了貝葉斯分類模型構建的復雜性，故樸素貝葉斯分類模型具有簡單和高效等特點，從而得到了廣泛應用[15-18]。

假定輸入訓練數據集D={X1,X2,…,Xp}，其中A1,A2,…,An表示n個屬性，C表示m個類別C1,C2,…,Cm。待分類樣本X=〈x1,x2,…,xn〉，其中xi為屬性Ai的值，則X屬于類別Ck的概率為：

(1)

由于計算P(X|Ck)過于復雜，所以假定n個屬性變量是相互獨立的，得：

(2)

由于P(X)為常數，因此只要最大化P(X|Ck)P(Ck)，則根據極大后驗假設得樸素貝葉斯分類模型為：

(3)

其中，概率P(Ck)和P(xi|Ck)的計算公式如下：

(4)

(5)

其中，n為訓練實例個數；Cj為實例j的類標記；xji表示第j個訓練實例的第i個屬性的值，其中:

(6)

整個樸素貝葉斯分類模型的實現主要分三個步驟：

(1)數據預處理。此過程的目的是為NBC的分類做鋪墊，將獲取的數據全部轉化為數值型，并將缺失數據進行補齊，若是連續數據則需要對其離散化。最后將數據分為兩部分：訓練數據與測試數據。

(2)構造分類模型。此過程的任務就是學習分類模型，統計各類別在訓練實例中出現頻率和條件屬性變量出現在各類別的條件概率值。其輸入是訓練樣本，輸出是分類模型。

(3)測試分類模型。此過程的任務是利用分類模型對測試數據集進行分類，其輸入是分類模型和測試數據集，輸出是測試數據集的分類結果。

2 結構擴展的樸素貝葉斯分類模型

結構擴展的樸素貝葉斯分類模型(AugmentedNaiveBayesian，ANB)，是基于樸素貝葉斯分類模型中的全部屬性變量都是類屬性的馬爾可夫覆蓋，對最初的樸素貝葉斯分類模型的結構進行擴展。基本原理：屬性變量之間的關聯關系通過有限的有向邊表示,從而從結構上擴展了樸素貝葉斯分類模型的結構。該思想放松了樸素貝葉斯分類模型的條件獨立性假設，并且擴展了樸素貝葉斯分類模型的網絡結構。ANB的關鍵是如何設計一個高效的結構擴展算法。關鍵點是要無約束地構造出所有屬性節點的父節點,必須要學習由條件屬性變量A1,A2,…,An組成的結構。然而,學習無限制的貝葉斯網絡結構己被證明是一個NP-難問題。于是,比較現實的方法是學習有限制條件貝葉斯網絡結構。為此,廣大研究者提出許多經典的模型和算法。這里主要研究分析了AODE。基本思想是除類屬性節點外為所有的其他屬性平均分配同一個約束類。圖2給出了一個AODE結構的例子。

圖2 AODE結構實例

對于測試實例X=〈x1,x2,…,xn〉，ANB使用式(7)進行分類測試：

(7)

應用乘法規則有：

(8)

應用馬爾可夫原理可得到：

(9)

ANB的構造步驟如下：

算法：ANB(D,X)。

輸入：訓練實例集D和測試實例X；

輸出：C(X)。

Step1：對于訓練實例集D，應用結構學習算法找到所有屬性節點的父節點；

Step2：根據式(9)預測測試實例X的類標記C(X)；

Step3：返回C(X)。

3 基于多屬性聯合的樸素貝葉斯分類算法

3.1 粗糙集相關概念

(1)在信息系統S=(U,Q,D,V,f)中，任何屬性P?Q，知識P的不可分辨關系定義為：

(10)

其中，U為論域。

記I為U中一組等價關系。對于X?U，集合X關于I的下近似是根據已有知識斷定，那些一定是屬于X的對象所組成的最大集合，有時也稱為X的正區(positiveregion)，記做POS(X)[16-17]：

(11)

集合X關于I的上近似(Upperapproximation)是指可能屬于X的一些元素所組成的最小集合：

(12)

(2)屬性依賴度：對于任意屬性qi∈Q，類屬性變量集合D與條件屬性變量qi的重要性是由D集合與qi之間的相互依賴程度所決定。D集合與qi之間的相互依賴程度定義為：

(13)

3.2 基于粗糙集屬性依賴度的多屬性聯合

文中基于結構擴展的思想，其中半樸素貝葉斯分類模型主要考慮如何有效而快速構成“組合屬性”，當目標數據集過于龐大，或者數據集中的屬性太多，那么進行屬性組合的時間將呈指數級增長，對運行環境有一定的要求，否則可能會造成系統的崩潰，因此半樸素貝葉斯分類模型在使用上有一定的局限性，最好是針對規模較小的數據集；而AODE算法則需要構造多個模型進行學習訓練,故在時間上和簡潔性上要遜色于單個模型的分類算法。總結以上兩種算法的不足，文中基于粗糙集中屬性依賴度的概念，提出了一種能夠快速對屬性進行組合的方法，實際上也是從結構上擴展了樸素貝葉斯算法，并且最終只要通過學習一個模型對測試實例進行預測。

對于信息系統S=(U,Q,D,V,f)，Q={q1,q2,…,qn}，n為屬性個數，k為選擇進行聯合的屬性個數，1≤k≤n，記A為經過聯合后得到的新屬性組集合。當k=1時即為樸素貝葉斯分類模型。文中主要是研究當k=2,3時的屬性聯合算法，即基于雙屬性聯合與三屬性聯合的樸素貝葉斯分類算法。在選擇聯合屬性時，基于聯合條件屬性相對于決策屬性依賴度的大小，選擇最大相對依賴度作為聯合條件屬性。這是有意義的。因為屬性的相對依賴度的大小反映了聯合條件屬性相對于決策屬性的一致程度，相對依賴度越大，在一定程度上說明該聯合條件屬性相對于決策屬性一致性就越強，也就說明該聯合條件屬性相對于決策屬性越重要。

首先給出k=2時屬性聯合后屬性組的值的定義，k=3時可以類比得到。

由式(2)可知：

其中

(14)

下面給出k=2時屬性聯合實現的過程。

算法1：雙屬性聯合的樸素貝葉斯分類算法(TwoPropertiesCombinedNaiveBayesianClassification，Two-PCNBC)。

輸入：決策表S=(U,Q,D,V)；

Step1：令j=1，qj∈Q，A=?；

Step2：對?qi∈Q,i=1,2,…,n，利用式(13)計算所有的γ(qj,qi)(D)，選擇滿足γaj(D)=max{(γ(qj,qi)(D))}的聯合屬性組合aj=(qj,qi)加入到A，即令A=A∪{aj}；

Step3：令j=j+1；

Step4：如果j>n，則終止，否則轉Step2。

通過上述過程最終得到新的屬性組集合A={a1,a2,…,an'}，1≤n'≤n，可以發現，此方法對兩個屬性進行聯合后的屬性個數最多為n，對?ai都有ai=(qi,q0)。其中q0∈Q時，即為AODE算法，此時的q0即為所有條件屬性除去決策屬性另一個父節點，即約束類。

當k=3時，屬性聯合的實現過程如下：

算法2：三個屬性聯合的樸素貝葉斯分類算法(ThreePropertiesCombinedNaiveBayesianClassification，Three-PCNBC)。

輸入：決策表S=(U,Q,D,V)；

Step1：令j=1，j'=1，qj∈Q，A=?；

Step2：對?qi,qt∈Q,i=j+1,…,n,t=1,2,…,n，利用式(13)計算γ(qj,qi,qt)(D)，選擇滿足γ(qj,qi,qt0)(D)=max{γ(qj,qi,qt)(D)}的聯合屬性組合(qj,qi,qt0)，記為新的屬性aj'，若聯合屬性組合(qj,qi,qt0)已在A中存在，則直接轉Step3，否則將aj'加入到新的屬性集合中，令A=A∪{ai}，j'=j'+1；

Step3：令i=i+1；

Step4：如果i

Step5：令j=j+1；

Step6：如果j≥n-1，則終止，否則轉向Step2。

下面給出基于粗糙集屬性依賴度的多屬性聯合樸素貝葉斯算法的步驟：

Step1：數據預處理。將數據全部轉化為數值型，并將缺失數據進行補齊，若是連續數據則將數據進行離散化。

Step2：確定k值，若k=2則使用算法1進行條件屬性聯合；若k=3則使用算法2進行屬性聯合。通過聯合后得到新信息系統S'=(U',A,D,V',f)。

Step3：將得到的新信息系統S'中數據集分成訓練樣本和待分類樣本，對訓練樣本的每一個樣本對象X進行遍歷，利用式(14)計算所有的先驗概率值，即P(xi/Ck)以及在類別Ci下各個條件屬性xi的取值概率P(xi/Ck)。

Step4：根據式(1)計算待分類樣本中待分類對象X屬于其他各類別的后驗概率，并通過式(3)得出最終分類結果。

4 實驗仿真及分析

為了驗證算法的可行性和有效性，下面將比較傳統的樸素貝葉斯分類算法(NB)、樹增強型樸素貝葉斯分類模型(TAN)、加權的平均單依賴估計(WAODE)以及文中提出的屬性聯合算法(Two-PCNBC和Three-PCNBC)在分類精度之間的差別。選用UCI機器學習庫中的8個數據集進行實驗仿真測試，數據集見表1，所有數據都經過預處理。

表1 預處理后的數據集

首先對數據集的順序進行隨機打亂，采用分割數據集的方法進行測試，其中訓練集為70%，測試集為30%，以十折交叉驗證的分類精度來評價這7種算法的分類效果。實驗仿真結果見表2。

表2 實驗結果

從表2可以看出，文中提出的基于粗糙集屬性依賴度的屬性聯合樸素貝葉斯算法是可行的，可以從數據中挖掘更多的信息，特別是相對于數據集Tic-tac-toe和Iris中屬性之間關聯性比較強的數據集，分類效果提高尤為明顯。從算法Two-PCNB和Three-PCNB的比較發現，并不是聯合的屬性個數越多就越好，有的數據集選擇兩個屬性進行聯合比選擇三個屬性進行聯合的效果反而要更好些。而對數據集Wine，發現對屬性聯合時反而降低了它的分類精度，這是因為在離散化時得到的單個屬性的屬性值個數比較多，導致屬性聯合時對應的屬性值域大大增加，從而增加了屬性的復雜度，在一定程度上對分類效果產生了負面影響。所以文中算法更適合屬性個數相對較小、屬性對應的屬性值域比較集中的數據集。

總體上，通過圖3可以看出，文中算法的改進效果還是相當不錯的。

圖3 8個數據集的平均分類準確率比較

5 結束語

文中基于粗糙集理論，結合粗糙集中屬性相對依賴度的概念，提出了一種基于最大相對屬性依賴度的屬性聯合樸素貝葉斯分類算法。通過平均選擇適當的屬性個數進行聯合，在8個數據集進行了仿真測試實驗，并與最新提出的相關算法進行比較，表明了該方法的有效性和可行性。如何改進在進行屬性聯合時屬性值增加的問題，以及將算法應用到現實中一些特定的數據都將作為下一步的研究工作。

[1]JiangL,ZhangH,CaiZ.AnovelBayesmodel:hiddenNaiveBayes[J].IEEETransactionsonKnowledge&DataEngineering,2008,21(10):1361-1371.

[2] 鄧維斌,王國胤,王 燕.基于RoughSet的加權樸素貝葉斯分類算法[J].計算機科學,2007,34(2):204-206.

[3] 張明衛,王 波,張 斌,等.基于相關系數的加權樸素貝葉斯分類算法[J].東北大學學報:自然科學版,2008,29(7):952-955.

[4] 鄭 默,劉瓊蓀.一種屬性相關性的加權貝葉斯分類算法研究[J].微型機與應用,2011,30(7):96-98.

[5] 張步良.基于分類概率加權的樸素貝葉斯分類方法[J].重慶理工大學學報:自然科學版,2012,26(7):81-83.

[6]WuJ,PanS,ZhuX,etal.Self-adaptiveattributeweightingforNaiveBayesclassification[J].ExpertSystemswithApplications,2015,42(3):1487-1502.

[7]LeeCH.AgradientapproachforvalueweightedclassificationlearninginnaiveBayes[J].Knowledge-BasedSystems,2015,85(C):71-79.

[8]TütüncüGY,KayaalpN.AnaggregatedfuzzynaiveBayesdataclassifier[J].JournalofComputational&AppliedMathematics,2015,286(C):17-27.

[9]KononenkoI.Semi-naiveBayesianclassifier[C]//EWSL-91.Berlin:Springer,1991:206-219.

[10]FriedmanN,GeigerD,GoldszmidtM.Bayesiannetworkclassifiers[J].MachineLearning,1997,29(2):131-163.

[11]WebbGI,BoughtonJR,WangZ.NotsonaiveBayes:aggregatingone-dependenceestimators[J].MachineLearning,2005,58(1):5-24.

[12]JiangLiangxiao,ZhangH,CaiZhihua,etal.Weightedaverageofone-dependenceestimators[J].JournalofExperimental&TheoreticalArtificialIntelligence,2012,24(2):219-230.

[13]Grzymaa-BusseJW,PawlakZ,SowiskiR,etal.Roughset[J].CommunicationsoftheACM,1995,38(11):800-805.

[14] 王國胤,姚一豫,于 洪.粗糙集理論與應用研究綜述[J].計算機學報,2009,32(7):1229-1246.

[15] 馬小龍.一種改進的貝葉斯算法在垃圾郵件過濾中的研究[J].計算機應用研究,2012,29(3):1091-1094.

[16] 張 輪,楊文臣,劉 拓,等.基于樸素貝葉斯分類的高速公路交通事件檢測[J].同濟大學學報:自然科學版,2014,42(4):558-563.

[17] 朱克楠,尹寶林,冒亞明,等.基于有效窗口和樸素貝葉斯的惡意代碼分類[J].計算機研究與發展,2014,51(2):373-381.

[18] 蘇 中,張宏江,馬少平.基于貝葉斯分類器的圖像檢索相關反饋算法[J].軟件學報,2002,13(10):2001-2006.

Naive Bayes Classification Algorithm Based on United Multi-attribute

XIE Xiao-jun1，CHEN Guang-xi2

(1.School of Mathematics and Computer Science,Guilin University of Electronic Technology,Guilin 541004,China;2.Guangxi University Image Processing Laboratory,Guilin University of Electronic Technology,Guilin 541004,China)

Naive Bayes classification algorithm imposes certain restrictions on the properties due to the conditional independence assumption,which may reduce the classification performance.Aiming at this problem,in order to weaken the negative influence of conditional independence assumption on the classification results,a new Naive Bayesian classification algorithm based on multi attributes is proposed from the point of view of structure expansion.In this algorithm,the combination of the maximum relative attribute dependency is selected as a new condition attribute by computing the size of the combination of the conditional attributes with respect to the decision attribute.The experiment results show that it is feasible and effective，especially for some of the properties between the correlation stronger data sets,classification effect is particularly obvious.

Naive Bayes;classification;rough set theory;relative attribute dependency;attribute combination

2016-02-26

2016-06-15

時間：2016-11-22

廣西壯族自治區自然科學基金(2013GXNSFC019330)；廣西壯族自治區高校科研資助項目(2013YB086)

謝小軍(1990-)，男，碩士研究生，研究方向為數值計算與軟件應用；陳光喜，教授，研究方向為可信計算、圖像處理。

http://www.cnki.net/kcms/detail/61.1450.TP.20161122.1228.038.html

TP181

A

1673-629X(2016)12-0077-05

10.3969/j.issn.1673-629X.2016.12.017