PCA (Principal Component Analysis)主成分分析公式推导

PCA (Principal Component Analysis) 公式推导

p≥k,∀Xp∈D,Yk=f(X), $p\ge k,\mathrm{\forall }{X}_p\in \mathcal{D},Y_k=f\left(X\right),$ 即 f $f$ 将 p $p$ 维向量 X $X$ 降维到 k $k$ 维向量 Y $Y$ 。
X^=g(Y)=DY,Dp×k=(d1,⋯,dk), $\hat{X}=g\left(Y\right)=DY,D_{p\times k}=\left(\begin{array}{ccc}{d}_1,& \cdots ,& d_k\end{array}\right),$ 其中 D $\mathcal{D}$ 是样本集合。

目标函数

argminf,g∑X∈D∥X−g(f(X))∥22 $\underset{f,g}{\mathrm{a}\mathrm{r}\mathrm{g}\mathrm{m}\mathrm{i}\mathrm{n}}\underset{X\in \mathcal{D}}{\sum }\Vert X-g\left(f\left(X\right)\right){\Vert }_2^2$
s.t. ∥dj∥2=1 $\text{s.t. }\Vert d_j{\Vert }_2=1$ 且 di,dj $d_i,d_j$ 互相正交， 1≤i,j≤k $1\le i,j\le k$ 。

公式推导

1. 
   ∥dj∥2=1 $\Vert d_j{\Vert }_2=1$ 且 di,dj $d_i,d_j$ 互相正交， 1≤i,j≤k $1\le i,j\le k$ ⇒D⊺D=Ik×k $\Rightarrow D^{⊺}D=I_{k\times k}$
   ∀X∈D,φ(D,Y;X)=∥X−g(Y)∥22=∥X−DY∥22 $\mathrm{\forall }X\in \mathcal{D},\phi \left(D,Y;X\right)=\Vert X-g\left(Y\right){\Vert }_2^2=\Vert X-DY{\Vert }_2^2$
   =(X−DY)⊺(X−DY) $={\left(X-DY\right)}^{⊺}\left(X-DY\right)$
   ⇒dφ(D,Y;X)=2(X−DY)⊺d(X−DY) $\Rightarrow \mathrm{d}\phi \left(D,Y;X\right)=2{\left(X-DY\right)}^{⊺}\mathrm{d}\left(X-DY\right)$
   =−2(X−DY)⊺(dD⋅Y+D⋅dY) $=-2{\left(X-DY\right)}^{⊺}\left(\mathrm{d}D\cdot Y+D\cdot \mathrm{d}Y\right)$
   =−2(X⊺−Y⊺D⊺)(dD⋅Y+D⋅dY) $=-2\left(X^{⊺}-Y^{⊺}{D}^{⊺}\right)\left(\mathrm{d}D\cdot Y+D\cdot \mathrm{d}Y\right)$
   =−2(X⊺−Y⊺D⊺)dD⋅Y−2(X⊺−Y⊺D⊺)D⋅dY $=-2\left(X^{⊺}-Y^{⊺}{D}^{⊺}\right)\mathrm{d}D\cdot Y-2\left(X^{⊺}-Y^{⊺}{D}^{⊺}\right)D\cdot \mathrm{d}Y$
   =−2(X⊺−Y⊺D⊺)dD⋅Y−2(X⊺D−Y⊺D⊺D)dY $=-2\left(X^{⊺}-Y^{⊺}{D}^{⊺}\right)\mathrm{d}D\cdot Y-2\left(X^{⊺}D-Y^{⊺}{D}^{⊺}D\right)\mathrm{d}Y$
   =−2(X⊺−Y⊺D⊺)dD⋅Y−2(X⊺D−Y⊺)dY $=-2\left(X^{⊺}-Y^{⊺}{D}^{⊺}\right)\mathrm{d}D\cdot Y-2\left(X^{⊺}D-Y^{⊺}\right)\mathrm{d}Y$
   ⇒∂φ∂Y=−2(X⊺D−Y⊺) $\Rightarrow {\displaystyle \frac{\mathrm{\partial }\phi }{\mathrm{\partial }Y}}=-2\left(X^{⊺}D-Y^{⊺}\right)$
   ⇒f(X)=Y∗=argminYφ=D⊺X $\Rightarrow f\left(X\right)=Y^{\ast }=\underset{Y}{\mathrm{a}\mathrm{r}\mathrm{g}\mathrm{m}\mathrm{i}\mathrm{n}}\phi =D^{⊺}X$
2. 
   φ(D,Y∗;X)=∥X−g(Y∗)∥22=∥X−DY∗∥22 $\phi \left(D,Y^{\ast };X\right)=\Vert X-g\left(Y^{\ast }\right){\Vert }_2^2=\Vert X-D{Y}^{\ast }{\Vert }_2^2$
   =∥X−DD⊺X∥22 $=\Vert X-D{D}^{⊺}X{\Vert }_2^2$
   =∥(Ip×p−DD⊺)X∥22 $=\Vert \left(I_{p\times p}-D{D}^{⊺}\right)X{\Vert }_2^2$
   ⇒∑X∈Dφ(D,Y∗;X)=∑X∈D∥(Ip×p−DD⊺)X∥22 $\Rightarrow \underset{X\in \mathcal{D}}{\sum }\phi \left(D,Y^{\ast };X\right)=\underset{X\in \mathcal{D}}{\sum }\Vert \left(I_{p\times p}-D{D}^{⊺}\right)X{\Vert }_2^2$
   =∑X∈D[(Ip×p−DD⊺)X]⊺(Ip×p−DD⊺)X $=\underset{X\in \mathcal{D}}{\sum }{\left[\left(I_{p\times p}-D{D}^{⊺}\right)X\right]}^{⊺}\left(I_{p\times p}-D{D}^{⊺}\right)X$
   =∑X∈DX⊺(Ip×p−DD⊺)(Ip×p−DD⊺)X $=\underset{X\in \mathcal{D}}{\sum }{X}^{⊺}\left(I_{p\times p}-D{D}^{⊺}\right)\left(I_{p\times p}-D{D}^{⊺}\right)X$
   =∑X∈DX⊺(Ip×p−2DD⊺+DD⊺DD⊺)X $=\underset{X\in \mathcal{D}}{\sum }{X}^{⊺}\left(I_{p\times p}-2D{D}^{⊺}+D{D}^{⊺}D{D}^{⊺}\right)X$
   =∑X∈DX⊺(Ip×p−DD⊺)X $=\underset{X\in \mathcal{D}}{\sum }{X}^{⊺}\left(I_{p\times p}-D{D}^{⊺}\right)X$
   令 X=(X1,⋯,X|D|)⊺, $\mathbf{X}={\left(\begin{array}{ccc}{X}_1,& \cdots ,& X_{|\mathcal{D}|}\end{array}\right)}^{⊺},$ 其中 |D| $|\mathcal{D}|$ 是样本集合 D $\mathcal{D}$ 的大小。则
   ∑X∈Dφ(D,Y∗;X)=tr[X(Ip×p−DD⊺)X⊺] $\underset{X\in \mathcal{D}}{\sum }\phi \left(D,Y^{\ast };X\right)=\mathrm{t}\mathrm{r}\left[\mathbf{X}\left(I_{p\times p}-D{D}^{⊺}\right){\mathbf{X}}^{⊺}\right]$
   =tr[X⊺X(Ip×p−DD⊺)] $=\mathrm{t}\mathrm{r}\left[{\mathbf{X}}^{⊺}\mathbf{X}\left(I_{p\times p}-D{D}^{⊺}\right)\right]$
   =tr[X⊺X(Ip×p−DD⊺)] $=\mathrm{t}\mathrm{r}\left[{\mathbf{X}}^{⊺}\mathbf{X}\left(I_{p\times p}-D{D}^{⊺}\right)\right]$
   =tr(X⊺X−X⊺XDD⊺) $=\mathrm{t}\mathrm{r}\left({\mathbf{X}}^{⊺}\mathbf{X}-{\mathbf{X}}^{⊺}\mathbf{X}D{D}^{⊺}\right)$
   =tr(X⊺X)−tr(X⊺XDD⊺) $=\mathrm{t}\mathrm{r}\left({\mathbf{X}}^{⊺}\mathbf{X}\right)-\mathrm{t}\mathrm{r}\left({\mathbf{X}}^{⊺}\mathbf{X}D{D}^{⊺}\right)$
   =tr(X⊺X)−tr(D⊺X⊺XD) $=\mathrm{t}\mathrm{r}\left({\mathbf{X}}^{⊺}\mathbf{X}\right)-\mathrm{t}\mathrm{r}\left(D^{⊺}{\mathbf{X}}^{⊺}\mathbf{X}D\right)$
   因此
   minf,g∑X∈D∥X−g(f(X))∥22=constant+maxD tr(D⊺X⊺XD) s.t. D⊺D=I(1) $\begin{array}{}\text{(1)}& \underset{f,g}{\mathrm{m}\mathrm{i}\mathrm{n}}\underset{X\in \mathcal{D}}{\sum }\Vert X-g\left(f\left(X\right)\right){\Vert }_2^2=\text{constant}+\underset{D}{\mathrm{m}\mathrm{a}\mathrm{x}}\mathrm{t}\mathrm{r}\left(D^{⊺}{\mathbf{X}}^{⊺}\mathbf{X}D\right)\text{ s.t. }{D}^{⊺}D=I\end{array}$
   由于 X⊺X ${\mathbf{X}}^{⊺}\mathbf{X}$ 是是半正定实矩阵，因此存在 Λ=⎛⎝⎜⎜λ1,⋱λp⎞⎠⎟⎟, $\mathrm{\Lambda }=\left(\begin{array}{ccc}{\lambda }_1,& & \\ & \ddots & \\ & & {\lambda }_p\end{array}\right),$ 存在正交矩阵 P, $P,$ 使得 X⊺X=P⊺ΛP, ${\mathbf{X}}^{⊺}\mathbf{X}=P^{⊺}\mathrm{\Lambda }P,$
   且 λj≥0,λi≥λj,i≤j,1≤i,j≤p, ${\lambda }_j\ge 0,{\lambda }_i\ge {\lambda }_j,i\le j,1\le i,j\le p,$
   于是 D⊺X⊺XD=D⊺P⊺ΛPD=(PD)⊺Λ(PD) $D^{⊺}{\mathbf{X}}^{⊺}\mathbf{X}D=D^{⊺}{P}^{⊺}\mathrm{\Lambda }PD={\left(PD\right)}^{⊺}\mathrm{\Lambda }\left(PD\right)$
   令 Q=(q1⋯qk)=PD, $Q=\left(\begin{array}{ccc}{q}_1& \cdots & q_k\end{array}\right)=PD,$ 则
   Q⊺Q=D⊺P⊺PD=I $Q^{⊺}Q=D^{⊺}{P}^{⊺}PD=I$
   于是 tr(D⊺X⊺XD)=tr(Q⊺ΛQ) $\mathrm{t}\mathrm{r}\left(D^{⊺}{\mathbf{X}}^{⊺}\mathbf{X}D\right)=\mathrm{t}\mathrm{r}\left(Q^{⊺}\mathrm{\Lambda }Q\right)$
   =∑j=1k∑i=1pλiq2ij $=\underset{j=1}{\overset{k}{\sum }}\underset{i=1}{\overset{p}{\sum }}{\lambda }_i{q}_{ij}^2$
   =∑i=1pλi(∑j=1kq2ij) $=\underset{i=1}{\overset{p}{\sum }}{\lambda }_i\left(\underset{j=1}{\overset{k}{\sum }}{q}_{ij}^2\right)$
   ≤∑i=1kλi $\le \underset{i=1}{\overset{k}{\sum }}{\lambda }_i$
   小于等于是因为：
   1) ∑i=1p∑j=1kq2ij=k $\underset{i=1}{\overset{p}{\sum }}\underset{j=1}{\overset{k}{\sum }}{q}_{ij}^2=k$
   2) 由于 Q $Q$ 的列向量可扩展成一组标准正交基，因此 ∑j=1kq2ij≤1 $\underset{j=1}{\overset{k}{\sum }}{q}_{ij}^2\le 1$
   当 PD=Q=(Ik×k0) $PD=Q=\left(\begin{array}{c}{I}_{k\times k}\\ \mathbf{0}\end{array}\right)$ 时等号成立。
   此时 D⊺X⊺XD=D⊺P⊺ΛPD=Q⊺ΛQ=⎛⎝⎜⎜λ1,⋱λk⎞⎠⎟⎟, $D^{⊺}{\mathbf{X}}^{⊺}\mathbf{X}D=D^{⊺}{P}^{⊺}\mathrm{\Lambda }PD=Q^{⊺}\mathrm{\Lambda }Q=\left(\begin{array}{ccc}{\lambda }_1,& & \\ & \ddots & \\ & & {\lambda }_k\end{array}\right),$
   则 X⊺Xdj=λjdj,1≤j≤k, ${\mathbf{X}}^{⊺}\mathbf{X}{d}_j={\lambda }_j{d}_j,1\le j\le k,$
   因此 dj $d_j$ 为 X⊺X ${\mathbf{X}}^{⊺}\mathbf{X}$ 的属于特征值 λj ${\lambda }_j$ 的特征向量。

性质

设 Y=(Y1,⋯,Yk)=XD, $\mathbf{Y}=\left(\begin{array}{ccc}{Y}_1,& \cdots ,& Y_k\end{array}\right)=\mathbf{X}D,$ X=(X1,⋯,X|D|)⊺, $\mathbf{X}={\left(\begin{array}{ccc}{X}_1,& \cdots ,& X_{|\mathcal{D}|}\end{array}\right)}^{⊺},$
则 maxDVarY=maxDtr(Y⊺Y)=maxDtr(D⊺X⊺XD) $\underset{D}{\max }\mathrm{Var}\mathbf{Y}=\underset{D}{\max }\mathrm{tr}\left({\mathbf{Y}}^{⊺}\mathbf{Y}\right)=\underset{D}{\max }\mathrm{tr}\left(D^{⊺}{\mathbf{X}}^{⊺}\mathbf{X}D\right)$ s.t. D⊺D=I $D^{⊺}D=I$
这就是公式推导 1 中的式子 (1)
此时称 Yj $Y_j$ 为 Y $\mathbf{Y}$ 的第 j $j$ 个主成分 (Principal Component) 。
称 k: $k:$ Number of Principal Components.
则 Yj $Y_j$ 的方差为 λj, ${\lambda }_j,$ 且 Yi,Yj $Y_i,Y_j$ 正交， 1≤i≠j≤k $1\le i\ne j\le k$ 。

证明

Y⊺iYj=(Xdj)⊺Xdj=d⊺iX⊺Xdj=λjd⊺idj={λj,0,i=j,otherwise,1≤i,j≤k, $Y_i^{⊺}{Y}_j={\left(\mathbf{X}{d}_j\right)}^{⊺}\mathbf{X}{d}_j=d_i^{⊺}{\mathbf{X}}^{⊺}\mathbf{X}{d}_j={\lambda }_j{d}_i^{⊺}{d}_j=\{\begin{array}{ll}{\lambda }_j,& i=j,\\ 0,& \text{otherwise}\end{array},1\le i,j\le k,$

推论

Percentage of total variation retained = VarYVarX=∑i=1kλi∑i=1pλi ${\displaystyle \frac{\mathrm{Var}\mathbf{Y}}{\mathrm{Var}\mathbf{X}}}={\displaystyle \frac{\underset{i=1}{\overset{k}{\sum }}{\lambda }_i}{\underset{i=1}{\overset{p}{\sum }}{\lambda }_i}}$