稀疏表示保持的鑒別特征選擇算法

夏廣勝　嚴慧

摘 要： 稀疏表示作為一種基于部分數據的表示，已經吸引了越來越多的關注，并廣泛應用于模式識別和機器學習領域。提出一種新的算法，稱為稀疏表示保持的鑒別特征選擇（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.