改进的禁忌搜索算法在肌电信号情感识别中的应用

邱 红，刘光远＋，赖祥伟

（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.