英语四级阅读理解
数据降维
巧克英语
随着信息获取与处理技术的飞速发展，人们获取信息和数据的能力越来越强，高维数据频繁地出现于科学研究以及产业界等相关领域。为了对客观事物进行细致的描述，人们往往需要利用到这些高维数据，如在图像处理中，数据通常为m*n大小的图像，若将单幅图像看成图像空间中的一个点，则该点的维数为m*n 维，其对应的维数是相当高的，在如此高维的空间中做数据处理无疑会给人们带来很大的困难，同时所取得的效果也是极其有限的；再如网页检索领域一个中等程度的文档集表示文档的特征词向量通常高达几万维甚至几十万维；而在遗传学中所采集的每个基因片段往往是成千上万维的。另外，若直接处理高维数据，会遇到所谓的“维数灾难”（Cur of dimensionality）问题：即在缺乏简化数据的前提下，要在给定的精度下准确地对某些变量的函数进行估计，我们所需要的样本数量会随着样本维数的增加而呈指数形式增长[1]。因此，人们通常会对原始数据进行“数据降维”。
数据降维是指通过线性或者非线性映射将高维空间中的原始数据投影到低维空间，且这种低维表示是对原始数据紧致而有意义的表示，通过寻求低维表示，能够尽可能地发现隐藏在高维数据后的规律[2]。对高维数据进行降维处理的优势体现在如下几个方面：1)对原始数据进行有效压缩以节省存储空间；2)可以消除原始数据中存在的噪声；3)便于提取特征以完成分类或者识别任务；4)将原始数据投影到2维或3维空间，实现数据可视化。主流的数据降维算法主要有七种，其名称和对比如图1所示，接下来会进行详细地介绍其中的五种：线性的PCA、MDS、LDA以及非线性的Isomap、LLE。
图1 七种不同降维算法及其对比
1.PCA（Principal Component Analysis, 主成成分分析法）
1.1 基本原理
PCA 是通过对原始变量的相关矩阵或协方差矩阵内部结构的研究，将多个变量转换为少数几个综合变量即主成分，从而达到降维目的的一种线性降维方法。 这些主成分能够反映原始变量的绝大部分信息，它们通常表示为原始变量的线性 组合。PCA 将数据方差作为对信息衡量的准则：方差越大，它所能包含的信息就越多，反之包含的信息就越少。因此，PCA 可以看成一个坐标变换的过程：将高维数据的坐标投影到数据方差最大的方向组成的新的坐标系中。虽然PCA 具有容易计算，解释性强等特点，但也存在不适用非线性结构高维数据、不适用非高斯分布数据以及主分量的个数难以确定等缺点，其算法步骤大致为：
Step 1：计算所有样本的均值m 和散布矩阵S ，所谓散布矩阵同协方差矩阵； Step 2：计算S 的特征值，然后由大到小排序；
Step 3：选择前p 个特征值对应的特征矢量作成一个变换矩阵E=[e1, e2, …, ep]；
Step 4：对于之前每一个n 维的特征矢量x 可以转换为p 维的新特征矢量y ：
()()y transpo E x m =-
1.2 应用及示例
因在特征提取和数据降维方面的优越性，PCA 近年来被广泛应用于特征提取、信号评测和信号探测等方面，其中人脸识别是PCA 的一个经典的应用领域：利用K-L 变换抽取人脸的主要成分，构成特征脸空间，识别时将测试图像投影到此空间，得到一组投影系数，通过与各个人脸图像比较进行识别。利用特征脸法进行人脸识别的数据降维部分具体步骤如下：
Step 1：假设训练集有200个样本，由灰度图组成，则训练样本矩阵为：
12200(,,...,)T x x x x =
我心依旧歌词
其中向量x i 为由第i 个图像的向量按列堆叠成一列的M*N 维向量。
Step 2：计算训练图片的平均脸：
fashionably late2001
late autumn2001i i i x ψ===∑
Step 3：计算差值脸，即每一张人脸与平均脸的差值：
,1,2,...,200i i d x i ψ=-=
Step 4：构建协方差矩阵：
2001
1
122001,(,,...,)T T i i i C d d AA A d d d ====∑
Step 5：求协方差矩阵的特征值和特征向量，构造特征脸空间。首先采用奇异值分解定理，通过求解A T A 的特征值和特征向量来获得AA T 的特征值和特征向量。求出A T A 的特征值λi 及其正交归一化特征向量v i 。根据特征值的贡献率选取前p 个最大特征向量及其对应的特征向量，贡献率是指选取的特
征值的和与占所有特征值的和比，即20011/
i p i i i i i a ϕλλ=====≥∑∑。一般取a=99%，即使训练样本在
前p 个特征向量集上的投影有99%的能量。再求出原协方差矩阵的特征向量：
/1,2,...,)i i u Av i p ==。则特征脸空间为：
12(,,...,)p w u u u =understand什么意思
Step 6：将每一幅人脸与平均脸的差值脸矢量投影到“特征脸”空间，即：
(1,2,...,200)T i i w d i Ω==
至此根据需要提取了前面最重要的部分，将p 后面的维数省去，从而达到降维的效果，同时保持了99%以上的原有的数据信息，接着就可以很方便的进行人脸的识别匹对了。
2. MDS （Multidimensional Scaling, 多维尺度分析法）
2.1 基本原理
MDS 分析的是成对样本间的相似性，利用这个信息去构建合适的低维空间，使得样本在此空间的距离和在高维空间中的样本间的相似性尽可能的保持一致。根据样本是否可计量，MDS 算法可分为计量多元尺度法和非计量多元尺度法，前者以样本间相似度作为实际输入，需要样本是等距（interval ）比例（ratio ）尺度，优点是精确，可以根据多个准则评估样本间差异，缺点是计算成本高，耗时。但对于很多应用问题，样本不费可计量，需要使用非计量多元尺度法，这种方法接受样本的顺序尺度作为输入，并以此自动计算相似值。样本尺度要求是顺序的（ordinal ），较简便，直观，从非计量的样本导出计量的分析结果，应用范围更广，但没法知道评估准则，效果较差。
基本的MDS 算法原理为：设X[1]，…,X[n]为p 维空间上的n 个点，其两两距离（相异度）为δ[i ，j]。相异度可以是定量的（如物理距离或比例），此时对应度量标度（metric scaling ），也可以是定性的（如感觉或偏好的排序），此时对应非度量标度（nonmetric scaling ）。度量标度要寻找t 维空间上（t<p ）的一个n 点结构Y[1]，…,Y[n]，这称为MDS 的一个解，其内点距离为d[i ，j]，使得δ[i ，j]和d[i ，j]近似相等。即存在一个单调函数f ，使d[i, j]≈f(δ[i ，j])。寻找函数f 的方法是极小化压力函数：
{}1/22()ij ij ij i j w d d ∧<-∑
这样得到的解称为最小二乘标度。
2.2 应用及示例 作为一种解决特殊类型问题的方法，MDS 算法在多个领域有着广泛的应用：在心理学
研究不同类别的心理刺激（如人格特质，性别角色）或物理刺激（如面孔，声音，颜色，味道）的认知的潜在结构，并绘制这些刺激的“感知图”（perceptual map ）；基于市场研究消费者的产品选择和产品偏好，可以识别产品间的联系；还可以应用到社交网络进行大型网络的集群的识别；其他应用涉及地理学、生态学、分子生物学、计算化学、图形学甚至流行音乐研究等。
譬如，对一个国家的许多城市而言，假如我们并不能确定它们的经纬度信息，却知道所有城市两两之间的距离，就可以通过MDS 方法将这些代表相似性的距离数据，呈现在二维坐标上。这种对相似性矩阵的处理可以推广到一般情况，从而实现数据的压缩。简单的讲，譬如我们可以获知高维数据点的距离分布，它们的绝对位置对我们而言意义并不大，我们所关注的是点与点之间的距离关系，那么就可以通过MDS 方法将高维点映射到二维空间，同时很好的保持了其距离关系。通过这样一个等距映射，我们就可以将数据量大幅减少。
3. LDA （Linear Discriminant Analysis, 线性判别式分析）本草纲目英语
3.1 基本原理
线性判别式分析(Linear Discriminant Analysis, LDA)，也叫做Fisher 线性判别(Fisher Linear Discriminant ,FLD)，是模式识别的经典算法。线性判别的基本思想是将高维的模式样本投影到最佳鉴别矢量空间，以达到抽取分类信息和压缩特征
gumdrop
mary j blige空间维数的效果，投影后保证模式样本在新的子空间有最大的类间距离和最小的类内距离，即模式在该空间中有最佳的可分离性。因此，它是一种有效的特征抽取方法。使用这种方法能够使投影后模式样本的类间散布矩阵最大，并且同时类内散布矩阵最小。与PCA保持数据信息不同，LDA是为了使得降维后的数据点尽可能地容易被区分。
3.2 应用及示例
LDA常用来提取特征向量，因此被广泛用于模式识别、特征提取、图像识别等领域。因其利用有监督的学习得到可分离的数据，因此也被用于聚类分析中。如果用LDA算法进行人脸特征提取，假设对于一个R n空间有m个样本分别为
x1,x2, ... ,x21, 即每个x是一个n行的矩阵，其中n i表示属于i类的样本个数，一共有c个类。首先得到类i的样本均值和总体样本均值，再求出类间离散度矩阵和类内离散度矩阵。LDA算法希望所分的类之间的耦合度低，同时类内的聚合度高，即类内离散度矩阵中的数值要小，而类间离散度矩阵中的数值要大，此处根据Fisher鉴别准则找到由一组最优鉴别矢量构成的投影矩阵W opt，其列向量为
d个最大特征值所对应的特征向量，其中d≤c-1，从而完成了数据的降维和聚类。
精锐教育怎么样
4.Isomap（Isometric Mapping, 等距映射算法）
4.1 基本原理
Isomap算法是近年来用于非线性降维的一个重要算法，算法的关键在于利用样本向量之间的欧氏距离dx(i, j)计算出样本之间的测地距离dG(i, j)，从而真实再现高维数据内在的非线性几何结构。然后使用经典MDS算法构造一个新的
d维欧氏空间Y(d是降维空间的维数)，最大限度地保持样本之间的欧式距离dY(i,j)与dG(i,j)误差最小，从而达到降维的目的，其核心是估算两点间的测地距离，优点是能处理非线性流行之类的高维数据、全局优化和渐进恢复，缺点是数据拓扑空间不稳定。算法主要步骤如下：
Step 1：构造近邻图。首先计算任意两个样本向量xi与xj的欧氏距离dX(xi,xj)，然后用全部的样本向量xi(1≤i≤N)构造无向图G。对于样本向量xi，在图G中将它与离它最近的n个样本向量(n是可调参数)连接起来，设置连接线的长度分别为它们各自的距离。
Step 2：计算任意两个样本向量之间的最短路径。在图G中，设置任意两个
