（计算数学专业论文）高维数据判别分析问题的若干研究.pdf

摘要 在模式识别，机器学习，数据挖掘等研究领域里面，我们往往需要通过降维 的手段从高维数据中提取出能代表数据特性的最优特征，去除冗余的部分，来 提高判别未知数据类别的正确率。 对于分类问题，一种常用的手段是通过一个投影矩阵作用到原始数据，将 原始数据投影到低维空间以形成新的低维数据。我们的目标是找到最优的投影 矩阵，使得在低维空间中，不同类之间的数据点尽可能分散，而类内数据点尽可 能靠拢。这样就能提高数据分类的正确率，而所求得到的投影矩阵就是保留数 据关于类别信息的最优特征矩阵。 本文首先介绍了目前已有的提取高维数据判别分析方法的背景，问题描 述以及研究现状，从全局角度介绍了p c a 算法和l d a 算法，又从局部角度介绍 了n p e 算法s d l s d a 算法，同时提出了在小样本问题情况下算法的解决方法。然 后针对l s d a 所建立的数据模型，提出了两种最优化问题，分别利用零空间算法 及其扩展开来的双空间算法和迭代法加以解决，同时证明了满足某个条件下， 两种优化问题的等价性。最后，针对迭代法计算量过大的问题，应用一种双线 性低秩逼近方法压缩原始数据，从而达到提高运算速度的目的。通过实验证明， 上述提到的算法都优于原有的l s d a 算法。 关键词：降维，特征提取，人脸识别，判别分析 a b s t r a c t u s u a l l yw en e e dt og e tt h em o s te f f e c t i v ef e a t u r e sf r o mt h eh i g h d i m e n s i o n a l d a t as e tb yu s i n gad i m e n s i o n a l i t yr e d u c t i o nm e t h o di nt h ef i e l do fp a t t e r nr e c o g - n i t i o n ，m a c h i n el e a r n i n ga n dd a t am i n i n g ，t h u st oe n h a n c et h ec l a s s i f i e r sd i s c r i m - i n a t i n gp o w e r ac o m m o nm e t h o di sc o m p u t i n gao p t i m a lt r a n s f o r m a t i o np r o j e c t i o n ，w h i c h m i n i m i z e st h ew i t h i n c l a s sd i s t a n c eo ft h ed a t as e ta n dm a x i m i z e st h eb e t w e e n - c l a s sd i s t a n c es i m u l t a n e o u s l y , t h u sa c h i e v i n gt h em a x i m u md i s c r i m i n a t i o na b i b i t y a n dt h et r a n s f o r m a t i o np r o j e c t i o nm a t r i xe x t r a c tf e a t u r e st h a tp r e s e r v ec l a s s s e p a r a b i l i t y a tf i r s t ，w ew i l lg i v eab r i e fi n t r o d u c t i o nt ot h eb a c k g r o u n d ，p r o b l e md e s c r i p - t i o na n dt h ee x i s t i n gr e s e a r c hw o r ko ft h eh i g h d i m e n s i o n a ld i s c r i m i n a n ta n a l y s i s ，s u c ha sp c a m e t h o da n dl d am e t h o df r o mt h eg l o b a lv i e w ，n p em e t h o da n d l s d am e t h o df r o mt h el o c a lv i e w w ea l s og i v ead e s c r i p t i o no fh o wt os o l v et h e u n d e r s a m p l e dp r o b l e m si nt h e s ea l g o r i t h m s t h e nw ep r o p o s et w on e w k i n d so f o p t i m i z a t i o nc r i t e r i o n sb a s e do nt h em o d e lo fl s d a w eu s en u l l - s p a c em e t h o d ，d u a l - s p a c em e t h o da n di t e r a t i v em e t h o dt os o l v et h et w oo p t i m i z a t i o nc r i t e r i - o n ss e p a r a t e l y w ea l s og i v eat h e o r e t i c a la n a l y s i st h a tn u l l s p a c em e t h o da n d i t e r a t i v em e t h o da r ee q u a lu n d e ram i l dc o d i t i o n f u r t h e r m o r e ，w eu s eaw e l l - k n o w nm e t h o dc a l l e db i l i n e a rl o wr a n ka p p r o x i m a t i o n so fm a t r i c e st or e d u c et h e c o m p u t a t i o n a lc o s t e x p e r i m e n t i a lr e s u l t sc a ni l l u s t r a t et h ee f f e c t i v e n e s so fo u r a l g o r i t h m s k e y w o r d s ：d i m e n s i o nr e d u c t i o n ，f e a t u r ee x t r a c t i o n ，f a c er e c o g n i z i n g ，d i s - c r i m i n a n ta n a l y s i s 第一章引言 在现实世界和人类活动中，往往会存在着大量的复杂现象，如何透过表象 发现隐藏在这些现象的客观规律，成了科学工作者的研究方向。例如对于声音 的研究，人们通过各类描述声音特征的指标去衡量它，例如响度，音调，音色等 等。掌握了声音的各类特征，并对这些特征加以数量化，就能在此基础上进行科 学研究，比如语音识别等。由于物质世界的复杂性，人们将客观事物抽象成数据 表示时，往往需要多变量组成的向量数据来表示。比如一副6 4x6 4 大小的图像， 我们往往会把它转化为一个4 0 9 6 维的向量去描述它。虽然这样的高维向量表示 方法不仅简洁高效同时又能保留客观现象本身及其丰富的信息，但是同时也会 对随后的数据处理工作带来不少困难。随着维数的增加，最终会导致“维灾难” ( c u r s eo fd i m e n s i o n a l i t y ) f1 】。 所以，通过降维的方法，提取我们研究过程所需要的信息，同时删除那些冗 余信息和降低噪声，成了一门新的研究方向【“】。 1 1 背景及问题 在机器学习，数据挖掘，机器视觉和模式识别等研究领域中，降维分析是 一个很重要的课题。通过降维，既可以提取出对我们研究过程中有意义的特征， 又能简化计算。但随之而来的问题是，如何去提取那些“好”的特征? 例如对 于文本聚类问题，如果我们想按照同一作者的文档为一类来加以聚类，但只是 按照一般的欧式度量去衡量数据点之间的距离，使用传统的k m e a n s 聚类方法， 最后得出的结果完全有可能达不到我们的目的：文档可能按照同一主题聚类了， 或者是按照同一种写作风格聚类了。再比如，我们把一系列的人脸图片转换为 数据直接进行分析，最终的结果可能是按不同的人聚类，也有可能是按不同的 姿势聚类的。由于最终结果的不确定性，所以我们往往从所要研究的海量数据 中取出一部分数据，根据自己的需要标上类标，这样的数据集称为训练集，而剩 余的数据称为测试集。通过训练集给出的相关信息，通过各种机器学习方法从 中提取出最优的能区分类的判别信息，利用这些信息对测试集分类。我们称这 样的方法为有监督学习。而把无类标信息的机器学习方法称为无监督学习。 第一章引言2 1 2 研究进展 在机器视觉和模式识别领域中，已经有不少算法涉及到通过降维方法提 取数据的最优特征，使得在低维空间中能够提高分类识别的正确率。在这些 算法中，p c a ( p r i n c i p a lc o m p o n e n ta n a l y s i s ) 2 和l d a ( l i n e a rd i s c r i m i n a n t a n a l y s i s ) 圈是两种最常用的方法。其中p c a 的主要思想是通过降维，提取出变 量的少数几个主成份，使得变量在低维空间中具有最大的离散度。当数据有监 督情况下，l d a 算法对于数据分类的效果往往会比无监督方法p c a 要好。 l d a 是种对于有监督降维和分类的经典算法。它通过寻找最优投影矩阵， 使得数据在低维空间中每一个类中数据点与其他类中数据点之间的距离尽可能 扩大，而对于同一个类中的数据点之间的距离要尽可能的小，最终达到判别分 类的最优效果。最优投影矩阵一般通过求解一个广义特征值问题来获得，该算 法已经在很多处理高维数据的领域中得到了应用。但是l d a 算法往往会遇到一 个所谓的“小样本 问题f 4 】。当数据的维数过高，超过了数据样本点的个数时， 会产生矩阵的奇异性问题，导致原有的算法失去意义。如何解决数据点的“小 样本”问题将会再介绍。 l d a 和p c a 虽然是两种高效的算法，但是它们都是从数据的整体角度分 析问题，缺乏对数据局部特征的观察，并且无法发现数据在低维空间中潜在 的几何结构。在这方面，例如i s o a m p ，l a p l a c i a ne i g e n m a p t i 】，l o c a l l yl i n e a r e m b e d d i n g i ，】等方法能够有效的探测出在低维空间中的几何结构，但是它们 都是无监督的非线性方法，不能提升数据的分类效果。最近，有不少基于局 部观点的判别分析方法对与数据点的邻域特性进行研究，产生了很好的效果。 y , j 女in p e ( n e i g h b o r h o o dp r e s e r v i n ge m b e d d i n g ) 8 1 ，m f a ( m a r g i n a lf i s h e r a n a l y s i s ) m ，l s d a ( l o c a l i t ys e n s i t i v ed i s c r i m i n a n ta n a l y s i s ) l lu 】。它们的共同 点都是通过对数据点的邻域进行建模，用来刻画几何特性。不同点是n p e 将高 维点投影到低维点后，继续保持在高维空间中的邻域性，而m f a 与l s d a 则是从 局部点的观点最大化类与类之间的距离以及最小化类内点之间的距离。 1 3 本文的贡献 理论上，本文先从高维数据全局角度阐述t p c a 算法和l d a 算法，并详细 推导出l d a 算法最终转化为广义特征值问题的整个过程，并指出了在实际问题 中l d a 所面临的小样本问题，并给出了解决这一问题的几种方法。 第一章引言3 然后本文又从高维数据的局部角度介绍了n p e 算法和l s d a 算法，并分析 了两者之间的相同点和不同点。接着，本文在l s d a 算法模型的基础上提出了两 类优化问题，给出了多种不同的解法，实验数据表明，这几种算法各有不同的特 点。然后对于算法运算量过大的问题，引入了双线性低秩逼近方法压缩原始数 据加以解决。最后证明了满足某个条件下两类优化问题的等价性。 最后，本文通过实际数据，比较了前面所讨论的各种不同的算法的优劣好 坏。 本文具体内容安排如下：第一章是引言部分，主要介绍了高维数据降维方 法的背景、研究现状以及本文贡献；第二章是从全局角度对p c a 算法和l d a 算 法以及在分析中具体遇到的问题的介绍；第三章就高维数据局部观点介绍 了n p e 算法和l s d a 算法的概念及方法；第四章给出了基于l s d a 算法的两种改 进模型，提出了零空间算法，双空间法和迭代法，并引入双线性低秩逼近方法减 少迭代法的计算量，最后理论上证明了满足某个条件下两种模型的等价性。第 五章是实验数据的展示。第六章是文章的总结。 第二章高维数据判别分析的全局方法 2 1p c a 算法 p c a ( 主成分分析) 算法是处理过多维数时所采用的一种经典算法，它采 用组合特征的方法来降维，用为数较少的新变量来反映原变量所提供的大部 分信息。对数据特征作线性组合不仅容易计算，而且可以进行解析分析。本质 上，p c a 是一种通过正交线性变换将原始数据投影到一个低维的坐标系统下， 使得在新坐标下，第一主成分方向是使得数据方差达到最大的方向，第二主成 分方向是使得数据方差第二大的方向，依次类推。下面推导出p c a 算法。 设有n 个样本x 1 ，x 2 ，x 。，这些点都是m 维向量。如果要用一个m 维向量代 表前面n 个样本点，那么不难证明这个向量就是前n 个样本点的均值c ， 但是样本均值并不能反映出样本之间的不同。假设存在一个投影矩阵，将m 维 样本空间都投影到一个通过均值点c f i 维数是1 ( 1 = 1 这里的e t ( i = 1 ，2 f ) 是f 维空间的单位正交基。 为了使得在降维后尽可能减少原始数据的信息损失，我们通过最小化平方 误差准则函数来得到系数a 触的集合。 j = + a k i e i ) 一x 知1 1 2 ( 2 1 ) 七= l t = 1 ，lf = i i a k i e t 一( x 七一c ) 1 1 2 ( 2 2 ) 七= 1i = 1 nj nfn = 口毛一2 e 丁( x 七一c ) + 帆一c i | 2 ( 2 3 ) 七 x n 脯 1 一几 = c 第二章高维数据判别分析的全局方法5 根据假设| | e i i i = 1 ( i = 1 ，2 ，z ) ，对a k i 求导，令j = 0 ，可以得到所有系数值 a k = e ，( x 七一c ) ，( k = 1 ，2 n ，i = 1 ，2 f ) ( 2 4 ) 由此我们得到了在j 空间下，高维样本点对应的表达式。但是张成2 维空间的标准 正交基组有无数个，如何找到使得误差准则函数j 最小的那一组昵? 把( 2 4 ) 带入( 2 3 ) 并化简，可以得到 nzn j = 一鳅x 七一c ) 2 】+ 一e l l 2 ( 2 5 ) 岛= lt = 1七= l nln = 一e ( x 七一c ) ( x 七一c ) t e t + 慨一c 盯 ( 2 6 ) k = li = 1七= l 定义e = ( e l ，e 2 ，e z ) 以及散布矩阵s = 冬1 ( x 七一c ) ( x k c ) t 。这样( 2 6 ) 可 进一步化简为 j = 一e r s e + l l x k c i l 2 七= l ( 2 7 ) 要使j 最小，也就是求矿s e 最大，利用拉格朗同方法，以及l l e l i = 1 可以有 u = e t s e a ( e 丁e 一1 ) ( 2 8 ) 对e 求偏导，再令导数为零，最终转化为求特征值一特征向量问题： s e = 入e ( 2 9 ) 散布矩阵s 的前m 个最大特征值对应的特征向量，它就是我们所要求的m 7 个标 准正交基。 p c a 算法十分简单。如果要将数据降维到m 7 维而尽可能保留原始数据的信 息的话，只要通过求解数据散布矩阵对应于前m 7 个最大特征值对应的特征向量 就可以了。 2 2l d a 算法 2 2 1 l d a 算法的理论推导 l d a ( l i n e a rd i s c r i m i n a n ta n a l y s i s ) 算法是一种经典的降维和最优特征提 取方法。l d a 试图寻找一个投影方向，使得在低维空问中最大化类与类之间数 第二章高维数据判别分析的全局方法 6 据点的距离( 类间距离) ，同时能最小化同一类中数据点的距离( 类内距离) ，最 终达到最佳的判别效果。下面给出l d a 算法的推导过程。 设存在n 个m 维高维数据点x 1 ，x 2 ，它们共同组成数据阵x r m 黼， 同时假设这些数据可被分为七个类，其中第i 类的数据组成子矩阵x i r m 加t ，i = 1 ，k ，冬l n i = 礼。每一个类的均值点定义为c = 磊1k e ，e = ( 1 ，l ，1 ) t r m ，所有数据的均值点定义为c = ! 。x e ，e = ( 1 ，1 ，1 ) 丁r n 。不失一般性， 可设x = 【x l ，孔】o 在数据点集中，数据类内点距离分散程度矩阵( w i t h i n - - c l a s ss c a t t e rm & - t r i x ) 可以定义为 ：三壹( x ) ( x 。) 7 ( 2 1 0 ) i = 1x x i 数据点类与类之间点距离的分散程度矩阵( b e t w e e n - - c l a s ss c a t t e rm a t r i x ) 可 以定义为 & = 去妻擎叫c i _ c ) t 三如c 嘶叫r 亿 总散布矩阵( t o t a ls c a t t e rm a t r i x ) 定义为 1 n & 2 嘉( x _ c ) ( x i _ c ) r 很显然，& = 鼠+ 鼠。 为了问题的简化，还可以定义 这样就有了 = 万1 c 1 ( e 1 ) t ，x k - - c k ( e 七) t 1 凰= 击【佤( c 1 - - c ) ，佤( c k _ c ) l 吼= 丽1 ( x c e 丁) ( 2 1 2 ) ( 2 1 3 ) ( 2 1 4 ) ( 2 1 5 ) s m = h 啦h 毛1s b = h b h ，s t = h t h i 1 、2 1 6 、 第二章高维数据判别分析的全局方法 7 数据点类内距离的分散程度用鼠的迹表示 t r ) - 1 z z 魄( x - - c i 尸( x - c 勺n 善到一。0 2 ( 2 1 7 ) = 1xx扛：1x 墨 数据点类间距离的分散程度用的迹表示 t r ( & ) ：丢妻州叫飞叫= 去妻非驯 ( 2 1 8 ) 我们所要求的是找出最优的投影矩阵g r r n x t , 使得在低维空间中，类内分散程 度尽可能小，类间分散程度尽可能大。即最大化下面的准则 j o ( e ) = 器器 ( 2 1 9 ) 通常在求l d a 算法时，更常用的是最大化另外一个最优准则【3 】，因为如果& 为 非奇异的正定阵，那么通过它能得到投影矩阵的显式解： 以( g ) = t r ( ( g t & g ) - 1 g t & g ) ( 2 2 0 ) 由于与& 都是对称阵，如果为非奇异的正定阵，【1 1 】给出了如下算法，找到 一个非奇异矩阵x 酞m m ，使得 x r s b x = a = d i a g ( a 1 k ) ，x 丁s , x = m ( 2 2 1 ) 算法2 2 1 计算x ，使得& 与& 同时对角化。 1 计算c h o l e s k y 分解s t = z z t ； 2 计算c = z 一1 鼠z t ； 3 用对称q r 算法计算s c h u r 贫 解q t c q = d i a g ( a l ，a m ) ； 4 令x = z t q 。返回结果。 显然，如果令z 是x 的第i 个列向量的化，x i 就是筇1 鼠对应于特征值a 的特 征向量。有了上述结果，有如下定理 1 3 】，给出了( 2 2 0 ) 的解： 定理2 2 1 投影矩阵g r m ，则当g = x ( 厶0 ) 丁时， ( g ) 达到最大值， 即g 对应于s 1 & 前f 个最大的特征向量，这里( 五0 ) r r m 。 第二章高维数据判别分析的全局方法8 证明把( 2 2 1 ) 代入( 2 2 0 ) ，有 j l ( a ) = t r ( g t x r x g ) 一1 g t x 坷a x 一1 g ) = t r ( ( z t z ) 一1 z t a z ) ( 2 2 2 ) ( 2 2 3 ) 这里有z = x g ，对z 做q r 分解，z = q r ，q r m 。是列正交的，冗非奇 异，我们有 以( g ) = t r ( ( r t r ) _ 1 r ：r q t a q r ) = t r ( r 一1q t a q r l = t r ( q t a q r r 一1 ) = t r ( q t a q ) ( 2 2 4 ) ( 2 2 5 ) ( 2 2 6 ) ( 2 2 7 ) 这罩的( 2 2 6 ) 是用到了迹的r ( a b ) = t r ( b a ) 的性质。所以最大化山( g ) 可转化 为 m “a xj 1 ( a ) 2q m r q a ：x t r ( q t a q ) 入l + + a g = t r ( 笥1 & ) ( 2 2 8 ) ( 2 2 9 ) ( 2 3 0 ) 这里的( 2 2 9 ) 是用到的是r a y l e i g hq u o t i e n t 理论【1 1 1 ，并且假设r a n k ( ) = q 。且 使得( 2 2 9 ) 等号成立的条件是q = ( 五，0 ) t ，这样g = x ( 五，0 ) 丁r 。由于对任意 的非奇异阵r 耐则，不难证明以( g ) = j 1 ( g r ) 。所以当g r m 则由筇1 鼠前f 个 最大特征值对应的特征向量组成时，以( g ) 达到最大，定理得证。 由此可得，如果非奇异的话，最佳投影矩阵g 是由筇1 前f 个最大特征值 对应的特征向量组成。但是由于r a n k ( & ) 0 和i ，总存在1 e ，使得九+ 1 = 凡+ 1 。由定义有： t r ( 曙( l ：，一a i + l l i ) u ) = 0 ( 4 1 3 ) 等价于： t r ( u ( l y 一( 九+ 1 ) 三 ) 以) = 0 ( 4 1 4 ) 当i _ c o 时，1 0 ，则有 t r ( 曙( l ：，一九l t ) u ) 一0 ( 4 1 5 ) 由以的定义，有： m a x t r ( u t ( l ；，一入t l t ) u ) 一0 ( 4 1 6 ) 当i _ c o ，a t 收敛到入。有m a x t r ( u t ( l v a l ) u ) _ 0 ，可以推得： a _ m a x 器豁( 4 1 7 u t u = it r ( u 7 u ， 三兰) 7 由此推得，算法收敛到最优解。证明完毕。 本算法是在【2 4 】中介绍的一种解决l d a 算法的迭代法的基础上加以改进的。 在每次迭代时，我们取的是所有正的特征值对应的特征向量，而【2 4 】取的是前f 个 从大到小排列的特征值对应的特征向量，若l 过大会将负特征值对应的特征向量 包括进来，每次迭代都不是所求的最大值，若f 过小，则会在每次迭代中损失一 部分判别信息。经过实验验证，本论文提的特征向量选取方法要好于原来的方 法。 4 3双线性最优低秩逼近 实验数据表明，前一节介绍的迭代法在判别数据类别上正确率很高，但计 算量较大。对于第一步去除零空间过程，会涉及至 s v d 分解，当数据量过大时， 第四章l s d a 算法的修正模型 会导致计算量的显著上升。所以在这里我们将介绍一种双线性最优低秩逼近的 方法在迭代算法执行前先压缩原始数据，以达到减少算法的计算量，同时并不 影响最终判别数据的效果。 对于小样本问题，根本原因在于数据点的个数小于数据点特征的个数，也即 对于n 个数据点x 1 ，z m r m 组成的数据阵x = ( z 1 ，x 2 ，x n ) ，有佗i ij u t u = i ，v t v = i _ 、 对于问题( 4 2 3 ) 没有显式解，所以采用交替的方式迭代法求解。下面给出具体 的算法： 算法4 3 1 给定数据矩阵 五) 鍪1 和所要压缩到的维数2 1 和z 2 。求得最终被压缩 的数据阵 ) 翟。 1 初始化u o = ( i ，o ) t ； 2 对于i = 1 ，开始循环迭代： a 计算m 1 = ：，霹阢一- 哩，。 b 取m 1 由大到小排序的前2 2 个特征值对应的特征向量 ) 1 将其赋 予k ，即k = ( v l ，v l ：) 。 c 计算= e 警1 砑k 一1 y l r _ 1 码。 d 取由大到小排序的前1 1 个特征值对应的特征向量j t 2 l j 3 f 1 = 1 将其赋 予以，即阢= ( u l ，乱f 。) 。 e 令巧= 孵冯k ，j = 1 ，佗，五= 筹。i i 玛一阢巧k t i i 刍。若生专丛 g ，则把以，k 分别赋予u ，y ，循环终止。否则i = i + 1 ，继续迭代 3 令m = u t x t v ( i = 1 ，n ) ，输出结果。 由于对每一次阢和k 的更新，l i u t x , v l l 都单调不减，因而冬，l i 五一 u k y r 慷单调不增，可以推出算法将最终收敛。 在这里讨论一下f 。和f 2 的选取问题，事实上并没有足够的理论依据可以证 明2 1 和2 2 究竟取多少才能使得问题( 4 1 8 ) 的残差最小，但是根据实验数据得到 第四章l s d a 算法的修正模型 的经验结果是，当f 1 z 2 1 时，可以达到最好的结果。所以我们在下面的实验中 采用f 1 = 2 2 。 我们最终采取的算法是：先用双线性低秩逼近对数据进行压缩，再采用迭 代法求出投影向量。以便达到在低维空间中最小化类内距离，最大化类间距离 的效果。 4 4两种优化问题的等价性 在具体实验中，我们发现零空间算法和迭代法这两种方法所求得的数据分 类的正确率多数情况下总是一样的。这给出了两种算法是否等价的疑问。接下 来，我们将通过理论分析，证明只要满足一个条件，两类优化问题确实是等价 的。 这两种算法是基于两种优化问题给出的。其中，零空问算法是求如下的最 优化问题： m a x t r ( g t x l b x t g ) ( 4 2 4 ) t r ( g t x l 。x r g ) = o 。 、 迭代法是求如下的最优化问题： 船m a x j 黼( 4 2 5 )g ：j 面孕丈i 两 由前面的讨论，我们已有以下结论： n u l l ( x l x t ) = n u l l ( x l b x t ) n u l l ( x l 加x t ) 同时，去除x l x 丁的零空间并不影响问题最终的解。因此取x l x t 做s v d 分 解x l t x t = u a u t ，这里a = ( a l ，入七) ，而入1 ，a 詹是x l t x t 的所有非零奇 异值。 我们在分析问题以前先去除x l 。x 丁的零空间，令 厶：u t l 以三6 = u t l 6 u ，瓦= u r l 仰u 那么两个最优化问题分别转化为： m a xt r ( n t 厶) t r ( n t l ) = o ( 4 2 6 ) 第四章l s d a 算法的修正模型 2 5 和 t r ( n t 厶n ) m a x = 二1 r n = i t r ( n t l t n ) ( 4 2 7 ) 最终求得的投影矩阵为g = u 。 先分析( 4 2 6 ) ，令为厶的零空间矩阵。则对任何可行解：t r ( n t 瓦n ) = 0 ，可以被表示为= w m ，其中m 满足m ? m = ，。m 可以通过解决下面的问 题求得： m ，a xt r ( m t w t 厶w m ) m t m = l ( 4 2 8 ) 因而m 由w 丁l 6 w 的正的特征值对应的特征向量组成。所以投影矩阵g = u w m 就是( 4 2 6 ) 的最优解。 对于问题( 4 2 7 ) ，将上面的n = w m 带入，有 丁厶n = n 丁( 厶+ 瓦) = m 丁w t ( 6 + 厶) w m = m t w t b w m ( 4 2 9 ) 这样糍= 1 ，而前面已经证明，0 丽t r ( 丽n t 五i ：b 丽n ) 1 。所以g = u w m 同样 是问题( 4 2 7 ) 的解。 综上所述，当g = u w m 时，两类优化问题将同时达到最大，所以这两类优 化问题等价。不过这里必需满足一个条件：厶。，有零空间w 。 第五章数值实验与比较 5 1最优特征提取的图像表示 对于所求的的投影矩阵，每个列向量都可以重构出一张图片，f 面我们将 把y a l e 数据库应用不同算法所得到的投影矩阵的列向量转化为图片，用柬显式 不同算法对瑚片在低维空间中保留的特征。我们各取前1 1 个列向量展示特征图 像 星4i 一1 熔周三脉咧瑟。 圈5 1 ：p c a 特征图。 图52 ：l d a 特征图 图53l s d a 特征图 我们可以看到，对于人脸图片中潜在的模式，虽然人的面部都有并不相同的纹 理，形状，大小和比例，有千差万别的无法描述的微妙特性，但从简单的特征 罔，可以有效的勾勒i b 人脸的轮廓，眼眶，鼻子等细节部分。 第五章数值实骁与比较 5 2 人脸数据实验 在这一节里，我们将通过三个人脸数据库的实际例子，具体比较静文所述 的各种算法的优劣，迭代法的收敛速度，以及采用取线性低秩逼近对算法速度 上的改进。 我们采用的是下面三个数据库： y a l e 数据库包含1 5 个人，每个人各有1 l 张图片，共1 6 5 张。 o r l 数据库，包含4 0 个人，每个人各有1 0 张图片，共4 0 0 张。 p i e 数据库包含6 8 个人，每个人各有1 7 0 张图片，共1 1 5 6 0 张。 我们先来看y a t e 数据库，图( 54 ) 显式了y 出e 数据库中前5 个人的人脸。对 于缚个人，根据光线强弱与表情的不同，共有儿张图片。 圈54 ：y a l e 数据库中的部分人脸数据图。 再来看o r l 数据库，阁( 5 5 ) 显式了o r l 数掘库中前5 个人的人脸。根据不同的 表情和细节每一个人自1 0 张图片。 第五章数值实验与比较 图55 ：o r l 数据库中的部分人脸数据围 摄后看p i e 数据库。图( 57 ) 显示了p i e 数据库中5 个人的1 0 张人脸。每个人由于 光线的不同而有1 0 张图片。 图56 ：p i e 数据库中获取的部分人脸数据图。 在实验之前，所有图片都经过规范化处理( 图片中人的双眼都排列在 同位置) ，再截取图片中的人脸作为最终实验的图片。每张裁取的图片都 是3 2x3 2 像素，2 5 6 色的荻度图。 第五章数值实验与比较 实验的过程如下： ( 1 ) 从数据库中，对每个人各随机提取n 张图片，一起组成训练集( n t r a i n ) ，剩下的图片作为测试集。 ( 2 ) 将前文讨论的算法作用于训练集，得到投影矩阵。然后利用所得的投 影矩阵，分别对训练集和测试集进行线性投影，得到训练集和测试集的低维表 达形式。 ( 3 ) 在低维空间中，采用分类算法( 5 2 1 ) ，得到测试集的预测类标，并和 测试集的真实类标相比较，求出整个判别算法的预测正确率。 ( 4 ) 为了避免随机提取图片导致的偶然性，重复( 1 ) ，( 2 ) ，( 3 ) 2 0 遍，取平 均值为最终的正确率。 常用的分类算法有很多种，我们这里采用的是基于中心的分类法。 算法5 2 1 给定已知分类的训练数据矩阵y ，分成k 类：m ，圪。给定一组未 知类别的测试点 协) ，判断它们的类别。 j 计算每一类训练集m 的中心，得到忌个中心点( c 1 ，) ； 2 计算每个协与各中心点c l ，的墨巨离d 巧= l l 驺一岛1 1 i 殳d e , j = m i n d i ，j 。 则将协分为第e 类。 我们将进行比较的算法有 ( 1 ) b a s e l i n e 算法( 即原始数据不经过降维分析直接分类) ， ( 2 ) l d a 算法( p c a + l d a ) ， ( 3 ) n p e 算法， ( 4 ) l s d a 算法， ( 5 ) m a x - m i n l s d a 算法( 在l s d a 模型的基础上采用先固定极大值，再求极 小值的方法，简称m l s d a ) ， ( 6 ) n u l l s p a c e - l s d a 算法( 在l s d a 模型的基础上采用零空间算法，简称n l s d a ) ， 第五章数值实验与比较 ( 7 ) d u a l s p a c e - l s d a 算法( 在n l s d a 算法的基础上增加零空间的正交补空间 的判别信息，简称d l s d a ) ， ( 8 ) i t e r a t i v e - l s d a 算法( 在l s d a 模型的基础上采用迭代法，简称i - l s d a ) ， ( 9 ) b i l i n e a r - i t e r a t i v e l s d a 算法( 先对数据做双线性低秩逼近，再采用i t e r a t i v e - l s d a 算法，简称b i - l s d a ) 。 表( 5 1 ) 和表( 5 2 ) 给出了对于y a l e 数据库，不同规模训练集下不同算法的 分类准确率。从表中可以看出，我们在本文中提到的两个基于l s d a 模型的算法 均优于l s d a 算法，而且正如前一章节所证明的，零空间算法和迭代法具有等价 性。对于先对数据进行双线性低秩逼近压缩，再采用迭代法，在y a l e 数据库上 产生了很好的效果，应该说是最优的。而且双空间法略好于零空间法。 表5 1 ：y a l e 燃：最高正确率( ) 及其维数( 2t r a i n 一5t r a i n ) 1b a s e l i n e 4 4 3 6 ( 1 0 2 4 )5 2 9 3 ( 1 0 2 4 )5 5 4 3 ( 1 0 2 4 )5 7 6 4 ( 1 0 2 4 ) 2l d a 4 6 0 4 ( 1 0 )6 3 9 3 ( 1 4 )7 1 3 5 ( 1 4 )7 5 6 0 ( 1 4 ) 3n p e 5 6 0 0 ( 1 4 )6 6 1 7 ( 1 4 )7 1 6 6 ( 1 4 )7 6 3 1 ( 1 4 ) 4l s d a 5 5 7 3 ( 1 4 )6 6 5 3 ( 1 4 ) 7 1 8 1 ( 1 4 ) 7 6 3 6 ( 1 4 1 5m l s d a 5 7 0 4 ( 1 4 )6 6 6 7 ( 1 4 )7 4 8 6 ( 1 4 )7 6 3 3 ( 1 4 ) 6n l s d a 5 5 4 4 ( 1 4 )6 7 3 0 ( 1 4 )7 2 2 7 ( 1 4 )7 6 2 2 ( 1 4 ) 7d l s d a 5 5 8 5 ( 1 4 )6 7 6 5 ( 1 4 )7 2 7 1 ( 1 47 6 8 9 ( 1 4 ) 8 i l s d a 5 5 4 4 ( 1 4 )6 7 3 0 ( 1 4 )7 2 2 7 ( 1 4 )7 6 1 8 ( 1 4 ) 9b i l s d a 5 7 3 3 ( 1 4 )6 8 1 7 ( 1 4 )7 2 1 4 ( 1 4 )7 8 7 8 ( 1 4 ) 表( 5 3 ) 和表( 5 4 ) 分别给出了关于o r l 数据库和p i e 数据库的分类效果。 从表( 5 3 ) 可以看出，由于训练集数量的增加，关于o r l 数据库的效果好于关 于y a l e 数据库的效果。在y a l e 数据库中反映的一系列特点，同样在o r l 数据库 上得到了反映。不过有一点不同，b i l s d a 算法此时和i l s d a 算法的正 确率相差不大。 第五章数值实验与比较 3 1 表5 2 ：y a l e 数据库：最高正确率( ) 及其维数( 6t r a i n 一8t r a i n ) m e t h o d6t r a i n7t r a i n8 t r a i n 1b a s e l i n e 6 0 9 3 ( 1 0 2 4 )6 5 3 3 ( 1 0 2 4 )6 6 6 7 ( 1 0 2 4 ) 2l d a 7 9 7 3 ( 1 4 ) 8 0 5 0 ( 1 4 )8 3 5 8 ( 1 4 ) 3n p e 7 6 8 0 ( 1 4 )7 9 8 3 ( 1 4 )8 1 5 6 ( 1 4 ) 4l s d a 7 7 0 7 ( 1 4 )7 9 3 3 ( 1 4 )8 3 3 3 ( 1 4 ) 5m l s d a 7 8 5 3 ( 1 4 )8 1 0 0 ( 1 4 )8 2 3 3 ( 1 4 ) 6n l s d a 8 0 4 0 ( 1 4 )8 2 6 7 ( 1 4 )8 5 0 1 ( 1 4 ) 7d l s d a 8 1 0 2 ( 1 4 )8 3 1 2 ( 1 4 )8 5 3 1 ( 1 4 ) 8i l s d a 8 0 4 0 ( 1 4 ) 8 2 6 7 ( 1 4 ) 8 5 1 1 ( 1 4 ) 9b i l s d a 8 0 5 3 ( 1 4 )8 1 5 3 ( 1 4 )8 2 5 6 ( 1 4 ) 从表( 5 4 ) 可以看出，随着训练集的增加，i l s d a 和n l s d a 的j 下确 率逐渐好于原l s d a 算法。数据量的增大使得数据全局特性要优于数据的局部 特性，所以l d a 算法在本数据上表现的比三s d a 算法要好。而且在本数据库上 零空间算法和迭代法的j 下确率开始出现偏差，原因是瓦没有零空间。 以上计算的正确率都是从不同算法降低到不同维数得到的正确率取最大值 得到的。接下来比较数据降低到不同维数对正确率的影响，我们选取l s d a 与n l s d a 做比较。观察图( 5 7 ) 和图( 5 8 ) 可以看到，n l s d a 算法正确率最初随 着维数增大上升很快，升到十几维时开始稳定下来并缓慢上升。而l s d a 算法 则十分均衡的上升。从总体上看，在y a l e 数据库上，n l s d a 的正确率略高于 l l l s d a 的j 下确率，在o r l 数据库上n l s d a 算法的正确率始终高于l s d a 算法。 且实验结果表明，当降低到的维数比数据类别个数少一时，正确率能达到最大。 我们接下来看i l s d a 算法迭代的收敛速度。我们分别在y a l e 和o r l 数据上 做实验，看入= 等等事碟每次迭代的具体值，观察图( 5 9 ) 可以发现，迭代速度 是很快的，一般迭代3 至1 1 4 步左右就基本达到最大值1 了。 再来分析双线性逼近算法的收敛速度问题。观察图( 5 1 0 ) 再来分析双线性 逼近算法的收敛速度问题。可以看到收敛速度很快，一般迭代2 步就可以收敛 了。可以看到收敛速度很快，一般迭代1 n 2 步就可以收敛了。 第五章数值实验与比较 表5 3 ：o r l 数据库：最高正确率( ) 及维数( 2 t r a i n 一5 t r a i n ) m e t h o d2t r a i n3t r a i n4t r a i n5t r a i n lb a s e l i n e 7 0 4 5 ( 1 0 2 4 ) 7 5 9 1 ( 1 0 2 4 )8