线性判别分析（Linear Discriminant Analysis，LDA）

Linear Discriminant Analysis（LDA）

输入：

			 原始数据$D=((x_1,y_1),(x_2,y_2),...,(x_m,y_m)$ 、​			类别标签$Y=[y_1,y_2,...,y_n]$、​			降维到的维度d

输出：

投影矩阵W、投影后的样本$Z$、

算法步骤：

• 1.计算类内散度矩阵$S_w$
• 2.计算类间散度矩阵$S_b$
• 3.计算矩阵$S_w^{-1}{S}_b$
• 4.计算$S_w^{-1}{S}_b$的最大的d个特征值和对应的d个特征向量$(w_1,w_2,...,w_d)$得到投影矩阵W
• 5.对样本集中的每一个样本特征$x_i$,转换为新的样本$z_i=W^T{x}_i$
• 6.得到输出样本集$D^{\prime }=((z_1,y_1),(z_2,y_2),...,(z_m,y_m))$

二类LDA

对于两个类别的中心点${\mu }_0,{\mu }_1$,在直线$w$的投影为$w^T{\mu }_0$和$w^T{\mu }_1$。

• 让不同类别的数据的类别中心之间的距离尽可能的大，也就是我们要最大化$||w^T{\mu }_0-w^T{\mu }_1|{|}_2^2$
• 希望同一种类别数据的投影点尽可能的接近${\Sigma }_{x\in w_i}(w^{T}x-w^T{\mu }_i{)}^2$尽可能小，也就是要同类样本投影点的协方差$w^T{\Sigma }_{0}w和w^T{\Sigma }_{1}w$尽可能的小，即最小化$w^T{\Sigma }_{0}w+w^T{\Sigma }_{1}w$。

优化的目标函数：
$$J(w)=\frac{||w^T{\mu }_0-w^T{\mu }_1|{|}_2^2}{w^T{\Sigma }_{0}w+w^T{\Sigma }_{1}w}=\frac{w^T({\mu }_0-{\mu }_1)({\mu }_0-{\mu }_1{)}^{T}w}{w^T({\Sigma }_0+{\Sigma }_1)w}$$
定义类内散度矩阵：
$$\begin{gathered} {S}_w={\Sigma }_0+{\Sigma }_1 \\ =\sum _{x\in X_0}(x-{\mu }_0)(x-{\mu }_0{)}^T+\sum _{x\in X_1}(x-{\mu }_1)(x-{\mu }_1{)}^T \end{gathered}$$
定义类间散度矩阵：
$$S_b=({\mu }_0-{\mu }_1)({\mu }_0-{\mu }_1{)}^T$$
对此目标函数的优化：
$$J(w)=\frac{||w^T{\mu }_0-w^T{\mu }_1|{|}_2^2}{w^T{\Sigma }_{0}w+w^T{\Sigma }_{1}w}=\frac{w^T({\mu }_0-{\mu }_1)({\mu }_0-{\mu }_1{)}^{T}w}{w^T({\Sigma }_0+{\Sigma }_1)w}$$
方法一：使用拉格朗日乘子法

可以将分母进行归一化：如果分子分母都可以任意取值那将会有无穷解，故将分母限制长度为1。

此时：
$$\{\begin{array}{l}J(w)=\frac{w^T{S}_{b}w}{w^T{S}_{w}w}\\ s.t.w^T{S}_{w}w=1\end{array}$$
使用拉格朗日乘子法：
$$\begin{gathered} c(w)=w^T{S}_{b}w-\lambda (w^T{S}_{w}w-1) \\ \to \frac{dc(w)}{dw}=2S_{b}w-2\lambda S_{w}w=0 \\ \to S_{b}w=\lambda S_{w}w \\ \to S_w^{-1}{S}_{b}w=\lambda w \end{gathered}$$
由上式得：求解的w就是矩阵$S_w^{-1}{S}_b$的特征向量

方法二：使用瑞利商的结论

瑞利商是指这样的函数

​ $$R(A,x)=\frac{x^{H}Ax}{x^{H}x}$$

它有性质：

它的最大值等于矩阵A最大的特征值，而最小值等于矩阵A的最小的特征值，也就是满足${\lambda }_{min}\le \frac{x^{H}Ax}{x^{H}x}\le {\lambda }_{max}$

广义瑞利商。广义瑞利商是指这样的函数$R(A,B,x)$:

​ $R(A,x)=\frac{x^{H}Ax}{x^{H}Bx}$

我们令$x=B-1/2x\prime$,则分母转化为： $$x^{H}Bx=x\prime H(B^{\frac{-1}{2}}{)}^{H}B{B}^{\frac{-1}{2}}x\prime =x{\prime }^H{B}^{\frac{-1}{2}}B{B}^{\frac{-1}{2}}x\prime =x{\prime }^{H}x\prime$$

而分子转化为：

​ $$x^{H}Ax=x{\prime }^H{B}^{-1/2}A{B}^{-1/2}x\prime$$

此时我们的$$R(A,B,x)$$转化为$$R(A,B,x\prime )$$:

​ $$R(A,B,x\prime )=\frac{x{\prime }^H{B}^{-1/2}A{B}^{-1/2}x\prime }{x{\prime }^{H}x\prime }$$

利用前面的瑞利商的性质，我们可以很快的知道，$R(A,B,x\prime )$的最大值为矩阵$B^{-1/2}A{B}^{-1/2}$的最大特征值，或者说矩阵$B^{-1}A$的最大特征值，而最小值为矩阵$B^{-1}A$的最小特征值。这里用到了对矩阵进行标准化。

方法三：直接对w进行求偏导
$$\begin{gathered} \frac{\partial J(w)}{\partial w}=\frac{\partial }{\partial w}(\frac{w^T{S}_{b}w}{w^T{S}_{w}w})=w^T{S}_{w}w\frac{\partial (w^T{S}_{b}w)}{\partial w}-w^T{S}_{b}w\frac{\partial (w^T{S}_{w}w)}{\partial w}=0 \\ \to (w^T{S}_{w}w)2S_{b}w-(w^T{S}_{b}w)2S_{w}w=0 \\ 除以w^T{S}_{w}w: \\ \to (\frac{w^T{S}_{w}w}{w^T{S}_{w}w})S_{b}w-(\frac{w^T{S}_{b}w}{w^T{S}_{w}w})S_{w}w=0 \\ \to S_{b}w-J{S}_{w}w=0 \\ \to S_w^{-1}{S}_{b}w-Jw=0 \\ \to Jw=S_w^{-1}{S}_{b}w \\ \to Jw=S_w^{-1}({\mu }_0-{\mu }_1)({\mu }_0-{\mu }_1{)}^{T}w \\ \to Jw=S_w^{-1}({\mu }_0-{\mu }_1)\underset{\text{c}\in R}{\underbrace{(({\mu }_0-{\mu }_1{)}^{T}w))}} \\ \to Jw=c{S}_w^{-1}({\mu }_0-{\mu }_1) \\ \to w=\frac{c}{J}{S}_w^{-1}({\mu }_0-{\mu }_1) \end{gathered}$$
Fisher’s linear discirminant

多类LDA

优化的目标函数：
$$J(w)=\frac{W^T{S}_{b}W}{W^T{S}_{w}W}$$
其中：
$$\begin{gathered} S_b=\sum _{j=1}^k{N}_j({\mu }_j-\mu )({\mu }_j-\mu {)}^T,\mu 为所有样本的均值向量、N_j为第j类样本的个数 \\ {S}_w=\sum _{j=1}^k{S}_{wj}=\sum _{j=1}^k\sum _{x\in X_j}(x-{\mu }_j)(x-{\mu }_j{)}^T \end{gathered}$$
有一个问题，就是$W^T{S}_{b}W$和$W^T{S}_{w}W$都是矩阵，不是标量，无法作为一个标量函数来优化！

常见的一个LDA多累优化目标函数定义为：
$$\begin{gathered} \underset{\text{w}}{\underbrace{argmax}}J(W)=\frac{\prod diag(W^T{S}_{b}W)}{\prod diag(W^T{S}_{w}W} \\ \to J(W)=\frac{{\prod }_{i=1}^d(w_i^T{S}_b{w}_i)}{{\prod }_{i=1}^d(w_i^T{S}_w{w}_i)}=\prod _{i=1}^d\frac{w_i^T{S}_b{w}_i}{w_i^T{S}_w{w}_i} \end{gathered}$$
广义瑞利商

最大值是矩阵$S_w^{-1}{S}_b$的最大特征值,最大的d个值的乘积就是矩阵$S_w^{-1}{S}_b$的最大的d个特征值的乘积,此时对应的矩阵W为这最大的d个特征值对应的特征向量张成的矩阵。