参考:http://blog.csdn.net/xiazhaoqiang/article/details/6579059
前言:
第二篇的文章中谈到,和部门老大一宁出去outing的时候,他给了我相当多的机器学习的建议,里面涉及到很多的算法的意义、学习方法等等。一宁上次给我提到,如果学习分类算法,最好从线性的入手,线性分类器最简单的就是LDA,它可以看做是简化版的SVM,如果想理解SVM这种分类器,那理解LDA就是很有必要的了。
谈到LDA,就不得不谈谈PCA,PCA是一个和LDA非常相关的算法,从推导、求解、到算法最终的结果,都有着相当的相似。
本次的内容主要是以推导数学公式为主,都是从算法的物理意义出发,然后一步一步最终推导到最终的式子,LDA和PCA最终的表现都是解一个矩阵特征值的问题,但是理解了如何推导,才能更深刻的理解其中的含义。本次内容要求读者有一些基本的线性代数基础,比如说特征值、特征向量的概念,空间投影,点乘等的一些基本知识等。除此之外的其他公式、我都尽量讲得更简单清楚。
LDA:
LDA的全称是Linear Discriminant Analysis(线性判别分析),是一种supervised learning。有些资料上也称为是Fisher’s Linear Discriminant,因为它被Ronald Fisher发明自1936年,Discriminant这次词我个人的理解是,一个模型,不需要去通过概率的方法来训练、预测数据,比如说各种贝叶斯方法,就需要获取数据的先验、后验概率等等。LDA是在目前机器学习、数据挖掘领域经典且热门的一个算法,据我所知,百度的商务搜索部里面就用了不少这方面的算法。
LDA的原理是,将带上标签的数据(点),通过投影的方法,投影到维度更低的空间中,使得投影后的点,会形成按类别区分,一簇一簇的情况,相同类别的点,将会在投影后的空间中更接近。要说明白LDA,首先得弄明白线性分类器(Linear Classifier):因为LDA是一种线性分类器。对于K-分类的一个分类问题,会有K个线性函数:
当满足条件:对于所有的j,都有Yk > Yj,的时候,我们就说x属于类别k。对于每一个分类,都有一个公式去算一个分值,在所有的公式得到的分值中,找一个最大的,就是所属的分类了。
上式实际上就是一种投影,是将一个高维的点投影到一条高维的直线上,LDA最求的目标是,给出一个标注了类别的数据集,投影到了一条直线之后,能够使得点尽量的按类别区分开,当k=2即二分类问题的时候,如下图所示:
红色的方形的点为0类的原始点、蓝色的方形点为1类的原始点,经过原点的那条线就是投影的直线,从图上可以清楚的看到,红色的点和蓝色的点被原点明显的分开了,这个数据只是随便画的,如果在高维的情况下,看起来会更好一点。下面我来推导一下二分类LDA问题的公式:
假设用来区分二分类的直线(投影函数)为:
LDA分类的一个目标是使得不同类别之间的距离越远越好,同一类别之中的距离越近越好,所以我们需要定义几个关键的值。
类别i投影后的中心点为:
衡量类别i投影后,类别点之间的分散程度(方差)为:
最终我们可以得到一个下面的公式,表示LDA投影到w后的损失函数:
我们分类的目标是,使得类别内的点距离越近越好(集中),类别间的点越远越好。分母表示每一个类别内的方差之和,方差越大表示一个类别内的点越分散,分子为两个类别各自的中心点的距离的平方,我们最大化J(w)就可以求出最优的w了。想要求出最优的w,可以使用拉格朗日乘子法,但是现在我们得到的J(w)里面,w是不能被单独提出来的,我们就得想办法将w单独提出来。
我们定义一个投影前的各类别分散程度的矩阵,这个矩阵看起来有一点麻烦,其实意思是,如果某一个分类的输入点集Di里面的点距离这个分类的中心店mi越近,则Si里面元素的值就越小,如果分类的点都紧紧地围绕着mi,则Si里面的元素值越更接近0.
带入Si,将J(w)分母化为:
同样的将J(w)分子化为:
这样损失函数可以化成下面的形式:
这样就可以用最喜欢的拉格朗日乘子法了,但是还有一个问题,如果分子、分母是都可以取任意值的,那就会使得有无穷解,我们将分母限制为长度为1(这是用拉格朗日乘子法一个很重要的技巧,在下面将说的PCA里面也会用到,如果忘记了,请复习一下高数),并作为拉格朗日乘子法的限制条件,带入得到:
这样的式子就是一个求特征值的问题了。
对于N(N>2)分类的问题,我就直接写出下面的结论了:
这同样是一个求特征值的问题,我们求出的第i大的特征向量,就是对应的Wi了。
这里想多谈谈特征值,特征值在纯数学、量子力学、固体力学、计算机等等领域都有广泛的应用,特征值表示的是矩阵的性质,当我们取到矩阵的前N个最大的特征值的时候,我们可以说提取到的矩阵主要的成分(这个和之后的PCA相关,但是不是完全一样的概念)。在机器学习领域,不少的地方都要用到特征值的计算,比如说图像识别、pagerank、LDA、还有之后将会提到的PCA等等。
下图是图像识别中广泛用到的特征脸(eigen face),提取出特征脸有两个目的,首先是为了压缩数据,对于一张图片,只需要保存其最重要的部分就是了,然后是为了使得程序更容易处理,在提取主要特征的时候,很多的噪声都被过滤掉了。跟下面将谈到的PCA的作用非常相关。
特征值的求法有很多,求一个D * D的矩阵的时间复杂度是O(D^3), 也有一些求Top M的方法,比如说power method,它的时间复杂度是O(D^2 * M), 总体来说,求特征值是一个很费时间的操作,如果是单机环境下,是很局限的。
PCA:
主成分分析(PCA)与LDA有着非常近似的意思,LDA的输入数据是带标签的,而PCA的输入数据是不带标签的,所以PCA是一种unsupervised learning。LDA通常来说是作为一个独立的算法存在,给定了训练数据后,将会得到一系列的判别函数(discriminate function),之后对于新的输入,就可以进行预测了。而PCA更像是一个预处理的方法,它可以将原本的数据降低维度,而使得降低了维度的数据之间的方差最大(也可以说投影误差最小,具体在之后的推导里面会谈到)。
方差这个东西是个很有趣的,有些时候我们会考虑减少方差(比如说训练模型的时候,我们会考虑到方差-偏差的均衡),有的时候我们会尽量的增大方差。方差就像是一种信仰(强哥的话),不一定会有很严密的证明,从实践来说,通过尽量增大投影方差的PCA算法,确实可以提高我们的算法质量。
说了这么多,推推公式可以帮助我们理解。我下面将用两种思路来推导出一个同样的表达式。首先是最大化投影后的方差,其次是最小化投影后的损失(投影产生的损失最小)。
最大化方差法:
假设我们还是将一个空间中的点投影到一个向量中去。首先,给出原空间的中心点:
上面这个式子如果看懂了之前推导LDA的过程,应该比较容易理解,如果线性代数里面的内容忘记了,可以再温习一下,优化上式等号右边的内容,还是用拉格朗日乘子法:
这是一个标准的特征值表达式了,λ对应的特征值,u对应的特征向量。上式的左边取得最大值的条件就是λ1最大,也就是取得最大的特征值的时候。假设我们是要将一个D维的数据空间投影到M维的数据空间中(M < D), 那我们取前M个特征向量构成的投影矩阵就是能够使得方差最大的矩阵了。
最小化损失法:
假设输入数据x是在D维空间中的点,那么,我们可以用D个正交的D维向量去完全的表示这个空间(这个空间中所有的向量都可以用这D个向量的线性组合得到)。在D维空间中,有无穷多种可能找这D个正交的D维向量,哪个组合是最合适的呢?
假设我们已经找到了这D个向量,可以得到:
上式表示,得到的新的x是由前M 个基的线性组合加上后D - M个基的线性组合,注意这里的z是对于每个x都不同的,而b对于每个x是相同的,这样我们就可以用M个数来表示空间中的一个点,也就是使得数据降维了。但是这样降维后的数据,必然会产生一些扭曲,我们用J描述这种扭曲,我们的目标是,使得J最小:
上式的意思很直观,就是对于每一个点,将降维后的点与原始的点之间的距离的平方和加起来,求平均值,我们就要使得这个平均值最小。我们令:
再用上拉普拉斯乘子法(此处略),可以得到,取得我们想要的投影基的表达式为:
这里又是一个特征值的表达式,我们想要的前M个向量其实就是这里最大的M个特征值所对应的特征向量。证明这个还可以看看,我们J可以化为:
也就是当误差J是由最小的D - M个特征值组成的时候,J取得最小值。跟上面的意思相同。
下图是PCA的投影的一个表示,黑色的点是原始的点,带箭头的虚线是投影的向量,Pc1表示特征值最大的特征向量,pc2表示特征值次大的特征向量,两者是彼此正交的,因为这原本是一个2维的空间,所以最多有两个投影的向量,如果空间维度更高,则投影的向量会更多。
总结:
本次主要讲了两种方法,PCA与LDA,两者的思想和计算方法非常类似,但是一个是作为独立的算法存在,另一个更多的用于数据的预处理的工作。另外对于PCA和LDA还有核方法,本次的篇幅比较大了,先不说了,以后有时间再谈:
参考资料:
prml bishop,introduce to LDA(对不起,这个真没有查到出处)
相关推荐
:线性判别分析(LDA)和主成分分析(PCA)都在各个领域有着重 要的作用。他们各自抓住样本在特征空间的不同特征, 一般情况下更趋向于使 用LDA, 因为LDA直接处理类间的分析问题, 而PCA则没有突出类的结构。 然而实验...
主成分分析法和线性判别分析常用来对原始数据进行简单的数学分析
将高维的模式样本投影到最佳鉴别矢量空间,以达到抽取分类信息和压缩特征空间维数的效果,投影后保证模式样本在新的子空间有最大的类间距离和最小的类内距离,即模式在该空间中有最佳的可分离性,与PCA区别:LDA考虑...
用于数据信号的降维主要包括线性判别分析和主成分分析法,代码全,可以运行
matlab线性判别分析函数,首先需要用PCA进行数据压缩,然后提前特征变量,进行判别分析
PCA+LDA 利于新学者使用 主成分分析 线性判别分析 代码来在cai deng
本研究回顾了基于主成分分析PCA和判别分析LDA的降维方法及其扩展,包括经典主成分分析、概率主成分分析、核主成分分析,以及线性判别分析、局部保持降维、图形嵌入判别分析和半监督降维分析。
系统地讲解了线性判别分析,主成分分析,奇异值分解的数学原理
原创,测试识别率0.99,重构图像完全比不上PCA,但能满足分类要求。可下载后直接运行,并保存特征向量数据
在这里,我训练了支持向量机,线性判别分析和四层前馈神经网络,以对来自CIFAR-10数据集的10个图像类别进行分类,从而以62.7%的SVM实现了最高的准确性。 该实验的关键问题是发现用于降低尺寸的PCA和LDA的非传统组合...
针对自动引导车(AGV)视觉引导过程中多分支路径识别与跟踪的实时性与稳健性要求, 提出一种主成分分析(PCA)-线性判别分析(LDA)与支持向量机(SVM)相结合的路径识别算法。首先对AGV行驶过程中拍摄的图像进行预处理, 并用...
该方法结合了主成分分析(PCA)和线性判别分析(LDA)以减少高光谱数据的维数。 首先,将PCA用于一维降维,并获得非奇异的类内散布矩阵。 其次,将LDA应用于第二维降维,大大减少了计算量。 最后,将相关向量机模型...
用fisher线性判别分析建立P300分类模型。特征提取用PCA。
提出了一种新的小波域主元分析与线性辨别分析相结合的红外人脸识别方法。首先通过DWT将红外人脸图像通过二级小波...同传统的PCA和PCA LDA的方法相比,该方法更能利用人脸图像的有用判别信息,并得到更好的识别效果。
PCA与LDA的介绍,pca-vs-lda.pdf,pca和lda在模式识别中可以用于降维,而lda的线性判别在统计中非常重要
基于二维线性判别分析的人脸识别算法研究,王丽莉,周亚同,在现有成熟的人脸识别算法中,主成份分析法(PCA)侧重于压缩,不利于分类,线性判别分析(LDA)算法虽适合于分类,但存在小样本的
依据主成分分析方法(PCA)对图像具有很好的表达能力,即能很好地重构原图像,而线性鉴别分析(LDA)可使图像样本具有较高可分性的特点,提出对图像先进行PCA处理,再进行LDA处理,从而降低人脸特征维数并对人脸图像进行...
基本上我们这里有 LDA(线性判别分析),直接 LDA,它可以做 LDA 但更好(基本上当你的类内散布矩阵 Sw 是奇异的时,它不会丢弃 Sw 的零空间,它包含大部分判别信息)和 PCA+LDA,它对数据进行 PCA,然后对降维数据...
与主成分分析(PCA)不同,LDA考虑了类别信息。 2. **二次判别分析(Quadratic Discriminant Analysis,QDA):** QDA是判别分析的另一种形式。与LDA不同,QDA不要求各个类别的协方差矩阵相等。因此,在QDA中,每个...
线性判别分析(linear discriminant analysis),LDA。也称为Fisher线性判别(FLD)是模式识别的经典算法。 (1)中心思想:将高维的样本投影到最佳鉴别矢量空间,来达到抽取分类信息和压缩特种空间维数的效果,投影...