PCA算法总结

.摘要： PCA（Principal Component Analysis),称主成分分析，从统计学的角度来说是一种多元统计方法。PCA通过将多个变量通过线性变换以选出较少的重要变量。它往往可以有效地从过于“丰富”的数据信息中获取最重要的元素和结构，去除数据的噪音和冗余，将原来复杂的数据降维，揭示隐藏在复杂数据背后的简单结构。近年来，PCA方法被广泛地运用于计算机领域，如数据降维、图像有损压缩、特征追踪等等。引言：在人脑的生理特征中，人脑对外界的认知手段多样，导致人获取的信息维数过高。如果人脑不对获取的信息进行降维处理，那么人脑对信息处理的效率和精准度都会下降，因此人脑对这些感知神经处理时，均通过了复杂的降维处理。PCA方法广泛运用于从神经科学到计算机图形学的数据分析。因为它是一种简单的非参方法，能够从复杂的数据集中提取出数据相关信息。我们进行主成分分析的动机是希望计算出一个含有噪音数据空间的最重要的基，来重新表达这个数据空间。但是这些新基往往隐藏在复杂的数据结构中，我们需要滤除噪音来找到重构出数据空间的新基。 PCA方法是一个高普适用方法，它的一大优点是能够对数据进行降维处理，我们通过PCA方法求出数据集的主元，选取最重要的部分，将其余的维数省去，从而达到降维和简化模型的目的，间接地对数据进行了压缩处理，同时很大程度上保留了原数据的信息，就如同人脑在感知神经处理时进行了降维处理。 所以在机器学习和模式识别及计算机视觉领域，PCA方法被广泛的运用。在人脸识别中，假设训练集是30幅不同的NN大小的人脸图像。把图像中每一个像素看成是一维信息，那么一副图像就是N2维的向量。因为人脸的结构有极大的相似性，如果是同一个人脸的话相似性更大。而我们的所希望能够通过人脸来表达人脸，而非用像素来表达人脸。那么我们就可以用PCA方法对30幅训练集图像进行处理，寻找这些图像中的相似维度。我们提取出最重要的主成份后，让被识别图像与原图进行过变化后的主元维度进行相似度比较，以衡量两幅图片的相似性。在图像压缩方面，我们还可以通过PCA方法进行图像压缩，又称Hotelling或者Karhunen and Leove变换。我们通过PCA提取出图像的主分量，去除掉一些次分量，然后变换回原图像空间，图像因为维数的降低得到了很大程度上的压缩，同时图像还很大程度上保留了原图像的重要信息。正文：PCA方法其实就是将数据空间通过正交变换映射到低维子空间的过程。而相应的基向量组应满足正交性且由基向量组构成的地位子空间最优地考虑了数据的相关性。在原数据集变换空间后应使单一数据样本的相互相关性降低到最低点。图1 红点代表原始数据点；绿点代表被映射到低维空间后的点；紫线代表映射平面。方差最大化上面我们说过PCA方法的过程其实是寻找低维子空间的过程。那么什么样的低维空间才符合我们要求的呢。因为我们希望被映射后的数据之间的相关性降低到最低点，所以我们可以采取求解被映射后方差最大化的最优策略来找到低维空间。假设我们有N个样本数据xn,每个样本数据是D维，我们希望样本数据映射到M1维情况，协方差矩阵S应该有M个特征特征值：，其对应的特征向量应为：u1,un。误差最小化PCA的另一种构造形式是基于误差最小化。我们引入D维完备正交基向量组，即（6）所以我们可以用完备正交基向量来线形表示样本数据集中的每一个数据xn，（7）充分利用根据等式（6）的正交属性，利用等式（7）可得系数,反代回等式（7），可得等式：（8）我们来看，表达等式（8）需要D维信息，而我们的目的是希望用MD维信息近似地表达出xn：（9）代表的是数据点的特殊分量，而bi代表的是所有数据点的所共有的分量。我们构造一个目标函数:（10）其通俗的含义是我们希望通过M维表达的出的数据点逼近D维样本数据点,这里我们采用欧式距离衡量两个数据点的相似性。那么我们的问题又转化为最小化目标函数J。通过求导，我们可以得出：（11）（12）反代回等式（10），得：（13）因此我们只要找寻协方差矩阵S的D-M个最小特征值就可。SVD奇异值分解PCA方法中对于协方差矩阵的分解，提取主成分，采用两种方法：1 特征值分解。该种方法有一定局限性，分解的矩阵必须为方阵。2 SVD奇异值分解。奇异值分解是线性代数中的一种重要的矩阵分解方法，在信号处理、统计学等领域都有重要的应用。奇异值分解可以将一个比较复杂的矩阵分解为几个更小更简单的子矩阵相乘的形式来表达，而这些子矩阵描述的是原矩阵的重要的特性。对于一个MN大小的矩阵A来说，总是可以分解为:（14）其中U和V分别是AAT和ATA的特征向量，而则是他们的特征根。在PCA方法中，我们选取P个最大特征根及其所对应的特征向量，对A进行逼近：（15）线性代数理论证明：A与A在最小二乘法的意义下是逼近的。而当P越接近N，则逼近的结果越接近于原矩阵。所以当我们选取的P远小于N时，所需要存储的信息量就会越小，达到了降维和压缩的目的。一、简介 PCA（Principal Components Analysis）即主成分分析，是图像处理中经常用到的降维方法，大家知道，我们在处理有关数字图像处理方面的问题时，比如经常用的图像的查询问题，在一个几万或者几百万甚至更大的数据库中查询一幅相近的图像。这时，我们通常的方法是对图像库中的图片提取响应的特征，如颜色，纹理，sift，surf，vlad等等特征，然后将其保存，建立响应的数据索引，然后对要查询的图像提取相应的特征，与数据库中的图像特征对比，找出与之最近的图片。这里，如果我们为了提高查询的准确率，通常会提取一些较为复杂的特征，如sift，surf等，一幅图像有很多个这种特征点，每个特征点又有一个相应的描述该特征点的128维的向量，设想如果一幅图像有300个这种特征点，那么该幅图像就有300*vector（128维）个，如果我们数据库中有一百万张图片，这个存储量是相当大的，建立索引也很耗时，如果我们对每个向量进行PCA处理，将其降维为64维，是不是很节约存储空间啊？对于学习图像处理的人来说，都知道PCA是降维的，但是，很多人不知道具体的原理，为此，我写这篇文章，来详细阐述一下PCA及其具体计算过程：二、PCA详解1、原始数据：为了方便，我们假定数据是二维的，借助网络上的一组数据，如下：x=2.5, 0.5, 2.2, 1.9, 3.1, 2.3, 2, 1, 1.5, 1.1Ty=2.4, 0.7, 2.9, 2.2, 3.0, 2.7, 1.6, 1.1, 1.6, 0.9T2、计算协方差矩阵什么是协方差矩阵？相信看这篇文章的人都学过数理统计，一些基本的常识都知道，但是，也许你很长时间不看了，都忘差不多了，为了方便大家更好的理解，这里先简单的回顾一下数理统计的相关知识，当然如果你知道协方差矩阵的求法你可以跳过这里。（1）协方差矩阵：首先我们给你一个含有n个样本的集合，依次给出数理统计中的一些相关概念：均值：标准差：方差：既然我们都有这么多描述数据之间关系的统计量，为什么我们还要用协方差呢？我们应该注意到，标准差和方差一般是用来描述一维数据的，但现实生活我们常常遇到含有多维数据的数据集，最简单的大家上学时免不了要统计多个学科的考试成绩。面对这样的数据集，我们当然可以按照每一维独立的计算其方差，但是通常我们还想了解这几科成绩之间的关系，这时，我们就要用协方差，协方差就是一种用来度量两个随机变量关系的统计量，其定义为：从协方差的定义上我们也可以看出一些显而易见的性质，如：(X的方差)需要注意的是，协方差也只能处理二维问题，那维数多了自然就需要计算多个协方差，比如n维的数据集就需要计算个协方差，那自然而然的我们会想到使用矩阵来组织这些数据。给出协方差矩阵的定义：这个定义还是很容易理解的，我们可以举一个简单的三维的例子，假设数据集有三个维度，则协方差矩阵为可见，协方差矩阵是一个对称的矩阵，而且对角线是各个维度上的方差。（2）协方差矩阵的求法：协方差矩阵计算的是不同维度之间的协方差，而不是不同样本之间的。下面我们将在matlab中用一个例子进行详细说明：首先，随机产生一个10*3维的整数矩阵作为样本集，10为样本的个数，3为样本的维数。MySample = fix(rand(10,3)*50)根据公式，计算协方差需要计算均值，那是按行计算均值还是按列呢，我一开始就老是困扰这个问题。前面我们也特别强调了，协方差矩阵是计算不同维度间的协方差，要时刻牢记这一点。样本矩阵的每行是一个样本，每列为一个维度，所以我们要按列计算均值。为了描述方便，我们先将三个维度的数据分别赋值：dim1 = MySample(:,1);dim2 = MySample(:,2);dim3 = MySample(:,3);计算dim1与dim2，dim1与dim3，dim2与dim3的协方差：sum( (dim1-mean(dim1) .* (dim2-mean(dim2) ) / ( size(MySample,1)-1 ) % 得到 74.5333sum( (dim1-mean(dim1) .* (dim3-mean(dim3) ) / ( size(MySample,1)-1 )% 得到 -10.0889sum( (dim2-mean(dim2) .* (dim3-mean(dim3) ) / ( size(MySample,1)-1 )% 得到 -10*000搞清楚了这个后面就容易多了，协方差矩阵的对角线就是各个维度上的方差，下面我们依次计算：std(dim1)2 % 得到 108.3222std(dim2)2% 得到 260.6222std(dim3)2% 得到 94.1778这样，我们就得到了计算协方差矩阵所需要的所有数据，调用Matlab自带的cov函数进行验证：cov(MySample)可以看到跟我们计算的结果是一样的，说明我们的计算是正确的。但是通常我们不用这种方法，而是用下面简化的方法进行计算：先让样本矩阵中心化，即每一维度减去该维度的均值，然后直接用新的到的样本矩阵乘上它的转置，然后除以(N-1)即可。其实这种方法也是由前面的公式通道而来，只不过理解起来不是很直观而已。大家可以自己写个小的矩阵看一下就明白了。其Matlab代码实现如下：X = MySample repmat(mean(MySample),10,1); % 中心化样本矩阵C = (X*X)./(size(X,1)-1)（为方便对matlab不太明白的人，小小说明一下各个函数，同样，对matlab有一定基础的人直接跳过：B = repmat(A,m,n )%将矩阵 A 复制 mn 块，即把 A 作为 B 的元素，B 由 mn 个 A 平铺而成。B 的维数是 size(A,1)*m, (size(A,2)*nB = mean(A)的说明：如果你有这样一个矩阵：A = 1 2 3; 3 3 6; 4 6 8; 4 7 7;用mean(A)（默认dim=1）就会求每一列的均值ans = 3.0000 4.5000 6.0000用mean(A,2)就会求每一行的均值ans = 2.0000 4.0000 6.0000 6.0000size(A,n)%如果在size函数的输入参数中再添加一项n，并用1或2为n赋值，则 size将返回矩阵的行数或列数。其中r=size(A,1)该语句返回的是矩阵A的行数， c=size(A,2) 该语句返回的是矩阵A的列数）上面我们简单说了一下协方差矩阵及其求法，言归正传，我们用上面简化求法，求出样本的协方差矩阵为： 3、计算协方差矩阵的特征向量和特征值因为协方差矩阵为方阵，我们可以计算它的特征向量和特征值，如下：eigenvectors,eigenvalues = eig(cov)我们可以看到这些矢量都是单位矢量，也就是它们的长度为1，这对PCA来说是很重要的。4、选择成分组成模式矢量求出协方差矩阵的特征值及特征向量之后，按照特征值由大到小进行排列，这将给出成分的重要性级别。现在，如果你喜欢，可以忽略那些重要性很小的成分，当然这会丢失一些信息，但是如果对应的特征值很小，你不会丢失很多信息。如果你已经忽略了一些成分，那么最后的数据集将有更少的维数，精确地说，如果你的原始数据是n维的，你选择了前p个主要成分，那么你现在的数据将仅有p维。现在我们要做的是组成一个模式矢量，这只是几个矢量组成的矩阵的一个有意思的名字而已，它由你保持的所有特征矢量构成，每一个特征矢量是这个矩阵的一列。对于我们的数据集，因为有两个特征矢量，因此我们有两个选择。我们可以用两个特征矢量组成模式矢量： 我们也可以忽略其中较小特征值的一个特征矢量，从而得到如下模式矢量： 5、得到降维后的数据其中rowFeatureVector是由模式矢量作为列组成的矩阵的转置，因此它的行就是原来的模式矢量，而且对应最大特征值的特征矢量在该矩阵的最上一行。rowdataAdjust是每一维数据减去均值后，所组成矩阵的转置，即数据项目在每一列中，每一行是一维，对我们的样本来说即是，第一行为x维上数据，第二行为y维上的数据。FinalData是最后