基于蝙蝠算法的貝葉斯分類器優化研究

蔣禮青　張明新　鄭金龍　戴　嬌

1(中國礦業大學計算機科學與技術學院　江蘇 徐州 221116)2(常熟理工學院計算機科學與工程學院　江蘇 常熟 215500)

?

基于蝙蝠算法的貝葉斯分類器優化研究

蔣禮青1,2張明新2*鄭金龍2戴嬌1

1(中國礦業大學計算機科學與技術學院江蘇 徐州 221116)2(常熟理工學院計算機科學與工程學院江蘇 常熟 215500)

樸素貝葉斯分類器是一種應用廣泛且簡單有效的分類算法，但其條件獨立性的“樸素貝葉斯假設”與現實存在差異，這種假設限制樸素貝葉斯分類器分類的準確率。為削弱這種假設，利用改進的蝙蝠算法優化樸素貝葉斯分類器。改進的蝙蝠算法引入禁忌搜索機制和隨機擾動算子，避免其陷入局部最優解，加快收斂速度。改進的蝙蝠算法自動搜索每個屬性的權值，通過給每個屬性賦予不同的權值，在計算代價不大幅提高的情況下削弱了類獨立性假設且增強了樸素貝葉斯分類器的準確率。實驗結果表明，該算法與傳統的樸素貝葉斯和文獻[6]的新加權貝葉斯分類算法相比, 其分類效果更加精準。

分類樸素貝葉斯屬性加權蝙蝠算法

0　引　言

樸素貝葉斯分類器NBC(Naive Bayes Classifiers)，訓練簡單，具有很強的健壯性和高效性；通過比較發現，樸素貝葉斯分類法可以與經過挑選的神經網絡及決策樹相媲美[1]，已經成功地應用到分類、聚類及模型選擇等數據挖掘任務之中[2,3]。由于樸素貝葉斯分類器存在條件獨立性假設，使其在預處理數據集時要進行屬性約簡。然而在實際應用中,大多數據集不滿足條件獨立性假設，針對樸素貝葉斯分類器的不足,學者學習研究貝葉斯信念網絡來改進其分類性能,文獻[4]證明，學習訓練數據集并得到一個最優貝葉斯網絡是NP-hard問題。在文獻[5]中，Zhang H提出根據屬性影響力的不同，給相應屬性賦予權值，這種方法模型稱為加權樸素貝葉斯模型；張步良提出基于分類概率加權的樸素貝葉斯分類方法[6]。他們提出的屬性加權方法具有局限性，如張步良的方法是通過對每個屬性做樸素貝葉斯分類，得到正確分類該屬性的概率，把該概率作為權值，而不考慮某個屬性對整體數據分類準確度的影響。針對傳統加權樸素貝葉斯分類器的缺點，本文利用蝙蝠算法進行全局最優屬性權值的搜索，目標是尋找影響整體數據分類精準度最強的權值，從而優化文獻[6]屬性加權方法。

蝙蝠算法BA(Bat Algorithm)，是2010年由Yang X S教授提出的一種新的啟發式群智能算法[7]。已有許多學者對蝙蝠算進行研究，與粒子群算法、遺傳算法及和聲算法等相比，蝙蝠算法有更好的計算精度和計算效率[8,9]。目前，蝙蝠算法已經廣泛應用于自然科學與工程科學領域中[10]。針對原始蝙蝠算法存在尋優不精、收斂慢和早熟的缺點，本文用新的改進方法對其進行改進，稱為改進的蝙蝠算法IBA(Improved Bat Algorithm)。

本文提出利用改進的蝙蝠算法優化樸素貝葉斯分類器NB-IBA的算法，將蝙蝠算法與樸素貝葉斯分類算法結合，采用IBA來自動搜索每個屬性權值，削弱條件獨立性假設，優化樸素貝葉斯分類器。試驗表明，NB-IBA算法確實能提高樸素貝葉斯分類器分類的精準度。

1　加權樸素貝葉斯分類算法

1.1樸素貝葉斯模型[1]

設D是訓練元組與類標號集合。每個元組用一個n維向量表示屬性向量，如X={x1,x2,…,xn}，描述由n個屬性A1,A2,…,An對元組的n個測量。假設類個數為m個，為C1,C2,…,Cm。給定一個X訓練元組，分類器預測屬于類Ci的X，當且僅當：

P(Ci|X)>P(Cj|X)1≤j≤mj≠i

(1)

當p(Ci|X)最大化，稱此時的類Ci為“最大后驗假設”。

類先驗概率可以用p(Ci)=|Ci,D|/|D| 估計，其中|Ci,D|是D中Ci類的訓練元組數。給定元組的類標號，因此：

=P(x1|Ci)P(x2|Ci)…P(xn|Ci)

(2)

可以根據X進行概率p(x1|Ci),p(x2|Ci),…,p(xn|Ci)的估計。考慮屬性值是離散的還是連續的：

第一，如果Ak是離散值，則p(xk|Ci)為屬性Ak中值為xk的且屬于Ci類的元組數除以Ci類的元組數|Ci,D|，Ak,Ci都屬于D。

第二，如果Ak是連續值屬性，假定連續值屬性服從高斯分布，由下式定義：

(3)

因此：

P(xk|Ci)=g(xk,μCi,σCi)

(4)

函數g中第二和第三個參數分別是Ci類訓練元組屬性Ak的均值(即平均值)和標準差。

后驗概率公式為：

(5)

測試樣(E={X1,X2,…,Xn}) 被分在后驗概率最大的類中，因為p(X)為常數，計算則不作考慮，樸素貝葉斯分類器的模型為：

(6)

1.2加權樸素貝葉斯模型

首先在樸素貝葉斯分類器中用屬性加權思想的是Webb等人[11]。本文運用加權算法直接用于每個條件概率p(xk|Ci)上，這樣，可以用更加直接的方式影響分類的整個過程。加權樸素貝葉斯模型為：

(7)

其中，屬性Ak的權值是wk，權值與屬性影響力成正比關系，權值大，對應屬性對分類正確率的影響力就強，反之則弱。

加權樸素貝葉斯的核心問題在于如何進行每個屬性權值的計算。針對該問題，本文提出了一個計算權值的新方法，用改進后的蝙蝠算法進行各個屬性權值的計算。

2　蝙蝠算法的改進及屬性權值的計算

2.1蝙蝠算法

本文用蝙蝠算法優化樸素貝葉斯分類算法，蝙蝠算法是2010年由Yang Xinshe 教授提出[8]。在一個D 維搜索空間中，由n只蝙蝠組成的一個群體在飛行的過程中位置xi、速度vi、響度Ai和脈沖速率ri的初始化是由具體解決的問題確定。

群體數n的選擇應綜合考慮算法的可靠性和計算時間，對通常問題10只蝙蝠已足夠，對于較復雜的問題可取50只。按照本文數據集的復雜性，蝙蝠個數取值公式如下[7]：

n=b+ξ×[c,d]

(8)

針對本文數據，b=c=10，d=40，ξ為屬于[0,1]隨機數。

飛行過程中蝙蝠更新位置xi、速度vi、響度Ai和脈沖速率ri的數學表達式為[12,13]：

fi=fmin+(fmax-fmin)β

(9)

(10)

(11)

當進入局部搜索，首先從最優解中任選個解，進行位置信息的隨機變更，讓每只蝙蝠基于局部解產生一個新解。公式如：

xnew=xold+εAt

(12)

其中，ε為一個隨機數且屬于[-1,1]；At是同一個時間段總蝙蝠響度的平均值。

隨著迭代過程的進行，更新脈沖發射響度Ai和速率ri。更新公式為：

(13)

其中，a和γ是常量。對于任意00，有：

(14)

通常情況令a=γ，參數值的選擇需要根據具體的試驗要求。

2.2蝙蝠算法的改進

針對加權樸素貝葉斯分類器分類錯誤率與屬性子集選擇的計算，重新定義蝙蝠算法的目標函數為：

(15)

式中，Eval(xi)對應分類的錯誤率，TF是屬性總數，SE是被選擇參與分類的屬性總數，δ和η分別表示分類精度的權重和特征子集比例的權重，其中δ∈[0,1]且η=1-δ。通常，分類的錯誤率比屬性子集比例賦予更高的權重，本文設置δ=0.9，η=0.1。

針對蝙蝠算法易于陷入局部最優和對高維空間搜索精度不高的缺點，提出了建立禁忌搜索TS(taboo search)機制，使蝙蝠群算法具備跳出局部最優的能力。為避免進行迂回搜索，禁忌搜索機制擁有一個存儲結構和禁忌準則,進而通過特赦準則來赦免禁忌表中的良好狀態,保證探索的多樣化，實現全局最優化；遇到沒被特赦的蝙蝠個體，利用下文的隨機擾動算子對其位置進行隨機擾動，進一步減小匹配誤差。

構造一個長度與蝙蝠個數相等的向量(禁忌表)記錄蝙蝠群體迭代E次不變的局部最優位置信息，其可能為局部最優解，為了快速跳出局部最優，增加種群多樣性，直接初始化蝙蝠群體。E值根據實際應用而定。在后續的搜索中，對存在禁忌表中的位置信息進行計數，然后以禁忌表中位置計數分量作為自變量構造罰函數[14]：

(16)

(17)

式中，ti是禁忌表的第i個分量，Δ是非常小的正數，a1>1，k是迭代次數。使用該罰函數根據式(14)重新構造相應的適應度函數，使適應度函數fitness(xi)與罰函數p(xi)近似成正比，則對應的適應度函數為：

(18)

如果某個位置被選作全局極值的次數越多，禁忌表記錄次數分量的值越大，相應罰函數的值較大，對應的適應度函數值也較大，該位置被再次作為全局極值的可能性就較小，這樣既可以剔除禁忌表中誤判的局部最優解，又保證了種群的多樣性；蝙蝠算法能最大可能跳離局部極值，得到精度更高的結果。若懲罰以后的適應度值仍最優，那么就用特赦準則，選取該位置為全局極值。

在對最優位置取值時與最佳位置會稍有偏差，所以在迭代過程中，如果遇到的位置在禁忌表中且通過罰函數計算的適應度值大于全局最優解的適應度值，那么這個局部最優解周圍可能存在我們要找的全局最優解。所以對局部最優解位置的速度值加入一個隨機擾動值，稱為“隨機擾亂算子”：

(19)

其中，φ為[0,1]，|Ri|為第i個位置的取值范圍大小，文中|Ri|=1。減少蝙蝠算法在局部最優解花費的時間，并進一步增強對局部最優解周圍區域搜索。

2.3屬性權值的計算過程

NB-IBA算法主要利用蝙蝠算法確定屬性權值，尋找權值是個訓練過程[15]。計算p(xk|Ci)時為避免零概率，要進行拉普拉斯校準。令wk=xi，并對wk進行標準化處理，使權值之和為1，每個蝙蝠對訓練樣本數據集分類進行預測，由于是有監督分類，可以得到樣本數據分類的錯誤率Eval(xi)。NB-IBA算法詳細步驟如下：

Step1數據預處理；讀取樣本數據，分別計算每個屬性的先驗概率和后驗概率；

Step2用式(8)隨機初始化蝙蝠群體數n，飛行過程中的位置xi(每只蝙蝠的位置代表一種屬性子集的組合)，速度vi，響度Ai，脈沖速率ri，常量E等各個參數。全局最優解best初始化為隨機一個最優xi，當前最優適應度值為fitnessbest；

Step3令wk=xi，并對wk進行標準化處理。每個個體對樣本數據集分類進行預測，用式(15)計算每個位置xi分類的適應度函數fitness(xi)的值；

Step4利用式(9)到式(11)生成新解，且每個參數都有最大與最小數值限制；

Step5判斷xi位置信息是否在禁忌表taboo中，存在，則次數分量值加1，執行Step8；不存在，則轉至Step6；

Step6判斷x*和適應度函數是否連續E代不變，是則執行Step7，否則轉至Step10；

Step7將x*位置信息保存到禁忌表taboo中，轉至Step2；

Step8利用式(16)-式(18)計算適應度值fitness(xi)，如果fitness(xi)>fitnessbest轉至Step9；否則fitnessbest=fitness(xi)，找到x*=xi，轉至Step4；

Step9執行式(19)，隨機擾動，用式(11)更新位置信息，利用式(14)生成fitnessnew，轉至Step10；

Step10判斷是否滿足變異條件(rand>ri)，如果滿足，用式(12)更新解的位置xnew；否則轉至Step11；

Step11若rand>Ai& fitness(xi)

Step12對蝙蝠列隊，找到當前最佳解x*；

Step13比較新位置的適應度值和當前最優適應度值是否滿足fitnessbest≤ fitnessnew，如果滿足，則更新當前最優適應度值和最優位置，否則轉到Step14；

Step14如果迭代結束，轉至Step15，否則轉至Step4；

Step15輸出全局最優解，可利用求得的權值wk=xi，用式(6)進行高維數據的分類預測。

3　仿真實驗

本文數據集來自UCI，依據不同規模，挑其中5種數據集，分別為：House-Votes，Credit-a，SPECTF-Heart，Lung和Mushroom。House-votes是廣泛使用的二元分類文獻數據集，這個數據集描述了每位美國眾議院議員投票情況，兩個類標號分別代表民主黨人和共和黨人；Credit也是一個二元分類數據集，關注的是信用卡的應用；SPECTF-Heart是一個包含76種屬性的二元類數據集，已經被用于心臟疾病的診斷中，其中1和0類編號表示患者是否存在心臟疾病；Lung是肺癌的病理學類型數據集，目的是展示最佳鑒別平面功率的病理類型；Mushroom(M-room)也是一個二元類數據集，包括假設樣本在傘狀蘑菇和環柄菇家族里與鰓蘑菇23種類型相同的特性描述。

圖1　Vote數據集分類錯誤行數的收斂曲線

圖3　MushRoom數據集分類錯誤行數的收斂曲線

針對數據集數據量較大且數據類型復雜的情況，進行多次試驗，在100次迭代內，改進的蝙蝠算法收斂速度明顯比未改進的快，不易陷入局部最優解，并能及早收斂至全局最優值。如圖1到圖3，上面曲線為改進前的蝙蝠算法，下面為改進后算法，剛開始的收斂速度都非常快，屬于隨機現象，但圖1的5～15次迭代、圖2的10～20與60～70次迭代和圖3的1～10次迭代過程中改進的算法效果明顯，改進后的算法可能利用禁忌搜索機制跳出了算法認為的局部最優或利用隨機擾動算子針對局部最優進行隨機擾動。因為E=9，改進后的算法在到達全局最優以前，幾乎不存在錯誤行數連續E次不變的情況，若存在E次不變，是由于下一次迭代所選蝙蝠位置信息的目標函數值恰好與上次相同。

經過多次測試，改進后的蝙蝠算法收斂速度和準確度都明顯優于未改進的蝙蝠算法。

圖4為針對所有數據集，NB-IBA算法(目標函數為錯誤率與屬性子集比例之和)的收斂曲線：

圖4　NB-IBA算法分類錯誤率的收斂曲線

圖4中橫坐標為迭代次數，縱坐標為分類的錯誤率值，利用改進后的蝙蝠算法優化樸素貝葉斯分類器，其分類的錯誤率明顯下降，即分類的準確率明顯提升。

本試驗對樸素貝葉斯分類算法(NB)、文獻[6]的新特征加權樸素貝葉斯分類算法(NB-W)以及NB-IBA算法進行試驗對比，NB-IBA算法在試驗的時候進行15次訓練，把所得屬性權值取均值，各算法的分類精度如表1所示。

表1　分類精度對比

本文利用五個UCI的數據集進行算法的驗證，除了Vote數據集，其余數據集所選擇的屬性與總屬性數值一樣，此時目標函數中的TF=SE。在這些數據集試驗中子屬性集的選擇對目標函數值不起作用，最終為計算錯誤率，也可以針對不同的屬性選擇進行試驗。針對Vote數據集，TF=17，SE=16。

圖5為表1的展現。

圖5　3種算法對5個數據集分類錯誤率對比

圖5中，橫坐標1～5數字按順序表示表1中5個數據集，縱坐標為分類的錯誤率。用本文提出的NB-IBA算法進行分類時，所有用到的數據集的錯誤率普遍比NB和NB-W低，若有數據集在測試數據上分類錯誤率偏高，可能是所設置的參數不適合、該訓練樣本設置的不合理或該數據集基本滿足條件類獨立性假設。

總的來說，NB-IBA在處理大部分數據集時能準確進行分類，到達理想的精確度。在算法的運行時間上，由于NB-IBA算法需要迭代地進行權值的搜索，因此訓練分類器的時間會比NB和NB-W慢一點，待訓練后，在以后的分類過程中，不僅速度與NB相當，精確率大幅度提高。本文在將位置轉換為權值時對其進行標準化處理，并不是直接用蝙蝠的位置作為權值。蝙蝠算法的參數根據具體問題具體設置，調整參數，可達到更令人滿意結果。

4　結　語

現有樸素貝葉斯分類算法條件獨立性假設與現實存在差異，本文利用給每個屬性賦予不同權值的方法削弱類獨立性假設。為進一步提高樸素貝葉斯的分類精準度，本文提出利用改進的蝙蝠算法優化貝葉斯分類器，改進的蝙蝠算法自動搜索屬性權值，并不是用蝙蝠位置作為權值，要對位置信息歸一化處理。由于傳統蝙蝠算法存在易陷入局部最優、早熟和收斂慢現象，本文改進蝙蝠算法，利用禁忌搜索機制避免算法陷入局部最優和早熟并達到全局最優化,利用隨機擾動算子對局部最優解進一步搜索，找到真正的全局最優解，最終實現快速收斂。本文提出的NB-IBA 算法可以根據數據特征提高樸素貝葉斯分類器精準度，只需極少訓練時間實現對樸素貝葉斯分類器的優化。試驗表明，NB-IBA相比傳統NB和文獻[6]的新NB-W算法，提高分類的精準度并證明了算法的可行性和有效性。

[1] Jiawei Han,Micheline Kamber.數據挖掘概念與技術[M].范明,孟小峰,譯.北京:機械工業出版社,2012:226-230.

[2] 徐光美,劉宏哲.基于特征加權的多關系樸素貝葉斯分類模型[J].計算機科學,2014,41(10):283-285.

[3] Chickering D M.Learning Bayesian Networks is NP-Complete[J].Lecture Notes in Statistics,1996,10(2):594-605.

[4] Zhang H.Learning weighted naive Bayes with accurate ranking[C]//Data Mining,2004.ICDM '04.Fourth IEEE International Conference on.IEEE,2004:567-570.

[5] Zhang H.Learning weighted naive Bayes with accurate ranking[C]//Data Mining,2004.ICDM '04.Fourth IEEE International Conference on.IEEE,2004:567-570.

[6] 張步良.基于分類概率加權的樸素貝葉斯分類方法[J].重慶理工大學學報:自然科學版,2012,26(7):81-83.

[7] Yang X S.A New Metaheuristic Bat-Inspired Algorithm[M].Nature Inspired Cooperative Strategies for Optimization (NICSO 2010).Springer Berlin Heidelberg,2010:65-74.

[8] 李枝勇,馬良,張惠珍.蝙蝠算法收斂性分析[J].數學的實踐與認識,2013,43(12):182-189.

[9] Yang X S,Gandomi A H.Bat algorithm:a novel approach for global engineering optimization[J].Engineering Computations,2012,29(5):464-483.

[10] Yang X S.Bat Algorithm:Literature Review and Applications[J].International Journal of Bio Inspired Computation,2013,5(3):141-149.

[11] Webb G I,Pazzani M J.Adjusted probability Naive Bayesian induction[J].Lecture Notes in Computer Science,1998,11(1):285-295.

[12] Yilmaz S,Kucuksille E U,Cengiz Y.Modified Bat Algorithm[J].Elektronika Ir Elektrotechnika,2014,20(2):71-78.

[13] 王文,王勇,王曉偉.一種具有記憶特征的改進蝙蝠算法[J].計算機應用與軟件,2014,31(11):257-259,329.

[14] 張世勇,熊忠陽.基于禁忌搜索的混合粒子群優化算法[J].計算機研究與發展,2007,44(S1):339-343.

[15] 連陽陽,任淑霞.一種基于離散粒子群優化的貝葉斯分類算法[J].科技信息,2014(4):66-71.

ON BAYESIAN CLASSIFIER OPTIMISATION BASED ON BAT ALGORITHM

Jiang Liqing1,2Zhang Mingxin2*Zheng Jinlong2Dai Jiao1

1(School of Computer Science and Technology,China University of Mining and Technology,Xuzhou 221116,Jiangsu,China)2(SchoolofComputerScienceandEngineering,ChangshuInstituteofTechnology,Changshu215500,Jiangsu,China)

Naive Bayesian classifier is a widely used simple and efficient classification algorithm, but there is a difference between the ″naive Bayesian hypothesis″ of conditional independence and the reality, such hypothesis restricts the accuracy of naive Bayesian classifier. To cripple this hypothesis, we used the improved bat algorithm (IBA) to optimise naive Bayesian classifier. IBA introduces Taboo search mechanism and random perturbation operator to prevent the na?ve Bayesian classifier from falling into local optimal solution, and thus accelerates the convergence rate. IBA automatically searches the weight value of every attribute, by assigning different weight to each attribute, it weakens the hypothesis of independence and enhances the accuracy of naive Bayesian classifier without greatly increasing the cost of calculation. Test result showed that comparing with traditional naive Bayesian and newest weighted Bayesian classification algorithm proposed in paper[6], the proposed algorithm has higher accuracy in classification effect.

ClassificationNaive BayesianAttribute weightingBat algorithm

2015-06-19。國家自然科學基金項目(61173130)。蔣禮青，碩士生，主研領域：數據挖掘。張明新，教授。鄭金龍，碩士。戴嬌，碩士生。

TP301.6

A

10.3969/j.issn.1000-386x.2016.09.061