奇异值分解与主成分分析.docx

《奇异值分解与主成分分析.docx》由会员分享，可在线阅读，更多相关《奇异值分解与主成分分析.docx（10页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、数值试验03:奇异值分解与主成分分析选作问题（讨论性的）6、假设数据源是一系列的图像，每幅图像都是一个矩阵。分别用经典的主成分 分析方法和奇异值分解方法计算特征脸。留意数据的中心化与归一化处理的影响。（1）奇异值分解：是一个能够适用于任意矩阵的一种分解方法：U为M*M方阵（U里面的正交向量称为左奇异向量），Z是一个M*N的矩阵（除 了对角线的元素都是0,对角线上的元素称为奇异值），是一个N*N的方（V 里面正交的向量称为右奇异向量）。我们将一个矩阵A的转置乘以A,并对AtA求特征值(AA) Vj二人 Zi那么V就为右奇异向量，且奇异值6 = 口，左奇异值U二” v 5o就为奇异值，U就为奇异向

2、量。奇异值O跟特征值类似，在矩阵E中也是从大 到小排列，而且o的削减特殊的快，在许多状况下，前10%甚至1%的奇异值的和 就占了全部的奇异值之和的99%以上了。也就是说，我们也可以用前r大的奇异 值来近似描述矩阵，局部奇异值分解：AmXn P Umxr Z rXrVXn （是一个远小于四、门的数）给定一幅M*N大小的图像，将它表示成M*N*1维向量，向量中元素为像素点的 灰度，按行存储，那么如下公式分别表示第i张图片和n张图片的平均值：令M*N*n矩阵X为:x1 - X, X2 - X, , x - X即中心化，将坐标原点移动到平均值位置。设。=XX，,那么Q是一个MN * MN矩 阵：(X

3、- xYQ = XXTQ = XXTX - X, x2 _ X，x - X(xo - xYQ被称为协方差矩阵。那么X中每一个元素X可以表达成:一 i=nx + Z gJiei其中ei是非零特征值对应的特征向量，对于M*N图像，e1,e2, .,en是M*N*1 维相互正交的向量。尺度gj是Xj在空间中的坐标。为了降维，可以对特征值设 定阈值或依据其他准那么，查找协方差矩阵Q中前k个特征向量。Q为M*N*M*N, 通常很浩大。考虑矩阵P = XTXQ的大小为M*N*M*N,而P的大小为n*n, N为训练样本图像数量，通常nM*N 设e是矩阵P的特征值入对应的特征向量，那么有：Pe = XeXTX

4、e = XeXXTXe = XXeQ(Xe) = X( Xe)所以X*e是矩阵Q的特征值大对应的特征向量。这就是用求特征值分解的方法。 对Q进行奇异值分解U就是QQT的特征向量，V就是Q的特征向量，Z中奇异值的平方就是OCT和 qtq的特征值。(2)主成分分析(PCA)的原理就是将一个高维向量x,通过一个特殊的特征向 量矩阵U,投影到一个低维的向量空间中，表征为一个低维向量y,并且仅仅损 失了一些次要信息。也就是说，通过低维表征的向量和特征向量矩阵，可以基本 重构出所对应的原始高维向量。在人脸识别中，特征向量矩阵U称为特征脸空间，因此其中的特征向量5 进行量化后可以看出人脸轮廓，在下面的试验中

5、可以看出。设有n个人脸训练样本，每个样本由其像素灰度值组成一个向量X”那么样本 图像的像素点数即为Xi的维数，由向量构成的训练样本集为,工汨。 该样本集的平均向量为：平均向量又叫平均脸。样本集的协方差矩阵为:求出协方差矩阵的特征向量”和对应的特征值入i ,这些特征向量组成的矩阵U 就是人脸空间的正交基底，用它们的线性组合可以重构出样本中任意的人脸图像。 并且图像信息集中在特征值大的特征向量中，即使丢弃特征值小的向量也不会影 响图像质量。将协方差矩阵的特征值按从大到小挨次：4二422 4/2（+1 N由大于兀的入i对应的特征向量构成主成分，主成分构成的变换矩阵为：U - （4, 2,，&/）这样

6、每一幅人脸图像都可以投影到L 二（/，“2, 4/）构成的特征脸 子空间中。MATLAB 实践:选取16张人脸图像作为数据源，大小为80X80 （这里的人脸图像要求大小相 同,人眼部位尽可能对齐）,把图像存储为80X80, 16的矩阵A,每列表示一张 图像，每行代表同一个位置的像素，因此一共有80X80个维度。中心化时各自减 去每个维度的均值，由于图像数据的量纲一样，所以不需要归一化。16张人脸 为：(a)对X用经典的主成分分析法计算特征脸,取前15个对应主成分特征脸:51 一52 -53 -54 -55 -56 一57 -58 -59 -60 -61 -62 -63 -64 -65 -66

7、-67 -68 -69 -70 -71 一72 -73 -7475m=mEan(y, 2);Irain_number=size(% 2):A=: for i=l: Train_number;temp= double (y (:, i) )-m;A= A temp;endL=A *A:V D=eig(L):L_eig_vec=;for i=l: size(V, 2);if (D(i,i)l)L_e.ig_yec= L_eig_vec V (: i);endendE i g enf ac e s=A*L_ e i g_ ve c;for i= 1:15eigenfaces=reshape (Eig

8、enf aces (:, i), 80, 80);figured)；imshow(mat2gray(eigenf aces):endMe an= re shape (m 80, 80):imshow (mat 2 g r ay (Me an ):通常状况下MNP的，而矩阵非零特征值的个数为minMN-1,P7,所以 在实现中使用维数少的P*P矩阵来代替理论上的协方差矩阵(MN*MN),削减 计算。接着我们依据PCA算法的理论对得到的特征值进行排序，并舍弃一部 分特征值(所占能量少，即特征值小的局部)在实现中我们设定的阈值为1, 保存特征值大于1的，小于1的将被舍弃。由此我们再求得协方差矩阵的特

9、 征向量，并且此特征向量就是所谓的“特征脸”。平均脸平均脸特征脸特征脸特征脸特征脸特征脸特征脸特征脸特征脸 特征脸取前15个对应主成分特征脸:(b)对X用奇异值方法计算特征脸,51 -52 -53 -54 -55 -56 -57 -58 -5960 -61 -62 -63 一64 -65 -66 -67 -68 -69 -70 -71 -72 -73 一74m二muanly, 2):Train_number=size(% 2):A=: for i=l: Train_number;temp=double(y(:, i)-m;A=A temp:endeu, ed, ev=svd(Aj 0):%ed

10、=diag (ed).2 ：L_eig_vec=;for i=l: size(ev, 2) if (ed(i,i)l)L_e.ig_yec= L_eig_vec ev(:, i); end endE i g enf ac e s=A*L_ e i g_ ve c: for i= 1:15eigenfaces=reshape(Eigenfaces(:, i), 80, 80):figured):imshow(mat 2 g r ay(e i g enf ac e ):endMe an= re shape (m, 80 80):imshow(mat 2 g r ay(Me 3n ): 采纳svd分

11、解来得到特征值和特征向量。平均脸 特征脸 特征脸 特征脸特征脸 特征脸 特征脸 特征脸特征脸 特征脸 特征脸 特征脸特征脸 特征脸 特征脸 特征脸由于SVD与PCA得到的特征向量可能符号相反，所以特征脸不同。7、奇异值分解与主成分分析是线性的降维方法。讨论非线性的方法如LLE,并 应用于适中选择的数据进行计算。分析和讨论LLE与PCA的差异。答：（1） LLE分析：LLE (局部线性嵌入)方法是流形学习的一种算法。流形学习，它是用非线性方法去觉察高维数据潜在的低维流形，然后在低维流形 坐标上展现出这种流形结构。总之，流形学习是把一组高维空间中的数据在低维 空间中重新展现，最终到达降维的目的。假

12、设”=5，*，Xj e R i e 1, . . .是原始高维空间的n个样本点，通过流行学习，觉察嵌入在高维空间中的低维流形，y =y i e Rd, i e 1, d DLLE是一种局部优化算法，其基本思想是：认为在局部意义下，数据的结构 是线性的，因此在局部区域内数据点七可以用其近邻点与的线性组合ZjT /勺 来近似表示，即为Z六叱/当，这样在数据点和其近邻点之间就构造了一个重构 权叱L由此重构权组成的权向量恰好保持了高维数据的局部线性结构，在低维空间中也保持这种局部的线性结构，即在低维空间中有xZ尸明X。由于局部区域内看是近似地由和与线性表示出来的，因此会有误差存在, 此误差尽管不能消退

13、，但可以使其到达最小，故引入误差函数：mine,/）=乞二巧-盯其限制条件为：1）假设与不在吃的邻域内，那么町，二; 2）假设与在天的邻域内,那么叫 0 ,且满意Er/j = 1。（2） LLE算法的实现在MATLAB实现中，我们将LLE的实现用下述函数表示：1卬 funct ionY=lle （X, K, d）其中X为我们的数据集，它是一个D*N的矩阵，D为采样点的维度，N为采样点 的个数；K为近邻点的个数，d是我们想要降到的维度，最终输出为降维后新的 d*N矩阵。D2步骤一：采用欧式距离人求得每个数据点的K个紧邻点 步骤二：依据第一步求取的紧邻点对数据线性重构并计算重构权值矩阵卬。 将误差

14、函数化简为：min （/）=小卜朋归=XL区, -町）=XI（巧-勺闻Ek W - W 1 - 1 八1 477 的约束条件下，求minmin巧一 XL %jXj的最小值,即：（乃=ZL + M小女-D 对上式叫求导并令其为o,那么可推出:z71 - 1,W.二仁1 T -1171*k J k其中乙 Rk =（3Xij）TXi - xQ ,/=（忆p町2,，/）,人为k维 全1列向量。MATLAB对重构权值矩阵卬的实现如下：if (KD)tol=le-3: elsetol=0;endW=zeros(K, N):Elfor ii=l:Nz=X (:, neighborhood(: j ii)-r

15、epmat (X (:3 ii), 1, K):C=z? *z：C=C+eye (K, K)*tol*trace(C)：W(：j ii)=Cones (K, 1)：W(:ii) =W(:3 ii)/sum(W(:- ii，)； end;步骤三：求低维嵌入Y 由于重构权向量%所描述的流形的局部几何结构在降维后也是保持不变的。因 此，采用上步求得的均在低维空间内重构，使下面局部重建损失函数最小:min cpY)=I =II=歹）（/ WY Yt）=trYMY1为了限定低维数据匀称分布和避开产生退化解，对Y加了两个约束条件:2。 =。， ZL “ J = I采用拉格朗日乘子，并结合约束条件得：Z(K

16、) = YMYt + 2(KKr NI)上式对Y求导得：MYt=所以（ = ,那么有_刈二, M最小的d个（2d+1）非零特征值所对应特征向量为2，3，。+1,那么=%，”3,，d + J即为所求的低维嵌入（最小特征值为0时不能反映原始 数据的特征，所以必需舍弃）M= sparse (1 :N, 1:N, ones (1, N), N,4 4*K*N); for ii=l:Nw=W(:3 ii);jj=neighborhood(:, ii): M(iij j j)=M(ii, j j)-w ； M(j j, ii)=M(j j, ii)-w;M(j j, j j)=M(j j, j j)-Fw

17、*w，：end;options. disp=0;options. isreal=l;options. issym=l;Y, eigenvals=eigs a d+1,必 options);Y= Y(:, 2: d+1) * *sqrt (N);(3)比拟PCA与LLE的区分：(a)从降维方法来看：降维方法通常分为线性降维和非线性降维。线性降维是假设高维数据位于全 局线性的结构中，使得降维后的低维数据能保持数据点的线性关系，PCA是常用 的线性降维方法；但当数据是非线性时，线性降维方法将破坏原始数据间的拓扑 结构，无法探究数据间的内部规律，因此消失了揭示数据间非线性性质的非线性 降维方法，流形学

18、习是非线性降维方法的一个重要分支。总之，PCA的特点是全 局线性；LLE特点是局部线性、全局非线性。(b)从适用性来看：对于非线性的高维数据，LLE算法能呈现其流形分布，而PCA可能会发生明 显扭曲而失效。PCA可能会使流形中相隔很远的点映射到低维空间后变得相近， 这样便很难揭示其流形分布；而LLE能保持原始数据拓扑结构不变。由于PCA 的目的是查找最小均方意义下最能够代表原始数据的投影方法(查找最优方向)， 所以PCA对椭球状分布的样本集有很好的效果，学习所得的主方向就是椭球的主 轴方向。而LLE适用于分布匀称并稠密的数据集的降维，而当数据集的分布稀疏 时，数据点的关联性较弱，选择的k近邻简

19、单造成信息选取方向的缺失，线性重 构误差大。(c)从算法实现来看：PCA将方差的大小作为保持原始高维数据信息量多少标准，通过求解中心化 和归一化后的数据集协方差矩阵的特征值和特征向量，设置肯定的阈值，留下特 征值大于阈值的那局部特征向量来实现降维；而LLE算法的局部线性表达在通过 查找k近邻并得出最小二乘意义下的近邻线性表示的重构权向量，然后求解低维 嵌入的表示的优化问题，这个优化问题也是协方差矩阵的特征值与特征向量求解, 只是要保存前d小的特征值(0除外)的特征向量来构成低维嵌入。(4)从算法的时间简单度来看：对于数据点个数为N,原始维度为D的数据集而言，PCA算法的时间简单度 为0(03), LLE算法的时间简单度为。(PN),其中p是稀疏矩阵中非零元和零元的比率。