文档介绍：机器学习领域中所谓的降维就是指采用某种映射方法，将原高维空间中的数据点映射到低维度的空间中。降维的本质是学习一个映射函数 f : x->y，其中x是原始数据点的表达，目前最多使用向量表达形式。 y是数据点映射后的低维向量表达，通常y的维度小要性。但是这样投影以后对数据的区分作用并不大，反而可能使得数据点揉杂在一起无法区分。这也是PCA存在的最大一个问题，这导致使用PCA在很多情况下的分类效果并不好。具体可以看下列图所示，假设使用PCA将数据点投影至一维空间上时，PCA会选择2轴，这使得原本很容易区分的两簇点被揉杂在一起变得无法区分；而这时假设选择1
轴将会得到很好的区分结果。
Discriminant Analysis所追求的目标与PCA不同，不是希望保持数据最多的信息，而是希望数据在降维后能够很容易地被区分开来。后面会介绍LDA的方法，是另一种常见的线性降维方法。另外一些非线性的降维方法利用数据点的局部性质，也可以做到比拟好地区分结果，例如LLE，Laplacian Eigenmap等。以后会介绍。
LDA
Linear Discriminant Analysis (也有叫做Fisher Linear Discriminant)是一种有监督的〔supervised〕线性降维算法。与PCA保持数据信息不同，LDA是为了使得降维后的数据点尽可能地容易被区分！
假设原始数据表示为X，〔m*n矩阵，m是维度，n是sample的数量〕
既然是线性的，那么就是希望找到映射向量a， 使得 a‘X后的数据点能够保持以下两种性质：
1、同类的数据点尽可能的接近〔within class〕
2、不同类的数据点尽可能的分开〔between class〕
所以呢还是上次PCA用的这张图，如果图中两堆点是两类的话，那么我们就希望他们能够投影到轴1去〔PCA结果为轴2〕，这样在一维空间中也是很容易区分的。
接下来是推导，因为这里写公式很不方便，我就引用Deng Cai老师的一个ppt中的一小段图片了：
思路还是非常清楚的，目标函数就是最后一行J〔a)，μ〔一飘〕就是映射后的中心用来评估类间距，s〔一瓢〕就是映射后的点与中心的距离之和用来评估类内距。J(a)正好就是从上述两个性质演化出来的。
因此两类情况下：
加上a’a=1的条件〔类似于PCA〕
可以拓展成多类：
以上公式推导可以具体参考pattern classification书中的相应章节，讲fisher discirminant的
OK，计算映射向量a就是求最大特征向量，也可以是前几个最大特征向量组成矩阵A=[a1,a2,….ak]之后，就可以对新来的点进行降维了：y = A’X〔线性的一个好处就是计算方便！〕
可以发现，LDA最后也是转化成为一个求矩阵特征向量的问题，和PCA很像，事实上很多其他的算法也是归结于这一类，一般称之为谱〔spectral〕方法。
线性降维算法我想最重要的就是PCA和LDA了，后面还会介绍一些非线性的方法。
局部线性嵌入〔LLE〕
Locally linear embedding〔LLE〕是一种非线性降维算法，它能够使降维后的数据较好地保持原有流形结构。LLE可以说是流形学习方法最经典的工作之一。很多后续的流形学习、降维方法都与LLE有密切联系。
见图1，使用LLE将三维数据〔b〕映射到二维〔c〕之后，映射后的数据仍能保持原有的数据流形〔红色的点互相接近，蓝色的也互相接近〕，说明LLE有效地保持了数据原有的流行结构。
但是LLE在有些情况下也并不适用，如果数据分布在整个封闭的球面上，LLE那么不能将它映射到二维空间，且不能保持原有的数据流形。那么我们在处理数据中，首先假设数据不是分布在闭合的球面或者椭球面上。
图1 LLE降维算法使用实例
LLE算法认为每一个数据点都可以由其近邻点的线性加权组合构造得到。算法的主要步骤分为三步：(1)寻找每个样本点的k个近邻点；〔2〕由每个样本点的近邻点计算出该样本点的局部重建权值矩阵；〔3〕由该样本点的局部重建权值矩
阵和其近邻点计算出该样本点的输出值。具体的算法流程如图2所示：
图 2 LLE算法步骤
Laplacian Eigenmaps 拉普拉斯特征映射
继续写一点经典的降维算法，前面介绍了PCA,LDA，LLE，这里讲一讲Laplacian Eigenmaps。其实不是说每一个算法都比前面的好，而是每一个算法都是从不同角度去看问题，因此解决问题的思路是不一样的。这些降维算法的思想都很简单，却在有些方面很有效。这些方法事实上是后面一些新的算法的思路来源。
Laplacian Eigenmaps[1] 看问题的角度和LLE有些相似，也是用局部的角度去构建数据之间的