线性判别分析LDA

LDA(Linear Discriminant Analysis)

是一种监督学习的降维技术，概括来说就是“投影后类内方差最小，类间方差最大”
也可以用来分类，不过因为计算复杂，应用较少。

基础概念

Hermitan矩阵

满足共轭转置矩阵和自己相等的矩阵，即$A^H=A$。如果我们的矩阵A是实矩阵，则满足$A^T=A$的矩阵即为Hermitan矩阵。

瑞利商（Rayleigh quotient）

$$R(A,x)=\frac{x^HAx}{x^Hx}$$

瑞利商$R(A,x)$有一个非常重要的性质，即他的最大值等于矩阵A最大的特征值，而最小值等于矩阵A的最小特征值，也就是满足：

$$\lambda_{min}\le\frac{x^HAx}{x^Hx}\le\lambda_{max}$$

当向量x是标准正交基时，即满足$x^Hx=1$时，瑞利商退化为：$R(A,x)=x^HAx$

广义瑞利商（generalized Rayleigh quotient）

$$R(A,B,x)=\frac{x^HAx}{x^HBx}$$

其中x为非零向量，而A,B为n*n的Hermitan矩阵，B为正定矩阵，令$x=B^{-\frac{1}{2}}x’$，可以将其转化为瑞利商

$$R(A,B,x')=\frac{x'^HB^{-\frac{1}{2}}AB^{-\frac{1}{2}}x'}{x'^HB^{-\frac{1}{2}}BB^{-\frac{1}{2}}x'}=\frac{x'^HB^{-\frac{1}{2}}AB^{-\frac{1}{2}}x'}{x'^Hx'}$$

则$R(A,B,x)$的最大最小值为矩阵$B^{-\frac{1}{2}}AB^{-\frac{1}{2}}\ 或者\ B^{-1}A$的最大最小特征值

二类LDA原理

假设

1. 数据集$D={(x_1,y_1),(x_1,y_1),…,(x_m,y_m)}$，其中任意样本$x_i$为n维向量，$y_i\in {0,1}$；
2. 定义$N_j(j=0,1)$为第j类样本的个数；
3. $X_j(j=0,1)$为第j类样本的集合；
4. $\mu_j(j=0,1)$为第j类样本的均值向量；
5. $\Sigma_j(j=0,1)$为第j类样本的协方差矩阵（严格说是缺少分母部分的协方差矩阵）。

$\mu_j$的表达式为：

$$\mu_j=\frac{1}{N_j} \sum_{x\in X_j}x \quad (j=0,1)$$

$\Sigma_j$的表达式为：

$$\Sigma_j=\sum_{x\in X_j}(x-\mu_j)(x-\mu_j)^T \quad (j=0,1)$$

由于是两类数据，因此只需要将数据投影到一条直线上即可。假设投影直线是向量$\omega$,则：

1. 对任意一个样本$x_i$，它在直线$\omega$上的投影为$\omega^Tx_i$；
2. 两个类别的中心点投影为$\omega^T\mu_0和\omega^T\mu_1$；
3. 同类样本透射电的协方差为$\omega^T\Sigma_0\omega和\omega^T\Sigma_1\omega$。

根据LDA思想，我们优化的目标即：

$$\underbrace{arg\ max}\ J(\omega)=\frac{\Vert \omega^T\mu_0-\omega^T\mu_1 \Vert^2}{\omega^T\Sigma_0\omega+\omega^T\Sigma_1\omega}=\frac{\omega^T(\mu_0-\mu_1)(\mu_0-\mu_1)^T\omega}{\omega^T(\Sigma_0+\Sigma_1)\omega}$$

此时，我们一般定义类内散度矩阵$S_\omega$为

$$S_\omega=\Sigma_0+\Sigma_1=\sum_{x\inX_0}(x-\mu_0)(x-\mu_0)^T+\sum_{x\inX_1}(x-\mu_1)(x-\mu_1)^T$$

定义类间散度矩阵$S_b$为：

$$S_b=(\mu_0-\mu_1)(\mu_0-\mu_1)^T$$

这样我们的优化目标重写为：

$$\underbrace{arg\ max}\ J(\omega)=\frac{\omega^TS_b\omega}{\omega^TS_\omega\omega}$$

上式符合广义瑞利商的结构，符合广义瑞利商的性质，于是$J(\omega)$的最大值就是$S_\omega^{-1}S_b$的最大特征值，$\omega$就是其对应的最大特征向量！

注意到对于二分类的时候，$Sb\omega$的方向恒为$\mu_0-\mu_1$，不放零$S_b\omega=\lambda(\mu_0-\mu_1)$，将其代入$(S\omega^{-1}Sb)\omega=\lambda\omega$,可以得到$\omega=S\omega^{-1}(\mu_0-\mu_1)$，也就是说我们只要求出原始二类样本的均值和方差就可以确定最佳的投影方向$\omega$了

多类LDA原理

（未完待续）。。。