樣本-屬性加權(quán)的樸素貝葉斯改進(jìn)算法

曾文賦(福建省福州第一中學(xué)，福建 福州350001)

分類是通過分析訓(xùn)練數(shù)據(jù)樣本，生成分類函數(shù)或模型，通過模型將數(shù)據(jù)庫中的數(shù)據(jù)映射到某一類別中，產(chǎn)生數(shù)據(jù)關(guān)于類別的精確描述。

樸素貝葉斯算法作為一種最簡(jiǎn)單、有效且在實(shí)際使用中很成功的分類算法，其性能可與神經(jīng)網(wǎng)絡(luò)、決策樹相媲美[1]。它發(fā)源于古典數(shù)學(xué)理論，具有堅(jiān)實(shí)的理論基礎(chǔ)，與其他方法相比有較小的誤差率，并廣泛應(yīng)用于數(shù)據(jù)挖掘、自然語言處理、醫(yī)療研究等眾多領(lǐng)域。例如，潘志方提出一種可根據(jù)用戶的網(wǎng)頁訪問記錄和網(wǎng)上交易記錄來動(dòng)態(tài)地對(duì)顧客進(jìn)行分類的方法[2]；劉青[3]等通過不斷改變EM算法的收斂初始條件以提高收斂效果，并結(jié)合樸素貝葉斯分類方法對(duì)未標(biāo)記的中文網(wǎng)頁進(jìn)行分類；張麗偉[4]等用遺傳算法對(duì)樸素貝葉斯分類算法進(jìn)行改進(jìn)，使之能夠較好地鑒別診斷病患所屬的癥候，比較分析改進(jìn)前后的識(shí)別效率。

樸素貝葉斯算法主要通過假設(shè)待考查的變量遵循某種概率分布，根據(jù)這些概率和已觀測(cè)到的數(shù)據(jù)進(jìn)行推理，作出最優(yōu)決策。算法基于條件獨(dú)立性假設(shè)，即假定特征向量的各分量間相對(duì)于決策變量相對(duì)獨(dú)立，然而在實(shí)際應(yīng)用中該假設(shè)并不現(xiàn)實(shí)，從而影響其分類性能。

1 樸素貝葉斯算法描述

設(shè)每個(gè)數(shù)據(jù)具有k個(gè)屬性，用向量a=[a1，a2，…，ak]描述, 其中a1，a2，…，ak分別表示樣本在屬性A1，A2，…，Ak上的值。假設(shè)數(shù)據(jù)有m個(gè)類,分別用V1，V2，…，Vm來表示。給定一個(gè)樣本，可得到最可能的目標(biāo)值如下：

對(duì)一個(gè)未知數(shù)據(jù)樣本x=[x1，x2，…，xk]，由貝葉斯定理得：

結(jié)合貝葉斯定理、條件獨(dú)立假設(shè)和P(x)對(duì)所有類均為常數(shù)，可判斷x的類別如下：

綜上，根據(jù)樸素貝葉斯算法，對(duì)于一個(gè)未分類的樣本x，只需分別計(jì)算出P(Vj)和 x屬于類別Vj的先驗(yàn)概率P(x|Vj)，再選出式(3)中概率最大的那個(gè)類即為x的類別。

2 改進(jìn)策略及算法描述

由于樸素貝葉斯算法假設(shè)數(shù)據(jù)遵循某種概率分布，認(rèn)為條件屬性對(duì)決策屬性的重要程度均相同且須滿足條件獨(dú)立性假設(shè)等,這些都會(huì)影響其在實(shí)際應(yīng)用中的分類性能。在實(shí)際應(yīng)用中，不同屬性對(duì)分類影響的效果是不同的，故改進(jìn)算法中考慮對(duì)不同的屬性給予不同的權(quán)值，定義屬性權(quán)刻畫條件屬性對(duì)決策屬性的重要性，以克服條件獨(dú)立性假設(shè)的缺陷，從而擴(kuò)展樸素貝葉斯算法；同時(shí)，通過屬性權(quán)結(jié)合信息熵獲得樣本熵權(quán)，對(duì)原始數(shù)據(jù)樣本進(jìn)行修正，提高算法的泛化能力。

2.1 屬性權(quán)計(jì)算

訓(xùn)練數(shù)據(jù)集由條件屬性和決策屬性來描述[5]，對(duì)不同的條件屬性進(jìn)行加權(quán)，通過計(jì)算條件屬性和決策屬性間的相關(guān)系數(shù)表示兩者間的相關(guān)度，得到屬性權(quán)WA。

假設(shè)X=(X1，X2，…，Xk)表示k個(gè)條件屬性，Y表示決策屬性。計(jì)算Xi和Y的相關(guān)系數(shù)如下：

其中 Cov(Xi，Y)為Xi和Y的協(xié)方差，D(Xi)、D(Y)分別為Xi和Y的方差。可知，屬性權(quán)WAi的值越大，表示第i個(gè)條件屬性對(duì)分類的影響越大。

2.2 樣本熵權(quán)計(jì)算

信息熵由香農(nóng)所提出[6]，用來度量不確定的信息量（隨機(jī)性）的大小，故計(jì)算信息熵等價(jià)于確定隨機(jī)變量的分布。假設(shè)一個(gè)數(shù)據(jù)樣本x=(x1，x2，…，xk)，結(jié)合信息熵和2.1節(jié)中所定義的屬性權(quán)計(jì)算樣本熵權(quán)如下：

通過結(jié)合屬性權(quán)和信息熵定義樣本熵權(quán)WS(x)，融合屬性信息修正原始數(shù)據(jù)樣本以提高泛化能力。

2.3 樣本-屬性加權(quán)的樸素貝葉斯算法描述

設(shè)數(shù)據(jù)集X中包含n個(gè)數(shù)據(jù)樣本，每個(gè)數(shù)據(jù)樣本具有k個(gè)屬性，第i個(gè)樣本可表示為Xi=(Xi1，Xi2，…，Xik)，i=1，2，…，n。X中含有m個(gè)類，用V1，V2，…，Vm來表示。樣本-屬性加權(quán)的樸素貝葉斯算法步驟描述如下：

(1)對(duì)原始數(shù)據(jù)集X中的屬性，由 2.1節(jié)計(jì)算出屬性權(quán) WA；

(2)對(duì)原始數(shù)據(jù)集X中的每個(gè)樣本，由2.2節(jié)計(jì)算出樣本熵權(quán)，記為WS；

(3)利用步驟(2)中計(jì)算獲得的已融合屬性信息的樣本熵權(quán)WS，對(duì)數(shù)據(jù)集X進(jìn)行加權(quán)，得到修正后的數(shù)據(jù)集X′，使得X′相比于X具有更好的泛化能力；

(4)對(duì)修正后的數(shù)據(jù)集X′，使用式(6)的加權(quán)樸素貝葉斯分類模型進(jìn)行分類，得到分類結(jié)果：

其中P(Vj)和P(xi|Vj)可由修正后數(shù)據(jù)集X′中獲得，加權(quán)樸素貝葉斯分類模型的加權(quán)因子WAi即為步驟(1)中計(jì)算獲得的屬性權(quán)。

3 實(shí)驗(yàn)結(jié)果與分析

實(shí)驗(yàn)數(shù)據(jù)采用UCI機(jī)器學(xué)習(xí)數(shù)據(jù)庫中的16個(gè)數(shù)據(jù)集，在Matlab開發(fā)環(huán)境中完成調(diào)試，對(duì)各個(gè)數(shù)據(jù)集分別使用樸素貝葉斯算法和樣本-屬性加權(quán)的樸素貝葉斯算法采用十折交叉驗(yàn)證方式比較其分類性能。

表1列出了實(shí)驗(yàn)所使用的各個(gè)數(shù)據(jù)集名、樣本數(shù)、屬性數(shù)和兩種算法分類的準(zhǔn)確率。

表1 數(shù)據(jù)集信息及兩種算法比較

由上表可知，改進(jìn)算法在實(shí)驗(yàn)中所使用的12個(gè)數(shù)據(jù)集分類準(zhǔn)確率與樸素貝葉斯算法相比均有不同程度的提高；且在兩個(gè)數(shù)據(jù)集上準(zhǔn)確率相同；另外，有兩個(gè)數(shù)據(jù)集的準(zhǔn)確率低于樸素貝葉斯算法。總體上看，樣本-屬性加權(quán)的樸素貝葉斯算法與樸素貝葉斯算法相比具有更好的分類性能。

本文對(duì)樸素貝葉斯算法進(jìn)行改進(jìn)，給出了樣本-屬性加權(quán)的樸素貝葉斯算法，在UCI數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，驗(yàn)證了改進(jìn)算法相比于原算法具有更好的分類性能。

[1]LANGLEY P，IBA W，THOMPSON K.An analysis of Bayesian classifiers[C].In：Proc of the 10th National Conference on Artificial Intelligence.MenloPark：AAA I Press，1992：223-228.

[2]潘志方.基于樸素貝葉斯學(xué)習(xí)的電子商務(wù)網(wǎng)站客戶興趣分類的應(yīng)用研究[J].計(jì)算機(jī)科學(xué)，2007，34(6)：214-215，222.

[3]劉青，何政.結(jié)合EM算法的樸素貝葉斯方法在中文網(wǎng)頁分類上的應(yīng)用[J].計(jì)算機(jī)工程與科學(xué)，2005，27(7)：65-66，90.

[4]張麗偉，段禪倫，熊志偉，等.樸素貝葉斯方法在中醫(yī)證候分類識(shí)別中的應(yīng)用研究[J].內(nèi)蒙古大學(xué)學(xué)報(bào)，2007，38(5)：568-571.

[5]宮秀軍，劉少輝，史忠植.一種增量貝葉斯分類模型[J].計(jì)算機(jī)學(xué)報(bào)，2002，25(6)：645-650.

[6]Zhang Jiguo，Zhu Yongzhong.Information entropy measures for fuzziness[J].Journal of Hohai University Changzhou，2001，15(4)：16-21.