基于樸素Bayes組合的簡易集成分類器①

宋叢威

(浙江工業(yè)大學(xué) 之江學(xué)院 理學(xué)院,紹興 312030)

樸素Bayes 分類器是一種簡單易用的分類器,在文本分類方面表現(xiàn)出色[1–4].垃圾郵件過濾是它最為成功的商業(yè)應(yīng)用[5].到現(xiàn)在一直有人嘗試把它應(yīng)用于各種領(lǐng)域[6–9].

樸素Bayes 分類器建立在條件獨立假設(shè)的基礎(chǔ)上:

其中,一個只和x有關(guān)的系數(shù)被省略了.而這個假設(shè)比較強,通常無法被滿足;計算出的后驗概率和實際值也相差較大.不過,樸素Bayes 分類器卻不會因此而受太大影響[10].實際上,樸素Bayes 分類器是一種可加模型[1],即有下述分解:

歷史上人們提出了不少改進(jìn)方案了[3,8].本文提出的改進(jìn)方法解決了樸素Bayes 分類器的兩個問題.

(1)通常樸素Bayes 分類器要么解決連續(xù)型的分類問題,要么解決離散型的分類問題,總之p(xi|c)的分布類型是同一的[11].而本文的方法不受此限制.

(2)在很多方面神經(jīng)網(wǎng)絡(luò)等機器學(xué)習(xí)算法和Bayes分類器是互補的.本文方法可以以非常簡單的方式將兩者結(jié)合起來.

1 樸素Bayes 組合分類器

本節(jié)主要推導(dǎo)樸素Bayes 組合公式,并簡述分類器的構(gòu)造.

1.1 樸素Bayes 組合公式

設(shè)x=(x1,x2,···,xm),即輸入變量被分解成m部分,在條件獨立假設(shè)的基礎(chǔ)上,通過簡單變形可得:

在算法設(shè)計上,下面的等價公式會比較好用:

作為分量,xi不必是1維的;p(c|xi)都是獨立計算的,互不干擾,而且也不是每一個都必須用Bayes 估計.如果第i項是用分類器fi進(jìn)行估計的,那么:

其中,fi,c表示fi在c上的分量,代表lnp(c|xi)的估計.這就是說,只要用不同部分的數(shù)據(jù)獨立訓(xùn)練多個訓(xùn)練分類器,然后簡單求和就可以得到一個不錯的分類器.這些分類器被稱為基分類器(相當(dāng)于線性代數(shù)中的基向量).這是一種特殊的可加模型,也可以看成一種簡單的集成機器學(xué)習(xí),即把fi(xi)看成是fi(Pix),其中Pi是x到xi的投影.我們把式(5)叫做樸素Bayes 組合公式,對應(yīng)的分類器為樸素Bayes 組合分類器.

本文的方法最初是為了改進(jìn)樸素Bayes 分類器而提出的,允許任意組合不同的樸素Bayes 分類器,如當(dāng)面對包含連續(xù)變量和連續(xù)變量的機器學(xué)習(xí)問題時,可以組合基于Gauss 分布和基于多項式的樸素Bayes 分類器.但式(4)確實不是非要用樸素Bayes 分類器計算p(c|xi)不可,而且實驗也支持用其他分類器能大大提高精確度.此時,嚴(yán)格地說它不再是樸素Bayes 分類器.

1.2 分類器的推廣

作為加性模型的特殊形式,式(5)的一種簡單推廣是增加系數(shù)如下:

這些系數(shù)可以通過遺傳算法獲得,而初始種群可根據(jù)式(5)合理設(shè)置.這個推廣將在以后的研究中實現(xiàn).

本文的分類器還可以對缺失型數(shù)據(jù)進(jìn)行分類,比如,只知道x=(x1,x2,···,xl),則只需計算:

即只用其中l(wèi)個基分類器.

輸入變量的每個分量的分布通常是很不相同的,如果單純采用單一分布下的樸素Bayes 分類器,效果會很差.本文的分類器允許人們根據(jù)每個變量的分布情況設(shè)計更有效的樸素Bayes 分類器,從而提高分類精度.

2 算法設(shè)計與實現(xiàn)

2.1 算法

算法基于式 (5),輸入變量X會被分解成m部分,第i部分作為第i個基分類器的輸入;這些分類器的輸出則是共同的.根據(jù)分割后的樣本,分類器被獨立訓(xùn)練.具體的流程如算法1.

算法1.樸素Bayes 組合分類算法(準(zhǔn)備數(shù)據(jù)集 )X,Y(1)選擇一組基分類器,構(gòu)造樸素Bayes 組合分類器;(X1,X2,···,Xm)(2)將輸入數(shù)據(jù)X 分割為;(Xi,Y)(3)第i 個基分類器擬合;xp(c|x)(4)利用樸素Bayes 組合式(5),對任意輸入 計算概率值;(5)根據(jù)概率值給出預(yù)測值.

其中第(3)步根據(jù)屬性的數(shù)據(jù)類型進(jìn)行分割,基本原則是分離離散與連續(xù)變量;第(4)步可以并行計算,獲得較快的速度.

算法1 中離散型和連續(xù)型的分別通常是相對的.一般多數(shù)觀測值的頻率都比較小時,該變量就應(yīng)被看作連續(xù)變量.

2.2 實現(xiàn)

本文采用Python 實現(xiàn),主要依賴scikit-learn 機器學(xué)習(xí)庫[12].本文算法基于和樸素Bayes 分類器一樣的公式,因此它的實現(xiàn)只需繼承scikit-learn 提供的實現(xiàn)樸素Bayes 算法的抽象類即可.

程序運行環(huán)境為MacOS10.15,Python3.7,scikit-learn 0.23.1.源代碼、數(shù)據(jù)和實驗結(jié)果已上傳至GitHub (https://github.com/Freakwill/nb-ensemble).

3 實驗分析

實驗數(shù)據(jù)來自CCF 人工智能競賽平臺https://www.datafountain.cn/competitions/337.為了使它成為一個分類問題,根據(jù)數(shù)值大小已經(jīng)把輸出變量分為3 個等級,即分3 類.總共50000 條數(shù)據(jù),抽出30%作為測試數(shù)據(jù).

根據(jù)數(shù)據(jù),輸入變量被大致分為3 個部分:0-1 型,整數(shù)型,實數(shù)型.關(guān)鍵的原則依然是看數(shù)據(jù)的頻數(shù).選取適合的基分類器.集成的分類器將和這些基分類器(單獨使用)進(jìn)行比較.

所有模型都會被重復(fù)運行10 遍,計算兩項指標(biāo)(精確度與耗時)的均值;每次運行可能有微小的偏差.每種模型確實可以設(shè)置各項參數(shù)調(diào)整性能,但并不顯著.除了神經(jīng)網(wǎng)絡(luò)設(shè)置了2000 次迭代,其隱層大小為8(樸素Bayes 組合中為5),其他都采用默認(rèn)值.

實驗結(jié)果(見表1)符合預(yù)期.無論耗時還是精確度,樸素Bayes 組合分類器都是介于樸素Bayes 分類器和其他分類器之間.該算法適用于那些允許犧牲一定精確度來節(jié)省時間的分類問題.如果對數(shù)據(jù)的分布做更深入的觀察,設(shè)計更有針對性的基分類器,是可以獲得更好的結(jié)果的.

表1 不同算法比較

4 結(jié)論與展望

本文利用本樸素Bayes 組合公式設(shè)計出一種新的分類器,它是一種非常簡便的集成機器學(xué)習(xí)方法.實驗結(jié)果表明,算法在不要求高精確度的情況下,可以提高算法性能.如果需要在精確度和計算時間之間權(quán)衡,那么可以使用本算法.

如果基分類器都是樸素Bayes 分類器,那么樸素Bayes 組合的結(jié)果當(dāng)然也是樸素Bayes 分類器.這樣就可以輕易組合出能處理混合不同分布類型的數(shù)據(jù)集,如本文中的實驗數(shù)據(jù),存在至少3 種類型的分布.實驗結(jié)果表明這種處理是成功的.因為基分類器并不限于樸素Bayes 分類器,所以對條件獨立性的假設(shè)的依賴也減輕了,從而提高了精確度.實驗還表明基分類器采用決策樹、神經(jīng)網(wǎng)絡(luò)等分類器能獲得更好的結(jié)果.

由于,本分類器以依然保留了不完全的條件獨立假設(shè),因此精確度的提升也是有限的,不能和某些成熟的算法競爭.但是,它的設(shè)計靈活簡單,并具有并行性,和那些“成熟算法”相比,適當(dāng)?shù)脑O(shè)置可以大大縮減計算時間,而不會顯著降低精確度.因此,這個算法適合那些對計算時間有較高要求的領(lǐng)域.

未來的研究主要沿著兩個方向發(fā)展:設(shè)計更好的基分類器,如為那些含0 較多的數(shù)據(jù)選擇更合理的分布進(jìn)而設(shè)計相應(yīng)的樸素Bayes 分類器;優(yōu)化樸素Bayes組合公式突破現(xiàn)有的性能瓶頸.