稀疏表示保持的鉴别特征选择算法

夏广胜　严慧

摘 要： 稀疏表示作为一种基于部分数据的表示，已经吸引了越来越多的关注，并广泛应用于模式识别和机器学习领域。提出一种新的算法，称为稀疏表示保持的鉴别特征选择（SRPFS），其目的是选择鉴别性特征子集，使得在所选特征子空间中，样本的稀疏类内重构残差和稀疏类间重构残差的差值最小化。与传统算法选择特征的独立性方式不同，该算法以批处理方式选择最具鉴别性的特征，并用于优化提出的l2，1范数最小化的目标函数。在标准UCI数据集和哥伦比亚图像数据库的实验结果表明，该算法在识别性能和稳定性方面优于其他经典特征选择算法。

关键词： 特征选择； 稀疏表示； 重构残差； l2，1范数

中图分类号： TN911?34 文献标识码： A 文章编号： 1004?373X（2015）18?0008?05

Abstract： A new algorithm for selection of distinguishable features preserved by sparse representation， whose aim is to select a subset of distinguishable features to minimize the difference value of reconstruction residual in sparse class and reconstruction residuals between sparse classes of samples in the subspace of selected features. The algorithm， which is different from the selection feature independence mode of the traditional algorithms， selects the most distinguishable features in batch mode and， is used to optimize the minimized objective function of l2，1?norm. The experimental results on standard UCI datasets and Columbia object image data base show that the algorithm is superior to other classic feature selection algorithms in the aspects of recognition performance and stability.

Keywords： feature selection； sparse representation； reconstruction residual； l2，1?norm

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 基于稀疏表示的分类方法

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中给出。

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种方法即All Features， Fisher Score， MCFS， 以及 ReliefF在4个公共数据集上进行比较，实验表明SRPFS在识别率以及稳定性方面明显优于其他方法。在未来，考虑将SRPFS的思想应用到非监督特征选择算法研究中，由于不使用样本的类别标签这将是一个更大的挑战。

参考文献

[1] KOLLER D， SAHAMI M. Toward optimal feature selection [C]// Proceedings of the 13th International Conference on Machine 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 Classi?cation [M]. 2nd ed. New York， USA： John Wiley & Sons， 2001.

[4] CAI Deng， ZHANG Chiyuan， HE Xiaofei. Unsupervised feature 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 regularized discriminative feature selection for unsupervised learning [C]// Proceedings of the Twenty?Second International Joint Conference on Artificial Intelligence. Barcelona， Spain： [s. n.]， 2011： 1589?1594.

[7] NIE Feiping， HUANG Heng， CAI Xiao， et al. Efficient and robust feature selection via joint [l2，1]?norms minimization [C]// Proceedings of the 2010 Advances in Neural Information Processing 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 Systems， 2013， 54： 199?206.

[9] WRIGHT J， YANG A Y， GANESH A， et al. Robust face recognition via sparse representation [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2009， 31（2）： 210?227.

[10] YANG Jian， CHU Delin. Sparse representation class?er steered discriminative projection [C]// Proceedings of the 20th International Conference on Pattern Recognition. Istanbul， Turkey： [s. n.]， 2010： 694?697.

[11] LU Canyi， HUANG Deshuang. Optimized projections for sparse representation based classi?cation [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 solution [J]. Communications on Pure and Applied Mathematics， 2006， 59（6）： 797?829.

[13] CANDES E， ROMBERG J， TAO T. Stable signal recovery from incomplete and inaccurate measurements [J]. Communications on Pure and Applied Mathematics， 2006， 59（8）： 1207?1223.

[14] CHEN S S B， DONOHO D L， SAUNDERS M A. Atomic decomposition by basis pursuit [J]. Society for Industry and Applied Mathematics Review， 2001， 43（1）： 129?159.

[15] DONOHO D L， TSAIG Y. Fast solution of [l1]?norm minimization 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/Data/MLData.html.

[18] BECK A， TEBOULLE M. A fast iterative shrinkage?thresholding algorithm for linear inverse problems [J]. SIAM Journal on Imaging Sciences， 2009， 2（1）： 183?202.