夏广胜，严慧
（南京理工大学计算机科学与工程学院，江苏南京210094）
摘要：稀疏表示作为一种基于部分数据的表示，已经吸引了越来越多的关注，并广泛应用于模式识别和机器学习领域。提出一种新的算法，称为稀疏表示保持的鉴别特征选择（SRPFS），其目的是选择鉴别性特征子集，使得在所选特征子空间中，样本的稀疏类内重构残差和稀疏类间重构残差的差值最小化。与传统算法选择特征的独立性方式不同，该算法以批处理方式选择最具鉴别性的特征，并用于优化提出的l2，1范数最小化的目标函数。在标准UCI数据集和哥伦比亚图像数据库的实验结果表明，该算法在识别性能和稳定性方面优于其他经典特征选择算法。
教育期刊网 http://www.jyqkw.com
关键词 ：特征选择；稀疏表示；重构残差；l2，1范数
中图分类号：TN911?34 文献标识码：A 文章编号：1004?373X（2015）18?0008?05
收稿日期：2015?05?05
基金项目：国家自然科学基金（61202134）；国家杰出青年科学基金（61125305）；中国博士后科学基金（AD41431）；江苏省博士后科学基金
0 引言
特征选择[1]用于从高维特征空间中选择特征子集，并保持特征子集的原始物理特性，根据使用类别标签与否，特征选择算法可分为非监督和监督两种，本文主要研究监督特征选择算法。经典的监督特征选择算法包括ReliefF[2]，Fisher Score[3] 以及多簇特征选择（Multi?Cluster Feature Selection，MCFS）[4]等，它们通过特征和类别标签之间的相关性来度量特征的重要性，但是大多数传统特征选择算法对每个特征的度量是独立进行的[3，5]，并且将特征逐个添加至所选特征子空间，这种选择方式的局限性在于特征之间的相关性被忽略[4]。最近，l2,1 范数正则化优化已经应用到特征选择算法，此类算法通过对特征选择矩阵进行l2,1 范数最小化约束来选择特征[6?7]。
与此同时，稀疏表示作为一种基于部分数据的表示，已经吸引了越来越多的关注，并已广泛应用于模式识别和机器学习领域[8]。稀疏表示方法假设一个超完备字典中样本的稀疏线性组合可以重构一个给定的样本，例如Wright 等提出的基于稀疏表示的分类方法[9]（Sparse Representation?based Classification，SRC），该方法的优化问题惩罚线性组合系数的l1 范数，SRC尝试使用所有训练样本的稀疏线性组合来表示一个给定的测试样本，并且认为稀疏非零表示系数集中在测试样本的同类训练样本上。受到SRC的启发，很多基于稀疏表示的特征抽取算法出现，例如文献[10?11]提出的稀疏表示分类器引导的监督特征抽取算法，该算法旨在减少类内重构残差，并与此同时增加类间重构残差，但二者在目标函数的形式上有所不同，文献[10]采用比值方式文献[11]采用差值方式。与特征选择算法不同，特征抽取将原始特征进行转换从而实现数据降维，特征的原始物理特性发生变化。回顾经典的监督特征选择算法，却不存在与SRC直接关联的，本文提出了一种稀疏表示保持的鉴别特征选择（SRPFS）算法，旨在寻找一种线性映射使得在所选特征子空间中，样本的稀疏类内重构残差足够小并且稀疏类间重构残差足够大，并用于优化提出的l2,1 范数最小化的目标函数。
1 基于稀疏表示的分类方法
2 稀疏表示保持的鉴别特征选择
2.1 问题描述
基于SRC决策规则，希望在所选特征子空间中样本xi 尽可能接近其稀疏类内重构并同时尽可能远离其稀疏类间重构，考虑所有样本，SRPFS的目标函数定义如下：
对L(U)关于U 求导，可以得到下式：
通过式（17）更新U t ；
t = t + 1 ；
直到收敛准则满足；
输出：U 。
2.3 L(U)的凹性研究
2αP 是正定的因为它是一个轴元素为正数的对角矩阵，根据正定矩阵的定义，如果G 是正定的很容易证明2αP + G 是正定的，然而很难直接证明G 的正定性，事实上通过在实验中对参数β 进行控制来保证G 的正定性，β 的取值在实验部分给出。在假设2αP + G 是正定的前提下，通过下面的定理证明目标函数在算法1中的迭代过程中的收敛性：
定理1：式（12）中的目标函数值在算法1中的迭代过程中单调减小。
证明：很容易证明式（12）就是解决以下的问题：
相应地，在第t 次迭代中有：
根据[7]中的引理，对于任意非零向量u ，ut∈ Rm ，下面的不等式成立：
它表明式（12）中的目标函数值在算法1中的迭代过程中单调减小。
3 实验
在本节中，通过实验验证算法SRPFS的性能，首先将SRPFS与经典的监督特征选择算法进行比较，然后分析SRPFS的收敛性。
3.1 实验设置
4 个公共数据集：Wine[16]，Breast Cancer Wisconsin（Diagnostic）[16]，Connectionist Bench （Sonar，Mines vs.Rocks）[16]以及COIL20[17]，Wine，Breast Cancer Wisconsin和Connectionist Bench 来自标准UCI库；来自哥伦比亚图像数据库的COIL20包含20个对象，数据集的描述在表1中给出。
将SRPFS 与All Features，Fisher Score，MCFS，以及ReliefF进行比较，实验中为保证式（20）中G 的正定性，β 在4 个数据集上分别设置为10-3，10-5，10-3，10-2，使用快速迭代收缩阈值算法（Fast Iterative Shrinkageand Thresholding Algorithm ，FISTA）[16]求解式（5），FISTA中的规范化参数设置为1，α 的调整范围为{1,10-1,10-2} ，对于MCFS以及ReliefF邻居样本数设置为5，由于Connectionist Bench和COIL20的特征数大于50，相应的所选特征数分别设为{1,2,?,30} ，{1,2,?,512}，即最大值取数据集维度的50%。
3.2 分类识别率比较
对于每个数据集，随机选择每类样本集的5种方法在4个数据集上的平均最高识别率（± std）的比较，如表2所示。选择的样本中80%做训练集，剩余样本做测试集，为了证明不同算法的可靠性，将训练集以及测试集的选择过程重复10 次，All Features，Fisher Score，MCFS，ReliefF 以及SRPFS 在4 个数据集上的平均最高识别率及标准差在表2中给出，可以看出所有的特征选择算法优于All Features，因此，特征选择算法有助于提高识别率，由于SRPFS中保持了样本之间的稀疏相关性，SRPFS从识别率和稳定性两方面的性能明显优于其他方法。
3.3 收敛性
在本节中，通过实验证明所提出的迭代算法单调减小目标函数值，直到收敛，图1展示了式（12）中的目标函数值在4个数据集上的收敛曲线图，可以看出目标函数在数次迭代后收敛。
4 结语
在本文中，提出了一种新的监督特征选择算法，称为稀疏表示保持的鉴别特征选择（SRPFS），其目的是选择鉴别性特征子集，使得在所选特征空间中，样本的稀疏类内重构残差和稀疏类间重构残差的差值最小化。通过实验验证SRPFS 的性能并与其他4 种方法即AllFeatures，Fisher Score，MCFS，以及ReliefF在4个公共数据集上进行比较，实验表明SRPFS在识别率以及稳定性方面明显优于其他方法。在未来，考虑将SRPFS的思想应用到非监督特征选择算法研究中，由于不使用样本的类别标签这将是一个更大的挑战。
教育期刊网 http://www.jyqkw.com
参考文献
[1] KOLLER D， SAHAMI M. Toward optimal feature selection [C]// Proceedings of the 13th International Conference on Ma?chine Learning. Bari，Italy：[s. n.]，1996：284?292.
[2] KONONENKO I. Estimating attributes：analysis and extensions of RELIEF [C]// Proceedings of the 1994 European Conference on Machine Learning. Catania，Italy：[s. n.]，1994：171?182.
[3] DUDA R O，HART P E，STORK D G. Pattern Classification [M]. 2nd ed. New York，USA：John Wiley & Sons，2001.
[4] CAI Deng，ZHANG Chiyuan，HE Xiaofei. Unsupervised fea?ture selection for multi ? cluster data [C]// Proceedings of the 2010 ACM Special Interest Group on Knowledge Discovery and Data Mining. Washington，USA：[s. n.]，2010：333?342.
[5] HE Xiaofei，CAI Deng，NIYOGI P. Laplacian score for feature selection [C]// Proceedings of Advances in Neural Information Processing Systems. Vancouver，Canada：[s. n.]，2005：231?236.
[6] YANG Yi，SHEN Hengtao，MA Zhigang，et al. l2,1 ?norm regu?larized discriminative feature selection for unsupervised learning [C]// Proceedings of the Twenty?Second International Joint Con?ference on Artificial Intelligence. Barcelona， Spain： [s. n.]，2011：1589?1594.
[7] NIE Feiping，HUANG Heng，CAI Xiao，et al. Efficient and ro?bust feature selection via joint l2,1 ? norms minimization [C]//Proceedings of the 2010 Advances in Neural Information Pro?cessing Systems 23. Vancouver，Canada：[s. n.]，2010：1?9.
[8] WANG J J Y，BENSMAIL H，YAO N，et al. Discriminative sparse coding on multi ? manifolds [J]. Knowledge ? Based Sys?tems，2013，54：199?206.
[9] WRIGHT J，YANG A Y，GANESH A，et al. Robust face recog?nition via sparse representation [J]. IEEE Transactions on Pat?tern Analysis and Machine Intelligence，2009，31（2）：210?227.
[10] YANG Jian，CHU Delin. Sparse representation classfier steered discriminative projection [C]// Proceedings of the 20th Interna?tional Conference on Pattern Recognition. Istanbul，Turkey：[s. n.]，2010：694?697.
[11] LU Canyi， HUANG Deshuang. Optimized projections for sparse representation based classification [J]. Neurocomputing，2013，113：213?219.
[12] DONOHO D L. For most large underdetermined systems of linear equations the minimal l1 ?norm solution is also the sparsest so?lution [J]. Communications on Pure and Applied Mathemat?ics，2006，59（6）：797?829.
[13] CANDES E，ROMBERG J，TAO T. Stable signal recovery from incomplete and inaccurate measurements [J]. Communica?tions on Pure and Applied Mathematics，2006，59（8）：1207?1223.
[14] CHEN S S B，DONOHO D L，SAUNDERS M A. Atomic de?composition by basis pursuit [J]. Society for Industry and Ap?plied Mathematics Review，2001，43（1）：129?159.
[15] DONOHO D L，TSAIG Y. Fast solution of l1 ?norm minimiza?tion problems when the solution may be sparse [J]. IEEE Transactions on Information Theory，2008，54（11）：4789?4812.
[16] Author unknown. UCI Donald Bren School of Information &Computer Sciences[EB/OL]. [2015?03?04]. http://www.ics.uci.edu/.
[17] Author unknown.Other standard data sets in matlab format[EB/OL].[2015?03?04]. http://www.cad.zju.edu.cn/home/dengcai/Da?ta/MLData.html.
[18] BECK A，TEBOULLE M. A fast iterative shrinkage?thresh?olding algorithm for linear inverse problems [J]. SIAM Journal on Imaging Sciences，2009，2（1）：183?202.
作者简介：夏广胜（1989—），女，河北衡水人，硕士。主要研究方向为模式识别与人工智能。严慧（1983—），女，江苏南京人，副教授，博士。主要研究方向为模式识别与人工智能。