目录
主成分分析(PCA)1. 坐标投影2. 最近重构性3. 最大可分性4. 求解主成分分析(PCA)
1. 坐标投影
主成分分析(PCA, Principal Component Analysis)是最常用的一种线性降维方法。
假设原来的样本是 d 维空间,样本矩阵 X=[x1x2⋯xm]∈Rd×mX=\begin{bmatrix}x_1 & x_2 & \cdots & x_m \end{bmatrix} \in \mathbb{R^{d\times m}}X=[x1x2⋯xm]∈Rd×m,xi∈Rdx_i \in \mathbb{R^d}xi∈Rd 表示第 i 个样本。为了方便起见,假设样本进行了中心化,即 ∑i=1mxi=0\sum_{i=1}^m x_i=0∑i=1mxi=0。现在要将样本投影到一个 k 维的超平面,其中 k<dk < dk<d。选取此超平面中的一组标准正交基作为坐标轴,记为 W=[w1w2⋯wk]W=\begin{bmatrix}w_1 & w_2 & \cdots & w_k \end{bmatrix}W=[w1w2⋯wk],其中 wiw_iwi 是标准正交向量,即 ∥wi∥2=1\left \| w_i\right \|_2=1∥wi∥2=1,wiTwj=0(i≠j)w_i^Tw_j=0\ (i \neq j)wiTwj=0(i̸=j)。则每个样本 xix_ixi 在这个低维坐标系中的投影为 zi=[zi1zi2⋯zik]Tz_i=\begin{bmatrix}z_{i1} & z_{i2} & \cdots & z_{ik} \end{bmatrix}^Tzi=[zi1zi2⋯zik]T, 其中 zij=wjTxiz_{ij}=w_j^T x_izij=wjTxi 是 xix_ixi 投影到第 j 个坐标轴 wjw_jwj 得到的坐标,证明如下。
证明方法一:xix_ixi 到第 j 个坐标轴 wjw_jwj 的投影长度为 wjTxi∥wi∥2=wjTxi\frac{w_j^Tx_i}{\left \| w_i\right \|_2}=w_j^Tx_i∥wi∥2wjTxi=wjTxi,因为 ∥wi∥2=1\left \| w_i\right \|_2=1∥wi∥2=1,所以投影的长度即为坐标。
证明方法二:假设 xix_ixi 投影在 wjw_jwj 的坐标为 c,则 xix_ixi 可分解为两个分量,一个分量是 c⋅wjc\cdot w_jc⋅wj,另一个是垂直 wjw_jwj 的分量,为 xi−c⋅wjx_i-c\cdot w_jxi−c⋅wj,可得 wjT(xi−c⋅wj)=0w_j^T(x_i-c\cdot w_j)=0wjT(xi−c⋅wj)=0,即 wjTxi=c∥wi∥22w_j^Tx_i=c \left \| w_i\right \|_2^2wjTxi=c∥wi∥22,因为 ∥wi∥2=1\left \| w_i\right \|_2=1∥wi∥2=1, 所以 c=wjTxic=w_j^Tx_ic=wjTxi
所以,样本 xix_ixi 在这个低维坐标系中的投影坐标为 zi=WTxiz_i=W^Tx_izi=WTxi,所有样本投影之后的结果是 Z=WTXZ=W^TXZ=WTX,ZZZ 的每一列是一个新的样本坐标。下面使用两种优化目标来推导 PCA 的求解公式。
2. 最近重构性
投影之后,利用投影得到的坐标 ziz_izi 来重构 xix_ixi,得到 x^i=∑j=1kzijwj=Wzi\hat{x}_i=\sum_{j=1}^kz_{ij}w_j=Wz_ix^i=∑j=1kzijwj=Wzi。由于 k 比 d 小,因此投影之后一般会有信息损失(除非所有 xix_ixi 都在 k 维超平面上,即 WWW 的列空间里)。信息损失为 ∥xi−x^i∥22\left \| x_i-\hat{x}_i\right \|_2^2∥xi−x^i∥22, 即 xix_ixi 到上述 k 维超平面的距离。要想使信息损失最小,则需要让所有样本到超平面的距离最小化,如下:
∑i=1m∥xi−x^i∥22=∑i=1m∥xi−Wzi∥22=∥X−WZ∥22\sum_{i=1}^m\left \| x_i-\hat{x}_i\right \|_2^2=\sum_{i=1}^m\left \| x_i-Wz_i\right \|_2^2=\left \|X-WZ\right \|_2^2i=1∑m∥xi−x^i∥22=i=1∑m∥xi−Wzi∥22=∥X−WZ∥22 把 Z=WTXZ=W^TXZ=WTX 代入,根据 ∥A∥22=tr(ATA)=tr(AAT)\left \| A\right \|_2^2=tr(A^TA)=tr(AA^T)∥A∥22=tr(ATA)=tr(AAT) 得
∥X−WWTX∥22=tr((X−WWTX)T(X−WWTX))=tr((XT−XTWWT)(X−WWTX))=tr(XTX−2⋅XTWWTX+XTWWTWWTX)=tr(XTX−2⋅XTWWTX+XTWWTX)=tr(XTX−XTWWTX)=tr(XTX)−tr(XTWWTX)\begin{aligned} \left \|X-WW^TX\right \|_2^2 & =tr((X-WW^TX)^T(X-WW^TX)) \\ & = tr((X^T-X^TWW^T)(X-WW^TX)) \\ & = tr(X^TX-2\cdot X^TWW^TX+X^TWW^TWW^TX) \\ & = tr(X^TX-2\cdot X^TWW^TX+X^TWW^TX)\\ & = tr(X^TX-X^TWW^TX) \\ & = tr(X^TX)-tr(X^TWW^TX) \end{aligned}∥∥X−WWTX∥∥22=tr((X−WWTX)T(X−WWTX))=tr((XT−XTWWT)(X−WWTX))=tr(XTX−2⋅XTWWTX+XTWWTWWTX)=tr(XTX−2⋅XTWWTX+XTWWTX)=tr(XTX−XTWWTX)=tr(XTX)−tr(XTWWTX) 上面的变换主要利用了 WTW=IW^TW=IWTW=I,注意 WWW 不是方阵,因此 WWT≠IWW^T \neq IWWT̸=I,不能消去。由于 tr(XTX)tr(X^TX)tr(XTX) 是常数,可以从优化目标里去掉,并且:
tr(XTWWTX)=tr((WTX)T(WTX))=tr((WTX)(WTX)T)=tr(WTXXTW)tr(X^TWW^TX)=tr((W^TX)^T(W^TX))=tr((W^TX)(W^TX)^T)=tr(W^TXX^TW) tr(XTWWTX)=tr((WTX)T(WTX))=tr((WTX)(WTX)T)=tr(WTXXTW) 因此最后的优化目标如下:
maxWtr(WTXXTW)s.t.WTW=I\max_W tr(W^TXX^TW) \\ s.t. \quad W^TW=IWmaxtr(WTXXTW)s.t.WTW=I 由于样本做了中心化,因此 XXTXX^TXXT 是协方差矩阵。
3. 最大可分性
除了要求信息损失最小之外,也可以从另一个角度去优化,我们希望投影之后的点在超平面上尽可能地分散开,不要都挤到一起,即使投影后的样本点方差最大化。由于 ∑i=1mzi=∑i=1mWTxi=WT∑i=1mxi=0\sum_{i=1}^mz_i=\sum_{i=1}^mW^Tx_i=W^T\sum_{i=1}^mx_i=0∑i=1mzi=∑i=1mWTxi=WT∑i=1mxi=0 (因为 xix_ixi 做了中心化),可以得出 ziz_izi 的均值也为 000。所以投影后方差可以表示为
∑i=1m∥zi∥22=∥Z∥22=∥WTX∥22\sum_{i=1}^m\left \|z_i\right \|_2^2=\left \|Z\right \|_2^2=\left \| W^TX \right \|_2^2i=1∑m∥zi∥22=∥Z∥22=∥∥WTX∥∥22 根据 ∥A∥22=tr(ATA)=tr(AAT)\left \| A\right \|_2^2=tr(A^TA)=tr(AA^T)∥A∥22=tr(ATA)=tr(AAT), 有:
∥WTX∥22=tr((WTX)(WTX)T)=tr(WTXXTW)\left \| W^TX \right \|_2^2=tr((W^TX)(W^TX)^T)=tr(W^TXX^TW)∥∥WTX∥∥22=tr((WTX)(WTX)T)=tr(WTXXTW) 因此优化目标为:
maxWtr(WTXXTW)s.t.WTW=I\max_W tr(W^TXX^TW) \\ s.t. \quad W^TW=IWmaxtr(WTXXTW)s.t.WTW=I
4. 求解
使用拉格朗日乘子法,令导数为0,可得
XXTW=λWXX^TW=\lambda WXXTW=λW 对 XXTXX^TXXT 进行特征值分解,将得到的特征值从大到小排列,前 k 个特征值对应的特征向量即为 WWW 的各个列向量。然后用 WTXW^TXWTX 就可求得降维后的样本矩阵 ZZZ。