Fisher大间距线性分类器

Fisher大间距线性分类器 Fisher大间距线性分类器 第l2卷第l2期 2007年l2月 中国图象图形 JournalofImageandGraphics Vo1.12,No.12 Dec.,2007 Fisher大间距线性分类器 陈才扣".杨静宇" (南京理工大学计算机科学与技术学院,南京210094)(扬州大学信息学院,扬州225009) 摘要作为一种着名的特征抽取方法,Fisher线性鉴别分析的基本思想是选择使得Fisher准则函数达到最大值 的向量(称为最优鉴别向量)作为最优投影方向,以便使得高维输入空间中的模式样本在该向量投影后,在类问散 度达到最大的同时,类内散度最小.大间距线性分类器是寻找一个最优投影矢量(最优分隔超平面的法向量),它 可使得投影后的两类样本之间的分类间距(Margin)最大.为了获得更佳的识别效果,结合Fisher线性鉴别分析和 大间距分类器的优点,提出了一种新的线性投影分类算法——Fisher大间距线性分类器.该分类器的主要思想就 是寻找最优投影矢量,.,(最优超平面的法向量),使得高维输入空间中的样本模式在,.,"上投影后,在使类问间 距达到最大的同时,使类内离散度尽可能地小.并从理论上讨论了与其他线性分类器的联系.在ORL人脸库和 FERET人脸数据库上的实验结果明,该线性投影分类算法的识别率优于其他分类器. 关键词大间距分类器支持向量机Fisher线性鉴别分析人脸识别 中图法分类号:TP391.41文献标识码:A文章编号:1006—8961(2007)l2—2l43—05 FisherLargeMarginLinearClassifier CHENCai.kou,.YANGJing.yu '(CollegeofComputerScienceandTechnology,NanjingUniversityofScienceandTechnology,Nanjing210094) (InformationEngineeringCollege,YangzhouUniversity,Yangzhou225009) AbstractFisherlineardiscriminantanalysis(LDA),awell— knownfeatureextractionmethod,searchesfortheprojection axesonwhichthedatasamplesfromdifferentclassesarefarfromeachotherwhilerequiringdatasamplesofthesameclass tobeclosetoeachother.Largemarginclassifier(LMC),alsoreferredaslinearsuppo~vectormachine,defindsaproject directionontowhichtwoclassesofthesamplesprojectedreachmaximalmargin.Withcombinationofadvantagesofboth LDAandLMC,thepaperdevelopsanovellinearprojectionclassficationalgorithm,calledFisherlargemarginlinear classifier.Theunderlyingideaisthatanoptimaldiscrimiantvectorwisfoundalongwhichthesamplesofhigh dimensionalinputspaceareprojectedsuchthatthemarginismaximizedwhilewithin— classscatteriskeptassmallas possible.Inaddition,relationstOotherclassifiersareexploredintheoryinthispaper.Finally,theproposedmethodis testedOnORLfacedatabaseandFERETfacedatabase.Theexperimentalresultsshowthattheproposedclassifier outperformsotherlinearclassifiers. Keywordslargemarginclassifier(LMC),supportvectormachines(SVM),Fisherlineardiscriminantanalysis, facerecognition 引言 维度缩减是模式识别中最基本的问题之一. Fisher线性鉴别分析(1ineardiscriminantanalysis, LDA)…是维度缩减的最为经典和广泛使用的方 法.它的主要思想是选择一个使得与分类相关的准 则——Fisher准则函数达到最大值的矢量作为最优 基金项目:国家自然科学基金项目(60472060,60632050);江苏省高校自然科学基金项目(05KJB520152);江苏省博士后科研资助计划项 目(苏人通[2005]249) 收稿日期:2005—12—14;改回日期:2007—02—09 第一作者简介:陈才扣(1967一),男.博士后,副教授,硕士生导师.主要研究方向为模式识别理论与应用,生物特征识别.E—mail: yzcck@126.corn 中国图象图形第l2卷 鉴别矢量(投影轴).其物理意义是,高维输入空间 中的模式样本在该鉴别矢量上投影后,可使同一类 的模式样本相互集中,不同类的样本相互分离,类间 散布程度和类内散布程度之比达到最大.但基于 Fisher鉴别准则的维度缩减方法面临以下3个主要 问题:一是类间散布矩阵常常为奇异矩阵;二是模式 样本要求假设服从一定的正态分布,否则得到的是 次优解;三是不能根据投影结果直接进行分类,因此 最后通常需要利用最近邻或最小距离分类器进行 分类. 最近,大间距分类器(1argemarginclassifier, LMC).正成为机器学习和模式识别领域的一个 研究热点.作为大间距分类器中的最着名的算 法——支持向量机(supportvectormachines,SVM), 以其良好的性能正受到人们越来越多的关注.大间 距分类器的基本思想是寻找一个最优投影矢量(最 优分隔超平面的法向量),使得投影后的两类样本 之间分类间距最大,它是根据Vapnik提出的结构风 险最小化(structureriskminimization)原理,其目的 是尽量提高学习机的推广能力.但现有的大间距分 类器在强调分类间距(margin)最大的同时,没有像 Fisher鉴别分析那样,同时考虑类内散度尽可能小 的问题.为此,结合上述两类算法的优点,本文提出 一 种新的大间距分类器算法——Fisher大间距分类 器(FLMC),该算法的一个突出优点是借助于现有 的支持向量机算法可直接进行计算,而不需要设计 新的求解算法.在ORL和FERET人脸数据库上的 测试结果表明,本文的算法都优于现有的大间距分 类器和Fisherfaces算法. 2Fisher大间距分类器 2.1大间距分类器 设线性可分样本集为(X,Y.),i=1,…,m,x? R,Y?{+1,一1}是类别标号,类别为"+1"和 " 一 1"的训练样本的个数分别为m.和m,并且m.+ m=m.Vapnik指出,具有最大问隔的分类超平面 能够满足结构风险最小化原理.求解最大间隔的最 优分类超平面的问题可以表示为如下的约束优化问 题,即 11 .,(..,)..,I1寺w… S.t.Y(WX+b)一1?0,i=1,2,…,m 定义如下的Lagrange函数: L(w,6,)=?ww一?Oli[),.(w+6)一1] (2) 对上式分别对W和b求偏导数,并令它们等于0,就 可把原问题转化为如下的对偶问题: maxQ(tr)=?.一??Oli),.(..) (3) s.t.?Yi.=0,i?0,i=1,…,m 若为最优解,则最优分类器为 X)=sgn{(W?X)+b"} =sgn {砉.)(4) 对于非线性可分的情况,大间距分类器可表示 为如下的约束优化问题: min(..,),=?l+C?. S.t.Y.(WX.+b)一1+.?0,i:1,2,…,m (5) 其中,C为某个指定的常数,其用于控制错分样本的 比例与算法复杂度之间的折衷. 2.2Fisher大间距分类器 ,根据Fisher鉴别准则函数的思想,本文对现有 的支持向量机的目标函数进行了如下的修正,使得 在最优解向量W(最优超平面的法向量)上投影 后,在保持最大的类间间距的同时,使得类内散度尽 可能地小. 可将式(1)修正为如下的形式: minJM(..,)?(+..,Sw..,)(6) S.t.Y.(WX+b)?1Vi 2JvI 其中,S=??(x一ni)(x一m)表示类内散 1 Jvt 布矩阵,mi表示模式样本均值.参数 为一正实数,用来平衡最大化类间间距和最小化类 内散度两个不同的目标.值越大,意味着最小化 类内散度越重要(相对于最大化类间散度而言),而 当=0时,式(6)就是普通的最大间距分类器.该 FLMC(Fisherlargemarginclassifier)分类器选择使 得J(W)达到最大值的方向作为最优投影方向. 显然,FLMC分类器所确定的最优投影方向是以另 第12期陈才扣等:Fisher大间距线性分类器 外一种方式,在使得投影后的类间散度达到最大的 同时,类内散度达到最小. 式(5)是一个凸二次优化问题,为了便于计算, 可将式(6)等价变换为 1一 rain寺'''(+'7w)'''… s.t.),.('.,+6)?1Vi 其中,I表示单位矩阵. 由于I+'7是一个对称矩阵,因此必存在正交 矩阵P=(p一,p),使得 P一(I+'7)P=P(I+'7)P=A(8) 其中,A=diag(A1,A2,…,A);pl,…,p为I+'7 的标准正交的特征向量,A,A,…,A为所对应的 特征值,且满足A,>0,J=1,…,n. I+'7也可写成 I+'7=PAVVPT=PAV(PAV)T(9) 将式(9)代人式(7),则有 wT/lPTw=wT(V)(V)Tw=IlaVPT'.,ll (10) 令'.,=AP'.,,则式(7)可改写成 1 rain'.,II(11, s.t.),.('.,''.+6)?1Vi 其中,''.'=(AP). 因此,求解式(11)的最优解可以使用传统的 SVM算法,下面给出计算FLMC的步骤: (1)对I+'7进行特征分解,即 I+'7=尸/lP; (2)把所有的训练样本.变换为'', ''=(AP); (3)利用现有的支持向量机算法求解式(10) 的二次规划问题来得到解'.,和6; (4)计算式(6)的解:'.,=(AP),'.,,,6=6. 由于非线性大间距分类器的解与线性大间距分 类器几乎完全相同,因此,对于非线性可分问题的 FLMC也与线性可分情况的FLMC几乎完全相同. 3FLMC分类器与其他分类器的关系 本节将讨论大间距Fisher分类器与传统的支持 向量机以及Fisher线性鉴别分析之间的关系. 显然,根据式(6)确定的最优投影方向'.,与 参数'7的取值有关.下面考察当参数'7趋向无穷 大时以及参数'7取值为0时的两种特殊情况. 3.1参数趋向无穷大时的FLMC分类器 定理1若为奇异矩阵,则当参数'7趋向无 穷大时,由式(6)确定的最优投影方向等价于由 式(12)确定的最优投影方向. 1 rainJ('.,)=?Ij s.t.),('.,j+6)?1Vi(12) '.,S'.,=0 证明设A为矩阵(I+'7?S)的某个特征值, p为对应的单位特征向量.因为奇异矩阵,故存 在单位向量p.,使得p.=0. 对于任意的正实数'7,由A和p的含义知, (I+'7?)p=Ap(13) 可把式(13)改写为 pp=(A—p)?A(14) '7 另外,由于为半正定矩阵,因而有 pp?0(15) 综合式(14)与式(15)不难得出 limpSp=0(16) 因此,当'7趋向于无穷大时,式(6)的解'.,一定 位于的零空间内.故式(12)确定的最优投影轴 即为式(6)确定的最优投影轴的极限情况. 定理2由式(12)确定的最优投影方向等价于 由式(17)确定的最优投影方向.或者说,若为 奇异矩阵,则当参数'7趋向无穷大时,由式(6)确定 的最优投影方向等价于由式(17)确定的最优投影 方向 max'.,Sh'., 『'.,S'.,=0(17) s?t.{【II=1 证明由类内散布矩阵的含义不难知道,当 为奇异矩阵时,训练样本是完全线性可分的.因 为奇异矩阵,故存在单位向量p,使得pp=0,即 pp=p?(一m)(一m)E?i = ?(p一pmi)0,i=1,2(18)E?I 即 V?,p=pm,i=1,2(19) 也就是说,在的零空间内总可以找到一个投 影方向,使得样本沿该方向投影后,同类样本对应着 中国图象图形第12卷 投影轴上的同一个点,异类样本对应着投影轴上不 同的点.此时,投影后两类样本之间的类间间距 就等于[WT(m-一mz)] 而 WSbW=W(m1一m2)(ml—m2)w = (Wm1一wm2)(20) 因此,最小化?II'.,II就等价于最大化'.,'.,. 3.2参数叩取值为0时的FLMC分类器 当参数取值为0时,FLMC分类器就退化为 式(1)的传统大间距分类器.由此可见,传统的支 持向量机可以看成FLMC分类器的一种特殊形式, 或者说,FLMC是传统支持向量机的推广. 4实验结果与分析 为验证本文分类器的识别效果,采用ORL和 FERET人脸图像数据库,对不同参数值下的 FLMC分类器,大间距分类器(LMC,即线性SVMs), 标准SVMs以及Fisher鉴别分析(Fisherfaces)的分 类效果进行了实验比较. ORL人脸图像数据库由40人,每人10幅92× 112大小的图像所组成.实验时,取每个人脸的前5 幅图像作为训练样本,后5幅图像作为测试样本,因 而训练样本和测试样本数均为200.FERET人脸图 像库由100个人,每人7幅分辨率为80×80pixels 的灰度图像组成.对于ORL人脸图像库,选取每个 人的前5幅图像作为训练样本,后5幅图像作为测 试样本,因而训练样本和测试样本数均为480.在 FERET人脸图像库上,实验一共进行10次,每次随 机选取每个人的3幅图像作为训练样本,其余4幅 图像作为测试样本,训练样本和测试样本数分别为 300和400. FLMC分类器,大间距分类器和标准SVMs本质 上都是两类分类器,在用于多类分类问题时,需要将 原问题分解为若干个两类分类问题.常见的分解方 式有以下3种:一对一(one—VS—one),一对多(one—VS— rest)和有向树(directedacyclicgraph,DAG).本 实验使用一对一分解方式.除了Fisherfaces方法 外,其他分类器都是直接基于原始图像进行分类的. 表1列出了大间距分类器,标准SVMs, Fisherfaces以及不同参数值下的FLMC分类器在 ORL数据集上的正确识别率,其中,Fisherfaces的识 别结果引自文献[6]中的表1,其他识别结果都是在 " 一 对一"分解方式下获得的.此外,大间距分类器 中的参数c的取值为1,标准SVMs分类器中是使用 高斯核函数,其参数=1.5×10一. 表1各个分类器在不同分辨率ORL图像下的 最优识别率比较 Tab.1Optimalrecognitionratesunderdifferent resolutionsusingseveralclassifiers 各个分类器在不同分辨率下的识别率(%) 分类器—— ll2×9256×4628×23l4×l27×6 从表1中参数在各种取值下的FLMC分类器 的识别结果不难看出,若取较小的值,则FLMC分 类器就获得较高的识别结果,当:0.1时,识别结 果最优,并且优于Fisher线性鉴别分析(Fisherfaces) 和传统的大间距分类器(线性支持向量机);同时, 随着取值的增大,识别性能逐渐下降,其识别精 度反而不如传统的大间距分类器.这个实验结果验 证了参数在FLMC分类器中的作用.但是FLMC 分类器的识别性能不如标准SVMs,其原因是由于人 脸图像的特征分布通常是非线性的,本文方法以及 大间距分类器只能获得线性分类面,而标准SVMs 则采用了非线性的高斯核函数,因而其最终得到的 分类面是非线性的,这正是非线性方法的优势所在. 此外,随着图像分辨率的降低(112×92,56×46,28× 23),FLMC的识别性能仅略有下降,但在7×6大小的 马赛克图像上的正确识别率却突然下降到85.0%, 大间距分类器在同样的图像上的识别率也只有 82.5%.这一方面说明了FLMC分类器和大间距分 类器对较低分辨率的图像不具有鲁棒性,另一方面 表明FLMC本质上仍然是大间距分类器(当取很 小的值),因此,它俩的实验结果的变化规律具有很 大的相似性也就不足为奇. 第l2期陈才扣等:Fisher大间距线性分类器2l47 表2列出了Fisherfaces,大间距分类器,标准 SVMs及FLMC分类器在FERET数据集上执行 10次鉴别分类后的正确识别率.其中,Fisherfaces 方法中采用最近邻分类来对抽取后的特征进行分 类.线性SVM参数c的取值为1,标准SVMs分类 器中是使用高斯核函数,其参数=1.5×10一. 表2Fisherfaces,LMC,SVMs以及FLMC在 FERET数据集上的识别率比较 Tab.2RecognitionratesintheFERETfacedatabse usingFisherfaces,LMC,SVMsandFLMC 表2中的数据表明,FLMC的正确识别率均分 别优于Fisherfaces和LMC,但低于SVMs,这进一步 验证了本文方法的有效性. 5结论 本文提出的Fisher大间距分类器不仅集中了 Fisher鉴别分析和大间距分类器的优点,而且具有 更强的物理意义.在ORL和FERET人脸数据库上 的实验结果表明,FLMC分类器在识别性能优于大 间距分类器,也明显高于Fisher线性鉴别分析.由 于其固有的线性特性,致使其识别性能略低于非线 性支持向量机. 2 3 4 5 6 7 参考文献(References) FisherRA.Theuseofmultiplemeasurementsintaxonomicproblems [J].AnnalsofEugenics,1936,7(partlI):179—188. VapnikV.TheNatureofStatisticalLearningTheory[M].New York:Springer—Verlag,1995. FreundYoav,SchapireRE.Largemarginclassificationusingthe perceptronalgorithm[J].MachineLearning,1999,37(3):277— 296. HuangKai—zhu,YangHai—qin,KingIrwin.Learninglargemargin classifierslocallyandglobally[A].In:ProceedingsoftheTwenty— firstInternationalConferenceonMachineLearning[C],Banff, Alberta,Canada,2004,69:268—275. BianZhaoqi,ZhangXue—gong.PatternRecognition[M].Beijing: TsinshuaUniversityPress,2000.[边肇祺,张学工.模式识别 [M].北京:清华大学出版社,2000.] PhillipsPJ,MoonH,RizviSA,eta1.TheFERETevaluation methodologyforfacerecognitionalgorithms[J].IEEETransactionson PatternAnalysisandMachineIntelligence,2000,22(10):1090一 ll04. HsuC,LinC.Acomparisonofmethodsformuhiclasssupportvector machines[J].IEEETransactionsonNeuralNetworks,2002, 13(2):415—425.