113
个编辑
更改
跳到导航
跳到搜索
创建页面，内容为“=定义= 线性判别分析既可以处理二分类问题, 同时也可以用来做有监督的数据降维. *两类问题：线性判别分析是一种线性分…”
=定义=
线性判别分析既可以处理二分类问题, 同时也可以用来做有监督的数据降维.
*两类问题：线性判别分析是一种[[线性分类器]]. 同时它也是[[贝叶斯分类]]准则的一个特例 (正负两类样本都采样于高斯分布,并且高斯分布的协方差相同)。
*多类问题：对于多类问题(假设总共有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>个特征向量组成的线性投影矩阵. 每一个特征向量将原始高维数据投影到低维空间相对应的维度.
[[category:旧词条迁移]]
线性判别分析既可以处理二分类问题, 同时也可以用来做有监督的数据降维.
*两类问题：线性判别分析是一种[[线性分类器]]. 同时它也是[[贝叶斯分类]]准则的一个特例 (正负两类样本都采样于高斯分布,并且高斯分布的协方差相同)。
*多类问题：对于多类问题(假设总共有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>个特征向量组成的线性投影矩阵. 每一个特征向量将原始高维数据投影到低维空间相对应的维度.
[[category:旧词条迁移]]