王 峻

(淮南師范學院 計算機學院, 安徽 淮南 232001)

樸素貝葉斯分類器[1]是一種簡單有效的分類方法，在人工智能、統(tǒng)計決策等領(lǐng)域得到廣泛應用。其屬性之間相互條件獨立的假設(shè)，忽略掉了屬性間相關(guān)性的客觀存在。在實際應用中，屬性間相關(guān)性和屬性對分類的影響都不完全相同，使得它的分類性能受到一定的影響。

屬性是數(shù)據(jù)集中最基本的組成部分，屬性的選擇和屬性間的相關(guān)性是影響貝葉斯分類器的主要因素，也是改善貝葉斯分類器性能的主要方法。程玉虎等[2]提出一種可變選擇性貝葉斯分類器,運用最大相關(guān)最小冗余方法選擇對分類最有效的屬性；徐光美[3]提出運用擴展信息標準選擇與分類最相關(guān)的屬性；李宏磊等[4]提出一種垂直切換算法，以降低因?qū)傩詶l件獨立假設(shè)而導致的分類性能影響。擴展貝葉斯分類器可以通過添加有向邊的方式表達屬性間的相關(guān)性，例如Friedman等[5]提出一種TAN分類器，每個屬性可以擁有一個非類別的父結(jié)點，通過添加有向邊的方式，按照樹型結(jié)構(gòu)的形式將屬性與非類別的父結(jié)點的相關(guān)性表達出來。Cheng J等[6]提出一種BAN分類器，每個屬性擁有不止1個非類別的父結(jié)點，完全放寬了屬性間獨立性的要求，屬性間的相關(guān)性得以充分表達。爬山搜索算法(HCS)和超父結(jié)點算法(SP)是選擇最優(yōu)父結(jié)點的有效算法[7]。石洪波[8]建立了一個雙層限定的貝葉斯分類模型表達屬性間的相關(guān)性。Kononenko[9]提出一種Seminaive Bayesian classifier，通過屬性分組將屬性相關(guān)性較強的屬性分在一組，同一分組內(nèi)允許屬性間存在相關(guān)性。李玉杰[10]提出可以運用貪婪選擇算法選擇屬性的最佳分組，同一分組內(nèi)允許屬性間存在相關(guān)性。

本文在運用x2統(tǒng)計對屬性相關(guān)性進行分析的基礎(chǔ)上，將屬性相關(guān)性較強的屬性分在一組，各個屬性分組之間相互獨立。在每個屬性分組中，在非類的父節(jié)點和子節(jié)點之間添加一條有向邊來表示相關(guān)屬性間的相關(guān)性，在屬性分組內(nèi)擴展樸素貝葉斯分類器。

1 樸素貝葉斯分類器NBC(Naive Bayes Classifiers)

樸素貝葉斯分類是通過計算條件概率實現(xiàn)分類預測，條件概率計算的理論依據(jù)是貝葉斯定理[11]，但它的前提條件是相互條件屬性相對獨立且對分類的影響相同。貝葉斯定理：

(1)

其中：P(H)是先驗概率，P(X|H)是條件概率，P(H|X)是進行分類預測的后驗概率。

樸素貝葉斯分類是根據(jù)貝葉斯定理，在計算條件后驗概率的基礎(chǔ)上，按照后驗概率值的大小完成對訓練數(shù)據(jù)集中的樣本的分類預測。

令S={A1,A2,……An,C}是訓練數(shù)據(jù)集，其中A1,A2,……An是屬性變量，C={c1,c2,……cm}是類別變量，ai是屬性Ai的取值，實例xi=(a1,a2,……an)屬于類cj的概率，由貝葉斯定理可表示為：

(2)

其中：P(cj)是類cj的先驗概率，P(cj|a1,a2,……,an)是后驗概率。

樸素貝葉斯分類基于最大后驗規(guī)則，測試集中的實例xi將被分配給后驗概率值最大的那個類。

樸素貝葉斯分類的前提條件是屬性間的獨立性和屬性對分類影響的一致性，這種限制在一定程度上降低了計算難度，但也影響了它的分類效果。

2 屬性相關(guān)性度量方法

2.1 基于x2統(tǒng)計的屬性相關(guān)性度量[12,13]

設(shè)屬性A的值為ai(i=1,2,…,m)，屬性B的值為bj(j=1,2,…,n)，屬性A、B的頻度計算如表1所示。

表1 屬性的頻度計算

x2統(tǒng)計的計算公式是：

(3)

公式中fij表示ai、bj同時出現(xiàn)的頻度，Ai表示ai出現(xiàn)的頻度，Bj表示bj出現(xiàn)的頻度，f是數(shù)據(jù)集的樣本數(shù)。屬性相關(guān)性度量的公式為：

(4)

ψ是屬性相關(guān)性的度量值，ψ的絕對值表示屬性間的相關(guān)程度，該方法亦可作為屬性與類別之間相關(guān)性的計算方法，用于表示屬性對分類的影響程度。

2.2 屬性分組算法

設(shè)變量集U={X1,X2,…Xn,C}，屬性集X={X1,X2,……Xn}，目標屬性分組π={π1,π2,…,πk}。首先，運用公式(3)和(4)，依次計算出每個屬性與其它屬性的ψ值；其次，計算每個屬性ψ值的平均值，按照平均值的大小進行降序排列，屬性分組中平均值最大的屬性與其它屬性相關(guān)性最強，可以作為每個屬性分組的關(guān)鍵屬性。算法流程描述如下：

(1)計算屬性集中每個屬性之間的屬性相關(guān)性度量ψ(Xi,Xj)；

(2)計算每個屬性與其它屬性相關(guān)性度量值的平均值Eψ(Xi)；

(3)根據(jù)平均值Eψ(Xi)，將所有屬性降序排列DescendSorted(Eψ(Xi))；

(4)將Eψ(Xi)最大值的屬性作為第一個分組的關(guān)鍵屬性，在所有ψ(Xi,Xj)中選擇與Xi相關(guān)性最大的屬性作為第一個屬性分組中的屬性，得到第一個屬性分組π1；

(5)在剩余屬性中選擇平均值最大的Eψ(Xj)作為第二個分組的關(guān)鍵屬性，在剩余屬性所有ψ(Xi,Xj)中選擇與Xj相關(guān)性最大的屬性作為第二個屬性分組中的屬性，得到第二個屬性分組π2；

(6)依次得到所有的屬性分組πk。

3 基于屬性分組的擴展樸素貝葉斯分類器KDANBC

3.1 基于屬性分組的貝葉斯分類器的公式[10]

用πi作為變量集合X的一個屬性分組劃分，在分類時假設(shè)各個屬性分組之間相互條件獨立，組內(nèi)各屬性相互依賴，通過合理選取屬性分組來達到改進分類器的目的，基于屬性分組的貝葉斯分類器可以用公式表示為：

(5)

由上述模型可得出KDANBC模型如下：

(6)

通過上式，分母的值對于選定的數(shù)據(jù)集是一個定值，通常作為一個常數(shù)對待。因此，可以用下式來表示KDANBC的分類模型

(7)

πi表示屬性集X的一個子集，對原數(shù)據(jù)集合X分組的合理性，將直接影響到分類的準確率，因此πi的合理選取與組合是分類器改進的關(guān)鍵。

3.2 基于屬性分組的擴展樸素貝葉斯分類器KDANBC

樸素貝葉斯分類器改進方法可以通過在相關(guān)屬性之間添加有向邊的方式擴展樸素貝葉斯的結(jié)構(gòu)，表達屬性間的相關(guān)性?；趯傩苑纸M的擴展樸素貝葉斯分類器就是在每個屬性分組中找到與其相關(guān)的屬性，并限定屬性分組內(nèi)一個屬性只擁有一個非類父結(jié)點，以簡化擴展樸素貝葉斯的結(jié)構(gòu)。算法流程描述如下：

(1)在第一個屬性分組中選擇絕對值最大ψ(π1i,π1j)；

(2)計算ψ(π1i,C)和ψ(π1j,C)，若ψ(π1i,C)>ψ(π1j,C),則π1i是π1j的非類父結(jié)點；若ψ(π1i,C)<ψ(π1j,C)，則π1j是π1i的非類父結(jié)點;

(3)在第一個屬性分組剩余屬性中選擇絕對值最大ψ,按照步驟(2)依次為每個屬性選擇非類父結(jié)點：

(4)在第二個屬性分組中，執(zhí)行步驟(1)、步驟(2)、步驟(3)，為每個屬性選擇非類父結(jié)點；

(5)依次執(zhí)行直到所有屬性分組的每個屬性都找到所對應的非類父結(jié)點；

(6)在各個屬性分組中，在每對非類父節(jié)點和子節(jié)點之間添加一條有向邊。

4 實驗結(jié)果及分析

本文6個實驗數(shù)據(jù)集均選自UCI數(shù)據(jù)集，數(shù)據(jù)集的基本情況如表2所示。首先，運用Weka[14]中的NBC和TAN算法測試每個數(shù)據(jù)集的分類正確率。其次，運用EDANBC算法進行測試，實驗采取隨機抽樣，70%作為訓練集，30%作為測試集，實驗10次計算分類平均正確率，NBC、TAN和EDANBC分類正確率對比如表2所示。

表2 分類正確率對比表

本文采用分類正確率作為樸素貝葉斯分類性能的評價標準。如圖1所示，與NBC對比，EDANBC的分類正確率在在每個數(shù)據(jù)集上均有一定程度的提高，分類性能明顯改善；與TAN對比，EDANBC的分類正確率在4個數(shù)據(jù)集上比TAN的分類正確率高，在其他2個數(shù)據(jù)集Car Evaluation和Postoperative-patient上TAN的分類正確率要高一些。在實驗的過程中發(fā)現(xiàn)，屬性分組個數(shù)K的合理選取是分類器改進的關(guān)鍵，如果K的值過大，屬性分組數(shù)過多，分類結(jié)構(gòu)過于松散。一般情況下，如果屬性變量個數(shù)不多于8個時，屬性分2組是比較合理的選擇。

圖1 分類正確率對比圖

5 結(jié) 語

放松屬性獨立性假設(shè)和表達屬性之間的相關(guān)性是提高樸素貝葉斯分類性能的主要方法之一，但構(gòu)建樸素貝葉斯分類器計算的復雜度會隨之增加。本文給出了基于x2統(tǒng)計的屬性相關(guān)性度量及屬性分組的方法，各個屬性分組之間相互獨立，組內(nèi)各屬性相互依賴。在每個屬性分組中，在非類的父節(jié)點和子節(jié)點之間添加一條有向邊來表示屬性間的相關(guān)性，將樸素貝葉斯分類器的擴展限定在每個屬性分組內(nèi)，可以有效地簡化擴展樸素貝葉斯分類器的結(jié)構(gòu)，提高了分類的準確性。屬性分組個數(shù)的合理選擇與各個分組間的獨立性的判定方法是分類器改進的關(guān)鍵，也是今后進一步關(guān)注和研究的方向。