奇异值分解与主成分分析

1、数值实验03:奇异值分解与主成分分析选作问题（研究性的）6、假设数据源是一系列的图像，每幅图像都是一个矩阵。分别用经典的主成分 分析方法和奇异值分解方法计算特征脸。注意数据的中心化与归一化处理的影响。（1）奇异值分解：是一个能够适用于任意矩阵的一种分解方法:U为M*M方阵（U里面的正交向量称为左奇异向量），另是一个M*N的矩阵（除 了对角线的元素都是0,对角线上的元素称为奇异值），是一个N*N的方（V 里面正交的向量称为右奇异向量）。我们将一个矩阵A的转置乘以A,并对ATA求特征值 （ATA） Vi= A. ,v,则v就为右奇异向量，且奇异值6=州，左奇异值匕二*b就为奇异值，u就为奇异向量。

2、奇异值b跟特征值类似，在矩阵工中也是从大到 小排列，而且b的减少特别的快，在很多情况下，前10%甚至1%的奇异值的和就 占了全部的奇异值之和的99%以上了。也就是说，我们也可以用前r大的奇异值 来近似描述矩阵，部分奇异值分解：（r是一个远小于m、n的数）给定一幅M*N大小的图像，将它表示成M*N*1维向董，向董中元素为像素点的 灰度，按行存储，则如下公式分别表示第i张图片和n张图片的平均值：兀1兀1X,=小2X七Xi2n /=i令M*N*n矩阵X为：X = xt - X, x2 - X9 .,Xn _ Xi即中心化，将坐标原点移动到平均值位置。设0 =XXr,则Q是一个MN*MN矩阵:Q被称为

3、协方差矩阵。 那么X中每一个元素X可以表达成:X丿=丸+工gj&其中6是非零特征值对应的特征向量，对于M*N图像，e1,e2,.，en是M*N*1 维相互正交的向量。尺度gji是X,在空间中的坐标。为了降维，可以对特征值设 定阖值或按照其他准则，寻找协方差矩阵Q中前k个特征向量。Q为M*N*M*N, 通常很庞大。考虑矩阵P =XTXQ的大小为M*N*M*N,而P的大小为n*n, N为训练样本图像数量，通常n«M*N 设e是矩阵P的特征值入对应的特征向量，则有：Pe=XeXTXe=XeXXTXe=XXeQ(Xe) =A(Xe；所以X*e是矩阵Q的特征值入对应的特征向量。这就是用

4、求特征值分解的方法。 对Q进行奇异值分解U就是OCT的特征向量，V就是Q9的特征向量，W中奇异值的平方就是QQ和 QTQ的特征值。(2)主成分分析(PCA)的原理就是将一个高维向量x,通过一个特殊的特征向 量矩阵U,投影到一个低维的向量空间中，表征为一个低维向量y,并且仅仅损 失了一些次要信息。也就是说，通过低维表征的向量和特征向量矩阵，可以基本 重构出所对应的原始高维向量。在人脸识别中，特征向量矩阵U称为特征脸空间，因此其中的特征向量u,进行 量化后可以看出人脸轮廓，在下而的实验中可以看出。设有n个人脸训练样本，每个样本由其像素灰度值组成一个向量X、则样本图 像的像素点数即为x,的维数，由向

5、量构成的训练样本集为-,%no该 样本集的平均向量为：X平均向量又叫平均脸。样本集的协方差矩阵为:求出协方差矩阵的特征向量u,和对应的特征值Ai,这些特征向量组成的矩阵U 就是人脸空间的正交基底，用它们的线性组合可以重构出样本中任意的人脸图像。 并且图像信息集中在特征值大的特征向輦中，即使丢弃特征值小的向邀也不会影 响图像质量。将协方差矩阵的特征值按从大到小顺序：久】- -兄小 由大于入d的入对应的特征向量构成主成分，主成分构成的变换矩阵为：U = （"1，“2,，d）这样每一幅人脸图像都可以投影到二（5, "2, ，5）构成的特征脸 子空间中。MATLAB 实践:选取16

6、张人脸图像作为数据源，大小为80X80 （这里的人脸图像要求大小相 同，人眼部位尽可能对齐），把图像存储为80X80,16的矩阵A,每列表示一张 图像，每行代表同一个位置的像素，因此一共有80X80个维度。中心化时各自减 去每个维度的均值，由于图像数据的量纲一样，所以不需要归一化。16张人脸为：（a）对X用经典的主成分分析法计算特征脸，取前15个对应主成分特征脸:515253545556575859GO616263646567迪697071T23745iR=inean(y, 2);Irain_nu».ber=sise 2): A=:for i=l: Iraui_nuniber; te

7、nip= double(y(:, i)-n; A=A temp:endL二A” «A：V D=eig(L):L.eig_vec=:for i=l:size(V,2)：辻(D(i,i)>l)L.,eig.vec= L.eig_vee V(:, i)： endendEigenfaces-A*L_eig_vec;for i=l: 15exg;en.£aces=reshape (EigenfacesSO, 80):figure(i):imshov(iiat2gray(eigen*faces? ) ;|endMean=reshape (% 80, 80): imshow (ma

8、t 2 g r ay (Me an?);通常情况下MN»P的，而矩阵非零特征值的个数为minMN-1,P-1t所以 在实现中使用维数少的P*P矩阵来代替理论上的协方差矩阵(MN*MN),减少 计算。接着我们根据PCA算法的理论对得到的特征值进行排序，并舍弃一部 分特征值(所占能董少，即特征值小的部分)在实现中我们设定的阈值为1,保留特征值大于1的，小于1的将被舍弃。由此我们再求得协方差矩阵的特 征向量，并且此特征向量就是所谓的“特征脸”。平均脸特征脸特征脸特征脸平均脸特征脸特征脸特征脸特征脸特征脸特征脸特征脸特征脸特征脸特征脸特征脸对X用奇异值方法计算特征脸，取前15个对应主成分特征

9、脸:51 一52 _53 _54 一55 _5658 _5959 _62 一jn.=nean(y, 2);Irain_number=SL2e(yJ 2):A=J;T)f or i=l: Irain.nwuber :t emp=double (y(:? 1) )-jn;A= A t eiip;endeu> ed, ev=svd (Aj 0):Ked=diag(ed)"2:L_eig_vec=:Hf or i=l: size (ev, 2)if<ed(i, i)>l)L.ei8.vec= L.eig.vec ev(:, i);endvec=65 end66 E1g en

10、f aces=A*L_e1g.ve c:67 一68 一Ifor i=l:1570 _71 一eigenf aces=reshape (Eigenfaces(:, i)80 80); figure (1):ljmshov (n.at 2g ray (e ig enf aces'):end.72 _73 一74Mean= re shape (叫 80, 80): i ins ho v mat 2 g r ay (Me an?):采用svd分解来得到特征值和特征向量。平均脸特征脸特征脸特征脸特征脸特征脸特征脸特征脸特征脸特征脸特征脸特征脸特征脸特征脸特征脸特征脸由于SVD与PCA得到的特征

11、向量可能符号相反，所以特征脸不同。7、奇异值分解与主成分分析是线性的降维方法。研究非线性的方法如LLE,并 应用于适当选择的数据进行计算。分析和研究LLE与PCA的差别。答：(1) LLE分析：LLE (局部线性嵌入)方法是流形学习的一种算法。流形学习，它是用非线性方法去发现高维数据潜在的低维流形，然后在低维流形 坐标上展示出这种流形结构。总之，流形学习是把一纽高维空间中的数据在低维 空间中重新展示，置终达到降维的目的。假设* = 血，叫，兀e屮，i e 1，"是原始高维空间的N个样 本点，通过流行学习，发现嵌入在高维空间中的低维流形，Y = %, yn> yt e Rd, i

12、 e 1,., Nf d « DLLE是一种局部优化算法，其基本思想是：认为在局部意义下，数据的结构 是线性的，因此在局部区域内数据点兀可以用其近邻点亏的线性组合工冃Wk 来近似表示，即这样在数据点和其近邻点之间就构适了一个重构 权由此重构权组成的权向量恰好保持了高维数据的局部线性结构，在低维空间中也保持这种局部的线性结构，即在低维空间中有门工冃。因为局部区域内是近似地由和线性表示出来的，因此会有误差存在, 此误差尽管不能消除，但可以使其达到最小，故引入误差函数：min"*）=工二 X,其限制条件为：1)若不在的邻域内，则虬=°； 2)若在人的邻域内,则也严，且满

13、足工:齐(2) LLE算法的实现在MATLAB实现中，我们将LLE的实现用下述函数表示：1 functionY = Lle (X, K, d)其中X为我们的数据集，它是一个D*N的矩阵，D为采样点的维度，N为采样点 的个数：K为近邻点的个数，d是我们想要降到的维度，最终输出为降维后新的 d*N矩阵。D步利用欧式距离电S求得每个数据点的K个紧邻点步骤二：根据第一步求取的紧邻点对数据线性重构并计算重构权值矩阵W。将误差函数化简为：min )=-=工：陽"-工：/川=工:丿Sw wT= 1利用拉格朗日乘子法在乙円 -“丄&-丄的约束条件下，求的最小值,即：对上式W求导并令其为0,则

14、可推出: 其中爲 e Rg = a - Xij y -心,比=(,Wl2iWlk)T ,片为 k 维 全1列向量。MATLAB对重构权值矩阵W的实现如下：if (K>D)tol=le-3;elsetol=0;end¥=zeros (Kf N): for ii=l:Fz=X (:, neighborhood(:, ii) )-repniat (K (:亠 ii), 1, K):C=z? *z:C=C+eye (K, K) *tol*trace(C): W(:5 ii)=Cones(K5 1); w(：ii)=w(:j ill/sum(Y(:J ill);end;步骤三：求低维嵌入

15、Y 由于重构权向量所描述的流形的局部几何结构在降维后也是保持不变的。因 此，利用上步求得的在低维空间内重构，使下面局部重建损失函数最小: min 仅F)=ML I” -亿宀=S". IK -妙=trYU 一 0) (Z "U=tNYMYH为了限定低维数据均匀分布和避免产生退化解，对Y加了两个约束条件：工：/ “范二加=1利用拉格朗日乘子，并结合约束条件得：z(r) = ymyt + ayyt - nd上式对Y求导得：W =兄"，所以( 一= 0，则有1 -27l=0, M最小的d个(2d+1)非零特征值所对应特征向量为逅,5,口Z ,则 卩=I"，即为所

16、求的低维嵌入(最小特征值为0时不能反映原始 数据的特征，所以必须舍弃)sparse (1:1: N, ones (1, N)川4*K*N): for ii=l!Nw=V(:, ii);jj=neighborhood(:j ii):B(iijj jJ-w* :B(j jjM(jjj jj)二爪(儿 jj)F*w':end：opti ons. disp=0:options. isreal=l: options. issyjii= 1;Yj ei?envals=eigs (M, d+b 0, options):Y=Y(;,2;d+l),*sqrt (Ji);(3) 比较PCA与LLE的区别：

17、(a) 从降维方法来看：降维方法通常分为线性降维和非线性降维。线性降维是假设高维数据位于全 局线性的结构中，使得降维后的低维数据能保持数据点的线性关系，PCA是常用 的线性降维方法；但当数据是非线性时，线性降维方法将破坏原始数据间的拓扑 结构，无法探索数据间的内部规律，因此出现了揭示数据间非线性性质的非线性 降维方法，流形学习是非线性降维方法的一个重要分支。总之，PCA的特点是全 局线性；LLE特点是局部线性、全局非线性。(b) 从适用性来看：对于非线性的高维数据，LLE算法能展现其流形分布，而PCA可能会发生明 显扭曲而失效。PCA可能会使流形中相隔很远的点映射到低维空间后变得相近， 这样便很难揭示其流形分布；而LLE能保持原始数据柘扑结构不变。由于PCA 的目的是寻找最小均方意义下最能够代表原始数据的投影方法(寻找最优方向)， 所以PCA对椭球状分布的样本集有很好的效果，学习所得的主方向就是椭球的主 轴方向。而LLE适用于分布均匀并稠密的数据集的降维，而当数据集的分布稀疏 时，数据点的关联性较弱，选择的k近邻容易造成信息选取方向的缺失，线性重 构误差大。(c) 从算法实现来看：PCA将方差的大小作为保持原始商维数据信息量多少标准，通过求解中心化 和