基本概念#

线性判别分析既是一种分类算法，也是一种降维方法，和PCA一样，LDA也是通过投影的方式达到去除数据之间冗余的一种算法。其基本想法是找到一个向量 $\boldsymbol{w}$ ，使所有样本投影到 $\boldsymbol{w}$ 上之后类别间距离最大。

正交投影#

已知：

计算 $\boldsymbol{x}$ 在 $\boldsymbol{w}$ 上的投影 $\boldsymbol{p}$ :

假设 $\boldsymbol{w}$ 是一个单位向量， 即 $\boldsymbol{w}^\mathrm{T}\boldsymbol{w} = 1$ , 对于一个数据集 $X=\{x_1, x_2,\cdots ,x_m\}$，其中 $\boldsymbol{x}_i$ 是 $d$ 维列向量，其在 $\boldsymbol{w}$ 上的投影 $\hat{\boldsymbol{x}_i}$ 可以表示为

其中 $a_i$ 是一个常数, 叫做 $\boldsymbol{x}_i$ 在 $\boldsymbol{w}$ 上的坐标或者偏移。

这一系列的值 $\{a_1,a_2,\cdots,a_m\}$ 表示了一个映射：$\boldsymbol{R}^d \rightarrow \boldsymbol{R}$ ，即通过投影，我们将 $d$ 维向量降维到了1维

数据集的假设#

为了简化问题和可视化结果，我们假设数据集中只有2个目标类和2个特征，可做出如下假设：

其中 $D_i$ 是 所有类别为 $c_i$ 的样本的集合。

投影数据的均值#

所有数据 $\boldsymbol{x}_i$ 投影到 $\boldsymbol{w}$ 上之后，计算 $D_i$ 中投影数据的均值：

其中 $\boldsymbol{\mu}_i$ 是 $D_i$ 中所有输入数据的均值向量

两个重要想法#

为了在投影空间最大化类间距离，我们可以想到需要最大化投影均值之差 $|m_1 - m_2|$，但仅凭这个条件还不足以确保在投影空间中找到最好分割，我们需要考虑投影数据的类内方差，过大的类内方差会导致不同类的数据之间产生重叠，所以我们需要同时最小化类内方差。

但是 LDA 没有直接使用方差，而是使用总平方偏差，即没取平均的方差：

Fisher’s LDA#

Fisher提出了一个思想：最⼤化⼀个函数，这个函数能够让类均值的投影分开得较大，同时让每个类别内部的方差较小，从而最小化了类别的重叠。这个函数被叫做 Fisher’s LDA：

重写上述公式：

对目标优化函数求导：

可知使 $J(\boldsymbol{w})$ 取最大值的条件是：

其中 $\lambda = J(\boldsymbol{w})$ ，是一个常量

如果 $S$ 是一个非奇异矩阵，那么上式两边同时左乘 $S_W^{-1}$ 可得：

最终，LDA问题其实就是求 $\boldsymbol{S}^{-1}_W\boldsymbol{S}_B$ 对应最大特征值，而我们前面要求的投影方向就是最大特征值对应的特征向量，我们将LDA问题化成了矩阵的特征值和特征向量的问题了。

多分类LDA#

上述推导针对的是二分类问题，对于多分类问题， $\boldsymbol{S}_W$ 的计算方式不变，而 $\boldsymbol{S}_B$ 矩阵需要采用如下的公式计算：

其中 $C$ 表示类别数；$n_i$ 表示第i类中样本个数，$\boldsymbol{\mu}_i$表示第i类样本的均值；$\boldsymbol{\mu}$ 表示整个样本的均值。