PCA与LDA介绍

PCA(主成分分析)

PCA是一种无监督降维方式，它将数据投影到一组互相正交的loading vectors(principal axes)之上，并保证投影后的点在新的坐标轴上的方差最大

记数据集(X=egin{bmatrix}egin{smallmatrix}vec{x_1}\vec{x_2}\vdots\vec{x_n}end{smallmatrix}end{bmatrix})为n行p列的矩阵（n个数据，每个数据p维），特征均值为(vec{mu}=(mu_1, mu_2, .., mu_p))，数据与均值的差异可表示为( ilde{X}=egin{bmatrix}egin{smallmatrix}vec{x_1}-vec{mu}\vec{x_2}-vec{mu}\vdots\vec{x_n}-vec{mu}end{smallmatrix}end{bmatrix})
假设需求解m个loading vector (vec{phi}_1,vec{phi}_2,...,vec{phi}_m)，({m}leq{min(n-1,p)})，且需满足(vec{phi}_i^Tvec{phi}_i=1)以及(vec{phi}_i^Tvec{phi}_j=0, i eq{j})
(X)在(vec{phi}_1)上的投影为(Xvec{phi}_1)，特征均值的投影为(vec{mu}cdotvec{phi}_1)，则投影后数据与均值的差异可表示为( ilde{X}vec{phi}_1)，投影后的方差为(vec{phi}_1^T ilde{X}^T ilde{X}vec{phi}_1)（省略了系数(frac{1}{n})）
记(Q= ilde{X}^T ilde{X})，(Q)即为数据集X的协方差矩阵。将(Q)进行特征值分解(Q=VLambda{V^T})，其中(Lambda)为对角矩阵，对角线上的元素为特征值（不失一般性，这里令其按从大到小的顺序排列）；(V=egin{bmatrix}egin{smallmatrix}vec{v_1}&vec{v_2}&cdots&vec{v_p}end{smallmatrix}end{bmatrix})为正交矩阵，它的列为对应的特征向量
投影后的方差可以写成(vec{phi}_1^TVLambda{V^T}vec{phi}_1=vec{a}_1^TLambdavec{a}_1=sum_{i=1}^plambda_ia_{1i}^2)，因为(sum_{i=1}^pa_{1i}^2=vec{a}_1^Tvec{a}_1=vec{phi}_1^TVV^Tvec{phi}_1=vec{phi}_1^Tvec{phi}_1=1)，所以方差的最大值为(lambda_1)，并且仅当(vec{phi}_1=vec{v}_1)时取到
(X)在(vec{phi}_2)上投影后的方差可以表示为(sum_{i=1}^plambda_ia_{2i}^2)（同上步类似，(vec{a}_2=V^Tvec{phi}_2) ，(sum_{i=1}^pa_{2i}^2=1)），又因为(a_{21}=vec{v}_1^Tvec{phi}_2=vec{phi}_1^Tvec{phi}_2=0)，所以方差的最大值为(lambda_2)，并且仅当(vec{phi}_2=vec{v}_2)时取到
对于(vec{phi}_i, i=3,...,m)可以按上述步骤依次求得，方差的最大值为(lambda_i)，并且仅当(vec{phi}_i=vec{v}_i)时取到
实际应用中首先将数据集(X)进行标准化（减去特征均值并除以特征标准差），此时协方差矩阵(Q=X^TX)。对(X)进行SVD分解，(X=USV)，其中(U)为n行n列的正交矩阵，列向量为(XX^T)的特征向量；(V)为p行p列的正交矩阵，列向量为(X^TX)的特征向量（即同将(Q)进行特征值分解得到的(V)）；(S)为n行p列的矩阵且非对角线上的元素为0，对角线上的元素(s_{ii}=sqrt{lambda_i})

LDA(线性判别分析)

LDA是一种有监督降维方式，假设数据集(X)共分为(K)个类，需保证投影后的点在新的坐标轴上类内离散度尽可能小，同时类间离散度尽可能大

记(vec{mu}_k)为第k个类的特征均值，(vec{mu})为总体的特征均值，则特征均值为({vec{mu}}_k=frac{sum_{iin{class} {k}}vec{x}_i}{n_k})，({vec{mu}}=frac{sum_{i=1}^nvec{x}_i}{n})
假设投影向量为(vec{phi})，第k类中数据与均值的差异可表示为( ilde{X}_k=egin{bmatrix}egin{smallmatrix}vec{x}_{k_1}-{vec{mu}}_k\vec{x}_{k_2}-{vec{mu}}_k\vdots\vec{x}_{k_{n_k}}-{vec{mu}}_kend{smallmatrix}end{bmatrix})，第k类的数据投影后的离散度可表示为(vec{phi}^T ilde{X}_k^T ilde{X}_kvec{phi})，(K)个类的类内离散度之和为(vec{phi}^Tsum_{k=1}^K ilde{X}_k^T ilde{X}_kvec{phi}=vec{phi}^TCvec{phi})，其中(C)的形式如下所示$$C=sum_{k=1}^{Ksum_{iin{class} {k}}(vec{x}_i-vec{mu}_k)}T(vec{x}_i-vec{mu}_k)$$
由PCA的第三步可以看出投影后数据的总体离散度为(vec{phi}^T ilde{X}^T ilde{X}vec{phi})，其中( ilde{X}=egin{bmatrix}egin{smallmatrix}vec{x_1}-{vec{mu}}\vec{x_2}-{vec{mu}}\vdots\vec{x_n}-{vec{mu}}end{smallmatrix}end{bmatrix})，则类间离散度可以表示为总体与类内离散度之差，即$$vec{phi}^T[ ilde{X}T ilde{X}-{C}]vec{phi}=vec{phi}^T[sum_{k=1}Kn_k({vec{mu}_k}-{vec{mu}})^{T({vec{mu}_k}-{vec{mu}})]vec{phi}=vec{phi}}TBvec{phi}$$
为了使类内离散度尽可能小，同时类间离散度尽可能大，需求解问题(argmax_{vec{phi}}frac{vec{phi}^TBvec{phi}}{vec{phi}^TCvec{phi}})，对(vec{phi})做变换(vec{phi}=Wvec{phi}^*)（注：对(C)进行特征值分解(C=UDU^T)，记(W=UD^{-1/2})），则上述问题转化为$$argmax_{vec{phi}^{{*}}frac{vec{phi}}{{*}T}W^TBWvec{phi}{*}}{vec{phi}^{{*}T}WTCWvec{phi}^{{*}}=argmax_{vec{phi}}{*}}frac{vec{phi}^{{*}T}WTBWvec{phi}^{{*}}{vec{phi}}{{*}T}vec{phi}^{*}}$$假设需求解m个loading vector (vec{phi}_1^*,vec{phi}_2^*,...,vec{phi}_m^*)，({m}leq{K-1})，且需满足(vec{phi}_i^{*T}vec{phi}_j^*=0, i eq{j})，上述问题可转化为$$argmax_{vec{phi}^{{*}}{vec{phi}}{{*}T}W^TBWvec{phi}{*}}, ext{ where }vec{phi}_i^{{{*}T}vec{phi}_i}{*}=1, ext{ and }vec{phi}_i^{{{*}T}vec{phi}_j}{*}=0, i eq{j}$$
此时可以参照PCA的做法，对(W^TBW)进行特征值分解(W^TBW=VLambda{V^T})，容易看出(vec{phi}^{*}_i=vec{v}_i)，(i=1,2,cdots,m)（证明过程见PCA的5-7步）。综上所述，最终求得的投影向量(vec{phi}_i=Wvec{phi}^{*}_i)，并且容易看出(vec{phi})满足(vec{phi}_i^{*T}vec{phi}_j^*=[W^{-1}vec{phi}_i]^T[W^{-1}vec{phi}_j]=vec{phi}_i^{T}Cvec{phi}_j=0, ext{ }i eq{j})
对于(vec{phi}^{*}_i)，有(W^TBWvec{phi}^{*}_i=lambda_ivec{phi}^{*}_i)，等式两边同时左乘W，有(WW^TBWvec{phi}^{*}_i=lambda_iWvec{phi}^{*}_i)，即(UD^{-1}U^TBvec{phi}_i=C^{-1}Bvec{phi}_i=lambda_ivec{phi}_i)。因此在实际求解过程中，可以直接求解(C^{-1}B)的特征值和特征向量，将特征值按从大到小排列取前m个特征值和特征向量，即为最终求得的(vec{phi}_i)
The Elements of Statistical Learning(2nd Edition) Section 4.3.3中给出了另外一种思路，即假设每个类内特征分布的协方差矩阵等于总体特征分布的协方差矩阵，则协方差矩阵的估计值即为矩阵(C)，上述这些步骤等价于通过空间变换将协方差矩阵变为单位阵（特征之间互不相关，每个特征的方差为1），再将每个数据替换为它所在类的均值，在变换后的空间上对其进行PCA降维