主成分分析(PCA)

PCA是一种降维的方法，用于将样本从较高的N维投影到较低的K维，PCA认为最好的K维空间是将样本点转换为K维后，每一维的样本方差都很大，方差较大保证了样本点在K维空间构成的超平面上的投影能尽可能的分开。

那么如何能找到符合条件的K维空间了？下面以将样本投影到某一维上为例：
首先对所有的样本进行中心化，即将样本减去他们的均值，

上图中Xi$X_i$为其中一个样本点，将Xi$X_i$投影到u（||u||=1）$u（||u||=1）$上

由于样本点已经进行中心化，所以其每一维特征均值都是0，因此投影到u$u$上的样本点的均值仍然是0。最佳的u$u$要使得投影后的样本点方差最大，方差可以用下面式子计算：

1m∑mi=1(XTiu)2=1m∑mi=1uTXi⋅XTiu=uT⋅(1m∑mi=1Xi⋅XTi)⋅u$\frac{1}{m}\sum _{i=1}^m(X_i^{T}u{)}^2=\frac{1}{m}\sum _{i=1}^m{u}^T{X}_i\cdot X_i^{T}u=u^T\cdot (\frac{1}{m}\sum _{i=1}^m{X}_i\cdot X_i^T)\cdot u$

令λ=1m∑mi=1(XTiu)2$\lambda =\frac{1}{m}\sum _{i=1}^m(X_i^{T}u{)}^2$ ，  ∑=1m∑mi=1Xi⋅XTi$\sum =\frac{1}{m}\sum _{i=1}^m{X}_i\cdot X_i^T$   （X的协方差矩阵为1m−1∑mi=1Xi⋅XTi$\frac{1}{m-1}\sum _{i=1}^m{X}_i\cdot X_i^T$）
则：
λ=uT∑u$\lambda =u^T\sum u$ 
⟹$⟹$ λu=uλ=u⋅uT∑u=∑u$\lambda u=u\lambda =u\cdot u^T\sum u=\sum u$
⟹$⟹$ λu=∑u$\lambda u=\sum u$

λ$\lambda$是∑$\sum$的特征值，u$u$是特征向量。最佳投影直线是特征值λ$\lambda$最大时对应的特征向量，其次是λ$\lambda$第二大对应的特征向量，以此类推。

所以PCA算法如下：
输入：样本集D={X1,X2,...,Xi,...,Xm},低维空间维数K$D=\{X_1,X_2,...,X_i,...,X_m\},低维空间维数K$
过程：1.对所有样本进行中心化：Xi⟵Xi−1m∑mi=1Xi$X_i⟵X_i-\frac{1}{m}\sum _{i=1}^m{X}_i$
           2.计算样本的协方差矩阵XXT$X{X}^T$
           3.对协方差矩阵XXT$X{X}^T$做特征值分解
           4.取最大的K个特征值所对应的特征向量W1,W2,...,Wk$W_1,W_2,...,W_k$
输出：投影矩阵W∗=(W1,W2,...,Wk)$W^{\ast }=(W_1,W_2,...,W_k)$
将原数据与投影矩阵相乘即得到降维后的数据

由于数据进行了中心化，且协方差矩阵是对称的，所以Wi$W_i$是标准正交基向量,|Wi|=1,WTiWj=0$|W_i|=1,W_i^T{W}_j=0$


参考书籍：《机器学习》