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

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

0 引言

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

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

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

1 樸素貝葉斯分類模型

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

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

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

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

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

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

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

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

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

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

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

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

2.1 TANF

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

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

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

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

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

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

2.2 HCS

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

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

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

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

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

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

2.3 SP

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

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

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

SP算法基本步驟：

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

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

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

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

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

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

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

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

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

初始化：ωi初始化為

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

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

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

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

End Do

輸出：

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

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

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

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

那么：

4 結(jié)束語

本文詳細(xì)分析了幾種改進或增強樸素貝葉斯分類算法，這幾種方法是從屬性間關(guān)系或分類器整體技術(shù)出發(fā)。目前，又有許多基于這兩方面的改進策略。如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)模型。