LDA基本思想：

投影的定义

同类投影点的接近

异类样本点的远离

找到一条直线（转为最优化）

类内散度矩阵与类间散度矩阵

目标函数对欧米伽大小的无关性

拉格朗日乘子法

LDA做法总结

本文着重于思想的理解与公式的推导~

Linear Discriminant Analysis（LDA）是一种经典的线性学习方法，亦称“Fisher判别分析法”

注意：本文中的 $\vec{\omega }=\begin{pmatrix} \omega_{1}\\ \omega_{2} \end{pmatrix}$ $\vec{\mu }=\begin{pmatrix} x \\y \end{pmatrix}$

LDA基本思想：

找到一条直线（低维空间），使得将平面（高维空间）中的样本点投影到直线（低维空间）中，尽量使得同类样本点接近，异类样本点远离，判断新样本：当将新样本投影后，根据其投影后的位置判断其类别。

投影的定义

什么叫样本点投影到直线上：将点 $\vec{\mu }$ （原点指向样本点的向量）投影到直线上，也就是投影到直线的单位方向向量 $\vec{\omega }^{T}$ 上，不妨设 $\vec{\mu}$ 的起点是原点 $O$ ，然后求原点 $O$ 至投影点的距离。

由向量的点乘可知： $\vec{\omega }^{T}\cdot {\vec{\mu}$ 是投影长度,i.e.原点 $O$ 至投影点的距离

同类投影点的接近

什么叫同类投影点接近：在一维空间中，我们常常使用方差来刻画样本点偏离平均值的程度。在此处，因为已经对样本点进行投影，将每个样本点降维成了一个实数，因此就是对投影求方差，就能刻画投影点偏离样本中心点的投影的程度，也就刻画了“接近”，即投影的方差越小越接近。i.e. $Var(\vec\omega^T\cdot\vec\mu)$ 越小，同类样本点越接近。

注意到西瓜书内使用的是： $\vec\omega^{T}\cdot\Sigma \cdot\vec\omega$ 刻画接近，其本质上是相等的，下面给出公式推导：

对于 $\vec\omega^{T}\cdot\Sigma \cdot\vec\omega$ 有如下变形：

$\because \Sigma =\begin{pmatrix} c_{11}& c_{12}\\ c_{21}& c_{22} \end{pmatrix}$

$c_{ij}=Cov(X_{i},X_{j})=E[X_{i}-E(X_{i})][X_{j}-E(X_{j})],i,j=1,2$

$\Rightarrow \vec\omega^{T}\cdot\Sigma \cdot\vec\omega=(\omega_{1}, \omega_{2})\cdot\begin{pmatrix} c_{11}& c_{12}\\ c_{21}& c_{22} \end{pmatrix}\cdot\begin{pmatrix} \omega_{1}\\ \omega_{2}\end{pmatrix}$

$\Rightarrow \omega_{1}^{2}c_{11}+\omega_{1}\omega_{2}(c_{12}+c_{21})+\omega_{2}^{2}c_{22}$

$\Rightarrow \omega_{1}^{2}Var(x)+2\omega_1\omega_{2}Cov(x,y)+\omega_{2}^{2}Var(y)$

$\Rightarrow\omega_{1}^{2}E[(x-Ex)^2]+2\omega_1\omega_{2}E[(x-Ex)(y-Ey)]+\omega_{2}^{2}E[(y-Ey)^2]$

$\Rightarrow E[(\omega_{1}x-\omega_{1}Ex)^2+2\omega_1\omega_{2}(x-Ex)(y-Ey)+(\omega_{2}y-\omega_{2}Ey)^2]\quad\quad\quad\quad(1)$

对于 $Var(\omega^{T}\cdot\vec\mu)$ 有如下变形：

$Var(\omega^{T}\cdot\vec\mu)=E[(\omega^T\cdot\vec\mu-E(\omega^T\cdot\vec\mu))^2]$

$\Rightarrow E\{[\begin{pmatrix} \omega_{1}\\\omega_{2}\end{pmatrix}\cdot\(x,y)]^2+[\begin{pmatrix} \omega_{1}\\\omega_{2}\end{pmatrix}\cdot\(Ex,Ey)]^2-2[\begin{pmatrix} \omega_{1}\\\omega_{2}\end{pmatrix}\cdot\(x,y)\cdot\begin{pmatrix} \omega_{1}\\\omega_{2}\end{pmatrix}\cdot\(Ex,Ey)]\}$

$\Rightarrow E[(\omega_{1}x+\omega_{2}y)^2+(\omega_{1}Ex+\omega_{2}Ey)^2-2(\omega_{1}x+\omega_{2}y)(\omega_{1}Ex+\omega_{2}Ey)]\quad\quad\quad\quad(2)$

可以验证的是：(1)=(2)

到此，证明了 $Var(\vec\omega\cdot\vec\mu)=\vec\omega^{T}\cdot\Sigma \cdot\vec\omega$ ，即样本之间的协方差本质上就是样本点投影的方差。

异类样本点的远离

什么叫异类样本点的远离：在一维空间中，我们使用样本差的绝对值刻画距离，在此处，为了刻画一类样本点的远离，也即是求不同类别样本点之间的距离，距离越大越“远离”，但是不同类别的样本点很多，因此此处只需求异类样本中心点之间的距离就好，也就是异类样本中心点投影的差的绝对值： $\left | \omega^T\mu_{0}-\omega^T\mu_1\right |$ ，为了去除绝对值这样的不光滑的函数我们采用二次函数代替绝对值，也就是 $(\omega^T\mu_{0}-\omega^T\mu_1)^2$ 越大，越远离。

此处的 $\mu_0$ 是第0类的样本中心点， $\mu_1$ 是第1类的样本中心点。后文也将这样表述。

找到一条直线（转为最优化）

什么叫找到一条直线：根据LDA思想，也就是找到这样的直线，使得样本点投影到直线之后，同类样本点接近，异类样本点远离。其实已经化成了一个最优化问题：

类内散度矩阵与类间散度矩阵

为方便计算

定义“类内散度矩阵” $S_w$ ：顾名思义，也就是刻画同类样本点之间“接近”程度的矩阵，下标 $w$ 是 $within$ 的首字母。

定义“类间散度矩阵” $S_b$ ：顾名思义，也就是刻画异类样本点之间“远离”程度的矩阵，下标 $b$ 是 $between$ 的首字母。

$S_w=\Sigma_0+\Sigma_1$

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

目标函数对 $\omega$ 欧米伽大小的无关性

因此该优化问题变为：

$max\quad \frac{\omega^TS_b\omega}{\omega^TS_w\omega}\\\\s.t.\quad\quad\quad\quad\vec\omega^T$

该目标函数也称“广义瑞利商”，注意到 $S_w$ 和 $S_b$ 都是 $2\times 2$ 的矩阵，所以目标函数中的分子与分母都是关于 $\omega_1,\omega_2$ 的二次项

不妨设目标函数的形式为：

$\frac{a_1\omega_1^2+a_2\omega_1\omega_2+a_3\omega_2^2}{b_1\omega_1^2+b_2\omega_1\omega_2+b_3\omega_2^2}$ 其中 $a_i,b_i$ ∈ $R$

可以化简为：

$\frac{a_1+a_2\frac{\omega_2}{\omega_1}+a_3(\frac{\omega_2}{\omega_1})^2}{b_1+b_2\frac{\omega_2}{\omega_1}+b_3(\frac{\omega_2}{\omega_1})^2}$

所以该式与 $\omega$ 大小无关，只与 $\omega$ 方向有关（ $\frac{\omega_2}{\omega_1}$ 确定之后， $\omega$ 的方向也就确定了）

不妨令 $\omega^TS_w\omega=1$ ，最优化问题化简为：(为方便之后的拉格朗日乘子法，将最大目标转换为最小目标)

$min \quad -\omega^TS_b\omega\\\\s.t.\quad\quad\omega^TS_w\omega=1$

拉格朗日乘子法

使用拉格朗日乘子法：由偏导为0得到两个等式：

$\left\{\begin{matrix} \omega^TS_w\omega-1=0\\ (\lambda S_w+\lambda S_w^T-S_b-S_b^T)\omega=0 \end{matrix}\right.$

由 $S_w,S_b$ 的定义可知， $S_w=S_w^T,S_b=S_b^T$ ,即他俩是对称矩阵。

$\Rightarrow \left\{\begin{matrix} \omega^TS_w\omega-1=0\\ \lambda S_w\omega=S_b\omega \end{matrix}\right.\quad\quad\quad\quad(3)$

上式子中 $\lambda$ 为拉格朗日乘子

注意到 $S_b\omega=(\mu_0-\mu_1)(\mu_0-\mu_1)^T\omega$

不妨设 $\mu_0-\mu_1=\begin{pmatrix} c\\d \end{pmatrix}$

$\Rightarrow S_b\omega=\begin{pmatrix} c\\ d\end{pmatrix}\cdot\begin{pmatrix} c &d \end{pmatrix}\cdot\begin{pmatrix} \omega_1\\\omega_2 \end{pmatrix}= \begin{pmatrix} (c\omega_1+d\omega_2)c\\ (c\omega_1+d\omega_2)d \end{pmatrix}=(c\omega_1+d\omega_2)\begin{pmatrix} c\\ d \end{pmatrix}$

所以 $S_b\omega$ 与 $\mu_0-\mu_1$ 同向，而上面已经证明了原始目标函数与 $\omega$ 的大小无关，也就是 $\omega$

大小任取，从而 $S_b\omega$ 长度任取，不妨就令：

$S_b\omega= \lambda(\mu_0-\mu_1)\quad\quad\quad\quad(4)$

现将(3)(4)联立解得：

$\omega=S_w^{-1}(\mu_0-\mu_1)$

到此整个LDA就做完了。

LDA做法总结

最后再总结一下LDA的结论：

计算类内散度矩阵的逆矩阵 $S_w^{-1}$
分别计算两类的样本中心点 $\mu_0,\mu_1$
计算最终找到的这条直线 $\omega=S_w^{-1}(\mu_0-\mu_1)$
将新样本点投影到求得的 $\omega$ 再判断其类别

如有错漏之处，敬请指正，谢谢！

张士玉小黑屋

当前位置：首页 » 《随便一记》 » 正文

详解线性判别分析(LDA)_yellowetao的博客

24 人参与 2022年03月10日 15:07 分类 : 《随便一记》评论

LDA基本思想：

投影的定义

同类投影点的接近

异类样本点的远离

找到一条直线（转为最优化）

类内散度矩阵与类间散度矩阵

目标函数对 $\omega$ 欧米伽大小的无关性

拉格朗日乘子法

LDA做法总结

评论（0）

赞助本站

最新文章

张士玉小黑屋

当前位置：首页 » 《随便一记》 » 正文

详解线性判别分析(LDA)_yellowetao的博客

24 人参与 2022年03月10日 15:07 分类 : 《随便一记》 评论

LDA基本思想：

投影的定义

同类投影点的接近

异类样本点的远离

找到一条直线（转为最优化）

类内散度矩阵与类间散度矩阵

目标函数对欧米伽大小的无关性

拉格朗日乘子法

LDA做法总结

评论（0） 赞助本站

最新文章

24 人参与 2022年03月10日 15:07 分类 : 《随便一记》评论

目标函数对 $\omega$ 欧米伽大小的无关性

评论（0）

赞助本站