机器学习-主成分分析及奇异值分解

-1-机器学习期末报告成员：白子轩，安勇正，李文涛，王琳时间：2016年4月9日-2-主成分分析（PCA）与奇异值分解（SVD)原理及其应用一、导论在实际问题研究中，多变量问题是经常会遇到的。变量太多，无疑会增加分析问题的难度与复杂性，而且在许多实际问题中，多个变量之间是具有一定的相关关系的。为了解决这些问题，最简单和最直接的解决方案是削减变量的个数，但这必然又会导致信息丢失和信息不完整等问题的产生。为此，人们希望探索一种更为有效的解决方法，它既能大大减少参与数据建模的变量个数，同时也不会造成信息的大量丢失。主成分分析正式这样一种能够有效降低变量维数，并已得到广泛应用的分析方法。二、主成分分析（PCA）主成分分析是数学上对数据降维的一种方法。其基本思想是设法将原来众多的具有一定相关性的指标123,,,pXXXX(比如p个指标），重新组合成一组较少个数的互不相关的综合指标mF来代替原来指标。那么综合指标应该如何去提取，使其既能最大程度的反映原变量X所代表的信息，又能保证新指标之间保持相互无关（信息不重叠）。设1F表示原变量的第一个线性组合所形成的主成分指标，即11112121...ppFaXaXaX,由数学知识可知，每一个主成分所提取的信息量可用其方差来度量，其方差1()VarF越大，表示1F包含的信息越多。常常希望第一主成分1F所含的信息量最大，因此在所有的线性组合中选取的1F应该是123,,,pXXXX的所有线性组合中方差最大的，故称1F为第一主成分。如果第一主成分不足以代表原来p个指标的信息，再考虑选取第二个主成分指标2F，为有效地反映原信息，1F已有的信息就不需要再出现在2F中，即2F与1F要保持独立、不相关，用数学语言表达就是其协方差12(,)0CovFF，所以2F是与1F不相-3-关的123,,,pXXXX的所有线性组合中方差最大的，故称2F为第二主成分，依此类推构造出的12mFFF、、为原变量指标123,,,pXXXX第一、第二、……、第m个主成分。11111221221122221122...............ppppmmmmppFaXaXaXFaXaXaXFaXaXaX根据以上分析得知：(1)iF与jF互不相关，即(,)0ijCovFF,并有()'iiiVrFaaa，其中Σ为X的协方差阵(2)1F是123,,,pXXXX的一切线性组合（系数满足上述要求）中方差最大的,即mF是与12-1mFFF、、都不相关的123,,,pXXXX的所有线性组合中方差最大者。12mFFFmp、、（）为构造的新变量指标，即原变量指标的第一、第二、……、第m个主成分。由以上分析可见，主成分分析法的关键就是确定原来变量(1,2,)jXjp在诸主成分(1,2,)jFim上的荷载(1,2,;1,2,)ijaimjp。从数学上可以证明，原变量协方差矩阵的特征根是主成分的方差，所以前m个较大特征根就代表前m个较大的主成分方差值；原变量协方差矩阵前m个较大的特征值i（这样取才能保证主成分的方差依次最大）所对应的特征向量就是相应原变量在主成分iF上的载荷ia，为了加以限制，载荷系数ia启用的是i对应的单位化的特征向量，即有'iiaa=1。三、主成分分析法的计算步骤主成分分析的具体步骤如下：（1）计算协方差矩阵计算样品数据的协方差矩阵：()ijpps，其中11()()1nijkiikjjksxxxxni，j=1，2，…，p-4-（2）求出Σ的特征值i及相应的正交化单位特征向量iaΣ的前m个较大的特征值120m,就是前m个主成分对应的方差，i对应的单位特征向量ia就是原来变量在主成分iF上的载荷系数，则原变量的第i个主成分iF为：'iiFaX主成分的方差（信息）贡献率用来反映信息量的大小，i为：1/miiii（3）选择主成分最终要选择几个主成分，即12mFFF、、中m的确定是通过方差（信息）累计贡献率()Gm来确定11()/pmikikGm当累积贡献率大于85%时，就认为能足够反映原来变量的信息了，对应的m就是抽取的前m个主成分。（4）计算主成分得分计算样品在m个主成分上的得分：1122...iiipipFaXaXaX12,im，，实际应用时，指标的量纲往往不同，所以在主成分计算之前应先消除量纲的影响。消除数据的量纲有很多方法，常用方法是将原始数据标准化，即做如下数据变换：*1,2,...,;1,2,...,ijjijjxxxinjps其中：11njijixxn，2211()1njijjisxxn根据数学公式知道，①任何随机变量对其作标准化变换后，其协方差与其相关系数是一回事，即标准化后的变量协方差矩阵就是其相关系数矩阵。②另一方面，根据协方差的公式可以推得标准化后的协方差就是原变量的相关系数，亦即，标准化后的变量的协方差矩阵就是原变量的相关系数矩阵。也就是说，在标准化前后变量的相关系数矩阵不变化。四、奇异值分解（SVD）-5-定义：设A为m*n阶矩阵，HAA的n个特征值的非负平方根叫作A的奇异值，记为()iA。如果把HAA的特征值记为()iA，则12()()HiiAAA。定理（奇异值分解）设A为m*n阶复矩阵，则存在m阶酉阵U和n阶酉阵V，使得：**'AUSV其中12(,,),0(1,),()riSdiagirrrankA。推论：设A为m*n阶实矩阵，则存在m阶正交阵U和n阶正交阵V，使得**'AUSV，其中12(,,),0(1,),()riSdiagirrrankA。TmnmmmnnnAUV奇异值分解提供了一些关于A的信息，例如非零奇异值的数目（S的阶数）和A的秩相同，一旦秩r确定，那么U的前r列构成了A的列向量空间的正交基，另外V的从右向左nr列为A的kernel的基。由A的奇异值分解111222TrrrAUVuvuvuv可见，A是矩阵1122,,,rruvuvuv的加权和，其中12,,r是权重。若将奇异值按递减顺序排列120r显然，奇异值大的项对矩阵A的贡献大。因此，当舍去了权重小的部分项后仍然能够较好地“逼近”A，这一特性常被用来压缩图像。矩阵A的秩k逼近定义为111222,1rrrAuvuvuvkr-6-五、奇异值分解（SVD)与主成分分析（PCA）的关系PCA的全部工作简单点说，就是对原始的空间中顺序地找一组相互正交的坐标轴，第一个轴是使得方差最大的，第二个轴是在与第一个轴正交的平面中使得方差最大的，第三个轴是在与第1、2个轴正交的平面中方差最大的，这样假设在N维空间中，我们可以找到N个这样的坐标轴，我们取前r个去近似这个空间，这样就从一个N维的空间压缩到r维的空间了，但是我们选择的r个坐标轴能够使得空间的压缩使得数据的损失最小。还是假设我们矩阵每一行表示一个样本，每一列表示一个feature，用矩阵的语言来表示，将一个m*n的矩阵A的进行坐标轴的变化，P就是一个变换的矩阵从一个N维的空间变换到另一个N维的空间，在空间中就会进行一些类似于旋转、拉伸的变化。mnnnmnAPA而将一个m*n的矩阵A变换成一个m*r的矩阵，这样就会使得本来有n个feature的，变成了有r个feature了（rn)，这r个其实就是对n个feature的一种提炼，我们就把这个称为feature的压缩。用数学语言表示就是：mnnrmrAPA但是这个怎么和SVD扯上关系呢？之前谈到，SVD得出的奇异向量也是从奇异值由大到小排列的，按PCA的观点来看，就是方差最大的坐标轴就是第一个奇异向量，方差次大的坐标轴就是第二个奇异向量…我们回忆一下之前得到的SVD式子：TmnmrrrrnAUV在矩阵的两边同时乘上一个矩阵V，由于V是一个正交的矩阵，所以V转置乘以V得到单位阵I，所以可以化成后面的式子TmnrnmrrrrnrnAVUVVmnrnmrrrAVU-7-将后面的式子与AP那个m*n的矩阵变换为m*r的矩阵的式子对照看看，在这里，其实V就是P，也就是一个变化的向量。这里是将一个m*n的矩阵压缩到一个m*r的矩阵，也就是对列进行压缩，如果我们想对行进行压缩（在PCA的观点下，对行进行压缩可以理解为，将一些相似的sample合并在一起，或者将一些没有太大价值的sample去掉）怎么办呢？同样我们写出一个通用的行压缩例子：rmmnrnPAA这样就从一个m行的矩阵压缩到一个r行的矩阵了，对SVD来说也是一样的，我们对SVD分解的式子两边乘以U的转置'UTTrmmnrrrnUAV这样我们就得到了对行进行压缩的式子。可以看出，其实PCA几乎可以说是对SVD的一个包装，如果我们实现了SVD，那也就实现了PCA了，而且更好的地方是，有了SVD，我们就可以得到两个方向的PCA，如果我们对'AA进行特征值的分解，只能得到一个方向的PCA。六、利用主成分分析（PCA）进行降维9个学生各科成绩如下，能不能把数据的六个变量用几个综合变量表示？这几个综合变量包含原来多少信息呢？-8-我们现在用主成分分析法求解，得到如下结果：结果分析：如用x1,x2,x3,x4,x5,x6分别表示原先的六个变量，而用y1,y2,y3,y4,y5,y6表示新的主成分，那么，第一和第二主成分为11234560.29880.46690.15520.50340.41770.4906yxxxxxx21234560.53550.31520.58600.20240.40100.2622yxxxxxx在y1表示式中x1的系数为-0.2988，这就是说第一主成分和数学变量的相关系数为-0.2988。相关系数(绝对值）越大，主成分对该变量的代表性也越大。从第二个特征根开始，累计方差贡献率就超过了85%，也就是说，可以通过第一、第二主成分来大致表示原来的数据信息。而且可以说，第一、第二主成分表达了原来信息的85.10%。-9-七、利用奇异值分解（SVD）进行图像处理先对图像进行灰度处理，转化为二维图像，然后利用SVD算法，对图片进行压缩处理，结果如下：原图大小14kb秩k=1（维）大小9kb-10-秩k=20（维）大小11kb秩k=40（维）大小12kb-11-秩k=60（维）大小13kb结果分析：秩k越大，图像重构越完善，图像越清晰，但压缩后图片比较大；秩k越小，图像重构越粗糙，图像月模糊，但压缩后图像比较小。参考文献：主成分分析和因子分析，吴喜之，2012,,5,25奇异值分解压缩图像，DspTian，2012,10,24SVD分解算法及其应用，十一城，2013,7,14-12-附录一：%主成分分析算法%读入文件数据X=load('data.txt');%标准化处理[p,n]=size(X);forj=1:nmju(j)=mean(X(:,j));sigma(j)=sqrt(cov(X(:,j)));endfori=1:pforj=1:nY(i,j)=(X(i,j)-mju(j))/sigma(j);endendsigmaY=cov(Y);%求X标准化的协差矩阵的特征根和特征向量[T,lambda]=eig(sigmaY);fori=1:nforj=i:niflambda(i,i)lambda(j,j)a=lambda(i,i);lambda(i,i)=lambda(j,j);lambda(j,j)=a;b=T(:,i);T(:,i)=T(:,j);T(:,j)=b;endendenddisp('特征根(由大到小):');disp(lambda);disp('特征向量:');disp(T);%方差贡献率;累计方差贡献率Xsum=sum(sum(lambda,2),1);fori=1:nfai(i)=lambd