幾種改進(jìn)的樸素貝葉斯分類器模型

四川九洲電器集團(tuán)有限責(zé)任公司 高曉利 王 維 趙火軍

介紹了樸素貝葉斯分類器模型，分析歸納了幾種基于較寬松屬性間關(guān)系的改進(jìn)算法，包含TANF算法、HCS及SP算法；同時(shí)在研究Adaboost集成技術(shù)的基礎(chǔ)上，詳細(xì)介紹了基于集成技術(shù)的改進(jìn)樸素貝葉斯模型，該技術(shù)能夠提高樸素貝葉斯分類器的分類 性能。

0 引言

在數(shù)據(jù)挖掘領(lǐng)域，分類是一個(gè)重要的研究方向，其關(guān)鍵問題是：構(gòu)造一個(gè)分類器，也就是一種分類算法或者說(shuō)構(gòu)建一個(gè)分類模型，然后給屬性集描述的實(shí)例指定最合適的標(biāo)簽。

在眾多分類方法的建模過程中，樸素貝葉斯分類器（Na?ve Bayesian Classifier）由于資源利用率高，計(jì)算精確度高，具有堅(jiān)實(shí)的數(shù)學(xué)理論基礎(chǔ)，從而得到了廣泛的應(yīng)用。樸素貝葉斯分類器是基于一個(gè)假定：在給定特征值條件下，屬性值之間相互條件獨(dú)立，但在工程應(yīng)用中，屬性值之間相互關(guān)聯(lián)，要想在工程中應(yīng)用，必須改進(jìn)樸素貝葉斯分類器，使之在假定條件不滿足的情況下，依然具有較高的工程應(yīng)用價(jià)值，就成為貝葉斯分類器的一個(gè)重要研究方向。

文章分析歸納了現(xiàn)在流行的幾種改進(jìn)樸素貝葉斯分類器模型，大體上可以分為以下兩類：一是研究屬性值的非條件獨(dú)立，即具有較寬松條件限制的分類器；二是研究提高整體性能的集成方法，即使用分類器集成技術(shù)，將不同的分類器有機(jī)組合成一個(gè)新的分類器，從而改善整體性能。本文的結(jié)構(gòu)安排如下：首先介紹樸素貝葉斯分類模型，其次分析歸納幾種基于屬性間關(guān)系的改進(jìn)算法，然后介紹一種非常流行的Adaboost集成技術(shù)，通過該技術(shù)提高樸素貝葉斯分類器的工程應(yīng)用價(jià)值，并且為這種分類器以后發(fā)展提出自己的看法。

1 樸素貝葉斯分類模型

樸素貝葉斯分類器原理是一種統(tǒng)計(jì)學(xué)方法。貝葉斯定理是分類器建模的理論基礎(chǔ)，它利用條件概率原理，利用先驗(yàn)信息和樣本數(shù)據(jù)信息確定事件的發(fā)生的概率。另外，樸素貝葉斯模型是一種生成模型，采用直接對(duì)聯(lián)合概率建模，以獲得目標(biāo)概率的方法。

其中α是正則化因子。依據(jù)概率的鏈準(zhǔn)則，式(（1）可以表示為：

現(xiàn)假定只有兩類，標(biāo)記為0和1；α1到αk表示測(cè)試集屬性；記則有：

其中z為常數(shù)，將（3）式和（4）式兩邊取對(duì)數(shù)后相減得：

（6）式兩邊取指數(shù)，則有：

假定屬性Aj具有種可能的屬性值，那么當(dāng)：

這里I是一個(gè)指標(biāo)函數(shù)，且滿足sigmoid函數(shù)，即：

（1）如果φ為真，那么I(φ) = 1；

（2）如果φ為假，那么I(φ) = 0。

實(shí)際上，（8）式描述的是一個(gè)具有sigmoid型的感知器激活函數(shù)，因此，樸素貝葉斯分類器在特定輸入場(chǎng)合上的表現(xiàn)能力等價(jià)于感知器。

2 基于屬性間關(guān)系的改進(jìn)算法

樸素貝葉斯網(wǎng)絡(luò)要求的條件獨(dú)立的假設(shè)在現(xiàn)實(shí)世界很難滿足，在工程上，為了提高貝葉斯分類器的性能，降低條件之間的聯(lián)系。國(guó)內(nèi)外機(jī)器學(xué)習(xí)的工作者先后提出了不同的方法，其中樹擴(kuò)展的樸素貝葉斯（Tree Augmented Na?ve Bayes,簡(jiǎn)稱TAN）是一類高效的、主流的方法。其基本思想是：以圖論為基礎(chǔ)，把不包括類的屬性組織為樹，每個(gè)節(jié)點(diǎn)不但擁有類屬性作為父節(jié)點(diǎn)，而且最多擁有一個(gè)其他屬性作為父節(jié)點(diǎn)，而類作為根節(jié)點(diǎn)，沒有父節(jié)點(diǎn)。目前實(shí)現(xiàn)TAN的常用方法有：由Friedman和Goldszmidt提出的TANF算法；由Keogh和Pazzani提出的HCS及SP算法，分別給予簡(jiǎn)單介紹。

2.1 TANF

Friedman和Goldszmidt結(jié)合貝葉斯網(wǎng)絡(luò)的相關(guān)性和樸素貝葉斯分類器的特點(diǎn)，并且兩者進(jìn)行有機(jī)整合，提出了TANF方法。該方法是在1968年提出的Chow-Liu方法為基礎(chǔ)上，將該方法將兩個(gè)屬性的條件信息用條件互信息代替。

TANF算法基本思路是：一、計(jì)算兩個(gè)屬性節(jié)點(diǎn)的條件互信息，在上訓(xùn)練模型；二、在類節(jié)點(diǎn)與每一屬性節(jié)點(diǎn)之間加一條邊。

具體構(gòu)造TANF過程如下：

Step3：根據(jù)圖論中的Dijkstra算法，構(gòu)造最大權(quán)值生成樹；

Step4：選擇合適的根變量，并假定所有的方向是以根變量為向外發(fā)出的方向；

Step5：完善以C為標(biāo)識(shí)的頂點(diǎn)和從C到Xi的弧，從而得到TANF模型。

2.2 HCS

Keogh和Pazzani在2001年提出了爬山搜索算法（HCS）實(shí)現(xiàn)TAN分類器構(gòu)造。每個(gè)節(jié)點(diǎn)最多有一個(gè)非類節(jié)點(diǎn)為父節(jié)點(diǎn)，因此最多增加N-1條（N是節(jié)點(diǎn)個(gè)數(shù)）相關(guān)聯(lián)的弧，最少增加0條?。礃闼刎惾~斯分類器）。HCS算法基本步驟：

Step1：初始化。將網(wǎng)絡(luò)初始化為一個(gè)樸素貝葉斯網(wǎng)絡(luò)；

Step2：評(píng)估當(dāng)前的分類器；

Step3：完善當(dāng)前分類器中合法的弧；

Step4：如果存在一條弧，使得分類器性能提高，則將該弧加入當(dāng)前分類器中，轉(zhuǎn)至step2，否則返回。

以樸素貝葉斯分類器初始化網(wǎng)絡(luò)，孤立點(diǎn)集O初始化為所有屬性點(diǎn)集X1,…, Xn，利用交叉驗(yàn)證評(píng)價(jià)從Xi到Xj的每條弧，如果不存在能夠提高分類器性能的弧，則表明當(dāng)前分類器是最優(yōu)的；否則，表明存在能夠提高分類器性能的弧，保留這條弧，并提出這條弧所指向的那個(gè)節(jié)點(diǎn)。當(dāng)O中包含當(dāng)且僅當(dāng)只有一個(gè)節(jié)點(diǎn)時(shí)，循環(huán)終止。

2.3 SP

SP算法是Keogh和Pazzani提出的另一種樹擴(kuò)展樸素貝葉斯分類器。同爬山搜索算法類似，SP也是通過剔除孤立點(diǎn)集中的頂點(diǎn)，尋找最優(yōu)弧來(lái)提高分類器的精度。把這個(gè)過程分為兩個(gè)步：第一步，尋找一個(gè)最優(yōu)的超父節(jié)點(diǎn)；第二步，尋找最優(yōu)子節(jié)點(diǎn)，找到這個(gè)子節(jié)點(diǎn)要與超父節(jié)點(diǎn)相對(duì)應(yīng)。

在給定擴(kuò)展貝葉斯網(wǎng)絡(luò)模型中，如果從節(jié)點(diǎn)Xsp到每個(gè)孤點(diǎn)擴(kuò)展了孤，則該節(jié)點(diǎn)Xsp稱為超父節(jié)點(diǎn)。

如果依次從該節(jié)點(diǎn)Xsp擴(kuò)展弧到每個(gè)子節(jié)點(diǎn)，并且計(jì)算該子節(jié)點(diǎn)在預(yù)測(cè)精確上的影響，由最佳弧指向的節(jié)點(diǎn)被稱為該超父節(jié)點(diǎn)Xsp的最優(yōu)子節(jié)點(diǎn)。

SP算法基本步驟：

Step1：以樸素貝葉斯模型初始化網(wǎng)絡(luò)；

Step2：評(píng)估當(dāng)前的分類器；

Step3：超父節(jié)點(diǎn)Xsp是各個(gè)節(jié)點(diǎn)中能夠提升準(zhǔn)確度最大的那個(gè)節(jié)點(diǎn)；

Step4：計(jì)算從Xsp到每個(gè)孤立點(diǎn)的弧，如果提高了準(zhǔn)確度，則保留它，繼續(xù)step3；否則，返回當(dāng)前分類器。

首先以樸素貝葉斯模型初始化網(wǎng)絡(luò)，孤立點(diǎn)列表O完全初始化為節(jié)點(diǎn)X1,…, Xn。其次，找出超父節(jié)點(diǎn)Xsp。接著尋找Xsp的最優(yōu)子節(jié)點(diǎn)。如果增加從Xsp到最優(yōu)子節(jié)點(diǎn)的弧后，提高了分類器的精度，則剔除最優(yōu)子節(jié)點(diǎn)，只是把此弧加入當(dāng)前分類器中，再次進(jìn)入SP循環(huán)。如果分類準(zhǔn)確度沒有提高或者，則返回當(dāng)前分類器。

3 使用集成技術(shù)的分類器

分類器集成學(xué)習(xí)，也就是把不同的分類器進(jìn)行組合，形成的最終的分類器。所謂集成也就是將多個(gè)不同的弱學(xué)習(xí)算法，通過一定的方法和手段，利用相關(guān)的技術(shù)，最終形成一個(gè)組合的強(qiáng)學(xué)習(xí)算法?，F(xiàn)在流行的集成方法很多，其中Boosting和Bagging是主流的集成技術(shù)，下面我們主要討論Boosting技術(shù)中的Adaboost算法是如何提高模型的分類精確度的。Adaboost算法的核心內(nèi)容是：

輸入：有N個(gè)訓(xùn)練例：

N個(gè)例子上的分布D：ωi為每個(gè)訓(xùn)練實(shí)例的權(quán)重，T為次數(shù)，N為總的次數(shù)。

初始化：ωi初始化為

Do for t =1,2,…, T do

（1）給定權(quán)值ωi（t）得到一個(gè)假設(shè)：

（2）求H（t）的誤差為：

（4）正規(guī)化ωi（t+1）使其綜合為1.0

End Do

輸出：

在這里，假設(shè)每一個(gè)分類器都是實(shí)際有用的，ε（t）＜0.5，即在每次分類的結(jié)果中，正確分類的結(jié)果始終大于錯(cuò)誤分類的結(jié)果，那么可以得到β（t）＜1，當(dāng)增加時(shí)，ωi（t+1）增加，因此顯然算法滿足增強(qiáng)的思想。

（1）利用Adaboost增強(qiáng)樸素貝葉斯時(shí)，h(t)采用公式（10）計(jì)算得出；

（2）算法的輸出是指：當(dāng)給定一個(gè)新的x，通過算法的第5步，就可以利用以前的每次增強(qiáng)學(xué)習(xí)效果，通過投票輸出最終的假設(shè)結(jié)果；

（4）算法最終的聯(lián)合假設(shè)H可以給定為：

那么：

4 結(jié)束語(yǔ)

本文詳細(xì)分析了幾種改進(jìn)或增強(qiáng)樸素貝葉斯分類算法，這幾種方法是從屬性間關(guān)系或分類器整體技術(shù)出發(fā)。目前，又有許多基于這兩方面的改進(jìn)策略。如Wang和Webb等提出了一種準(zhǔn)懶惰式的限制性貝葉斯網(wǎng)絡(luò)分類器的條件概率調(diào)整方法，在某些情況下可以減小誤差分類器。另外，在分類器整體技術(shù)方面，F(xiàn)an H, Ramamobamaro將顯示模式技術(shù)應(yīng)用到分類器的構(gòu)造中，在數(shù)據(jù)集合中部分屬性值表現(xiàn)的比較活躍，這些屬性值組合成的序列被稱為顯現(xiàn)模型。