线性判别分析

来自集智百科
跳转到: 导航搜索

目录

定义

线性判别分析既可以处理二分类问题, 同时也可以用来做有监督的数据降维.

  • 两类问题:线性判别分析是一种线性分类器. 同时它也是贝叶斯分类准则的一个特例 (正负两类样本都采样于高斯分布,并且高斯分布的协方差相同)。
  • 多类问题:对于多类问题(假设总共有K类), 线性判别分析能够将高维数据降维到K-1维. 在新的低维空间, 类内样本之间的距离缩小, 类间样本之间的距离拉大; 换句话说, 新的低维表示对于当前的多分类问题更有判别力.

两类问题(基于贝叶斯方法)

贝叶斯准则回顾

按照贝叶斯公式可知,后验概率正比于似然函数和先验概率的乘积


P(y|x) \varpropto P(x|y)P(y)

给定输入样本,后验概率最大的类别就是贝叶斯准则下预测的输出.

对于二分类问题, 贝叶斯准则可以简化为判断决策函数的大于零或者小于零。 决策函数是不同类别后验概率的对数似然比。


f(x) = logP(x|y=1) - logP(x|y=2) + logP(y=1) - logP(y=2)

如果正负样本的数量相同,或者正负类别的先验概率相等,那么决策函数可以进一步简化为,


f(x) = logP(x|y=1) - logP(x|y=2)

二次判别分析(高斯假设)

假设正负样本采样于不同的高斯分布,


P(x|y=1) = N\left(x\left|\mu _1\right.,\Sigma _1\right),


P(x|y=2) = N\left(x\left|\mu _2\right.,\Sigma _2\right).

将以上的分布函数带入到二分类的决策函数中,可以得到二次判别分析的决策函数


f_{QDA}(x) = x^T\left(\Sigma _2^{-1}-\Sigma _1^{-1}\right)x - \left(\mu _2^T\Sigma _2^{-1}-\mu _1^T\Sigma _1^{-1}\right)x+\left(\log  \left|\Sigma _2\right|-\log  |\Sigma _1|+\mu _2^T\Sigma _2^{-1}\mu _2-\mu _1^T\Sigma _1^{-1}\mu _1\right)

可以看出, 二次判别分析的决策函数是关于输入特征(or 变量的)二次函数. 从左到右, 决策函数中的三项分别对应着,二次项,一次项和常数项.

线性判别分析(高斯假设+同方差假设)

如果进一步假设, 正负样本的方差相同, 那么二次判别分析就退化为线性判别分析. 在二次判别分析的基础上, 令  \Sigma_1 = \Sigma_2 = \Sigma , 可以很容易得到线性判别分析的决策函数.


f_{LDA}(x) = - \left(\mu _2^T\Sigma^{-1}-\mu _1^T\Sigma^{-1}\right)x+\left(\mu _2^T\Sigma^{-1}\mu _2-\mu _1^T\Sigma^{-1}\mu _1\right)

可以看出, 因为方差相同的假设, 二次项从原来的决策函数中消失了, 最高次项是线性的. 这也是该方法被称为线性判别分析的原因.

多类问题(Fisher判别分析)

K近邻方法与监督降维

解决多分类问题的一种简单的方式是K近邻投票. K近邻的基本假设是:相邻的样本应该有相同的类别标签. 但是如果训练数据密度不够,那么这个假设的可靠性就会降低,直接导致分类的效果下降. 另外,最近邻搜索的计算和存储成本随着样本的维度线性增长, 当数据维度很高时,对于很多实际应用(实时跟踪或者识别; 有内存限制的设备如手机,相机,等), K近邻方法的成本都过高.

为了解决以上两个问题,一般会用监督降维的方法提取低维的,更有判别力的特征. 这样做,一方面能够提高K近邻方法的效果, 另外一方面会降低成本.

一种监督降维方法--Fisher判别分析

Fisher判别分析就是一种能够达到上述效果的监督降维方法. Fisher判别分析通过同时最小化类内差(同一类别内部样本之间差异), 并且最大化类间差(不同类别样本之间的差异),获得更加有判别力的低维特征, 以及从高维到低维的线性投影。如果类别数量是K, 那么高维数据将会被投影到K-1的低维空间. 当K=2, 也就是二分类问题时, Fisher判别分析等价于线性判别分析(贝叶斯方法+高斯+同方差假设).

具体推导

具体来说, 假设样本数量是n, 降维之前样本的集合为 \{x_1, x_2, ... , x_n \}, x_i\in \mathbb{R}^D, 他们对应的类别标签是 \{y_1, y_2, ... , y_n \}, y_i\in \mathbb{N}. 降维之后的样本集合为 \{u_1, u_2, ... , u_n \}, u_i\in \mathbb{R}^d . 通过一个未知的(待学习的)线性投影  W \in \mathbb{R}^{d\times D } , 原有的高维数据被映射到对应的低维表示。在新的低维空间中, 类内差 \sigma_w 被缩小, 类间差 \sigma_b 被放大. 这里的下标分别是within和between的首字母. 类内差和类间差可以通过如下公式计算,


\sigma_w = \sum _{y_i= y_j} \left\|u_i-u_j\|^2\right.


\sigma_b = \sum _{y_i\neq y_j} \left\|u_i-u_j\|^2\right.

考虑到低维表示是原始高维数据的线性投影, 也就是  u_i = W x_i , 将这个线性投影带入到类内差以及类间差的计算公式中可以得到,


\sigma_w = trace(S_w W^T W), \quad where~~ S_w = \sum _{y_i = y_j} (x_i-x_j)^T(x_i-x_j)


\sigma_b = trace(S_b W^T W) , \quad  where~~ S_b = \sum _{y_i \neq  y_j} (x_i-x_j)^T(x_i-x_j)

我们的目标是缩小类内差并且增加类间差. 考虑到, 1)类内差和类间差非负 2)假设类内差不等于零(也就是说类内协方差差矩阵S_w所有特征值大于0. 一般来说,在样本充足且原始数据维度不是很高的情况下,这个假设成立), 缩小类内差以及增大类间差的双目标可以统一到一个目标函数中, 也就是如下目标函数

 \underset{W}{\max } \frac{\sigma _b}{\sigma _w}

可以证明以上问题的最优解是矩阵S_w^{-1} S_b的前d个特征向量组成的线性投影矩阵. 每一个特征向量将原始高维数据投影到低维空间相对应的维度.

个人工具
名字空间
操作
导航
工具箱