Linear Discriminant Analysis.

线性判别分析(Linear Discriminant Analysis,LDA)，又称Fisher判别分析，是一种线性分类方法。LDA的思想是，给定训练样本集，将所有样本投影到空间中的一个超平面上，使得相同类别的样本的投影点尽可能接近，不同类别的样本的投影点尽可能远离。在对一个新的样本进行分类时，先将其投影到该超平面上，再根据投影点的位置(以及预先设置的阈值)确定该样本的类别。LDA也可以看作是一种监督的线性降维方法。

1. 二分类线性判别分析

若记$N$个样本点$\{x_1,x_2,...,x_N\}$，属于类别$0$和类别$1$的样本总数分别为$N_0$和$N_1$。在样本空间中寻找一个向量$w$，将样本$x$投影到向量$w$上，得到投影$w^Tx$(注意到投影是标量)。

对投影的解释如下。若向量$x$与向量$w$之间的夹角为$\theta$，则将向量$x$直接投影到向量$w$上的长度为$|x|\cos \theta$。直接计算两向量内积$w^Tx= |w| |x| \cos \theta$；当$|w|=1$时两者等价，因此用内积表示投影。

注意到向量$w$可以被看作是分离超平面的法向量，通过选择使得样本投影的类间差距大,类内方差小的向量$w$，可以找到将$w$作为法向量的分离超平面$f(x)=w^Tx$，从而对样本点进行分类。

(1) 类间差距大(松耦合)

不同类别样本点之间的类间差距可以用均值(代表样本中心)投影之间的差距衡量。若记类别$c$的样本均值为$\mu_c = \frac{1}{N_c} \sum_{x \in X_c}^{} x$，则均值投影为$\frac{1}{N_c} \sum_{x \in X_c}^{} w^Tx = w^T\mu_c$。对于二分类问题，类别$0$和类别$1$的均值投影差异表示为$\|w^T\mu_0-w^T\mu_1\|_2^2$。

(2) 类内方差小(高内聚)

同一类别样本点之间的类内方差可以用投影后的协方差矩阵衡量。若记类别$c$的样本协方差为$\Sigma_c = \frac{1}{N_c} \sum_{x \in X_c}^{} (x-\mu_c)(x-\mu_c)^T$，则类别$c$投影后的协方差矩阵表示为：

\[\frac{1}{N_c} \sum_{x \in X_c}^{} (w^Tx-w^T\mu_c)(w^Tx-w^T\mu_c)^T = \frac{1}{N_c} \sum_{x \in X_c}^{} w^T(x-\mu_c)(x-\mu_c)^T w = w^T\Sigma_cw\]

对于二分类问题，类别$0$和类别$1$的类内方差之和表示为$w^T\Sigma_0w+w^T\Sigma_1w$。

(3) LDA的目标函数

相同类别的样本的投影点尽可能接近，可以让同一类别样本投影点的协方差$w^T\Sigma_0w+w^T\Sigma_1w$尽可能小；
不同类别的样本的投影点尽可能远离，可以使不同类别的中心投影之间的距离$\|w^T\mu_0-w^T\mu_1\|_2^2$尽可能大。

二分类的线性判别分析最大化以下目标函数：

\[J = \frac{||w^T\mu_0-w^T\mu_1||_2^2}{w^T\Sigma_0w+w^T\Sigma_1w} = \frac{w^T(\mu_0-\mu_1)(\mu_0-\mu_1)^Tw}{w^T(\Sigma_0+\Sigma_1)w}\]

定义：

类间散度矩阵(between-class scatter matrix)

\[S_b = (\mu_0-\mu_1)(\mu_0-\mu_1)^T\]

类内散度矩阵(within-class scatter matrix)

\[S_w = \Sigma_0+\Sigma_1\]

则目标函数可写作：

\[J = \frac{w^TS_bw}{w^TS_ww}\]

上述问题等价于求广义瑞利商的极值。由于对向量$w$等比例缩放不影响广义瑞利商的值，不失一般性，令$w^TS_ww=1$，此时对广义瑞利商求极值，就是在约束$w^TS_ww=1$下，求$w^TS_bw$的极值。采用拉格朗日乘子法，定义拉格朗日函数：

\[L(w,\lambda)= w^TS_bw-\lambda(w^TS_ww-1)\]

上式对$w$求梯度，并令梯度为$0$，可得：

\[S_bw=\lambda S_ww\]

注意到$(\mu_0-\mu_1)^Tw$是标量，因此$S_bw = (\mu_0-\mu_1)(\mu_0-\mu_1)^Tw$与$\mu_0-\mu_1$同方向，不妨令$S_bw = \lambda(\mu_0-\mu_1)$，代入上式得：

\[w = S_w^{-1}(\mu_0-\mu_1)\]

若不同类别之间的数据无关(线性可分)，即$S_w$是各向同性的对角矩阵$S_w∝I$，则有$w∝(\mu_0-\mu_1)$。

求得$w$后，即求得分类超平面的法向量，从而可得最终分类超平面：

\[f(x)=w^Tx=S_w^{-1}(\mu_0-\mu_1)x\]

2. 多分类线性判别分析

可以将LDA从二分类推广到多分类的情形。若记$N$个样本点$\{x_1,x_2,...,x_N\}$，共有$C$种类别，所有样本点的均值为$\mu = \frac{1}{N} \sum_{i=1}^{N} x_i$，定义全局散度矩阵 $S_t$：

\[S_t = \sum_{i=1}^{N}(x_i-\mu)(x_i-\mu)^T\]

类内散度矩阵 $S_w$定义为每个类别的散度矩阵之和：

\[S_w = \sum_{c=1}^{C} S_{w_c} = \sum_{c=1}^{C} \sum_{x \in X_c}^{} (x-\mu_c)(x-\mu_c)^T\]

则类间散度矩阵 $S_b$可以通过$S_t$和$S_w$计算如下：

\[\begin{aligned} S_b &= S_t - S_w = \sum_{i=1}^{N}(x_i-\mu)(x_i-\mu)^T - \sum_{c=1}^{C} \sum_{x \in X_c}^{} (x-\mu_c)(x-\mu_c)^T \\ &= \sum_{c=1}^{C} \sum_{x \in X_c}^{}(x-\mu)(x-\mu)^T - \sum_{c=1}^{C} \sum_{x \in X_c}^{} (x-\mu_c)(x-\mu_c)^T \\ &= \sum_{c=1}^{C} \sum_{x \in X_c}^{} (xx^T-x\mu^T-\mu x^T + \mu\mu^T - xx^T+x\mu_c^T+\mu_c x^T - \mu_c\mu_c^T) \\ &= \sum_{c=1}^{C} \sum_{x \in X_c}^{} (-x\mu^T-\mu x^T + \mu\mu^T +x\mu_c^T+\mu_c x^T - \mu_c\mu_c^T) \\ &= \sum_{c=1}^{C} (-\sum_{x \in X_c}^{}x\mu^T-\sum_{x \in X_c}^{}\mu x^T + \sum_{x \in X_c}^{}\mu\mu^T +\sum_{x \in X_c}^{}x\mu_c^T+\sum_{x \in X_c}^{}\mu_c x^T - \sum_{x \in X_c}^{}\mu_c\mu_c^T) \\ &= \sum_{c=1}^{C} (-N_c\mu_c\mu^T-N_c\mu\mu_c^T + N_c \mu\mu^T +N_c\mu_c\mu_c^T+N_c\mu_c\mu_c^T - N_c\mu_c\mu_c^T) \\ &= \sum_{c=1}^{C} (-N_c\mu_c\mu^T-N_c\mu\mu_c^T + N_c \mu\mu^T +N_c\mu_c\mu_c^T) \\ &= \sum_{c=1}^{C} N_c(\mu_c-\mu)(\mu_c-\mu)^T \end{aligned}\]

上式表示类间散度矩阵可以表示成所有类别样本的中心与总体中心之间的差距之和。多分类LDA的优化目标函数表示为：

\[\mathop{\max}_w \frac{tr(W^TS_bW)}{tr(W^TS_wW)}\]

上式也是广义瑞利商的形式，可以将问题转化为广义特征值问题：

\[S_w^{-1}S_bW = \lambda W\]

3. 核线性判别分析

将核方法引入线性判别分析，即可得到核线性判别分析(Kernelized Linear Discriminant Analysis)，从而将线性模型扩展成非线性模型。

引入映射$\phi:\mathcal{X}→\mathcal{F}$将样本空间$\mathcal{X}$变换到高维的特征空间$\mathcal{F}$，在$\mathcal{F}$中构造线性判别分析，以求得：

\[f(x)=w^T \phi(x)\]

第$c$类样本在特征空间$\mathcal{F}$中的均值计算为：

\[\mu_c^{\phi} = \frac{1}{N_c} \sum_{x \in X_c}^{} \phi(x)\]

引入核函数$K(x_i,x_j)=\phi(x_i)^T\phi(x_j)$隐式地表示特征映射$\phi$及其内积，则由表示定理，函数$f(x)$表示为：

\[f(x)=w^T\phi(x)=\sum_{i=1}^{N}\alpha_iK(x,x_i), \quad w = \sum_{i=1}^{N}\alpha_i\phi(x_i)\]

若记训练样本在特征空间$\mathcal{F}$中的类间散度矩阵 $S_b^{\phi}$和类内散度矩阵 $S_w^{\phi}$，两个散度矩阵计算为：

\[\begin{aligned} S_b^{\phi} &= (\mu_0^{\phi}-\mu_1^{\phi})(\mu_0^{\phi}-\mu_1^{\phi})^T \\ S_w^{\phi} &= \Sigma_0^{\phi}+\Sigma_1^{\phi} = \sum_{c=0,1}^{} \sum_{x \in X_c}^{}(\phi(x)-\mu_c^{\phi})(\phi(x)-\mu_c^{\phi})^T \end{aligned}\]

则核线性判别分析的目标函数可表示为：

\[J = \frac{w^TS_b^{\phi}w}{w^TS_w^{\phi}w}\]

使用线性判别分析的方法求解上述问题即可得到$\alpha$，进而求得函数$f(x)$。