Linear Discriminant Analysis.
线性判别分析(Linear Discriminant Analysis,LDA),又称Fisher判别分析,是一种线性分类方法。LDA的思想是,给定训练样本集,将所有样本投影到空间中的一个超平面上,使得相同类别的样本的投影点尽可能接近,不同类别的样本的投影点尽可能远离。在对一个新的样本进行分类时,先将其投影到该超平面上,再根据投影点的位置(以及预先设置的阈值)确定该样本的类别。LDA也可以看作是一种监督的线性降维方法。
1. 二分类线性判别分析
若记NN个样本点{x1,x2,...,xN},属于类别0和类别1的样本总数分别为N0和N1。在样本空间中寻找一个向量w,将样本x投影到向量w上,得到投影wTx(注意到投影是标量)。
对投影的解释如下。若向量x与向量w之间的夹角为θ,则将向量x直接投影到向量w上的长度为|x|cosθ。直接计算两向量内积wTx=|w||x|cosθ;当|w|=1时两者等价,因此用内积表示投影。
注意到向量w可以被看作是分离超平面的法向量,通过选择使得样本投影的类间差距大,类内方差小的向量w,可以找到将w作为法向量的分离超平面f(x)=wTx,从而对样本点进行分类。
(1) 类间差距大(松耦合)
不同类别样本点之间的类间差距可以用均值(代表样本中心)投影之间的差距衡量。若记类别c的样本均值为μc=1Nc∑x∈Xcx,则均值投影为1Nc∑x∈XcwTx=wTμc。对于二分类问题,类别0和类别1的均值投影差异表示为‖wTμ0−wTμ1‖22。
(2) 类内方差小(高内聚)
同一类别样本点之间的类内方差可以用投影后的协方差矩阵衡量。若记类别c的样本协方差为Σc=1Nc∑x∈Xc(x−μc)(x−μc)T,则类别c投影后的协方差矩阵表示为:
1Nc∑x∈Xc(wTx−wTμc)(wTx−wTμc)T=1Nc∑x∈XcwT(x−μc)(x−μc)Tw=wTΣcw对于二分类问题,类别0和类别1的类内方差之和表示为wTΣ0w+wTΣ1w。
(3) LDA的目标函数
- 相同类别的样本的投影点尽可能接近,可以让同一类别样本投影点的协方差wTΣ0w+wTΣ1w尽可能小;
- 不同类别的样本的投影点尽可能远离,可以使不同类别的中心投影之间的距离‖wTμ0−wTμ1‖22尽可能大。
二分类的线性判别分析最大化以下目标函数:
J=||wTμ0−wTμ1||22wTΣ0w+wTΣ1w=wT(μ0−μ1)(μ0−μ1)TwwT(Σ0+Σ1)w定义:
- 类间散度矩阵(between-class scatter matrix)
- 类内散度矩阵(within-class scatter matrix)
则目标函数可写作:
J=wTSbwwTSww上述问题等价于求广义瑞利商的极值。由于对向量w等比例缩放不影响广义瑞利商的值,不失一般性,令wTSww=1,此时对广义瑞利商求极值,就是在约束wTSww=1下,求wTSbw的极值。 采用拉格朗日乘子法,定义拉格朗日函数:
L(w,λ)=wTSbw−λ(wTSww−1)上式对w求梯度,并令梯度为0,可得:
Sbw=λSww注意到(μ0−μ1)Tw是标量,因此Sbw=(μ0−μ1)(μ0−μ1)Tw与μ0−μ1同方向,不妨令Sbw=λ(μ0−μ1),代入上式得:
w=S−1w(μ0−μ1)若不同类别之间的数据无关(线性可分),即Sw是各向同性的对角矩阵Sw∝I,则有w∝(μ0−μ1)。
求得w后,即求得分类超平面的法向量,从而可得最终分类超平面:
f(x)=wTx=S−1w(μ0−μ1)x2. 多分类线性判别分析
可以将LDA从二分类推广到多分类的情形。若记N个样本点{x1,x2,...,xN},共有C种类别,所有样本点的均值为μ=1N∑Ni=1xi,定义全局散度矩阵 St:
St=N∑i=1(xi−μ)(xi−μ)T类内散度矩阵 Sw定义为每个类别的散度矩阵之和:
Sw=C∑c=1Swc=C∑c=1∑x∈Xc(x−μc)(x−μc)T则类间散度矩阵 Sb可以通过St和Sw计算如下:
Sb=St−Sw=N∑i=1(xi−μ)(xi−μ)T−C∑c=1∑x∈Xc(x−μc)(x−μc)T=C∑c=1∑x∈Xc(x−μ)(x−μ)T−C∑c=1∑x∈Xc(x−μc)(x−μc)T=C∑c=1∑x∈Xc(xxT−xμT−μxT+μμT−xxT+xμTc+μcxT−μcμTc)=C∑c=1∑x∈Xc(−xμT−μxT+μμT+xμTc+μcxT−μcμTc)=C∑c=1(−∑x∈XcxμT−∑x∈XcμxT+∑x∈XcμμT+∑x∈XcxμTc+∑x∈XcμcxT−∑x∈XcμcμTc)=C∑c=1(−NcμcμT−NcμμTc+NcμμT+NcμcμTc+NcμcμTc−NcμcμTc)=C∑c=1(−NcμcμT−NcμμTc+NcμμT+NcμcμTc)=C∑c=1Nc(μc−μ)(μc−μ)T上式表示类间散度矩阵可以表示成所有类别样本的中心与总体中心之间的差距之和。多分类LDA的优化目标函数表示为:
maxwtr(WTSbW)tr(WTSwW)上式也是广义瑞利商的形式,可以将问题转化为广义特征值问题:
S−1wSbW=λW3. 核线性判别分析
将核方法引入线性判别分析,即可得到核线性判别分析(Kernelized Linear Discriminant Analysis),从而将线性模型扩展成非线性模型。
引入映射ϕ:X→F将样本空间X变换到高维的特征空间F,在F中构造线性判别分析,以求得:
f(x)=wTϕ(x)第c类样本在特征空间F中的均值计算为:
μϕc=1Nc∑x∈Xcϕ(x)引入核函数K(xi,xj)=ϕ(xi)Tϕ(xj)隐式地表示特征映射ϕ及其内积,则由表示定理,函数f(x)表示为:
f(x)=wTϕ(x)=N∑i=1αiK(x,xi),w=N∑i=1αiϕ(xi)若记训练样本在特征空间F中的类间散度矩阵 Sϕb和类内散度矩阵 Sϕw,两个散度矩阵计算为:
Sϕb=(μϕ0−μϕ1)(μϕ0−μϕ1)TSϕw=Σϕ0+Σϕ1=∑c=0,1∑x∈Xc(ϕ(x)−μϕc)(ϕ(x)−μϕc)T则核线性判别分析的目标函数可表示为:
J=wTSϕbwwTSϕww使用线性判别分析的方法求解上述问题即可得到α,进而求得函数f(x)。
Related Issues not found
Please contact @0809zheng to initialize the comment