主成分分析法

1 问题描述

• 给定一组向量，求其主成分方向 $$\{z_1,z_2,\dotsm ,z_N\}$$

2 问题求解

• 中心化，其$z$中心化后表示为 $$\{x_1,x_2,\dotsm, x_N\} \\ =\{z_1-\frac{1}{N}\sum_{i=1}^N z_i,z_2-\frac{1}{N}\sum_{i=1}^N z_i,\dotsm ,z_N-\frac{1}{N}\sum_{i=1}^N z_i\} \\=\{z_1-\mu,z_2-\mu,\dotsm ,z_N-\mu\}$$

• 优化目标：选择单位向量$u_1$, 最大化样本方差 $$\frac{1}{N}\sum_{i=1}^N (<x_i,u_1>)^2 \\ = \frac{1}{N}\sum_{i=1}^N u_1^Tx_ix_i^Tu_1 \\ = \frac{1}{N}\sum_{i=1}^N u_1^Tx_ix_i^Tu_1 \\ = \frac{1}{N}u_1^T X^TX u_1 \ \because X=(x_1,x_2,\dotsm, x_N)^T$$

• 求解1：使用拉格朗日法

• 优化目标 $$\left\{ \begin{matrix} \max_{u} u^T X^TX u \\ u^Tu = 1 \end{matrix} \right\}$$

• 拉格朗日函数为 $$l(u)=u^TX^TXu+\lambda(1-u^Tu)$$

• 求导得 $$\frac{\partial l}{\partial u}=2X^TXu-2\lambda u=0\\ \frac{\partial l}{\partial \lambda} = 1-u^Tu=1$$

• 可以得出 $$X^TXu=\lambda u$$

• 可见，当$u$是$X^TX$的特征向量时，上式即可变为局部最大值，且最大值特征向量对应的特征值 $$u^TX^TXu=\lambda u^Tu=\lambda$$

• 求解2：使用奇异值

• 对于$X^TX​$来说，是一个对称的矩阵，对称阵不同特征值对应的特征向量两两正交，并且这组特征向量构成了空间中的一组单位正交基$(\mu_1, \mu_2,\dotsm, \mu_N)​$。

• 因此 $$u^TX^TXu=(\sum_{i=1}^N k_i\mu_i^T)X^TX (\sum_{i=1}^N k_i\mu_i) \\ = (\sum_{i=1}^N k_i\mu_i^T)(\sum_{i=1}^N \lambda_i k_i\mu_i) \\ = \sum_{i=1}^N \lambda_i k_i^2\mu_i^T\mu_i = \sum_{i=1}^N \lambda_i k_i^2 \le \lambda_1 \sum_{i=1}^N k_i^2=\lambda_1(\sum_{i=1}^N k_i\mu_i^T)(\sum_{i=1}^N k_i\mu_i)=\lambda_1u^Tu$$

• 可以得到结论 $$\frac{\|Xu\|^2}{\|u\|^2}\le \lambda_1\\ \frac{\|Xu\|}{\|u\|}\le \sqrt{\lambda_1}=\sigma_1\\ $$

• 当$u$是最大特征对于特征向量时, $u^TX^TXu$最大，且 $$u^TX^TXu =\lambda_1u^Tu$$

• 第一主轴已经找到，第二主轴为次大特征值对应的特征向量的方向，以此类推

  • 这是因为后面的主成分方向在与前一个保持正交的前提下有最大的方差，因此第二主成分方向是剩余的特征向量的线性组合$\sum_{k=2}^N k_i\mu_i$（对称阵特征向量两两正交），因此第二主轴为次大特征值对应的特征向量的方向