摘要:针对流形嵌入降维方法中在高维空间构建近邻图无益于后续工作，以及不容易给近邻大小和热核参数赋合适值的问题，提出一种稀疏判别分析算法（SEDA）。首先使用稀疏表示构建稀疏图保持数据的全局信息和几何结构，以克服流形嵌入方法的不足；其次，将稀疏保持作为正则化项使用Fisher判别准则，能够得到最优的投影。在一组高维数据集上的实验结果表明，SEDA是非常有效的半监督降维方法。
关键词:判别分析；稀疏表示；近邻图；稀疏图�
中图分类号: TP391.4 文献标志码:A
�
Sparse discriminant analysis
�
CHEN Xiao.dong�1�*, LIN Huan.xiang�2
�1．School of Information and Engineering, Zhejiang Radio and Television University, Hangzhou Zhejiang 310030, China�;��
2．School of Information and Electronic Engineering,Zhejiang University of Science and Technology, Hangzhou Zhejiang 310023, China
Abstract:
Methods for manifold embedding exists in the following issues: on one hand, neighborhood graph is constructed in such the high-dimensionality of original space that it tends to work poorly; on the other hand, appropriate values for the neighborhood size and heat kernel parameter involved in graph construction is generally difficult to be assigned. To address these problems, a novel semi-supervised dimensionality reduction algorithm called SparsE Discriminant Analysis (SEDA) is proposed. Firstly, SEDA sets up a sparse graph to preserve the global information and geometric structure of the data based on sparse representation. Secondly, it applies both sparse graph and Fisher criterion to seek the optimal projection. Experiments on a broad range of data sets show that SEDA is superior to many popular dimensionality reduction methods.
Methods for manifold embedding have the following issues: on one hand, neighborhood graph is constructed in such high.dimensionality of original space that it tends to work poorly; on the other hand, appropriate values for the neighborhood size and heat kernel parameter involved in graph construction are generally difficult to be assigned. To address these problems, a new semi.supervised dimensionality reduction algorithm called SparsE Discriminant Analysis (SEDA) was proposed. Firstly, SEDA set up a sparse graph to preserve the global information and geometric structure of the data based on sparse representation. Secondly, it applied both sparse graph and Fisher criterion to seek the optimal projection. The experimental results on a broad range of data sets show that SEDA is superior to many popular dimensionality reduction methods.�Key words:
discriminant analysis; sparse representation; neighborhood graph; sparse graph
�
0 引言�
在信息检索、文本分类、图像处理和生物计算等应用中，所面临的数据都是高维的。由于维数灾难，直接处理这些数据变得非常困难�［1］。最常用的方法就是通过使用降维（Dimensionality Reduction，DR）技术来降低这些高维数据的维数。降维的目的就是在低维空间中尽量真实地刻画输入数据，减少它们的复杂性，提高计算效率。基于降维后所期望得到的信息，现有的降维可以分为三类：判别方法�［1-8］、几何方法�［9-11］和基于判别和几何方法�［12-14］。基于可获得的先验信息，降维方法又可分为� ［15］：监督方法�［8,12,16-17］和无监督方法�［1,2,4,6,9,11］。�
上述多数方法都可以被统一到图嵌入框架中�［8,11］，因此，图的构建成为这些方法的核心问题。事实上，对这些方法来说，构建一个高质量的图仍是个开放问题�［17］。目前，流形嵌入方法（manifold embedding）使用�k近邻技术和ε�球近邻技术来构建近邻图（neighborhood graph）�［9,18］。一旦这种近邻图被构建，边的权值由Gaussian函数或者局部重构关系来决定。这种近邻图构建方法通常存在以下几个问题�［19］：首先，大多数算法中的近邻图是预先构建，因此，它未必有益于后续的降维工作；其次，近邻图通常是在高维空间中构建，这样构建的图在后续的工作中表现差强人意；最后，近邻图需要的两个参数，即近邻的大小�（k）和热核参数（σ），通常不容�易赋给合适的值。�
因此，在降维方法中研究图的构建显得尤为重要。另外，多数无监督降维方法在寻找投影方向过程中忽略了部分先验信息的作用，以至于它们往往不能得到最优的投影�［3,14］。监督降维方法需要大量有标记样本作训练样本，限制了它的应用�［14］。最近，半监督降维方法得到越来越多研究人员的关注�［3,5,7,10,13-15］ 。这类方法是利用少量有标记样本和大量无标记样本寻找最优的投影方向。与监督方法相比，它更适合实际应用，与无监督方法相比，有较高的效率。�
然而，现有的一些半监督降维方法通常面临和流形嵌入方法相同的问题，即近邻图构建。如:半监督判别分析算法（Semi.Supervised Discriminant Analysis，SDA）�［10］和半监督局部Fisher判别分析算法（Semi.supervised Local Fisher Discriminant Analysis，SELF）�［14］。为了解决这些问题，本文提出一个新颖的稀疏判别分析（SparsE Discriminant Analysis，SEDA）算法，SEDA通过使用稀疏重建技术解决流形嵌入方法中近邻图构建问题。同时，新方法在降维过程中又能同时利用有标记和无标记样本寻找投影，提高了算法效率。具体地说，SEDA有以下4个特点。�
1）SEDA拥有同其他半监督降维方法（如SDA、SELF）相同的特征。如，它是线性的方法，也容易地拓展到非线性空间。因此，可以解决外样本问题。另外， SEDA使用稀疏重构技术来保存样本的几何结构，这有利于降低算法的计算复杂度。�
2）SEDA不需要调节模型参数，如热核宽度和近邻参数。通常，这些参数需要使用交叉验证技术给它们分配数值，但交叉验证方法既需要训练样本，还非常耗时。相比之下，SEDA不需要处理这些参数。因此，它简单实用。�
3）与Fisher判别分析（Fisher Discriminant Analysis，FDA）�［16］相同，SEDA是一个全局算法。但不同的是，SEDA使用稀疏表示来重构样本，以至于它包含了局部几何信息。�
4）由于SEDA在求解投影向量过程中使用了有标记和无标记样本，因此，它与流形嵌入方法相比有好的效率。同时，SEDA可以容易地拓展到监督降维中。
1 相关工作�
根据先验信息的不同类型，半监督降维方法一般可分为两类：一类是使用有类标号的样本来引导降维过程�［10,14,20,22-23］；另一类是使用成对约束（must.link和cannot.link）来指导降维�［3,5,7,10,15,20-21］。事实上，使用有类标号的样本可以得到成对约束，但不能由成对约束得到样本的类标号。因此，这两类方法之间存在着一定的相关性。下面简单回顾三个有代表性的半监督降维算法。�
1.1 半监督判别分析�
半监督判别分析算法（SDA）�［10］是一个较为流行的基于样本标号的半监督降维方法。它使用基于FDA判别准则寻找投影，其实质是FDA的半监督化。SDA首先需要刻画高维空间中近邻样本之间的关系。详细地说，给定一个样本集�X，构建一个k近邻的近邻图G来建模近邻样本之间的关系。如果图中两个顶点x�i和x�j互为近邻，那么它们之间就存在一条边，相应的权值矩阵为P，其定义如下：�
根据上述理论分析，得到如下结论。�
1）从算法1不难发现，SEDA简单且易执行。自从Liu等�［26］改进Lasso算法以后，优化�l�1�范式的计算复杂度已经减少到线性时间。因此，第一步较容易地计算稀疏权值矩阵�S。第三步借助于谱回归�［10］计算出投影向量，并使用�Nystrom�［27］�方法解决大规模数据降维问题。�
2）对于每一个样本x�i，利用稀疏约束，其重构都是使用样本集的所有样本。因此，通过使用稀疏权值矩阵S，�SEDA�能自然地保持判别信息。�
�
3）不同于现有半监督算法使用局部保持技术来求解投影， SEDA使用稀疏保持投影作为正则化项寻找投影方向。所以，它不需要调节模型参数，如热核宽度和近邻参数。�
3 实验�
下面使用8个真实数据来验证文中所提出稀疏判别分析算法（SEDA）。为了综合评价新算法的性能，使用5个最新提出的典型算法与SEDA进行对比。算法分别如下。�
1）局部保持投影（LPP）�［9］。是一个无监督降维算法，它使用近邻图来指导降维。�
2）稀疏保持投影（Sparsity Preserving Projection，SPP）�［4］。是无监督降维算法，它使用稀疏表示寻找投影。�
3）半监督判别分析（SDA）�［10］。基于Fisher标准的半监督降维算法，构建近邻图作为正则化项。�
4）半监督局部Fisher判别分析（SELF）�［14］。联合FDA和LPP进行降维的一个半监督算法。�
5）基于流形学习的半监督降维算法（Semi.Supervised Dimensionality Reduction Framework，SDRF）�［23］。一个最新提出的半监督降维框架。�
为了公平比较，在使用上述降维方法投影数据到低维空间后，使用最近邻分类方法来计算各个算法的性能。6个算法在每个数据集运行40次，取平均值作为最终的分类性能。�
3.1 在一组高维数据集上的实验�
首先使用4个高维数据集进行实验，它们分别是：Reuters是一个文本数据集，它包含135类21�578个文本。在本实验中，选择常用的18类6�750个样本；WebACE 包括20个不同标题2�340个文本；WebKB包含7类（student，faculty，staff，course，project，department 和other）8�280个文本；WebKB4是WebKB的一个子集。4个数据集的属性如表1所示。实验中，有标号样本数分别选择为每个数据集样本数的5%，10%，15%和20%。具体实验结果如图1～4所示。�
3.2 在人脸数据集上的实验�
下面进一步通过4个人脸数据集（ORL，AR，CMU PIE和YaleFaceB）来验证SEDA算法的性能。首先，ORL数据集由400幅不同表情和光照的人脸图像组成，其中每个人有10幅图像。在实验中，ORL数据集人脸图像被设置成大小32×32像素的256级灰度图像。其次，AR数据集由126类4�000幅人脸图像组成。在本实验中，选择100个人（50个男人和50个女人）2�600幅人脸图像，图像设置成66×48大小的灰度图像；再次，CMU PIE人脸数据集包括68个人41�368幅图像。选择5组接近正面姿态的图像（C05，C07，C09， C27和 C29）。对于每一类，选择170幅32×32灰度图像进行实验。最后，YaleFaceB数据集包括38个人16�128幅人脸图像。从每个人脸库里选择120幅32×32灰度图像。在实验中，分别从每个人脸数据集里选择10%，20%和30%的样本作为有标号样本，实验环境和3.1节设置相同。实验结果如表2～4所示。�
3.3 实验讨论�
通过上面的理论分析以及6个算法在8个高维数据集上的实验，可以得出以下结论。�
1）SEDA在文中所用的大多数数据集上，包括3个高维数据集和4个人脸数据集，无论是在少量标号样本还是大量标号样本环境下，都能取得比其他5个算法好的性能。其中，在4个人脸数据集上，SEDA的优势更加明显。因此，可以得到初步的结论：文中所提出的SEDA是一个相对有效的半监督降维算法。�
2）尽管在WebACE数据集上，SDRF能够得到较好的结果，但在其他数据集上，它没有SEDA执行得好，而且与其他数据集相比也没有明显优势。事实上，尽管SDRF试图用Hadamard动力算子（Hadamard Power Operator）技术提高无标号样本的功效，但其实质还是构建近邻图来指导降维。因此，SDRF的效果并不令人满意。�
3）SDA和SELF需要构建近邻图来降维，所以分配合适的参数，对构建近邻图至关重要。另一方面，近邻图的构建是在原空间进行的，当维数特别高时，构建的近邻图往往无益于降维。因此，在有标记样本较少时，SDA和SELF的性能还没有SPP好。但当标记样本数量逐渐增多时，SDA和SELF的性能要好于SPP。�
4）SPP的性能比LPP好，原因是前者使用稀疏表示进行投影时，既保存了数据的全局信息，也兼顾了数据的几何结构。这也自然地解释了SEDA为什么性能更好的原因。�
4 结语�
本文提出一种简单而有效的半监督稀疏判别分析算法（SEDA）。具体地说，基于稀疏表示，SEDA搭建的稀疏图得到稀疏重构权值；其次，SEDA把稀疏保持作为正则化项使用Fisher判别准则来寻找最优的投影。实验结果表明，SEDA的性能不仅优于最新提出的几个流形的半监督降维方法SDA，SELF和SDRF，更优于无监督降维方法。�参考文献:
［1］
YE J, ZHAO Z, WU M. Discriminative K.Means for clustering ［EB/OL］.[2011-05-01].http://www.kyb.mpg.de/publications/attachments/NIPS2007-Ye_4710[0].pdf.
［2］
CHEN H T, CHANG H W, LIU T L. Local discriminant embedding and its variants［C］// CVPR�05: Proceedings of the 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. Washington, DC: IEEE Computer Society, 2005:846-853.
［3］
尹学松, 胡恩良, 陈松灿. 基于成对约束的半监督判别分析［J］. 软件学报, 2008, 19(11): 2791-2802.
［4］
QIAO L, CHEN S, TAN X. Sparsity preserving projections with applications to face recognition［J］. Pattern Recognition,2010,43(1):331-341.
［5］
YIN X, HU E. Distance metric learning guided adaptive subspace semi.supervised clustering［J］. Frontiers of Computer Science in China, 2011, 5(1): 100-108.
［6］
HOI S C H, LIU W, LYU M R, et al. Learning distance metrics with contextual constraints for image retrieval［C］// CVPR�06: Proceedings of the 2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. Washington, DC: IEEE Computer Society,2006:2072-2078.
［7］
陈小冬, 尹学松, 林焕祥. 基于判别分析的半监督聚类方法［J］. 计算机工程与应用, 2010, 46(6): 139-143.
［8］
YAN S, XU D, ZHANG B, et al. Graph embedding and extensions: A general framework for dimensionality reduction［EB/OL］.[2011-08-01].http://www.ntu.edu.sg/home/dongxu/TPAMI.GE.pdf .
［9］
HE XIAO.FEI, NIYOGI P. Locality preserving projections［EB/OL］.[2011-08-01]. http://people.cs.uchicago.edu/～xiaofei/conference.24.pdf.
［10］
CAI D, HE X, HAN J. Semi.supervised discriminant analysis［EB/OL］.[2011-08-01]. http://www.cs.uiuc.edu/～hanj/pdf/iccv07_dengcai_SDA.pdf.
［11］
CAI DENG, HE XIAO.FEI, HAN JIA.WEI. Sparse projections over graph［EB/OL］.[2011-09-01]. http:// www.省略/Papers/AAAI/2008/AAAI08.097.pdf .
［12］
SUGIYAMA M. Dimensionality reduction of multimodal labeled data by local fisher discriminant analysis［J］.The Journal of Machine Learning Research, 2007,8(5):1027-1061.
［13］
尹学松, 胡恩良. 半监督局部维数约减［J］. 中国图象图形学报, 2011, 16(9): 2121-2131.
［14］
SUGIYAMA M, NAKAJIMA T, SESE J. Semi.supervised local Fisher discriminant analysis for dimensionality reduction［J］. Machine Learning, 2010:78(1/2):35-61.
［15］
尹学松, 胡恩良. 半监督正则化学习［J］.小型微型计算机系统, 2010, 31(12):2389-2393.
［16］
BELHUMEUR P, HSSPANHA J, KRIEGMAN D. Eigenfaces vs. Fisherfaces: Recognition using class specific linear projection［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence, 1997,19(7): 711-720.
［17］
LIU W, CHANG S.F. Robust multi.class transductive learning with graphs［C］// Proceedings of IEEE Conference on Computer Vision and Pattern Recognition. [S.l.]:IEEE, 2009:8.
［18］
BELKIN M, NIYOGI P. Laplacian eigenmaps for dimensionality reduction and data representation[J]. Neural Computation, 2003,15 (6):1373-1396.
［19］
ZHANG L, QIAO L, CHEN S. Graph.optimized locality preserving projections［J］. Pattern Recognition, 2010, 43(6):1993-2002.
［20］
TANG W, XIONG H, ZHONG S, et al.Enhancing semi.supervised clustering: A feature projection perspective［C］// KDD�07: Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM,2007:707-716.
［21］
XIANG S, NIE F, ZHANG C. Learning a Mahalanobis distance metric for data clustering and classification［J］. Pattern Recognition, 2008,41(12):3600-3612.
［22］
SONG Y, NIE F, ZHANG C, et al.A unified framework for semi.supervised dimensionality reduction［J］. Pattern Recognition, 2008,41(9): 2789-2799.
［23］
CHATPATANASIRI R, KIJSIRIKUL B. A unified semi.supervised dimensionality reduction framework for manifold learning［J］. Neurocomputing, 2010, 73(3): 1631-1640.
［24］
JOLLIFFE I. Principal component analysis［M］. 2nd. Berlin: Springer,2002.
［25］
WRIGHT J, YANG A, SASTRY S, et al. Robust face recognition via sparse representation［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence, 2009, 31(2):210-227.
［26］
LIU J, YE J. Efficient euclidean projections in linear time［EB/OL］.[2011-06-01].省略/archive/icml2009/papers/123.pdf.
［27］
ZHANG K, KWOK J T. Density.weighted Nystr�m method for computing large kernel eigensystems［J］.Neural Computation,2009, 21(1):121-146.