基于低秩评分的非监督特征选择算法

谢乃俊，杨国亮，罗 璐，梁礼明

（江西理工大学 电气工程与自动化学院，江西 赣州341000）

0 引 言

根据评判数据特征重要性时是否利用了类别标签信息，特征选择算法可以分为有监督、无监督和半监督3类方法。有监督特征选择算法主要是依据数据的特征与类别标签信息之间的相关程度来选择特征，经典的算法有fisher评分（fisher score，FS）［1］。现实中，数据的类别标签信息很少，人为地去获取数据的类别标签非常耗时、代价昂贵，因此人们提出了半监督和无监督特征选择算法。方差评分 （variance data，VD）和拉普拉斯评分 （Laplacian score，LS）属于非监督方法。在方差评分算法中，代表信息量多的特征点被选择；拉普拉斯评分算法在考虑信息量的同时引入了局部信息描述能力约束项来对特征进行评分。半监督方法则利用部分类别标签作为数据的一种先验信息，文献［2］中提出了 一 种 半 监 督 的 约 束 评 分 （constrain score，CS），同时利用无标签的数据和带有标签的数据来进行数据的特征选择，提高算法的性能。随后，文献 ［3］中将稀疏表示系数引入特征的评分标准中，提出了无监督的稀疏评分特征选择方法。然而，稀疏表示理论方法为了使数据的表示稀疏满足稀疏性，需要一个完备的词典，怎样构建有效的数据字典存在很大的挑战。低秩表示理论是在稀疏的基础上发展而来的最新的数据表示方法，它通过最小化核范数来诱导数据在字典下的低秩结构，能够有效揭示数据的全局结构信息。目前，低秩表示在子空间恢复［4］、运动目标检测［5］、特征提取［6］等任务中得到成功的运用。本文运用具有干净字典约束的低秩表示模型学习数据的全局连接权值矩阵，揭示数据的全局结构和鉴别信息，利用该权值矩阵代替拉普拉斯评分机制中的局部连接矩阵，构建了一种低秩评分机制，用于非监督的特征选择。该算法对那些揭示数据全局结构信息和鉴别信息能力较强、表达信息量较多的特征赋予更大的重要性。

1 低秩连接权值矩阵

数据的连接权值矩阵一定程度上能够揭示数据间的某种关系，利用不同方法构建的连接权值矩阵所表示的数据结构信息不同。低秩表示模型能够学习出数据在字典下的最低秩表示，这种表示能够揭示数据的全局结构信息，同时又有一定的数据鉴别表达能力［7］。本节在低秩表示模型中引入干净字典约束和低秩系数对称性约束构建低秩连接权值矩阵，揭示数据间的结构信息。

1.1 干净字典约束的低秩表示

假设数据集合X ＝［x1，x2，…，xn］∈Rd×n，采样于l个独立的子空间（ln），d代表数据的维数，n表示数据点的个数。现实数据往往受噪声的干扰，假设采样数据集X由原始干净数据D 和噪声干扰数据E 叠加而成，因此，数据X 可以表示成X ＝D＋E。由ln可知，“干净”数据集中某些数据点来自相同的子空间，彼此间具有类似的属性，所以干净数据矩阵D 具有低秩性特点，而噪声干扰数据往往满足稀疏性。通过低秩性和稀疏性约束，可以构建如下的优化目标函数来恢复出 “干净”数据成分和噪声成分

式中：λ＞0是噪声惩罚参数，平衡噪声对干净数据的影响。上述优化问题是典型的非凸优化问题，在鲁棒主成分分析［8］中，常常将式 （1）转换为具有封闭解的松弛凸优化问题

假设数据集D 中的任意一列di能够由数据本身D 中的每一列线性 组合表示成di＝Dzi，D ＝［d1，d2，…，dn］∈Rd×n中每一列di代表一个数据点向量，Zi＝Rn×l是字典中所有列对数据di线性表示的系数。由于所有数据都是在相同的字典下进行线性表示，数据集D 具有低秩性，所以在表达式D＝DZ 中，系数矩阵Z 同样具有低秩这一特性。考虑一对数据点（di，dj）两者互相表示时具有对等性，我们引入对称约束条件Z ＝ZT，因此，可以通过求解如下优化问题得到数据的低秩表示系数

式 （4）的最优解Z＊是数据在干净字典约束下的最低秩表示，Z＊＝［，，…，］。数据在字典下的低秩表示是一种全局联合的表示方式，具有揭示数据全局结构信息的表达能力，能够自动的学习出数据间的相关性，使得具有相近属性的数据在相互表示的时候提供较大的权值。

1.2 低秩模型求解

增广拉格朗日乘子（augmented Lagrange multipiler，ALM）法分为精确增广拉格朗日 （EALM，exact ALM）方法和非精确增广拉格朗日 （IALM，inexact ALM）方法也称为交替方向法 （ADM）。Lin在文献 ［11］中证明了非精确增广拉格朗日方法能够有效的解决式 （2），下面我们详细的介绍运用ADM 方法求解干净字典约束的低秩表示模型式 （4）。首先参考文献 ［12］，介绍一种优化问题求解定理。

定理1 假设存在如下优化问题

其中M ＝UΣVT代表数据矩阵M 的奇异值分解，式 （5）的最优解为

式中：Σ1——数据矩阵M 的奇异值大于的奇异值，U1、V1——相应的奇异向量。

通过引入拉格朗日乘子Y 消除式 （4）中的等式约束X ＝D＋E，保留等式约束D ＝DZ 和Z ＝ZT，式 （4）转换成

利用迭代方法求解最优的（D，Z，E，Y），由于无法一次性得出所有参数的最优解，采用交替求解策略，固定其他参数，分别对每个参数独立的进行更新。

（1）更新D，Z

为了更新（D，Z），固定参数E，Y，更新方法如下

根据定理1可知，上述问题的最优解为

（2）更新E

固定参数D，Z，Y，对参数E 进行更新

［13］可知：参数Ek＋1的最优化解为Ek＋1＝其中，当时，算子Ωε（X）的第i列为否则，Ωε（X）的第i列为零向量。完整的迭代求解过程列在算法1中。

1.3 数据的低秩权值矩阵

数据的图结构能够揭示数据集中隐含的本质结构信息，不同的构图方法揭示的数据信息结构也不同。传统的K 邻域和ε邻域图构建反映了数据集在欧式空间中局部结构关系，揭示的是数据的局部结构信息。数据的局部信息结构被证明能够很好的揭示数据的流形结构，但是局部邻域图的构建过程面临邻域参数k 的选择问题。在构图方法中参数k对图的好坏起到决定性作用，现有方法往往通过经验设置k值，没有一种好的有效的机制来对进行适应性计算。基于稀疏表示的l1图从数据全局角度考虑来揭示数据点间的关系，通过学习出数据在字典下的稀疏表示来揭示数据的全局结构信息。但是由于稀疏性约束条件，往往只有很少的一部分全局信息被揭示，而且，当数据存在噪声干扰时，l1图揭示数据信息的能力会受到影响。

低秩图是在上述干净字典约束的低秩表示模型的基础上构建了揭示数据全局信息的一种结构图。由于干净字典约束低秩表示模型学习的是数据在干净字典下的全局联合线性表示，能够揭示数据间的全局结构信息，同时干净字典约束还能消除噪声数据的干扰。因为数据被字典联合的全局表示，低秩模型学习得到的全局连接权值相似度矩阵中存在密集的数值很小的连接值，这些值对全局信息的揭示不起作用，所以，将每个数据的低秩表示系数归一化

（zi＝zi/zi2）并设置一个阈值，使得阈值以下的系数为零。数据的低秩权值矩阵W 定义为

2 低秩评分

有一数据集X ＝［x1，x2，…，xn］∈Rd×n，d表示数据特征的个数，n为数据样本的个数。令fri是第i个样本数据xi的第r个特征为反映某个特征所包含信息量大小的能力，定义如下的数据特征方差模型

低秩评分是在方差模型的基础上保持了数据样本点间的全局结构信息提出的一种特征评分算法，选择出那些包含信息量多，全局结构信息表达能力强的特征。低秩评分模型如下

式中：Wij——数据样本点间的相似度关系，通过上述低秩表示模型学习得出的，具有全局数据表示能力，权值的Wij表示数据样本点（i，j）间的相似关系，具有大权值的样本点来自同类的概率大，且具有较好的鉴别表示能力。Vs（r）表示特征的方差估计，特征方差估计的本质是将特征投影到最大方差的方向上，在该方向选择出满足条件的特征。大的方差说明数据特征在不同环境下属性的表现区分性大，包含的信息量丰富，区分不同属性事物的能力强。相反，小方差的特征对不同属性事物区分发挥不了多大的作用。从式 （14）中我们能够观察出，如果某一特征的Vs（r）和Wij越大，（fri－frj）越小，那么该特征最后的低秩评分结果较小，特征表达信息的能力强。

经过下面简单的推导可以得出

由此，低秩评分模型式 （14）转换为

式中：L——拉普拉斯矩阵L ＝D－W ，D 为一对角矩阵，Dii＝Wij。数据特征的低秩评分算法过程见算法2。

3 实验分析

为了验证提出的低秩评分算法的有效性，我们在Iris鸢尾花数据集、PIE和ORL人脸数据集上分别进行实验并同传统的特征选择算法进行比较。实验先通过特征选择算法在原始特征上选出一个子集，然后在新的特征子集上进行聚类或分类实验。在PIE数据集上进行数据的聚类实验，在ORL库上进行分类实验。低秩评分算法属于非监督的特征选择算法，因此选择同已存在的方差评分，拉普拉斯评分和稀疏评分3 种非监督的特征选择算法进行比较分析，其中拉普拉斯算法中的邻域参数设置为k＝5。

3.1 Iris鸢尾花数据集

鸢尾花数据集包含3种类别共150 个数据样本点，每种类别的数据样本个数为50，每个数据样本点含有4个数据特征。

我们分别选择数据的单个特征利用简单的最近邻分类器对数据进行分类，数据中第1，2，3，4个特征对应的分类识别率分别为：r1＝0.38，r2＝0.20，r3＝0.84，r4＝0.86。表明不同特征在分类中发挥的作用按降序排列依次为：F4，F3，F1，F2，Fi表示第i个特征。

表1中列出了数据4个特征在不同评分算法下的最后评分结果。在方差评分中，得分越高说明该特征的作用越大，其他几种算法则是得分越小的重要性越大。从表1中列出了4种算法学习出的特征重要性排位结果：方差评分算法为F3，F1，F4，F2，低秩评分算法和其他两种算法都是F4，F3，F1，F2。对比上面分别用每个特征进行分类实验可知，在特征选择效果上而言，方差评分效果不佳，而低秩评分算法和其他两种算法对特征重要性评价更接近真实情况。另外，在利用不同算法对数据特征打分后，按其重要性选择不同的特征组合来进行实验，选取数据中的不同特征组成两个特征子集合，分别为特征子集（F1，F2），（F4，F3），将特征集中的两个特征分别视为x 和y 轴，得到数据特征鉴别能力的可视化图，结果如图1所示。结果同样证明，特征F4，F3的对数据的鉴别表达能力要强于特征F1，F2。

表1 几种评分算法对不同特征的评分结果

图1 Iris数据2维可视化

3.2 PIE人脸数据集

PIE人脸数据集中收集了68个人的41368张人脸数据，包含每个人在不同光照，表情和姿态条件下的数据，来自卡内基梅隆人脸表情数据库。在本文的实验中，保持人脸的表情和姿态条件不变，选取每个人的21张不同光照下的人脸数据组成实验数据集。每张人脸数据都被裁剪为32×32像素大小的尺度。在PIE 数据集上，先利用不同算法对特征进行选择，然后通过K 均值聚类算法对新的特征数据集聚类。最后选择归一化互信息度量标准 （normalized mutual information metric，NIM）来评价几种不同特征选择算法在聚类中的表现。NIM 的基本思想是通过比较数据点的真实标签信息和聚类得到的标签信息来评价实验的表现。在PIE人脸数据上低秩打分中惩罚参数设置为λ＝0.5。

为了得到可靠的实验结果，在数据集的68个类别子集上选取不同的类别数进行实验 （类别数分别选取K ＝5，10，30，68）。在给定一个特定的类别数K 后，下面的过程被重复执行20次，求解20次的平均表现性能。在68类数据中随机的选择K 类数据，运用不同的特征评分方法对每个特征进行打分，学习出其重要性排序；选择前d 个特征组成新的特征数据进行10次K 均值聚类实验，选出最好的聚类效果。图2显示选取不同数量特征时，几种特征重要性评分算法在聚类中的表现，K 表示参与实验的类别数，横坐标轴表示选择特征的维数，纵坐标表示分类的NIM 数值，NIM 数值越大分类效果越好。通过比较结果表明，在所有的情况下本文提出的低秩评分算法在聚类实验中取得最好的表现。在类别数K 选择为5类和10类的情况下，特征数量选择为300个以内时，低秩评分算法和稀疏评分算法的表现相当的稳定，而拉普拉斯评分在100个特征数以内，聚类表现出现一个上升阶段，这说明，利用数据全局结构信息的评分机制比利用数据局部结构信息的评分机制更能揭示特征点的重要性。随着类别数的增多，不同特征维数下的方差评分聚类表现反而越来越稳定，不会出现类似5类中前200个特征数内的那种大的波动，表明利用数据方差信息的评分机制需要更多数据来揭示数据特征的重要性。

图2 几种算法在不同特征数下的聚类表现

特征选择的主要目的是为了减少数据的维数，使得某些算法在低维数据上能够快速有效的执行，同时又不影响数据本质属性的表达能力。为了验证特征选择算法的性能，表2列出了4种算法在选取不同特征个数下的聚类表现结果，表中数值表示算法在聚类表现中的NIM 值。对比几种算法的表现可以看出：①所有算法在选择特征数量适当时，聚类效果更好，说明特征选择算法能够有效的提高数据聚类算法的聚类能力；②低秩评分特征选择算法在选择不同特征时的聚类表现都强于其他几种算法，尤其在特征选择数量少的时候，优势更加的明显，证明了低秩特征选择算法在数据聚类中相比于其他算法更具有优势。为了更加直观的揭示各种算法在聚类中表现不同的原因，在人脸图像中分别标注了特征重要性排序后的前50、100、150、200个特征的几何位置分布如图3所示。从图中能够直观的看出，特征通过方差评分算法对其重要性排序后，排序靠前的200个特征点主要分布在人脸图像的四周和中间鼻子位置；拉普拉斯评分算法和稀疏评分算法的结果显示重要性前200个特征主要是在人脸的眼睛，鼻子，嘴巴区域分散的分布；低秩评分算法则主要集中在眼睛，嘴巴和鼻子区域，从直观的认知中可知，人脸特征主要是由五官来决定的，图3所示的结果能够直观的说明低秩评分取得较好表现的原因。

表2 不同算法聚类的NIM 评价结果

3.3 ORL人脸数据集

ORL人脸库是由英国剑桥Olivetti实验室提供，数据集包含40个人共400张图片，收集了每个人在不同时期，不同表情和不同姿态下的10张人脸图片。每张人脸数据都经过位置校正预处理并被裁剪为32×32像素大小的尺度。实验中，首先，我们分别在每类中选择不同数量（l＝2，4，6，8）数据样本参与学习，通过不同打分机制得到特征点的重要性排序，该数据库上低秩评分机制中的参数设置为λ＝1.6。然后选择原始数据的前d个特征子集组成新的数据表示原始数据，利用最近邻分类器对数据分类。

几种算法在不同特征数下的分数表现如图4所示。

图3 不同算法评价的重要特征几何分布

图4 几种算法在不同特征数下的分类表现

图4中给出了不同打分算法给数据特征评分后，按特征重要性选择不同的特征数进行最近邻分类的结果，L 表示每类参与学习的样本数。从实验结果中能够看出低秩评分算法在不同的数据参与训练情况下都取得了比其他算法要好的效果。不同算法随着参与训练的样本增多时取得的分类效果也有所提升，但是相对于在PIE 人脸数据库上取得的效果来说，低秩评分效果的优势较其他几种算法而言没有那么的明显，主要原因是ORL数据库中，人脸图像在姿态上存在较大的差异导致数据的低秩这一特性受到一定程度的破坏，影响了低秩评分的效果。图5中标记了二维人脸特征的重要性信息，从左向右依次是取训练样本数为2，4，6，8的评分结果，图中越亮的位置表示该特征越重要。从图5中能够直观的看出，经过低秩评分机制获得的重要性特征集中分布在人脸的嘴巴，鼻子和眼睛部位，说明低秩评分机制能够更好的揭示特征重要性的真实情况。

图5 特征重要性分布

4 结束语

本文提出一种基于低秩评分的非监督特征选择算法。算法综合考虑了数据特征信息量大小的表达能力，揭示数据全局结构信息和鉴别信息的能力以及相同情况下特征属性相近性的能力，因此，通过低秩评分特征选择算法选择出的重要性特征能够很好的揭示数据的本质特征信息。同已经存在的方差评分，拉普拉斯评分和稀疏评分特征选择相比较，低秩评分在数据聚类和分类任务中获得了更好的表现。尤其在数据类别较多和选择特征数量较少的情况下，优势更加明显，体现了低秩评分特征选择比传统的特征选择算法能够更好地提升传统模式识别中聚类和分类算法的性能。

参考文献：

［1］Gu Q，Li Z，Han J.Generalized fisher score for feature selection ［C］//Proceedings of the International Conference on Uncertainty in Articial Intelligence，2011.

［2］Zhang D，Chen S，Zhou Z H.Constraint score：A new filter method for feature selection with pairwise constraints［J］.Pattern Recognition，2008，41 （5）：1440－1451.

［3］SU Yaru.Research on dimensionality reduction of high－dimensinal data［D］.Hefei：University of Science and Technology of China，2012 （in Chinese）.［苏雅茹.高维数据的维数约简算法研究 ［D］.合肥：中国科学技术大学，2012.］

［4］Liu G，Lin Z，Yan S，et al.Robust recovery of subspace structures by low－rank representation ［J］.Pattern Analysis and Machine Intelligence，2012，35 （1）：172－184.

［5］Shen X，Wu Y.A unified approach to salient object detection via low rank matrix recovery ［C］//IEEE Conference on Computer Vision and Pattern Recognition.IEEE，2012：853－860.

［6］Zhang N，Yang J.Low－rank representation based discriminative projection for robust feature extraction ［J］.Neurocomputing，2013，111：13－20.

［7］Zhuang L，Gao H，Huang J，et al.Semisupervised classification via low rank graph ［C］//Sixth International Conference on Image and Graphics.IEEE，2011：511－516.

［8］Candès E J，Li X，Ma Y，et al.Robust principal component analysis？［J］.Journal of the ACM，2011，58 （3）：1－11.

［9］Recht B，Fazel M，Parrilo P A.Guaranteed minimumrank solutions of linear matrix equations via nuclear norm minimization［J］.SIAM Review，2010，52 （3）：471－501.

［10］Xu H，Caramanis C，Sanghavi S.Robust PCA via outlier pursuit［J］.Systems Advances in Neural Information Processing Systems，2010，23：2496－2504.

［11］Lin Z，Chen M，Ma Y.The augmented Lagrange multiplier method for exact recovery of corrupted low－rank matrices［R］.UIUC Technical Report UILU－ENG－09－2215，2009.

［12］Vidal R，Favaro P.Low rank subspace clustering（LRSC）［J］.Pattern Recognition Letters，2014，43：47－61.

［13］Liu G，Lin Z，Yu Y.Robust subspace segmentation by lowrank representation ［C］//Proceedings of the 27th International Conference on Machine Learning，2010：663－670.