线性判别分析LDA

线性判别分析 (Linear Discriminant Analysis, LDA) 是一种常用的有监督降维方法

LDA最早是由Fisher提出的用于解决二分类问题的方法，因此也称为FDA，下面我们从二分类开始讲解LDA

LDA二分类

对于二分类问题，假设给定样本集$D\in R^{2\times m}$，记$D_1,D_2$分别是属于两个类别的样本集合

LDA的目标是将样本投影到一个直线上，使同类样本间尽可能近，异类样本间尽可能远

为了量化评价这个目标，可以定义Fisher判别准则

$$J(w)=\frac{\|\widetilde{\mu_1}-\widetilde{\mu_2}\|^2_2}{S_1+S_2}$$

其中$\widetilde{\mu_1},\widetilde{\mu_2}$分别为两类样本投影后的均值向量，$S_1，S_2$分别为两类样本投影后各自的方差
对于二维向量投影到直线上的情况，$\widetilde{\mu_1},\widetilde{\mu_2}$为实数

显然$J(w)$越大，则投影点的类别可分性越强

记$\mu_1,\mu_2$分别为两类样本投影前的均值向量，投影直线为$w$，则有

$$\begin{aligned} \|\widetilde{\mu_1}-\widetilde{\mu_2}\|^2_2&=\|w^T\mu_1-w^T\mu_2\|^2_2\\ &=w^T(\mu_1-\mu_2)(\mu_1-\mu_2)^Tw \\ &=w^TS_bw \end{aligned}$$

其中$S_b=(\mu_1-\mu_2)(\mu_1-\mu_2)^T$称为类间散度矩阵

$$\begin{aligned} S_i &= \sum_{x\in D_i} (w^Tx-w^T\mu_i)\\ &= \sum_{x\in D_i} w^T(x-\mu_i)(x-\mu_i)^Tw\\ &=\sum_{x\in D_i} w^T\Sigma_iw \end{aligned}$$

其中$\Sigma_i$为第$i$类样本的协方差矩阵，称$S_w=\Sigma_1+\Sigma_2$为类内散度矩阵，则$S_1+S_2=w^TS_ww$

因此Fishe判别准则变为

$$J(w)=\frac{w^TS_bw}{w^TS_ww}$$

令约束为$w^TSww=1$，则可用拉格朗日乘数法求解 $\mathop{\text{argmin}}\limits{w} -w^TS_bw$，解得

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

因此可以对$S_w^{-1}S_b$进行特征值分解，得到的特征向量就是$w$

将样本点按$w^Tx$投影到直线上后，所有样本点就是一个实数，因此可以直接确定一个阈值进行二分类

多维推广

在有$c$个类别，样本为$d$维的情况下，我们可以将LDA推广为降维算法

记$\mu$为所有样本的均值向量，重新定义类间散度矩阵和类内散度矩阵为

$$S_b=\sum_{i=1}^c |D_i|(\mu_i-\mu)(\mu_i-\mu)^T\\ S_w=\sum_{i=1}^c S_i =\sum_{i=1}^c\sum_{x\in D_i}(x-\mu_i)(x-\mu_i)^T$$

则优化目标变为

$$\mathop{\text{argmax}}\limits_{W} \frac{tr(W^TS_bW)}{tr(W^TS_wW)}$$

同样用拉格朗日乘数法可解得

$$S_w^{-1}S_bW=\lambda W$$

该结果于之前是相同的，进行特征值分解并保留最大的$d’$个特征值对应的特征向量组成变换矩阵$W$即可