PCA原理

在介绍PCA的原理前，首先回顾一下坐标系的变换以及向量的点积。两个向量的点乘代表着一个向量在另一个向量方向上的投影，并乘上另一个向量的长度。如果另一个向量刚好是单位向量，那就纯粹是一个向量在另一个单位向量上的投影：$\frac{\vec{a}\vec{b}}{|\vec{a}|} = |\vec{b}|cos\theta$。回顾坐标系，一个向量在某个坐标系的坐标分别是该向量在各坐标轴上的投影长度，因此向量的坐标可以由其在某坐标系$x’Oy’$的坐标$x’, y’$与各坐标轴方向的单位向量的乘积得出。举个例子，在平面直角坐标系中，向量(1, 1)的坐标就是(1, 1)，如果将其坐标系整体逆时针旋转45度，即新的坐标轴变成 $(\frac{\sqrt{2}}{2}, \frac{\sqrt{2}}{2})$以及$(\frac{-\sqrt{2}}{2}, \frac{\sqrt{2}}{2})$，那么新的坐标将变成：

$\begin{vmatrix} \frac{\sqrt{2}}{2} & \frac{\sqrt{2}}{2} \\ \frac{-\sqrt{2}}{2}& \frac{\sqrt{2}}{2} \end{vmatrix} \cdot \begin{vmatrix} 1 \\ 1 \end{vmatrix} = \begin{vmatrix} \sqrt{2} \\ 0 \end{vmatrix}$

PCA的作用就是给原始数据找一个新的坐标系，使得数据在新的坐标系下，每个字段方差最大，也就是最容易区分彼此，尽可能保留原始数据。假设这样的一个新的坐标系记为$H$, 其中$H$每一行向量都是新坐标系的每一个坐标轴坐标，是单位向量，而数据矩阵$X$每一列就是原始的一个数据样本。因此经过PCA转换后的坐标为：

$Z=HX$

在这里，我们假设X已经进行中心化，也就是所有样本每一维的均值都是0，我们还希望转换后每一个样本尽可能分散分布，也就是转换后的坐标字段间协方差最大，防止出现冗余数据，尽量加大压缩比例。总结而言就是两个目标：

字段方差最大，从而保留尽可能多的信息
字段间协方差绝对值最小（最优值为0），尽量减少冗余信息

即：

$argmax_H tr(ZZ^T) = argmax_H tr(HXX^TH^T)\\ ZZ^T=diag(z_1, z_2, ..., z_n)$

这里我们解释下为什么需要$ZZ^T$而不是$Z^TZ$等之类的其他式子最大：我们知道，$Z$的每一列都是一个新的样本(sample)，每一行是坐标的一维，或称一个字段，那么$ZZ^T$的对角线就是每一个字段的方差和，第i行第j列的元素表示第i个字段和第j个字段的协方差。注意，是字段的方差和协方差，直接讨论样本的方差和协方差（即$Z^TZ$）是没有意义的，下面我们再解释为什么。
由第二个目标，我们知道，转换后的坐标系彼此之间应该线性无关，为什么呢，因为仅凭第一个目标约束条件，$H$的每一行的约束没有差别，$H$的每一行将得到完全一样的优化结果，因此我们需要添加约束使得结果唯一。假设$ZZ^T$满足第二个条件，由于$XX^T$又是实对称矩阵，那么只要$H$是正交矩阵就能满足这个要求（注意这个是充分不必要条件，非正交矩阵$H$也能用于矩阵对角化，注意，如果是相似对角化那么这个就是充分必要条件了，相似对角化是$H^{-1}AH$这种形式的），为了结果的唯一性，我们选取$H$为单位正交矩阵，因此我们有一个额外的约束就是$H$每行向量单位正交，也就是：

$HH^T = I$

综上，使用拉格朗日乘子法，列出：

$f(H, XX^T) = tr(HXX^TH^T) - \vec{\alpha} tr(HH^T-I)$

分别求导得：

$\begin{align} \frac{df}{dH} = tr(2XX^TH^T - 2\vec{\alpha} H^T) &= 0 \\ \Rightarrow XX^TH^T &= \vec{\alpha} H^T \\ \end{align}$

显然$H$是$XX^T$的特征向量，代回$f(H, XX^T)$得$f(H, XX^T) = \vec{\alpha} I$
注意理解时将$f$拆开成一行一行来看，每一行的最大化实际上就是最大化这一行对应的特征值，由此可知，若$\vec{\alpha}$取$XX^T$最大的前k个特征值便可最大化$f$，与此相对应，H总共有k行，每一行是对应的特征向量。

P.S. 解释下为什么$Z^TZ$没有意义，因为不管哪个假设，我们都限定了$H$是单位正交，我们有：

$Z^TZ =X^TH^THX = X^TX$

也就是，$Z^TZ$根本与$H$的选取无关，如果$H$满足单位正交矩阵的性质。

整体流程

首先对$X$进行中心化
求出$XX^T$的特征值和特征向量
根据要求，取前k大特征值及其对应的特征向量，特征向量作为$H$每行的向量，转换后的数据为$Z = H\cdot X$

附录

为什么对角化不需要正交

假设正交矩阵$Q$满足$QAQ^T=\Lambda$，那么我们有：

$\begin{align} QAQ^T&=\Lambda = \sqrt{\Lambda}\sqrt{\Lambda}^T \\ \Rightarrow \sqrt{\Lambda}^{-1}QAQ^T(\sqrt{\Lambda}^{T})^{-1} &= (\sqrt{\Lambda}^{-1}Q)A(\sqrt{\Lambda }^{-1}Q)^T \\ \Rightarrow Q'AQ'^T &=I, where\ Q'=\sqrt{\Lambda}^{-1}Q\\ \Rightarrow A &= (Q'^{-1})(Q'^T)^{-1} \\ &= Q'^{-1}(Q'^{-1})^{T}\\ \Rightarrow (A^{-1})^T&= Q'Q'^T \end{align}$

可以看到，$Q’$并非正交矩阵，其相乘为$(A^{-1})^T$而不是$\Lambda$