基于改进SFS特征选择BP识别算法

朱旭东等

摘 要： 特征选择在BP神经网络算法中起着重要作用，顺序前向选择算法（SFS算法）利用前向搜索叠加的方式，从众多的原始特征中获得对分类识别算法最有效的主要特征，实现样本特征维数压缩。提出一种改进SFS特征选择算法，设计了加权判别函数和测试反馈停止准则。实验证明，改进算法能有效压缩样本特征维数，提高BP网络收敛速度和正确识别率。

关键词： 特征选择； SFS； BP网络； 收敛速度

中图分类号： TN911?34； TP391.4 文献标识码： A 文章编号： 1004?373X（2015）12?0001?04

0 引 言

一个完善的BP神经网络识别系统中，特征选择是不可缺少的一个重要技术环节，它一般处于样本特征数据采集和识别算法两大环节之间，与后续的BP神经网络分类算法的性能息息相关，是模式识别领域研究的核心内容之一。

近几年来，在数据挖掘的机器学习领域所涉及的维数都比较高，所提取的特征不能满足不同类的样本差别较大，而同类的样本差别较小的特点，或者提取的特征彼此相关性很大，并且存在很多冗余的特征。另外，当样本特征维数增加到一定值以后若是再继续增加，反而会导致分类识别算法识别率变差，这些不足严重影响到分类识别算法性能。特征选择的任务就是从原始特征中挑选出对识别算法最有效且数目最少的特征，去除噪音特征和冗余不相关的特征，实现样本特征空间维数的简化，减少识别算法运算复杂度和系统运算时间，提高网络收敛速度。因此，特征选择在BP神经网络算法中起着重要作用。一般情况下，一个完整的特征选择算法包括4个要素：搜索起点和方向，搜索策略，特征评估函数和算法停止准则。

文献[1?4]提出了SFS特征选择的算法，文献[5]提出了基于一种特征判别函数的SFS特征选择算法，并在BP网络和向量机识别系统中进行了验证；本文在此基础上，设计了加权判别函数和测试反馈停止准则等改进方法，使特征选择算法更为合理、规范，选出的优秀特征子集更为有效和精简。

1 SFS算法模型和缺陷分析

顺序前向选择算法（SFS）是一种简单的自下而上的搜索方法[5]，首先把目标特征集初始化为空集合，然后根据所设立的评价规则函数处理原始特征集合中的每一个特征，比较每个特征的函数值，选择其中函数值最大的对应特征加入目标特征子集。然后在保留这个入选特征的基础上重复上面的过程，从原始特征集剩余的特征中循环选择剩余的特征与入选的特征匹配，比较组合特征所得到的函数值，选择与入选特征组合所得到的评价函数值最大的特征加入目标特征子集。按照顺序前向选择方式重复以上的选择步骤，直到维数达到规定的最大维数[6]。作为一种最基本的贪心算法，该算法要求每次选择的特征都能使加入后的新特征子集最优[7]。

具体的算法描述如下：

假设原始特征集有n个特征，表示为：{fd ，1≤d≤n}，设立特征评估准则函数为：

[FDR=jMi≥jMμi-μj2σi2-σj2] （1）

式中：[M]表示样本所含的类别；[μi]和[μj]分别表示第[i]类和第[j]类的类内特征向量均值；[σi2]和[σj2]分别表示第[i]类和第[j]类的类内方差[5]。

Step1： 将目标特征子集Xk初始化为空，即Xk=[?]。

Step2： 计算原始特征集F[（f1，f2，…，fn）]中每一个特征[fd]的函数评价函数值[FDR（fd）]，找到其中最大的函数值[FDR（fa）]=max{[FDR（fd）]}，将[FDR（fa）]所对应的特征[fa]加入目标特征子集Xk；

Step3：将其余未入选的n-1个特征依次与已入选特征[fa]匹配，得到匹配后的组合特征的准则函数值[FDR]的大小按照升序排序，如果：

[FDR（Xk?{F1}）>FDR（Xk?{F2}）>…>FDR（Xk?{Fn-1}）] （2）

则将能使[FDR]值最大的特征加入到目标特征子集[Xk]中，得到更新后的目标特征子集：

[Xk=Xk?F1] （3）

Step4：按照Step3的思想，依次增加能使[FDR]值最大的的特征到目标特征子集Xk中，每次只增加一个特征，直到目标特征子集的数量达到设定的最大的L值的水平，从而得到更新后最终的目标特征子集Xk。

通过顺序前向选择算法更新目标特征子集，使目标特征子集几乎包含原始特征集中的所有最优特征，更能准确地代表原始特征集，过滤掉大部分的噪声和冗余特征，增加了分类的有效性，算法计算量较小。但是，与此同时，SFS算法也存在着明显的缺陷：现有的特征评估准则函数公式区分度不够好，还有待进一步完善；传统的算法停止准则是建立在预先凭借经验设立特征子集最大维数，当目标特征子集的特征维数达到预先设定最大维数时停止搜索运算。该种方法武断性强，并没有考虑客观实验数据的差异性，可以进一步根据需要进行停止准则的改进；算法没有充分地考虑目标特征子集已入选的特征与特征之间的相关性。

针对以上问题，需要在原SFS算法的基础上进行必要的改进。

2 改进算法

2.1 SFS判别函数公式加权改进

式（1）给出的判别函数FDR是类与类之间的差异性和类内一致性的比值，FDR值越大表示两类之间的差别性越大。分子[μi]和[μj]分别表示第[i]类和第[j]类的类内特征向量均值，[μi-μj2]代表各类别之间的差异性，[μi-μj2]越大FDR值越大；分母[σi2]和[σj2]分别表示第[i]类和第[j]类的类内方差，[σi2-σj2]代表的是各自类内的分布一致性。[σi2]和[σj2]各自的值越小，FDR值就越大。

分母[σi2-σj2]不能很好地表现第[i]类和第[j]类的各自的类内一致性，还可能出现负数的情况，并且显然没有考虑到各类别的类内方差可能存在个别偏大的情况。因此，可以通过改进判别函数FDR的公式来解决上述这些问题。改进的判别公式[FDR′]如下所示：

[FDR′=jMi≥jMμi-μj2aσi2+bσj2] （4）

式中：[M]表示样本所含的类别；[μi]和[μj]分别表示第[i]类和第[j]类的类内特征向量均值；[σi2]和[σj2]分别表示第[i]类和第[j]类的类内方差[2]，[a，b∈（0，1]]。

式（4）[FDR′]是在原有式（1）FDR的基础上把公式的分母进行了一些改进。如果想FDR值很大，就要求公式分母上各类别的类内方差[σi2]和[σj2]的值都要很小，要求各类别的类内一致性要很高，但是在实际的工程实验时，不能保证所有数据样本类别的类内方差都能符合要求，总是存在少部分类别的类内方差可能偏大。因此，在判别公式分母各类别的类内方差[σi2]和[σj2]前分别加个取值在[（0，1]]的系数，当出现个别类内方差[σi2]和[σj2]过大的情况时，适当地减小相应类别方差系数的取值，这样就能保证判别公式[FDR′]的值很大；另外，将判别公式分母[σi2]和[σj2]之间由“[-]”变成“[+]”更能准确地表达判别函数的函数值大小与各类别的类内一致性的关系。判别公式要求只有各类别的类内一致性同时很高，即各类别的类内方差[σi2]和[σj2]的值同时很小，函数值[FDR′]才能最大。综上所述，改进后的[FDR′]判别函数能更好地描述各类别之间的区别性，判别函数[FDR′]值越大，各类别的差别性就越大。判别函数[FDR′]为选择最优特征组合提供了更科学、更合理和更准确的衡量标尺。

2.2 基于测试反馈的SFS算法停止准则改进

原SFS算法停止准则是凭借经验预先设置特征子集最大维数，当目标特征子集的特征数量达到预先设置的最大维数时，强行停止搜索运算。这样的停止准则武断性强，没有考虑到实际数据的差异性和实验环境的复杂性，算法的预期效果会受到影响，得到的最优特征子集的有效性和科学性往往会打折扣。针对这个缺陷，本文提出了一种基于分类正确率反馈的SFS算法的停止准则，根据入选特征子集的特征依次用BP神经网络训练所有样本，在测试集上用对应的特征测试，如果在特征选择测试中前后几次的分类正确率差值平均值小于设定的阈值，说明特征子集的测试正确率进入了峰值，可以停止搜索算法。

具体基于分类正确率反馈的SFS停止准则算法如下：

Step1：设置正确率浮动门限阈值为[β0]，初始化目标特征子集[Xk]为空，即[Xk=?]；

Step2：利用SFS算法依次从原始特征集[F={Fj，j=1，2，…，N}]中遴选出与[Xk]中特征匹配的判别函数值最大的特征加入特征子集[Xk]，得到更新后的最优特征子集[Xk={s1，s2，…，sm：1≤m

Step3：将匹配更新后最优特征子集[Xk]的训练样本送入BP网络训练，当训练次数大于500次时，停止训练，得到与最优特征子集[Xk]中维数相对应的m个训练模型[M={Mode1，Mode2，…，Modem}]。将训练模型[M]在测试集上得到m个对应特征的分类准确度[R={α1，α2，…，αm}]；用[αm]，[αm+1]和[αm+2]分别表示特征子集[Xk={s1，s2，…，sm}]，[Xk={s1，s2，…，sm，sm+1}]和[Xk={s1，s2，…，][sm，sm+1，sm+2}]时经测试集得到的与[Xk]特征维数相对应的BP网络分类准确度；

Step4：如果[Maxam+1-ai，am+2-am+1<β0]，算法停止搜索。否则，转到Step2。

基于测试反馈的算法停止准则是将选择的最优特征送入BP网络测试所选特征相对应的分类准确度，并将结果反馈回SFS算法，SFS算法根据反馈的情况决定是否继续搜索。基于测试反馈的算法停止准则更加科学、规范和合理，能根据不同的实验数据采取智能的算法停止策略，泛化性更强，准确性更好，应用性更广泛。

3 实验结果及分析

仿真平台主要利用Matlab软件，针对给定的数据样本建立BP神经网络识别系统，用Matlab语言编写应用程序，通过比较改进前和改进后算法的仿真结果，分析改进算法的优劣，证实了改进算法的可行性和有效性。

为了对改进算法进行检验，保证数据的真实性，实验采用医学显微镜医学检验样本对算法进行了验证，数据库为尿沉渣细胞，共14类，形状、纹理、颜色等特征共90维，从2万多个样本中，选出了1 212个训练样本和151个测试样本。

实验选用3层的BP网络结构，输入层节点的数量是根据每个样本提取的维数来确定；中间的隐含层节点数根据经验选择为2×输入特征维数+2；输出层节点数根据分类的数量选择为14，代表14类细胞。这是典型的3层BP神经网络结构。隐含层的激活函数和输出层的输出函数都采用tansig，训练函数选择trainrp函数，输出层传输函数采用purelin，训练步数为500，目标误差精度是0.001。

建立好实验环境后，根据特征选择相应的维数将训练样本送入BP网络进行训练构造与选择最优特征维数相对应的模型，利用特征选择相对应维数的模型对测试集进行测试得到相应的BP识别正确率，其性能曲线如图1所示。图中横坐标表示最优特征选择的维数，纵坐标表示与选择最优特征维数相对应的BP算法识别正确率。图1为原始全部特征、原SFS、改进SFS特征选择维数与相应BP网络识别正确率对比。

与相对应BP网络识别正确率对比

如图2所示是Matlab程序生成的各类最终识别结果的混淆矩阵，测试样本经过BP网络模型测试验证得到详细的各类别样本的正确识别数据。数据主要分成3部分，分别记录全部特征、原SFS特征选择和改进SFS特征选择BP算法的各类别样本的正确识别率。原SFS和改进SFS特征选择最终选择的最优特征子集的数量分别是40维和42维。各部分表格中加颜色的各区域是各类别样本被正确识别的数量，最右侧一列是各类别被正确识别比例，每个部分的右下角加红的数据是记录各部分算法的平均正确识别率，可以清楚对比地看出3种算法的各类别样本的识别情况。

实验中分别记录全部特征?BP算法、原SFS特征选择?BP算法和改进SFS特征选择?BP算法的最终结果，将各算法数据结果分别在样本特征选择维数、迭代步数和正确识别率进行对比，对比结果见表1。

根据图1和图2，改进SFS特征选择的最优特征是42维，比全部特征90维少了38，但是比原SFS算法40维多了2维特征；在正确率的对比上，改进SFS特征选择BP识别率比全部特征BP识别率略低一点，但是比原SFS识别率高。由图2和表1可知，改进的SFS特征选择BP算法的迭代步数是100次，比全部特征?BP网络的迭代步数少20次，比原SFS?BP算法迭代步数120次少了20次；在正确率方面，改进的SFS特征选择的BP算法正确识别率比全部特征?BP算法正确识别率少了0.613 2%，基本接近全部特征?BP算法识别率，比原SFS?BP算法的识别率高0.657 3%。

综上所述，改进SFS特征选择成功缩减了样本特征维数，由全部特征的90维压缩到了42维，过滤掉了大部分的噪声和冗余特征，减小了BP神经网络的运算复杂度，并且基本接近全部特征的BP算法识别率，比原始全部特征BP算法识别率仅少0.613 2%；改进SFS算法选择的特征比原SFS选择的特征多了2维，但是改进SFS的BP识别率比原SFS?BP识别率提高了0.659 1%，迭代步数也少了20次。综合衡量，不难看出，基于改进SFS特征选择?BP识别算法比原SFS?BP算法和原始全部特征的BP算法更为科学、合理和可行。

4 结 语

本文通过设计加权判别函数和测试反馈停止准则等方法改进SFS特征选择算法，充分考虑到各类别样本的类内方差可能存在个别偏大的情况，采取判别函数系数加权的方法来调整类内方差值，又提出了基于测试反馈的SFS算法停止准则，克服了原来的预先设定阈值的缺陷。实验证明，改进算法能有效压缩样本特征维数，提高BP网络收敛速度和正确识别率。

参考文献

[1] MENEGATTI E， PRETTO A， PAGELLO E. Testing onmidirectional vision?based Mont Carlo localization under occlusion [C]// Proceeding of IEEE/RSJ 2004 International Conference on Intelligent Robots and Systems. [S.l.]： IEEE， 2004， 3： 2487?2493.

[2] 计智伟，胡珉，尹建新.特征选择算法综述[J].电子设计工程，2011（5）：45?51.

[3] 姚旭，王晓丹，张玉玺，等.特征选择方法综述[J].控制与决策，2012（2）：161?165.

[4] 李敏，卡米力·木依丁.特征选择方法与算法的研究[J].计算机技术与发展，2013（12）：16?21.

[5] REZATOFIGHIA Seyed Hamid， SOLTANIAN?ZADEH Hamid. Automatic recognition of five types of white blood cells in peripheral blood [J]. Computerized Medical Imaging and Graphics， 2011， 35： 333?343.

[6] PUDIL P， NOVOVICOVA J， KITTLER J. Floating search methods in feature selection [J]. Pattern Recognition Letters 1994， 15： 1119?1125.

[7] GUYON I. An introduction to variable and feature selection [J]. Journal of Machine Learning Research， 2003， 3： 1157?1182.

[8] 易超群，李建平，朱成文.一种基于分类精度的特征选择支持向量机[J].山东大学学报：理学版，2010（7）：119?121.