一种核Fisher判别分析的快速算法

一种核Fisher判别分析的快速算法 一种核Fisher判别分析的快速算法 第29卷第7期 2007年7月 电子与信息 JournalofElectronics&InformationTechnology V01.29No.7 Ju1.2007 一 种核Fisher判别分析的快速算法 赵峰张军英?梁军利 (西安电子科技大学计算机学院西安710071) (西安电子科技大学雷达信号处理国家重点实验室西安710071) (济南大学理学院济南250012) (中国科学院声学研究所北京100080) 摘要:针对训练样本多时核Fisher判别分析(KFDA1的计算代价大,特征提取速度慢问 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 ,本文提出一种KFDA 的快速算法.该算法首先基于线性相关性理论,设计出一种优化方法,快速寻找训练样本在特征空间所张成的子空 间的一组基;然后用这组基线性 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 示最佳投影方向,结合特征空间中的Fisher准则函数,推导出求解最佳投影方 向的新公式,其求解过程只需对一个阶数等于基的个数的矩阵特征值分解,同时提取某样本特征时只需计算该样本 与这组基之间的核函数.基于多个数据集的实验验证了该算法的有效性. 关键词:核Fisher判别分析;最佳投影方向;核函数 中图分类号:TP391.4文献标识码:A'文章编号:1009—5896f2007)07_1731—04 AFastAlgorithm.aboutKernelFisherDiscriminantAnalysis ZhaoFeng??ZhangJun-ying??LiangJun—li? (SchoolComputerScienceandEngineering,XidianUniversity,Xi'an710071,China) (NationalKeyLabofRadarSignalProcessing,XidianUniversity,Xi'an710071,China) (SchoolofScience,JinanUniversity,Jinan250012,China) (InstituteofAcoustics,ChineseAcademyofSciences,Beijing100080,China) Abstract:ThestandardKernelFisherDiscriminantAnalysis(KFDA)maysufferfromthelargecomputation complexityandtheslowspeedoffeatureextractionforthecaseoflargenumberoftrainingsamples.Totacklethese problems.afastalgorithmofKFDAispresented.Thealgorithmfirstlyproposesanoptimizedalgorithmbasedon thetheoryoflinearcorrelation,whichfindsoutabasisofthesub— spacespannedbythetrainingsamplesmapped ontothefeaturespaceandwhichavoidstheoperationofmatrixinversion;Thenusingthelinearcombinationof thebasistoexpresstheoptimalprojectionvectors,andcombiningwithFishercriterioninthefeaturespace,a novelcriterionforthecomputationoftheoptimalprojectionvectorsispresented,whichonlyneedstocalculatethe eigenvalueofamatrixwhichsizeisthesameasthenumberofthebasis.Inaddition,thefeatureextractionforone sampleonlyneedstocalculatethekernelfunctionsbetweenthebasisandthesample.TheexperimentMresults usingdifferentdatasetsdemonstratethevalidityofthepresentedalgorithm. Keywords:KernelFisherDiscriminantAnalysis(KFDA);Optimalprojectionvector;Kernelfunction 1引言 核Fisher判别分析(KFDA1的基本思想是经过非线性映 射将输入数据映射到一个高维特征空间,在特征空间中进行 Fisher线性判别分析,隐含地实现输入空间的非线性判别.由 于KFDA能有效提取非线性判别特征,因而成为模式识别与 机器学习等领域的研究热点【卜引. 在KFDA实现过程中,需要求解KKb的特征值(其中 ,麟表示核类内矩阵与核类间矩阵,它们是mxm矩阵, 2006-07-04收到,200612-06改回 国家自然科学基金(60574039,60371044)和国家部级基金资助课题 m表示训练样本数),其计算复杂度是O(m.);而且所有训 练样本都要参与最佳投影方向的表达.m大时,KFDA面临 计算复杂度大以及特征提取速度慢问题.文献f6,71从几何的 角度,选择少量"显着"训练样本近似表示f表示最佳 投影方向1的方法,解决上述问题.但其为近似算法,存在理 论意义上的不确定性,而且训练数据的筛选过程,计算代价 也比较大. 本文首先基于向量组的线性相关性的有关理论,推导出 一 种自适应的优化算法,寻找训练样本在特征空间中所张成 的子空间的一组基,该算法避开了矩阵求逆运算,加速了子 空间基的选取.然后将表达成这组基的线性组合,并结合 1732电子与信息第29卷 特征空间中的Fisher准则函数,推导出一个用来确定tt,的 新公式,使得KFDA求解中只需特征值分解一个阶数等于基 的个数的矩阵,计算复杂度是O(r.)(其中r表示基的个数); 同时由于线性表示tt,的这组基的个数r大大少于训练样本 总数,所以对某样本提取判别特征时只需计算该样本与这组 基间核函数,节省特征提取时间. 2KFDA描述 设X={q,,…,)表示训练样本集,共有m个样本, 其中(=l,2,…,m)是一个n维列向量,分别属于一个特定 模式类,共有C类.第J类的样本子集记为蜀(J=l,2, … ,C),样本数记为m,.KFDA通过一个非线性变化妒, 将输入空间的所有样本影射到一个高维特征空间F中,即 :?XcR"一()?F,其中称()为样本所对应 的核样本,在F上进行线性Fisher判别分析.此时Fisher 准则函数的表达形式为 )=舞(1) 其中tt,?F,,是F中相应类间散布矩阵和类内散布 矩阵,即 =— c(c L - 1)i=1i=1 (.一uj)(u~-uj) 1 备c1(())(()) 札 1 … E 置 根据再生核理论,最佳投影向量tt,司表不为 tt,?Q;()(3) 将式(3)代入式(1),并在运算中用核函数七(,)代替 F空间~(fii)与~(fij)的内积,即,J=k(fi.,)=<(), (,)>,则式(1)变为 J(Q)=鬈(4)aAa 其中 a(Q1,Q2,,Qm)T = 1c(一)(一) 1 备c1(一)(一M2) = 击(c,轰七c-.,七c] = (k(fi,fi),七(,fi),…,七(,)) (5) 本文称式(4)为核Fisher准则函数.由广义Rayleigh商 的性质【8l,式(4)的一组最优解可取j的d个较大特征 值所对应的特征向量,,…,(其中:(m…, )),则一组最佳投影方向为Wi?()0=l, J=I 2,…,d).核样本()在这些方向上作投影(见式(6)),投影 坐标便是的判别特征.其物理意义是投影坐标所对应点的 总体类内距较小,类间距较大. ()=T():七(,)(6) j=l 3子空间基的确定 实际上,训练样本对应的核样本(z)在F中所张成的 子空间{()}的维数等于核矩阵K=(,)压的秩r.一 般情况下有r<<m.下面的问题是如何寻找子空间() 的一组基.文献f6,71采用一种迭代算法选择少量样本,其对 应的核样本近似表达这组基.事实上,从线性代数的有关理 论考虑,f()}的一组基是可以找到的,无须近似表达.下 面给出寻找子空间{()基的理论推导. 定理l设?%2,…,%(1sm)表示s个训练样 本,~(fib),~(fib.),…,~(fib)为其对应的特征样本,对应的 核矩阵记为=(k(fib.,%,))1({1.则~(fib1),~(fib2),…, ()线性无关{=}det(K~)?0. 证明令B=[~(fib1),(62),…,(%)】,则=BB, 故rank(B)=rank(K).又(%1),(2),…,(%,)线性无 关{=}rank(B)=s,即rank(Ks)=s,即det()?0. 证毕 定理2设%1,%2,…,%(1sm)表示s个训练样 本,~(fib),~(fib.),…,~(fib)为其对应的核样本且线性无关. 为任意一个训练样本,核样本为().则(%),(锄.),…, (6),()线性无关{=}—jTn-?0.其中= k(fi,),K=(k(fib1,fi),k(fib2,fi),…,k(fib,)),Ks=(k(fib{, ))1,压s, 由定理1以及行列式的性质易证定理2成立.根据上述 定理,采用一种自适应的迭代算法来寻求f()'的一组基. 基本思想是假设利用t(1tsm)个样本{1c_,完成了训 练,得到子空间()}{_1的一组基~(fib),~(fib.),…, (6).对于新的样本,依据定理2判定()与~(fib1). ~(fib2),…,~(fib)是否线性无关.如果无关,则令~(fibfs+11)= (),构成一个新的线性无关组(%1),(%2),…,(), ~(fib11).当遍历所有训练样本时,所求的线性无关组 ~(fib1),~(fib2),…,~(fib)即为子空间{()}的一组基. 利用定理2进行无关性判别时,存在对一个s阶矩阵 K的求逆运算.随着迭代算法的进行,s可能逐渐增大, 求逆运算的计算量是相当大的.针对这个问题,本文提出一 种迭代算法,避免了求逆运算,降低了计算复杂度. 定理3设线性无关组(61),~(fib2),…,~(fib)对应的核 矩阵为K,(61),(62),…,~(fib1,)对应的核矩阵为 _l_一1,方便起见,令V=(k(fib1,fib),k(fi6),…, 第7期赵峰等:一种核Fisher判别分析的快速算法1733 k(xbl1)%)),A=七(‰,Xb),D=,,则 一 由逆矩阵的定义易证定理3成立.由定理3,对s阶矩 阵的求逆运算转化为对s一1阶矩阵求逆,依次下去,求 逆运算变为乘法运算.结合定理2,便可很方便地寻求子空 间{()}的一组基妒(%.),妒(%.),…,(‰).具体算法步骤如 下: 步骤1初始化:在训练样本集X:{研,2,…,‰}任选 一 样本,满足七(,)?0令S:{},H:伽),G=1/ ((,)),=1. 步骤2如果t:m,则输出日,终止程序.否则,下 一 步. 步骤3在集合=X—S中选择一个样本,令S: U{},t:t+1;并验证式(8)成否成立 一 KTGK=0(8) 其中.?H,(j).=k(i,),=七(,). 步骤4如果式(8)成立,返回步骤2;否则令 H=HUf茁}, . 1『(一KTGK,)G+GTG—Gj1GI一 TG1f' 返回步骤2. 程序终止时,集合日中的向量所对应的核样本即为子 空间{()}的一组基. 4核Fisher判别分析的快速算法 假定通过上述算法获得一组基(%),(%.),…, 妒(%),则最佳投影向量可表达为 r W?.(%)(9) 将式(9)代入式(1)并整理得 = 盘(10) 具甲 = (,…,) = 1cc(t一砑,)(.一,) = ?(一.)(一) 丽t=去(轰…,善z)】T : ((%,z),(z.,z),…,(%,)) (11) 由广义Rayleigh商的性质[8】,式(10)的最优解可取r×r 矩阵:的较大特征值对应的特征向量,其计算复杂度 仅为O(r0).相比KFDA求解矩阵Kb的特征值,计算 量降低.特别m较大时,优势更加明显.设1,72,…,为 式(10)的一组最优解,其中=(7…,?).根据式 (10),任意样本所对应的核样本在W.上的投影为 一 P()=()=?7(,)(12)J:1 其中.=?::17().样本茁的判别特征为(), (i=1,2,…,d).称本节算法为核Fisher判别分析的快速算法 (FastalgorithmaboutKernelFisherDiscriminantAnalysis, FKFDA). 5实验分析 5.1实验数据的描述 为了验证FKFDA的性能,本文从不同角度选取了3组 数据进行实验,并同KFDA进行比较.第一组数据是二维仿 真数据(记为simulateddata),第一类数据的产生方式为 X:{(1.,1.)},其中:1,2,…,400,z1.,1.均服从方差 dr=0.5均值=0的正态分布;第二类的产生方式为 = {(z2,Y2)},其中=1,2,…,400,X2i=cos(C),Y2= sin(0i).,Oi分别服从正态分布一?(1.5,0.2),Oi一?(不 /4,0.5).其空间分布图见图1(a).第二组数据是分类实验 中常用的四维Iris数据.该数据是提取3种不同类别花瓣的 特征作为特征向量.共含150个样本,分三类,每类50个 样本.每个样本4维.第三组数据采用B一52,歼一6和歼一7 三种飞机的缩比模型微波暗室转台数据f记为Dark-room data).目标的方位角变化范围为0.一155.,俯仰角恒为5., 平均方位角采样间隔为0.43..该数据是101维的,每类选 取300个数据用于实验. 2 1 O - 1 — 202-202-202 0xZ (a)原始数据(b)KFDA(c)FKFDA 的识别曲线的识别曲线 图1KFDA与FKFDA对simulateddata的识别曲线图 5.2实验结果分析 实验中,测试数据采用等间隔方式从全部实验数据中抽 取,训练数据从剩余数据中等间隔选取.具体选取情况见表 1,如表1的第3行,测试样本数为2×100,表示每类抽取 100个用于测试,训练样本数为2×200,表示在测试样本抽 取后的剩余样本中,每类选取200个用于训练,其他行的意 义类似.实验中采用高斯核七(,Y)=exp(一一!,/.)作 为核函数,参数是经验值.判别特征提取后,采用最小距 离法进行识别.另外,在确定子空间的基时,考虑到计算误 差的客观存在,我们把式(8)替换为一jTG?,,本文 1734电子与信息第29卷 实验取E=0.1.图1描绘的是当训练样本取400时,两种 方法对simulateddata的分类曲线.表1列出了两种方法用 于不同数据集的各项指标比较.表1中识别速度比是指识别 相同的测试样本,KFDA与FKFDA所花费的时间比.显然 比值越大,说明FKFDA相比于KFDA,特征提取的速度越 快. 从表1以及图l(b),1(c)可看出,FKFDA相比于KFDA, 它们的识别率几乎一致f小的差别主要是由于计算误差引起 的),说明FKFDA与KFDA提取的判别特征基本一样.从 基的个数,即训练样本在特征空间中所张成的子空间的维数 来看,数目远远小于训练样本数,原因在于特征空间中,核 样本间存在很强的相关关系.特别是随着训练样本的增多, 子空间的维数增加并不明显,说明这种相关关系更强.反映 到特征提取速度上,FKFDA具有明显的优势,特别是训练 样本越多,优势越明显,这与训练样本在特征空间中所张成 的子空间的维数的变化趋势是一致的. 6结束语 基于子空间f()}的一组基,提出了一种KFDA的快 速算法一FKFDA.相比于KFDA,由于快速算法通过对训 练样本的筛选,找到训练样本对应的核样本()在F中所 张成的子空间f()}的一组基,将最佳投影方向由这组基 线性表示,使得KFDA实现过程中需要进行特征值分解的矩 阵的阶数由m(训练样本数)降低到r(子空间{()}的维 数),节省了存储空间,加快了特征提取的速度.同时,设计 出一种优化的迭代算法来寻求子空间{())的一组基,该 算法将求逆运算转化为乘法运算,计算量较小. 参考文献 [1】MikaS,RatschG,andJasonG.Fisherdiscriminantanalysis withkernels.Proc.ofNeuralNetworksSignalProcessing IEEE,Madison,wI,USA,1999:41—48. 【2】BaudatGandAnouarF.Generalizeddiscriminantanalysis usingakernelapproach.NeuralComputation,2000,12(1O): 2385—2404. f3]TristromC.Twovariationsonfisher'Slineardiscriminantfor patterrecognition.IEEETrans.onPatternAnalysisand MachineIntel~gence,2002,24(2):268—273. 【4】YangJ,FrangiAF,andYangJY.Anewkernelfisher discriminantalgorithmwithapplicationtofacerecognition. NeuralComputation,2004,56(4):415—421. 【5】LiangZZHandShiPF.Anefficientandeffectivemethodto solvekernelfisherdiscriminantanalysis.NeuralComputation, 2004,61(1):485—493. 【6】LiuQHandLuHQ.ImprovingkernelFisherdiscriminant analysisforfacerecognition.IEEETrans.onCircuitsand SystemsforVideoTechnology,2004,14(1):42—49. f71BaudatGandAnouarF.Kernel-basedmethodsandfunction approximation.ProceedingsoftheInternationalJoint ConferenceonNeuralNetworks,Washington,DC,2001: 1244—1249. [8】BianZHQandZhangXG.MatrixTheory.2ndedition, Xi'an:NorthwesternploytechnicaluniversityPress,2004: 262—288. 赵峰 张军英 梁军利 男,1974年生,博士生,研究方向为雷达目标识别,智 能信息处理等. 女,1961年生,博士,教授,博士生导师,目前主要从 事人工神经网络,智能信息处理,图像处理,分子成像, 计算生物信息学,模式识别,优化等方面的研究工作, 已发表学术论文80余篇. 男,1978年生,博士生,研究方向为阵列信号处理,自 适应滤波等.