搜档网
当前位置:搜档网 › 基于LDA的人脸识别 (1)

基于LDA的人脸识别 (1)

基于LDA的人脸识别

成员及各自任务:

程鑫:LDA基本算法

姜华杰:LDA改进算法

赵铖:背景和LDA的相关应用

摘要

线性决策分析是人脸识别技术中应用最广泛的算法之一。本文主要介绍了fisher算法的原理。Fisher算法的核心思想是寻找最佳投影向量,使类内离散度达到最小,类间离散度达到最大,通过对样本空间进行投影,从而达到分类的目的。应用LDA算法会遇到小样本问题,使得计算复杂度提高。本文针对小样本问题,介绍了LDA的改进算法,并证明了类内离散的矩阵的零空间的最大特征值对应的特征向量即为最佳投影向量。

关键词:LDA 人脸识别信用评估

目录

第一章背景 (4)

第二章 LDA的基本算法 (5)

2.1两类LDA算法的原理 (5)

2.2多类LDA算法的原理 (7)

第三章 LDA的改进算法 (10)

3.1 问题的提出与解决办法 (10)

3.2传统LDA的方法与潜在问题 (10)

3.3改进的LDA算法 (11)

第四章相关应用 (15)

4.1标准化LDA进行人脸识别 (15)

4.2线性判别分析在个人性用评估中的应用 (18)

参考文献 (22)

第一章背景

LDA:Linear Discriminant Analysis (线性判别分析)简称判别分析,是统计学上的一种分析方法,用于在已知的分类下遇到有新的样本时,选定一个判别标准,以判定如何将新样本放置于哪一个类别之中。这种方法主要应用于人脸识别,以及医学的患者疾病分级、经济学的市场定位、产品管理及市场研究等范畴。

关于LDA分析的研究应追溯到Fisher在1936年发表的经典论文( Fisher R A. The use of multiple measurements in taxonomic problems),其基本思想是选择使得Fisher准则函数达到极值的向量作为最佳投影方向,从而使得样本在该方向上投影后,达到最大的类间离散度和最小的类内离散度。在Fisher思想的基础上,Wilks和Duda分别提出了鉴别矢量集的概念,即寻找一组鉴别矢量构成子空间,以原始样本在该子空间内的投影矢量作为鉴别特征用于识别。

1970年Sammon提出了基于Fisher鉴别准则的最佳鉴别平面的概念。随后,Foley和Sammon进一步提出了采用一组满足正交条件的最佳鉴别矢量集进行特征抽取的方法。

1988年Duchene和Leclercq给出了多类情况下最佳鉴别矢量集的计算公式。

2001年Jin和Yang 从统计不相关的角度,提出了具有统计不相关性的最优鉴别矢量集的概念。与F-S鉴别矢量集不同的是,具有统计不相关性的最优鉴别矢量是满足共轭正交条件的,该方法被称为不相关的鉴别分析或Jin-Yang线性鉴别法。

以上提到的各种方法仅适用于类内散布矩阵非奇异(可逆)的情形,但实际应用中存在着大量的典型的小样本问题,比如在人脸图像识别问题中,类内散布矩阵经常是奇异的。这是因为待识别的图像矢量的维数一般较高,而在实际问题中难以找到或根本不可能找到足够多的训练样本来保证类内散布矩阵的可逆性。因此,在小样本情况下,如何抽取Fisher最优鉴别特征成为一个公认的难题。

第二章 LDA 的基本算法

LDA 的基本思想是找到合适的向量,使得样本特征经过向量映射后获得最大的类间离散程度和最小的类内离散程度。

给定m 个n 维特征的训练样例

{

})

()()()

(i i 2i 1i ,...,,n

x x x x (i 从1到m )

,每个(i)

x

应一个类标签(i)y 。我们就是要学习出参数θ,使得

)(i )(i T x g y θ=)((g 是sigmoid 函数)。我们先从只有两类的况开始考虑,然后再来考虑多类时的情况。

2.1两类LDA 算法的原理

给定特征为d 维的N 个样例,{}

)

()(2)(1)(,...,,i d

i i i x x x x ,其中有1N 个样例属于类别1C ,

另外2N 个样例属于类别2C ,两类个数之和为N 。原始特征数为d ,我们想将其降到一维,而又要保证类别能够“清晰”地反映在低维数据上,也就是这一维就能决定每个样例的类别。我们需要找到一个最佳投影向量w ,使得样例x 在w 方向上投影之后,能够容易区分它们的类别,样例x 在最佳投影向量w 上的投影表达式为

x w T

y = (1)

这里的y 是x 投影到直线上的点到原点的距离。

什么是最佳的投影方向呢?首先要使投影之后的得到的样本中心点尽量的分离,定量表示也即是:

)()(21~

2~

1μμμμ-=-=T w w J (2) 此处

i μ是每类样例的均值(中心点)

,这里i 只有两个,

∑∈

=

i

x x N ω

μi

11 (3) ~

i μ 是x 投影到w 后的样本点均值,

i T x T

i

y i

w x w N y N i

i

μμω

ω∑∑∈

∈==

=

11~

i (4)

但是仅仅只是样本点的中心分离是不够的,各类的样本元素还需要紧凑,也即是每个类的元素离其中心点的距离要尽量的小。也即是样本点之间的方差要小,方差越大,样本点越难以分离。因此,我们引入了散列值,对投影之后的类求散列值,即是

∑∈-=

i

w y i

i y S 2

~

2

~)

(μ (5)

从公式中可以看出,只是少除以样本数量的方差值,散列值的几何意义是样本点的密集程度,值越大,越分散,反之,越集中。

而我们想要的投影后的样本点的样子是:不同类别的样本点越分开越好,同类的越聚集越好,也就是均值差越大越好,散列值越小越好。那么,我们可以使用J(w)和S 来度量,最终的度量公式是

2

~1

2

~12

~2

~

1)(S S w J +-=

μμ (6)

将~

i μ的表达式带入散列值的式子可以得到

∑∑∑∈∈∈--=-=

-=

i

i

i

w x T i i T w x i T T

w y i

i w x x w w x w

y S ))(()()

(22

~

2

~μμμμ (7)

定义上式中中间那部分为:

∑∈--=i

w x T i i i x x S ))((μμ (8)

这个公式的样子不就是少除以样例数的协方差矩阵,称为散列矩阵(scatter matrices )。对于只有两类的情况下,定义

21S S S w += (9)

称为类内散列矩阵。同时,

w S w w w w B T T T T T =--=-=))((w -21212

212~

2~

1μμμμμμμμ)()( (10)

称为类间散列矩阵。 那么J(w)最终可以表示为

w

S w w S w w J w T B T =)( (11)

现在,我们需要通过上面的式子,求出w 使得J (w )最大。由于我们只是需要知道w 的方向,所以为了方便求解,我们令,那么加入拉格朗日乘

子后,求导

w

S w S w S w S dw

dc

w S w w S w w c w B w B w T B T λλ=?=-=?--=022)1()( (12)

其中用到了矩阵微积分,求导时可以简单地把w

S w T w 当做

2

w w S 看待。如果

w

S 可逆,那么讲求导后的结果两边都乘以

1

-w

S ,得

w w S S B w λ=-1

(13)

从中可以看出w 是矩阵B

S S 1

w -的特征向量。 这个公式称为Fisher linear

discrimination 。

由于T

B S )-(-2121μμμμ)(=,那么w T B w S λμμμμμμ*==)()(212121-)-(-w ,带

入最后的特征公式得

w S S S w B λλμμ=*=--)(211

w 1w -w , (14)

而w 扩大缩小任何倍不影响结果,因此可以约去两边的未知常数λ和

w

λ,得:

)(w 211

μμ-=-w S (15)

W 即是我们最终需要找到的投影向量。

2.2多类LDA 算法的原理

针对两类的情况,我们将d 维降到一维,但是在多类的情况下,一维已经不能满足需求。假设我们有C 个类别,需要K 维向量(或者叫做基向量)来做投影。

将这K 维向量表示为[]k w w w W ...,,21,

=。我们将样本点在这K 维向量投影后的结果表示为[]k y ,...,y ,y 21,有一下公式成立

x W x w T T i i ==y y , (16) 同两类的情况一样,仍然从类间散列度和类内散列度来考虑,度量)

(w J 。 其中i μ和w S 与上节的意义一样,wi S 是类别i 里的样本点相对于该类中心点i μ的散列程度。1B S 变成类别i 中心点相对于样本中心点μ的协方差矩阵,即类i 的散列程度。∑==c

i wi w S S 1,wi S 的计算公式不变,仍然类似于类内部样本点的协方差矩阵,

其中

∑∈--=

i

w x T

i

i

wi x x S )

)((μμ (17)

B S 需要变,原来度量的是两个均值点的散列情况,现在度量的是每类均值点相对于样本中心的散列情况。类似于将i u 看作样本点,μ是均值的协方差矩阵,如果某类里面的样本点较多,那么其权重稍大,权重用Ni/N 表示,但由于)(w J 对倍数不敏感,因此使用i N 。

∑==C

i T i i i B N S 1

)-)(-(μμμμ (18)

其中:

i

w x i x

i

N N

x N

μμ∑∑∈?=

=

11

(19)

上面讨论的都是在投影前的公式变化,但真正的)(w J 的分子分母都是在投影后计算的。下面我们看样本点投影后的公式改变:

这两个是第i 类样本点在某基向量上投影后的均值计算公式。 ∑∈

=

i

y i y N ω

μi

~

1

(20) ∑?=

y

y N

1~

μ

(21) 下面两个是在某基向量上投影后的~

w S 和~

B S

∑∑=∈=C

i w y T i i w i

y y S 1~

~

~

)-)(-(μμ (22)

∑==C

i T i i i B N S 1

~

~~~~

)-)(-(μμμμ (23)

综合各个投影向量(w )上的~

w S 和~

B S ,更新这两个参数,得到

W S W S w T w =~

(24) W S W S B T B =~

(25) 其中,W 是基向量矩阵,~w S 是投影后的各个类内部的散列矩阵之和,~

B S 是投影后各个类中心相对于全样本中心投影的散列矩阵之和。

回想我们上节的公式)(w J ,分子是两类中心距,分母是每个类自己的散列度。现在投影方向是多维了(好几条直线),分子需要做一些改变,我们不是求两两样本中心距之和,而是求每类中心相对于全样本中心的散列度之和。

然而,最后的J(w)的形式是

W

S W W S W S S w J w T

B T w

B

=

=

~

~

)( (26)

由于我们得到的分子分母都是散列矩阵,要将矩阵变成实数,需要取行列式。又因为行列式的值实际上是矩阵特征值的积,一个特征值可以表示在该特征向量上的发散程度。因此我们使用行列式来计算。

整个问题又回归为求J(w)的最大值了,我们固定分母为1,然后求导,得出最后结果

i w i B w S w S λ= (27) 与上节得出的结论一样

i i B w w S S λ=-1

w (28) 最后还归结到了求矩阵的特征值上来了。首先求出B S S 1

w

-的特征值,然后取前K 个特征向量组成W 矩阵即可。

由于B S 中的)(μμ-i 秩为1,因此B S 的秩至多为C (矩阵的秩小于等于各个相加矩阵的秩的和)。由于知道了前C-1个i μ后,最后一个c μ可以有前面的i μ来线性表示,因此B S 的秩至多为C-1。那么K 最大为C-1,即特征向量最多有C-1个。特征值大的对应的特征向量分割性能最好。

然而B S S 1

w

-不一定是对称阵,因此得到的K 个特征向量不一定正交,这也是与PCA 不同的地方[1]。

第三章 LDA 的改进算法

3.1问题的提出与解决办法

LDA 的基本思想是找到合适的向量,使得样本特征经过向量映射后获得最大的类间离散程度和最小的类内离散程度。但是,当样本数量小于样本特征维数时,样本的特征矩阵可能变成奇异矩阵,在这种情况下执行LDA 时会使计算时间复杂度变得非常大。

近年来,许多研究人员已经注意到小样本对LDA 的影响,并提出了不同的解决方法。一种解决方法是降低样本维度[2]。Goudail 等人通过计算每个样本中的25个局部自相关系数来降低样本特征的维度[3];Swets and Weng 等人通过PCA 方法来降低样本维度。另一种方法是通过线性算法来降低计算的复杂度。这就是我们下面要探讨的改进LDA 算法。

3.2传统LDA 的潜在问题

在进行线性决策分析之前,必须获得人脸特征,因此要通过形态学滤波器分离人脸,构建出人脸数据库[4]。通过此方法提取的人脸特征主要包括眼睛,鼻子和嘴三部分。人脸特征的生成主要通过像素聚类的方法实现。在进行像素聚类之前,必须将人脸图像转化成标准大小。通过K 均值聚类法将像素点聚为m 类,从而将I[N][P][P]的灰度特征矩阵转换为I[N][M]的特征矩阵,其中N 表示图像数量,P*P 表示图像的大小。

像素聚类的目的是降低特征的维度,提取图像的几何特征,并没有考虑类别之间的区分性,而真正区分各类别的是LDA 。它通过寻找投影向量,使得映射后的样本特征获得最小的类内离散程度和最大的类间离散程度。

假设训练集包含K 各类,每个类中包含M 个样本,LDA 方法要找的映射矩阵At ,使得:

~

m ~m

k

t

k X A X = (29) 其中,k

X m

表示从第K 类的第m 个样本中提取的n 维特征向量,~

m k

X 表示k X m

经过n*d 的特征矩阵A 映射后得到的向量。寻找矩阵A 的方法是通过fisher 准则:

q

S q q

S q F w T B T =)q ( (30)

其中,∑=--=?∈K

k T k

k

B n x x x x S q 1))((,,∑∑==--=K

k M

m T k

k m k

k m

w X X x X S 11))(( S b 和S w 分别代表类内离散的矩阵和类间离散度矩阵。其中

∑==M m k

m k

X M X 11,∑∑===K k M

m k m X KM X 111 (31)

此问题最终转换成了凸优化问题:

n

q q F q ?∈=)(max arg ~

(32)

通过将所有特征向量映射到q 上,使得样本获得最小的类内离散度和最大的

类间离散度。通过线性算法的求解,可得到q 是B S S 1

w

-的最大特征值对应的特征向量。

当样本数量小于样本特征维数时,S w 会变为奇异矩阵,在求解1

w -S 时会有较高

的时间复杂度,这就是小样本引发的问题。

为了解决小样本问题,Liu 等人提出了改进的fisher 准则函数[5]:

n n q q q F q F ?

∈?

∈=)(max arg )(max arg ^

(33)

下面介绍两个定理:

通过上述两个定理,可以将F(q)转换成F^(q)进行求解。传统的求解方法是寻找(S b +S w )-1*S b 的最大特征值对应的特征向量,但是在小样本的情况下会有较高是时间复杂度。一种改进的方法是计算计算S t (S t =S b +S w )的零空间,这样上式的分母趋于0,分子不为0,F^(q)趋于无穷大。这种方法有如下问题:1.判别向量集的正确性。2.算法的稳定性。3.奇异值问题。

3.3改进的LDA 算法

图1 改进LDA 算法示意图

假设人脸数据库包含K 个类别,每类中含有M 个样本,令k

X m 表示第k 类中第

m 个样本的特征向量。b S 和v S 分别表示类间和类内离散度,总的离散度v b t S S S +=。

通过1可知,我们要寻找向量q ,使得0q =q S W t ,此时)q (^F 取得最大值1。通过2可知,最佳投影向量q 是v S 零空间的线性组合。定理1可以保证任意q 包含于0V 并且0q b =q S t ,都可以使)q (^F 获得最优值,但无法保证0q b =q S t 取得最大

值。

通过定理2可知,样本的特征向量通过T QQ 变换后0~

v

=S ,使得)q (~F 获得最大值1。因此,我们要从中选择一个映射向量,使得类间离散度达到最大。基于这

种思想,我们可以采用主元分析(PCA)方法。PCA 的基本思想是寻找一个投影向量,使得样本特征经过投影后保留最多的原始信息。通过PCA 方法得到的投影向量是

~t S 的L 个最大特征值对应的特征向量),(T T QQ S QQ S S S S S ~t ~t ~

b ~v ~b ~t ==+=。

通过定理3可知,由PCA 方法找到的投影向量具有最优的线性区分特性。

算法流程图如下:

图2 LDA算法流程图

第四章 LDA 的改进算法

4.1标准化LDA 进行人脸识别

人脸识别在安全系统和人机交互等方面有着巨大的应用前景,当用统计方法解决人脸识别问题是,一再碰到的问题是维数问题,线性判别分析是其中较为常用的方法。Fisher 准则函数就是为了发现这样的投影方向,使得样本类间离散度和样本类内离散度的比值最大。

下面介绍一种利用LDA 进行人脸识别的例子:

采用的方法是将样本类间离散度投影到样本类内离散度的零空间,然后选择相对投影后的样本类间离散度的较大特征值向量作为变换矩阵。 样本类间离散度矩阵定义为:

∑=--=c

i T i i i u u u u P S 1b ))(( (34)

样本类间离散度矩阵定义为:

i c

i i S P S ∑==1w (35)

其中, ()()[]

i

T

i i C u x u x E S ∈--=x |i

(36)

Fisher 准则函数:max

W

S W

W

S W W J T

b T w

t w op max arg =)

( (37)

通过线新代数理论,我们知道opt W 就是满足如下等式的解

),...,2,1(w b m i W S W S i i ==λ (38) 传统LDA 对样本类间离散度的定义还有一点不足,该定义使得所有样本均值和各个类均值尽可能的分开,但却可能造成各个类均值相互接近,也就引起了相邻类的大量样本的重叠。考虑一个从d 维空间投影到一维空间的例子。图一画出了4个类,每个类一共有100个测试样本,其均值就是所有测试样本的中心。根据(1)定义的样本类间离散度,导出投影方向A ,但如果所有样本从二维空间投影到该方向,转化为1维空间,类别1,3的样本就会有较大的重叠。针对这个问题,我们重新定义样本类间离散度

T j i j i c i c

i j ij

j

i

u u u u w p p S ))(()(1

11

b --?

=∑

∑-=+= (39)

)()(ij j i T

j i u u u u --=? (40)

加权函数: 2ij

ij 1

)(?=

?ω (41) 图三所示的投影方向B 就是从式(5)、(6)、(7)推导出的新的投影方向。显然,在判别能力上该方向优于投影A ,特别是原来较为相近的三个类能够更好的分类。

图三 不同定义的样本类间离散度导出不同的投影方向

本文新提出的基于LDA 的方法-----标准化LDA 的基本不走如下:

步骤一:根据式(35)、(36)定义样本类内离散度; 步骤二:根据(38)、(39)、(40)定义样本类间离散度;

步骤三:保留样本类内离散度的零空间,因为它们包含了对判别最有帮助的信息)(,0w I V V V s V T T ==;

步骤四:将样本类间离散度投影到样本类内离散度的零空间,V s V s T

b b = 步骤五:特征分解投影之后的样本类间离散度,对解对应m 个较大特征值i λ的特征向量,Λ=U s U T b ,其中,Λ是对角矩阵,对角元素是按照降序排列的i λ

步骤六:最后的投影方向即LDA 降维转换矩阵为VU A =

由上述过程可知,Λ==A s A A s A T T b ,0w 因此,A s A T b 和A s A T w 的比值达到最大, 即我们的求解使得Fisher 准则函数取得了最大值。

我们在Olivetti2Oracle Research Lab (ORL )数据库上进行实验。ORL 数据库包括400 个人脸图像:40 个人每个人10 幅图像,其中包括姿态、光照和表情的差别。

不经过任何预处理过程,对每个人随机选取5 幅图像作为训练集,另外5 幅作

为测试集。我们与其他三种算法进行比较。算法1 是传统的PCA ,该算法利用所有样本的协方差矩阵决定最后的投影方向;算法2 是PCA + LDA,该算法首先利用PCA 降低维度,使得样本类内离散度矩阵不再是退化的。第三种算法是Yu 和Yang 提出的,该算法首先删去样本类间离散度矩阵的零空间,然后在非零空间里求对应样本类内离散度矩阵较小特征值的特征向量,并将此作为最后的投影方向。图四所示为识别率随维数变化的曲线图。

图四:识别率随维数变化曲线

图四显示出本文提出的标准化LDA 具有最好的识别率。不同于PCA + LDA ,该方法直到维数取到39 才达到最好的识别率,而本文算法在维数达到15 之后,就一直保持着非常高的识别率。这显示了本文算法的有效性。因为对一个具有较多类别的识别系统而言,标准化LDA 算法只需要取较少的维数就可以达到较好的性能。Yu 和Yang 的LDA 方法在维数等于20 的时候获得最大值,之后识别率开始降低,这是因为第一次降维移走样本类间离散度的零

空间之后,子空间维度仅为39 ,限制了进一步的判别分析。

另一个实验是识别率对不同数目的训练样本。根据图四所示实验结果,我们选取4 种算法各自的最好参数: PCA , PCA + LDA 和本文的标准化LDA都选取39 作为维数, Yu 和Yang 的LDA 算法选取20 为最后子空间的维度。固定维度参数,将每个类别的训练样本从2 变化到9 。图五所示为最后的实验结果比较。可以看到,不管训练集中有多少图像,标准化LDA 的算法都比其他的算法有更好的性能。

图五:识别率随训练样本数目变化曲线

4.2 线性判别分析在个人信用评估中的应用

伴随着我国商业银行个人信贷业务的不断开展,个人信用评估的重要作用日益加强。个人信用评估是一种建立数学模型并应用计算机技术对个人的信用信息进行统计、计算及量化分析的方法。经历了最初简单的判别方法到今天包括线性规划、分类树、神经网络k-近邻判别在内的诸多数量方法的过程,其中判别式分析是最先被才用呢并被国外商业银行广泛使用的方法。下面将介绍LDA如何在个人信用评估中发挥作用的。

表一:个人信用评估的指标体系及对应的变量

由于他们的分析是基于不同的数据资料进行的,因此表中的数据只能在同一行内进行比较而不能跨行比较,虽然这种分析的结果不能完全作为评判某种方法优劣的依据,但是从他们的研究结果中我们可以对这些方法的准确率有一个大致的判断,其中线性判别式方法的准确程度基本可以与其他方法持平。说明其还是具有适用性的。

表二:输出结果一览表

依据“5C ”原则,即个人特性、贷款数额、资产、能力和形势的基础上筛选出那些相关性较强并容易获取的的变量,建立本文的指标体系,具体如表二所示,以此作为进一步选择变量的基础。

表一体现了各变量的特点及函数关系,其中对一些初始的变量进行了处理,例如年龄变量1X ,我们由长期观察的数据得知其与还款的可能性可能成二次函数、正态分布、折现或直线关系。经过对各种函数拟合结果的验证,我们发现二次函数的拟合优度明显增大,于是得出:)6016(x 21

≤≤+=x x x

对于那些难以获取和数据分布不理想的变量,例如有无信用不良记录、是否抵押遗产等, 在指标体系设定中进行了剔除, 因此没有体现在表中。 线性回归模型的建立和应用:

上述的指标体系表明, 是否获得贷款Y 与i x 所表示的指标变量之间存在一定的依赖关系, 据此建立多元回归模型, 表示为:

εββββ+++++=151522110...X X X Y (42) 这里采用某商业银行住房抵押贷款的资料, 选取251个样本, 使用SPSS 软件采用显著性逐级检验分析的方法计算和输出结果。输出结果表明7X 、9X 、12X 、

1X 和4X 为通过显著性检验的指标。通过计算, 可以得出最后实验回归模型方程为:129741236.0136.0296.02067.704682.1112.2X X X X E X E Y +------=∧

(43)

通过计算结果和回归方程我们可以看出, 个人是否获得贷款Y 与年龄1X 、工作稳定情况4X 、受教育程度价7X 、本人月收人9X 、是否有其他固定资产12X 联系相对较大, 而与性别、婚否、职位、工作时间等联系相对很小, 基本符合我国国情和实际情况。

相关主题