基于屬性加權(quán)的樸素貝葉斯分類算法改進(jìn)

胡勝利+王琦敏

摘要：通過對樸素貝葉斯算法的學(xué)習(xí)和理解，針對削弱樸素貝葉斯屬性條件獨立假設(shè)的問題，該文提出了一種改進(jìn)的加權(quán)算法，該算法通過對增益率加權(quán)和關(guān)聯(lián)度得分加權(quán)的思想來確定新的權(quán)重系數(shù)來提高準(zhǔn)確性。最后，在MATLAB軟件中使用UCI數(shù)據(jù)集對模型進(jìn)行了驗證。實驗結(jié)果表明，相對于傳統(tǒng)的樸素貝葉斯算法，改進(jìn)后的算法提高了分類的準(zhǔn)確率。

關(guān)鍵詞：貝葉斯公式；樸素貝葉斯算法；MATLAB

中圖分類號：TP311 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2017）29-0257-02

貝葉斯算法也叫貝葉斯推理，在18世紀(jì)，英國學(xué)者貝葉斯曾提出計算條件概率的公式用來解決如下問題：在已經(jīng)知道某條件概率情況下，怎樣得到兩個事件交換后的概率，即已知P（A|B）的情況下求P（B|A）。貝葉斯定理的進(jìn)行分類的一個簡單的應(yīng)用就是樸素貝葉斯算法，它的基本思想就是對給出的等待分類的項，求出在此項出現(xiàn)的條件下各項類別出現(xiàn)的概率，在這些概率中找出最大的，就認(rèn)為這個等待分類的項屬于那個概率最大的對應(yīng)的類別。

已知集合：C={y1，y2，y3，.....，yn}和I={x1，x2，x3，......，xn}，通過構(gòu)造相應(yīng)的映射規(guī)則y=f（x），使得I集合中的任意元素xi有且僅有一個在C中的元素yi，使得yi=f（xi）成立。在分類問題中集合C就表示類別集合，I集合就表示數(shù)據(jù)集合，而映射規(guī)則f就是分類器。分類算法就是構(gòu)造相應(yīng)的分類器。分類算法基本上都是通過相關(guān)經(jīng)驗來構(gòu)造相應(yīng)的映射，在一般情況下未能構(gòu)造完全準(zhǔn)確的映射是因為分類算法缺少一定量的數(shù)據(jù)，最后可以通過對我們已經(jīng)知曉的數(shù)據(jù)進(jìn)行分析和整理來求出這一定概率上的分類。文獻(xiàn)[1]提出了根據(jù)屬性的重要性給不同屬性賦不同權(quán)值的加權(quán)樸素貝葉斯（Weighted Naive Bayes，WNB）模型，并通過實驗發(fā)現(xiàn)它們能改進(jìn)樸素貝葉斯的分類效果。文獻(xiàn)[2]則利用數(shù)據(jù)本身導(dǎo)出特征加權(quán)的方法來提高樸素貝葉斯分類器的分類性能。本文則是通過對增益率加權(quán)和關(guān)聯(lián)度得分加權(quán)的思想來確定新的權(quán)重系數(shù)來提高準(zhǔn)確性。

1 樸素貝葉斯分類原理

貝葉斯分類是非規(guī)則分類，首先通過我們已經(jīng)分過類的例子集，訓(xùn)練出所需要的分類器，最后沒有分類的數(shù)據(jù)可以使用分類器進(jìn)行分類，這些分類器算法包含有基于結(jié)構(gòu)的森林?jǐn)U展、平均樹擴展（ATAN）的樸素貝葉斯和基于屬性的條件似然對數(shù)（CLL）樸素貝葉斯等。

貝葉斯分類具備以下幾個特點：

（1） 可以對不確定的預(yù)測做出假設(shè)的特點，確定某一實例從屬的類別，計算得出所求那一類的概率，明確不僅僅是把該實例絕對性的指給某一類，最后所求的實例從屬的類就是擁有具有最大概率的類。

（2） 屬性的類別可以是多樣的，如離散、混合甚至是連續(xù)型的，實例的全部屬性都要加入到聯(lián)合概率計算中，即分類不止一個的屬性決定。

（3） 對實例的預(yù)測也可以由多個假設(shè)加上權(quán)重的概率一起計算出，等等。

貝葉斯定理檢驗假設(shè)h的概率，基于假設(shè)的先驗概率，給定假設(shè)下觀察到不同數(shù)據(jù)的概率以及觀察到數(shù)據(jù)的本身的先驗概率。用P（h）表示假設(shè)h的初始概率。用P（D）表示即將要觀察的數(shù)據(jù)D的先驗概率，P（h|D）代表給定D時假設(shè)h成立的概率，P（D|h）表示假設(shè)成立的條件下D的概率。貝葉斯規(guī)則定義如下所示：

令Dc表示訓(xùn)練集D中第c類樣本組成的集合，如果有充足的獨立同分布樣本，就可以容易的統(tǒng)計出類先驗概率：

假設(shè)有m個類C1，C2，.....，Cm，給定元組X，在條件X下分類法將預(yù)測X屬于具有最高后驗概率的類，樸素貝葉斯預(yù)測X屬于類Ci，當(dāng)且僅當(dāng)：

由貝葉斯定理易知：

由于P（X）對所有類為常數(shù)，所以最大化p（Ci|X）即P（X|Ci）P（Ci）最大即可。而P（Ci）即先驗概率，P（X|Ci）即X樣本屬性的聯(lián)合概率，計算方式如下：

由于（5）式的計算需要假設(shè)樣本的n個屬性相互獨立，而在日常生活環(huán)境下，沒有完全相互獨立的事物存在，即事物之間必定存在著某種普遍的聯(lián)系。因此在這種現(xiàn)實情況下樸素貝葉斯算法會受到一定的影響，為了削弱這種影響本文通過對（5）式中的屬性進(jìn)行加權(quán)，將屬性間的相互獨立要求削弱。即將（5）式修改如下：

現(xiàn)在就是尋找一個方法來計算這個權(quán)重w。

2 加權(quán)樸素貝葉斯計算模型

2.1 模型計算方式

在樸素貝葉斯分類器中，屬性變量與類變量的關(guān)系并不是簡單的是/否關(guān)系，所以屬性加權(quán)方法的提出很大程度上弱化了樸素貝葉斯條件獨立的假設(shè)。屬性加權(quán)可以看作是屬性選擇的一個概括化和一般化。2004年zhang和sheng提出了一種基于增益率的屬性加權(quán)方法，其屬性權(quán)值的計算公式如下：

式中，GR（i）代表屬性變量Ai的增益率，m代表樣本所含屬性個數(shù)。還有一種基于ReliefF的屬性加權(quán)方法，其主要是將屬性的關(guān)聯(lián)度得分結(jié)果作為屬性的權(quán)值，起計算方式如下：

式中，RelevanceScore（Ai）代表基于ReliefF的屬性選擇方法中屬性Ai的關(guān)聯(lián)度得分。為了同時考慮到屬性的增益率加權(quán)系數(shù)和關(guān)聯(lián)度得分加權(quán)系數(shù)，本文定義了一種新的屬性加權(quán)計算方式為：

式中wz表示增益率加權(quán)系數(shù)，ws表示關(guān)聯(lián)度得分加權(quán)系數(shù)。

2.2 算法步驟如下

（1） 計算屬性的增益率加權(quán)系數(shù)和關(guān)聯(lián)度得分加權(quán)系數(shù)。

（2） 根據(jù)前面的計算結(jié)果來計算權(quán)重w。

（3） 通過計算出的權(quán)重系數(shù)來對樣本進(jìn)行樸素貝葉斯分類。

其算法流程圖如圖1：

3 仿真實驗結(jié)果

本文所使用的實驗工具是美國MathWorks公司出品的商業(yè)數(shù)學(xué)軟件MATLAB7.1版。通過從UCI數(shù)據(jù)集[4]中下載相關(guān)數(shù)據(jù)集來驗證提出的加權(quán)樸素貝葉斯算法是否比原來的樸素貝葉斯算法好。表1為實驗數(shù)據(jù)，通過從圖中的實驗數(shù)據(jù)可以看出本文提出的加權(quán)算法比原算法分類效果要好，特別是對于類別數(shù)數(shù)據(jù)集較少的數(shù)據(jù)。

4 結(jié)論

本文針對消若屬性條件獨立的問題，所提出的加權(quán)屬性樸素貝葉斯算法。雖然在算法的分類精確度上有了明顯的提高，但是通過計算屬性增益率權(quán)重和關(guān)聯(lián)度得分權(quán)重來計算新的加權(quán)系數(shù)，從算法的復(fù)雜度角度分析，明顯提高了算法的時間復(fù)雜度。接下來的研究就是怎樣提高算法的時間復(fù)雜度。

參考文獻(xiàn)：

[1] Harry Z，Sheng S L.Learning Weighted Naive Bayes with accurate ranking[C]//Proceedings of the 4th IEEE Interna-tional Conference on Data Mining（ICDM 04），Brighton，UK，2004：567-570.

[2] 程克飛，張聰.基于特征加權(quán)的樸素貝葉斯分類器[J].計算機仿真，2006，23（10）：92-94.

[3] Friedman N，Goldszmidt M. Building classifiers using Bayesian network[A].Proc Nation Conference on Artifi-cial Intelligence[C]. Menlo Park， CA： AAAI Press，1996，27-1284.

[4] Blake C.Keogh E.MerzC.UCI repository of machine learning database[EB/OL].http：//www.ics.uci.edu/mlearn/MLRepository.html.1998.endprint