基于PSO的小样本特征选择优化算法研究

杨鹤标，刘 芳，胡惊涛

(江苏大学 计算机科学与通信工程学院， 镇江 212013)

在实际生活应用中小样本数据集普遍存在，如自然语言的文本数据、医疗领域的疾病数据、视觉成像的图像数据等[1].小样本数据是指数据维数高，样本绝对数量少或者样本数远小于数据维数特征的数据[2].小样本数据有维度高的特征，会出现噪声、冗余和不相关特征等现象；加之训练样本数目少，使得传统的学习方法效能严重降低，易造成过拟合现象.研究发现，在不改变原特征空间的前提下，选择一些分辨力高同时能够表征原始特征空间性质的特征子集是解决小样本高维度[3]和过拟合问题[4]的关键.为此，文献[5]利用数据集训练attention模型，将一个标记的训练集和一个未标记的测试集映射到其标签中，进行微调以适应新的特征集，以解决one-shot learning问题；文献[6]在孪生网络[7]基础上引入迁移学习[8]算法，利用YOLOv2算法模型参数，对损失函数进行修改，采取局部放大策略提高小样本场景中算法的性能.目前还提出了K-紧邻模型[9]、范数支持向量机[10]、低秩矩阵近似[11]等特征选择方法，这些特征选择方法在特征间冗余处理方面还未达到良好的效果.

最大化类间距离可以提高特征子集泛化能力，最小化类内距离可以提高特征子集的拟合精度，因此需要最大化类间距离的同时最小化类内距离，在对文本特征达到理想的精确度的同时还可以提高特征的泛化能力.对此采用粒子群算法(particle swarm optimization,PSO)，在获取每个特征向量的gBest(全局最优权重)和pBest(局部最优权重)的基础之上，能够有效的挖掘到每个全局最优特征的信息并且避免局部最优特征的隔阂影响，这样能够在较低时间复杂度的情况下有效避免最优权值变化范围出现的不平衡现象.

1 相关工作

1.1 特征选择的相关研究

特征选择是解决小样本问题的关键步骤.目前主流的特征选择方法支持向量机(support vector machines,SVM)[12]及套索算法回归模型(lease absolution shrinkage and selection operator,Lasso)[13]等，在处理数据时有很大的优势，SVM和Lasso目的是找到一个将分类效果达到最合理化的超平面，对不等式约束条件下的二次型递推更新式函数进行优化，以达到目标函数的负梯度方向与约束函数的梯度方向一致最优解的目的[14].

但是在处理具有语义信息的数据时，上述方法存在不能获取深层次语义组合特征的缺陷，会造成语义的缺失.长短期记忆网络(long short-term memory,LSTM)有处理连续性数据的能力，在处理文本数据获取文本特征的同时包含了上下文信息[9]，在自然语言处理领域已有多种应用，如谷歌在机器翻译方面就使用了LSTM[15].学者们对LSTM进行了更加广泛的研究，如树形结构的长短期记忆神经网络(Tree-LSTM)、双向长短期记忆网络(Bi-LSTM)等，是解决序列化的特征选择问题的首选方法.

1.2 粒子群算法

PSO算法可完成人工神经网络中的连接权值训练、结构设计、学习规则调整、特征选择、连接权值的初始化和规则提取[16-17]等.将个体权值与整个特征集里的其它特征向量权值共享，找到最优的个体权重作为整个特征集的当前全局最优解，特征中的所有特征向量通过自己找到的当前个体权重和整个特征集共享当前全局最优解权重，根据自己的上下义词距离来确定最优权重.

令D为算法搜索空间的维数，S为特征集的规模(即包含特征的个数)，于是第i个特征在D维空间的位置定义为：

Xi=(xi1,xi2…，xiD)

(1)

第i个特征的上义词距离为：

Vi=(xi1,vi2…，viD)

(2)

第i个特征的下义词距离为：

V′i=(v′i1,v′i2…，v′iD)

(3)

第i个特征的局部最优权重为：

Pp=(pp1,pp2…，ppD)

(4)

第i个特征的全局最优权重为：

Pg=(pg1,pg2…，pgD)

(5)

对于第k代的第i个特征其第d维(1≤d≤D)的上下义词距离更新公式为：

vid(k+1)=wvid(k)+c1randid(.)[pid(k)-xid(k)]+c2randid(.)[pid(k)-xid(k)]

(6)

式中：w∈[0,1];c1、c2为非负常数；randid(.)∈[0,1]，特征向量上下义词差的绝对值小于等于阈值，产生趋于0的回归系数，使均方误差平滑收敛.

2 循环神经网络下的Bi-PSO算法

文中选用基于LSTM的文本特征选择模型，利用ReliefF算法效率高、普适性强的特点来获取候选子集.使添加了记忆细胞变种的Bi-LSTM的梯度dct/dct-1为1，以防止出现梯度消失现象[18]；在获得特征的上下文语义的基础上，调整权值参数和偏置值，获得文本特征权重.利用PSO的算法思想进行优化，限定学习因子c1和c2的值，度量新选特征Pi(k)和候选特征Xi(k)之间的相关性，以达到特征权重最优、整体平衡状态，获得最优特征子集.

2.1 候选子集生成

实际应用领域的数据集中，特征与特征之间存在各种各样的内在关联[19].ReliefF特征选择算法的优势在于能够快速、简单和高效地选择出特征子集，获得的子集在不同的学习算法中具有很强的普适性，一般直接利用所有训练数据的统计性能评估特征.ReliefF特征选择过程如图1.

图1 ReliefF模式特征选择过程Fig.1 ReliefF mode feature selection process

特征的权重更新公式如下：

W(A)=

(7)

式中：diff(A,R1,R2)为样本R1和R2在特征A上的差；Mj(C)为类C∉class(R)中第j个最近邻样本;m为抽样次数；R为近邻数.

(8)

ReliefF模式特征选择算法与具体的分类算法是相互独立的，单独作为学习算法的预处理步骤，得到候选特征子集.

2.2 基于Bi-LSTM的语义模型

循环神经网络(recurrent neural network,RNN)在传统的前馈神经网络中隐藏层节点之间加入了连接关系，使得RNN有了时间的概念，能够记住某个时间段的信息，从而对任意长度的序列数据进行处理.RNN单元含有一个记忆模块，而这个记忆模块与其输入、输出神经元直接相连，它可以选择性的记忆某些词语的信息而不会受到文本序列变长的影响.

理论上RNN可以处理任意长度的序列数据，但是由于梯度消失和梯度爆炸问题，使得RNN不能有效的解决长距离依赖问题.长短期记忆网络(LSTM)就是为了解决这个问题而设计的，其核心结构是记忆细胞(Memory Cell)C，使得梯度dct/dct-1为1，比普通的循环神经网络更好的获取到长距离的信息.LSTM在处理序列文本时只考虑先前的时序信息而忽略了上下文信息，而它的变种双向长短期记忆网络(Bi-LSTM)则很好的解决了这一问题，它既能考虑到先前的时间信息，也能考虑到未来的时间信息，所以文中采用Bi-LSTM作为记忆层，Bi-LSTM的结构如图2.

图2 Bi-LSTM结构Fig.2 Bi-LSTM structure

给定句子输入x={x1,x2,…,xn}，其中xt为t时刻的词向量，t-1时刻隐藏层的状态为ht-1，则t时刻LSTM的记忆细胞状态由以下几个门限决定.

忘记门：决定了LSTM何时会丢失细胞中的信息，公式为：

ft=σ(Wxfxt+Whfht-1+bf)

(9)

输入与更新门：输入门与更新门确定LSTM要把什么信息保存在细胞中，公式为：

it=σ(Wxixt+Whiht-1+bi)

(10)

ct=ftct-1+iiτ(Wxcxt+Whcht-1+bc)

(11)

输出门：输出门确定了将要输出的值，公式为：

Ot=σ(Wxoxt+Who+ht-1+bo)

(12)

ht=otθ(ct)

(13)

式中：σ为Sigmoid层，用W和b来连接输入层和隐藏层；O为神经网络的输出状态；Q为输出门的细细胞状态.Bi-LSTM最终将两个方向产生的输出向量h相连接，得到最终的输出：h⨁h.

2.3 Bi-PSO的算法原理

粒子群优化算法无法直接优化多目标问题，因此需要对多目标进行处理.文献[20]将基于分解的多目标进化算法的思想引入粒子群优化，再将多目标聚合为单目标后，相邻优化问题相互借鉴信息，以实现多目标问题.文中根据上下义词进行动态加权，实现多目标优化问题.

首先，候选特征依据其与已选特征的相互关系(冗余或依赖)赋予动态权值，每当新特征被选出后，根据候选特征的权值进行动态的调整.算法通过不断提高与已选特征子集具有依赖关系的特征的权值，以及降低与之具有冗余关系的特征的权值，从而能够在较低时间复杂度的情况下选择高度相关、内部依赖和低度冗余的特征子集.Bi-PSO算法的具体实现过程如下.

Bi-PSO算法Input:X// Candidate feature subsetOutput:D// Optimal feature subset1.D[ ]2.D[ ]3.PI=Random X()4.while (Xi(k+1)≥Pi(k)) do5. Pi(k+1)=Pi(k))6. D′.and(Pi(k+1))7. P(g)(k)=Random D′()//P(g)(k) is the Optimal feature8. if P(g)(k)=arg f(Pi(k)) then9. D.add (P(g)(k))10. else11. Xi(k+1)=Xi(k)+Vi(k+1)//Vi(k) is the adjustment range of the Threshold12. return Step413. end if14.else15. Pi(k+1)=Xi(k+1)16. D.add Pi(k+1)17.end while18.return D

Bi-PSO算法的主要特点是：候选特征根据其与已选特征的相互关系(冗余或依赖)赋予权值.根据候选特征的权值进行动态的改变，其步骤为：

(1) 随机从原始特征空间中选取特征作为初始优化点，并在搜索过程中随机选择将要增加或删除的特征(随机搜索避免了在同一方向上容易产生局部最优解的缺点)，第i个候选特征的权重更新公式为：

Xi(k+1)=Xi(k)+Vi(k+1)

(14)

(2) 限定学习因子c1和c2的值，度量新选Pi(k)和候选特征Xi(k)之间的相关性，根据全局特征调整每个候选特征当前的权重Pi(k+1)，更新公式为：

(15)

式中:f(.)为目标函数.

(3) 调整最终特征权值，权衡整个特征子集g的最优权重，减少特征冗余，公式为：

Pg(k+1)=arg minf(Pi(k+1)) 1≤i≤S

(16)

(4) 判断计算结果是否小于允许误差精度，如果是则保存并输出此时计算的特征权值和偏差值作为当前训练的结果，加入最优特征子集，当前候选特征i训练结束；否则继续第二步计算.

(5) 提高与已选特征集合具有依赖关系的候选特征的权值、降低与之具有冗余关系的候选特征的权值，获得最终特征子集D.

3 实验环境和实验数据

实验环境配置1：使用python及TensorFlow框架编写模型，Basic- LSTMCell(size)定义两个LSTM网络，size为制定的隐含层神经元数目，创建好后将两个神经网络传入static_bidirectional_rnn

(lstm_fw_cell, lstm_bw_cell),即创建好双向长短期记忆网络.模型的训练时间取决于模型的层数以及神经元的个数，文中设定每层神经元个数为20，层数为2层.

实验环境配置2：根据Bi-LSTM得到的实验结果进行特征子集的优化，采用了4种不同的分类算法分别比较各种特征选择算法的性能，分别是朴素贝叶斯(Naive Bayesian)、支持向量机(SVM)、最近邻(1-Nearest Neighbor,1-NN)和C4.5决策树，并选用mRMR、ReliefF和IG作对比实验.实验平台采用公认的机器学习集成软件Weka，各学习算法的有关参数均设为Weka的默认值.

实验数据：为了全面验证所提特征选择算法的有效性，模拟实验采用了5个来自UCI机器学习存储库大小不同的测试数据集，这些数据集经常用来比较机器学习领域中特征选择算法的性能，表1给出了这些测试集的简单概要描述.

表1 实验测试数据集的概要描述Table 1 Summary description of theexperimental test data set

从表1可以看出，这些数据集来自不同的领域，如生物医学、计算机科学、人文学等，包含了不同数量的样本数据、特征和类别属性，类别数对应着类别属性的个数，它们在一定程度上能够验证特征选择算法在不同条件下的性能.

4 实验结果与分析

Naive Bayesian、SVM、1-Nearest Neighbor和C4.5决策树，分别代表了4种不同类型的机器学习算法，能够更全面地对特征选择算法性能进行验证.模拟实验中选用了mRMR、ReliefF和IG 3种典型的特征选择算法作为对比实验，其中mRMR算法是被业界广为称赞的基于信息理论的特征选择算法，具有很强的代表性；ReliefF是非常优秀的基于欧式距离的特征选择算法，其Neighbors和Istances分别设为5和30；IG是被业界广为称赞的基于信息熵的特征选择算法.Ave为特征选择算法在数据集上的平均分类准确性.原始特征列表示的是学习算法在没有使用特征选择算法情况下的分类准确率.得到的实验结果如表2～5.

表2 特征选择算法在Naive Bayesian分类性能比较Table 2 Comparison of feature selection algorithms in naive bayesian classification %

表3 特征选择算法在SVM分类性能比较Table 3 Comparison of feature selection algorithms in SVM classification performance %

表4 特征选择算法在1-NN分类性能比较Table 4 Comparison of feature selection algorithms in 1-NN classification %

表5 特征选择算法在C4.5决策树分类性能比较Table 5 Comparison of feature selection algorithms in C4.5 decision tree classification %

从表2～5可以看出Bi-PSO算法在性能上占明显优势，如数据显示，Bi-PSO算法在所有训练样本数据集上对应的不同分类器，其平均性能分别是81.80%、81.12%、81.24%、80.32%，Bi-PSO算法分类性能平均比Bi-LSTM提高2.225%，Bi-PSO算法计算代价也是在可接受范围之内的.

为了验证已选子集中单个特征的区分性能，在相同特征子集规模上进行了一组对比试验，将4种特征选择算法分别在Lymphography、Synthetic样本数据集上依次获取不同数量的特征，并使用5种分类器进行训练测试，使用十折交叉验证方式获取分类模型在数据集上的分类性能，实验结果如图3.

图3 在不同特征个数上分类性能的比较Fig.3 Comparison of classification performanceon different feature numbers

图3中，X轴为特征子集的前k个特征，Y轴为该前k个特征在的学习算法下的平均分类准确度，可以看出，Bi-PSO在特征数较少的情况下都能表现出良好的分类精度，在选择出少量特征之后每次所选的特征都会对已选的特征性能带来提升.从Lymphography数据集实验结果中可以看出，在特征数小于16的情况下Bi-PSO分类精度曲线均高于其他算法；从Synthetic数据集结果中可以看出，在特征数大于55的情况下，Bi-PSO的分类精度与其他算法结果几乎重合，而对于具有60个原始特征的Synthetic数据集来说，55个特征已失去了特征选择的意义.

5 结论

循环神经网络越来越多地运用到自然语言处理中，但存在着模型规模庞大、需要海量的数据、学习效率低等问题，因此，提出了一种基于Bi-LSTM，采用粒子群算法的思想的方法，让神经网络能够很好地学习到小样本数据集的特征.该算法对于小样本的特征选择的学习起到了重要作用，不仅可以很好解决特征的泛化和小样本的过拟合问题，同时也提高了网络的学习效率，为小样本问题的研究提供了一种新思路.

下一步的研究工作：(1)如何进一步优化算法以实现粒子群自适应多目标选择；(2)如何在获取最优特征子集的过程中，通过限定学习因子降低时间复杂度，更快的训练得到惯性权重.

参考文献(References)

[1] 王翔,胡学钢.高维小样本分类问题中特征选择研究综述[J].计算机应用,2017,37(9):2433-2438,2448.DOI:10.11772/j.issn.1001-9081.2017.09.2433.

WANG Xiang,HU Xuegang.Overview on feature selection in high-dimensional and small-sample-size classification[J].Journal of Computer Applications,2017,37(9):2433-2438,2448.DOI:10.11772/j.issn.1001-9081.2017.09.2433.(in Chinese)

[2] VAPNIK V. The nature of statistical learning theory[M]. Springer Science & Business Media, 2013:163-167.

[3] 宁永鹏.高维小样本数据的特征选择研究及其稳定性分析[D].厦门：厦门大学,2014.3

[4] STEPHAN N , NATALIE L , MARIANNE D . Building change detection from historical aerial photographs using dense image matching and object-based image analysis[J]. Remote Sensing, 2014, 6(9):8310-8336.DOI:10.3390/rs6098310.

[5] VINYALS O,BLUNDELL C,LILLICRAP T,et al.Matching networks for one shot learning[C]//Proceedings of the 30th International Conference on Neural Information Processing Systems.Barcelona:NIPS: 2016：3637-3645.

[6] 柳青林.基于小样本学习的目标匹配研究[D].西安：西安电子科技大学,2018:17-38

[7] BROMLEY J,GUYON I,LECUN Y,et al. Signature verification using a "SIAMESE" time delay neural network [J].International Journal of Pattern Recognition & Artificial Intelligence, 1993,7(4).669-688.DOI:10.1142/S0218001493000339.

[8] LUO Xiong,CHEN Yi,SHEN Feng. Text classification dimension reduction algorithm for Chinese web page based on deep learning [C]// International Conference on Cyberspace Technology.Beijing, China: IET, 2014:451-456.DOI:10.1049/cp.2013.2171.

[9] LÜDERS B, SCHLGER M, KORACH A, et al. Continual and one-shot learning through neural networks with dynamic external memory[C]// European Conference on the Applications of Evolutionary Computation. Springer, Cham, 2017:886-901.DOI:10.1007/978-3-319-55849-3_57.

[10] 鲍捷,杨明,刘会东.高维数据的1-范数支持向量机集成特征选择[J].计算机科学与探索,2012,6(10):948-953.DOI:10.3778/j.issn.1673-9418.2012.10.010.

BAO Jie,YANG Ming,LIU Huidong.Ensemble feature selection based on 1-norm support vector machine for high-dimensional data[J].Journal of Frontiers of Computer Science and Technology,2012,6(10):948-953. DOI:10.3778/j.issn.1673-9418.2012.10.010.(in Chinese)

[11] 张恒敏,杨健,郑玮.低秩矩阵近似与优化问题研究进展[J].模式识别与人工智能,2018,31(1):23-36.DOI:10.16451/j.cnki.issn1003-6059.201801003.

ZHANG Hengmin,YANG Jian,ZHENG Wei.Research progress of low-rank matrix approximation and optimization problem [J].Pattern Recognition and Artificial Intelligence,2018,31(1):23-36. DOI:10.16451/j.cnki.issn1003-6059.201801003.(in Chinese)

[12] LEI Haijun,HAN Tao,ZHOU Feng,et al. A deeply supervised residual network for hep-2 cell classification via cross-modal transfer learning[J]. Pattern Recognition the Journal of the Pattern Recognition Society,2018,79:290-302.DOI:10.1016/j.patcog.2018.02.006.

[13] 孙鑫.机器学习中特征选问题研究[D].长春：吉林大学,2013:25-24

[14] 童忆莹.基于增量聚类和ReliefF的特征选择方法[D].重庆：西南大学,2011:23-29.

[15] SHEN F,LUO X,CHEN Y.Text classification dimension reduction algorithm for Chinese web page based on deep learning[C]//International Conference on CyberspaceTechnology.IET, 2014:451-456.

[16] LOGANINA V, MAKAROVA L V, TARASOV R V, et al.The composition cement binder with the use of the synthesized aluminosilicates[J]. Advanced Materials Research, 2014,1022:3-6.DOI:10.4028/www.scientific.net/AMR.1022.3.

[17] TAN M, WANG L, TSANG I W. Learning sparse SVM for feature selection on very high dimensional datasets[C]// International Conference on International Conference on Machine Learning. Haifa, Israel:ICML,2010:1047-1054.

[18] 徐帅.基于统计学的大数据特征分析研究[D].北京：北京邮电大学, 2018:27-36,

[19] 崔鸿雁,徐帅,张利锋.机器学习中的特征选择方法研究及展望[J].北京邮电大学学报,2018,41(1):1-12.DOI:10.13190/j.jbupt.2017-150.

CUI Hongyan,XU Shuai,ZHANG Lifeng.The key techniques and future vision of feature selection in machine learning[J].Journal of Beijing University of Posts and Telecommunications,2018,41(1):1-12.DOI:10.13190/j.jbupt.2017-150.(in Chinese)

[20] 徐鹤鸣.多目标粒子群优化算法的研究[D].上海：上海交通大学, 2013:17-22.