主要思想

主成分分析对原始高维空间进行线性变换，将所有数据投影到一个低维度子空间中，从而达到降维的目标。

为了寻找这 个子空间，我们基本想法是:

1. 最大可分性：样本在这个超平面的投影尽可能分得开
2. 最近重构性：样本点到超平面的距离足够近

基于最近重构性

• 目标：为了使得样本点到超平面的距离足够近

• 假如数据集是n维的，共有m个数据$(x^{(1)},x^{(2)},\dots ,x^{(m)})$，原坐标系为 $\left\{w_1,w_2,\dots ,w_n\right\},$ 其中 $w$ 是标准 正交基, 即 ||$w{\Vert }_2=1,w_i^T{w}_j=0$ 。

• 将数据从n维降到p维，则新的坐标系为 $\left\{w_1,w_2,\dots ,w_p\right\}$，样本点 $x^{(i)}$ 在p维坐标系中的投影为： $z^{(i)}={\left(z_1^{(i)},z_2^{(i)},\dots ,z_p^{(i)}\right)}^T$。其中, $z_j^{(i)}=w_j^T{x}^{(i)}$ 是 $x^{(i)}$ 在低维坐标系里第j维的坐标。

• 如果用 $z^{(i)}$ 来恢复原始数据 $x^{(i)}$,则得到的恢复数据 ${\bar{x}}^{(i)}={\sum }_{j=1}^p{z}_j^{(i)}{w}_j=W{z}^{(i)},$ 其中, $W$为标准正交基组成的矩阵，维度为nxp，可以理解为p个维度为n的基向量。

• 考虑整个样本集，我们希望所有的样本到这个超平面的距离足够近，即最小化下式：
  $$\begin{array}{rl}\sum _{i=1}^m{\Vert {\bar{x}}^{(i)}-x^{(i)}\Vert }_2^2& =\sum _{i=1}^m{\Vert W{z}^{(i)}-x^{(i)}\Vert }_2^2\\ & =\sum _{i=1}^m{\left(W{z}^{(i)}\right)}^T\left(W{z}^{(i)}\right)-2\sum _{i=1}^m{\left(W{z}^{(i)}\right)}^T{x}^{(i)}+\sum _{i=1}^m{x}^{(i)T}{x}^{(i)}\\ & =\sum _{i=1}^m{z}^{(i)T}{z}^{(i)}-2\sum _{i=1}^m{z}^{(i)T}{W}^T{x}^{(i)}+\sum _{i=1}^m{x}^{(i)T}{x}^{(i)}\\ & =\sum _{i=1}^m{z}^{(i)T}{z}^{(i)}-2\sum _{i=1}^m{z}^{(i)T}{z}^{(i)}+\sum _{i=1}^m{x}^{(i)T}{x}^{(i)}\\ & =-\sum _{i=1}^m{z}^{(i)T}{z}^{(i)}+\sum _{i=1}^m{x}^{(i)T}{x}^{(i)}\\ & =-tr\left(W^T\left(\sum _{i=1}^m{x}^{(i)}{x}^{(i)T}\right)W\right)+\sum _{i=1}^m{x}^{(i)T}{x}^{(i)}\\ & =-tr\left(W^{T}X{X}^{T}W\right)+\sum _{i=1}^m{x}^{(i)T}{x}^{(i)}\end{array}$$
  其中第（1) 步用到了 ${\bar{x}}^{(i)}=W{z}^{(i)},$ 第二步用到了平方和展开, 第 (3) 步用到了矩阵转置公式 $(AB{)}^T=B^T{A}^T$ 和 $W^{T}W=I,$ 第 (4) 步用到了
  $=W^T{x}^{(i)},$ 第 (5) 步合并同类项, 第
  (6) 步用到了 $z^{(i)}=W^T{x}^{(i)}$ 和矩阵的迹,第7步将代数和表达为矩阵形式。
  注意到 ${\sum }_{i=1}^m{x}^{(i)}{x}^{(i)T}$ 是数据集的协方差矩阵， W的每一个向量 $w_j$ 是标准正交基。而 ${\sum }_{i=1}^m{x}^{(i)T}{x}^{(i)}$ 是一个常量。最小化上式等价于:
  $$\underset{W}{\underbrace{\arg \min }}-\mathrm{tr}\left(W^{T}X{X}^{T}W\right)\text{ s.t. }{W}^{T}W=I$$
  $$J(W)=-\mathrm{tr}\left(W^{T}X{X}^{T}W+\lambda \left(W^{T}W-I\right)\right)$$
  对W求导有 $-X{X}^{T}W+\lambda W=0,$ 整理下即为
  $$X{X}^{T}W=\lambda W$$最小值对应的W由协方差矩阵 $X{X}^T$ 最大的p个特征值对应的特征向量组成。

• $\lambda$为协方差矩阵$X{X}^T$的特征值矩阵，特征值在对角线上，当数据集从n维降到p维时，只需要找到最大的p个协方差矩阵的特征值对应的特征向量组成的$W$矩阵，根据$z^{(i)}=W^T{x}^{(i)}$可以将数据降维。

基于最大投影方差

$Z=W^{T}X$代表样本在新坐标系的投影，投影方差为$W^{T}X{X}^{T}W$，最大化方差等同于最大化方差的trace
$$\underset{W}{\underbrace{\arg \max }}\mathrm{tr}\left(W^{T}X{X}^{T}W\right)\text{ s.t. }{W}^{T}W=I$$
对比基于最近重构性中的目标函数可以发现，除符合不同外两者一致。

利用拉格朗日方法
$$J(W)=\mathrm{tr}\left(W^{T}X{X}^{T}W+\lambda \left(W^{T}W-I\right)\right)$$

$$\begin{gathered} 对W求导有X{X}^{T}W+\lambda W=0整理下即为 \\ X{X}^{T}W=-\lambda W \end{gathered}$$

同上一节，-$\lambda$为协方差矩阵$X{X}^T$的特征值矩阵，特征值在对角线上。

算法流程

求样本 $x^{(i)}$的p维主成分等同于求样本集协方差矩阵的$X{X}^T$的前p个特征值对应的特征向量矩阵$W$，根据$z^{(i)}=W^T{x}^{(i)}$可以$x^{(i)}$进行降维。
输入：n维样本集$(x^{(1)},x^{(2)},\dots ,x^{(m)})$
输出：p维样本集$(x^{(1)},x^{(2)},\dots ,x^{(m)})$

1. 样本中心化 $x^{(i)}=x^{(i)}-\frac{1}{m}{\sum }_{j=1}^m{x}^{(j)}$
2. 计算协方差矩阵$X{X}^T$
3. 对$X{X}^T$进行特征值分解
4. 取出最大的p个特征值对应的特征向量，标准化后组成特征向量矩阵$W$
5. 对每个样本进行线性变化$z^{(i)}=W^T{x}^{(i)}$
6. 输出p维样本集