主成分分析,即principal components analysis, 简称PCA,也被翻译成“主分量分析”或“主元分析”。PCA旨在利用降维的思想,把多指标转化为少数几个综合指标。在统计学中,主成分分析是一种简化数据集的技术。它是依赖于数据的线性变换。这个变换把数据变换到一个新的坐标系统中,使得任何数据投影的第一大方差在第一个坐标(称为第一主成分)上,第二大方差在第二个坐标(第二主成分)上,依次类推。主成分分析经常用减少数据集的维数,同时保持数据集的对方差贡献最大的特征。这是通过保留低阶主成分,忽略高阶主成分做到的。这样低阶成分往往能够保留住数据的最重要方面。但是,这也不是一定的,要视具体应用而定。
主成分分析法是一种降维的统计方法,它借助于一个正交变换,将其分量相关的原随机向量转化成其分量不相关的新随机向量,这在代数上表现为将原随机向量的协方差阵变换成对角形阵,在几何上表现为将原坐标系变换成新的正交坐标系,使之指向样本点散布最开的p个正交方向,然后对多维变量系统进行降维处理,使之能以一个较高的精度转换成低维变量系统,再通过构造适当的价值函数,进一步把低维系统转化成一维系统。
概括起来说,主成分分析主要由以下几个方面的作用。
奇异值分解是线性代数中一种重要的矩阵分解,在信号处理、统计学等领域有重要应用。奇异值分解在某些方面与对称矩阵或Hermite矩阵基于特征向量的对角化类似。然而这两种矩阵分解尽管有其相关性,但还是有明显的不同。对称阵特征向量分解的基础是谱分析,而奇异值分解则是谱分析理论在任意矩阵上的推广。奇异值分解在统计中的主要应用为主成分分析(PCA),它是一种数据分析方法,用来找出大量数据中所隐含的“模式”,它可以用在模式识别,数据压缩等方面。PCA算法的作用是把数据集映射到低维空间中去。 数据集的特征值(在SVD中用奇异值表征)按照重要性排列,降维的过程就是舍弃不重要的特征向量的过程,而剩下的特征向量张成空间为降维后的空间。
令\widehat{X} 为一个居中的N×P维数据矩阵(设N>P)
奇异值分解总是存在的,并针对符号唯一。V的列即为主元,且Z_j=U_jd_j
令S_q 为除了最前面的q个对角线元素之外的元素全为0的矩阵。则\widehat{X_q}=US_qV^T 满足\min_{rank(\widehat{X_q})=q} \big\Vert\widehat{X}-\widehat{X_q}\big\Vert
通过奇异值分解进行空间变换:X→Y,形成从p维到q维的变换,其中p»q,之后进行重现并计算误差。
1.只适用于一般的离散数据集,对于非线性数据集不适用。
2.虽然如此,PCA 方法还是在许多领域(例如人脸识别)得到广泛应用,此外,也有提出使用 Kernel 方法扩展 PCA 的算法,亦即先将原始数据从特征空间映射到一个高维空间中,消除其非线性的性质,然后在这样的空间中应用 PCA ,亦即 KernelPCA 方法(参见 Scholkopf, B. and Smola, A. and Muller, K.R., Kernel principal component analysis, Artificial Neural Networks—ICANN'97)。
除了 KernelPCA 之外,另一种将 PCA 用在非线性数据分析的方法是使用 LocalPCA ,现在比较热的流形学习中对于数据分布在一个低维流形上的假设实际上就是假定了数据在一个足够小的局部领域内是程线性的,这也正式 PCA 用武的地方,因此,在局部范围内使用 PCA 来分析流形结构也就成了一个顺理成章的事情。比如,在 tangent space learning 中,算法的目的是得出 manifold 的切空间,而如果使用局部方法的话,在一个流行局部的切空间其实就可以直接通过对局部 sample 进行 PCA 分解而求得。
3.以下是对课件的补充和扩展(介绍RPCA及其在CVPR2010人脸图像上的应用):
不适用于非高斯噪声污染的数据集。
设数据m\times n矩阵M=L+S,L为潜在的低秩矩阵,S噪声矩阵。如果S非高斯噪声,例如稀疏且幅值不定的噪声,那么PCA将失效。
此时,宜用改进的模型RPCA(Robust PCA)。
RPCA通过以下目标函数求解:
通过迭代计算求最优值:
1.初始化:S_{0}=Y_{0}=0,k=0
2.while \|M-L-S\|_{F}>10^{-7}\|M\|_{F} do
3. L_{k+1}=D_{1/\mu}(M-S_{k}-Y_{k}/\mu)
4. S_{k+1}=S_{\lambda/\mu}(M-L_{k+1}+Y_{k}/\mu)
5. Y_{k+1}=Y_{k}+\mu (M-L_{k+1}-S_{k+1})
6. k=k+1
7.end while
8.输出L,S
对于标量x,函数S_{a}(x)=sgn(x)max\{|x|-a,0\},即截断操作。当输入为矩阵时,对每一元素独立操作。函数D_a(X)也是截断操作,但作用于矩阵奇异值:设矩阵X的SVD分解为X=U\Sigma V^{T},那么D_a(X)=US_{a}(\Sigma)V^{T}。
对RPCA做一些修改,可用于人脸对齐与去噪。这是RPCA研究团队一篇CVPR2010的工作:
Yigang Peng, Arvind Ganesh, John Wright, Wenli Xu, and Yi Ma. RASL: Robust Alignment by Sparse and Low-rank Decomposition for Linearly Correlated Images. To appear in CVPR, June 2010.
(a)算法输入40张同一人不同光照、遮挡,姿势和表情的图片。(b)-(d)为算法输出,算法同时完成对齐(b)、提取真实人脸(c)和分离噪声(异物)(d)。算法主要思路为寻找一组几何变换\tau使对齐后的图像Dº\tau能被分解为低秩成分和稀疏噪声。
LLE算法针对非线性降维问题利用线性重构的局部对称性找出高维数据空间中的非线性结构并在保持各数据点临近位置关系情况下把高维空间数据点映射为低维空间对应的数据点其计算步骤包括计算寻找数据点或邻居数据点构造数据点及计算权值矩阵并通过权值矩阵计算低维向量。
相同点:都是降低维度的算法。可把相距很远的数据点映射在一个平面的临近位置。 不同点:PCA和MDS都是对高维空间中的可变因素的线性建模。LLE则是非线性的降维问题,不会涉及局部最小值问题。映射后,PCA和MDS无法保留流形的基本结构,而LLE则可以保证两点之间的测量距离不会改变。
(1)寻找每个样本点的k-近邻点。把相对于所求样本点距离最近的k个样本点规定为所求样本点的k-近邻点,这里k是一个预先给定值。由Sam T. Roweis 和 Lawrence K. Saul等人所提出的LLE算法中,采用了欧氏距离以减轻计算的复杂度。然而,若假定高维空间中的数据是非线性分布的,也可采用Diijstra距离。Dijkstra距离是一种图上的测地距离,它能够保持样本点之间的曲面特性。这一度量在ISOMAP算法中有广泛的应用。针对样本点多的情况,普通的Dijkstra算法不能满足LLE算法的要求。 (2)由每个样本点的近邻点计算出该样本点的局部重建权值矩阵W使得
(3) 由该样本点的局部重建权值矩阵和其近邻点计算出该样本点的输出值。
寻找X空间中的邻点
For i=1:N compute the distance from Xi to every other point Xj find the K smallest distances assign the corresponding points to be neighbors of Xi end
重构权重W
for i=1:N create matrix Z consisting of all neighbors of Xi subtract Xi from every column of Z compute the local covariance C=Z'*Z solve linear system C*w = 1 for w set Wij=0 if j is not a neighbor of I set the remaining elements in the ith row of W equal to w/sum(w); end
计算输出矩阵Y
create sparse matrix M = (I-W)'*(I-W) find bottom d+1 eigenvectors of M (corresponding to the d+1 smallest eigenvalues) set the q-th ROW of Y to be the q+1 smallest eigenvector (discard the bottom eigenvector [1,1,1,1...] with eigenvalue zero)
ISOMAP是近年来用于非线性降维的一个重要算法,它是对经典MDS的扩展,也是寻求保持数据点之间距离的低维表示。算法的基本思想是利用样本向量之间的欧氏距离Dist(i,j)计算出样本之间的测地距离DG(i,j),然后使用经典MDS算法来获得相应的低维投影。这样能够减少样本之间的欧式距离Dist(i,j)与DG(i,j)的误差,最大程度上保持高维数据内在的非线性(等距)几何结构,通过低维数据的分析来获得相应的高维数据特性,从而达到简化分析、获取数据有效特征以及可视化数据的目标。
(1)选取邻域构造邻域图G。
计算每个样本点同其余样本点之间的欧氏距离。当Xj是Xi的最近的k个点中的一个时,认为它们是相邻的,即图G有边XjXi(这种邻域称为k-邻域)。设边XjXi的权为d(Xj,Xi),对P=1,……,N有
(2)计算任意两个样本向量之间的最短路径。
当图G有边XjXi时,设最短路径如dG(Xi,Xj)=d(Xj,Xi),否则设dG(Xi,Xj)=\infty。对k=1,2,…,N,
dG(Xi,Xj)=min {dG(Xi,Xj),dG(Xi,Xk)+dG(Xk,Xj)}
(3)计算D维映射
将经典MDS应用到距离矩阵DG。
令
嵌入(Embedding)被描述为一个机器学习任务,AdaBoost方法用来把多个简单的1维嵌入结合成为一个d维的嵌入;按照与一个查询对象的相似程度获得所有DB对象的排序。
数据集S,距离函数D:S×S→ R^1
要点:D可能计算复杂;D可能不满足三角不等式。
嵌入被看做分类器,如果a与b或c接近,给出对a,b,c的估计。其中X为对象集,D\le x 为距离函数。
输出是一个分类器: H = /sum_{j=1}^dα_j\tilde{F}_j 最终输出是一个嵌入 F:X→R^d 和一个距离测度 D:R^d×R^d→R^d