详解线性判别分析(LDA)

目录

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:顾名思义,也就是刻画同类样本点之间“接近”程度的矩阵,下标wwithin的首字母。

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

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_wS_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_iR

可以化简为:                                       

\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的结论:

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

如有错漏之处,敬请指正,谢谢!

你可能感兴趣的