稀疏判别分析摘要:针对流形嵌入降维方法中在高维空间构建近邻图无益于后续工作，以及不容易给近邻大小和热核参数赋合适值的问题，提出一种稀疏判别分析算法（seda）。
首先使用稀疏表示构建稀疏图保持数据的全局信息和几何结构，以克服流形嵌入方法的不足；其次，将稀疏保持作为正则化项使用fisher判别准则，能够得到最优的投影。
在一组高维数据集上的实验结果表明，seda是非常有效的半监督降维方法。
关键词:判别分析；稀疏表示；近邻图；稀疏图sparse discriminant analysischen xiao.dong1*, lin huan.xiang 21．school of information and engineering, zhejiang radio and television university, hangzhou zhejiang 310030, china;2．school of information and electronicengineering,zhejiang university of science and technology, hangzhou zhejiang 310023, chinaabstract:methods for manifold embedding exists in the followingissues: 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 dimensionalityreduction 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 graph0 引言在信息检索、文本分类、图像处理和生物计算等应用中，所面临的数据都是高维的。
由于维数灾难，直接处理这些数据变得非常困难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算法以后，优化l1s。
第三步借助于谱回归10］计算出投影向量，并使用nystrom27］2）对于每一个样本x i，利用稀疏约束，其重构都是使用样本集的所有样本。
因此，通过使用稀疏权值矩阵s，seda3）不同于现有半监督算法使用局部保持技术来求解投影， seda 使用稀疏保持投影作为正则化项寻找投影方向。