基于回溯搜索算法的导联选择脑机接口研究

戴圣法，魏庆国，魏中海

（南昌大学 信息工程学院，江西 南昌　330031）

基于回溯搜索算法的导联选择脑机接口研究

戴圣法，魏庆国，魏中海

（南昌大学 信息工程学院，江西 南昌330031）

在脑机接口（BCI）中，传统的共空域模式（CSP）算法在提取特征信号与事件相关去同步/同步（ERD/ERS）的信息上得到了很好的效果。但是CSP算法受限于电极导联数、EEG信号的时间段和频带等因素，如电极导联数的增加，CSP算法容易过拟合，数据记录容易混乱，使得运算变得复杂，增加运算时间，降低数据分类正确率。所以，CSP算法存在局限性。使用回溯搜索优化算法（BSA）能够为CSP算法自动挑选出一组导联数组子集，并且以分类错误率作为BSA算法的目标函数进行实验。实验采用两类实验数据（第三、四届国际BCI竞赛数据集）进行交叉验证分类实验。实验结果表明，两类数据的导联数目大幅度减少，分类正确率有所提高。

脑机接口；共空域模式；回溯搜索优化算法；最优导联选择

0　引　言

脑机接口（Brain Computer Interface，BCI）是一种直接利用脑信号连接和控制外界设备，不依靠人体神经和肌肉的通信系统［1］。通过BCI系统，将人脑的想法、思维转化为控制外部设备的指令，可以帮助那些患有肌肉萎缩性侧索硬化、脑干中风等疾病的人实现与外界交流［2］。

当人想象某个精神任务或者执行某个肢体运动时，大脑皮层的某个区域中脑电信号会发生变化，这类现象伴随着脑电信号能量的减小或增加。Pfurtscheller将脑电信号能量的减小称为事件相关去同步（Event-related Desynchronization，ERD），而能量的增加称为事件相关同步（Event-related Synchronization，ERS）［3-4］。在EEG节律信号中mu节律和beta节律信号是ERD/ERS现象有关的两种固有频率信号，mu节律信号的频率范围一般为8～12 Hz，beta节律信号［5］为18～26 Hz。

传统的共空域模式（Common Spatial Pattern，CSP），在ERD/ERS相关的特征提取上是很有效的算法。由于ERD/ERS信号发生在特定的脑区域，而采集信号的导联分布于整个大脑区域，所以导联通道中存在许多无关的通道。因此，CSP的性能会受到限制［6］。

本文采用回溯搜索优化算法（Backtracking Search Optimization Algorithm，BSA）与CSP算法相结合的方法。在使用CSP算法之前尽可能地挑出有用的脑电信号的导联子集。实验中采用第三届国际脑机接口竞赛数据集（BCI Competition III Dataset Iva）［7］和第四届国际脑机接口竞赛数据集（BCI Competition IV Dataset IIa）［8］进行分类实验。实验结果表明该方法比单纯使用CSP算法的分类识别率更高。

1　方　法

在脑电信号处理的实验中，采用切比雪夫I型8～30 Hz（包含mu节律和beta节律）的带宽IIR带通滤波器［9］对多通道EEG信号进行滤波，然后用BSA算法选择最优导联，对选出的导联使用CSP算法进行特征提取，最后线性判别分析（Linear Discriminant Analysis，LDA）分类器［10］对特征信号进行分类。并用10×5倍交叉验证之后的分类错误率作为BSA的目标函数评判选出的导联数集的优劣。BSA与CSP结合的导联选择算法流程如图1所示。

图1　BSA与CSP结合的导联选择算法流程

1.1共空域模式算法

CSP算法基于两个实对称矩阵的联合对角化，并进行空间-时间源建模［11-12］。把原始的EEG信号分解为空域模式，通过空域模式使两类信号的差别达到最大化，从而提取与任务相关的信号分量。具体分为如下三个步骤：

（1）求解脑电信号的协方差矩阵，建立空间-时间源模型。实验时，受试者被要求执行两种不同的想象任务a和b。想象任务a和b诱发的多通道EEG信号为空间-时间信号矩阵Xa和Xb，并按式（1）建模：

式中：Sa和Sb分别是与任务a和b有关的源分量，Ca和Cb是Sa和Sb的空域模式；Sc是共同条件下的源分量，Cc是Sc的空域模式。

设EEG信号记录的通道数为N，每个导联信号的采样点数为T，矩阵Xa和Xb的维数都是N×T。任务a和b对应的脑电信号的空间协方差矩阵为：

式中：T表示转置运算；trace（X）是求矩阵X的主对角元素之和；Ra和Rb都是N×N的矩阵。

（2）协方差联合对角化。对两个协方差矩阵之和R进行特征分解：

式中：U0是特征向量矩阵；Λ是特征值矩阵，矩阵R与Λ的维数都是N×N。在以下的讨论中，如无特别说明，都假设特征值不为零。则白化变换的矩阵P可用式（4）表示：

对Ra和Rb分别进行白化变换后得：

Sa和Sb具有如下两个重要性质：

① Sa和Sb具有共同的特征向量：

② Sa和Sb对应的特征值之和为I：

式中：Λa和 Λb分别是Sa和Sb的特征值矩阵；I为单位矩阵。设Λa的对角元素以降序排列，任务a的初始几个空间因子占有的方差被最大化，那么任务b相应的方差被最小化。这两类任务可分别由 Λa和 Λb中最大的m个特征值对应的特征向量表示，即Uam和Ubm表示。由于特征值矩阵对角元素是递减排列的，所以在特征矩阵中的第一个和最后一个特征向量是识别两类任务的最佳特征向量。

（3）构造空域滤波器。用Uam构建空域滤波器Fa，用Ubm构建空域滤波器Fb，其中m≪N，Fa和Fb如下所示：

然后将记录的EEG数据分别通过构建好的两个空域滤波器进行空域滤波，得到这两类信号的源信号：

式中：F的行向量表征的是滤波器的系数；F-1的列向量表征的是共空域模式矩阵，亦被称为时不变脑电信号源分布向量。当F-1投影到脑部时，可直观地显示脑神经活动的分布情况。对于类别未知的测试集数据，可以通过由训练集数据训练好的分类器实现数据类别的分类。相应的特征可在源信号的基础上构造为：

则特征向量可表示为 f=［fa，fb］，式（10）中的对数运算是为了让特征向量 fa和 fb中的元素更接近于正态分布。关于CSP算法的计算步骤和详细描述可参阅文献［13］。

1.2回溯搜索优化算法

BSA是2013年由Cicicioglu提出的一种进化算法［14］。该算法通过自身产生实验种群，控制搜索方向和搜索边界。在整个过程中只有一个控制参数，因此该算法相比其他进化算法操作简单。而且该算法同其他进化算法的步骤类似，分别为种群初始化、历史种群选择、种群突变、种群交叉和最后种群输出。

（1）种群初始化

实验中采用随机产生种群的方法进行初始化，即：

式中：P为种群；i∈［1，2，…，N］，j∈［1，2，…，D］，N是种群大小，D是问题维数；low和up分别为搜索区间的下限和上限；U是随机均匀分布。Pi是种群P中的目标个体。

（2）历史种群选择

初始化的历史种群定义如下：

BSA算法进行每一次迭代运算时，当历史种群a小于随机新种群b时 old P=P，a，d～U（lowj，upj），即更新历史种群。

（3）种群突变

通过式（13）产生突变种群的最初形式为：

式中：F为控制搜索方向矩阵（old P-P）幅度的参数，F=3·rndn，rndn～N（0，1），N是正态分布。

（4）种群交叉

在BSA算法种群交叉过程中，产生实验种群T的最后形式。在实验种群的初始值不断的突变中，适应于优化的实验个体用来进化目标种群个体。种群交叉过程分为两个步骤：

①计算一个二进制维数为N×D的map矩阵，map矩阵的初始值为［0］N×D，通过利用种群P的相关个体操纵实验种群 T的个体。当 mapi，j=1，i∈［1，2，…，N］，j∈［1，2，…，D］时，Ti，j=Pi，j，实现了实验种群T个体的更新。

②通过式（14）进行交叉：

式中：rndn～N（0，1），N为正态分布；mixrate为控制种群个体元素的数目参数，mixrate=1；“┌┐”是上限取整符号；randi（D）为从［0，D］中随机取一个整数；c，d～U（0，1），U（0，1）表示在0～1均匀分布；u为随机排序，且 u∈［1，2，…，D］的整数向量。

BSA算法通过mixrate控制新种群T个体中元素的个数，同时利用和randi（D）进行实验突变和突变结束。当c＜d时，mapi为多个具有随机位置的向量；反之，mapi为仅有为0的向量。在交叉过程之后产生的种群中，超出被允许的搜索空间范围的部分个体是突变策略的结果。按照式（11）产生新的种群。

（5）最后种群输出

通过贪婪选择机制，相比对应初始种群P中有选择适应度值（目标值）较好的种群个体，种群进行更新。当种群P中的个体比全局最小值有更好的适应值时，记录和输出当前最优种群的个体元素，同时更新初始种群，完成一次迭代。重复上述过程，直至到最大迭代次数，最后输出全局最小值。

1.3基于BSA的导联选择方法

原始EEG信号通过8～30 Hz带宽带通滤波器进行滤波，然后使用CSP算法对信号进行特征提取。由于CSP的性能与导联关系密切，导联的选择是一个关键步骤。在BSA算法中设置两个参数为：下限 low=［0，0，…，0］1×N，上限up=［1，1，…，1］1×N。这是一个N维的电极优化选择向量，向量每一个分量代表一个导联。设其中的一个分量为ci，i∈［1，2，…，N］，那么ci～ U（0，1）。另设一串二进制编码为C1×N，满足Ci=［ci］，i∈［1，2，…，N］。其中U（0，1）表示在0～1均匀分布，“［］”为取高斯整。同时设置种群大小 N=50，问题维数D=2。按C中的编码抽取导联，数字编号为1的导联挑出，数字编号为0的导联舍弃。BSA算法在进化中不断地产生随机数组合，挑选出不同的导联子集。整个过程以分类错误率作为评判准则，当迭代次数达到设定的迭代次数时，BSA算法就会停止，并且输出全局最小值，即分类错误率最小，同时输出对应的最优导联子集。

2　实验结果及数据分析

2.1实验数据的预处理

本文采用的数据是第三届国际竞赛脑机接口数据集（BCI competition III dataset IVa）和第四届国际竞赛脑机接口数据集（BCI competition IV dataset IIa）。

第三届国际竞赛脑机接口数据集是由5个受试者（Aa，Al，Av，Aw，Ay）进行BCI运动想像实验所得到的数据集。在实验中受试者分别执行想象右手和脚运动两种想象任务。EEG信号由118个电极记录，电极分布如图2（a）所示。每个受试者进行280次实验，两种想象任务实验的次数相同，各为140次。采集的实验数据经过放大后再用0.05～200 Hz的带通滤波器滤波，且数据采样率为1 kHz。在本实验中，对原始记录的EEG数据进行下采样，下采样率为100 Hz。在时域滤波之前，对原始连续的实验数据截断成单次实验数据。

第四届国际竞赛脑机接口数据集是由9个受试者（A1～A9）进行BCI运动想象实验所得到的数据集。在实验中受试者分别执行想象左手、右手、脚和舌头四种想象任务。EEG信号由22个电极记录，电极的分布如图2（b）所示。

图2　EEG信号电极分布图

该数据集包含两组数据（T session，E session），由两个不同的时间段完成。每组实验分为6个时间段进行，每个时间段受试者进行了48次运动想象实验，其中每类实验次数为12，一组实验共包括6×48=288次单次运动想象实验。电极记录的EEG信号都要经过250 Hz的采样及0.5～100 Hz的低通滤波，经过放大后保存。在实验过程中，除了记录EEG信号的22个电极外，还有三个单极性的电极用来记录眼电EOG信号。与EEG信号一样，EOG信号也要经过放大处理、采样（采样率为250 Hz）和0.5～100 Hz的带通滤波。在本实验中先将数据进行8～30 Hz的宽带滤波，按时间段为2 s（2.5～4.5 s），采样率为250 Hz截取数，从四类数据中抽取左手和右手两类数据进行实验。

2.2交叉验证分类结果

为了能够合理的得到分类结果，在实验中采用10× 5倍交叉验证。10× 5倍交叉验证就是将一个受试者的数据集随机排列10次，每一次随机排列的数据被分为5个相等的部分；其中一个部分用于测试，而其余4个部分用于训练分类器。这个交叉验证步骤共有50次分类测试，求50个测试结果的平均值。在算法性能的评价上，采用两种方法进行实验，分类结果进行对比，即：全导联的CSP算法提取特征，其流程如图3所示；采用BSA导联优化与CSP相结合的算法提取特征，其流程如图1所示。

图3　CSP算法流程

BSA是一种基于种群的进化遗传算法。在实验中对种群进化迭代次数的选择做了进一步实验。改变不同的迭代次数并观察实验结果的变化。设置迭代次数为2，5，10，20，30，40，50，60，70。

5个受试者的分类正确率与迭代次数的关系如图4所示。随着迭代次数增加，分类正确率缓慢增长。当迭代次数为60时，分类效果最好，最终设置迭代次数为60。9个受试者的平均分类正确率与迭代次数的关系如图4所示。考虑到迭代次数越多，运算时间越长，最终两个时间段的数据选择设置迭代次数为40，此时分类效果较好。

图4　BSA导联选择5个受试者与9个受试者平均分类正确率与迭代次数的关系

表1表示在迭代次数为60时，5个受试者采用BSA最优导联及全部导联的分类正确率及方差。比较两种方法的结果可以得出，5个受试者使用BSA进行导联选择的平均分类正确率比使用全部118导联要高出5%，尤其受试者Aa提升了10%，效果非常明显。而且，5个受试者的导联数目也减少了一半左右，数目减少十分突出。

表1　五个受试者采用BSA最优导联及全部导联的分类正确率（%）及方差

表2表示在迭代次数为40时，9个受试者采用BSA最优导联及全部导联的分类正确率及方差。比较两种方法的结果可以得出，9个受试者的平均分类正确率分别提高了5%（T session）和8%（E session）。同样，9个受试者的导联数总体上都减少了，甚至部分受试者的导联数减少了一半。

表1和表2中的数据表明，BSA算法对导联的选择和优化十分有效，对基于运动想象的两分类BCI系统有一个显著的提升，具有重要意义。

表2　九个受试者采用BSA最优导联及使用全部导联的分类正确率（%）及方差

3　结　语

在BCI研究中，传统的CSP算法对两种不同的运动想象任务的判别，得到了比较好的结果，但是在实验中不同的受试者，其最佳的导联分布，滤波频带和数据时间段也不相同。而基于传统CSP算法的BCI系统中采用固定的导联、频带和时间段，所以传统CSP算法存在局限性。本文中，在应用CSP对多通道EEG信号提取特征之前，先使用BSA算法自动地选择恰当的导联，然后进行交叉验证实验。实验结果表明，这个方法是十分有效的。

设计一个实际应用的运动想象BCI系统，导联通道数目应该尽可能小，最好的做法是选择最优导联子集代替整个导联集。在本文中，遗传优化算法BSA应用于两个数据集，即第三届国际竞赛脑机接口数据集和第四届国际竞赛脑机接口数据集。实验结果表明，BSA可以选择导联数量较少，并保持分类精度提高。CSP的性能还受到其他因素影响，如频带和时间窗长度。因此，研究一种能同时考虑多个因素的方法是未来的趋势。

［1］WOLPAW J R，BIRBAUMRE N，MCFARLAND D J，et al. Brain-computer interfaces for communication and control［J］. Clinical neurophysiology，2002，113（6）：767-791.

［2］NICOLAS-ALONSO L F，GOMEZ-GIL J.Brain computer interfaces，a review［J］.Sensors，2012，12（2）：1211-1219.

［3］TORO C，DEUSCHL G，THATCHER R，et al.Event-related desynchronization and movement-related cortical potentials on the ECoG and EEG［J］.Electroencephalography and clinicalneurophysiology/evokedpotentialssection，1994，93（5）：380-389.

［4］BABILONI C，CARDUCCI F，CINCOTTI F，et al. Human movement-related potentials vs desynchronization of EEG alpha rhythm：a high-resolution EEG study［J］.Neuroimage，1999，10（6）：658-665.

［5］HUANG S J，WU X M.Feature extraction of electroencephalogram for imagery movement based on Mu/ Beta rhythm［J］.Journal of clinical rehabilitative tissue engineering research，2010，43（14）：8061-8064.

［6］NOVI Q，GUAN C，DAT T H，et al.Sub-band common spatial pattern（SBCSP）for brain-computer interface［C］//Proceedings of 2007 3rd International IEEE/ EMBSConferenceonNeuralEngineering.［S.l.］：IEEE，2007：204-207.

［7］BLANKERTZ B.BCI competitionⅢ webpage［EB/OL］.［2005-11-03］.http：//www.bbci.de/competition/iii.

［8］BBCI.BCI competition IV［EB/OL］.［2011-07-03］.http：//www. bbci.de/competition/iv/.

［9］DORNHEGE G，BLANKERTZ B，KRAULEDAT M，et al. Combined optimization of spatial and temporal filters for improving brain-computer interfacing［J］.IEEE transactions on biomedical engineering，2006，53（11）：2274-2281.

［10］GARRETT D，PETERSON D A，WANDERSON C.Comparison of linear，nonlinear，and feature selection methods for EEG signal classification［J］.IEEE transaction on neural systems and rehabilitation engineering，2003，11（2）：141-144.

［11］WANG Y，BERG P，SCHERG M.Common spatial subspace decomposition applied to analysis of brain responses under multiple task conditions：a simulation study［J］.Clinical neurophysiology，1999，110（4）：604-614.

［12］SAMEK W，VIDAURRE C，MÜLLER K R，et al.Stationary common spatial patterns for brain-computer interfacing［J］. Journal of neural engineering，2012，9（2）：13-15.

［13］MÜLLER-GERKING J，PFURTSCHELLER G，FLYVBJERG H.Designing optimal spatial filters for single-trial EEG classification in a movement task［J］.Clinical neurophysiology，1999，110（5）：787-798.

［14］CIVICIOGLU P.Backtracking search optimization algorithm for numerical optimization problems［J］.Applied mathematics and computation，2013，219（15）：8121-8144.

Study on brain-computer interface with lead selection based on backtracking search optimization algorithm

DAI Shengfa，WEI Qingguo，WEI Zhonghai
（College of Information Engineering，Nanchang University，Nanchang 330031，China）

In brain-computer interface（BCI），the traditional common spatial pattern（CSP）algorithm has a good effect on characteristic signal extraction and event-related desynchronization/event-related synchronization（ERD/ERS）information.The CSP algorithm is easily limited by electrode lead quantity，time period and frequency band of EEG signal，such as the increasing of electrode lead quantity，easy overfitting of CSP algorithm and easy chaos of data record，which can make the operation complex，increase the operation time and reduce the accuracy of data classification.Therefore，the CSP algorithm have a limitation. The backtracking search optimization algorithm（BSA）proposed in this paper can automatically select a subset of lead array for CSP algorithm，and take the classification error rate as the objective function of BSA algorithm to test.The two datasets from the datasets of the Third，Fourth International BCI Competitions are adopted in the experiment to perform the classification experiment of cross validation.The experimental results show that the lead quantity of the two datasets are dramatically reduced，and the classification accuracy is improved.

brain-computer interface；common spatial pattern；backtracking search optimization algorithm；optimal lead selection

TN911-34；TP301

A

1004-373X（2016）13-0010-05

10.16652/j.issn.1004-373x.2016.13.003

2015-09-28

国家自然科学基金项目（61365013）；江西省自然科学基金项目（2009GZS0073）

戴圣法（1988—），男，江西南昌人，硕士研究生。主要研究方向为通信与信息系统。

魏庆国（1963—），男，江西南昌人，教授，博士。主要研究方向为信号处理、模式识别、机器学习、脑机接口。

魏中海（1988—），男，江西南昌人，硕士研究生。主要研究方向为信号与信息处理。