Linear Discriminant Analysis.

线性判别分析(Linear Discriminant Analysis,LDA),又称Fisher判别分析,是一种线性分类方法。LDA的思想是,给定训练样本集,将所有样本投影到空间中的一个超平面上,使得相同类别的样本的投影点尽可能接近,不同类别的样本的投影点尽可能远离。在对一个新的样本进行分类时,先将其投影到该超平面上,再根据投影点的位置(以及预先设置的阈值)确定该样本的类别。LDA也可以看作是一种监督的线性降维方法。

1. 二分类线性判别分析

若记NN个样本点{x1,x2,...,xN},属于类别0和类别1的样本总数分别为N0N1。在样本空间中寻找一个向量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=1NcxXcx,则均值投影为1NcxXcwTx=wTμc。对于二分类问题,类别0和类别1的均值投影差异表示为wTμ0wTμ122

(2) 类内方差小(高内聚)

同一类别样本点之间的类内方差可以用投影后的协方差矩阵衡量。若记类别c的样本协方差为Σc=1NcxXc(xμc)(xμc)T,则类别c投影后的协方差矩阵表示为:

1NcxXc(wTxwTμc)(wTxwTμc)T=1NcxXcwT(xμc)(xμc)Tw=wTΣcw

对于二分类问题,类别0和类别1的类内方差之和表示为wTΣ0w+wTΣ1w

(3) LDA的目标函数

二分类的线性判别分析最大化以下目标函数:

J=||wTμ0wTμ1||22wTΣ0w+wTΣ1w=wT(μ0μ1)(μ0μ1)TwwT(Σ0+Σ1)w

定义:

Sb=(μ0μ1)(μ0μ1)T Sw=Σ0+Σ1

则目标函数可写作:

J=wTSbwwTSww

上述问题等价于求广义瑞利商的极值。由于对向量w等比例缩放不影响广义瑞利商的值,不失一般性,令wTSww=1,此时对广义瑞利商求极值,就是在约束wTSww=1下,求wTSbw的极值。 采用拉格朗日乘子法,定义拉格朗日函数:

L(w,λ)=wTSbwλ(wTSww1)

上式对w求梯度,并令梯度为0,可得:

Sbw=λSww

注意到(μ0μ1)Tw是标量,因此Sbw=(μ0μ1)(μ0μ1)Twμ0μ1同方向,不妨令Sbw=λ(μ0μ1),代入上式得:

w=S1w(μ0μ1)

若不同类别之间的数据无关(线性可分),即Sw是各向同性的对角矩阵SwI,则有w(μ0μ1)

求得w后,即求得分类超平面的法向量,从而可得最终分类超平面:

f(x)=wTx=S1w(μ0μ1)x

2. 多分类线性判别分析

可以将LDA从二分类推广到多分类的情形。若记N个样本点{x1,x2,...,xN},共有C种类别,所有样本点的均值为μ=1NNi=1xi,定义全局散度矩阵 St

St=Ni=1(xiμ)(xiμ)T

类内散度矩阵 Sw定义为每个类别的散度矩阵之和:

Sw=Cc=1Swc=Cc=1xXc(xμc)(xμc)T

类间散度矩阵 Sb可以通过StSw计算如下:

Sb=StSw=Ni=1(xiμ)(xiμ)TCc=1xXc(xμc)(xμc)T=Cc=1xXc(xμ)(xμ)TCc=1xXc(xμc)(xμc)T=Cc=1xXc(xxTxμTμxT+μμTxxT+xμTc+μcxTμcμTc)=Cc=1xXc(xμTμxT+μμT+xμTc+μcxTμcμTc)=Cc=1(xXcxμTxXcμxT+xXcμμT+xXcxμTc+xXcμcxTxXcμcμTc)=Cc=1(NcμcμTNcμμTc+NcμμT+NcμcμTc+NcμcμTcNcμcμTc)=Cc=1(NcμcμTNcμμTc+NcμμT+NcμcμTc)=Cc=1Nc(μcμ)(μcμ)T

上式表示类间散度矩阵可以表示成所有类别样本的中心与总体中心之间的差距之和。多分类LDA的优化目标函数表示为:

maxwtr(WTSbW)tr(WTSwW)

上式也是广义瑞利商的形式,可以将问题转化为广义特征值问题:

S1wSbW=λW

3. 核线性判别分析

核方法引入线性判别分析,即可得到核线性判别分析(Kernelized Linear Discriminant Analysis),从而将线性模型扩展成非线性模型。

引入映射ϕ:XF将样本空间X变换到高维的特征空间F,在F中构造线性判别分析,以求得:

f(x)=wTϕ(x)

c类样本在特征空间F中的均值计算为:

μϕc=1NcxXcϕ(x)

引入核函数K(xi,xj)=ϕ(xi)Tϕ(xj)隐式地表示特征映射ϕ及其内积,则由表示定理,函数f(x)表示为:

f(x)=wTϕ(x)=Ni=1αiK(x,xi),w=Ni=1αiϕ(xi)

若记训练样本在特征空间F中的类间散度矩阵 Sϕb类内散度矩阵 Sϕw,两个散度矩阵计算为:

Sϕb=(μϕ0μϕ1)(μϕ0μϕ1)TSϕw=Σϕ0+Σϕ1=c=0,1xXc(ϕ(x)μϕc)(ϕ(x)μϕc)T

则核线性判别分析的目标函数可表示为:

J=wTSϕbwwTSϕww

使用线性判别分析的方法求解上述问题即可得到α,进而求得函数f(x)