（应用数学专业论文）高维复杂数据的有监督特征提取方法.pdf

摘要 当前数据维效的大幅增长给数据处理带来了前所未有的挑战，如何从这些高维复杂的数据中 发现事物的本质规律成为了迫切需要解决的问题作为处理高维数据中非常重要的前处理步骤一 效据降维一也就越来越受到人们重视对高维复杂数据降维方法的研究，是一个非常有挑战性 的问题，有着重要的理论价值，并在模式识别，生物信息学、数字图像处理等领域有着广瑟的应 用本文研究以数据的分类、可视化为目标的高维复杂数据降维的理论与方法，提出如下针对不 同情形的降维算法t 在基于可分性准则的前提下。针对且前缺乏有效降维算法的高维小样本数据集，提出了一种新 的有监督的特征提取算法一判别多维尺度映射( d i s c r i m i n a t em u l t i d i m e n s i o n a lm a p p i n g ，d m m ) 它是在结合了经典的多维尺度变换( c l a s s i c e dm d s ) 和线性判别分析( l d a ) 优点的基础上提出来 的d m m 算法能有效地处理维数远大于样本数的数据集，并且还有着很多良好的性质；计算量 小，无任何参数的设置，具有解析解文中给出了算法的理论支持，并通过大量的数值实验验证了 算法的有效性 当d m m 算法应甩于大样本数据集时，会出现计算量过大的问题本文引入l a n d m a r k 思想， 提出了适合高维大样本数据集的改进的d m m 算法一l a n d m a r k 判别多维尺度映射( l d m m ) l d m m 算法不仅能极大地减少计算量，而且参数设置简单灵活数值实验显示了算法的稳定性和 有效性 提出了基于流形结构数据集的特征提取算法一测地度量判别映射( g e o d e s i c - m e t r i cd i s c r i l n - i n a t em a p p i n g , g d m ) 它是在d m m 的基础上通过引入测地距离来保留数据分布在全局上的非 线性特性，从而实现了将线性降维算法d m m 到非线性降维算法g d m 的转化数值实验验证了 g d m 能使存在流形结构数据集的降维结果适于分类 当数据集存在流形结构，并且给定的样本点能近似逼近漉形时。i s o m a p 算法能有效地发现数 据的内在低维结构但是当部分数据缺失时，l s o m a p 算法中测地距离的计算会产生巨大的偏差而 使算法失效本文针对具有间断流形结构的敷据集提出了测地臣商的计算方法。推广了i s o m a p 算 法大量的数值实验表明它在数据缺失的情况下也能有效地发现数据的内有结构类似于i s o m a p ， 新的测地距离计算方法同样也适用于g d m 关键词； 特征提取，多维尺度变换，线性判别分析，流形学习，可分性准则。测地距商 a b s t r a c t n o w d a y st h ef a s ti n c r e a s i n gd i m e n s f o n m i t yo fd a t as e t sh a sb r o u g h tt r e m e n d o u sc h a 上l e n g ei n d a t ap r o o e 日i n g , e oi t su r g e n tt od i s c o v e rt h ei n t r i n s i ce t r u c t t t t o ft h ec o m p l e xd a t a 日e t 8w i t h h i g h - d i m e u s i a n a l i t y d i m e n s i o n a l i t yr e d u c t i o n , ni m p o r t a n tp r e p r o c e s s i n g 咖t oc o p ew i t hh i g h - d i m e n s i o n s ld a t as e t s ，h a sa t t r a c t e dc o n s i d e r a b l ea t t e n t i o n si nr e c e n ty e a r s i t sac h a l l e n g i n gw o r k t oe x t r a c ti n f o r m a t i o nf r o mc o m p l e xd a t as e t s ，w h i c hh a si m p o r t a n tt h e o r e t i c a ls i g n i f i c a n c ea n dw i d e a p p l i c a t i o n si np a t t e r nr e c o g f t i t i o n ，b i o i n f o r n n t i o n ，d i g i t a li m a g ep r o c e s s i n ga n d o n i nt h i sd i s s e r t a t i o n t h et h e o r i e sa n dm e t h o d so f d i m e n s i o n a lr e d u c t i o ni nh i g h - d i m e n s i o n a l m p l e x d a t a s e t a a r e s t u d i e d f r o mc l a r i f i c a t i o n a n d v i s u a l i z a t i o a 也w p o i n t s c o r r e s p o n d i n g t o d i f f e r e n t c a 8 民耽h a v ed e v e l o p e dm ”c e r a ln 唧f e a t u r ee x t r a c t i o nm e t h o d sb e l o w b a s e do f tc l a s s i f i c a t i o np r i n c i p a l w ep r o p o s eaf t e ws u p e r v i s e df e a t u r ee x t r a c t i o f ta l g o r i t h mc a l l e d d i s c r i i m n a t e m u l t i d i m e n s i o n a l m a p p i n g f d m m ) ，w h i c h i s e s p e c h l i y e f f e c t i v e f o rs m a l l s a m p l e d a t a s e t s w i t h h i g h - d i m e n s i o n a l i t y t h e a l g o r i t h m t a k e s a d v a n t a g e s o f c l a s s i c a l m d s a n d l d a , a n d m e a n w h i l e a v o i d st h e i rd i s a d v a n t a g e s d m mh a sm a n ya p p e a l i n g 触t i 删：翱n a 】4 凹c o m p u t a t i e n a lc o m p l e x i t y n op a r o j 口a e t e t 8t ob es e l e c t e d ，a n dh a v i n gf o r m a ls o l u t i o n w eg i v et h e o r e t i c a la n a l y s i so fd m m ，a n d d e m o n s t r a t ew i t hn u m e r i c a le x p e r i m e n t st h a td m mi se f f e c t i v ei np r a c t i c a lr i s e i f t h e n u m b e r o f d a t a i s v e r y l a r g e ，i t i s e x p e n s i v e f o r d m m i n p r a c t i c e t os o l v e t h i sp r o b l e m , w e d e s c r i b e a v a r i a t i o n o n d m m ( l d m m ) ，w h i c h w o r k s t r a c t a b l y w i t h v e r y l a r g e d a t as e t s ，a n d p r e s e r v e s t i l ea t t r a c t i v ep r o p e r t i e so fd m m t h e l e c t i o no fl a n d m a r kp a r a m e t e ri sf l e x i b l e a n dm u c ht - l o r e e f f i c i e n tc o m p a r i n gt om d dt h ee x p e r i m e n t sr e m t l t ss h o wt h a tl d m mc a n 舀wr e s u l t sa p p r o x i m a t e t o t h e o i l t p u to f d m m w ee x t e n dd m mf o rn o n - f i n s o rm a n i f o l d s a n dd e v e l o pan 哪n o n l h a s a rd i m e n s i o n a l i t yr e d u c t i o n m e t h o d c a l l e dg e o d e s i c - m e t r i cd i s c r i m i n a t em a p p i n g ( g d m ) g d mi m 糟t h eg e o d e b i cd i s t a n c et o e s t i m a t et h ei n t r i n s i cg e o m e t r yo ft h ei i n d e r i y i d 【gr e a r o l d ，i ou g l yn o m f i f t e a td a t as e t s db e s u e e 自s f u l l ye m b e d d e di nt h i sw a y i s o m a pa l g o r i t h mw a sp r o p o s e df o rl e _ a r o i f t gan o n l i n e a x l a n i f o i da n dh a db e e nd e m o n s t r a t e d i t s8 i i 代懒f ma p p l i c a t i o n st om a n yd 如e e t a h o w e v e r ，w h e um a n i f o l db 钱姗凹d i s c o n n e c t e d ，t h e b e t w e e n - r e g i o ng e o d e s i cd i e , r i c e sw i l lv a r yd r a s t i c a l l ya n di s o m a pc a n n o ta c h i e v ed e s i r a b l ee m b e d - d i n g w ed e v e l o pam e t h o dt oc o m p u t et h eb e t w e e n - r e g i o ng e o d e s i cd i s t a n c e s ，a n dt h e ng e n e r a l i z e i s o n m pf o ru n c o n n e c t e dm a n i f o l d s e x p e r i m e n t a lr e s u l t so n 目n t h e t i ca n dr e a ld a t ai l l u s t r a t et h e e f f i c i e n c yo ft h ep r o p o s e da i g o r i t h n t g d mc a n 幽h eg e n e r a l i z e df o ru n c o n n e c t e dm a n i f o l d sa st h e 8 a q l ew a y i s o m a p k e y w o r d s ：f e a t u r e e x t r a c t i o n , m u l t i d i m e n s i o n a ls c a l i n g 1 i n e a r d i s c r i m i n a t e a n a l y s i s ，m a n i f o l d l e a r n i n g ，c l a s s i f i c a t i o np r i n c i p a l ，g e o d e s i cd i s t a n c e 1 i 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得中国农业大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 研究生签名： 瑚晚泳 帆砰多月，多日 关于论文使用授权的说明 本人完全了解中国农业大学有关保留、使用学位论文的规定，即：学校有权 保留送交论文的复印件和磁盘，允许论文被查阅和借阅，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。同意中国农业大学可以用不同方式在不同 媒体上发表、传播学位论文的全部或部分内容。 ( 保密的学位论文在解密后应遵守此协议) 研究生签名： 导师签名： 瑚嘲 p 吣 前年月，；日 i 时间：，肿7 年石月，如 1 1研究背景及其意义 第一章绪论 随着信息时代的到来，数据集较以往有了显著变化，其主要特点可以归纳为，高数据量、高维 数、高数据增长率非结构化以及不能被人的感知单独处理比如在气象分析中，在某一对刻记录 的气温气压、湿度、降雨量等数据组成了个高维的变量，在不同地点不同时刻记录的所有记 录值则组成了个高维的数据集又如在人脸识别中，一幅2 5 6 2 5 6 的人脸图像，用计算机存储 就是一个6 5 5 维的向量一方面，随着维数的不断提高，数据集能够提供更多更完整的信息；另 一方面，我们面临着艰巨的问题，被信息淹没却又缺乏知识，即不能从数据中合理、有效地找到我 们所需要的知识如何在保持数据信息足够完整的意义下合理地约简数据集，来更好地描述数据 集的内在规律和满足存储、决策需求成为丁个亟需解决的同题 维数膨张引发噬数灾难( o f d i m e m i o n a l i t y ) ”，即要保持一定取样密度所需的样本数随 着维致的增加星指数级增长，给数据分析带来了重大的挑战维效灾难还常表现为模型的复杂程 度或模型的表示长度随着维数急剧增加，分类器的性能随着维致的增加迅速降低等 虽然致据集本身是高维的复杂的，但隐藏在这些数据集中的反映数据本质特征的信息却通 常是低维的，而且这些特征往往本质上不依赖于实际观测的维致以人脸识别为例，y a l e 人脸图 像数据库s 1 j 包含了l o 个人的5 8 5 0 幅多姿态，多光照的图像每幅图的大小为1 2 8x1 2 8 。通过 行堆叠的方式将其转化为向量就是1 2 8x1 2 8 = 1 6 3 8 4 维尉这样大的个数据库，进行分类和识 别需要很大的存储量和计算量但是大脑却能在瞬间识别同个人在不同光照、不同姿态甚至扭 曲后的身份这说明这一图像数据的固有维教可能很低，也就是说高维观测数据变量可以用少量 几个影响因素来表示这种现象在几何上表现为数据点散布在低维光滑流形上，如图l - l 所示 将人脸图像按照光照，姿态等模式进行存储就可以使识别同题得到简化这一典型例子表明， 将数据的维数降到合适的大小。同时尽可能多地保留原始数据集的信息，在很多情况下是可行的 甚至是必须的 降维是指样本从高维输入空间通过线性或非线性映射投影到个低维空间。从而找出隐藏在 围1 - - 1 ：嵌人在1 6 3 8 4 ( 1 2 8x 1 2 8 ) 维的y a l e 人脸数据库b 的低维流形1 2 l 高维观测数据中有意义的低维结构降维的方式可分为两类，特征选择和特征提取特征选择是 指从原始特征中依据某些原则选取最有教的一些特征子集而特征提取是指对原始特征进行映射 ( 或变换) 。即对原空f 霹进行坐标变换，形成一些新的特征来表示样本【3 】本文涉及到的均为特征 提取技术数据降维主要有四个目的f 4 j 【5 】- 1 压缩数据到低维空同，可以降低存储要求。并简化计算复杂度 2 在剔除冗余信息的同时，也降低了噪声对原始数据的影响 3 从非结构化数据集中提取出某种结构化成分来反映数据集的规律，以便更好地用于识别问题 4 把数据投影到低维空间。特别是人眼可观测的二维或三维空间，可以实现高维数据的可视化， 发现数据的本质规律 统计学、微分几何学、代数学以及计算算法等的发晨为特征提取提供了数学理论基础，促进 了特征提取算法的快速发展其研究成果和技术已经广瑟应用于模式识别，生物信息学计算机 视觉、图像处理等众多领域如高维数据的可视化可昕化；人脸识别。文本分类、语音识别；基 于内容检索的模型；数据融合中豹插值；枧壤中三维对像的鼹踪和检测；基因表达分析中，用于检 测和区分不同的疾病和疾病类型等 1 2 研究现状 降维算法一般可分为线性方法和非线性方法线性方法能有效地发现线性子空间，且在数据内 插、外推，压缩、去噪以及可视化等方面已经被证明是非常有效的传统的线性降维算法中最著名的 有主成分分析( p r i n c i p l ec p o m ta n a l y s i s ，p c a ) 【6 】吲和多维尺度变换( m u l t i d i m e n s i o n a ls c a l i n g ， m d s ) 【8 】科翻其它线性方法有因子分析( f a c t o ra a l y 豳) 【l l 】线性翔别分析( 1 i n e a rd i s c r i m i n a t e a n a l y s i s ，l d a ) ( 1 2 】【13 】独立主成分分析( i n d e p e n d e n t “p e n a n a l y s i s ，i c a ) 【? j 【1 4 1 非负矩阵 分解( 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 ) 1 5 等 线性降维方法有着运算简便。并常能产生简单的解析解等优点它的理论基础建立在全局线性 假设之上，对于线性结构以及数据分布近似于线性的较小规模甸题，通常能够得到最优子空问 这些方法的局限性在于假设致据的固有结构是线性的。在简单化数据分析的同时，也可能扭曲了 对数据内在规律性的真实反映对于较大规模的效据集，数据的固有结构往往呈现非线性性，数 据分布明显弯曲，当曲率较大时，则不能再近似地认为样本取自线性子空间在这种情况下，线性 算法就不能正确地描述数据集的结构了如雹l - 2 所示，。s w i f o u ”是个二维可展曲面，传统 线性p c a 在数据集表现高度非线性的复杂分布时，不能有效地恢复其内在结构，而非线性降维算 法i s o m a p 成功地恢复了数据集的主要结构和分布方向 针对高维数据的非线性特性，发展了大量的非线性的降维方法，包括神经网络、遗传算法，流 形学习i 1 6 j 等早期的一些非线性降维算法，如s a m m o n 映射f 1 7 1 ，自组织映射( s e l f - o r g a n i z i n g m a p ，s o m ) 1 8 1 9 等，由于使用了梯度下降法等选代方法求解最优值，很容易陷入局部的极小值， 并且算法的最终结果受初始值，迭代次数和收敛精度等参数的影响很大 2 ( a ) ( b )( c ) 囝1 - 2 ；( a ) 三维空问 s w i t m - r o l l 曲面是二维平面在三维欧氏空同弯曲而成的( b ) p c a 的降维效果 c ) i s o m p 的降箍效果 近年来。微分几何的迅速发展和广瑟应用为流形学习提供了坚实的理论基础2 0 0 0 年，s e u g 等在s c i e n c e 上发表文章，提出感知可能以藏形方式存在，并在神经生理学上发现整个神经细胞群 的触发率可以由少量变量组成的函数来描述，如眼的角度和头的方向视觉记性也可能是以稳态 的流形存储【2 0 i 同年，以s c i e n c e 杂志上的两篇文章为标志【2 l 】【2 2 】。流形学习作为一种维敦约 简方法，开始受到国内外学者的广瑟关注，并成为个新的研究热点流形学习算法根据对数据 点之同相似度的定义方法分为两类。一是基于全局的方法，即计算每个数据点与所有其他数据 点的关系，建立全连接图；二是基于局部的方法，即考虑每个数据点与其领域内的点的关系。 如 近邻或近邻 基于全局的算法有等度规映射( i s o m e t r i cm a p p i n g ，i s o m a p ) 2 1 ，核主成分分析( k e r n e lp r i n c i p a l 唧鹏武a n s l y s i s ，k i ： c a ) 2 3 1 ，主蓝线( p 由d p a lc u h 谮，珏s 主曲线) 1 2 4 1 1 2 s t 等1 s o m a p 的基本 思想是用流形上的测地距离【g e o d e s i cd 矾a n c e ) 来代替欧氏距离。再使用标准的多维足变换进行降 维，从而既实现了对数据的降维，又保留了敷据分布在全局上的非线性特征k p c a 是p c a 的 非线性推广，其主要思想是把输入数据通过核变换映射到h i l b e r t 特征空间。然后在这个特征空间 执行线性p c a 此外，h a s t i e 和s t m t z | e 提出了主曲线，即一维主流形( 舛酗p a lm a n i f o l d s ) 的 概念从概率分布来看，主曲线满足自相合( s e l f - c o n s i s t e n t ) 特性，即主曲线上的每点是相应数 据集中投影该点的样本点集的期望平均主曲线也是线性主成分分析的非线性推广。与其不同是 的，主曲线反映了数据集的整体中间结构而非单纯的统计描述 基于局瓤的方法以局部线性嵌入算法( 蛐l i n e a re m b e d d m g ，l l e ) 2 2 l a p l a c i a n 特征映 射( l a p l a c i a ne i g e n m a p ) 2 6 1 2 7 等方法为代表l l e 和l a p l a c i a n 特征映射都是基于局部保序思 想来获得高维观测空问与低维结构在局部意义下的对应) 2 6 1 1 2 7 1 这类方法是用邻域内的某种线性 表示来描述数据内在的几何特性，再构造全域内数据点的权重系数来描述数据的几何结构类似 的方法还有局部切空间变换算法( b c 8 it a n g e n ts p a c ea l i g n m e n t ，l t s a ) 2 8 1 等 近年来，针对流形学习主要是无监督降维方法的特点，发展了大量的有监督算法b 鼽3 4 】此 外，针对流形学习对新来样本点般没有解析解的问题，文 3 5 - 3 z 等中都提出了推广的流形学习 算法 3 、，、砖一一 蔚唧哥；雾 潞 又 ，一， l i 7 田l _ 3 ：p c a 把二维坐标下的点( 左i 勘投影捌维直线t ( 右边) 【4 5 l 与早期的方法相比，上述的两类非线性降维方法都有很多明显的优点，如算法易于实现。算 法的最优值求解般可转化为求解矩阵的特征值问题，优化过程不会陷入局部的极小值，算法参 效简单，适用于有全局事线性结构的数据集等当然，这些算法有的也存在确定低维空间维敦的 问题和计算量过大的问题，针对这些问题，大量的文章f 3 8 1 4 4 1 提出了解决的办法 1 2 1 数据的线性降维方法 线性降维方法是寻找高维数据中的线性变量，来模拟原始数据的一种方法这里我们主要 介绍主成分分析( p r i d p a ic o m p o n e n ta n a l y s i s ，p c a ) 和多维尺度变换( m u l t i d i m e n s i o n a l 豫d h 峨 m d s ) 1 主成分分析( p c a ) 主成分分析是一种非常经典的线性降维方法p c a 的主要思想是找到一个投影映射。将 棒本从高维空问投影到低维于空问，使得它们在这个子空问中的方差尽可能大具体来说，就是 寻找一系列正交的关于初始变量的线性组合，称为主成分，第一主成分代表了数据最大的变化方 向，第二主成分代表了数据第二大的变化方向，对大多数数据来讲，前几个最大的主成分 能够解释几乎所有的方差。这样余下的主成分在满足信息损失最小的前提下被丢弃如图l _ 3 所 示，p c a 把二维坐标下的点投影到一维直线上的情况 设原始数据集x = 瓤攥l ，e p ，样本均值为孑= 毒龟，这个投影可以通过样本的协 方差矩阵的特征值分解获得， r c 僻) = 寺( q 一_ ) 溆一军广 ( 卜1 ) 。= 1 ( 膏= 钆，扣：l ，m ( 1 | 2 ) 这里凡是协方差矩阵o w ( x ) 的特征值，仇是对应的特征向量( 满足谚吩= 0i 五母地；1 ) 。 也称为主轴( p r i n c i p a l 把特征值按从大到小的腰序捧列a l 沁 。取最大的前 p 个特征值对应的特征向量组成投影映射w = h ，屹，划那么数据集x = 鉴。的主成分 变换为； 雏= w 1 慨一_ ) ，i = 1 ，2 ，( 1 3 ) 4 样本集从m 维降到p 维保留的方差比侧为 p# r = 凡0 - 0 - = 1i l 除了保留最大方差外，p c a 还有以下两个好的性质， 1 去相关性( d e c o r r i l a t i o n ) 投影后的样本y = h 席x 是不相关的 e ( y y t ) = e ( ( v r x ) ( w t x ) t ) = w e ( x x t ) w = w t c o ( x ) w = a ( 1 5 ) 这里a 是特征值矩阵，是对角阵从上可以看出投影后的样本之间的相关系数为零，即不相 关 2 重构误差最小( 1 e a s ts q u a r e sr e c o n s t r u c t i o n ) 对于样本龟，投影向量为玑= 胪( 以一莉，由 于是正变基，所以在原空问里重梅i = 鼽，那么p c a 重构误差为。 c = 0 ( ( 而一动一毛) 1 1 2 = ( 1 _ 6 ) = p + l 从上式可以看出p c a 在最小重构意义上是最优投影 2 多维尺度变换( m d s ) 对于一个效据集。通常我们感兴趣的数据特性不是每个点的具体位置，而是它们之间有 什么不同多维尺度变换是一种传统的寻求数据点之间差异性( 或相似性) 的降维算法它的 目标是使得原数据集中相近的点在低维空间仍然保持相近。远离的点仍然远离 对于数据集x = z ， 岛，五舻，记两点与之阿的差异度( 或相似度) 为d ( 弓) ， ，；i ，2 ，简记为奶差异度( 或相似度) 通常是一种距离测量，即两点越相似，它们 的距离越小常用的距离测量方法包括欧氏距离， m h a t t a n 距离m i n k o w s k i 距离、最大 范数等m i n k o w s l d 距离提供了定义高维空间距离的一般方法； 仇 奶= i 一巧k i l l p ( 1 - 7 ) t 代表致据维数，当r = 2 时，上式即为欧氏距离 设原始数据集对应的低维映像集为m ) 整- ，鼽舻，使得数据点在低维空间的距离屹= 扩钕，彩) 与高维空间相应距离奶尽可能接近通常不可能对所有的距离都实现屹= 奶， m d s 采用s t r e s s 函效来评估南和略的接近程度z 蜘。：障 ( 1 - - 8 ) 尺度因子一通常在0 l 幻一咯j 2 或“曙的基础上选择当白取欧氏距离时，就称为 经典的m d s ，在后面第二章还将从另一角度介绍这一方法 5 1 2 2 数据的非线性降维方法 由于我们面临的数据本身呈现广泛的非线性特性。非线性降维方法长期以来都是国内外学者 研究的主要方向这里我们介绍目前广惩关注的流形学习中的几个主要算法：等度规映射汹o m 酢 t i cm a p p i n g , 1 s o m a p ) ，局部线性嵌套算法( j 0 c a l l yl i n e a re m b e d d i n g , l l e ) 和拉普拉斯特征映射 ( l a p l a c = i a ne i g e n m a p ) 1 等度规映射( i s o m a 】p ) 等度规映射( 王岛o m p ) l 2 1 1 是t e n e n b a u m 等于2 0 0 0 年提出的一种非线性降维方法其基本思 想是当数据集具有嵌入欧氏空间的内在流形结构时，可以通过保距映射获得观测空问数据集在低 维空问的对应描述要在计算上可行，算法采用了图模型思想，通过设定局部领域值以获得局部 敢氏空问数据点之问的连通性，而在全局意义下，通过寻找各点在图意义下的最短路径来获得远 点之间的距离，并以这种距离来近似描述远点之闯的测地线距离在获得距离矩阵后，i s o m a p 采 用经典的m d s 方法来构造内在低维结构具体算法分以下三步： 算法1 2 1 ( i s o m a p 算法) 1 构造邻域图g 根据点戤，q 之闻的欧氏距离d 溆，巧) 定义近郐点，即著在黾的半径f 之内或者是戤的耳个最近邻点之一，则定义q 为冠的近邻点，连接魏和而，该边的长 度等于d ( 毛，) 2 计算最短路径长；在邻域图g 中计算任意两点嗣和弓之间的最短路径长如慨，q ) ，并以 此估计在拓扑空间m 中的测地距离d m 0 。，) 3 构造低维嵌入t 根据距离矩阵d c ，采用经典的m d s 方法构造保持拓扑结构的低维嵌入空间 y i s o m a p 用于恢复内在扁平的数据集时，效果较好( 如图l - 2 ) 所示对于存在内在曲率的低维瘴 形。s l i v a 针对流形学习中的保角映射问题提出了相应的g h m a p ( 血m n a i 1 8 m p ) 算法【4 6 】 与i s o n “p 算法惟一不同的是，d i s o m a p 对数据点之问度量的定义相郐边的度量形式转变为 陬一町肌压行面订面，这里的m ( i ) 是包含在数据点冠邻域内的数据集的平均匪离 2 局部线性嵌套算法( l l e ) 局部线性嵌套算法( l l e ) 2 2 认为流形上每一个局部邻域内的任意一点都可以描述为邻域内 其它点的线住表示，各个郐域之问的连接信息也可以通过相互重叠的部分得以描述，而这个线性 关系在映射时保持不变，这样即可以将原始致据映射到统一的个全局低维坐标系统，并保留邻 接特征具体的算法步骤如下； 算法1 2 2 ( l l e 算法) 1 邻域点确定= 用k 近郐或e 近邻法确定每个数据点的邻域点 2 计算权值矩阵，定义 妒( ) = l l 戤一锄1 1 0 - 9 ) j 6 考虑约束j = 1 同时，如果新和巧非邻域，则饵，i = 0 按最小二乘思想求解式 ( 1 曲) 的权矩阵w 3 由权值彬重构低维嵌入 ，。定义 p ( 1 ，) = l l 瓠一- 酽( i - i o ) j 其中+ = ”卵妒妒( ) 考虑约束i 玑。o 及莩玑好。7 ，求解 y 。24 叫叩( ” ( 1 1 1 ) 与l s ( m 且p 算法保持全局测地距离不变的思想不同l l e 强调在数据集结构不满足全局线性 结构时，观测空间与内在低维空间之问在局部意义下的结构可以用线性空间近似 3 拉普拉斯特征映射( l a p l a c i a ne i g e n m a p ) 要实现局部意义下的最优嵌套，b e l k i n 基于谱图理论提出岫特征映射 2 6 1 1 2 7 1 按谱 图理论，可以构造相应嵌入空间目标函数如下t ( 轨一珊) 2 w h ( 卜1 2 ) 其中权值矩阵1 1 0 采用j = e z v ( - l i 氟一q 酽i t ) ，r 核函数考虑在低维结构对域的约束 矿d f = 1 ( d “= h 0 ) 及防止数据集收缩至单点的约束矿d ，= 0 情况下，最小化( 1 - 1 2 ) 可对 j 应于求解下式的最小特征向量t 五，= d ，( 1 - 1 3 ) 其中d 为对角权矩阵，l = d w 为l a p l a c i ( 对称。半正定) 矩阵 与l l e 算法相似，l a p l a c i a n 特征映射也是基于局部保序思想来获得观测空问与低维结构在 局部意义下的对应与l l e 算法不同的是，该算法利用了l a p l a d a m b e l k i n 算子的特性i 国p l a c j a m b e l k i n 算于定义为浇形切空问上梯度向量的负散度函数，流形的最优嵌套可通过隶i d p l a d a n b e l h n 算于的特征函数来实现 与i s o m a p 方法不同，l l e 和l a p l a c i a n 特征映射采用了局部领域思想，领域矩阵表现为稀疏 阵，可以通过对稀疏阵的相关数值处理来加速谱分析的算法实现 1 3 论文的研究内容 本文研兜内容为高维复杂致据的特征提取算法首先总结了前人的相关研究成果，然后针对 以下几个同题进行了深入研究，并取得了一定的刨新， 1 模式识别中出现的大量高维数据使得维数约简成为了个非常关键的步骤但是很多降维 方法是无监督的，没有充分利用已知的类别标号，降维结果往往不适合分类；而现有的有监督降维 7 算法( 如l d a ) 由于计算量和维数有关，处理高维数据时存在计算量过大甚至无法求解的同题本 文通过分析经典的多维尺度变换( c l a s s i c a lm d s ) 和线性判别分析( l d a ) 的优缺点。提出了一种新 的有监督的持征提取算法一判别多维尺度映射( d i s c r i m i n a t e m u l t i d i m e n s i o n a lm a p p i n g ，d m m ) 它对目前缺乏有效降维算法的高维小样本数据集取得了很好的降维效果文中给出了算法的理论 支持并用大量的数值实验验证了算法的有效性针对d m m 算法在解决高维大样本数据集时计算 量过大的同题，引入了l a n d m a r k 思想得到一新的算法一h n d m a r kd m m ( l d m m ) 对l a n d m a r k 点 的选取也给出了有监督的选取算法为了克服上述两种算法只适合于具有线性或近似线性结构的 数据集降维，文中类似千i s o m a p 算法将测地距离代替欧氏距离来获得全局的非线性结构，从而将 d m m 算法推广成一种非线性降维算法一测地度量判别映射( g e o d e s i c m e t r i cd i s c r i m i n a 毛em a p p i n g , g d m ) 2 测地距离的计算是i s o m a p 和g d m 方法中的关键步骤但由于部分数据点的遗失会造成 测地距离计算的巨大偏差本文针对这个问题提出了计算处于间断流形的数据点问的测地甩南方 法对连通图中的数据点依然栗甩最短路估计测地距离，而不连通的数据点之同重构一条近似的 测地线 1 4 本文的组织结构 本文的内容按以下结构组织： 1 、第一章绪论，介绍特征提取算法的研究背景和意义，简述了特征提取方法的发展现状 2 ，第二章分三部分，分别针对高维小样本数据集、高维大样本数据集和非线性结构数据集提 出了相应的有监督降维算法 第一小节分析经典的m d s 算法和l d a 算法的优缺点。提出了一种新的有监督的特征提取算 法一爿别多维尺度映射( d m m ) 文中给出了算法的理论支持并用大量的教值实验验证了算法的 有效性 第二小节引入l a n d m a r k 思想来解决d m m 处理高维大样本数据集时计算量过大的问题提出 了l a n d m a r k 点的选取方法，并通过实例进行验证 第三小节针对存在非线性结构的数据集引入测地距离来度量数据点问的相异度。将d m m 算 法法推广为一种非线性降维算法一测地度量判别映射( g d m ) 最后总结三种方法的性质并比较了备个方法的优缺点及适用范围 3 第三章针对部分数据缺失使得测地距离计算发生较大的偏差使得i s o m a p 和g d m 算法失 效的同题，提出了改进的测地距离计算方法并通过大量的数值实验对算法的有效性进行了验证 4 第四章总结我们在特征提取算法中所傲的工作，并提出了我们今后的研究方向和目标 8 第二章基于可分性的特征提取算法 模式识别就是对模式进行分类，随着计算机的普及和互联网的推广，模式识别已经扩展到越 来越多的应用领域，如文本识别、语音识别、图像检索、数据挖掘生物认证生物信息学等在 许多模式识别问题中，原始样本的数据通常是高维的，而隐台于其中可用于分类识别的信息却往 往是低维的高维数据使得分类和识别需要很大的计算量，而且这些特征中很多是对分类没有太 大用处的，甚至对分类有副作用的特征提取的基本任务之是如何从原始样本数据中找出那些 对模式识别最有效的特征，从而实现特征空间维数的压缩因此。数据处理的前步骤一特征提取 一是模式识别至关重要的步，它直接影响着分类器的设计和性能 本章提出了基于可分性准则下的一系列有监督的特征提取算法分别针对高维小样本( 样本 敷维教) 数据集。高维大样本教据集和存在非线性结构的数据集提出了相应的算法，并给出了 理论支持然后通过数值实验验证了算法的有效性最后是本章小结 2 1 适用于高维小样本数据集的降维算法 直到现在。处理人脸数据基因表达数据等仍然是非常困难的，这是由于存在椎数灾艘1 和 “小拌j 问题所以数据降维方法始终是一个非常重要的研究方向，很多基于统计( s t a t i s t i c a l ) 或基于几何理论( g e o m e t r y ) 的数据降维算法被提出如人脸识别中的经典算法e i g e n f a c e 4 7 1 、 f i s h e r f a c e 4 8 近年来，揭示数据固有几何分布的流形学习算法( m a n i f o l dl e a r n i n g ) 也取得了很 大的发展如i s o m a p ，l l e l a p l a d a ne i g e n m a p 、k e r n e lp c a 4 9 等 以上提出的算法虽然在。维数灾难和。小样本”问题上取得了一定的进展。但还存在很多同 题如e i g e n f z l c e 和f i s h e d a c e 分别是基于主成分分析和线性判别分析提出的，从而在计算上依赖 于敷据的维教，当维数高达成千上万时，计算量将是非常可观的甚至是不可行的流形学习算法 通常对过于稀疏的数据集缺乏有效性，并且由于是无监督算法，没有充分利用已知的类别信息。 降维结果往往并不适合分类 经典的多维尺度变换( c i a 鹤i c a im d s ) 的计算量依赖于样本效而不是维数，对小样本数据集计 算量是非常小的但它是一种无监督的保距映射，并不是以分类为降维目的线性判别分析( 1 i n e a r d i s c r i m i n a t e a n a l y m ，l d a ) 是基于可分性判据设计的降维算法，但由于计算量由样本的维效决定， 对高维小样本数据集会存在计算量过大的同题本节结合这两个算法的优点，提出了一种适合分 类的降维算法，使得计算量依赖于样本效而以分类为目进行降维 下面首先介绍经典的m d s 算法和线性判别分析降维算法。接下来导出一种新的算法一爿别 多维尺度映射( d m m ) ，最后通过大量的数值实验来验证d m m 算法的有效性。 2 1 1 经典的多维尺度变换和线性判别分析 9 1 经典的多维尺度变技( c l a s s i c a lm