pca

2014年09月05日

PCA简介

PCA是Principal Component Analysis(主成分分析)的缩写,此方法的目标是找到数据中最主要的元素和结构,去除噪音和冗余,将原有的复杂数据降维,揭露出隐藏在复杂数据背后的简单结构。从线性代数角度来看,PCA目标是找到一组正交基去重新描述得到的数据空间,这个维度就是主元,将原数据投影到该数据空间上,就可以达到降维的目的。

K-L变换与PCA

K-L变换是Karhunen-Loeve变换的简称,是一种特殊的正交变换。它是建立在统计特性基础上的一种变换,也称做霍特林(Hotelling)变换。 K-L变换的优点是去相关性,是均方误差意义下的最佳变换。 设随机向量 \(X \in R^{n} \)(n阶列向量),它的均值向量为 \(m_x \),则协方差矩阵可以表示为:
\(Cov(x)\)是一个n*n阶的实对称矩阵。 K-L变换定义了一个正交变换\(A \in R^{n \times n}\),将\(X \in R^{n}\)的向量映射到用\(Y \in R^{n}\)代表的向量,并且使Y向量中的各分量间不相关:

PCA算法的理论依据是K-L变换,通过寻找线性变换W,实现对高维数据的降维。

混乱的数据中通常包含三种成分:噪音、旋转和冗余。在区分噪音的时候,可以使用信噪比或者方差来衡量,方差大的是主要信号或者主要分量;方差较小的则认为是噪音或者次要分量;对于旋转,则对基向量进行旋转,使得信噪比或者方差较大的基向量就是主元方向;在判断各个观测变量之间是否冗余时,可以借助协方差矩阵来进行衡量和判断。

PCA的主要思想:

1.最小化冗余量,对应于协方差矩阵的非对角线元素要尽量小;
2.最大化信号,对应于要使协方差矩阵的对角线上的元素尽可能的大。对角线上的元素值越大,也就是对应于越重要的主元。该思想实现方法就是对协方差矩阵进行对角化。

PCA的模型中存在假设条件:

1.PCA的内部模型是线性的,kernel-PCA就是使用非线性的权值对PCA扩展;
2.针对的样本的概率分布模型只限于指数概率分布模型。从而扩展出ICP(独立主元分析)。
3.数据本身具有较高的信躁比。
4.假设主元向量之间是正交的。

PCA的可视化理解

PCA的求解方法:

SVD(奇异值分解)方法 K-L变换适用于方阵,但现实中,得到的大部分矩阵不是方阵,奇异值分解方法可以获得一个变换描述矩阵的重要特征。奇异值分解的形式: 其中A是一个\(N\times M\)的矩阵,得到的\(U\)是一个\(N\times N\)的方阵(里面的向量是正交的,U里面的向量称为左奇异向量),\(\Sigma\)是一个\(N\times M\)的矩阵(除了对角线的元素都是0,对角线上的元素成为奇异值),\(V^{T}\)(V的转置)是一个\(M\times M\)的矩阵,里面的向量也是正交的,\(V^{T}\)里面的向量称为右奇异向量)。
奇异值是怎么和特征值对应起来的。
这里得到的v,就是上面的右奇异向量。此处我们还可以得到左奇异值\(\sigma_i\)和左奇异向量\(\mu_i\)

这里的\(A^{T}A\)与后面的协方差矩阵的形式统一了以来,求解出来的\(V^{T}\)与后面的\(S^{T}S\)是同构的。

得到左奇异向量或者右奇异向量后,按照特征值递减顺序组成特征向量矩阵。
则左奇异向量矩阵为\(U_{n\times r}\),右奇异向量矩阵为\(V_{r\times m}^{T}\) ,r的大小取决于\(A^{T}A\)所求得的特征矩阵\(\Sigma\). 如何把\(A_{nm}\)变成\(A_{nr}\):
如何把\(A_{nm}\)变成\(A_{rm}\):

弄清楚了SVD与PCA的关系后,PCA是SVD的再次包装,就知道怎么求解PCA了。

另外一种等价的方法 求协方差矩阵的特征向量矩阵
协方差矩阵的计算可以通过下面的公式计算:
其中\(S \in R^{n\times d}\) 是中心化后的矩阵, 协方差矩阵的计算方式(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);
sum((dim1-mean(dim1)).*(dim3-mean(dim3)))/(size(MySample,1)-1);
sum((dim2-mean(dim2)).*(dim3-mean(dim3)))/(size(MySample,1)-1);
协方差矩阵的对角线上就是各个维度上的方差
std(dim1)^2;
std(dim2)^2;
std(dim3)^2;

协方差矩阵也可以这样计算,先让样本矩阵中心化,即每一维度减去该维度的均值,使每一维度上的均值为0,然后直接用新得到的样本矩阵乘上它的转置,然后除以(N-1)。该方法可以由前面的公式推导出来。 matlab代码实现如下:

X=MySample=repmat(mean(MySample),10,1);  %  中心化样本矩阵,使各维度均值为0
C=X'*X/(size(X,1)-1);

为什么在PCA中,协方差矩阵的特征向量就是主元,等价于原矩阵的奇异值分解,主元并非降维后的样本矩阵,而是投影矩阵,原矩阵可通过投影矩阵投影达到降维的目的。
假设协方差特征矩阵为\(P_1\)(正交化后的特征矩阵为\(P\)),PCA降维后的样本矩阵为\(S_1\), 根据PCA的目的,\(S_1\)中的各个维度间的协方差基本为零,也就是说,\(S_1\)的协方差矩阵 为\(\mit\Lambda_1\),满足如下等式: 又因为 带入可得: 由于样本矩阵 \(S^{N \times d}\) 的每一行是一个样本,特征向量矩阵\(P_1^{d \times p}\)的每一列是一个特征向量。右乘\(P_1\)相当于每个样本乘以\(P_1\)的特征向量为基进行线性变换,得到的新样本矩阵\(S_1 \in R^{N\times p}\)中的每个样本的维数变为了p,完成了降维操作。 实际上,\(P_1\)的特征向量就是低维空间新的坐标系,称之为”主成分”,\(S_1\)的协方差矩阵\(\mit\Lambda_1\)为近对角矩阵,说明不同维度间已经基本独立,噪声和冗余的数据已经不见了。
但使用svd解决PCA问题,可以同时得到两个方向上的PCA。实际上在SVD中,左奇异向量需要右乘元矩阵,可以对原矩阵做列变换,可以把原矩阵的每列作为一个特征,每一行代表一个样本,进行特征维度缩减,维度由m变为r,右奇异向量\(V^{T}\)需要左乘原矩阵A,相当于对A的行向量做变换,A的每一行可看成一个特征,进行维度缩减,维度又原来的n变为r。

观察PCA后的样本协方差矩阵和原始矩阵的协方差矩阵可以发现各个维度上的方差有所变化,但对角线之和没有变,能量重新得到了分配,这就是降噪的功劳。 将原矩阵与投影矩阵相称可得到降维后的矩阵。

svd与LSI

PCA与LDA是特征抽取的两种主要经典方法 LDA(线性评判分析) 信号表示:特征抽取后的特征要能够精确地表示样本信息,使得信息丢失很小,对应的方法是PCA 信号分类:特征抽取后的特征,要使得分类后的准确率很高,不能比原来特征进行分类的准确率低。对于线性来说,对应的方法是LDA PCA不具有鉴别特性 LDA与PCA的目标不一样,导致他们的方法也不一样。PCA得到的投影空间是协方差矩阵的特征向量,而LDA则是通过求得一个变换W,使得变换之后的新均值之差最大,方差最大,变换W就是特征的投影方向。
PCA做分类时一般使用主向量作为特征进行分类,而不是降维后的矩阵来做分类。

参考文章:

奇异值分解及其应用
百度文库
PCA与SVD
Kernel PCA的推导