（计算数学专业论文）基于矩阵分解理论学习的数据降维算法研究.pdf

学位论文独创性声明 本人承诺：所呈交的学位论文是本人在导师指导下所取得的研究成果。论文中除特别加以标注和 致谢的地方外，不包含他人和其他机构已经撰写或发表过的研究成果，其他同志的研究成果对本人的 启示和所提供的帮助，均已在论文中做了明确的声明并表示谢意。 学位论文作者签名： 学位论文版权的使用授权书 本学位论文作者完全了解辽宁师范大学有关保留、使用学位论文的规定，及学校有 权保留并向国家有关部门或机构送交复印件或磁盘，允许论文被查阅和借阅。本文授权 辽宁师范大学，可以将学位论文的全部或部分内容编入有关数据库并进行检索，可以采 用影印、缩印或扫描等复制手段保存、汇编学位论文，并且本人电子文档的内容和纸质 论文的内容相一致。 保密的学位论文在解密后使用本授权书。 学位论文作者签名： 指导教师签名： 签名日期：1 乡年j 胡乃徊 辽宁师范大学硕士学位论文 摘要 随着信息时代的到来，科研工作中经常会遇到大量的高维数据。例如图像检索、模 式识别、人类基因分布、特征分类等。为了便于数据分析和探测数据的内部结构，通常 采用数据降维的方法。数据降维的目的是要找出隐藏在高维数据中的低维流形结构。由 于矩阵是数据全部信息的体现，为了更精准地探究数据的内部结构的变化，采用数学方 法是有必要的。矩阵分解理论尤其是以二维矩阵的分解和张量的分解的学习是近年来出 现在人工智能领域中的一种重要方法，并且在探索数据降维方面取得了令人瞩目的成 果。 近年来，出现了许多有效的基于流形学习的数据降维方法。主要包括主成分分析 ( p c a ) 、局部线性嵌2 n ( l l e ) 、线性差别分析( l d a ) 、和近邻保留嵌入( n p e ) 等。这些算 法都是典型的一维数据降维方法，并且已经广泛的应用于数据降维、模式识别及特征提 取等领域。一维数据降维方法只能处理向量化的数据，数据的向量化过程会导致部分有 用的信息丢失，而且高维数据的向量化表示会引发维数灾，导致计算复杂程度加大。这 些是一维算法所面临的问题。目前，科研工作者针对这一类问题，以矩阵分解理论为基 础，抽象出采用二维矩阵分解和张量分解的数据降维思想，并提出了许多有效的基于矩 阵分解理论学习的数据降维方法。主要包括二维主成分分析( 2 d p c a ) 、二维线性差别分 析( 2 d - l d a ) 、张量局部差异分析( t l d e ) 、以及张量子空间分析( t s a ) 等。 本文以矩阵分解原理为基础，全面的分析了现有的数据降维方法，并总结出数据降 维算法理论中的重要原理，重点研究了n p e 算法并对其进行了修正改进。本文的主要 工作包括： ( 1 ) 从矩阵的奇异值分解和张量的高阶奇异值分解两个方面，结合张量子空间分析 ( t s a ) 和张量近邻保留嵌x , ( t n p e ) 两个算法，研究矩阵分解理论与降维的结合及应用原 理。 ( 2 ) 近邻保留嵌n ( n p e ) 作为一种降维算法，需要先进行矩阵向量化，但是原始数据 ( 图像矩阵) 的维数通常过大，容易造成一些有用的信息丢失，不能充分的反映原始数 据内部的几何拓扑特征。针对这一缺点，我们提出了一种基于矩阵分解理论学习的算法 二维近邻保留嵌a ( 2 d - n p e ) 。 关键词：数据降维；奇异值分解；高阶奇异值分解；近邻保留嵌入( n p e ) ；二维降维理 论 爹 辽宁师范大学硕士学位论文 r e s e a r c ho nd a t ad i m e n s i o n a l i t yr e d u c t i o na l g o r i t h m sb a s e do nm a t r i x d e c o m p o s i t i o nl e a r n i n g a b s t r a c t w i t ht h ei n f o r m a t i o na g e sa r r i v a l ，w ea l w a y se n c o u n t e rm a s s i v eh i g h d i m e n s i o n a ld a t a i n e v i t a b l yw h e nd o i n gr e s e a r c h e s ，i n c l u d i n gi m a g e v i d e or e t r i e v e d , p a t t e r nr e c o g n i t i o n , h u m a ng e n ed i s t r i b u t i o n ，f e a t u r ec l u s t e ra n ds oo n i nn o r m a lc a s e ，w eu s et h ew a yo f d i m e n s i o n a l i t yr e d u c t i o nf o ra n a l y z i n gd a t aa n dm a k i n ga ni n v e s t i g a t i o no nt h ei n t e r n a l s t r u c t u r eo fd a t a 砀eg o a lo fd i m e n s i o n a l i t yr e d u c t i o ni st of i n dt h el o w - d i m e n s i o n a l m a n i f o l ds t r u c t u r ee m b e d d e di nt h eh i g h - d i m e n s i o n a ld a ms e t t oi n v e s t i g a t et h ev a r yo ft h e i n t e r n a ls t r u c t u r eo fd a t ap r e c i s e l y ，i ti se s s e n t i a lt ou s em a t h e m a t i c a lm e t h o df o rm a t r i xc a l l r e f l e c ta l li n f o r m a t i o no ft h ed a t a t w o d i m e n s i o n a lm a t r i x d e c o m p o s i t i o na n dt e n s o r d e c o m p o s i t i o no fm a t r i xd e c o m p o s i t i o nt h e o r y i sa ni m p o r t a n tm e t h o do fa r t i f i c i a l i n t e l l i g e n c el e a r n i n gr o s ei nr e c e n ty e a r s ，i th a sa r c h i v e dr e m a r k a b l es u c c e s s i 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 n i nr e c e n ty e a r s ，t h e r eh a sa l r e a d yd e v e l o p e dm a n ye f f e c t i v e l yd a t a d i m e n s i o n a l i t y r e d u c t i o nm e t h o d sw h i c ha r eb a s e do nm a n i f o l dl e a r n i n g m a i n l yi n c l u d m gp r i n c i p a l c o m p o n e n ta n a l y s i s ( p c a ) ，l o c a l l yl i n e a re m b e d d i n g 皿l e ) ，n e i g h b o r h o o dp r e s e r v i n g e m b e d d i n g 呷e ) a n ds oo n t h e s et y p i c a lo n e - d i m e n s i o n a lr e d u c t i o nm e t h o d sh a v em a n y a p p l i c a t i o n si nd a t ad i m e n s i o n a lr e d u c t i o n , p a t t e r nr e c o g n i t i o na n df e a t u r ee x t r a c t i o n n e o n e d i m e n s i o n a lr e d u c t i o nm e t h o dc a no n l yw o r kw i mv e c t o r i z e dd a t aw h i c hm a yn o tc a p t u r e w e l ls o m eu s e f u li n f o r m a t i o ni nt h eo n g j n a ld a t a m o r e o v e r ，h i 幽一d i m e n s i o n a lv i e t o r i z e d r e p r e s e n t a t i o n sa l s o s u f f e rf r o mt h ec l n s eo fd i m e n s i o n a l i t ya n dt h eh i g hc o m p u t a t i o n a l d e m a n d t h e s ea l ea np r o b l e m st h eo n e d i m e n s i o n a lr e d u c t i o nm e t h o dh a s a tt h ep r e s e n t t i m e ，s c i e n t i f i cr e s e a r c hw o r k e r sh a v es u m m a r i z e dt h ed a t ad i m e n s i o n a l i t yr e d u c t i o nt h e o r y w h i c hu t i l i z i n gt w o d i m e n s i o n a lm a t r i xd e c o m p o s i t i o na n dt e n s o rd e c o m p o s i t i o nb a s e do i l m a t r i xd e c o m p o s i t i o nt h e o r yt os o l v et h o s ep r o b l e m s m a n ye f f e c t i v e l yd a t ad i m e n s i o n a l i t y r e d u c t i o nm e t h o d sw h i c ha r eb a s e do nm a t r i xd e c o m p o s i t i o nt h e o r y1 e a r n i n gh a v ea l r e a d y b e e np r o p o s e d , m a i n l yi n c l u d i n gt w o d i m e n s i o n a lp r i n c i p a lc o m p o n e n t a n a l y s i s ( 2 d p c a ) ， t w 0 一d i m e n s i o n a ll i n e a r d i s c r i m i n a n ta n a l y s i s ( 2 d l d a ) t e n s o rl o c a ld i s c r i m i n a n t e m b e d d i n g ( t l d e ) ，t e n s o rs u b s p a c ea n a l y s i s ( t s a ) a n ds oo n 砸sp a p e ri sb a s e do nm a t r i xd e c o m p o s i t i o nt h e o r y ，a n a l y z e st h e e x i s t i n gd a t a d i m e n s i o n a l i t yr e d u c t i o na l g o r i t h m sc o m p r e h e n s i v e l ya n ds u m m a r i z e st h ei m p o r t a n tt h e o r y o fd a t ad i m e n s i o n a l i t yr e d u c t i o na l g o r i t h m s i tp u t se m p h a s i so nn p e a l g o r i t h ma n dp r o p o s e s i t si m p r o v e da l g o r i t h m t h ef o l l o w i n gi n n o v a t i v ew o r k si nt h i sp a p e ri n c l u d e s ： 一i i 基于矩阵分解理论学习的数据降维算法研究 ( 1 ) c o m b i n e dw i t ht w oa l g o r i t h m so ft e n s o rs u b s p a c ea n a l y s i sa n dt e n s o r 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 ，w e d i s c u s st h e t h e o r yo fa p p l i c a t i o n s f o r d i m e n s i o n a l i t yr e d u c t i o nb a s e d o nt h e s i n g u l a r v a l u ed e c o m p o s i t i o no fm a t r i xa n d h i g h e r - o r d e rs i n g u l a rv a l u ed e c o m p o s i t i o no ft e n s o r ( 2 ) t r a d i t i o n a la l g o r i t h mo fn 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 gf t 印e ) w h i c hh a sb e e n u s e df o rd i m e n s i o n a l i t yr e d u c t i o nn e e dt r a n s f o r mt h eo r i g i n a ld a t ai n t ov e c t o r s b u tt h e d i m e n s i o no ft h eo r i g i n a ld a t aa l eu s u a l l yh i g h , a n dt h ev e e t o r i z e dd a t aa l s ol o s ts o m eu s e f u l i n f o r m a t i o ns ot h a tt h ei n t r i n s i cl o c a lg e o m e t r i ca n dt o p o l o g i c a lp r o p e r t i e so ft h eo r i g m a ld a t a c o u l dn o tb ee s t i m a t e d t h e n ，an e wt w o d i m e n s i o n a ln 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 ( 2 d - n p e ) i sp r o p o s e df o rs o l v et h et h i sp r o b l e m , w h i c hi sb a s e dd i r e c t l yo nm a t r i x d e c o m p o s i t i o nt h e o r yl e a r n i n gf o rd i m e n s i o n a l i t yr e d u c t i o n k e yw o r d s ：d i m e n s i o n a l i t yr e d u c t i o n ；s i n g u l a rv a l u ed e c o m p o s i t i o n ；h i g h e r - o r d e r s i n g u l a r v a l u e d e c o m p o s i t i o n ；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 ( n p e ) ； t w o d i m e n s i o n a ld i m e n s i o u a l i t yr e d u c t i o n - i i i - 一 辽宁师范大学硕士学位论文 目录 孑商要i a b s t r a c t i i l 绪论一l 1 1 研究背景一l 1 2 预备知识2 1 2 1 流行学习2 1 2 2 张量3 1 3 本文研究内容_ 6 1 4 论文组织结构6 2 矩阵分解理论在降维中的应用8 2 1 引言8 2 2 奇异值分解( s v d ) 与张量子空间分析( t s a ) 一9 2 3 高阶奇异值分解( h o s v d ) 与张量近邻保留嵌h ( t n p e ) 1 0 2 4 矩阵分解在降维中的应用原理1 1 2 5 小结11 3 一种基于近邻保留嵌入的算法( 2 d - n p e ) 1 2 3 1 引言j 1 2 3 2n p e 算法回顾1 3 3 3 改进的n p e 数据降维方法( 2 d - n p e ) 1 3 3 3 1 构造流形空间上的邻域g 1 4 3 3 2 算法及推导1 4 3 3 3 2 d - n p e 算法1 5 3 4 实验对比分析：18 3 5 小结1 9 结论：2 0 参考文献2 2 攻读硕士学位期间发表学术论文情况2 4 致 谢2 5 嚣黔。 ，詹 7 i 辽宁师范大学硕士学位论文 1 绪论 1 1 研究背景 在当今高速发展的信息时代，人们在模式识别和计算机视觉领域研究数据的获取变 得越来越方便快捷，对数据提取和处理的方法也越来越多样化。然而，在现实世界中， 数据集更新加快，复杂程度加大，伴随着数据维数也增高，由于处理技术的落后，使人 们在特征提取和数据降维研究中把原始数据压缩到一个低维子流形空间的过程时，造成 了重要信息资源的不必要流失，导致人们不能很好的利用数据资源对客观世界进行较丰 富，较细致的描述和刻画。因此，如何能在保持数据信息资源足够完整性的基础上从大 量的高维数据信息中提取出有效的简约数据资源，同时避免数据的维数灾和计算程度复 杂化等问题，俨然已经成为满足人们感知需要和计算机视觉领域的研究重点。 人们在机器学习中所面临的研究数据多数来源于客观世界，客观世界中事物的复杂 性赋予了这些信息资源数据结构的复杂性和数据维数的高维化，于是降维成为人工智能 领域中最基本，最重要的问题。一方面，数据降维通过映射变换把高维数据投影到低维 流形空间上，同时保持原始信息的数据资源内部的几何拓扑性质不变；另一方面，复杂 的高维数据资源中，并非所有信息的数据资源都是重要的，有意义的，通过数据降维， 使高维数据以低维形式表示，筛选出了重要的信息资源，使后期的数据计算和处理变得 没那么复杂。因此，数据降维成为人工智能领域中的必要手段。 通常情况下，人们在数据降维中所寻找的最优映射与矩阵分解理论有着重要的联 系，这就使得矩阵分解理论在机器学习中扮演着重要的角色。在传统的数据降维方法中， 人们通常采用的都是把原始信息的数据资源转化为向量形式的技术，然而在向量化的这 个过程中，由于原始信息的数据资源维数往往过大，数据内部结构异常复杂，在筛除掉 大量的冗余信息的同时伴随着部分重要的相关信息丢失，而且后期的计算复杂程度也很 大。针对这一类问题，人们开始转变思维，使得张量思想进入了数据降维的世界。所谓 的张量思想，就是算法直接应用于高维数据资源的一种处理技术。高效的数据降维处理， 不仅可以在一定程度上减轻数据资源维数灾所带来的影响，促进高维数据的分类，还可 以避免了原始信息的数据资源向量化所带来的复杂计算和部分重要信息的不必要丢失， 这使得降维理论在人工智能领域上成功的迈进了一个台阶。目前，以矩阵分解理论学习 的基于二维矩阵和张量的数据降维方法理论已经成为人工智能领域内的研究热点之一。 ， 基于矩阵分解理论学习的数据降维算法研究 1 2 预备知识 1 。2 1 流行学习， 数据降维是指通过线性或非线性映射将数据从高维空间映射到低维空间，并且保持 数据内部的几何拓扑性质不变。从几何学角度上分析，数据降维可以看成是挖掘嵌入在 高维数据中的低维线性或非线性流形，这种嵌入保留了原始数据的几何特性。流形学习 的本质是当采样数据所在的空间为一个低维的光滑流形时，要从采样数据研究出低维流 形的内在几何结构或规律性质。 流形是一个局部可坐标化的拓扑空间，从拓扑空间的一个邻域( 开集) 到欧式空间的 开子集的同胚映射，使得每个局部都可以坐标化。 定义1 1 集合x 上的一个拓扑就是x 的子集的一个族f ，它满足以下条件： 辽宁师范大学硕士学位论文 其中岛表示噪声，y ，ycr j ，d o ，c r , ( i = 1 , 2 ，) 为矩阵么的正 奇异值。 利用矩阵变换，( 2 1 ) 式我们可以变形为得： 醐圳彳矿 ( 2 - 2 ) 根据矩阵“左乘列变换，右乘行变换 的运算法则，当( 2 2 ) 式中的u 和y 的阶数发 生改变，u r , 4v 的阶数也会随之发生改变。 例2 2 v , 4 r 雕。”，j u r “。西和v r 8 。屯，贝u 有b = u r , 4 v r 西。吒( 嘎 t n ，畋 刀) 且u 和y 为正交矩阵。 例2 2 表明对于任意的m 刀阶的矩阵彳，通过两个正交矩阵的乘积运算，可以得到 4 x 畋阶的矩阵召，并且4 m ，畋 n 。它的实际应用意义是对于一张m x n 维的图片， 我们可以寻找到两个正交变换，通过映射降为碣攻维的图片。 张量子空间分析( t s a ) 就是利用了例2 2 的原理。对于流形空间上的m 个数据 z 。，x 2 ，- ，以，其中五r or 也，通过寻找两个最优正交转换矩阵u r 硝和 矿r 掣如，使个原始数据映射到低维空间上的巧，e ，l ，其中z r 1 , 。如( ， 乞 吃) ，并且满足关系式誓= u r x , v ，i = 1 ，2 ，肌。利用奇异值分解( s v d ) 原理，张量 子空间分析( t s a ) 把原始数据五转化成新的数据墨，维数从啊x n 2 的高维空间降低到 乞的低维流形空间，并且数据内部的几何拓扑结构保持不变，而u 和矿可以通过该 算法的最优化问题求解来确定，这样我们就达到了降维的效果。 i 基于矩阵分解理论学习的数据降维算法研究 2 3 高阶奇异值分解( h o s v d ) 与张量近邻保留嵌a ( t n p e ) 高阶奇异值分解( h o s v d ) 是近年来比较热门的一个研究题目。它是在奇异值分解 ( s v d ) 理论的基础上发展起来的，以矩阵分解为基础，针对张量进行分解，在张量空间 作用达到降维。越来越多的学者开始关注张量分解，从事张量分解的研究，使得高阶奇 异值分解在降维中的应用日趋广泛。在上一章我们复习了张量的相关知识，下面我们重 点探究高阶奇异值分解( h o s v d ) 和数据降维算法的具体结合应用。 上一章的定理1 1l 我们知道了对于高阶张量有如下的奇异值分解( h o s v d ) ，即 v y r i , 。1 2 ”。k ，有y 。形】u ( 1 ) 2 【厂( 2 ) u ( ) ， ki ，i ” 其中元素为k 妇= 纥小知u o ) ，吧哦 h 1j 2 乱j n 一1 根据上一章的定理1 1 1 和性质1 9 ，我们可以推出，对于x r i , 。如”。i x ，u r l ， 】厂= x 。u r 1 2 ”。i 一- 1 x j x l + i x “，当矩阵u 的行阶发生改变时，】，的阶数也会发生 改变。下面的例子就很好的说明了阶数的变化。 例2 3 vx r 。如”。i x ，u ( r a , 。( f = 1 , 2 ，) ，贝i j 有： y = x x lu 0 ) 2u 2 u r 西。d 2 ”。如 ( 2 3 ) 当例2 3 中的u ( 为正交矩阵时，( 2 3 ) 式为张量近邻保留嵌a ( t n f e ) 的降维思想。 张量近邻保留嵌) k ( t n p e ) 主要是利用高阶奇异值分解和张量运算法则，针对张量空间上 的数据进行降维。对于张量空间上的万个数据五，五，e ，其中五r 耶7 ：”， 我们的目标是寻找k 个最优正交矩阵u o r d s x l t ( 或 厶，i = 1 , 2 ，k ) ，使原始数据映 ， 射成低维流形空间中的新数据五，e ，e ，其中z r 小d 2 ”，并且满足关系式： z = j l u 0 ) 2 u 2 ) 七u 七( f = 1 , 2 ，刀) 、(24) 张量近邻保留嵌a ( t n p e ) 算法是把原始数据五映射成新的数据鬈，而维数由 五l x , 降为盔畋畋，同时原始张量数据的内部几何拓扑结构保持不 变。 推论2 4 定理1 1 1 有如下变换： y 2 彬1 u 1 2 u 2 u 胁 。 以) = u 4 败。) 妙斛1 u 2 o 【厂聊o u 1 9 u ( n - 1 ) ) ( 2 5 ) 其中，圆表示k r o n e c k e r 积1 7 】。 。亭 。 鬻辽宁师范大学硕士学位论文 推论2 4 的意义在于把张量的运算转化成矩阵的运算，结合推论和矩阵的运算，我 们可以知道奇异值分解( s v d ) 和高阶奇异值分解( h o s v d ) 之间的关系b 8 。 2 4 矩阵分解在降维中的应用原理 由于矩阵是数据全部信息的体现，而矩阵分解往往能从这些复杂的数据中提取出相 对重要的特征信息，因此，人们渐渐将矩阵分解越来越多的应用于维数约简等方面，这 使得矩阵分解理论在数据降维中的地位越来越重要了。因此我们结合多种算法总结出矩 阵分解在降维中的两个重要应用原理。 原理2 5 对高维空问r 舭再上的数据五，石2 ，x ，通过寻找两个正交矩阵 u r “d - 和y r 硝磊，满足：z = u r 五y ，f = 1 , 2 ，n ，得到低维流形空间r d t 列：上的 数据巧，e ，瓦( 西 m ，畋 刀) 正交矩阵u 和y 通过具体算法的目标函数利用最 优化问题来求解。 数据：置一z 维数：r 耐”专r 毛划2 原理2 6 对张量空间融。如”。知上的数据五，x ：，jx ，通过寻找个正交矩阵 u o r d l “，满足关系式】：- - x , iu 1 2u 2 u ( f = 1 , 2 ，) ，得到张量空间 r 西。心”划上的低维数据巧，e ，瓦( 呸 ) 正交矩阵u 可以通过具体的张量算 法所对应的目标函数利用最优化问题来求解。 数据：五一z 维数：r ，l 。1 2 ”村寸j 5 c d l d 2 ”如 上述两个原理主要是针对奇异值分解和高阶奇异值分解在当今多种降维算法中的 应用所总结出来的。通常，现实中高维数据往往是复杂的，这就需要我们把高维数据转 化成低维数据来研究，原理2 5 和原理2 6 为维数转化提供了很好的思想和工具。 2 5 小结 本章结合张量子空间( t s a ) 算法和张量近邻保留嵌a ( t n p e ) 算法，分析了奇异值分 解和高阶奇异值分解在降维算法中的具体应用，并总结出了两个具体的应用原理，这使 得我们对降维思想有了较深入的理解，同时为研究降维的学者们提供了较好的参考和工 具，激发学者们对多维线性代数的研究兴趣，进而有利于数据降维工作的进一步开展。 基于矩阵分解理论学习的数据降维算法研究 3 一种基于近邻保留嵌入的算法( 2 d n p e ) 为了特征提取和降维，在人工智能领域出现过很多方法。传统的邻域保持嵌入呻e ) 作为一种降维算法，需要先进行矩阵向量化，但是原始数据( 图像矩阵) 的维数通常过大， 容易造成一些有用的信息丢失，不能充分的反映原始数据内部的几何拓扑特征。针对这 一缺点，本章提出了一种新的二维近邻保留嵌入( 2 d - n p e ) ，该算法直接作用于图像矩阵， 基于图像矩阵实现降维。与传统的近邻保留嵌入q 冲e ) 相比，该算法解决了矩阵向量化所 导致的有用信息的不必要丢失问题，同时实验3 4 结果分析表明，在同等维数的特征空 间里，新算法的识别更有效率，精确性更高。 3 1 引言 目前，在模式识别和计算机视觉领域等方面，原始数据和图像空间维数往往过大， 这给特征提取和数据降维增加了困难，为了解决这一难题，人们根据一定目标的性能来 寻找一个线性或非线性的空间变换，把原始的数据信息压缩到一个低维子空间，从而使 数据在子空间中的分布更紧密，可以较好的对数据进行描述，同时也简化了计算程度。 p c a t 7 1 ，l l ee 9 1 ，n - p e t l 9 】等算法都是应用这一思想。在诸多传统的降维方法中，主要的 思想是把原始数据( 图像矩阵) 转化成向量，然后通过向量来寻找一个线性或非线性的映 射，把原始数据投射到低维流形空间，达到降维。但是，在原始数据转化成向量的过程 中，通常会导致原始数据的部分有用信息丢失，而实际操作中原始数据( 图像矩阵) 的维 数往往过大，也给矩阵转化成向量增加了计算的复杂程度。事实上，高维数据向量化的 复杂程度给传统的降维方法增加了难度，针对这一问题，人们提出了一种新的降维思想 张量思想，即算法直接作用于图像矩阵，不需要把原始数据转化成向量，也就避免 了矩阵向量化的复杂计算和有用信息的部分丢失。随着代数学的发展，人们根据张量思 想抽象出了一种新的降维方法一二维算法啪】，现今在人工智能领域涌现了多种基于 二维的降维方法，较为突出的有二维主成分分析( 2 d p c a ) n 们，二维线性差别分析 ( 2 d l d a ) 1 1 】，而后又出现了双向二维主成分分析( ( 2 d ) 2 - p c a ) t 1 2 】和( 2 d ) 2f l d t 2 1 1 等算 法。这些方法成功地应用了二维算法理论，使降维理论步入了一个新的台阶。 本章提出了一种新的基于近邻保留嵌入( n p e ) 的二维近邻保留嵌入( 2 d - n p e ) ，是一 种新的基于矩阵分解理论学习的降维方法。该算法直接作用于原始数据，避免了有用信 息的部分丢失和计算程度的复杂问题，应用二维算法理论，基于图像矩阵达到降维。 辽宁师范大学硕士学位论文 二维的算法理论，以矩阵分解理论为基础，避免了维数灾，减少了原始数据信息的 丢失，大大提高了图像识别和特征提取的精准性。通过上一章的阐述和以上分析，本章 主要是针对n p e 算法应用二维的算法理论，即2 d - n p e 算法。 3 2n p e 算法回顾 近邻保留嵌x ( r p e ) 是一种近似于局部线性嵌入( l l e ) 的数据降维算法。和传统的全 局降维方法不同，n p e 的目标是保持流形的局部邻域结构，可以作用任意数据点，其中 包括离散的样本点。n p e 算法是线性的，采取保持局部邻域结构，在实际应用中效率更 高，对离散值也没那么敏感。n p e 算法的具体描述如下： s t e p l 给出n 个样本数据点而，x 2 ，工。r “，寻找一组基彳r “d ，使样 本数据点在这组基的作用下映射成低维数据点y l ，y 2 ，y 。r jp 以) ，并且 满足变换：y t = a r 而 s t e p 2 与l l e 构建权值的方法2 2 1 类似，n p e 通过仿射矩阵s = & 。来构造邻域。 仿射矩阵通常可以采用权值或者热核的公式来计算得到。这里的仿射矩阵s 中的元素满 足：吩= 1 ，歹= 1 ，2 ，n s t e p 3 n p e 的最优化问题可以通过下面式子解决： 血私渺1 1 2 = 中而一p 吖材一r 彳。 j j a r 厨r a = i ( 3 1 ) 其中，m = ( ，一s ) r u s ) ，x = k ，x 2 ，x n ，】r = y l ，y 2 ，y 。r ，i 为刀露 阶的单位矩阵。使用l a g r a n g e 乘子法嘲，解得m y r = 2 y r ，取膨的值最小的d 个非零 特征值所对应的特征向量作为低维坐标】，。 3 3 改进的n p e 数据降维方法( 2 d - n p e ) 给定流形空间上n 个数据点五，五，以，其中x t r 删8 。2 d - n p e 算法的目 。标是寻找一个最优映射u r 榭( d m ) ，通过映射把原始高维数据投影为低维数据 巧，r 2 ，e ，其中z r 出4 ，i = 1 ，2 ，n ，同时保持流形空间的内部几何拓 扑性质不变。 3 3 1 构造流形空间上的邻域g 利用热核公式计算仿射矩阵s = 麒。， 基于矩阵分解理论学习的数据降维算法研究 圹 纛警呐4 2 一o 剐蛳吣一) 2 ， 其中，t 为j f 常数，( 足，4 ) 表示4 的k 邻域。 3 3 2 算法及推导 输入n 个样本数据点x 。，x ：，x 。r “4 ，寻找低维空间的一组标准正交基 u r ”d ，通过基的映射变换= u r 五r 幽“，我们就可以得到低维流形上的n 个输 出点五，e ，- ，e 。为了保持流形内部的局部结构，可由下面的优化问题实现。具体 推导过程如下： s t e p l 构造优化函数的推导： r a i n f c = 莩慨一手艺1 1 2 = 军p r 置一二s o u 1 1 2 = 加 ( u r 五- e u r x p ( u r x t - e u r x s ) r i jj ) = 驴 u r ( 置一勤x s ) ( 五一勤一) r u i l ， j = t r u r ( 墨- e 勤) ( 置一) r u ( 3 4 ) l l ，j j s t e p 2 约束条件的推导： 8 z0 2 = ( z l r ) = 纱妙r 五r 五) r = 护妙r x , x u ) = 纱妙r 五f u ) r 恽删卜l l j = 1 ( 3 5 ) 3 3 3 2 d - n p e 算法 辽宁师范大学硕士学位论文 m i n f ( v ) = 护v r ( 五一置) 一一) r u ki jj ) r、 豇驴u r 置f u = 1 ( 3 6 ) l i j 本章所提到的算法的具体步骤描述一般如下： 2 d - n p e 算法 s t e p1 输入初始化样本置，五，以，其中五r 嬲”； s t e p2 构造邻域g ，利用热核公式计算仿射矩阵s ； s t e p3 计算m ，并将其进行特征分解，得到特征值及对应的特征向量阵； s t e p4 取膨的前d 个最大特征值所对应的特征向量u ，最终得到影= u r 五。 ( 3 6 ) 式中的未知矩阵u 可以通过下面式子利用广义特征值的方法得到： ( 一s 扩乃) ( 置一j i ，) r 弦= 名( x t 祥弦 ( 3 7 ) ，j f 令m = ( 五一j 扩x j ) ( 置一) r ，那么u 为m 前d 个最大特征值所对应的 i ij 特征向量。 图3 1三类娜w 白c e 的数据集 f i g 3 1 t h r e et y p eo ff e y - 瑚【w f 犯ee i a t a 基于矩阵分解理论学习的数据降维算法研究 ( a ) 2 d - n p e 降至2 维分类结果 0 ( b ) n p e 降至2 维分类结果 图3 2f r e y - r a w f a e e 的数据集降至2 维效果图 f i g 3 2 2 - d i m e n s i o n a lr e s u l to ff r e y m w f a c e 一1 6 辽宁师范大学硕士学位论文 d i m o n $ 1 0 n a 图3 3 n p e ，2 d - n p e 算法f r e y - r a w f a c e 识别率曲线图 f 远3 3 c u r v eo f d i m e n s i o n a l a c c u r a c yr a t i ob yn p ea n d2 d - n p e ( a ) 2 d - n - p e ，2 d l d a ，2 d p c a ，p c a 算法的维数一识别率曲线图 一1 7 o_硒正eol善60墨 基于矩阵分解理论学习的数据降维算法研究 ( b ) 2 d - n p e ，2 d l d a ，2 d p c a ，p c a 算法维数一识别率数据表 51 01 52 02 53 03 54 0 2 d 二n p e0 5 2 2 2o 6 1 l l0 5 9 4 40 6 7 7 80 6 8 8 90 7 0 0 00 7 0 5 60 7 1 1 1 2 d l d a0 6 0 5 60 6 2 7 80 6 2 7 80 6 5 5 60 6 7 2 20 6 8 8 90 7 0 0 00 6 9 4 4 2 d p c a0 6 0 0 00 6 5 0 00 6 2 7 80 6 6 6 70 6 8 3 30 6 9 4 4o 6 9 4 40 6 8 8 9 p c a 0 3 3 3 30 5 4 4 40 6 3 8 90 6 6 1 10 6 6 1 10 6 6 1 10 6 6 1 l0 6 6 1 1 4 55 05 56 06 57 07 58 0 2 d o n p eo 7 1 1 10 7 1 6 70 7 1 1 10 7 0 5 60 7 1 1 10 7 0 5 60 7 0 5 60 7 0 0 0 2 d l d a0 7 0 0 00 6 9 4 40 7 0 0 00 6 8 8 90 6 9 4 40 6 8 8 90 6 7 7 80 6 7 7 8