PCA(主成分分析)
PCA (Principal Component Analysis)是一种无监督降维方式，它将数据投影到一组互相正交的loading vectors (principal axes)之上，并保证投影后的点在新的坐标轴上的方差最大
1. 记数据集X=\begin{bmatrix}\begin{smallmatrix}\vec{x}_1\\\vec{x}_2\\\vdots\\\vec{x}_n\end{smallmatrix}\end{bmatrix}为n行p列的矩阵（n个数据，每个数据p维），数据集X中的p个特征对应的均值为\vec{\mu}=(\mu_1, \mu_2, .., \mu_p)，每个数据与均值的差异可表示为\tilde{X}=\begin{bmatrix}\begin{smallmatrix}\vec{x}_1-\vec{\mu}\\\vec{x}_2-\vec{\mu}\\\vdots\\\vec{x}_n-\vec{\mu}\end{smallmatrix}\end{bmatrix}
2. 假设需求解m个loading vector \vec{\phi}_1,\vec{\phi}_2,\cdots,\vec{\phi}_m，其中{m}\leq{\min (n-1,p)}，且需满足\vec{\phi}_i^T\vec{\phi}_i=1以及\vec{\phi}_i^T\vec{\phi}_j=0, i\neq{j}
3. 数据集X在\vec{\phi}_1上的投影为X\vec{\phi}_1，特征均值的投影为\vec{\mu}\cdot\vec{\phi}_1，则投影后数据与均值的差异可表示为\tilde{X}\vec{\phi}_1，投影后的方差为\vec{\phi}_1^T\tilde{X}^T\tilde{X}\vec{\phi}_1（省略了系数{1}/{n}）
4. 记Q=\tilde{X}^T\tilde{X}，Q即为数据集X的协方差矩阵。将Q进行特征值分解Q=V\Lambda{V^T}，其中\Lambda为对角矩阵，对角线上的元素\lambda_1,\lambda_2,\cdots,\lambda_p为特征值（不失一般性，这里令其按从大到小的顺序排列），V=\begin{bmatrix}\begin{smallmatrix}\vec{v}_1&\vec{v}_2&\cdots&\vec{v}_p\end{smallmatrix}\end{bmatrix}为正交矩阵，它的列为对应的特征向量
5. 投影后的方差可以写成\vec{\phi}_1^TV\Lambda{V^T}\vec{\phi}_1=\vec{a}_1^T\Lambda\vec{a}_1=\sum_{i=1}^p\lambda_ia_{1i}^2，因为\sum_{i=1}^pa_{1i}^2=\vec{a}_1^T\vec{a}_1=\vec{\phi}_1^TVV^T\vec{\phi}_1=\vec{\phi}_1^T\vec{\phi}_1=1，所以方差的最大值为\lambda_1，并且仅当\vec{\phi}_1=\vec{v}_1时取到
6. 数据集X在\vec{\phi}_2上投影后的方差可以表示为\sum_{i=1}^p\lambda_ia_{2i}^2（同上步类似，\vec{a}_2=V^T\vec{\phi}_2 ，\sum_{i=1}^pa_{2i}^2=1），又因为a_{21}=\vec{v}_1^T\vec{\phi}_2=\vec{\phi}_1^T\vec{\phi}_2=0，所以方差的最大值为\lambda_2，并且仅当\vec{\phi}_2=\vec{v}_2时取到
7. 对于\vec{\phi}_i, i=3,\cdots,m可以按上述步骤依次求得，方差的最大值为\lambda_i，并且仅当\vec{\phi}_i=\vec{v}_i时取到
8. 实际应用中首先将数据集X进行标准化（减去特征均值并除以特征标准差），此时协方差矩阵Q=X^TX。对X进行SVD分解，X=USV，其中U为n行n列的正交矩阵，列向量为XX^T的特征向量；V为p行p列的正交矩阵，列向量为Q的特征向量（该矩阵即为将Q进行特征值分解得到的V）；S为n行p列的矩阵且非对角线上的元素为0，对角线上的元素s_{ii}=\sqrt{\lambda_i}
LDA(线性判别分析)
LDA (Linear Discriminant Analysis)是一种有监督降维方式，假设数据集X共分为K个类，需保证投影后的点在新的坐标轴上类内离散度尽可能小，同时类间离散度尽可能大
1. 记\vec{\mu}_k为第k个类的特征均值，\vec{\mu}为总体的特征均值，则特征均值可表示为{\vec{\mu}}_k=\frac{\sum_{i\in{class}\ {k}}\vec{x}_i}{n_k},\space \vec{\mu}=\frac{\sum_{i=1}^n\vec{x}_i}{n}
2. 假设投影向量为\vec{\phi}，第k类中数据与均值的差异可表示为\tilde{X}_k=\begin{bmatrix}\vec{x}_{k_1}-{\vec{\mu}}_k\\\vec{x}_{k_2}-{\vec{\mu}}_k\\\vdots\\\vec{x}_{k_{n_k}}-{\vec{\mu}}_k\end{bmatrix}第k类的数据投影后的离散度可表示为\vec{\phi}^T\tilde{X}_k^T\tilde{X}_k\vec{\phi}，K个类的类内离散度之和为\vec{\phi}^T\sum_{k=1}^K\tilde{X}_k^T\tilde{X}_k\vec{\phi}=\vec{\phi}^TC\vec{\phi}，其中C的形式如下所示C=\sum_{k=1}^K\sum_{i\in{class}\ {k}}(\vec{x}_i-\vec{\mu}_k)^T(\vec{x}_i-\vec{\mu}_k)
3. 由PCA的第三步可以看出投影后数据的总体离散度为\vec{\phi}^T\tilde{X}^T\tilde{X}\vec{\phi}，其中\tilde{X}=\begin{bmatrix}\begin{smallmatrix}\vec{x}_1-{\vec{\mu}}\\\vec{x}_2-{\vec{\mu}}\\\vdots\\\vec{x}_n-{\vec{\mu}}\end{smallmatrix}\end{bmatrix}，则类间离散度可以表示为总体与类内离散度之差，即\vec{\phi}^T[\tilde{X}^T\tilde{X}-{C}]\vec{\phi}=\vec{\phi}^T\left[\sum_{k=1}^Kn_k({\vec{\mu}_k}-{\vec{\mu}})^T({\vec{\mu}_k}-{\vec{\mu}})\right]\vec{\phi}=\vec{\phi}^TB\vec{\phi}
4. 为了使类内离散度尽可能小，同时类间离散度尽可能大，需求解问题\underset{\vec{\phi}}{\arg\max}\frac{\vec{\phi}^TB\vec{\phi}}{\vec{\phi}^TC\vec{\phi}}对\vec{\phi}做变换\vec{\phi}=W\vec{\phi}^*（注：对C进行特征值分解C=UDU^T，记W=UD^{-1/2}），则上述问题转化为\underset{\vec{\phi}^{*}}{\arg\max} \frac{\vec{\phi}^{{*}T}W^TBW\vec{\phi}^{*}}{\vec{\phi}^{{*}T}W^TCW\vec{\phi}^{*}}=\underset{\vec{\phi}^{*}}{\arg\max} \frac{\vec{\phi}^{{*}T}W^TBW\vec{\phi}^{*}}{\vec{\phi}^{{*}T}\vec{\phi}^{*}}假设需求解m个loading vector \vec{\phi}_1^*,\vec{\phi}_2^*,\cdots,\vec{\phi}_m^*，其中{m}\leq{K-1}，上述问题可转化为\underset{\vec{\phi}^{*}}{\arg\max}\space {\vec{\phi}^{{*}T}W^TBW\vec{\phi}^{*}},\text{ where }\vec{\phi}_i^{{*}T}\vec{\phi}_i^{*}=1\text{ and }\vec{\phi}_i^{{*}T}\vec{\phi}_j^{*}=0, i\neq{j}
5. 此时可以参照PCA的做法，对W^TBW进行特征值分解W^TBW=V\Lambda{V^T}，容易看出\vec{\phi}^{*}_i=\vec{v}_i,\space i=1,2,\cdots,m（证明过程见PCA的5-7步）。综上所述，最终求得的投影向量\vec{\phi}_i=W\vec{\phi}^{*}_i，并且容易看出\vec{\phi}满足\vec{\phi}_i^{T}C\vec{\phi}_j=[W^{-1}\vec{\phi}_i]^T[W^{-1}\vec{\phi}_j]=\vec{\phi}_i^{*T}\vec{\phi}_j^*=0,\text{ }i\neq{j}
6. 对于\vec{\phi}^{*}_i，有W^TBW\vec{\phi}^{*}_i=\lambda_i\vec{\phi}^{*}_i，等式两边同时左乘W，有WW^TBW\vec{\phi}^{*}_i=\lambda_iW\vec{\phi}^{*}_i，即UD^{-1}U^TB\vec{\phi}_i=C^{-1}B\vec{\phi}_i=\lambda_i\vec{\phi}_i因此在实际求解过程中，可以直接求解C^{-1}B的特征值和特征向量，将特征值按从大到小排列取前m个特征值对应的特征向量，即为最终求得的\vec{\phi}_i
7. The Elements of Statistical Learning(2nd Edition) Section 4.3.3中给出了另外一种思路，即假设每个类内特征分布的协方差矩阵等于总体特征分布的协方差矩阵，则协方差矩阵的估计值即为矩阵C，上述这些步骤等价于通过空间变换将每个类内的协方差矩阵变为单位阵（特征之间互不相关，每个特征的方差为1），再将每个数据替换为它所在类的均值，在变换后的空间上对其进行PCA降维