基于蝙蝠算法的貝葉斯分類器優(yōu)化研究

蔣禮青　張明新　鄭金龍　戴　嬌

1(中國(guó)礦業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院　江蘇 徐州 221116)2(常熟理工學(xué)院計(jì)算機(jī)科學(xué)與工程學(xué)院　江蘇 常熟 215500)

?

基于蝙蝠算法的貝葉斯分類器優(yōu)化研究

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

1(中國(guó)礦業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院江蘇 徐州 221116)2(常熟理工學(xué)院計(jì)算機(jī)科學(xué)與工程學(xué)院江蘇 常熟 215500)

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

分類樸素貝葉斯屬性加權(quán)蝙蝠算法

0　引　言

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

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

本文提出利用改進(jìn)的蝙蝠算法優(yōu)化樸素貝葉斯分類器NB-IBA的算法，將蝙蝠算法與樸素貝葉斯分類算法結(jié)合，采用IBA來(lái)自動(dòng)搜索每個(gè)屬性權(quán)值，削弱條件獨(dú)立性假設(shè)，優(yōu)化樸素貝葉斯分類器。試驗(yàn)表明，NB-IBA算法確實(shí)能提高樸素貝葉斯分類器分類的精準(zhǔn)度。

1　加權(quán)樸素貝葉斯分類算法

1.1樸素貝葉斯模型[1]

設(shè)D是訓(xùn)練元組與類標(biāo)號(hào)集合。每個(gè)元組用一個(gè)n維向量表示屬性向量，如X={x1,x2,…,xn}，描述由n個(gè)屬性A1,A2,…,An對(duì)元組的n個(gè)測(cè)量。假設(shè)類個(gè)數(shù)為m個(gè)，為C1,C2,…,Cm。給定一個(gè)X訓(xùn)練元組，分類器預(yù)測(cè)屬于類Ci的X，當(dāng)且僅當(dāng)：

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

(1)

當(dāng)p(Ci|X)最大化，稱此時(shí)的類Ci為“最大后驗(yàn)假設(shè)”。

類先驗(yàn)概率可以用p(Ci)=|Ci,D|/|D| 估計(jì)，其中|Ci,D|是D中Ci類的訓(xùn)練元組數(shù)。給定元組的類標(biāo)號(hào)，因此：

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

(2)

可以根據(jù)X進(jìn)行概率p(x1|Ci),p(x2|Ci),…,p(xn|Ci)的估計(jì)?？紤]屬性值是離散的還是連續(xù)的：

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

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

(3)

因此：

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

(4)

函數(shù)g中第二和第三個(gè)參數(shù)分別是Ci類訓(xùn)練元組屬性Ak的均值(即平均值)和標(biāo)準(zhǔn)差。

后驗(yàn)概率公式為：

(5)

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

(6)

1.2加權(quán)樸素貝葉斯模型

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

(7)

其中，屬性Ak的權(quán)值是wk，權(quán)值與屬性影響力成正比關(guān)系，權(quán)值大，對(duì)應(yīng)屬性對(duì)分類正確率的影響力就強(qiáng)，反之則弱。

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

2　蝙蝠算法的改進(jìn)及屬性權(quán)值的計(jì)算

2.1蝙蝠算法

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

群體數(shù)n的選擇應(yīng)綜合考慮算法的可靠性和計(jì)算時(shí)間，對(duì)通常問(wèn)題10只蝙蝠已足夠，對(duì)于較復(fù)雜的問(wèn)題可取50只。按照本文數(shù)據(jù)集的復(fù)雜性，蝙蝠個(gè)數(shù)取值公式如下[7]：

n=b+ξ×[c,d]

(8)

針對(duì)本文數(shù)據(jù)，b=c=10，d=40，ξ為屬于[0,1]隨機(jī)數(shù)。

飛行過(guò)程中蝙蝠更新位置xi、速度vi、響度Ai和脈沖速率ri的數(shù)學(xué)表達(dá)式為[12,13]：

fi=fmin+(fmax-fmin)β

(9)

(10)

(11)

當(dāng)進(jìn)入局部搜索，首先從最優(yōu)解中任選個(gè)解，進(jìn)行位置信息的隨機(jī)變更，讓每只蝙蝠基于局部解產(chǎn)生一個(gè)新解。公式如：

xnew=xold+εAt

(12)

其中，ε為一個(gè)隨機(jī)數(shù)且屬于[-1,1]；At是同一個(gè)時(shí)間段總蝙蝠響度的平均值。

隨著迭代過(guò)程的進(jìn)行，更新脈沖發(fā)射響度Ai和速率ri。更新公式為：

(13)

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

(14)

通常情況令a=γ，參數(shù)值的選擇需要根據(jù)具體的試驗(yàn)要求。

2.2蝙蝠算法的改進(jìn)

針對(duì)加權(quán)樸素貝葉斯分類器分類錯(cuò)誤率與屬性子集選擇的計(jì)算，重新定義蝙蝠算法的目標(biāo)函數(shù)為：

(15)

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

針對(duì)蝙蝠算法易于陷入局部最優(yōu)和對(duì)高維空間搜索精度不高的缺點(diǎn)，提出了建立禁忌搜索TS(taboo search)機(jī)制，使蝙蝠群算法具備跳出局部最優(yōu)的能力。為避免進(jìn)行迂回搜索，禁忌搜索機(jī)制擁有一個(gè)存儲(chǔ)結(jié)構(gòu)和禁忌準(zhǔn)則,進(jìn)而通過(guò)特赦準(zhǔn)則來(lái)赦免禁忌表中的良好狀態(tài),保證探索的多樣化，實(shí)現(xiàn)全局最優(yōu)化；遇到?jīng)]被特赦的蝙蝠個(gè)體，利用下文的隨機(jī)擾動(dòng)算子對(duì)其位置進(jìn)行隨機(jī)擾動(dòng)，進(jìn)一步減小匹配誤差。

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

(16)

(17)

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

(18)

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

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

(19)

其中，φ為[0,1]，|Ri|為第i個(gè)位置的取值范圍大小，文中|Ri|=1。減少蝙蝠算法在局部最優(yōu)解花費(fèi)的時(shí)間，并進(jìn)一步增強(qiáng)對(duì)局部最優(yōu)解周圍區(qū)域搜索。

2.3屬性權(quán)值的計(jì)算過(guò)程

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

Step1數(shù)據(jù)預(yù)處理；讀取樣本數(shù)據(jù)，分別計(jì)算每個(gè)屬性的先驗(yàn)概率和后驗(yàn)概率；

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

Step3令wk=xi，并對(duì)wk進(jìn)行標(biāo)準(zhǔn)化處理。每個(gè)個(gè)體對(duì)樣本數(shù)據(jù)集分類進(jìn)行預(yù)測(cè)，用式(15)計(jì)算每個(gè)位置xi分類的適應(yīng)度函數(shù)fitness(xi)的值；

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

Step5判斷xi位置信息是否在禁忌表taboo中，存在，則次數(shù)分量值加1，執(zhí)行Step8；不存在，則轉(zhuǎn)至Step6；

Step6判斷x*和適應(yīng)度函數(shù)是否連續(xù)E代不變，是則執(zhí)行Step7，否則轉(zhuǎn)至Step10；

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

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

Step9執(zhí)行式(19)，隨機(jī)擾動(dòng)，用式(11)更新位置信息，利用式(14)生成fitnessnew，轉(zhuǎn)至Step10；

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

Step11若rand>Ai& fitness(xi)

Step12對(duì)蝙蝠列隊(duì)，找到當(dāng)前最佳解x*；

Step13比較新位置的適應(yīng)度值和當(dāng)前最優(yōu)適應(yīng)度值是否滿足fitnessbest≤ fitnessnew，如果滿足，則更新當(dāng)前最優(yōu)適應(yīng)度值和最優(yōu)位置，否則轉(zhuǎn)到Step14；

Step14如果迭代結(jié)束，轉(zhuǎn)至Step15，否則轉(zhuǎn)至Step4；

Step15輸出全局最優(yōu)解，可利用求得的權(quán)值wk=xi，用式(6)進(jìn)行高維數(shù)據(jù)的分類預(yù)測(cè)。

3　仿真實(shí)驗(yàn)

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

圖1　Vote數(shù)據(jù)集分類錯(cuò)誤行數(shù)的收斂曲線

圖3　MushRoom數(shù)據(jù)集分類錯(cuò)誤行數(shù)的收斂曲線

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

經(jīng)過(guò)多次測(cè)試，改進(jìn)后的蝙蝠算法收斂速度和準(zhǔn)確度都明顯優(yōu)于未改進(jìn)的蝙蝠算法。

圖4為針對(duì)所有數(shù)據(jù)集，NB-IBA算法(目標(biāo)函數(shù)為錯(cuò)誤率與屬性子集比例之和)的收斂曲線：

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

圖4中橫坐標(biāo)為迭代次數(shù)，縱坐標(biāo)為分類的錯(cuò)誤率值，利用改進(jìn)后的蝙蝠算法優(yōu)化樸素貝葉斯分類器，其分類的錯(cuò)誤率明顯下降，即分類的準(zhǔn)確率明顯提升。

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

表1　分類精度對(duì)比

本文利用五個(gè)UCI的數(shù)據(jù)集進(jìn)行算法的驗(yàn)證，除了Vote數(shù)據(jù)集，其余數(shù)據(jù)集所選擇的屬性與總屬性數(shù)值一樣，此時(shí)目標(biāo)函數(shù)中的TF=SE。在這些數(shù)據(jù)集試驗(yàn)中子屬性集的選擇對(duì)目標(biāo)函數(shù)值不起作用，最終為計(jì)算錯(cuò)誤率，也可以針對(duì)不同的屬性選擇進(jìn)行試驗(yàn)。針對(duì)Vote數(shù)據(jù)集，TF=17，SE=16。

圖5為表1的展現(xiàn)。

圖5　3種算法對(duì)5個(gè)數(shù)據(jù)集分類錯(cuò)誤率對(duì)比

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

總的來(lái)說(shuō)，NB-IBA在處理大部分?jǐn)?shù)據(jù)集時(shí)能準(zhǔn)確進(jìn)行分類，到達(dá)理想的精確度。在算法的運(yùn)行時(shí)間上，由于NB-IBA算法需要迭代地進(jìn)行權(quán)值的搜索，因此訓(xùn)練分類器的時(shí)間會(huì)比NB和NB-W慢一點(diǎn)，待訓(xùn)練后，在以后的分類過(guò)程中，不僅速度與NB相當(dāng)，精確率大幅度提高。本文在將位置轉(zhuǎn)換為權(quán)值時(shí)對(duì)其進(jìn)行標(biāo)準(zhǔn)化處理，并不是直接用蝙蝠的位置作為權(quán)值。蝙蝠算法的參數(shù)根據(jù)具體問(wèn)題具體設(shè)置，調(diào)整參數(shù)，可達(dá)到更令人滿意結(jié)果。

4　結(jié)　語(yǔ)

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

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

[2] 徐光美,劉宏哲.基于特征加權(quán)的多關(guān)系樸素貝葉斯分類模型[J].計(jì)算機(jī)科學(xué),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] 張步良.基于分類概率加權(quán)的樸素貝葉斯分類方法[J].重慶理工大學(xué)學(xué)報(bào):自然科學(xué)版,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].數(shù)學(xué)的實(shí)踐與認(rèn)識(shí),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ìn)蝙蝠算法[J].計(jì)算機(jī)應(yīng)用與軟件,2014,31(11):257-259,329.

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

[15] 連陽(yáng)陽(yáng),任淑霞.一種基于離散粒子群優(yōu)化的貝葉斯分類算法[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。國(guó)家自然科學(xué)基金項(xiàng)目(61173130)。蔣禮青，碩士生，主研領(lǐng)域：數(shù)據(jù)挖掘。張明新，教授。鄭金龍，碩士。戴嬌，碩士生。

TP301.6

A

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