基于屬性分組的擴(kuò)展樸素貝葉斯分類(lèi)器

王 峻

(淮南師范學(xué)院 計(jì)算機(jī)學(xué)院, 安徽 淮南 232001)

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

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

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

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

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

(1)

其中：P(H)是先驗(yàn)概率，P(X|H)是條件概率，P(H|X)是進(jìn)行分類(lèi)預(yù)測(cè)的后驗(yàn)概率。

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

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

(2)

其中：P(cj)是類(lèi)cj的先驗(yàn)概率，P(cj|a1,a2,……,an)是后驗(yàn)概率。

樸素貝葉斯分類(lèi)基于最大后驗(yàn)規(guī)則，測(cè)試集中的實(shí)例xi將被分配給后驗(yàn)概率值最大的那個(gè)類(lèi)。

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

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

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

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

表1 屬性的頻度計(jì)算

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

(3)

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

(4)

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

2.2 屬性分組算法

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

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

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

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

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

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

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

3 基于屬性分組的擴(kuò)展樸素貝葉斯分類(lèi)器KDANBC

3.1 基于屬性分組的貝葉斯分類(lèi)器的公式[10]

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

(5)

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

(6)

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

(7)

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

3.2 基于屬性分組的擴(kuò)展樸素貝葉斯分類(lèi)器KDANBC

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

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

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

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

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

(5)依次執(zhí)行直到所有屬性分組的每個(gè)屬性都找到所對(duì)應(yīng)的非類(lèi)父結(jié)點(diǎn)；

(6)在各個(gè)屬性分組中，在每對(duì)非類(lèi)父節(jié)點(diǎn)和子節(jié)點(diǎn)之間添加一條有向邊。

4 實(shí)驗(yàn)結(jié)果及分析

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

表2 分類(lèi)正確率對(duì)比表

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

圖1 分類(lèi)正確率對(duì)比圖

5 結(jié) 語(yǔ)

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