改進的禁忌搜索算法在肌電信號情感識別中的應用

邱 紅，劉光遠＋，賴祥偉

（1.西南大學 電子信息工程學院，重慶400715；2.西南大學 計算機與信息科學學院，重慶400715）

0 引 言

近年來在情感識別技術方面取得了很好的成果，如：Reza R Derakhshani等人采用測量眨眼對恐懼情感的識別，得到了較好的識別率［1］。Chung－Hsien Wu等人基于聲學信息 （AP）和語義標簽 （SLs）的情感識別，去除個別個性品質的影響，識別率可以達到85.79%［2］。Milan Gnjatovic等人研究了采用人機交互會話系統去期望發生情感反應的范圍［3］。Bjorn Schuller等人對采用語音識別情感出現的不一致性進行研究和提出策略［4］。George E等人提出多級支持向量機對心率 （HR），皮膚電反應 （GSR），皮膚溫度（ST）進行分類，并對情感進行識別，得到了很高的識別率［5］。Petrantonakis等人提出一種新的算法結合4種分類方法對腦電信號進行6種情感的識別，最高辨識率達到85.17%［6］。其中一個分支是基于生理信號對情感狀態進行識別，通過特殊的儀器檢測生理信號并識別出情感。肌電信號 （electromyography，EMG），它在情感識別中扮演了重要角色，將EMG信號用于情感狀態識別具有重要的意義，國際上已對其進行了研究。Kim J［7］以音樂誘發高興、悲傷、憤怒和愉悅4種情感，建立了3個被試的90組樣本庫，測試了肌電、皮膚電導、心電和呼吸4種生理信號。

針對肌電信號數據提取的126個原始特征中相關特征之間不含更多的分類信息的缺點，采用相關性分析刪除相關特征。禁忌搜索算法可以接受劣解，具有良好的全局收斂性，所以進一步的特征選擇采用禁忌搜索算法，但基本的禁忌搜索算法對初始解和鄰域結構有較大的依賴性［8］。為了彌補其不足，提出了一種改進的禁忌搜索算法。實驗結果表明，采用相關性分析和改進的禁忌搜索算法結合能以較少的特征子集個數獲得較好的識別率。

1 數據采集和特征提取

采用電影片段激發被試高興、憤怒、厭惡、恐懼、悲傷、驚奇6種情感，并用Biopac MP150多通道生理信號記錄儀采集被試肌電信號，初始采樣頻率設置為1000Hz。參照文獻 ［9］的特征提取方法，從肌電信號的樣本集中共提取了126個原始特征。為減少因個體差異對情感分類帶來的不利影響，將被試的各種情感的特征取值減去其平靜狀態下的特征取值，并進行歸一化［10］。

2 肌電信號的特征選擇

特征選擇是指從原始特征中選擇分類能力最強的特征組合。在用肌電信號進行情感識別時采用的是二分類情感識別法，目標情感是單獨的一種情感，非目標情感是其它5種情感的集合。識別能力可以用擊中率 （TPR）和虛報率（FPR）來表示，它們分別定義為

在ROC平面中，橫坐標為FPR，縱坐標為TPR，對角線上的系統為無用系統。系統性能較好區域為TPR＞FPR的區域，該區域離對角線的距離越遠越好；系統性能較差的區域為TPR＜FPR的區域，該區域離對角線的距離越遠越差［11］。

將實驗測試得到的肌電信號各情感樣本集隨機平均分為3部分：第1部分用于對分類器的訓練；第2部分用于對分類器的測試，第3部分用于驗證選擇特征的有效性。

2.1 序列后向算法

序列后向算法 （SBS）是一種自上而下的方法。其基本思想是在運行之初假定整個特征集合就是所需要的優化特征集，每步運行過程中刪除一個對準則函數無貢獻或貢獻最小的特征［12］。

2.2 相關性分析

原始特征數目較大且含有相關的特征，這樣不僅會降低機器運行速度且多次獨立運行算法進行特征選擇會得到多種不同的特征組合，不利于情感識別系統的建立。文獻［13］中引用定理與定義給予證明：原始特征集的分類能力不因刪除或增加相關性特征而減弱的理論。所以采用相關分析方法是可以的。該方法用式 （3）計算出126個原始特征兩兩特征的相關系數

式中：rxy——線性相關系數；X，Y——其中的兩個特征；xi——X第i個樣本值；yi——Y第i個樣本值；——X均值；——Y均值；n——特征集的樣本個數。

得到一個相關系數矩陣后，采用單獨最優特征組合排序方法對126個特征對分類能力貢獻大小進行排序，將rxy＞e的兩個特征中刪除一個排序相對靠后的特征，但當遇到兩個特征中已有一個特征被刪除時，要保留與被刪除特征相關的哪個特征。

具體的刪除特征步驟如下：

步驟1 刪除原始特征集Mm×n（m是樣本個數，n是特征維數為126）中畸形的樣本，并且將特征矩陣歸一化，得到特征矩陣Ml×n（l為刪除樣本后的樣本個數）。

步驟2 采用單獨最優特征組合排序方法對特征矩陣Ml×n進行排序。

步驟3 計算出經過步驟1處理后的126個特征之間的線性相關系數矩陣。

步驟4 假定一個閥值e，如果rxy＞e，按步驟2所排除的順序，比較x和y特征，刪除排在后面的那個特征。然后輸出一個特征矩陣為Ml×p（p為經過刪除后的特征維數）。

2.3 改進的禁忌搜索算法

禁忌搜索 （tabu search，TS）是對人類記憶過程的一種模擬，禁忌記憶的一些局部最優解，接受部分較差解，從而可以跳出局部搜索達到全局搜索的目的［14］。其最重要的思想是采用了禁忌技術，其最重要的思想是采用了禁忌技術，但為了避免遺失優良解，禁忌搜索同時采用 “特赦準則”策略，該策略使搜索可以無視禁忌技術［15］。

該算法與傳統的優化算法相比具有很好的爬山能力且區域集中搜索與全局分散搜索能較好平衡，為克服基本算法的不足，提出了一種改進的禁忌搜索算法應用于肌電信號的情感識別。該算法將搜索空間分解分為多個子空間，利用序列后向算法在每個子空間得到的解作為禁忌搜索的初始解，以Fisher分類器的正確率作為評判標準，從每個初始解出發在對應的子空間開始搜索，得到每個子空間的最優特征子集，最后對這些解進行評價，找出整個空間的最優特征子集。

具體改進禁忌搜索算法步驟如下：

步驟1 將特征向量用一個0／1串位表示，并把運行序列后向算法的結果放在表L中，j表示L的第j行，j＝1；

步驟2 初始化：禁忌表T＝Φ，初始解x（j）＝L（j，：），設置禁忌長度，最優解Bestsofar＝x（j），局部最優解cand＝x （j），適應度函數f（x（j））＝sqrt（ratA2＋ratB2），ratA和ratB分別為fisher計算出的目標與非目標情感的正確識別率；

步驟3 判斷是否滿足最大迭代步數的停止準則，如滿足則終止計算，并把Bestsofar放在表S的第j行，然后轉步驟6；

步驟4 生成候選解集V （cand），其生成方式是別將cand的第i位cand（i）值變為1－cand（i），從第i位的下一位開始到第i位的上一位，遇到值等于1－cand（i）的p位，將其值變為1－cand（p）后結束，將鄰域集中被禁忌了的解，隨機產生與這個解特征維數相等的解代替后所產生的解集。計算出每個候選解的f，得到F（V （cand））集，找出Max（F）所對應的候選解Qmax，cand＝Qmax，如f（cand）＞f（Bestsofar）則Bestsofar＝cand，將cand放入禁忌表中；

步驟5 用特赦準則提前釋放禁忌表中迭代10次均好于當前局部最優解的解，轉步驟3；

步驟6j＝j＋1；如果j不等于特征總維數轉步驟2；

步驟7 選出S表中Max（f）對應的解作為最優解（Y），輸出結果。

3 實驗結果分析

對126個EMG信號的原始特征運用改進的禁忌搜索算法進行特征選擇，并獨立運行程序10次，得到10個最優解，并對每個最優解進行驗證，得到結果如表1、圖1所示。

表1 以原始特征運行10次改進的TS算法的結果

圖1 改進的TS算法特征選擇的情感識別系統的ROC平面

采用相關系數大于0.92的相關性分析對特征降維后，運用基本的禁忌搜索算法進行特征選擇，并獨立運行程序10次，得到10個最優解，并對每個最優解進行驗證，得到結果如表2、圖2所示。

采用相關系數大于0.92的相關性分析對特征降維后，運用改進的禁忌搜索算法進行特征選擇，并獨立運行程序10次，得到10個最優解，并對每個最優解進行驗證，得到結果如表3、圖3所示。

圖2 相關性和基本TS算法結合進行特征選擇的情感識別系統的ROC平面

如表1所示，對126個EMG原始特征運用改進的禁忌搜索算法選擇出的最優特征子集驗證高興、驚奇、厭惡、悲傷、憤怒、恐懼時，最優特征子集特征維數分別為21，12，18，13，21和22。如表3所示，用相關性分析對原始特征降維后，運用改進的禁忌搜索算法選擇出的最優特征子集，最優特征子集特征個數分別為7，4，6，4，7和7。從表1和表2對比可看出用相關性分析對原始特征降維后，禁忌搜索算法的搜索空間降低從而減少了特征選擇時間，在保持較好的識別率的情況下選出的最優特征維數明顯降低，且獨立運行10次所得到的最優特征組合也更穩定，如高興每次選擇的最優特征組合相同，更有利于情感識別系統的建立。所以相關性分析運用于EMG信號的情感識別的特征選擇是可行的。

表2 相關性分析去除相關性較強的特征后獨立運行10次適應度函數為TS算法的結果

表3 相關性分析去除相關性較強的特征后運行10次改進的TS算法的結果

圖3 相關性分析和改進的TS算法結合進行特征選擇的情感識別系統的ROC平面

如表2所示，用相關性分析去除相關性較強的特征后，運用基本的禁忌搜索算法選擇出的最優特征子集，最優特征子集特征維數分別為15，14，10，8，7和19。從表2和表3結果對比可看出，用改進的禁忌搜索算法能以較少的特征獲得相近的識別率，表明改進的禁忌搜索算法比基本的禁忌搜索算法更優。

從ROC圖中各情感的位置離對角線的距離可知肌電信號情感識別系統對高興的識別效果最好。文獻 ［16］基于最大最小蟻群算法對脈搏進行情感識別；文獻 ［17］基于粒子群算法對皮膚電進行情感識別；將以上文獻中的結果與本文的結果對比，可看出肌電對高興的識別效果比采用其它生理信號對高興情感的識別效果更好，所以在建立的情感識別模型中可以使用肌電信號識別高興情感。

4 結束語

提出了一種基于相關性分析和改進的禁忌搜索算法的特征選擇方法，該方法利用相關性分析去除相關性較強的特征后，使用改進的禁忌搜索算法與Fisher分類器結合進行特征選擇。實驗結果表明，該特征選擇方法用于肌電信號的情感識別，獲得了較好的識別率。在分析了基本的禁忌搜索算法和改進的禁忌搜索算法選出的特征子集個數和識別率后，能夠看出改進的禁忌搜索算法較優。在進一步研究中，可以采用非線性相關分析方法和采用特征選擇算法結合不同的分類器進行肌電信號的情感識別。

［1］Derakhshani RR，Lovelace CT.An ensemble method for classifying startle eye blink modulation from high－speed video records［J］.IEEE Transactions on Affective Computing，2011，2 （1）：50－63.

［2］WU Chung－hsien，LIANG Wei－Bin.Emotion recognition of affective speech based on multiple classifiers using acoustic－prosodic information and semantic labels ［J］.IEEE Transactions on Affective Computing，2011，2 （1）：10－21.

［3］ Milan Gnjatovic.Inducing genuine emotions in simulated speech－based human－machine interaction：The NIMITEK corpus［J］.IEEE Transactions on Affective Computing，2010，1（2）：132－144.

［4］Bjorn Schuller.Cross－corpus acoustic emotion recognition：Variances and strategies ［J］.IEEE Transactions on Affective Computing，2010，1 （2）：119－131.

［5］George E S.Support vector machines to define and detect agitation transition ［J］.IEEE Transactions on Affective Computing，2010，1 （2）：98－108.

［6］Panagiotis CP.Emotion recognition from brain signals using hybrid adaptive filtering and higher order crossings analysis ［J］.IEEE Transactions on Affective Computing，2010，1 （2）：81－97.

［7］KIM J.Emotion recognition based on physiological changes in music listening ［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2008，30 （12）：2067－2083.

［8］WANG Dingwei.Intelligent optimization methods［M］.Beijing：Higher Education Publishing，2006：82－94 （in Chinese）.［汪定偉.智能優化方法 ［M］.北京：高等教育出版社，2006：82－94.］

［9］CHENG Ying.The research of EMG signal in emotion recognition based on TS and SBS algorithm ［C］.The 3rd International Conference on Information Sciences and Interaction Sciences，2010：363－366.

［10］WEN Wanhui.Foundation of emotion physical response sample and data correlation analysis［J］.China Science F Information Science，2010，41 （1）：77－89 （in Chinese）. ［溫萬惠.情感生理反應樣本庫的建立與數據相關性分析 ［J］.中國科學F輯信息科學，2010，41 （1）：77－89.］

［11］Bradley A P.The use of the area under the ROC curve in the evaluation of machine learning algorithms［J］.Pattern Recognition Society，1997，30 （2）：1145－1159.

［12］MAO Yong.A survey for study of feature selection algorithms［J］.Pattern Recognition and Artificial Intelligence，2007，20（2）：212－217 （in Chinese）.［毛勇.特征選擇算法研究綜述［J］.模式識別與人工智能，2007，20 （2）：212－217.］

［13］JI Xiaojun.Application of the correlation analysis in feature selection ［J］.Jouranal of Test and Measurement Technology，2001，15 （1）：15－18 （in Chinese）.［吉小軍.相關性分析在特征選擇中的應用 ［J］.華北工學院測試技術學報，2001，15 （1）：15－18.］

［14］HU Yongliang.Research on tabu search applied in off－line MPLS layout design ［J］.Computer Engineering and Design，2006，27 （3）：387－389 （in Chinese）.［胡永良.禁忌搜索在MPLS離線型規劃設計中的應用研究 ［J］.計算機工程與設計，2006，27 （3）：387－389.］

［15］WU Liangjie.Research on generalized assignment based on ant coloney algorithm with tabu search［J］.Computer Engineering and Design，2009，30 （15）：3591－3697 （in Chinese）.［吳良杰.基于禁忌搜索和蟻群算法的廣義分配問題研究［J］.計算機工程與設計，2009，30 （15）：3591－3697.］

［16］ZHANG Huiling.Research of emotion recognition based on pulse signal［C］.The 3rd International Conference on Advanced Computer Theory and Engineering，2010：506－509.

［17］WU Guanghua.The analysis of affective recognition from GSR based on PSO ［C］.International Symposium on Intelligence Information Processing and Trusted Computing，2010：60－64.