樣本-屬性加權的樸素貝葉斯改進算法

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

分類是通過分析訓練數據樣本，生成分類函數或模型，通過模型將數據庫中的數據映射到某一類別中，產生數據關于類別的精確描述。

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

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

1 樸素貝葉斯算法描述

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

對一個未知數據樣本x=[x1，x2，…，xk]，由貝葉斯定理得：

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

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

2 改進策略及算法描述

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

2.1 屬性權計算

訓練數據集由條件屬性和決策屬性來描述[5]，對不同的條件屬性進行加權，通過計算條件屬性和決策屬性間的相關系數表示兩者間的相關度，得到屬性權WA。

假設X=(X1，X2，…，Xk)表示k個條件屬性，Y表示決策屬性。計算Xi和Y的相關系數如下：

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

2.2 樣本熵權計算

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

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

2.3 樣本-屬性加權的樸素貝葉斯算法描述

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

(1)對原始數據集X中的屬性，由 2.1節計算出屬性權 WA；

(2)對原始數據集X中的每個樣本，由2.2節計算出樣本熵權，記為WS；

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

(4)對修正后的數據集X′，使用式(6)的加權樸素貝葉斯分類模型進行分類，得到分類結果：

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

3 實驗結果與分析

實驗數據采用UCI機器學習數據庫中的16個數據集，在Matlab開發環境中完成調試，對各個數據集分別使用樸素貝葉斯算法和樣本-屬性加權的樸素貝葉斯算法采用十折交叉驗證方式比較其分類性能。

表1列出了實驗所使用的各個數據集名、樣本數、屬性數和兩種算法分類的準確率。

表1 數據集信息及兩種算法比較

由上表可知，改進算法在實驗中所使用的12個數據集分類準確率與樸素貝葉斯算法相比均有不同程度的提高；且在兩個數據集上準確率相同；另外，有兩個數據集的準確率低于樸素貝葉斯算法?？傮w上看，樣本-屬性加權的樸素貝葉斯算法與樸素貝葉斯算法相比具有更好的分類性能。

本文對樸素貝葉斯算法進行改進，給出了樣本-屬性加權的樸素貝葉斯算法，在UCI數據集上進行實驗，驗證了改進算法相比于原算法具有更好的分類性能。

[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]潘志方.基于樸素貝葉斯學習的電子商務網站客戶興趣分類的應用研究[J].計算機科學，2007，34(6)：214-215，222.

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

[4]張麗偉，段禪倫，熊志偉，等.樸素貝葉斯方法在中醫證候分類識別中的應用研究[J].內蒙古大學學報，2007，38(5)：568-571.

[5]宮秀軍，劉少輝，史忠植.一種增量貝葉斯分類模型[J].計算機學報，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.