LDA降维原理

1. 什么是LDA

LDA和PCA一样，是一种降维技术。不同的是，PCA可以用于无监督学习，通过最大化特征方差构造新特征。而LDA则是用于监督学习，要求数据有标签，通过最大化类间方差和最小化类内方差构造新特征。

2. 怎么求解LDA

LDA降维目标是构造一个新特征，使得每个类别在新特征下的方差最大，同时最小化类内方差。假设数据特征是$x$，标签为$y$，总共有$K$个类别，新特征的线性变换参数为$w$，则可以使用下面的式子计算在新特征下的类内方差：

$$inner_k=\sum_{y_i=k}(w^Tx_i-w^T\mu_k)^2=\sum_{y_i=k}w^T(x_i-\mu_k)^2w=w^T(\sum_{y_i=k}(x_i-\mu_k)(x_i-\mu_k)^T)w$$

其中，$\mu_k$表示类别$k$的样本特征的均值。每个类别都可以计算出类内方差，则总的类内方差等于：

$$inner=w^T(\sum_{k=1}^K\sum_{y_i=k}(x_i-\mu_k)(x_i-\mu_k)^T)w=w^TS_ww$$

同样地，定义类间方差：

$$var=\sum_{k=0}^Kw^T(\mu_k-\mu)(\mu_k-\mu)^Tw=w^T(\sum_{k=0}^K(\mu_k-\mu)(\mu_k-\mu)^T)w=w^TS_bw$$

其中，$\mu$是所有样本特征的均值。LDA希望类间方差$var$尽量大的同时类内方差$inner$尽量小，所以可以认为要求：

$$w=arg\max_{w}\frac{w^TS_bw}{w^TS_ww}$$

注意到，当存在一个解$w$时，$w$的任意倍数也可以是解，所以加上限制：

$$w^TS_ww=1$$

现在可以使用拉格朗日乘子法求解，对$w$求导得到：

$$S_w^{-1}S_bw=\lambda w$$

其中$\lambda$是拉格朗日乘子法在约束项的系数。所以$w$的最优解是$S_w^{-1}S_b$特征值最大对应的特征向量。和PCA一样，要选出$m$个新特征，就选择特征值前$m$大的特征向量。需要注意的是，因为$S_w$一般是不可逆的，所以需要修正为$S_w+\beta E$，$\beta$是一个很小的值。还有因为$S_b$的秩小于等于类别数$K$，所以LDA的新特征数不能大于$K$。

现在总结一下LDA的流程：
(1) 计算出类内方差矩阵$S_w$和类间方差矩阵$S_b$
(2) 求$S_w^{-1}S_b$的特征向量
(3) 选择特征值前$m$大的特征向量组成降维矩阵
(4) 使用原矩阵左乘降维矩阵，得到降维结果