基于細菌覓食算法和支持向量機的表情識別

馬家辰，武冠群，馬立勇，孫明健

（哈爾濱工業大學（威海）信息與電氣工程學院，山東 威海264209）

0 引 言

為提高表情識別［1］準確率，可以在表情識別的預處理、特征提取和識別分類3方面做改進［2，3］。作為識別分類方法之一，基于統計學習理論的支持向量機 （support vector machine，SVM）算法，在模式識別問題中表現出許多優勢，近年來越來越受到重視，將SVM 運用于人臉表情識別中，已取得較好的實驗結果［4］，但其分類性能取決于參數的選擇。為了提高分類準確率；在改進SVM 方面，朱婭妮等利用遺傳算法優化SVM 參數，并將優化后的SVM（GA－SVM）用于人臉表情識別［5］；Min Tang等提出了應用于表情識別的PSO－SVM 算法 （粒子群算法優化SVM）［6］。本文提出了基于細菌覓食算法的SVM 參數選取方法，并將該方法用于人臉表情識別，用來提高表情識別準確率。最后與未改進SVM、GA－SVM、PSO－SVM 比較，驗證了本文提出算法的有效性。

1 支持向量機

1.1 支持向量機基本原理

支持向量機是一種有效的、廣泛應用的非線性的數據分類方法，最大特點是實現在統計學習理論上的結構風險最小。根據提取的有限的樣本信息，該方法不僅尋求在訓練樣本時得到最小誤差，而且保證在對待其它數據是也得到最小誤差，盡量獲取更好的學習泛化能力［7］。

支持向量機通過某個函數實現訓練或者待測數據的空間的升維，即將其轉換為某個空間 （維度高于原空間維度）。之后在轉換后的空間中使不同類的訓練數據之間存在最大的距離，得到最優分類面，通過該分類面對待處理數據進行分類［8］。

設線性可分樣本集為（Xi，yi），i＝1，2，…，n，X ∈Rd，yi∈｛－1，＋1｝是類別標號。

d維空間線性判別函數的一般形式為

分類面方程為

當W·X＋b≥0時，yi＝＋1；

當W·X＋b≤0時，yi＝－1；

將判別函數歸一化，然后等比例調節系數W 和b，使兩類所有樣本都能滿足式 （3）

此時分類間隔為2／ W ，這樣將求間隔最大變為求W 最小。所求的最優分類面的位置取決于支持向量即滿足＝1樣本點。

則求最優分類面問題轉化為優化問題

引入拉格朗日乘子αi≥0（i＝1，2，…，n）本優化問題轉化為對偶化問題

約束條件為

由此可得到最優分類函數為

其中，α＊為α的最大值，b＊為b的最小值。

對線性不可分情況，Vapink通過引入正的松弛影子ξi構造軟邊緣分類面，允許錯分樣本存在。于是，求取最優分類面問題轉變為在條件ξi ≥0和yi［（W·Xi）＋b］－1＋ξi≥0下最小化，即

其中，C為正常數，代表錯分樣本的懲罰力度。

引入適當的核函數K（Xi，Xj），可以實現某一非線性變換后的線性分類，目標函數變為

約束條件為

相應的最優分類函數轉化為

通常非線性變換的核函數包括：徑向基核函數 （RBF），多項式核函數，Sigmoid核函數，分別為式 （13）、式 （14）、式（15）。本文SVM 采用徑向基核函數作為核函數

1.2 參數對SVM 性能的影響

SVM 雖然能解決小樣本、非線性、高維數和局部極值點等實際問題，但是其參數參數的選擇對其性能有很大的影響，參數 （核函數參數、誤差懲罰參數C）的選取就成為亟待解決的問題。

核函數參數的作用是影響數據在高維的特征空間中分布的復雜度。由于映射函數隨核函數參數的改變而改變，導致樣本空間的維數的改變。樣本空間維數在影響此空間構造的線性分類面維數的最大值的同時，還影響線性分類面能達到的經驗誤差的最小值。本文采用RBF函數為核函數 （核函數參數是σ2），σ2增大，最優分類面的結構風險減小，但經驗風險會增大；σ2越小，則影響相反；σ2過大、過小均會降低SVM 的分類性能。所以，選擇合適的σ2才能得到最佳的SVM 性能。

誤差懲罰參數C 的作用是使在已知的數據空間中同時調節訓練過程的復雜度以及經驗風險值，從而得到更好的學習泛化能力。在確定的數據子空間中，取較小C 值，則對經驗誤差懲罰較小，訓練的復雜度小但經驗風險值偏大，稱為 “欠學習”；反之，稱為 “過學習”。當C 不小于某個值時，SVM 的復雜程度達到了所在空間的極限，經驗風險值和泛化能力變化極小。每個數據子空間都存在最優的C，使SVM 的推廣能力達到最好。

本文通過細菌覓食算法尋優，獲取應用到表情識別中SVM 各個參數的最優解，為應用在新領域的支持向量機獲得最佳參數提供一種新的方法，從而得到應用在表情識別的SVM 算法的最優性能，提高識別準確率。

2 基于細菌覓食算法的SVM 參數優化

2.1 細菌覓食算法的基本原理

隨著生物群體優化算法的發展，Passino提出了模擬大腸桿菌吞噬食物的細菌覓食算法 （bacteria foraging algorithm，BFA）。

作為一種新型的仿生類優化算法，細菌覓食算法是一種全局的隨機搜索算法。該算法主要通過模擬細菌覓食的趨向性、復制和遷移這3種操作迭代計算來求解實際問題的最優解。

2.1.1 趨向性操作

游動、旋轉是細菌在覓食行為中的兩種基本運動：旋轉是指細菌在環境差的區域中改變運動方向來尋找較優區域，游動是指細菌沿環境好的區域方向不斷前進，這兩種基本運動的目的是尋找食物豐富區域并避開有害區域。在細菌覓食優化算法中這兩種運動合稱為趨向性操作。

設S 為細菌數量，每個個體在其所處空間中占有不同位置。對應到實際應用中，所求問題的可能解可用每個個體所在的位置表示。

經過某一次趨向性操作，細菌個體i可表示為

式中：P（i，j，k，l）——細菌個體i的位置，j、k、l——該個體經歷的趨向性、復制、遷徙的次數。C（i）＞0表示細菌游動的步長，Φ（j）表示細菌旋轉產生的隨機的運動方向［9］。

2.1.2 復制操作

擇優生存是生物進化過程的規律。細菌生存一段時間后，一些尋找食物豐富區域能力差的個體會被淘汰，剩余的個體會進行繁殖來維持種群規模不變。在細菌覓食優化算法中稱之為復制操作。

在BFA 中，為了保證經過復制操作后算法的種群大小不變，本文中設被淘汰的細菌為Sr＝S／2個。將細菌按其位置的優劣排序，淘汰掉排在后面的Sr個細菌，并復制排在前面的Sr個細菌，這樣保持了細菌種群大小的不變，而且新生細菌與產生該個體的細菌具有相同的位置［10］。

2.1.3 遷移操作

當細菌生活的某些區域發生環境、食物等突然變化時，可能導致生活在這個區域的細菌部分死亡或迫使部分細菌遷移到一個新的區域。在細菌覓食優化算法中稱之為遷移操作。

設遷移操作以給定概率ped發生。如果種群中的某個細菌滿足遷移發生的條件，則這個細菌個體死亡，并在生存空間的任意位置隨機產生一個新個體替代原個體，這個新個體與被替代個體可能具有不同位置。遷移操作隨機生成新個體使算法更容易跳出局部極值并得到全局最優解，避免算法陷入局部最優解。

除了以上3個迭代操作，BFA 算法還模擬細菌群聚的特點，即細菌之間的相互影響。種群中每個個體不僅按照自己的行為搜索食物，還根據收到種群中其它細菌發出的吸引信號和排斥信號改變運動方向，使細菌之間保持安全距離。

設P（i，j，k，l）（i＝1，2，...，S）為種群中某個細菌的位置，J（i，j，k，l）為細菌i經歷j次趨向性、k次復制、l次遷徙后的覓食能力，則此時細菌之間相互的干擾程度表示為式（17）。其中，d、h、wa、wr為4個不同參數，m 為維度［11］

由于個體之間吸引與排斥的影響，個體i每一次完成趨向性行為后，其適應度值為

2.2 適應度函數

適應度函數描述了個體性能的主要指標。優化算法的設計根據適應度的大小，對個體進行優勝劣汰，達到尋優的目的。在本文的細菌覓食算法中，適應度函數與表情識別問題分類相關，將適應度函數與細菌尋找食物能力相聯系，即與表情識別結果聯系，達到尋優的效果。

本文采用分類結果的相對誤差絕對值的和作為適應度函數，如式 （19）所示，其中test為待測表情圖像分類結果，lable為其實際的歸類

2.3 基于BFA的SVM 參數優化設計

細菌覓食算法的待選參數包括：細菌個數S，單個細菌前進步長C，趨向性次數Nc，復制次數Nre，遷移次數Ned，每次向前游動的最大步數Ns，遷移概率ped以及種群細菌之間傳遞信號的影響值Jcc中的4個參數。BFA 的尋優能力和優化速度與這些參數值的選擇緊密相關。

細菌個數S、單個細菌前進步長C 控制種群的多樣性和收斂性，針對實際問題選擇合適的S、C 既能夠有較快的算法收斂速度且有效地避免算法過早收斂，又能增加算法逃離局部極值的能力；趨向次數Nc 值越大，算法的搜索更細致，但會增加算法的復雜度；反之，Nc 值越小，算法越容易陷入局部極值；合適的復制次數Nre 值使算法在復雜度較低的前提下，能避開環境較差區域而去較好區域搜索更優區域，從而提高算法的收斂速度；遷移次數Ned 也需要合適，這樣既可以使算法復雜度較低，又可以發揮遷移操作的隨機搜索作用；趨向性操作中另一個參數Ns是細菌沿某一搜索方向上游動的最大步長數，Ns 越大，細菌可以更多地根據種群中的較優解引導運動，但是也會使算法更容易陷入局部極值區域；若遷移概率ped選取適當的值，可以使算法跳出局部極值且算法不是隨機搜索；細菌之間的影響值Jcc的4個參數值大小決定算法的群聚性，也需要選取適當［12］。所有參數的選擇可以根據實際情況適當改變（如在參數經驗值條件下適當減小S、Nc、Nre，增大C 等），在基本不影響尋優的情況下減少計算量。

選取合適的細菌覓食算法參數后，利用如圖1所示的細菌覓食算法優化支持向量機參數整體流程，將其應用到表情識別系統中，可得到最優的SVM 參數，進而得到最優的識別準確率。

圖1 BFA 優化SVM 參數整體流程

3 實驗設計及結果分析

本實驗構建的人臉表情識別系統采用美國CMU 機器人研究所建立的人臉表情數據庫 （CMU AMP face expression database）進行訓練和測試。從數據庫中選取10 個人的高興、平靜、驚訝3種表情的表情圖像，將其按表情分為3類，每類10 幅，并且取每類中6 幅圖像作為訓練圖像，最后將所有圖像進行識別測試，部分表情圖像如圖2所示。本實驗利用主成分分析 （PCA）算法對圖像進行特征提取，將相對誤差的絕對值和作為適應度函數，采用BFA－SVM 算法對表情進行識別分類。BFA 優化SVM 參數的整體流程如圖1所示。

將尋優范圍設定為C ∈［95，100］，σ2∈［1，5］，運行10次，得到平均識別準確率和平均尋優時間。PCA 特征提取后所得的特征臉如圖3所示。

為了與其它應用在表情識別的改進SVM 分類算法及未改進SVM 分類算法作對比，本實驗在同樣的實驗數據、特征提取方法及適應度函數前提下，同時采用未改進SVM 分類算法［13］、GA－SVM 分類算法［5，14，15］、PSO－SVM 分類算法［6，16］對表情圖像進行識別測試，實驗結果見表1。

圖2 部分表情圖像

圖3 PCA 特征提取后的特征臉

表1 實驗結果1

改變遺傳算法、粒子群算法、細菌覓食算法參數 （步長、群體數等參數合理，使尋優循環次數、尋優范圍基本不變），運行10次，得到平均識別準確率和平均尋優時間，結果見表2。

表2 實驗結果2

從算法原理上分析，BFA 優化SVM 參數的具體操作體現出該尋優算法的優越性：趨向性操作通過在細菌位置附近旋轉、移動，并通過判斷旋轉后細菌的適應度函數值是否得到改善，來決定細菌是否要沿當前方向繼續移動，實現了算法的局部尋優能力；復制操作直接淘汰適應度較差的細菌，用適應度值較優的細菌將其取代，加快了算法的尋優速度，與GA 算法、PSO 算法相比 （GA 算法需要復雜的遺傳操作淘汰較差適應度值個體，而PSO 算法通過跟蹤兩個極值不斷更新個體實現優勝劣汰），BFA 算法需要較短的時間即可達到尋優目的；遷移操作讓細菌以一定概率遷移到搜索范圍內的任意位置，避免了算法尋優陷入局部極值。趨向、復制和遷移操作實現了BFA 算法可以快速的對SVM 參數在某個范圍內進行全局尋優。

從上述實驗結果可以看出：對不同的分類算法在不同參數下運行多次，BFA－SVM 算法的平均識別準確率約為93.3%，GA－SVM 分類算法的平均識別準確率約為85.3%，PSO－SVM 分類算法的平均識別準確率約為90.6%；未改進的SVM 算法由于參數的選取具有隨機性，當C＝99，σ2＝5時，其準確率為80.0%。上述實驗結果說明BFASVM 算法與其它應用到本實驗上的SVM 的相關算法相比，具有最高的平均識別準確率，且參數尋優時間最短。

4 結束語

表情識別是一個跨學科的前沿課題，具有很好的學術價值和應用前景。由于每個人臉型不同，且表情在面部表達的不確定性，使計算機識別表情較為復雜。傳統方法采用PCA 與SVM 算法可以識別人臉表情，但SVM 的參數對結果的影響較大，導致識別準確率較低。本實驗將細菌覓食算法 （BFA）優化的SVM 用于表情識別，提高了分類的準確率。本實驗還將BFA－SVM 算法與其它SVM 改進算法進行了比較，結果表明，BFA－SVM 算法應用在表情識別系統中有較高平均識別準確率和較短的尋優時間。為了進一步提高準確率和尋優速率，進一步優化BFA－SVM 算法，是今后研究的方向。

［1］Cohen J.Foundations of human computing：Facial expression and emotion ［J］.Lecture Notes in Computer Science，2007，4451：233－238.

［2］ZOU Guofeng，WANG Kejun，YUAN Lei，et al.New research advances in facial expression recognition ［C］／／The Proceedings of the 25th CCDC，2013：3403－3409（in Chinese）.［鄒國鋒，王科俊，原蕾，等.人臉表情識別研究新進展 ［C］／／第25界中國控制與決策會議論文集，2013：3403－3409.］

［3］Rami Alazrai，George LEE CS.Real－time emotion identification for socially intelligent robots ［C］／／ICRA，2012：4106－4111.

［4］WANG Zhiliang，MENG Xiuyan.The facial engineering science［M］.Beijing：China Machine Press：2008（in Chinese）.［王志良，孟秀艷.人臉工程學［M］.北京：機械工業出版社：2008.］

［5］ZHU Yani，WANG Zhe.Facial expression recognition based on GA－SVM ［C］／／The Proceedings of CIAC，2009：1495－1990（in Chinese）.［朱婭妮，王喆.基于遺傳算法進化的SVM 人臉表情識別 ［C］／／中國智能自動化會議論文集，2009：1495－1990.］

［6］TANG MIN，CHEN FENG.Facial expression recognition and its application based on curvelet transform and PSO－SVM ［J］.Optik，2013，124 （22）：5041－5046.

［7］DING Shifei，QI Bingjuan，TAN Hongyan.An overview on theory and algorithm of support vector machines ［J］.Journal of University of Electronic Science and Technology of China，2011，40 （1）：2－10 （in Chinese）. ［丁世飛，齊丙娟，譚紅艷.支持向量機理論與算法研究綜述 ［J］.電子科技大學學報，2011，40 （1）：2－10.］

［8］Zhu Wenxin，ZHONG Ping.A new one－class SVM based on hidden information ［J］.Knowledge－Based Systems，2014，60：35－43.

［9］Dasgupta S，Biswas A，Das S，et al.A micro－bacterial foraging algorithm for high－dimensional optimization ［C］／／IEEE Congress on Evolutionary Computation，2009：785－792.

［10］Rutuparna Panda，Manoj Kumar Naik，Panigrahi BK.Face recognition using bacterial foraging strategy ［J］.Swarm and Evolutionary Computation，2011，1 （3）：138－146.

［11］Das S，Biswas A，Dasgupta S，et al.Bacterial foraging optimization algorithm：Theoretical foundations，analysis，and applications［J］.Foundations of Computer Intel，2009，3：23－55.

［12］ZHOU Yalan.Research and application on bacteria foraging optimization algorithm ［J］.Computer Engineer and Applications，2010，46 （20）：16－21 （in Chinese）.［周雅蘭.細菌覓食優化算法的研究與應用 ［J］.計算機工程與應用，2010，46 （20）：16－21.］

［13］Faruqe Omar，MD AL Mehedi Hasan.Face recognition using PCA SVM ［C］／／3rd International Conference on Anti－counterfeiting，Security and in Communication.Hong Kong：IEEE，2009：97－101.

［14］LIAN Ke，HUANG Jianguo，WANG Houjun，et al.Study on a GA based SVM decision tree multi classification strategy［J］.Chinese Journal of Electronics，2008，36 （8）：1502－1507 （in Chinese）.［連可，黃建國，王厚軍，等.一種基于遺傳算法的SVM 決策樹多分類策略研究 ［J］.電子學報，2008，36 （8）：1502－1507.］

［15］Stanislaw Osowski，robert Sirosc，Tomasz Markiewicz，et al.Application of support vector machine and genetic algorithm for improved blood cell recognition ［J］.IEEE Transactions on Instrumentation and Measurement，2009，58 （7）：2159－2168.

［16］Valuvanthorm S，Nitsuwat S，HUANG Maolin.Multi－feature face recognition based on PSO－SVM ［C］／／10th Intertional Conference on ICT ＆ Knowledge Engineering.Bangkok：IEEE，2012：140－145.