主成分分析 (Principal Component Analysis, PCA) 是最常用的一种降维方法

PCA寻找一个低维的超平面， 并将所有样本投影到这个超平面上，这个超平面满足

  • 最近重构性：所有样本向量到这个超平面距离都足够近
  • 最大可分性：样本向量在这个超平面上的投影尽可能分开，即投影后方差尽可能大

具体来说，PCA先寻找一组新的正交基，对所有样本进行坐标变换，再删去一部分坐标实现降维

实际上，基于最近重构性和基于最大可分性的推导得到的结果是等价的

PCA推导

假设数据集$D\in R^{d\times m}$，即每个样本$x$是一个$d$维向量，共有$m$个样本向量

首先对数据集进行中心化，即$x\leftarrow x - \frac{1}{m}\sum_{i=1}^m x_i$

当前样本空间的基为自然基，设新的基为规范正交基${w_1,w_2,…,w_d}$

显然从自然基到该正交基的过度矩阵就是$W=(w_1,w_2,…,w_d)$，其中$w_1,w_2,…,w_d$在$W$中做列向量

设向量$xi=(x{i1};x{i2};…;x{id})$在新的基下坐标为$zi=(z{i1};z{i2};…;z{id})$，其中$z_i=W^{-1}x_i=W^Tx_i$

记$X=(x_1,x_2,…,x_m),Z = (z_1,z_2,…,z_m)$，即$X,Z\in R^{d\times m}$，则$Z=W^TX$

若丢弃部分坐标，即令$W=(w1,w_2,…,w{d’})$，则由$zi’=W^Tx_i$可得维度为$d’$的低维坐标$(z{i1};z{i2};…;z{id’})$

基于最大可分性的推导

投影后样本点的协方差矩阵为$ZZ^T={W}^TX(W^TX)^T=W^TXX^TW$

为使投影后样本点的方差尽可能大，只需求 $\mathop{argmax}\limits_{W}tr(W^TXX^TW)$

其中$tr(\cdot)$为矩阵的迹，其值为方阵的特征值之和，也等于方针的主对角线元素之和

基于最近重构性的推导

设由投影点$z_i$重构的样本点为$\hat{x_i}=Wz_i$，则重构点与原样本点距离为

显然$\sum{i=1}^m x_i^Tx_i$是一个常数，因此最小化重构点与原样本间距离就是求 $\mathop{argmin}\limits{W}-tr(W^TXX^TW)$

显然两种方法推导出的结果是等价的，令约束条件为$W^TW=I$，使用拉格朗日乘数法解得

因此，只需对样本的协方差矩阵$XX^T$进行特征值分解，取最大的$d’$个特征值对应的特征向量组成$W$即可

综上，PCA的算法流程如图所示

pca