线性判别分析

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

定义

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

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

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

贝叶斯准则回顾

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

[math] P(y|x) \varpropto P(x|y)P(y) [/math]

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

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

[math] f(x) = logP(x|y=1) - logP(x|y=2) + logP(y=1) - logP(y=2) [/math]

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

[math] f(x) = logP(x|y=1) - logP(x|y=2) [/math]

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

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

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

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

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

[math] 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) [/math]

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

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

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

[math] 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) [/math]

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

多类问题(Fisher判别分析)

K近邻方法与监督降维

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

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

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

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

具体推导

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

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

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

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

[math] \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) [/math]

[math] \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) [/math]

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

[math] \underset{W}{\max } \frac{\sigma _b}{\sigma _w} [/math]

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