600字范文 > 基于矩阵分解的PCA 白化ZCA白化

基于矩阵分解的PCA 白化ZCA白化

时间：2020-01-12 23:37:03

相关推荐

基于矩阵分解的PCA 白化ZCA白化

基于矩阵分解的PCA 白化&ZCA白化

@author: Heisenberg

主成分分析（principal component analysis, PCA）是一种常用的数据降维算法。主要思想是将nnn维的向量映射到kkk维上，这kkk维全新的正交特征也被成为主成分。通过计算数据矩阵XXX的协方差矩阵Σ\SigmaΣ，得到协方差矩阵的特征值特征向量，选择方差最大（也即特征值最大）的k个特征（坐标轴方向）组成的矩阵，以将原来的XXX变换到新的空间上。

做whitening白化（亦作sphering,球化）的处理的条件：

使数据的不同维度去相关；使数据每个维度的方差为1；

1、协方差矩阵及散度矩阵

在数据处理之前，先对数据矩阵XXX做中心化，则样本方差为

S2=1n−1Σi=1N(xi−xˉ)2S^2=\frac{1}{n-1}\Sigma_{i=1}^{N}(x_i-\bar{x})^2S2=n−11Σi=1N(xi−xˉ)2，用矩阵描述即S2=1n−1XXTS^2=\frac{1}{n-1}\mathbf{X}\mathbf{X^T}S2=n−11XXT

而散度矩阵为

S2=Σi=1n(xi−xˉ)(xi−xˉ)TS^2=\Sigma_{i=1}^{n}(\mathbf{x_i}-\mathbf{\bar{x}})(\mathbf{x_i}-\mathbf{\bar{x}})^{T}S2=Σi=1n(xi−xˉ)(xi−xˉ)T，即S2=XXTS^2=\mathbf{X}\mathbf{X^T}S2=XXT

可以看到散度矩阵即协方差矩阵乘以（样本量-1）。二者的特征值和特征向量一样的。

基本思路即对S2S^2S2进行分解。

2、特征值矩阵分解

2.1 特征值与特征向量

若一个向量vvv是矩阵A\mathbf{A}A的特征向量，则可以表示为Av=λvAv=\lambda vAv=λv，其中λ\lambdaλ称之为特征值，vvv是正交向量。

2.2 特征值分解矩阵

对于矩阵AAA，有一组特征向量vvv，将这组向量正交化单位化后，能得到一组正交单位向量。

A=QΣQ−1\mathbf{A}=Q\Sigma Q^{-1}A=QΣQ−1.

其中QQQ是A的特征向量组成的矩阵，Σ\SigmaΣ是一个对角阵，对角线上的元素就是特征值。实对称矩阵都可以分解为实特征向量和实特征值。且只有方阵才可以进行特征值分解。

3、SVD矩阵分解

对于任意矩阵AAA总是存在如下的奇异值分解：

A=UΣVTA=U\Sigma V^TA=UΣVT

也即Am×n=Um×mΣm×nVn×nTA_{m\times n}=U_{m\times m}\Sigma_{m\times n}V^T_{n\times n}Am×n=Um×mΣm×nVn×nT, 展开形式如下所示：

(x11x12x1n⋱xm1xmn)=(u11um1⋱u1mumm)(σ10⋱σr⋱00)(v11v1n⋱vn1vnn)\left(\begin{array}{cccc} x_{11} & x_{12} & & x_{1 n} \\ & & \ddots & \\ x_{m 1} & & & x_{m n} \end{array}\right)=\left(\begin{array}{ccc} u_{11} & & u_{m 1} \\ & \ddots & \\ u_{1 m} & & u_{m m} \end{array}\right)\left(\begin{array}{cccc} \sigma_{1} & & & & 0 \\ & \ddots & & & \\ & & \sigma_{r} & \\ & & & \ddots & \\ 0 & & & & 0 \end{array}\right)\left(\begin{array}{ccc} v_{11} & & v_{1 n} \\ & \ddots & \\ v_{n 1} & & v_{n n} \end{array}\right) ⎝⎛x11xm1x12⋱x1nxmn⎠⎞=⎝⎛u11u1m⋱um1umm⎠⎞⎝⎜⎜⎜⎜⎛σ10⋱σr⋱00⎠⎟⎟⎟⎟⎞⎝⎛v11vn1⋱v1nvnn⎠⎞

其中，

UUU是左奇异向量，是AATAA^TAAT单位化后的特征向量构成的正交矩阵，有UTU=IU^TU=IUTU=I,UT=U−1U^T=U^{-1}UT=U−1；

VVV是右奇异向量，是ATAA^TAATA单位化后的特征向量构成的正交矩阵，有VTV=IV^TV=IVTV=I,VT=V−1V^T=V^{-1}VT=V−1，所以奇异值分解也可以写为AV=UΣAV=U\SigmaAV=UΣ；

Σ\SigmaΣ是ATAA^TAATA(或AATAA^TAAT)的特征值求平方根后的对角矩阵。

图解：

图源自维基百科，可见左右奇异矩阵U,VU,VU,V都是旋转坐标轴，对角矩阵Σ\SigmaΣ是为了压缩数据矩阵。

4、基于特征值分解的PCA降维

4.1 基本步骤

对于数据矩阵X=[x1,x2,⋯,xn]X=[x_1,x_2,\cdots,x_n]X=[x1,x2,⋯,xn]。其中xix_ixi都是列向量

去中心化。i.e. xi−xˉx_i-\bar{x}xi−xˉ就算协方差矩阵S2=1nXXTS^2=\frac{1}{n}\mathbf{X}\mathbf{X^T}S2=n1XXT通过特征值分解法求S2S^2S2的特征值与特征向量。对特征值按照从大到小的顺序，选取最大的KKK个。将对应的K个特征向量分别作为行向量组成特征向量矩阵PPP将数据转换到K个特征向量构建的新空间中，i.e. Ym×n=Pk×mXm×nY_{m\times n}=P_{k\times m}X_{m \times n}Ym×n=Pk×mXm×n

4.2 举例

举个栗子更形象些：

对于矩阵X=(−1−1020−20011)X=\left(\begin{array}{ccccc}-1 & -1 & 0 & 2 & 0 \\ -2 & 0 & 0 & 1 & 1\end{array}\right)X=(−1−2−10002101)

求其协方差矩阵

S2=15(−1−1020−20011)(−1−2−10002101)=(65454565)S^2=\frac{1}{5}\left(\begin{array}{ccccc}-1 & -1 & 0 & 2 & 0 \\ -2 & 0 & 0 & 1 & 1\end{array}\right)\left(\begin{array}{cc}-1 & -2 \\ -1 & 0 \\ 0 & 0 \\ 2 & 1 \\ 0 & 1\end{array}\right)=\left(\begin{array}{cc}\frac{6}{5} & \frac{4}{5} \\ \frac{4}{5} & \frac{6}{5}\end{array}\right) S2=51(−1−2−10002101)⎝⎜⎜⎜⎜⎛−1−1020−20011⎠⎟⎟⎟⎟⎞=(56545456)

求解得到特征值为λ1=2,λ2=25\lambda_1=2,\lambda_2=\frac{2}{5}λ1=2,λ2=52，对应的特征向量为q1=[1,1]T,q2=[−1,1]Tq_1=[1,1]^T, q_2=[-1,1]^Tq1=[1,1]T,q2=[−1,1]T

将特征向量标准化得到q1=[12,12]T,q2=[−12,12]Tq_1=[\frac{1}{\sqrt{2}},\frac{1}{\sqrt{2}}]^T, q_2=[-\frac{1}{\sqrt{2}},\frac{1}{\sqrt{2}}]^Tq1=[21,21]T,q2=[−21,21]T

则线性变换矩阵P=(1212−1212)P=\left(\begin{array}{cc}\frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \\ -\frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}}\end{array}\right)P=(21−212121)

选取K=1，则可得到

Y=(1212)(−1−1020−20011)=(−32−12032−12)Y=\left(\begin{array}{ll} \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \end{array}\right)\left(\begin{array}{ccccc} -1 & -1 & 0 & 2 & 0 \\ -2 & 0 & 0 & 1 & 1 \end{array}\right)=\left(\begin{array}{lllll} -\frac{3}{\sqrt{2}} & -\frac{1}{\sqrt{2}} & 0 & \frac{3}{\sqrt{2}} & -\frac{1}{\sqrt{2}} \end{array}\right) Y=(2121)(−1−2−10002101)=(−23−21023−21)

5、基于SVD分解的PCA降维

5.1 基本步骤

对于数据矩阵X=[x1,x2,⋯,xn]X=[x_1,x_2,\cdots,x_n]X=[x1,x2,⋯,xn]。其中xix_ixi都是列向量

去中心化。i.e. xi−xˉx_i-\bar{x}xi−xˉ就算协方差矩阵S2=1n−1XXTS^2=\frac{1}{n-1}\mathbf{X}\mathbf{X^T}S2=n−11XXT通过SVD分解法求S2S^2S2的特征值与特征向量。对特征值按照从大到小的顺序，选取最大的KKK个。将对应的K个特征向量分别作为列向量组成特征向量矩阵PPP将数据转换到K个特征向量构建的新空间中

5.2 优点

某些SVD算法不用先求XXTXX^TXXT就求出右奇异矩阵，降低运算开销。左右两个奇异矩阵可以在行和列两个方向对数据进行压缩。i.e. Ym×k=Xm×nVn∗kTY_{m\times k}=X_{m\times n}V^T_{n*k}Ym×k=Xm×nVn∗kT ，右奇异矩阵对列进行压缩; Yk×n=Uk×mTXm×nY_{k\times n}=U^T_{k\times m}X_{m \times n}Yk×n=Uk×mTXm×n，左奇异矩阵对行数进行特征压缩。(在此说的维度转置与否都是要与原矩阵对应的)

5.3 举例

举个栗子：

对于矩阵A=(32223−2)A=\left(\begin{array}{ccc}3 & 2 & 2 \\ 2 & 3 & -2\end{array}\right)A=(32232−2)，可得到：

AAT=(178817),ATA=(131221213−22−28)A A^{T}=\left(\begin{array}{cc}17 & 8 \\ 8 & 17\end{array}\right), \quad A^{T} A=\left(\begin{array}{ccc}13 & 12 & 2 \\ 12 & 13 & -2 \\ 2 & -2 & 8\end{array}\right) AAT=(178817),ATA=⎝⎛131221213−22−28⎠⎞

对AATAA^TAAT求特征值为λ1=25,λ2=9\lambda_1=25,\lambda_2=9λ1=25,λ2=9; 特征向量为u1=(1/21/2)u2=(1/2−1/2)u_{1}=\left(\begin{array}{c}1 / \sqrt{2} \\ 1 / \sqrt{2}\end{array}\right) \quad u_{2}=\left(\begin{array}{c}1 / \sqrt{2} \\ -1 / \sqrt{2}\end{array}\right)u1=(1/21/2)u2=(1/2−1/2)对ATAA^TAATA求特征值为λ1=25,λ2=9,λ3=0\lambda_1=25,\lambda_2=9,\lambda_3=0λ1=25,λ2=9,λ3=0; 特征向量为v1=(1/21/20)v2=(1/18−1/184/18)v3=(2/3−2/3−1/3)v_{1}=\left(\begin{array}{c}1 / \sqrt{2} \\ 1 / \sqrt{2} \\ 0\end{array}\right) \quad v_{2}=\left(\begin{array}{c}1 / \sqrt{18} \\ -1 / \sqrt{18} \\ 4 / \sqrt{18}\end{array}\right) \quad v_{3}=\left(\begin{array}{c}2 / 3 \\ -2 / 3 \\ -1 / 3\end{array}\right)v1=⎝⎛1/21/20⎠⎞v2=⎝⎛1/18−1/184/18⎠⎞v3=⎝⎛2/3−2/3−1/3⎠⎞则A的SVD分解可以写作如下：

A=USVT=(1/21/21/2−1/2)(500030)(1/21/201/18−1/184/182/3−2/3−1/3)A=U S V^{T}=\left(\begin{array}{cc} 1 / \sqrt{2} & 1 / \sqrt{2} \\ 1 / \sqrt{2} & -1 / \sqrt{2} \end{array}\right)\left(\begin{array}{ccc} 5 & 0 & 0 \\ 0 & 3 & 0 \end{array}\right)\left(\begin{array}{rrr} 1 / \sqrt{2} & 1 / \sqrt{2} & 0 \\ 1 / \sqrt{18} & -1 / \sqrt{18} & 4 / \sqrt{18} \\ 2 / 3 & -2 / 3 & -1 / 3 \end{array}\right) A=USVT=(1/21/21/2−1/2)(500300)⎝⎛1/21/182/31/2−1/18−2/304/18−1/3⎠⎞

选取K=2，则对A进行列的压缩可以得到：

Y(2×2)=A(2×3)V(3∗2)Y_{(2\times 2)}=A_{(2\times 3)}V_{(3*2)}Y(2×2)=A(2×3)V(3∗2)

也即

Y=(32223−2)(1/21/181/2−1/1804/18)=(5/23/25/2−3/2)Y=\left(\begin{array}{ccc}3 & 2 & 2 \\ 2 & 3 & -2\end{array}\right)\left(\begin{array}{ccc}1 / \sqrt{2} & 1 / \sqrt{18} \\ 1 / \sqrt{2} & -1 / \sqrt{18} \\0 & 4 / \sqrt{18} \end{array}\right) =\left(\begin{array}{cc}5/\sqrt{2} & 3 / \sqrt{2} \\ 5/\sqrt{2} & -3 / \sqrt{2}\end{array}\right) Y=(32232−2)⎝⎛1/21/201/18−1/184/18⎠⎞=(5/25/23/2−3/2)

选取K=1，对A进行行的压缩可以得到：

Y(1×3)=U(1×2)TA(2×3)Y_{(1\times 3)}=U^T_{(1\times 2)}A_{(2\times 3)}Y(1×3)=U(1×2)TA(2×3)

Y=(1/21/2)(32223−2)=(5/25/20)Y=\left(\begin{array}{cc}1 / \sqrt{2} & 1 / \sqrt{2}\end{array}\right)\left(\begin{array}{ccc}3 & 2 & 2 \\ 2 & 3 & -2\end{array}\right)=\left(\begin{array}{ccc}5 / \sqrt{2} & 5 / \sqrt{2}& 0\end{array}\right) Y=(1/21/2)(32232−2)=(5/25/20)

其中u1=(1/21/2)u_{1}=\left(\begin{array}{c}1 / \sqrt{2} \\ 1 / \sqrt{2}\end{array}\right)u1=(1/21/2)称之为第一主成分，以此类推。

5.4 方差贡献率

对于特征值对角矩阵Σ=(σ1⋱σr)(r×r)\Sigma=\left(\begin{array}{ccc} \sigma_{1} & & \\ & \ddots & \\ & & \sigma_{r} \end{array}\right)_{(r\times r)}Σ=⎝⎛σ1⋱σr⎠⎞(r×r)

如果我们想保留99%的方差贡献率则使得αi=Σi=1kσiΣj=1rσj≥0.99\alpha_i = \frac{\Sigma_{i=1}^k\sigma_i}{\Sigma_{j=1}^r\sigma_j}\geq0.99αi=Σj=1rσjΣi=1kσi≥0.99即可.

Generally，75%以上就合格。

6、正则化

若在举例5.3的步骤2中不对特征向量做标准化

即XPCA−White=Σ−12UTX=[1λ1000⋱0001λn]XrotateX_{PCA-White}=\Sigma^{-\frac{1}{2}}U^TX=\left[\begin{array}{ccc} \frac{1}{\sqrt{\lambda_{1}}} & 0 & 0 \\ 0 & \ddots & 0 \\ 0 & 0 & \frac{1}{\sqrt{\lambda_{n}}} \end{array}\right]X_{rotate}XPCA−White=Σ−21UTX=⎣⎡λ11000⋱000λn1⎦⎤Xrotate

Proof:

SPCAhite2=1mXPCAwhiteXPCAwhiteT=Σ−12UT(1mXXT)U(Σ−12)T=Σ−12UTS2UΣ−12∵对角阵=Σ−12(UTU)Σ(UTU)Σ−12∵SVD分解=Σ−12IΣIΣ−12∵酉矩阵UUT=UTU=I=I\begin{aligned} S^2_{P C A \text { hite }} &=\frac{1}{m} X_{\text {PCAwhite }} X_{\text {PCAwhite }}^{T} \\ &=\Sigma^{-\frac{1}{2}} U^{T}\left(\frac{1}{m} X X^{T}\right) U\left(\Sigma^{-\frac{1}{2}}\right)^{T} \\ &=\Sigma^{-\frac{1}{2}} U^{T} S^2 U \Sigma^{-\frac{1}{2}}\quad \because \text{对角阵}\\ &=\Sigma^{-\frac{1}{2}}\left(U^{T} U\right) \Sigma\left(U^{T} U\right) \Sigma^{-\frac{1}{2}}\because \text{SVD分解} \\ &=\Sigma^{-\frac{1}{2}} I \Sigma I \Sigma^{-\frac{1}{2}}\because \text{酉矩阵}UU^T=U^TU=I \\ &=I \end{aligned} SPCAhite2=m1XPCAwhiteXPCAwhiteT=Σ−21UT(m1XXT)U(Σ−21)T=Σ−21UTS2UΣ−21∵对角阵=Σ−21(UTU)Σ(UTU)Σ−21∵SVD分解=Σ−21IΣIΣ−21∵酉矩阵UUT=UTU=I=I

通常在实践中，一般选XPCA−White,i=Xrot,iλi+ϵX_{PCA-White,i}=\frac{X_{rot,i}}{\sqrt{\lambda_i+\epsilon}}XPCA−White,i=λi+ϵXrot,i，ϵ=10−5\epsilon=10^{-5}ϵ=10−5.

原因：

有时一些特征值在数值上接近0，在缩放步骤时将导致除以一个接近0的值；这可能使数据上溢或造成数值不稳定；对图像来说，正则化项对输入图像也有一些平滑去噪（或低通滤波）的作用，可改善学习到的特征。

7、ZAC白化

Zero-phase Component Analysis Whitening 零相位成分分析白化

PCA and ZCA whitening differ only by a rotation.
——《Neural Networks: Tricks of the Trade》

ZCA白化只是在PCA白化的基础上做了一个旋转操作，使得白化之后的数据映射回源空间更加的接近原始数据。

YZAC,(m×n)=U(m×k)YPCA,(k×n)=U(m×k)U(k×m)TXm×nY_{ZAC,(m\times n)=U_{(m\times k)}Y_{PCA,(k\times n)}}=U_{(m\times k)}U^T_{(k\times m)}X_{m \times n}YZAC,(m×n)=U(m×k)YPCA,(k×n)=U(m×k)U(k×m)TXm×n

下图可以更有助加深理解。

图片源自StackChange.

图1为原始数据，图2为PCA选取的最大方差方向的新坐标轴，下方对应的为映射到新坐标轴后，原始阴影部分数据在新坐标空间的最东边，而图3进行ZAC坐标旋转之后，将阴影部分数据转到了新坐标空间的东北部分。

Proof：

∑ZCAwhite=1mXZCAwhiteXZCAwhiteT=U1mXPCAwhileXPCAwhiteUT=UIUT=I\begin{aligned} \sum_{\text {ZCAwhite }} &=\frac{1}{m} X_{\text {ZCAwhite }} X_{\text {ZCAwhite }}^{T} \\ &=U \frac{1}{m} X_{\text {PCAwhile }} X_{\text {PCAwhite }} U^{T} \\ &=U I U^{T} \\ &=I \end{aligned} ZCAwhite∑=m1XZCAwhiteXZCAwhiteT=Um1XPCAwhileXPCAwhiteUT=UIUT=I

可见其仍能保证白化的合法化，协方差矩阵是对角阵的单位矩阵。

举例1（特征值分解）：

YZCA,(2×5)=U(2×1)YPCA,(1×5)Y_{ZCA,(2\times5)}=U_{(2\times1)}Y_{PCA,(1\times5)}YZCA,(2×5)=U(2×1)YPCA,(1×5)

YZAC=(1212)(−32−12032−12)=(−3/2−1/203/2−1/2−3/2−1/203/2−1/2)Y_{ZAC}=\left(\begin{array}{ll} \frac{1}{\sqrt{2}} \\ \frac{1}{\sqrt{2}} \end{array}\right)\left(\begin{array}{lllll} -\frac{3}{\sqrt{2}} & -\frac{1}{\sqrt{2}} & 0 & \frac{3}{\sqrt{2}} & -\frac{1}{\sqrt{2}} \end{array}\right)=\left(\begin{array}{ccccc}-3/2 & -1/2 & 0 & 3/2 & -1/2 \\ -3/2 & -1/2 & 0 & 3/2 & -1/2\end{array}\right) YZAC=(2121)(−23−21023−21)=(−3/2−3/2−1/2−1/2003/23/2−1/2−1/2)

举例2（SVD分解）：

YZCA,(2×3)=U(2×1)YPCA,(1×3)Y_{ZCA,(2\times 3)}=U_{(2\times1)}Y_{PCA,(1\times 3)}YZCA,(2×3)=U(2×1)YPCA,(1×3)

YZCA=(1/21/2)(5/25/20)=(5/25/205/25/20)Y_{ZCA}=\left(\begin{array}{c}1 / \sqrt{2} \\ 1 / \sqrt{2}\end{array}\right)\left(\begin{array}{ccc}5 / \sqrt{2} & 5 / \sqrt{2}& 0\end{array}\right)=\left(\begin{array}{ccc}5/2 & 5/2 & 0 \\ 5/2 & 5/2 & 0\end{array}\right) YZCA=(1/21/2)(5/25/20)=(5/25/25/25/200)