降维算法研究与比较

降维方法研究与比较

降维算法分类的简单汇总图1、PCA算法的介绍PCA（Principalcomponentanalysis）中文翻译为主成分分析，是一种对数据进行分析的技术，最重要的应用是对原有数据进行简化。正如它的名字：主成分分析，这种方法可以有效的找出数据中最“主要”的元素和结构，去除噪音和冗余，将原有的复杂数据降维，揭示隐藏在复杂数据背后的简单结构。它的优点是简单，而且无参数限制，可以方便的应用与各个场合。PCA算法的原理主要思想：将原本的数据降低维度，从而使得降低了维度的数据之间的方差最大（也可以说投影误差最小）。目标：找到一组正交基，使样本变换后样本的协方差为0，方差尽可能大。推导过程

样本均值（N为样本点个数）样本协方差矩阵（对角线上的元素为方差，其它为协方差）优化目标等价于将协方差矩阵对角化，设P为变换矩阵，新空间的样本y的协方差矩阵为那么优化目标变为：寻找矩阵P，满足D为对角矩阵

PCA算法步骤设有N个M维的样本数据1）将原始数据按列组成M行N列矩阵X；2）将X的每一行进行零均值化，即减去这一行的均值；3）求出协方差矩阵；4）求出协方差矩阵的特征值及对应的特征向量；5）将特征值从大到小排列，输出能量99%的特征值对应的特征向量，组成矩阵;6)即为降维后的数据。推导过程C为实对称矩阵，由线性代数的性质可知，一个n行n列的实对称矩阵一定可以找到n个单位正交特征向量，我们将其按列组成矩阵则协方差矩阵C有如下结论：其中为对角阵，对角元素为特征值。至此，就可以得到,P是协方差矩阵C的特征向量单位化后按行排列的矩阵，如果中的特征值从大到小，那么对应的特征向量从上到下，在PCA算法中一般取能量大于99%的特征值，那么其对应的特征向量构成的矩阵P就是所求的变换矩阵。PCA算法的应用PCA算法是对数据进行降维处理，我们根据需要将“主元”向量的重要性进行排序，取前面重要的部分，将后面的维数省去。优点：无参数限制，不需要人为设定参数或进行人工干预；缺点：如果用户对观测对象有一定的先验知识，却无法通过参数化等方法对处理过程进行干预，可能会得不到预期的效果，效率也不高。2、LDA算法的介绍LDA（LinearDiscriminantAnalysis）中文翻译为线性判别分析，有些资料上也称为是Fisher’sLinearDiscriminant。线性判别分析的基本思想是将高维的样本投影到最佳判别矢量空间，以达到抽取分类信息和压缩特征空间维数的效果，投影后保证样本在新的子空间有最大的类间距离和最小的类内距离，即模式在该空间中有最佳的可分离性。因此，它是一种有效的特征抽取方法。LDA算法的公式推导

主要思想：这种方法使投影后样本的类间散布矩阵最大，且同时类内散布矩阵最小。也就是说，它能够保证投影后样本在新的空间中有最小的类内距离和最大的类间距离，即达到最佳的可分离性。二分类问题：投影函数公式推导LDA分类的目标是使得不同类别之间的距离越远越好，同一类别之中的距离越近越好。类别的均值，投影后的类别均值

投影后各类均值差的绝对值，类内方差其中目标函数：

推导结果多个类别类间离散度矩阵，其中类内离散度矩阵目标函数，用拉格朗日法得最终求，为的特征向量LDA算法步骤设有N个C类样本，每类个1）计算每类样本均值，计算所有样本均值；2）计算类内、类间离散度矩阵和；3）求的特征值，特征向量；4）取最大的K个特征值对应的特征向量。LDA算法的应用LDA降维是直接和类别的个数相关的，与数据本身的维度没关系，比如原始数据是n维的，一共有C个类别，那么LDA降维之后，一般就是1维，2维到C-1维进行选择。举例说明图的左边是PCA，整组数据在表示上更加方便(降低了维数并将信息损失降到最低)，但在分类上也许会变得更加困难；图的右边是LDA，在增加了分类信息之后，两组输入映射到了另外一个坐标轴上,两组数据之间就变得更易区分了。PCA与LDA的比较PCA在许多模式识别应用中取得了较好的效果，但由于它是以所有样本的最优重构为目的，并且是无监督的，因此不适用于描述不同类别。而LDA是有监督的，它是以样本的可区分性为主要目标，所以基于LDA的算法通常要优于PCA算法。LDA算法也有不足之处，它存在奇异值问题，即样本维数高于样本个数时类内离散度矩阵是奇异矩阵，有效的解决方法有PCA+LDA等。尽管PCA、LDA在模式识别应用中取得了较好的效果，但是他们仅能发现全局的欧式结构，无法发现隐藏的内在非线性流行结构，因而为了发现内在的流行结构，基于流形学习的算法成为热点，其中包括局部线性嵌入LLE，局部保持投影LPP等。LPP算法的介绍LPP算法本质上是一种线性降维方法，基于最近邻图来建立映射，因而它具有一般线性降维算法不具备的流行学习能力。其目标是寻找一个转换矩阵将高维空间中的数据投影到低维空间中，使得在高维空间中互为近邻的两点投影到低维空间后仍互为近邻。

LPP算法可以很好地保留数据的局部信息，主要考虑的就是保持数据中近邻点之间的结构。LPP算法的公式推导目标：寻找一个投影方向，使得经过的变换后得到的在一个相对低维的空间能够尽可能的代表同时相邻的点经过变换后仍应尽可能的相互接近。目标函数：其中为第i个样本和第j个样本之间相似性程度，可以取用近邻或近邻的高斯权或均匀权作为相似性度量。

公式推导目标函数：约束条件：其中为数据矩阵，是一个拉普拉斯矩阵，是一个

对角矩阵，其中，权重矩阵的确定，即对所创建的最近相邻

图的边进行赋值，表示与节点之间的权重。公式推导

对于一般的情形，可以采用高斯函数赋值，赋值规则如下：

，参数为总体样本方差；

对于简单二值情形，可以采用简单二值赋值，赋值规则如下：

对应着第个样本，越大，则反映出第个样本越重要。为了去除目标函数最小化问题的一个缩放问题并消除平移的任意性，加一个约束条件整理得,用拉格朗日法可以得

公式推导然后对求导后，得到等式，则求解最小化目标函数的变换矩阵可以通过解上式的广义特征值得到，为的特征值对应的特征向量。LPP算法比一般的流形学习方法具有更低的计算复杂度和实现代价，它可以看做是拉普拉斯特征映射的线性化算法，将数据从高维空间映射到较低维空间，且保持数据之间的相似关系，即原始空间上相邻的数据点在投影空间上也保持相应的邻近关系。LLE算法介绍LLE算法是一种非线性无监督的降维方法，能够使降维的数据保持原有的拓扑结构。LLE算法具有平移、旋转及缩放不变性，可以广泛的应用于非线性数据的降维、聚类、可视化以及图像分割等领域。主要思想：假定每个数据点与它的近邻点位于流形的一个线性或近似线性的局部邻域，数据点可以由其近邻点来线性表示，重构低维流形时，相应的内在低维空间中的数据点保持相同的局部近邻关系，即高低维中每个点用周围点表示它的权重相同。LLE算法步骤给定N个输入样本向量，通过LLE算法将得到输出值1、在高维空间根据欧氏距离寻找每个样本的近邻点，确定K个邻域点；2、计算每个样本点的局部重建权值矩阵，定义一个误差函数，其中为的k个近邻点，是与

之间的权值，如果不是的近邻点，且要满足条件，权重矩阵的选取通过最小化重构误差来实现；LLE算法步骤

3、将所有的样本点映射嵌入到低维空间中，低维嵌入与它的近邻点能反映高维输入空间中对应样本点的重构权值关系，即最小化损失函数：

,加上约束条件后推得

其中令，最后解特征向量，要使代价函数达到最小，低维嵌入为的最小第2到第d+1个特征值对应的特征向量。

LLE算法应用优点：LLE算法可以学习任意维的局部线性的低维流形.LLE算法中的待定参数很少,K和d.LLE算法归结为稀疏矩阵特征值计算,计算复杂度相对较小,容易执行.缺点：LLE算法要求所学习的流形只能是不闭合的且在局部是线性的.LLE算法中的参数K,d