PSO_BFA優化詞袋模型及蛋白質亞細胞定位預測

胡雪嬌，陳行健，趙 南，薛 衛

南京農業大學 信息科學技術學院，南京210095

1 引言

詞袋模型（Bag of Words model，BOW）源自于文本處理領域，研究人員不斷發掘其潛能，在物體識別領域中[1-2]也有廣泛應用。BOW 模型一般由特征提取、聚類分析構建字典、直方圖構建三部分組成，將目標對象轉換為特征向量送入分類器完成分類，最終將目標對象轉換為特征向量送入分類器完成分類[3]。為提高BOW模型的性能，提出了許多優化算法。如Irfan等人[4]通過對字典降維并使用TF_IDF（Term Frequency_Inverse Document Frequency）算法賦予相應詞權重，解決了文本錯誤匹配問題；Li 等人[5]使用空間金字塔匹配技術（Spatial Pyramid Matching，SPM），在圖像表示階段加入局部特征的空間位置信息，從而提高了分類性能。Xie 等人[6]通過分析鄰域像素和局部圖像，引入LQP（Local Quantized Pattern）構建字典，取得了較好效果；Zhu等人[7]利用模糊均值（Fuzzy C-Means）代替K 均值（K-Means）優化字典，使初始聚類中心的選擇更加合理；汪榮貴等人[8]引入顯著區域提取，結合三角剖分方法融入圖像全局信息，得到了較好的預測效果。

當前眾多詞袋模型的算法改進雖然取得了良好的效果，但是忽略了對詞袋模型的參數的優化，其中參數大多根據經驗值選取。在使用BOW 模型完成特征提取的過程中，存在窗口大小d 和字典大小k 組成的一組參數，對BOW 的性能影響非常大。本文結合群體智能化的粒子群算法（Particle Swarm Optimization，PSO）和全局尋優能力強的細菌覓食算法（Bacterial Foraging Algorithm，BFA），在PSO進行局部搜索時，加入BFA的復制和遷移行為，求得混合算法PSO_BFA 的最優解為窗口大小d 和字典大小k 的最佳組合。將優化后的BOW 模型應用到蛋白質亞細胞定位預測中，結合蛋白質序列的氨基酸組成和偽氨基酸組成獲得蛋白質序列的詞袋特征[9]，最后送入支持向量機多類分類器進行定位預測，實驗證明PSO_BFA 優化的詞袋模型能有效提高蛋白質亞細胞定位預測的精度。

2 PSO_BFA優化詞袋模型

詞袋模型最初用于文本建模，是一種利用機器學習算法對文本數據進行特征表達的方法。其基本原理是將目標對象用若干無序單詞來表示，這些單詞組成一個集合。通過統計每個單詞在文檔中出現的次數對目標對象進行向量化描述。應用詞袋模型進行某項具體研究通常分為以下幾個步驟：首先對目標對象進行局部區域分析，并提取局部特征作為特征單詞訓練字典。此時存在一個窗口值d，即特征單詞的長度。在獲得目標對象的局部特征后，需要對這些特征單詞進行聚類，獲取一定數量的聚類中心作為字典，通常使用K-means 聚類[10]，字典大小k 的取值決定了最終的聚類效果。利用字典將目標對象的各個局部特征映射到與之距離最近的聚類中心，然后統計目標對象屬于各個聚類中心的特征單詞個數，獲得單詞直方圖，計算目標對象中每個特征單詞出現的頻率，即為最終的詞袋特征。在傳統詞袋模型中，窗口值d 和字典大小k 值的選取對詞袋模型的性能影響較大，針對這一問題，提出一種基于PSO_BFA優化的改進詞袋模型，尋找窗口大小d 和字典大小k 的最佳組合。

2.1 粒子群算法

粒子群算法是由文獻[11]提出的一種新型群體智能進化算法，具有記憶最佳位置、共享信息等特點。在PSO 優化問題中，每一個解即為一個粒子，每個粒子在N 維搜索空間中按照一定的速度運動，通過適應度函數來評價粒子的優劣，粒子根據自己的運動經驗以及其他粒子的運動經驗，來動態調整運動速度和位置，向搜索空間中最優的位置運動，從而得到優化問題的最優解。粒子通過跟蹤兩個“極值”來更新狀態[12]：第一個是整個種群當前時刻找到的最優解，叫作全局極值Gbest ；第二個是粒子自身所找到的最優解，叫作個體極值Pbest。在N 維搜索空間中第i 個粒子的位置和速度分別表示為Xi=(xi1,xi2,…,xiN)和Vi=(vi1,vi2,…,viN)T。通過評價各粒子的目標函數，確定t 時刻每個粒子的最佳位置(Pbest)Pi=(pi1,pi2,…,piN)T以及群體所發現的最佳位置(Gbest)Pg=(pg1,pg2,…,pgN)T。

2.2 細菌覓食算法

細菌覓食算法是由Passino等人[13]于2002年基于細菌覓食行為過程而提出的一種隨機搜索的智能仿生優化算法。細菌的覓食過程主要描述為趨向行為、復制（繁殖）行為和遷移（驅散）行為。其中復制行為使細菌覓食算法擁有優勝略汰的特點。淘汰較差的半數細菌，保留較好的半數菌體并復制產生新細菌。假設細菌種群規模為M ，群體中要淘汰的細菌數為Mr=M/2。在淘汰過程中首先將群體中的細菌個體按照自身的適應值好壞進行排序，將適應值較差的Mr 個細菌淘汰，剩下的Mr 細菌個體進行自身復制，即復制出與原來的個體一樣的新個體，從而保持群體總數保持不變[14]。

BFA算法中的細菌驅散過程，能夠加強細菌覓食算法的全局尋優能力，避免細菌陷入局部最優。細菌的驅散操作是在菌體經過數次復制行為之后發生的。驅散操作會根據一定的遷移概率Ped來決定是否驅散。當遷移概率Ped滿足驅散條件時，則將隨機地把細菌驅散到其所在搜索空間中去。由以上過程可看出BFA 算法有群體智能算法的全局尋優、易計算等優點[15]。

2.3 PSO_BFA優化詞袋模型優化實現

PSO進行群體、協同搜索，記憶個體和群體信息[16]，具有相當快的逼近最優解的速度，原理簡單，通用性強，不依賴問題信息，易實現[17]。缺點是在局部的搜索準確性不高，且易陷入局部最優[18]。BFA在沿某一方向進行搜索的過程中，可根據適應值的變化調整運動方向，具有變方向搜索能力[19]，使細菌個體易找到所在鄰域內的最優值，不易錯過更優解所在的區域，大大提高了對全局的搜索精度和搜索能力[20]。主要缺點是沒有對菌群最優信息的記憶功能，全局搜索能力弱且收斂速度慢[21]。混合粒子群和細菌覓食算法彌補了兩種算法的缺陷，將細菌覓食算法的復制和遷移行為應用到粒子群算法中提高算法的全局搜索能力和收斂速度。

在運用BOW 模型提取特征的過程中，存在兩個重要參數：窗口大小d 和字典大小k。為優化窗口大小d和字典大小k 的取值過程，將d 的取值范圍作為橫向坐標，k 的取值范圍作為縱向坐標構建參數搜索空間，每一組(d,k)值對應一組特征向量，每一組特征向量具有相應的分類準確率。將求得最高分類準確率的過程抽象為粒子尋求最高適應度值的過程，(d,k)為粒子在搜索空間的位置。因此，d 、k 值的選取過程轉化為粒子的移動過程，可以利用PSO 和BFA 的群體智能尋優方法實現BOW 模型的參數尋優，從而獲得識別精度較高的特征向量。

鑒于以上分析，在PSO 進行局部搜索時，加入BFA的復制和遷移行為，如果粒子的適應度值有增長趨勢，則按原始方式更新速度和位置。如果大多粒子的適應度值沒有明顯提高，保留適應度值較高的半數粒子，去除適應度值較低的另半數粒子，留下的半數粒子復制產生新粒子，保持粒子總數不變。然后將粒子隨機驅散到搜索空間的其他位置，進行下一階段的搜索。解空間由窗口大小d 和字典大小k 構成，粒子的適應度值即為該組(d,k)計算出的分類準確率。

PSO-BFA混合優化算法流程如圖1所示。

圖1 PSO_BFA混合優化算法流程圖

設計實現的算法思想：在一個兩維的目標搜索空間中，由T（T ＞10）個粒子構成一個群體，其中第i 個粒子的位置表示為Xi=(d,k)，d 為窗口大小，k 為字典大小。每個粒子的位置就是一個潛在的解。首先初始化一群隨機粒子，通過迭代找到適應度值最高的解，在迭代過程中，粒子通過跟蹤自身最優解(Pbest)Pi=(pi1,pi2,…,piN)T和整個種群的最優解pg2,…,pgN)T更新自己的位置[13]。用公式表示粒子的速度和位置更新如下：

式中，i=1,2,…,M，M 為粒子總數；d=1,2,…,N，N 為解空間維數；ω 為慣性因子；是粒子的速度向量；c1、c2為加速因子；r1和r2是均勻分布在[0，1]上的隨機數，互相獨立；是當前粒子的位置；pid表示當前粒子本身最優解的位置；pgd表示當前整個種群最優解的位置[14]。

輸入：慣性因子c1、c2，最大迭代次數Tmax，粒子個數M ，每代復制粒子數和淘汰粒子數為M/2，窗口大小d 和字典大小k 的取值范圍，粒子速度范圍[-vdmax,vdmax]，遷移概率Ped=0，取值根據不同情況的經驗值進行選取。

輸出：種群最優值Gbest 及位置Pg。

算法步驟如下：

（1）設置初始種群，初始化各參數，根據窗口大小d和字典大小k 的取值范圍設置粒子位置范圍[xmin,xmax]，在位置范圍內隨機初始化粒子的位置Xi以及速度Vi，用Pi記錄粒子當前位置為粒子初始最優位置，設置遷移概率Ped=0。

（2）循環操作：for i=1,2,…,Tmax，如果i ≤Tmax循環繼續，否則循環結束。

（3）根據SVM 分類預測結果評價各粒子的適應度值，用Gbest 記錄當前種群最優的適應度值，相應粒子位置為當前最優位置記做Pg，用Pbest 記錄個體最優適應度值，然后根據公式（1）來更新粒子的速度，通過公式（2）更新粒子的位置。

（4）更新粒子速度位置后，則根據分類預測結果重新評價粒子的適應度值，若優于更新前的粒子，則更新該粒子的Pi為粒子當前位置。若某粒子位置更新后成為種群適應度值最高的粒子且優于已有的Gbest ，則更新Gbest ，種群最優Pg更新為該粒子的位置。若更新后最高適應度值低于上一代Gbest，則Ped=Ped+0.1。Ped值按一定粒度值增加，是為了防止粒子陷入局部最優發生早熟的現象，將SVM 分類預測結果終分類結果作為粒子適應度值，根據適應度值來動態更新遷移概率值，經多次實驗得出粒度設為0.1效果最佳。

（5）如果Ped＜0.5，轉向下一步，否則，保留適應度值較高的M/2 個粒子，淘汰適應度值較低的另M/2 個粒子，留下的M/2 個粒子復制產生新粒子，新粒子屬性與原粒子相同，粒子總數不變，然后將粒子隨機驅散到搜索空間的其他位置。遷徙概率Ped的取值范圍在0到1之間，設置值過大會導致算法在搜索空間中變成隨機窮舉搜索。因此，根據經驗值將Ped的最大值設為0.5。

（6）i=i+1，轉向步驟（2）。

（7）循環結束，輸出種群最優解Gbest ，以及種群最優位置Pg。

為檢驗優化詞袋模型的性能，將其應用到蛋白質亞細胞定位預測研究中，運用優化詞袋模型提取蛋白質序列特征，然后將特征值送入支持向量機進行分類預測，并將分類準確率作為適用度值，對每一組(d,k)值對應的詞袋特征值進行評價。

3 實驗與分析

3.1 數據集

采用兩個凋亡蛋白數據集ZD98和CH317，ZD98數據集由Zhou 和Doctor[22]構建，分為4 個亞細胞定位類別，共有98 條蛋白質序列，分別是線粒體蛋白（Mitochondrial proteins，mi）13 條、細胞質蛋白（Cytoplasmic proteins，cy）43 條、膜蛋白（Membrane proteins，me）30條和其他類蛋白（other）12條。CH317數據集是由Chen和Li[23]構建，分為6個亞細胞定位類別，共有317條蛋白質序列，分別是分泌蛋白（Secreted proteins，se）17 條、細胞核蛋白（Nuclear proteins，nu）52 條、細胞質蛋白（Cytoplasmic proteins，cy）112 條、內質網蛋白（Endoplasmic reticulum proteins，en）47 條、膜蛋白（Membrane proteins，me）55 條和線粒體蛋白（Mitochondrial proteins，mi）34條。

3.2 參數選擇

對實驗的PSO_BFA 優化算法參數進行設置，慣性因子c1=c2=2，最大迭代次數Tmax=1 000，粒子個數M =50，每代復制粒子數和淘汰粒子數為M/2，窗口大小d 取值范圍設為[L/5,L]，其中L 為數據集中最短蛋白質序列的長度，字典大小k 取值范圍設為[20，500]，k,d 值均取整數，粒子速度范圍[-vdmax,vdmax] ，其中vdmax=k ?xdmax，0.1 ≤k ≤0.2，xdmax為d 維空間上限，遷移概率Ped初始化為0。

3.3 檢驗方法與評價指標

首先根據優化后的詞袋模型提取蛋白質序列的詞袋特征。實驗借助Lin等人[24]設計開發的LIBSVM工具箱構造SVM 多類分類器，采用一對一的構造方法為任意兩類樣本構造一個SVM分類器。對一個未知樣本進行分類時，根據當前類別投票數來判別該樣本屬于哪一類別，采用Jackknife進行假設檢驗。Jackknife是亞細胞定位預測中應用最多的檢驗方法，基本原理為：先從數據集中取出一條蛋白質序列作為測試序列，其余蛋白質序列作為訓練集，一次測試結束后將這條測試序列放回數據集。第二輪檢驗，取出下一條蛋白質序列作為測試序列，剩下的做訓練集，以此類推，直到數據集中所有序列都測試完畢[25]。測試次數等于數據集的大小，這種檢驗方法具有最小的任意性，是一種客觀有效的交叉驗證方法[26]。

為了便于比較蛋白質亞細胞區間預測的結果，對實驗方法進行有效評估，引入敏感性Sn、特異性Sp和相關系數MMCi這3個指標進行評價，并統計總的準確率A，定義如下：

其中，FNi是第i 類亞細胞區間預測錯誤的序列條數，TPi是第i 類亞細胞區間預測正確的序列條數，TNi是被正確預測的非第i 類亞細胞區間的序列條數，FPi是非第i 類亞細胞區間但被預測為第i 類區間的序列條數，M 為亞細胞類別總數。

3.4 實驗結果與分析

運用PSOBFA優化前后的BOW模型對數據集ZD98和CH317進行蛋白質序列特征提取，并將各特征值送入SVM 分類器進行亞細胞定位預測，實驗結果分別列于表1和表2中。在表中，用PSO算法優化的BOW_AAC和BOW_PseAAC特征提取算法表示為pso1和pso2，用BFA算法優化的BOW_AAC 和BOW_PseAAC 特征提取算法表示為bfa1 和bfa2，經PSO_BFA 優化的特征提取算法表示為b_f1 和b_f2。根據實驗結果繪制優化前后的預測結果圖，如圖2～5所示。

3.4.1 ZD98實驗結果與分析

表1、圖2 和圖3 結果顯示，在數據集ZD98 上，經PSO_BFA 優化的BOW 模型得到的詞袋特征綜合性能提升明顯，并能進一步提高識別準確率。經過PSO_BFA優化后的BOW_AAC 和BOW_PseAAC 的預測準確率比單PSO 優化方法分別提高了1.1%和1.0%，比單BFA優化方法均提高了2.1%。在other 亞細胞類上，經優化的BOW_PseAAC特征的特異性Sp達到了100%。

3.4.2 CH317實驗結果與分析

由表2、圖4 和圖5 結果可以看出，在數據集CH317上，PSO_BFA 優化后的BOW 模型比PSO 優化的BOW準確率分別提高了1.0%和0.6%，與BFA_BOW_AAC相比，預測準確率分別提高了1.9%和1.2%，PSO_BFA_BOW_AAC的綜合性能均有明顯提升。與PSO_BOW_AAC 相比，PSO_BFA_BOW_AAC 在se 和mi 亞細胞類上，敏感性Sn提升了5.9%，在en亞細胞類上，特異性Sp提升3.4%，在mi亞細胞類上，相關系數MMCi提升3.8%。PSO_BFA_BOW_PseAAC與PSO_BOW_PseAAC、BFA_BOW_PseAAC相比在各亞細胞區間均有不同程度的性能提升。

表1 ZD98數據集預測結果 %

表2 CH317數據集預測結果 %

圖2 優化前后的BOW_AAC在ZD98上的預測結果

圖3 優化前后的BOW_PseAAC在ZD98上的預測結果

圖4 優化前后的BOW_AAC在CH317上的預測結果

圖5 優化前后的BOW_PseAAC在CH317上的預測結果

對比以上結果可以看出，在兩個數據集上經加入細菌覓食優化的粒子群算法優化的BOW 模型都獲得了更高的識別準確率。不管是在特異性Sp和相關系數MMCi還是在總的準確率A 的評價上，結果均優于粒子群算法和細菌覓食算法優化的BOW模型。這說明在同一的目標搜索空間下，PSO_BFA 優化算法的收斂概率大于細菌覓食算法，且同時大于粒子群優化算法。這印證了粒子群算法與細菌覓食算法的不同特點：粒子群算法的搜索速度快、較粗略，能相對快速確定全局極值的鄰域，但局部搜索準確率不高；而細菌覓食算法的搜索比較細致，易在局部取得最優值，但全局尋優能力差且收斂速度慢。混合粒子群和細菌覓食算法結合兩者的優點，將細菌覓食算法的復制和遷移行為應用到粒子群算法中提高算法的全局搜索能力和收斂速度。因此，無論在準確率還是在搜索速度上，均顯著優于單一的粒子群算法和細菌覓食算法，上述實驗成功證明了優化算法的有效性。

3.4.3 與其他算法對比

為了進一步說明優化算法在蛋白質亞細胞區間定位預測的有效性，將本文方法在ZD98和CH317數據集上的預測結果列于表3、4中，同時將選取在蛋白質亞細胞定位預測領域中具有代表性的傳統蛋白質序列特征提取算法AAC、PseAAC、PSSM 和組合特征向量（Combined Feature Vector）等算法進行特征提取，并送入SVM分類器得到的預測準確率一并列出；表中也列出了趙南等人[9]將詞袋模型結合AAC 算法對蛋白質序列進行特征提取，采用Jackknife進行檢驗的實驗結果。表格的前兩行，根據文獻[27]和[28]中提到的AAC、PseAAC方法作為特征提取的方法，提取20 維向量作為一條蛋白質序列特征，然后放入SVM 中進行分類得出預測結果。實驗使用libsvm中的庫函數，主要參數為最佳懲罰參數c 和核函數參數g，文中通過交叉驗證方法訓練得到一組最佳參數。文獻[29]中采用位置特異性評分矩陣（PSSM）提取蛋白質序列特征，主要參數PSI-BLAST設為0.001。文獻[9]中，詞袋模型中窗口大小d 和字典大小k 根據經驗值選取。

表3 ZD98數據集預測結果比較%

表4 CH317數據集預測結果比較 %

從表3 可以看出，在ZD98 數據集上本文算法相比傳統蛋白質序列特征提取算法AAC、PseAAC等在總體預測精度上最大提升了約10 個百分點，在cyto 亞細胞類上的預測準確率達到了100%，實驗證明本文方法能有效增加蛋白質亞細胞區間定位預測的準確率。將本文方法與基于特征融合和詞袋模型的實驗結果進行對比，在相同數據集上的準確率也都提高了約3 到4 個百分點，實驗表明本文算法較基于傳統蛋白質序列特征提取的改進算法也具有顯著優勢。通過表4 的比較可以看出，在CH317 數據集上，本文算法在cyto 這一亞細胞類上的預測準確率最高達到了98.2%，相比其他算法提升了約3.6個百分點，在Nucl這一亞細胞類上的準確率最高提升了19.8個百分點，總的準確率較優化前的詞袋模型提升了4.4個百分點。

詞袋模型是一種十分有效的文本特征提取方法，經過本文的優化效果得到進一步提升。詞袋模型中d 值和k 值對特征提取效果的影響很大。對比算法[9]中，詞袋模型中窗口大小d 和字典大小k 均是根據經驗值選取的，然而針對不同的研究對象以及樣本空間最優參數值都是不同的，隨機選取或根據經驗值選取參數均會影響最終預測結果。本文使用PSO_BFA 混合優化算法，將最終分類結果作為粒子適應度值，動態求得d 值和k值的最佳組合，從而改進詞袋模型的預測分類效果。同時，隨著數據規模的增大，發揮粒子群和細菌覓食結合算法的群體智能優化性能，在參數空間中對窗口大小d和字典大小k 的選取更加合理，能夠找到一組或多組(d,k)使提取的詞袋特征值具有較高的識別精度。

4 結束語

BOW模型應用廣泛，但針對傳統BOW模型的改進工作很少涉及參數優化。本文利用BOW模型的主要參數窗口大小d 和字典大小k 構建參數搜索空間，將BOW 模型求得最高分類準確率的過程，抽象為粒子尋求最高適應度值的過程。充分發揮PSO_BFA算法的群體智能優化的性能，對(d,k)的選取過程進行優化，并將其應用到蛋白質亞細胞定位預測研究中。經PSO_BFA優化的BOW模型得到的詞袋特征能在更短的時間內找到相應的亞細胞區間，數據集規模越大，性能提升越明顯。實驗證明基于PSO_BFA優化的詞袋模型應用于蛋白質亞細胞定位預測中能有效提高識別精度。本文在詞袋模型參數優化方面的研究取得了一些成果，然而詞袋模型忽略了數據的位置信息，接下來將對位置特征的提取融合進行研究，并嘗試在預測模型構建方面做一些工作，集成學習、深度學習等方法將是關注的重點。