（计算数学专业论文）矩阵的非负分解算法及应用.pdf

摘要 降维是一种在高维数据中挖掘低维相关性的技术，在模式识别，机器学习， 独立组分分析以及图像处理等领域有着广泛的应用。而非负矩阵分解( n m f ) 做为降维方法的一种，因其明确的物理意义及良好的可解释性受到广泛的关 注。 根据分解的目的，非负矩阵分解大致可以分为两种，一是在保证数据某些 性质的基础上，将高维空间的样本点映射到某个低维空间上，除去一些不重要 的细节，获得原数据的本质信息；二是在从复杂混乱的系统中得到混杂前的各 独立信息的种类和强度。因此，基于非负矩阵分解过程应用领域的不同，分解 过程所受的约束和需要保留的性质都不相同，本文将以i c a 分析和人脸识别为 例针对上述两种应用场合，给出非负矩阵分解方法的一系列改进方法。 本文首先介绍了非负矩阵分解产生的背景、其问题描述以及研究现状。接 着本文针对稀疏存储问题，提出了一种新的向量稀疏性度量方法，给出了向量 最优稀疏逼近的求解算法，进而给出非负矩阵的稀疏低秩逼近算法。然后，针 对人脸识别领域，本文提出加权归一化的概念，并给出了两种行之有效的加权 方法，该算法在人脸识别领域获得了足以与传统p c a 方法相媲美的识别效果。 最后，在i c a 领域，本文给出了带平移的非负矩阵分解的算法，将非负矩阵分解 算法推广到无非负限制的独立组分分析领域中，并提出了平滑化分级提取策略， 有效的改善了独立组分提取的效果。 关键词：降维，非负矩阵分解，稀疏化，人脸识别，独立组分分析 a b s t r a c t a sa t e c h n o l o g yf o ro b t a i n i n gl o wd i m e n s i o n a lr e p r e s e n t a t i o nf r o me x t r e m e l v h i g hd i m e n s i o nd a t a ，d i m e n s i o n a l i t yr e d u c t i o np l a y sa ni m p o r t a n tr 0 1 ei nm a n v f i e l d ss u c ha sp 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 g ，i n d e p e n d e n tc o m p o n e n t a n a l y s i s ( i c a ) a n di m a g ep r o c e s s i n g ，e t c n o n - n e g a t i v em a t r i xf a c t o r i z a t i o n ( n m f f o rs h o r t ) ，am e t h o do fd i m e n s i o nr e d u c t i o n ，c a t c h e sm a n y p e o p l e se y e si nr e c e n t y e a r sf o ri t se x p l i c i tp h y s i c a lm e a n i n ga n dg o o de x p l i c a t i o n b yt h ee n do ff a c t o r i z a t i o n ，n m fc a nb ec l a s s i f i e di n t ot w o c a t e g o r i e s ：o n e a i mi st od i s c a r ds o m ef r a g i l ei n f o r m a t i o na n dg e ts o m ei n t r i n s i ci n f o r m a t i o n d e e pi ns o m e t h i n gb ym a p p i n gt h es a m p l ep o i n t si na h i g hd i m e n s i o ns p a c ei n t o as u b s p a c ew i t hm u c hl o w e rd i m e n s i o nw h i l er e s e r v i n gc e r t a i np r o p e r t i e s t h e o t h e rt r i e st og e ts o m ep r o p e r t i e so rs t r e n g t ho fl a t e n ti n d e p e n d e n tc o m p o n e n t i na nu n k n o w nc o m p l e xs y s t e m t h e r e f o r e ，d u et ot h ed i f f e r e n ta p p l y i n gf i e l d o fn m f ，t h ei m p o s e ds t r i c t n e s sa n dp r o p e r t i e st or e s e r v ea r e v e r vd i 雎r e n t i n t h i sp a p e r ，t a k i n gi c aa n df a c er e c o g n i z i n ge x p e r i m e n tf o re x a m p l e w ew i l l p r o p o s eas e r i e so fm e t h o dt oe n h a n c et h er e p r e s e n t a t i o no fn m f 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 ，a c a d e m i cd 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 fn o n n e g a t i v em a t r i xf a c t o r i z a t i o n t h e nw ep r o p o s ean e wk i n do fs p a r s em e a s u r e m e n to fv e c t o r ，a n da l g o r i t h mt o 8 0 l v et h eo p t i m a ls p a r s ea p p r o x i m a t i o nw a s g i v e n ，w h i c hw i l lb eu s e di nt h ef 0 1 - l o w i n ga l g o r i t h mn a m e ds p a r s en m f a f t e rt h i s ，i nt h ef i e l do ff a c er e c o g n i z i n g ， w ep r o p o s et h ec o n c e p t i o no fw e i g h t e du n i t ya n d g i v et w ok i n d so fe f f e c t i v ea p - p r o a c ht oc o m p u t et h ew e i g h t e dc o e f f i c i e n t ，b yw h i c h ，w eg e ta g r e a te f f e c ti no u r e x p e r i m e n t m e a n w h i l e ，i nt h ef i e l do fi c a ，w ep r o p o s eau e w a p p r o a c ：ho fn m f w i t hs h i f t ，w h i c he x t e n d st h ep r e v i o u sn m f t ot h ef i e l dw i t h o u tn o l l - n e g a t i v e s t r i c t n e s s f u r t h e r m o r e ，w ee n h a n c es o m em e t h o d st om o d i f yt h er e s u l t ，s u c ha s s t a g e - e x t r a c t i o na n dc o m p o n e n t - s m o o t h n e s s k e y w o r d s ：n m f ，d i m e n s i o nr e d u c t i o n ，s p a r s e ，f a c er e c o g n i z i n g ，i c a 浙江大学研究生学位论文独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发 表或撰写过的研究成果，也不包含为获得逝姿盘堂一或其他教育机构的学位或 证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均己在论文 中作了明确的说明并表示谢意。 学位论文作者签名：弓长永竞签字日期： 劢四年乡月呵日 学位论文版权使用授权书 本学位论文作者完全了解逝姿盘堂有权保留并向国家有关部门或机 构送交本论文的复印件和磁盘，允许论文被查阅和借阅。本人授权逝婆叁堂 可以将学位论文的全部或部分内容编入有关数据库进行检索和传播，可以采用影 印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：歹反永荔 导师签名： 签字日期：砂以年6 月( 日 签字日期： 第一章引言 物质世界和人类社会中存在着大量的复杂事物及现象，人们希望揭示隐藏 在这些纷繁芜杂的表象下的事物和现象的客观规律。比如对天气状况，随着气 象学的发展，现在用来描述气象特征的指标非常多，例如温度、湿度、气压、风 力、降雨量、辐射强度等等，这样对于每时每刻的天气状况，可以用多变量组成 的向量数据表示，这些用多个变量描述现象的数据，抽象出来就是高维数据。高 维数据提供了有关客观现象的极其丰富、详细的信息，然而，数据维数的增多 也给随后的数据处理工作带来了前所未有的困难，因此，必须寻求一种新的处 理高维数据的方法，以便于我们可以从纷繁复杂的高维数据中发现更为本质的 信息。 这种情况下，数据降维一一把高维空间数据映射n i l 乇维空间的数据处理技 术就应运而生了。 1 1 背景及问题 降维问题在包括诸如数据挖掘、机器学习和计算机图像等领域中有着广泛 的应用。作为一种重要的降维方法，非负矩阵分解的目是从高维空间中的样本 点中发现隐藏其中的低维模式，并以这些低维模式为基础，将高维样本点映射 到某个低维空间上，以获取原高维数据更为本质的信息，并以更加直观的方式 表达出来。这样，对原高维数据的处理就可以放到在低维空间中进行，比如分 类、标记以及检测等等。 一方面，在一些人脸识别的图像处理中【l 】f 】，- - 昌j j 图像可以表示成一个向 量，其维数等于它的全部象素个数，比如5 6 4 6 ，向量中的每个元素可以取为 对应象素点的灰度值，这样一个向量便可以完整的保存一副图像。然而在人脸 识别中，给出一张新的图片，我们关心的只是这张图片是否具有人脸的结构，库 中是否出现过类似的人脸特征，如果有，它是属于哪个人的? 事实上，一张人脸 灰度图可以看作眼睛、屑毛、鼻子、嘴巴、额头等多种组分不同形式的组合。一 张图片的像素数通常很大，而该图片所能表示的人脸特征数却远远小于象素总 数。因此我们希望从图像数据中发掘人脸图片中各种相对独立的较为准确的局 第一章引言 2 部特征，在保证需要的识别精度的前提下，以尽可能少的内存存储。 另一方面，随着非负矩阵分解理论的发展，n m f 已经开始作为一种独立组 分分析的手段应用于某些新的领域同，如医学中对于新出现的稀有病症的症状 研究【4 】，生理学中对于神经末端电磁响应情况的研究以及近几年提出的在红外 光谱分析中的应用等。以前者为例，每种病症都需要通过一系列的症状及一些 遗传因素来判断。在n m f 中，将一些罕见病人每人的相关信息，如发热、虚汗、 疲倦、抖动以及遗传病史等诸多因素排成一个向量，组成一个症状矩阵，通过 对这些矩阵的分析可以得出不同的症群，以及每个病人在各个症群中的可能性， 以此作为医生诊断的辅助。 可以看出，原有的应用都要求所得的数据为非负数据。然而，在多数i c a 模 型中，有这样一种情形：在一个未知的封闭系统中，存在一些不断运动的物 体( 如海洋中的鱼) ，我们不知道运动物体的种类及数量，但我们可以获取一些 信号如红外线，微波，声波等，信号的种类及强度随着活动物的种类及距离而不 同变化。如何通过不段变化的信号来判断信号源的种类以及信号的强度( 在实 际应用中表示距离或者数量) ，便是我们关心的问题。在这种情形下，非负性的 约束是不现实的。我们希望对原有的非负矩阵分解方法进行改进，将其推广到 无非负约束的情况，使之更好的为人类服务。 1 2研究进展 由于在现实中，很多数据是用正数或零表示的，而非负矩阵的非负特性正 好迎合了这一要求，这使得非负矩阵的研究受到科学家们的广泛关注。近些年 来，经过科学家们的不懈努力，非负矩阵研究取得了不少进展f 3 】【6 】【硼均【切，并以 各种形式应用于多个领域。非负矩阵分解技术( n m f ) 就是基于这种非负矩阵 理论产生的模式识别方法。 该方法继承了非负矩阵的非负性优点，在运算中始终保证数据的非负 性，使它有较为明确的物理意义，便于解释实际问题。作为一种模式识别技 术，n m f 也因此而被广泛的接受。最近，有人【lu | 【l l l 【l 】将其用于人脸识别， 并与传统的p c a 方法相比较，给出了非负矩阵分解所得人脸的基图像。后 来，p a t r i k h o y e r 等人还提出了稀疏化的概念【鲻l ，并应用于人脸识别，有效的降 低了人脸局部特征的存储要求。虽然n m f 的人脸识别能力还不能和传统的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 ，即主频率分析) 相比，但其出色的特征显示能 第一章引言3 力，及明确的含义使它逐渐显示了其在人脸识别中的独特能力。 另一方面，作为一种独立组分分析的手段，n m f 在症状识别，文本挖掘【1 4 1 ， 神经响应分析i 上5 1 等传统领域也获得了长足的发展【1 6 蚪九近年来，严建军【瑚等 人将n m f 应用于光谱图像分析，获得较好的实验效果。但是同时，n m f 在诸多 的i c a 领域中还是遇到了不少问题，由于对源数据非负性的限制，使得它在微 波、声学等领域的运用受到限制。因此，i c a 领域需要一种既有明确的可解释 性，又能广泛应用的i c a 技术。 1 3 本文的贡献 理论上，本文首先分析了已有的向量稀疏值定义存在的问题，并提出了一 种更为直观有效的稀疏值定义，实验证明，在统计意义下，该定义和通常所说的 向量稀疏性有很好的吻合，这是原有的稀疏值定义所无法达到的，新的稀疏值 定义更能直观准确的描述向量的稀疏性。接着，本文介绍了向量的最优稀疏逼 近问题，并深入了分析了最优稀疏逼近的性质，进而给出完整的近似求解方法。 然后本文通过实验比较了新的稀疏逼近求解方法与其他已有算法，证明新的算 法所求得的解在满足稀疏性要求的同时，具有更小的逼近误差。最后，本文将 新的稀疏逼近求解方法应用于非负矩阵分解，对非负矩阵稀疏低秩分解的算法 做了介绍。 关于实际应用，本文首先针对人脸识别领域，提出了基矩阵加权归一化的 概念，并给出了基于标准差和基于平均偏差的两种加权方案。实验表明，这两 种加权方法都能大大提高非负矩阵分解的人脸识别率。特别的，在出现孤立点 的特殊情形，基于平均偏差的加权方法表现出了良好的稳定性。经过加权，非 负矩阵分解获得了足以与p c a 相媲美的效果。接着，针对人脸识别中的矩阵稀 疏存储问题，本文通过实验给出了非负矩阵稀疏低秩分解中稀疏阈值和所得人 脸识别率之间的关系，为实际应用中该算法的参数设定提供了依据。然后，针 对n m f 在i c a 中的应用局限，本文提出了带平移的非负矩阵低秩分解算法，将 非负矩阵分解扩展到了无非负限制的领域，使得该算法可以在更广阔的i c a 领 域中获得应用。最后，为改善独立组分提取的效果，本文还提出了平滑化方法 及分级提取方案，使得提取的独立组分更加符合实际。 本文具体内容安排如下：第一章是引言部分，主要介绍了降维的背景、研 究现状以及本文贡献；第二章是对稀疏度量的讨论及向量稀疏逼近的计算；第 第一章引言 4 三章就原有的非负矩阵分解算法提出了基矩阵归一化的概念及方法；第四章给 出基矩阵归一化及矩阵稀疏分解算法在人脸识别领域的实验效果。第五章介绍 带平移的非负矩阵分解算法及分级提取与平滑化方法的概念。第六章是i c a 的 部分数值实验结果，第七章是文章总结。 第二章非负向量的稀疏逼近 2 1非负向量的稀疏性度量 通常所说的稀疏性与非零矩阵中零元的个数所占的比重有关，与元素的符 号及顺序无关。对于非零向量z ，记忙1 1 0 为向量的非零元素个数，称为0 _ 范数，则 稀疏值可简单定义如下： s p o ( x ) = 尝【o 1 】 我们称为向量的0 - 稀疏值。这种定义比较直观，对于礼维向量来说，它的值域是 区间【0 ，1 】的几个等分点( 包含0 和1 ) 。 注意到，如果向量的零元或者小元素受到微小的扰动( 如零元变成e ) ，向量 的阻稀疏值会有较大的偏离( 至少为丢) 。为解决这种不确定性，通常考虑寻找 一个逼近s p o ( z ) 的连续函数作为稀疏值的定义。 2 1 1 现有的稀疏值定义 由于向量的稀疏值与元素符号无关，即s p 0 ( i x i ) = s p o ( z ) ，因此，只需考虑 z 7 已华兰 z 7 ：珥i z t 0 ，i = 1 ，2 n ，z o ) 的稀疏值定义即可。 给定非零向量z 冗军，令( z ) = 丽l l = i l l ，容易验证 1 e ( x ) 而 文 1 3 h h 将 s 嘶) = 而4 - a - e ( x ) 。，1 】 作为z 的稀疏性值定义，我们称为向量的1 一稀疏值。 另一种定义是 s p 2 ( z ) = 、n - = e ( z 广) 2 【。，1 1 ( 2 1 ) ( 2 2 ) ( 2 3 ) 第二章非负向量的稀疏逼近 6 我们称为向量的2 稀疏值。 显然，s p l ( x ) - 与s p 2 ( z ) 都是关于z 的连续函数。更一般的，稀疏值定义通常 具有如下性质。 定理2 1 1 给定非零向量z ，则s p o ( z ) ，s p l ( x ) - 与s p 2 ( z ) 具有以下性质： j 当z 1 = x 2 = x 3 = = z n o ，则s p t ( z ) = 0 2 当z 只有一个非零分量时，s 耽( z ) = 1 3s p t ( z ) = s p t ( i x l ) = s p i ( n z ) ，a 冗 显然：s p l ( z ) 与s p 2 ( z ) 都将向量z 映射到了区间【o ，1 m ，并在定理2 1 1 中的 两种极端条件下与s p 0 ( z ) 重合。关于一般情形下两种稀疏值定义对s p 0 ( z ) 的逼近 误差，我们有以下定理。 定理2 1 2 对任一非零向量z ，i l k = i i x l l o ，则s p o ( z ) ，s p l 扛) 与s p 2 ( z ) 有： js p l ( z ) s p 2 ( z ) s p ( o ) 时，s p ( a ( s ) ) = 8 。 证明第1 ，2 ，3 ，条显然，下面证明第4 条。 不妨令z 冗他1 为向量a 的8 一最优稀疏逼近，z 7 为a 在z 方向上的投影，则 拈盎z ( 2 7 ) 第二章非负向量的稀疏逼近 1 0 显然s p ( x ) = s p ( z ) ，且i i 一一n l l 2 忙一o l l 2 。若z t g 是a 在某个方向的投影，则 必有i i 一一n 0 2 s p ( a ( s ) ) 8 忪一a l l 2 s 。由于n ( s ) 是关于s 的连续函数，o ( s ) 必是 集合吼的内点。定义球体 b r ( o ( s ) ) = z 7 护ii i z a ( s ) 1 1 2 r ) 则存在一个r ，使得耳( o ( s ) ) cq 。球体b ( n ( s ) ) 中必存在一点z ，使得 忙一0 0 8 。这与n ( s ) 是。的s 一最优稀疏逼近矛盾，故假设不正 确，s p ( a ( s ) ) = 8 ，定理得证。 - 为了简化问题( 2 6 ) ，我们给出如下定理。 定理2 2 2 给定非负向量a ，s 0 ，1 】，若z = n ( s ) ，记o o 冗惫是由8 的非零分 量构成的短向量，其中尼= l i x l l o ，t k i 殳s p ( a ) s 。记 n ( s 一1 1 + k s s t2 i ：广 第二章非负向量的稀疏逼近 如果z 是短向量o o 的一个s 1 - 最优稀疏逼近，则将z 按如下方式扩展所得的向 量z 冗n 必是长向量a 的一个8 一最优稀疏逼近。 证明记q 。的子集 ：t z ， 。 【0 i f 哟0 e l s e 人乞( s ) = z 7 已华l x i 0 ，s p ( x ) s ， 翰= 0 ， i f a i = o ) 由定理2 2 1 中第5 条知，问题( 2 6 ) 只需在集合虬( s ) 中求解。 对于任意z 虬( s ) ，记n 为口的非零分量组成的短向量，z 中对应元素组成 的短向量记为z ，则 忪一a i l 2 = 0 z 一a 1 1 2 显然s p ( z ) s s p ( z ) 8 1 ，于是，问题( 2 6 ) 等价于求解最优化问题 其中 霉观，慨一。i f 2 q 。，= x 7 已晕l z 0 ， s p ( x ) 8 1 显然，z 就是向量0 f i g s l 一最优稀疏逼近。于是问题( 2 6 ) 的解就, - j - 通过短向量最 优稀疏逼近问题的解加零得到，定理得证。 由上述定理，问题( 2 6 ) 归结为求一个不含零分量的向量的最优稀疏逼近问 题。因此，可进一步假定a 为正向量，记 m ) = n 一署( 几一1 ) ( s + 喜) ， ( 2 8 ) 容易验证：s p ( x ) s 等价于粤( z ) d ( s ) 。于是，约束集q 。可简化为 q 。= z 冗华 iz ( z ) 冬d ( s ) ) 第二章 非负向量的稀疏逼近 1 2 2 2 2 最优稀疏逼近的近似计算 给定正向量a ，一般地，求解问题( 2 6 ) 是困难的。我们首先考虑求取该问题 在保持向量2 - 范数情形下的解z ，在z 的基础上通过投影法来获得问题( 2 6 ) 的近 似解。 保持2 一范数的约束下，最优稀疏逼近问题有如下形式： m i nl i z o i l 2 ，s t 1 i x l l 2 = i l a l l 2 ，z q 。 ( 2 9 ) 由定理2 2 1 中单调性定理，当s p ( x ) 上的正交投影a 。记e 冗“为分量全为1 的向量，易证，e 上，事实上，对任意 的向量z 7 r 。，y 7 f s ，则 ( z - y ) 丁e = ( 兢一玑) = 兢一y i = 0 ttt 因此，e 是超平面丌8 的法向量。于是，a t r s 可表示为= a 一口e 的形式。由o 7 r 。可得 q = 1 咒( 1 1 n i i 。一d ( s ) 2 ) 定理2 2 3 设a 冗n 为正向量，且0 s p ( a ) 8 。令 如果 则 r s = ，仉= 三( 叫一m ) l i n | | 2 一 m i 。n a i 之q 8 i r 8 i l a ( 8 ) = r s a 一叩3 e ( 2 1 0 ) ( 2 1 1 ) 第二章非负向量的稀疏逼近 1 3 证明首先考虑超平面中满足条件l i x l l 2 = i l n i l 2 的向量的表示问题。记 e o = e 何为e 的单位化向量，q 。为e 的正交补空间的一组标准正交基，则 q = e o ，q 1 】构成了一个正交阵。易知，超平面丌s 可以表示为 任取z 7 f s 。由于 7 b = 8 钆一q i ziz 冗俨1 ) i i z 崦= 0 口几一q l z l l ；= i i e o ，q 1 r ( 一q ，z ) l l ；= ( e 吾口。) 2 + i i q t a 死一z i i ；， 且a 。故成立 z i l 2 _ 丢( m ) i i 。1 1 2 ) 2 + i i q t 一z i | ； 因此，如果i i x l l 2 = i l a l l 2 。则参数向量z 必满足 q t a 扎一z l l 2 = 无疑，我们可以将z 表示为 z = q t a “+ f l u ， 兰r 1 其中，u 为单位向量，虽p l l u l l 2 = 1 。将其带入z 的表达式，得 z = a 丌。一q i ( q t a 。, + f l u ) = ( j q 1 q t ) a 。一r l q l u 注意到q = 【e o ，q 1 为正交阵，故有j q , q t = e o e 百= l e e t 。将其代入上式并 再次应用性质。7 i s ，我们得到z 的简洁表示 z2 d ( s ) l l a l l 2 其中u 是任一, 一1 维单位向量。 e 一7 1 q 1 乱， 下面考虑z 与。的逼近性问题。由于j i q ，u l l 2 = 1 ，e t q l = 0 ，因而有 z n 嬷=e + r i q l u l l ；=i i n d ( ol l a l l =e 崦+ r j r 2 r l a ? q l u 上式表明：最小化忙一n i l 2 等价于最小化( a t q l 钍) 丁= u t ( q t a ) 。因此，最优向 量“必定为u = 一q o i | q o l l 2 。从而得到问题( 2 6 ) 在无非负性约束下的最优 解 z2 d ( s ) t l a l l =e - i - r l q ，q z i i q o i l 2 第二章非负向量的稀疏逼近 1 4 为进一步简化z 的表示，利用等式i i - l ；= 去h a i l ；+ i i q t n l l ； - 矢n q t a i 2 = 兰您 再次利用i q , q t = l e e t ，并结合上式，得 ：型剖!e+垒(jleetx) 。= - i e 十一i 一 j o ：型必兰e + 尘( n 一业e ) 一一r 。t 。一l - j 一一r - =三(d(s)11口112一沙iin，) e + 薏口r 2r 2 = 考( d ( s ) 1 1 n 1 1 2 一r s i i n l l t ) e + r 8 n = 一仇e + r s a ， 其中7 _ 。三，r _ l 。由条件( 2 1 0 ) 可验证若x 非负，则z 即为n 保持2 一范数情形下的最 优稀疏逼近。 一 若a 不满足上述定理中的条件( 2 1 0 ) ，则m ( 2 1 1 ) 定义的向量z = r s a r i s e 可 能存在负元。此时x 不是问题( 2 9 ) 的解。对于这种情况，我们将n 中对应z 的负 元的位置置零，再进行求解。注意，此时得到的结果茁不再满足忙1 1 2 = i l a l l 2 。 由定理2 2 1 中第4 条，最优解是向量a 在某个方向上的投影。故可在求得近 似逼近z 后，定义 a t x 。卜蕊z 以获得更好的逼近。 综上，我们给出s p a 算法如下。 算法2 2 1 z = s p a ( a ，8 ) 1 记录原向量口= a 。 2 计算d ( s ) = 、佗一i ( 佗一1 ) ( s + j ) ，z ( n ) = 涨，若粤( 口) d ( s ) ，则z = 。，结 束程序。 3 判断：若n 的非零元全部相等，则取d 2 ( s ) 的整数部分，保留。的前个正元，其 余置零，得到向量z ，结束程序。 第二章非负向量的稀疏逼近 1 5 4 计算 仉2 赢( l l n i i t d ( s ) l l n l l 2 ) 5 令a 卜r s a + 一仉s i g n ( a + ) ，若a 的元素均为非负，则z = a ，z d 贝, l ，a 卜q + ，转 步骤2 。 6 计算投影z 卜荔v t x z ，返回结果。 随着步骤3 和5 不断进行，z 中零元不断增加，终能获得非负向量，故该算法 一必定收敛。 2 2 3 最优稀疏逼近的其他解法 关于向量的最优稀疏逼近，p a t r i k h o 妒r 在文 1 3 】中也给出了另一种算法。 该算法基于向量的1 一稀疏值，不妨称之为s p a l 算法，其主要过程如下。 算法2 2 2 z = s p a i ( a ，8 ) 1 由1 稀疏值定义计算d ( s ) = 何一( 历一1 ) s 。 2 若i l a l l ，d ( 8 ) l l a l l 2 ，则z = a ，结束程序。 3 迭代： a 计算a 卜a + - - i - a s i g n ( a + ) ，其中q 使它满足a ：= d ( s ) l l a l l = 。显然 q 刊s ) 戕一赢 b 若a i 中含有负元，则。卜a p ，转步骤a 。 c 计算1 ，使得 a 卜( 1 7 ) 0 7 + 7 s i g n ( a + ) 满足| l o i i z = l i o i l 2 0 d 若n ，中舍有负元，则n 卜a t ，转步骤a 。 第二章非负向量的稀疏逼近1 6 4 令x 卜a ，返回z 。 显然，出现负元时，本算法直接将负元置零，而不是将对应位置的原向 量a 置零，这一点与算法2 2 。l 中的处理方法不同。 2 2 4 逼近效果比较 为了给出s p a 算法的结果，我们在m a t l a b 中生成一随机非负向量a ，设 定不同的稀疏阈值8 【0 ，1 1 ，求n 的s 一最优稀疏逼近，并与s p a l 算法所得结果进 行对比。本实验选取向量长度为礼= 1 0 0 0 ，由于两种算法采用的稀疏值定义不 同，为统一标准，此处均采用式2 4 中的定义。 ，两种求解方法的残差比较(n s s p a ls p a o 2 3 3 4 5 33 3 3 1 3 0 46 9 6 5 06 8 3 8 0 0 61 1 0 2 2 51 0 5 1 2 1 0 81 5 8 4 7 01 4 3 0 7 5 0 91 9 0 6 7 61 6 2 8 3 3 由上表，对于任意的8 0 ，1 1 ，算法s p a 的逼近残差小于s p a l ，即所得解具 有更好的逼近性。注意到，稀疏阈值s 偏大时，s p a l 的解出现了残差大于i i n i l 2 的 情况，显然，这是不可取的。事实上，若令m 为保留a 的任一非零元，将其它元素 置零后的向量，则必有l l n m l l l l a l i ，j | _ s p ( m ) = 1 ，向量a 的最优稀疏逼近z 应 有比m 更好的逼近性。由于算法s p a 的解是a 在某个方向的投影，所以残差不会 大于l i n l l 2 。虽然我们不能证明算法s p a 所得结果就是n 的s 一最优稀疏逼近，但逼 近效果要明显优于s p a l 算法。 第三章非负矩阵的稀疏低秩分解 3 1非负矩阵低秩逼近的求解 有了求向量稀疏逼近的方法，可进一步将其应用与非负矩阵的低秩分解问 题中。该问题可描述如下： 给定非负矩阵v 冗m 期及所降维数k ，求解最优化问题 m i n l i v w h il e w e n t 。l eh e t t y _ x “。 ( 3 1 ) 通常，称左边的矩阵w 为基矩阵，w 的各列表示原有数据的潜在模式，而 右边的矩阵日称为系数阵，代表各种模式在该数据点的强度。在一些特殊的领 域，还要求w 或日有一定的稀疏性以节省存储空间。 非负矩阵分解常见的求法假设逼近误差误差服从正态分布，结合梯度法得 到如下的迭代： w 卜w o ( y h r ) o ( w 日日r ) ， 日卜h o ( w t v ) o ( w t w h ) 其中。和分别代表两个矩阵元素的乘法与除法( 即点乘与点除) 。 p a t r i k h o y e r 在已有分解的基础上加入稀疏约束，给出了非负矩阵的稀疏低 秩分解算法，见文 1 3 】。以对日的各列进行稀疏化为例，该算法具体步骤如下。 算法3 1 1 【彬明= s n m f ( v k ，8 ，7 - ) j 设初值w = y ( ：，l ：后) ，h = v 0 ：k ，：) 。 2 迭代： 卜w 圆( y 日r ) o ( 彤日h t ) ， 日b 日o ( w t v ) o ( w r w h ) 第三章非负矩阵的稀疏低秩分解1 8 3 逐列计算h ，( - ，i ) = s p a r s e ( h ( ：， ) ，s ) ，然后 h 卜h l 卜w o ( v h 丁) o ( w 日日丁) 名1 5 d = i i v w h i l 2 f 7 - ，或迭代次数超过限制，则终止迭代。否则转步 骤幺 注：其中步骤3 中稀疏化方法s p a r s e p - 丁选择前面介绍的任一计算方法。 由于稀疏限制会增大逼近误差，降低收敛速度。在本算法中，我们减少了 步骤3 中的稀疏化操作次数，增加w 和日的迭代次数比，以加速收敛。 3 2 基矩阵的归一化 对于非负矩阵分解v = w 日，记叫i 和砰分别为矩阵w 的第i 列和日的第 j 行。显然有 叫j 九 = 兰竺a 危 。 、 。 从上式可以看出，由于上述矩阵分解算法未对基矩阵的范数做任何约束， 若将基矩阵的某一列乘以一个任意的正常数，同时将系数阵的对应行除以该数， 该分解的逼近效果不变。也即是说，如果对基矩阵或系数矩阵的范数不做任何 约束，则基矩阵的各列及系数矩阵各行在获得同样逼近效果的前提下，仍有一 定的随机性。在实际的运用中，需要将基矩阵通过一定的方式进行归一化，以 获得稳定的结果。 为得到稳定的基矩阵w ，需要对所得w 的列进行单位化，我们称之为w 的归一化。一般的，归一化后可表示为如下形式： y = w 日= ( 等，等等) ( 三! 萎 = 咖膏 ( 3 2 ) 关于归一化策略，有两种形式比较常见，一种是对w 的列进行2 - 范数单位 化，即啦= 1 1 w i l l 2 , 另一种则直接取啦= m a 翰l w i i ，如下的独立组分分析便采用 此种方式。 第三章 非负矩阵的稀疏低秩分解 1 9 在人脸识别领域中，非负矩阵分解( n m f ) 有着特殊的应用，具体背景见 第四章介绍。在本节我们根据人脸识别的特殊目的，寻找更适合于模式识别的 归一化方法。 3 2 1 用于图象识别的归一化策略 通常，人脸识别通过分析坐标向量日对图片的归属性作出判断，因此我们 确定归一化方案总的思路是：通过归一化使训练集对应的坐标向量日尽可能分 类聚集，将对应的系数通过式( 3 2 ) 作用到基向量w 上，进而改变测试集对应坐 标向量各分量大小，以期在测试集中各类对应也能获得较好的聚集。 由式( 3 2 ) ，q 可看作对日的各行的加权，不同的权值意味着该分量对人脸识 别的相对贡献率，这将直接影响实验效果。为得到较好的识别效果，我们根据 各分量的分类聚集程度来定义日的各个分量的类相关度，并以此来选择合适的 系数o l 进行加权。 记t 为类相关度向量，丁第t 个分量冗表示日的第i 行对分类的类相关系数。 则加权向量q 可如下定义： 7 ： 啦一蕊砸 将口代入式( 3 。2 ) ，即得到优化后的及日。下一节我们来专门讨论类相关度 t 的计算。 3 2 2 类相关度t 的计算 3 2 2 1 基于标准差的类相关度 在人脸识别中的应用中，类相关度t 的计算是加强分类聚集，完成基矩阵 归一化的关键。为得到较好的分离聚集，传统方法总是考虑使得类内方差最 小，类问方差最大。不妨设h 冗m 肌，共分为c 类，记g 为第i 类对应的列指标 集，i g l 为该类的列数，则样本总均值 h = 磊1 马 他一 第i 类坐标均值 疋2 网1 薹马 第三章非负矩阵的稀疏低秩分解 则类间方差与类内方差可定义如下： 2 虿1 夸网1 薹( b 谰( 吻固t ， 瓯= 虿1 ( 而一无) ( 而一无) t 一 ( 3 3 ) ( 3 4 ) 易见，协方差矩阵的对角元鼠( i ，i ) 及( i ，i ) 分别对应h 第i 行元素的类内方 差及类间方差。记向量兄为各分量对应的标准差比值，则有 咒= ( 3 5 ) 可以认为，h 中第i 行的类相关系数是关于尼的增函数，不妨定义为厂( z ) ， 则正= 厂( 尼) ，称之为基于标准差的类相关度丁。 实验证明，该方法定义的类相关度t 在大多数情况下能够较好地用于识别 领域的加权。 3 2 2 2 基于平均偏差的类相关度 通过实验可以发现，在聚集较好的簇中，若出现一些孤立点，则标准差会出 现一定范围的扰动。简单的，考虑标准差定义 厅一 z ，( z ) = 、y n r ( z ) = 、三( ( z 1 一牙) 2 + ( x 2 一牙) 2 + + ( z n 一牙) 2 ) 当存在某一点娩到均值点的距离远大于其他点时，则有( z ) 鲁。 在人脸识别领域内，偶尔会出现一些孤立点，如人加带副太阳镜，或配带饰 品等。在这种情形下，方差对孤立点敏感的特性有时会影响到人脸的识别准确 度。 考虑到上述方法的这一缺点，我们倾向于使用另一种叫做平均偏差的统计 量g o p 【1 9 】【2 0 】来代替标准差，g n p 定义为 g a p ( z ) = l ( i x l - 牙1 + i x 2 - - ：云i + + i x n - - 2 1 ) ( 3 6 ) 实验表明，标准偏差g a p l 匕标准差更加稳定。在出现少量孤立点的情形，平 均偏差g a p 受到的影响相对较小。事实上，我们有以下的定理。 第三章非负矩阵的稀疏低秩分解2 1 定理3 2 1 给定一系列数据x = x l ，x 2 ，x n ，有均值牙及标准差( x ) ，c a p ( x ) 为 由式( 3 6 ) 定义的平均偏差，则关于任一数据点，标准差及平均偏差的导数有 如下性质： i d u 。( 兢x ) l 而1 ， i d g a p ；( x ) i d x 昙 i、n 证明记y ( x ) 为数据集x 的方差，y ( z ) 对既求导得v 7 ( z ) ，则有 对瓤求导得： y ( x ) d u ( x ) y ( z ) = 代入可得 2 俑 ( x i n - 1 + 呈n 叫( 一扣知叫 d u ( x ) d x i z t z ( 3 7 ) ( 3 8 ) 显然有 i 警l 丽1 且当兢为孤立点而其他数据点聚集状态较好时，标准差导数的逼近于其绝对值 上界。式( 3 7 ) 得证。 另一方面，由式( 3 6 ) 得 佗g a p ( x ) 式( 3 8 ) 得证。 i 睾矿去 佗一1 几一1 、r 十r 2塾二1 2 0 3 时可直接取零。相关数值实验结果见第四节人脸识别的应用。 第四章人脸识别中的应用 人脸识别问题如下：给出训练集，内容为若干人中每人数张照片( 灰度图) ， 将每张照片的各象素点按列排成向量，作为该图片的数据。训练集中所有图片 的数据向量组合成矩阵y ，通过矩阵y 的变换发现训练集中人脸图片的潜在模 式，并希望通过这些潜在模式对训练集外一些人脸图片做出归属性的判断。 首先考虑人脸图片中潜在模式的形式，虽然人的面部各种器官都不同的纹 理，形状，大