基于互信息量的加權(quán)樸素貝葉斯算法

馬睿

摘要：樸素貝葉斯算法是一種簡(jiǎn)單而高效的分類算法，但是其分類能力卻受到條件獨(dú)立性的假設(shè)所影響。文章針對(duì)樸素貝葉斯算法的這一弊端，提出以互信息量為加權(quán)的樸素貝葉斯算法。通過計(jì)算條件屬性和決策屬性之間的互信息量，對(duì)不同的條件屬性賦予不同的權(quán)重，從而在保持樸素貝葉斯算法簡(jiǎn)潔的基礎(chǔ)上有效地提高了其分類性能。首先提出了以互信息量為屬性權(quán)值的求解方法，然后論證了相應(yīng)的算法理論，最后對(duì)所提算法進(jìn)行了實(shí)際驗(yàn)證，并得到很好的效果。

關(guān)鍵詞：加權(quán)；樸素貝葉斯算法；互信息量

分類問題一直以來(lái)都是數(shù)據(jù)挖掘和機(jī)器學(xué)習(xí)研究的熱點(diǎn)問題，主要是通過對(duì)樣本數(shù)據(jù)或訓(xùn)練集的分析和學(xué)習(xí)來(lái)構(gòu)造分類器，然后把待分類的樣本映射到對(duì)應(yīng)的類別中。目前已有很多成熟的分類算法，比如決策樹分類算法、貝葉斯分類算法、基于規(guī)則的分類算法和支持向量機(jī)的分類算法等。在眾多分類方法和理論中，樸素貝葉斯（NaiveBayes，NB）由于計(jì)算高效、精確度高，并具有堅(jiān)實(shí)的理論基礎(chǔ)而得到了廣泛應(yīng)用[1]。在文獻(xiàn)[2]中針對(duì)加權(quán)貝葉斯分類模型提出了基于相關(guān)系數(shù)的權(quán)重求解方法。文獻(xiàn)[3]中基于Rough Set的屬性重要性理論，提出了基于Rough Set的加權(quán)樸素貝葉斯分類方法，并分別從代數(shù)觀、信息觀及綜合代數(shù)觀和信息觀的角度給出了屬性權(quán)值的求解方法。文獻(xiàn)[4]中在挖掘出來(lái)的規(guī)則和置信度的基礎(chǔ)上，對(duì)樸素貝葉斯分類算法進(jìn)行改進(jìn)，根據(jù)挖掘出來(lái)的關(guān)聯(lián)規(guī)則和置信度對(duì)條件屬性進(jìn)行加權(quán)。

就分類而言，條件屬性和決策屬性之間的相關(guān)程度越高，條件屬性對(duì)分類的影響會(huì)相應(yīng)變大。針對(duì)這一分類模型本文提出了基于互信息量的樸素貝葉斯權(quán)重求解方法。

1 算法理論

1.1樸素貝葉斯分類

樸素貝葉斯分類是基于貝葉斯定理，即：其中，P（B|A）為條件A下B的后驗(yàn)概率，P（B）為B的先驗(yàn)概率，P（A|B）為條件B下A的后驗(yàn)概率，尸（A）表示爿的先驗(yàn)概率。那么樸素貝葉斯分類思想就是：刑個(gè)樣本S={S1，S2，…，Sn}（訓(xùn)練數(shù)據(jù)集），每個(gè)樣本Si都表示為一個(gè)n維向量{X1，X2，…，Xn。}，xi為Si的特征屬性。還有k個(gè)類C={C1，C2，…，Ck}（，每個(gè)樣本就屬于一個(gè)類別。此外給出一個(gè)待檢測(cè)樣本X（未知類），可以用最高條件概率尸（Ci|X）來(lái)預(yù)測(cè)未知類的類別。即：

對(duì)于所有的類別來(lái)說尸（X）是一個(gè)定數(shù)，最大化先驗(yàn)概率尸（X Ic，/）尸（Q可通過最大化后驗(yàn)概率尸（Ci|X）轉(zhuǎn)化得到。先驗(yàn)概率尸（xi|Ci），P（x2|Ci》…，P（xn|ci）可以從訓(xùn)練數(shù)據(jù)集中獲取。據(jù)此理論就可以求出檢測(cè)驗(yàn)本X的類。

那么樸素貝葉斯分類模型就可以定義為

1.2加權(quán)貝葉斯分類

在實(shí)際操作中很難讓樸素貝葉斯條件獨(dú)立性的這個(gè)假設(shè)成立，可以給不同的屬性賦不同的權(quán)值使樸素貝葉斯得以擴(kuò)展，這就是加權(quán)樸素貝葉斯[5]： 其中，Wi代表屬性xi的權(quán)值，屬性的權(quán)值越大，該屬性對(duì)分類的影響就越大。加權(quán)樸素貝葉斯的關(guān)鍵問題就在于如何確定不同屬性的權(quán)值。

1.3互信息量

互信息表示I（x；y）表示某一事件y所給出的關(guān)于另一事件x的信息[6]。定義事件y口事件x之間的互信息量為： 當(dāng)后驗(yàn)概率p（yIx）等于先驗(yàn)概率p（y）時(shí)，互信息量I（x；y）等于零，表示兩個(gè)事件獨(dú)立：當(dāng)后驗(yàn)概率p（y|x）大于先驗(yàn)概率p（y）時(shí)，互信息量J（5‘；y）大于零，為正值，意味著x的出現(xiàn)有助于減小y出現(xiàn)的不確定性，即一個(gè)出現(xiàn)會(huì)增加另一個(gè)出現(xiàn)的可能性：當(dāng)后驗(yàn)概率p（y|x）小于先驗(yàn)概率p（y）時(shí)，互信息量J（x；y）小于零，意味著x的出現(xiàn)增加了y出現(xiàn)的不確定性，即一個(gè)出現(xiàn)會(huì)減少另一個(gè)出現(xiàn)的可能性。所以利用互信息量作為衡量屬性相關(guān)性分析的指標(biāo)是可行的。

2 基于互信息量的加權(quán)樸素貝葉斯分類

在現(xiàn)實(shí)的世界中，條件屬性之間完全獨(dú)立幾乎是不存在的，屬性之間都存在著或多或少不同程度的聯(lián)系，并且每個(gè)條件屬性和決策屬性之間的相關(guān)程度也是不一樣的，所以要對(duì)每個(gè)條件屬性進(jìn)行加權(quán)[7]。本文通過計(jì)算條件屬性和決策屬性之間的互信息量，對(duì)條件屬性進(jìn)行加權(quán)。即

W=I（X，Y）

基于互信息量的樸素貝葉斯分類模型首先要根據(jù)分類樣本（訓(xùn)練數(shù)據(jù)集），計(jì)算條件屬性的權(quán)值，即計(jì)算條件屬性和決策屬性的互信息量。然后進(jìn)行樸素貝葉斯分類做出預(yù)測(cè)。其基本分類模型如圖1所示。 具體步驟：（1）數(shù)據(jù)預(yù)處理。對(duì)訓(xùn)練數(shù)據(jù)集和待分類數(shù)據(jù)進(jìn)行缺失值補(bǔ)充和離散化。（2）根據(jù)訓(xùn)練數(shù)據(jù)集，根據(jù)每個(gè)條件屬性的屬性值xi和類別值yi，計(jì)算類別值下屬性值出現(xiàn)的概率p（xi|yi）和類別概率P（yi）。由此計(jì)算互信息量/（x；y），并作為條件屬性的權(quán)重系數(shù)。（3）生成加權(quán)樸素貝葉斯權(quán)重系數(shù)表。（4）分類。調(diào)用權(quán)重系數(shù)表，對(duì)樣本數(shù)據(jù)進(jìn)行加權(quán)樸素貝葉斯計(jì)算分類。

3 應(yīng)用舉例

如表1所示，一個(gè)訓(xùn)練數(shù)據(jù)集有條件屬性和決策屬性。條件屬性包括Outlook，Tem （Temperature），Hum（humidity），Windy，決策屬性D（條件屬性代表的天氣情況，決策屬性代表是否外出打網(wǎng)球）。

根據(jù)表1，按照條件屬性和決策屬性的互信息量，求解每一個(gè)條件屬性的權(quán)重系數(shù)。由此可得到一個(gè)權(quán)重系數(shù)表，如表2所示。

假設(shè)待分類檢測(cè)樣本為：X= （Sunny Hot HighStrong），那么通過本文所提的算法可以算得樣本的分類為：No。

4 結(jié)語(yǔ)

在現(xiàn)實(shí)世界中，樸素貝葉斯假設(shè)的先決條件很難得到滿足。基于互信息量的加權(quán)樸素貝葉斯算法，很好地解釋了條件屬性和決策屬性的關(guān)系，為分類做了先決判斷，并能最終得到準(zhǔn)確的分類結(jié)果。

[參考文獻(xiàn)]

[1]HAN J M，KAMBER M.數(shù)據(jù)挖掘：概念與技術(shù)[M].范明，孟小峰，譯北京：機(jī)械工業(yè)出版社，2005.

[2]張明衛(wèi)，王波，張斌，等基于相關(guān)系數(shù)的加權(quán)樸素貝葉斯分類算法[J].東北大學(xué)學(xué)報(bào)，2008 （7）：952-955.

[3]鄧維斌，王國(guó)胤，王燕.基于RoughSet的加權(quán)樸素貝葉斯分類算法[J].計(jì)算機(jī)學(xué)報(bào)：2007（2）：204-206.

[4]張春，郭明亮大數(shù)據(jù)環(huán)境下樸素貝葉斯分類算法的改進(jìn)與實(shí)現(xiàn)J].北京交通大學(xué)學(xué)報(bào)，2015 （4）：35-41

[5]HARRY Z， SHENG S.Learning weighted naive bayes with accurate ranking[C].Brighton： Fourth IEEE International Conference onData Mining，2004

[6]張龍飛基于互信息的樸素貝葉斯改進(jìn)模型研究[D].長(zhǎng)春：吉林大學(xué)，2010

[7]張震，胡學(xué)鋼基于互信息量的分類模型[J].計(jì)算機(jī)應(yīng)用，2011（6）：1678-1680.