经典机器学习系列之【线性判别分析LDA】

我的微信公众号名称:深度学习与先进智能决策
微信公众号ID:MultiAgent1024
公众号介绍:主要研究强化学习、计算机视觉、深度学习、机器学习等相关内容,分享学习过程中的学习笔记和心得!期待您的关注,欢迎一起学习交流进步!

  线性判别分析,英文名称Linear Discriminant Analysis(LDA)是一种经典的线性学习方法。本文针对二分类问题,从直观理解,对其数学建模,之后模型求解,再拓展到多分类问题。

大体思想

  给定训练样例集,设法将样例投影到一条直线上,使得同类样例的投影点尽可能接近异类样例的投影点尽可能远离;在对新样本进行分类时,将其投影到同样的这条直线上,再根据投影点的位置来确定新样本的类别。

LDA二维示意图

数学原理

  道理是这么个道理,我们现在需要在数学上对其进行分析。我们接下来先建立求解上述问题的数学模型,之后再求解。

数学模型建立

  那我们怎么从数学上去实现上述的思想呢?这里我们以二分类为例,对其展开叙述:

  给定数据集D=\{(x_{i},y_{i})\}_{i=1}^{m}y_{i} \in \{0,1\},令X_{i}\mu_{i}\sum_{i}分别表示第i \in \{0,1\}类示例的集合、均值向量、协方差矩阵。

  如果将样本投影到直线w上,那么样本所对应的均值和方差也将做一个线性变换,也即是投影之后的均值和方差。依据投影的数学关系,我们可以知道,原始样本的均值w上的投影为w^{T}\mu_{i} ;原始样本的协方差w上的投影为w^{T}\sum_{i}w;由于直线在一维空间上,所以w^{T}\mu_{0}w^{T}\mu_{1}w^{T}\sum_{0}ww^{T}\sum_{1}w均为实数。

  1. 同类样本的投影点尽可能接近这句话在数学上就可以表示为,让同类样本的协方差尽可能地小。即w^{T}\sum_{0}w + w^{T}\sum_{1}w尽可能地小;
  2. 异类样本投影点尽可能地远离,所表示的意思就是,让两类样本的均值之间的距离尽可能地大。即||w^{T}\mu_{0}-w^{T}\mu_{1}||_{2}^{2}尽可能大。

  综合以上两点,组合一个最大化的目标函数J

J=\frac{||w^{T}\mu_{0}-w^{T}\mu_{1}||_{2}^{2}}{w^{T}\sum_{0}w+w^{T}\sum_{1}w} \\
=\frac{w^{T}(\mu_{0}-\mu_{1})(\mu_{0}-\mu_{1})^{T}w}{w^{T}(\sum_{0}+\sum_{1})w}

  这个式子看起来符号有点多,我们将其化简一下,定义两个量:类内散度矩阵类间散度矩阵

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

  定义类内散度矩阵S_{w}=\sum_{0}+\sum_{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}
  • 类间散度矩阵(between-class scatter matrix):

  定义类间散度矩阵S_{b}=(\mu_{0}-\mu_{1})(\mu_{0}-\mu_{1})^{T}

  此时,最大化的目标函数J可重写为:

J = \frac{w^{T}S_{b}w}{w^{T}S_{w}w}

  把上式称为S_{b}S_{w}广义瑞利商(generalized rayleigh quotient)。

数学模型求解

  现在的问题就变成了,我们怎么来求这个投影方向w,使得目标函数最大。

  优化目标函数J的分子和分母都是关于w的二次项,因此求解最大化Jw的长度无关,只与其方向有关。那么我们将分母约束为1,将原问题转换为带有约束的最优化问题,再利用拉格朗日乘子法对其求解即可,原问题等价为:

min_{w} \ \ -w^{T}S_{b}w
s.t. \ \ w^{T}S_{w}w =1

  由拉格朗日乘子法可知,上式等价于:

S_{b}w=\lambda S_{w}w

  其中\lambda是拉格朗日乘子。由于(\mu_{0}-\mu_{1})^{T}w是标量,所以S_{b}w的方向恒为\mu_{0}-\mu_{1},不妨令:

S_{b}w=\lambda(\mu_{0}-\mu_{1})

  这里之所以可以令参数为\lambda,是因为整个问题我们都在求解方向,且S_{b}w的方向恒为\mu_{0}-\mu_{1},所以长度设置怎么好算怎么来。将S_{b}w=\lambda(\mu_{0}-\mu_{1})带入S_{b}w=\lambda S_{w}w可得:

w=S_{w}^{-1}(\mu_{0}-\mu_{1})

  到这里投影方向w的求解就完事了。但上述解涉及到求逆矩阵,考虑数值解的稳定性,实践过程中通常将S_{w}进行奇异值分解。S_{w}=U\sum V,这里\sum是一个实对角矩阵,其对角线上的元素是S_{w}的奇异值,再求解,得出S_{w}^{-1}=V \sum^{-1} U^{-1}

LDA推广到多分类

  将LDA推广到多分类问题中,假定存在N类,且第i类示例数为m_{i}。定义“全局散度矩阵S_{t}

S_{t}=S_{b}+S_{w} \\
= \sum_{i=1}^{m}(x_{i}-\mu)(x_{i}-\mu)^{T}

  \mu是所有样本的均值向量。

  将类内散度矩阵S_{w}重定义为每个类别的散度矩阵之和:

S_{w}=\sum_{i=1}^{N}S_{w_{i}}

  其中:

S_{w_{i}}=\sum_{x \in X_{i}}(x-\mu_{i})(x-\mu_{i})^{T}

  由此可求解出S_{b}

S_{b}=S_{t}-S_{w} \\
= \sum_{i=1}^{N}m_{i}(\mu_{i}-\mu)(\mu_{i}-\mu)

  用S_{b}S_{w}S_{t}三者中的任意两者都能够构造优化目标。常见的一种构造如下所示:

max_{W}\frac{tr(W^{T}S_{b}W)}{tr(W^{T}S_{w}W)}

  其中W \in R^{d \times (N-1)}tr(·)表示矩阵的迹(trace)。上式通过广义特征值问题求解:

S_{b}W=\lambda S_{w}W

  W的闭式解为S_{w}^{-1}S_{b}d^{'}个最大广义特征值所对应的特征向量组成的矩阵,d^{'} \leq N-1

  若将W视为一个投影矩阵,则多分类LDA将样本投影到d^{'}维空间,d^{'}通常小于原有属性数d。于是,可通过这个投影来减少样本点的维数,且投影过程中使用了类别信息,因此LDA也常被视为经典的监督降维技术

  与PCA降维不同LDA降维会保留类的区分信息。在LDA二分类中,第一类的均值与第二类的均值如果重叠在一起,将会找不到投影方向。PCA与LDA并没有某一种比另外一种更好的这种说法。

  本文主要参考书目,周志华机器学习。以前都没发现这书居然写地这么好。emmmm。

https://juejin.im/post/5e33d102f265da3e1932e041

「点点赞赏,手留余香」

    还没有人赞赏,快来当第一个赞赏的人吧!
0 条回复 A 作者 M 管理员
    所有的伟大,都源于一个勇敢的开始!
欢迎您,新朋友,感谢参与互动!欢迎您 {{author}},您在本站有{{commentsCount}}条评论