黃建瓊，郭文龍

1.福州外語外貿(mào)學(xué)院 理工學(xué)院，福州 350202

2.福建江夏學(xué)院 電子信息科學(xué)學(xué)院，福州 350108

1 前言

在機(jī)器學(xué)習(xí)中，將數(shù)據(jù)集類別分布不平衡的現(xiàn)象稱為不平衡問題。采用傳統(tǒng)算法解決此類問題時(shí)，分類結(jié)果往往偏向多數(shù)分類，導(dǎo)致少數(shù)分類無法被正確識(shí)別出來。此外，傳統(tǒng)算法基本是基于總體分類最大化來訓(xùn)練分類器的，這樣會(huì)忽略一些樣本的錯(cuò)誤分類，從而影響傳統(tǒng)分類器的分類結(jié)果[1-3]。然而在許多實(shí)際應(yīng)用中，少量樣本卻比大量樣本更有價(jià)值，如銀行欺詐用戶識(shí)別、醫(yī)學(xué)癌癥診斷以及網(wǎng)絡(luò)黑客入侵等[4-8]。

不平衡數(shù)據(jù)挖掘是數(shù)據(jù)挖掘中一個(gè)極其重要的問題，目前已有許多算法應(yīng)用在數(shù)據(jù)挖掘上，如K-最近鄰居算法(K-Nearest Neighbor，KNN)、決策樹算法（Decision Tree，DT）、人工神經(jīng)網(wǎng)絡(luò)（Artificial Neural Network，ANN）和遺傳算法（Genetic Algorithm，GA）等[9-13]。這些算法通常假設(shè)數(shù)據(jù)集中各種分類的分布是均衡的，且可忽略某些分類。對(duì)此，部分學(xué)者提出一些處理不平衡數(shù)據(jù)的優(yōu)化方法，如調(diào)整訓(xùn)練數(shù)據(jù)集的規(guī)模，使用代價(jià)敏感的分類器和滾雪球等[14-16]。而這些方法仍可能造成一般規(guī)則中的信息丟失和其他類別的錯(cuò)誤分類，并最終導(dǎo)致數(shù)據(jù)過度匹配以及因過多的具體規(guī)則而引發(fā)的表現(xiàn)不佳。針對(duì)傳統(tǒng)的優(yōu)化方法無法解決數(shù)據(jù)集面臨的這些問題，智能優(yōu)化算法隨之而生。

近年來，一些文獻(xiàn)提出了混合PSO 與BFO 方法研究最優(yōu)化問題，如礦井自動(dòng)化控制的主要參數(shù)最優(yōu)化、電動(dòng)機(jī)控制系統(tǒng)、伺服系統(tǒng)的PID參數(shù)最優(yōu)化、電力系統(tǒng)穩(wěn)定性優(yōu)化、詞袋模型優(yōu)化及蛋白質(zhì)亞細(xì)胞定位預(yù)測[17-21]；另有文獻(xiàn)提出優(yōu)化粒子群算法應(yīng)用于SVM_ELM 模型及改進(jìn)粒子群算法用于特征選擇[22-23]。因?yàn)榱Ｗ尤菏諗克俣瓤欤阉髂芰?qiáng)，本文提出混合粒子群優(yōu)化算法與改進(jìn)的細(xì)菌覓食優(yōu)化算法應(yīng)用于不平衡數(shù)據(jù)分類，目的是找到一個(gè)有效的算法解決原始BFO容易陷入局部優(yōu)化的問題，并最終提高不平衡數(shù)據(jù)的準(zhǔn)確性。

粒子群優(yōu)化算法（Particle Swarm Optimization，PSO）是由Eberhart博士和Kennedy博士提出的[24]。它是一種模擬社會(huì)行為的群體啟發(fā)式算法，類似鳥群會(huì)聚集到最優(yōu)位置，以實(shí)現(xiàn)在多維空間中找到準(zhǔn)確的目標(biāo)。細(xì)菌覓食優(yōu)化算法（Bacterial Foraging Optimization，BFO）是Passino于2002年根據(jù)大腸桿菌在人體腸道覓食現(xiàn)象而提出的仿生智能算法[25]。BFO 算法主要包括趨化、聚集、復(fù)制和遷徙四個(gè)操作。細(xì)菌覓食趨化操作可加強(qiáng)細(xì)菌的局部搜索能力，但是細(xì)菌覓食的全局搜索能力只能通過遷徙來完成，且全局搜索能力受到遷徙概率的限制，因此容易陷入局部最優(yōu)。

本文提出了混合粒子群優(yōu)化算法與改進(jìn)的細(xì)菌覓食優(yōu)化算法應(yīng)用于不平衡數(shù)據(jù)分類。數(shù)據(jù)預(yù)處理采用Borderline-SMOTE 和 Tomek Link 的方法。然后，利用所提出的算法對(duì)不平衡數(shù)據(jù)進(jìn)行分類。因?yàn)镻SO 具有較強(qiáng)的全局搜索能力、個(gè)體效應(yīng)和群體效應(yīng)，將PSO 結(jié)合到改進(jìn)的BFO 中，可改進(jìn)原始BFO 的趨化操作過程。其次，改進(jìn)復(fù)制操作過程，提高優(yōu)勝劣汰的選擇標(biāo)準(zhǔn)。最后，改進(jìn)遷徙操作過程，防止種群陷入局部最優(yōu)，防止進(jìn)化停滯。所提出的算法可提高原BFO的全局搜索能力和搜索效率，提升不平衡數(shù)據(jù)的分類準(zhǔn)確度。研究目的是獲得一個(gè)有效的算法來提高不平衡數(shù)據(jù)的準(zhǔn)確性，以便解決原始BFO 容易陷入局部優(yōu)化的問題。卵巢癌微陣列數(shù)據(jù)是卵巢癌癥診斷的重要信息，本文利用實(shí)際卵巢癌微陣列數(shù)據(jù)進(jìn)行分類。本文算法提高了卵巢癌診斷的準(zhǔn)確率，有助于更準(zhǔn)確地判斷和理解醫(yī)學(xué)中的卵巢癌信息。本研究可建立一個(gè)供醫(yī)療使用的數(shù)據(jù)庫系統(tǒng)，以便于研究和跟蹤每個(gè)卵巢癌患者的病史。

2 細(xì)菌覓食優(yōu)化和粒子群優(yōu)化算法介紹

本文提出的混合算法是結(jié)合粒子群優(yōu)化算法與改進(jìn)的細(xì)菌覓食優(yōu)化算法，并將該算法應(yīng)用于不平衡數(shù)據(jù)分類。下面簡要描述粒子群優(yōu)化算法與細(xì)菌覓食優(yōu)化算法原理。

2.1 細(xì)菌覓食優(yōu)化算法

細(xì)菌覓食優(yōu)化算法（BFO）具有非常好的分類效果，是一種全局隨機(jī)搜索的進(jìn)化算法。BFO 算法主要通過使用趨化、聚集、復(fù)制和遷徙四個(gè)操作的迭代計(jì)算來解決優(yōu)化問題[26]。在趨化操作中，大腸桿菌在覓食中有兩個(gè)基本運(yùn)動(dòng)：游動(dòng)和翻滾。

通常，在環(huán)境條件惡劣的區(qū)域中，細(xì)菌會(huì)更經(jīng)常翻滾；在好的環(huán)境中，則更經(jīng)常游動(dòng)。設(shè)細(xì)菌的種群規(guī)模為S，則P(j,k,l)={θi(j,k,l)|i=1,2,…,S}，表示細(xì)菌種群S中，第i個(gè)細(xì)菌的第j次趨化操作、第k次復(fù)制操作及第l次遷徙操作。設(shè)H(i,j,k,l)表示第i個(gè)細(xì)菌在位置θ(j,k,l)的代價(jià)，Nc為趨化操作的一個(gè)方向上的細(xì)菌長度。那么，第i個(gè)細(xì)菌每一步的趨化操作可用以下式子表示：

其中，α(i)>0 代表細(xì)菌向前游動(dòng)的步長單位，β(i)代表細(xì)菌翻滾后的隨機(jī)方向向量的單位向量。經(jīng)過趨化操作步驟后，開始聚集操作過程，在聚集操作中，除了細(xì)菌自身的覓食方式外，每個(gè)細(xì)菌個(gè)體會(huì)收到群體中的其他個(gè)體發(fā)來的呼吁信號(hào)。因此，在BFO算法中，每一個(gè)細(xì)菌個(gè)體覓食的決策行為主要受到兩個(gè)因素的影響：一是自身所獲得的信息，即在單位時(shí)間內(nèi)個(gè)體覓食的目的是最大化個(gè)體獲得的能量；二是來自其他個(gè)體的信息，即通過群體中的其他細(xì)菌來傳遞覓食信息。其聚集操作用式（2）表達(dá)如下：

其中，Hcc(θ,P(j,k,l))是附加在實(shí)際代價(jià)函數(shù)上的懲罰值，θm表示最優(yōu)細(xì)菌的位置，dattract、drepellent、wattract和wrepellent為可以被適當(dāng)選擇的不同的系數(shù)。在聚集操作中，Ns為生物學(xué)動(dòng)機(jī)選擇次數(shù)。聚集操作可用式子表示如下：

基于復(fù)制操作保持群體規(guī)模不變的原則，在復(fù)制過程中，按照細(xì)菌位置計(jì)算代價(jià)H的優(yōu)劣排序，把排在后面的50%細(xì)菌淘汰掉，剩余的一半細(xì)菌進(jìn)行自我復(fù)制，各自生成一個(gè)與自己完全相同的新個(gè)體，即生成的新個(gè)體與原個(gè)體有相同的位置，也就說具有相同的覓食能力。經(jīng)過Nre復(fù)制步驟后，開始遷徙操作過程，設(shè)Ned為遷徙的步數(shù)，遷徙伴隨著一定的概率Ped發(fā)生，當(dāng)個(gè)體細(xì)菌滿足遷徙的概率Ped，個(gè)體會(huì)死亡，并在解空間的任一位置隨機(jī)產(chǎn)生一個(gè)新個(gè)體。新個(gè)體可能與原始細(xì)菌有不同的覓食能力，有利于跳出局部最優(yōu)解。細(xì)菌覓食優(yōu)化流程圖如圖1所示。

圖1 細(xì)菌覓食優(yōu)化算法的流程圖

2.2 粒子群優(yōu)化算法

粒子群優(yōu)化算法（PSO）是一種學(xué)習(xí)鳥群在自然界中覓食的仿生算法，把鳥當(dāng)成空間中一個(gè)粒子，鳥群就是粒子群。PSO是基于群體（群體中的每個(gè)個(gè)體又稱為粒子）協(xié)作的隨機(jī)搜索算法，粒子會(huì)在每一次迭代中更新自己[27]。為找到最優(yōu)解，每個(gè)粒子根據(jù)它自身找到的最優(yōu)位置(pbest)與其他所有成員找到的最優(yōu)位置(gbest)這兩個(gè)因素來改變它的搜索方向[28]。Shi等學(xué)者將pbest稱為認(rèn)知部分，gbest稱為社會(huì)部分。每個(gè)粒子攜帶相應(yīng)的信息，即它自己的速度和位置。粒子根據(jù)自身的相應(yīng)信息，來決定它運(yùn)動(dòng)的距離和方向。粒子群優(yōu)化算法（PSO）先初始化一組隨機(jī)分布到待搜索的解空間中的粒子，包括個(gè)體最優(yōu)位置pbest和全局最優(yōu)位置gbest兩個(gè)最優(yōu)因素。個(gè)體最優(yōu)位置是由每個(gè)粒子搜尋到的最優(yōu)解，而全局最優(yōu)位置則是由粒子群體獲得的最優(yōu)解。PSO算法采用正反饋機(jī)制，而使得它具有記憶功能。該算法原理簡單，參數(shù)較少，且適用性較好。粒子根據(jù)以下的公式來更新自己的速度和位置[29]：

圖2 粒子群優(yōu)化算法的流程圖

3 本文算法

針對(duì)BFO算法收斂速度慢以及易陷入局部最優(yōu)的缺點(diǎn)，本文提出了將粒子群優(yōu)化算法與改進(jìn)的細(xì)菌覓食優(yōu)化算法相結(jié)合，應(yīng)用于不平衡數(shù)據(jù)的分類。本文旨在提高卵巢癌微陣列資料分類的準(zhǔn)確度，并提高醫(yī)生對(duì)卵巢癌微陣列資料判斷的實(shí)用性和準(zhǔn)確性。本文用三個(gè)數(shù)據(jù)集測試所提出算法的性能。一個(gè)是卵巢癌微陣列數(shù)據(jù)（ovarian cancer microarray data），另兩個(gè)來自UCI數(shù)據(jù)庫的垃圾電子郵件數(shù)據(jù)集（spam email dataset）和動(dòng)物園數(shù)據(jù)集（zoo dataset）。卵巢癌微陣列數(shù)據(jù)來自某醫(yī)院收集到的卵巢癌基因芯片真實(shí)數(shù)據(jù)，共有9 600個(gè)特征，不平衡率約為1∶20[30]。使用的微陣列數(shù)據(jù)實(shí)例包括卵巢組織、陰道組織、宮頸組織和子宮肌層，包括6例良性卵巢腫瘤（BOT）、10例卵巢腫瘤（OVT）和25例卵巢癌（OVCA）。垃圾電子郵件數(shù)據(jù)集和動(dòng)物園數(shù)據(jù)集來自UCI 數(shù)據(jù)庫。對(duì)于垃圾電子郵件數(shù)據(jù)集，共有4 601 封電子郵件，具有 58 個(gè)特征，如表 1 所示，不平衡率約為1∶1.54；對(duì)于動(dòng)物園數(shù)據(jù)集，共有101 個(gè)實(shí)例，具有17個(gè)特征，如表2所示，不平衡率約為1∶25。

表1 垃圾電子郵件數(shù)據(jù)集的58個(gè)特征

表2 動(dòng)物園數(shù)據(jù)集的17個(gè)特征

本文算法的流程圖如圖3 所示。首先進(jìn)行參數(shù)初始化，數(shù)據(jù)預(yù)處理采用Borderline-SMOTE和Tomek Link的方法，并應(yīng)用本文算法對(duì)不平衡數(shù)據(jù)進(jìn)行分類。為了對(duì)少數(shù)類進(jìn)行過采樣，設(shè)計(jì)了Borderline-SMOTE，其主要思想是通過從少數(shù)類產(chǎn)生合成實(shí)例來平衡類別[31]。對(duì)于少數(shù)類實(shí)例的子集，通過搜索得到k個(gè)最近鄰。將k近鄰定義為歐氏距離和mi之間的最小距離，并從中隨機(jī)選擇n個(gè)合成實(shí)例，記錄為Yj,j=1,2,…,n，以創(chuàng)建新的少數(shù)實(shí)例mnew，如式（6）所述，其中rand是[0，1]之間的隨機(jī)數(shù)。

圖3 本文算法的流程圖

Tomek Link 為一種數(shù)據(jù)清洗技術(shù)，能被有效地應(yīng)用于消除采樣方法中的重疊[32]。Tomek Link 用于刪除類之間不必要的重疊，直到屬于同一類中最小距離處的最近鄰對(duì)。假設(shè)一對(duì)最小歐氏距離的最近鄰(mi,mj)屬于不同的類，d(mi,mj)表示mi和mj間的歐幾里德距離。如果不存在滿足式（7）的實(shí)例ml,則(mi,mj)為一對(duì)Tomek Link。

在本文中，用于SMOTE的參數(shù)k設(shè)置為k=3。在對(duì)數(shù)據(jù)進(jìn)行預(yù)處理之后，產(chǎn)生θi。隨后，執(zhí)行本文算法。針對(duì)BFO 算法易陷入局部最優(yōu)的缺點(diǎn)，本文算法包括改進(jìn)的趨化操作過程、改進(jìn)的復(fù)制操作過程以及改進(jìn)的遷徙操作過程。

3.1 改進(jìn)的趨化操作

原始BFO 算法主要是以趨化操作過程進(jìn)行搜索。當(dāng)趨化操作搜索目標(biāo)區(qū)域時(shí)，其游動(dòng)步長和翻滾操作直接影響算法的效果。當(dāng)游動(dòng)步長較大時(shí)，全局搜索能力較強(qiáng)；反之，則局部搜索能力較強(qiáng)。由于趨化操作的特性，BFO 算法具有良好的局部搜索能力，因?yàn)樗梢栽谮吇僮髦懈淖兎较?，所以局部搜索?zhǔn)確度非常好。但細(xì)菌的全局搜索能力只能依靠遷徙操作，其全局搜索能力欠佳。

因?yàn)镻SO具有較強(qiáng)記憶和全局搜索能力、個(gè)體效應(yīng)和群體效應(yīng)，本文利用PSO這個(gè)優(yōu)點(diǎn)，將PSO結(jié)合到改進(jìn)的BFO中，可改進(jìn)原始BFO的趨化操作過程，以便解決原始BFO容易陷入局部優(yōu)化的問題。通過使用粒子先進(jìn)行搜索，然后將粒子當(dāng)成細(xì)菌，以提高原始BFO的全局搜索能力。本文目的是找到一個(gè)有效的算法，即結(jié)合PSO 收斂速度快、搜索能力強(qiáng)和BFO 分類效果佳的優(yōu)點(diǎn)，提高不平衡數(shù)據(jù)的準(zhǔn)確性。

3.2 改進(jìn)的復(fù)制操作

在原始BFO 算法復(fù)制操作過程中，種群規(guī)模為S的細(xì)菌群中，利用當(dāng)前細(xì)菌位置代價(jià)值H作為好壞排列依據(jù)，有一半(S/2)的優(yōu)良細(xì)菌被復(fù)制，復(fù)制產(chǎn)生的子群代替原始細(xì)菌群中的另一半劣質(zhì)細(xì)菌，種群的多樣性降低。為了增加群體的多樣性，并避免丟失最優(yōu)個(gè)體，本文引入父代個(gè)體（最優(yōu)父代個(gè)體除外）與最優(yōu)父代個(gè)體做交叉運(yùn)算?；旌瞎奖硎救缦拢?/p>

其中，X代表父代個(gè)體（最優(yōu)父代個(gè)體除外），Xbest代表最優(yōu)父代個(gè)體，rand為區(qū)間[0，1]內(nèi)的隨機(jī)數(shù)。

3.3 改進(jìn)的遷徙操作

遷徙操作有助于BFO 算法跳出局部最優(yōu)解，并找到全局最優(yōu)解，在原始BFO 的遷徙操作中按照給定的固定概率Ped進(jìn)行遷徙，沒有考慮種群的進(jìn)化情況。本文改進(jìn)了原有BFO 算法中的遷徙操作，引入了種群進(jìn)化因子，根據(jù)種群的進(jìn)化情況進(jìn)行遷徙，有利于算法尋優(yōu)的有效性，防止種群進(jìn)化不前而陷入局部最優(yōu)。其群體進(jìn)化因子公式表示如下：

式中，Hgen代表第gen次迭代時(shí)的最優(yōu)代價(jià)值，rand用于防止式子中的分母為0，本文用(1-fevo) 代替原始BFO算法中的Ped。當(dāng)fevo>1 時(shí)，則進(jìn)化加速，此時(shí)種群進(jìn)化程度較快，種群群體處在快而有效的尋優(yōu)狀態(tài)，以較低的遷徙概率(1-fevo)進(jìn)行遷徙，可以保留當(dāng)前有利的位置信息。當(dāng)0 ≤fevo<1 時(shí)，進(jìn)化減慢，容易陷入局部最優(yōu)，需要以較高的遷徙概率(1-fevo)進(jìn)行遷徙，跳出局部最優(yōu)解，防止種群進(jìn)化不前。

為了克服原始BFO 算法容易陷入局部最優(yōu)的缺點(diǎn)，本文算法的整個(gè)過程如下：

（1）設(shè)定粒子群種群大小為S，隨機(jī)生成每個(gè)粒子的初始速度和位置，設(shè)定PSO 的最大迭代次數(shù)為T。在本文中，PSO 插入到每個(gè)BFO 的趨化過程中，PSO 的種群大小與BFO相同。設(shè)定BFO算法參數(shù)Nc,Ns,Nre,Ned,dattract,drepellent,wattract,wrepellent；設(shè)定 BFO 迭代次數(shù)為Nc×Nre×Ned。

（2）在本文中，代價(jià)H定義為計(jì)算每個(gè)粒子的分類準(zhǔn)確度。求出第i個(gè)粒子的最優(yōu)位置，以及總體中所有粒子最優(yōu)代價(jià)時(shí)的最優(yōu)位置。如果和比上一次迭代的值好，則更新和。

（4）如果滿足設(shè)置的終止條件則停止，否則跳回到步驟（2）。終止條件是達(dá)到總體中所有粒子最優(yōu)代價(jià)時(shí)的最優(yōu)位置，或超過設(shè)定的PSO 的最大迭代次數(shù)T。式（4）和式（5）將粒子視為細(xì)菌，PSO完成獲得更新的位置。換句話說，在改進(jìn)的趨化性操作過程中執(zhí)行PSO以獲得更新的位置θi。

（5）執(zhí)行BFO 群集過程中，由式（3）計(jì)算Hsw的代價(jià)值。

（6）在改進(jìn)的復(fù)制操作過程中，執(zhí)行式（8）增加群體的多樣性并避免丟失最優(yōu)個(gè)體，即父代個(gè)體（最優(yōu)父代除外）與最優(yōu)個(gè)體做交叉運(yùn)算。

（7）在改進(jìn)的遷徙操作過程中，執(zhí)行式（9）使用群體進(jìn)化因子fevo。PSO 根據(jù)(1-fevo)生成新的θi。在改進(jìn)的BFO中，用(1-fevo)替換原始BFO中的Ped。

（8）如果滿足BFO 的最大迭代次數(shù)，則算法結(jié)束。最后，在此實(shí)驗(yàn)中輸出分類準(zhǔn)確度的結(jié)果。

本文算法中，代價(jià)H定義為分類準(zhǔn)確度。利用混淆矩陣測試本文算法的性能?；煜仃嚾绫?所示。

表3 混肴矩陣

TP和FP分別代表真陽性分類和假陽性分類，F(xiàn)N和TN分別代表假陰性分類和真陰性分類。預(yù)測值是一個(gè)正例，記錄為P（Positive）。預(yù)測值是一個(gè)負(fù)例，記錄為N（Negative）。預(yù)測值與實(shí)際值相同，記錄為T（True）。預(yù)測值與實(shí)際值相反，記錄為F（False）。模型分類后，在數(shù)據(jù)集中定義的結(jié)果有4 個(gè)：TP,預(yù)測為正，實(shí)際為正；FP,預(yù)測為正，實(shí)際為負(fù)；TN,預(yù)測為負(fù)，實(shí)際為負(fù)；FN,預(yù)測為負(fù)，實(shí)際為正。分類準(zhǔn)確度計(jì)算公式如下：

采用接受者操作特征曲線（Receiver Operating Characteristic，ROC）和曲線下面積（Area Under the Curve，AUC）可以測試分類結(jié)果的性能。這是因?yàn)镽OC 曲線具有良好的特性：當(dāng)測試數(shù)據(jù)集中正例和負(fù)例的分布發(fā)生變化時(shí)，ROC 曲線可以保持不變。不平衡數(shù)據(jù)常發(fā)生在實(shí)際數(shù)據(jù)集中，也就是說，負(fù)實(shí)例要比正實(shí)例多得多（反之亦然），并且測試數(shù)據(jù)中正實(shí)例和負(fù)實(shí)例的分布可能隨時(shí)間變化。計(jì)算AUC可作為不平衡數(shù)據(jù)的評(píng)估方法，它可以全面描述分類器在不同決策閾值下的性能。AUC的計(jì)算公式如下：

4 實(shí)驗(yàn)結(jié)果和分析

本文目的是為了獲得有效的算法來提高不平衡數(shù)據(jù)的準(zhǔn)確性。為了驗(yàn)證本文算法的性能，利用卵巢癌微陣列數(shù)據(jù)、垃圾電子郵件數(shù)據(jù)集和動(dòng)物園數(shù)據(jù)集進(jìn)行仿真實(shí)驗(yàn)，數(shù)據(jù)預(yù)處理采用Borderline-SMOTE 和Tomek Link的方法。

4.1 參數(shù)取值和實(shí)驗(yàn)結(jié)果收斂性及運(yùn)算復(fù)雜度分析

算法的參數(shù)值設(shè)定是算法性能和效率的關(guān)鍵，BFO有許多參數(shù)，如何確定BFO 的最優(yōu)參數(shù)來優(yōu)化算法性能是一個(gè)非常復(fù)雜的問題。原始BFO參數(shù)取值對(duì)實(shí)驗(yàn)結(jié)果收斂性及運(yùn)算速度的影響主要有：

（1）種群規(guī)模S的大小影響B(tài)FO效能的發(fā)揮，種群規(guī)模小，BFO的計(jì)算速度快，但種群的多樣性降低，影響算法的優(yōu)化性能；種群規(guī)模大，個(gè)體初始時(shí)分布的區(qū)域多，靠近最優(yōu)解的機(jī)會(huì)就越高。也可以說是，種群規(guī)模越大，種群中個(gè)體的多樣性就越高，越能避免算法陷入局部最優(yōu)值。但是種群規(guī)模太大時(shí)，算法的計(jì)算量就會(huì)增加，算法的收斂速度會(huì)變慢。

（2）趨向性操作執(zhí)行的次數(shù)Nc的值越大，算法的搜索更細(xì)致，但是算法的復(fù)雜度也會(huì)隨之增加；反之，Nc的值越小，算法更容易陷入局部最優(yōu)值，算法的性能好壞就更多地依賴于復(fù)制操作。

（3）復(fù)制操作執(zhí)行的次數(shù)Nre的值越大，算法越能避開食物缺乏或者有毒的區(qū)域而去食物豐富的區(qū)域搜索，從而提高算法的收斂速度。當(dāng)然Nre太大，同樣也會(huì)增加算法的復(fù)雜度；反之，如果Nre太小，算法易早熟收斂。

（4）遷徙操作執(zhí)行的次數(shù)Ned值太小，算法沒有發(fā)揮遷徙操作的隨機(jī)搜索作用；反之，Ned值越大，算法能搜索的區(qū)域越大，解的多樣性增加，能避免算法陷入早熟，其算法的復(fù)雜度也會(huì)隨之增加。遷徙概率Ped選取適當(dāng)?shù)闹的軒椭惴ㄌ鼍植孔顑?yōu)值，但是Ped的值不能太大，否則BFO就變成了隨機(jī)搜索算法。

啟發(fā)式搜索算法的自身優(yōu)勢，一次運(yùn)行就得到一組解，能夠耗費(fèi)較小時(shí)間和計(jì)算代價(jià)搜索到理想的解，并取得很好的效果。其中，粒子群優(yōu)化算法由于其收斂速度快、搜索能力強(qiáng)的優(yōu)點(diǎn)受到諸多研究者關(guān)注。本文利用PSO的優(yōu)點(diǎn)，將PSO結(jié)合到改進(jìn)的BFO中，可改進(jìn)原始BFO 的趨化操作過程，解決原始BFO 容易陷入局部優(yōu)化的問題。為了避免出現(xiàn)大量計(jì)算時(shí)間又可找到全局解，本文在設(shè)定PSO和BFO的參數(shù)時(shí)，依據(jù)經(jīng)驗(yàn)值將BFO算法參數(shù)設(shè)置為S=50,Nc=100,Ns=4,Nre=4，Ned=2,Ped=0.25,dattract=0.05,drepellent=0.05,wattract=0.05,wrepellent=0.05,α(i)=0.1,i=1,2,…,S。BFO 迭代次數(shù)為Nc×Nre×Ned=100×4×2=800[25]。PSO 的最大迭代次數(shù)設(shè)置為5 000，其他參數(shù)設(shè)置為慣性權(quán)重w=0.6，學(xué)習(xí)因子c1=c2=1.5，每個(gè)粒子的最大速度vmax=2[24]。本文采用隨機(jī)分區(qū)的10 倍交叉驗(yàn)證結(jié)果，即將數(shù)據(jù)分為10 份，其中9 份數(shù)據(jù)作為訓(xùn)練數(shù)據(jù)，剩下1份作為測試數(shù)據(jù)。

4.2 本文算法與其他算法的分類準(zhǔn)確度比較分析

下面除了研究本文算法外，也用其他現(xiàn)有算法進(jìn)行比較，如支持向量機(jī)（Support Vector Machine，SVM）、決策樹（DT）、隨機(jī)森林（Random Forest，RF）、K-最近鄰算法(KNN)及原細(xì)菌覓食優(yōu)化（BFO）。支持向量機(jī)是在高維特征空間中使用線性函數(shù)假設(shè)空間的學(xué)習(xí)系統(tǒng)。決策樹使用分區(qū)信息熵最小化遞歸地將數(shù)據(jù)集劃分為更小的子分區(qū)，然后生成樹結(jié)構(gòu)。隨機(jī)森林是一種集成的分類學(xué)習(xí)方法，它在訓(xùn)練時(shí)構(gòu)造多個(gè)決策樹，并輸出依賴于大多數(shù)類的類。K-最近鄰算法是一種基于n維模式空間中最接近訓(xùn)練樣本的目標(biāo)分類方法。原細(xì)菌覓食優(yōu)化算法如第2.1節(jié)所述。

（1）表4 分別列出了卵巢癌微陣列數(shù)據(jù)、垃圾電子郵件數(shù)據(jù)集和動(dòng)物園數(shù)據(jù)集的分類性能。從表4 中可以看出，本文算法對(duì)卵巢癌微陣列數(shù)據(jù)、垃圾電子郵件數(shù)據(jù)集和動(dòng)物園數(shù)據(jù)集的平均分類準(zhǔn)確度分別為93.47%、96.42%和99.54%。從表4 可以明顯看出，在對(duì)所有方法進(jìn)行比較后，本文算法具有最優(yōu)的分類結(jié)果，這是因?yàn)橹悄苄畔⒖梢栽跍y試數(shù)據(jù)集的分類上有好的性能表現(xiàn)，而本文算法也具有類似的功能，因此在分類準(zhǔn)確度上有較好的表現(xiàn)結(jié)果。

（2）在比較結(jié)果中，可以發(fā)現(xiàn)原始BFO對(duì)三個(gè)數(shù)據(jù)集的分類準(zhǔn)確度均沒有本文算法分類準(zhǔn)確度好。因?yàn)樵糂FO 可以在趨化操作中改變方向，所以局部搜索能力更好，但是全局搜索只能依靠遷徙操作過程，全局搜索能力不是很好，所以在分類準(zhǔn)確度表現(xiàn)上沒有本文算法好。

（3）本文算法在改進(jìn)的趨化過程中引入了PSO，具有記憶和全局搜索的能力。在研究中首先使用粒子進(jìn)行全局搜索，然后將這些粒子視為細(xì)菌，提高了全局搜索能力。改進(jìn)的復(fù)制操作過程中，在保留最優(yōu)個(gè)體的情況下，對(duì)復(fù)制后的父代引入交叉算子，增加種群的多樣性。在改進(jìn)的遷徙操作過程中，引入了(1-fevo)替換原始BFO 中的Ped，以防止種群死亡和陷入局部最優(yōu)狀態(tài)，因此在分類準(zhǔn)確度上有較好的表現(xiàn)。

表4 不同算法的分類準(zhǔn)確度

4.3 ROC和AUC分析

在本次的仿真實(shí)驗(yàn)中，ROC 和AUC 用于評(píng)估本文算法性能，AUC的值介于0～1之間且越大越好。卵巢癌微陣列數(shù)據(jù)的AUC 值為0.979，如圖4 所示。垃圾電子郵件數(shù)據(jù)集的AUC 值為0.987，如圖5 所示。動(dòng)物園數(shù)據(jù)集的AUC值為0.995，如圖6所示。實(shí)驗(yàn)結(jié)果顯示，本文算法具有良好的分類性能。

圖4 卵巢癌微陣列數(shù)據(jù)的ROC和AUC

圖5 垃圾電子郵件數(shù)據(jù)集的ROC和AUC

圖6 動(dòng)物園數(shù)據(jù)集的ROC和AUC

本文提出了混合粒子群和改進(jìn)的細(xì)菌覓食優(yōu)化算法應(yīng)用于不平衡數(shù)據(jù)的分類，根據(jù)研究結(jié)果，提出以下幾方面的建議：

（1）算法運(yùn)行的改進(jìn)。實(shí)現(xiàn)優(yōu)化的關(guān)鍵是算法的操作，設(shè)計(jì)出色的運(yùn)算對(duì)提高算法的性能和效率起著重要作用。在原BFO算法中，提高其趨化性和復(fù)制性，遷徙操作，協(xié)調(diào)處理算法的局部挖掘能力和全局探索能力將成為BFO研究的熱點(diǎn)。

（2）算法參數(shù)的選擇。算法的參數(shù)值是決定算法性能和效率的關(guān)鍵。在進(jìn)化算法中，沒有通用的方法來確定算法的最優(yōu)參數(shù)，其中大多數(shù)是根據(jù)經(jīng)驗(yàn)選擇的。目前，BFO的參數(shù)很多，如何確定BFO的最優(yōu)參數(shù)來優(yōu)化算法本身的性能是一個(gè)非常復(fù)雜的問題。本文在4.1節(jié)中進(jìn)行了參數(shù)取值和實(shí)驗(yàn)結(jié)果收斂性及運(yùn)算復(fù)雜度的分析，可作為未來繼續(xù)研究的方向。

（3）與其他算法結(jié)合。結(jié)合BFO 和其他算法的優(yōu)點(diǎn)以提出更有效的算法是BFO研究中的重要課題。

5 結(jié)論

本文提出一種混合粒子群和改進(jìn)的細(xì)菌覓食優(yōu)化算法應(yīng)用于不平衡數(shù)據(jù)的分類。數(shù)據(jù)預(yù)處理用Borderline-SMOTE和Tomek Link技術(shù)。隨后，將本文算法應(yīng)用于不平衡數(shù)據(jù)的分類，以解決原始BFO 算法陷入局部最優(yōu)的缺點(diǎn)。使用三個(gè)數(shù)據(jù)集來測試本文算法的性能。本文算法包括改進(jìn)的趨化操作過程、改進(jìn)的復(fù)制操作過程以及改進(jìn)的遷徙操作過程。在本文中，通過在改進(jìn)的趨化操作過程中使用粒子進(jìn)行搜索，然后將粒子視為細(xì)菌，可以提高BFO 的全局搜索能力。在改進(jìn)了趨化操作之后，進(jìn)行了群集操作、改進(jìn)的復(fù)制操作，最后進(jìn)行改進(jìn)的遷徙操作。本文算法對(duì)卵巢癌微陣列數(shù)據(jù)的平均分類準(zhǔn)確度為93.47%，對(duì)垃圾電子郵件數(shù)據(jù)集和動(dòng)物園數(shù)據(jù)集的平均分類準(zhǔn)確度分別為96.42%和99.54%，卵巢癌微陣列數(shù)據(jù)的AUC值為0.979，垃圾電子郵件數(shù)據(jù)集和動(dòng)物園數(shù)據(jù)集的AUC 值分別為0.987 和0.995。實(shí)驗(yàn)結(jié)果表明，本文算法與現(xiàn)有方法比較，在不平衡數(shù)據(jù)分類準(zhǔn)確度中有良好的表現(xiàn)結(jié)果。