（计算机应用技术专业论文）非线性维数约减的研究及其应用.pdf

中文摘要 h 河人类社会r 益深入到信息叫代，存进行科学研究的过程中，不可避免地 会遇剑九量的高维数掘，如全球气候模型、人类基因分粕、文本聚类和文本分类 。的诩频等，所以经常会面临维数约减的问题维数约减的目的是找出隐藏在高 维数折 中的低维结构。 刈维数约减的研究是机器学习的重要主题，维数约减较中肯地把握了人类的 州皇| j i 学习和抽敦思维过程的形式特征。 绯数约减算法大致可以分为两类，一。类是线性的方法：如主成分分析法( p c a ) 和经她多维尺度算法( c m d s ) ，另。类是非线性的方法：如等距映射法( i s o m a p ) 、 局域线性：嵌入法( l l e ) 和自组织等距嵌入法( st e ) 等。 本义首先对几种维数约减算法进行了研究和分析。经典的维数约减算法，如 h c a 和l ( ：s ，实现简单，可以确保发现处于高维向量空恻的线性子空间上的数掘 集的舆。峡儿f r u 结构。但是这类算法的线性本质使其无法揭示复杂的非线性流形。 为此，f t ：多非线性维数约减算法相继提出。i s o m a p 是一种全局优化算法，该算 法建也赴经典多维尺度算法c m d s 基础之卜，试图保持数据问内在的几何特性， 【1 1 ：j 保持数据点之间的测地线距离；l l e 是一种无监督的学习算法，揭示非线性流 形n 0 伞局结构。l l e 使用一种局域对称和线性重构的方法，将输入空i 训的点集映 划为个单一低维的全局坐标系，并保持点的邻域关系。s i e 则是基于种几何 的观点：一个全局等距的嵌入必然是局域等距的，同样，适当选定一组局域等距 约束条件，可以蕴含全局等距：s i e 利用点集的距离分布作为等距约束条件，通 过适当选耿保持局域距离分布的局域等距映象，在概率意义上强迫出全局等距嵌 入映致。 为了客观评价各种非线性维数约减算法的重构质量，本文采用仿真数据和真 实数据分别用各种维数约减算法进行重构。本文将非线性维数约减的方法引入文 本分类，并验证了基于非线性维数约减的文本分类的可用性。仿真实验表明，剥 j 无嘹数据集，i s o m a p 和s i e 重构质量近似，优于l l e ；对于含噪数掘集，l l e 和【s o 1 l k t p 这样的全局非线性嵌入算法， = l = 于噪声导致的伪自由度在整体上扭曲 r e 构流形，导致重构质量的严重f 降，而s i e 可以有效屏蔽少数噪声点对于重构 质量的影响，保持近似优化的重构质量；对于真实数据，对于不同的应用，各个 算法的重构质量有很大差异。 关键词：机器学习非线性维数约减局域线性嵌入等距映射自组织等距嵌入 文本分类 a b s t r a c t s c i e n t i s t sw o r k i n gw i t hl a r g ev o l u m e so fh i g h - d i m e n s i o n a ld a t a ，s u c ha sg l o b a l c l i m a t e p a t t e r n s ，h u m a ng e n e d i s t r i b u t i o n r e g u l a r l y c o n f r o n t t h e p r o b l e m o f d i m e n s i o n a l i t yr e d u c t i o n ；f i n d i n gm e a n i n g f u l l o w - d i m e n s i o n a ls t r u c t u r e sh i d d e ni n t h e i rh i g h d i m e n s i o n a lo b s e r v a t i o n s t h er e s e a r c ho fd i m e n s i o n a l i t yr e d u c t i o ni s av e r yi m p o r t a n ti s s u ei nm a c h i n e l e a r n i n g t h ea l g o r i t h m so fd i m e n s i o n a l i t yr e d u c t i o nc a nb ec l a s s i f i e d i n t ot w o c a t e g o r i e s o n ei s l i n e a rd 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 d ，s u c ha sp c aa n dc m d s ； t h eo t h e ri sn o n l i n e a rd 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 d ，s u c h a sl l e ，i s o m a pa n ds i e a tf i r s t ，s e v e r a l a l g o r i t h m s o f d i m e n s i o n a l i t y r e d u c t i o na r e a n a l y z e d t h e c l a s s i c a l t e c h n i q u e s f o rd i m e n s i o n a l i t yr e d u c t i o n ，p c aa n dc m d s ，a r es i m p l et o i m p l e m e n t a n dg u a r a n t e e dt o d i s c o v e rt h et r u es t r u c t u r eo fd a t al y i n go no rn e a ra l i n e a r s u b s p a c eo ft h eh i g h - d i m e n s i o n a li n p u ts p a c e b u tt h e s ea l g o r i t h m s c a n n o t r e v e a lt h et r u es t r u c t u r eo ft h ec o m p l e xn o n l i n e a rm a n i f o t d sb e c a u s eo ft h e i rl i n e a r f e a t u r e s i s o m a pi s a g l o b a lo p t i m a la l g o r i t h m i tb u i l d so i lc m d sb u ts e e k st o p r e s e r v et h ei n t r i n s i cg e o m e t r y o f d a t a ，a sc a p t u r e di nt h eg e o d e s i cm a n i f o l dd i s t a n c e s b e t w e e na l l p a i r so f d a t ap o i n t s l l e ，a nu n s u p e r v i s e dl e a r n i n ga l g o r i t h m ，a t t e m p t st o d i s c o v e rt h eg l o b a ls t r u c t u r eo fn o n l i n e a rm a n i f o l d s t h em a p p i n gi sd e r i v e df r o mt h e s y m m e t r i e so fl o c a l l yl i n e a rr e c o n s t r u c t i o n t h ed a t ai sm a p p i n g i n t oas i n g l eg l o b a l c o o r d i n a t e s y s t e mo fl o w e rd i m e n s i o n a l i t y s i e b a s e so ng e o m e t r i ci n t u i t i o n s ：a g l o b a li s o m e t r i ce m b e d d i n g m u s tb eal o c a li s o m e t r i ce m b e d d i n gs i m i l a r l y , ap r o p e r s e io fc o n s t r a i n t so fl o c a li s o m e t r i cw i l le n t a i lag l o b a li s o m e t r i ce m b e d d i n g s i e m a k e su s eo ft h e p o i n t t o p o i n t d i s t r i b u t i o na sl o c a lc o n s t r a i n t sa n df o r c e sg l o b a l i s o m e t r y i nas e n s eo f p r o b a b i l i t y i no r d e rt ov a l u et h e q u a n t i t i e s o ft h er e c o n s t r u c t i o n o ft h en o n l i n e a r d i m e n s i o n a l i t y r e d u c t i o n a l g o r i t h m s ，t h i sp a p e ru s e s s i m u l a t e dd a t as e t sa n dt h e n a t u r a ld a t as e t s i nt h i sp a p e r ，t h en o n l i n e a rd i m e n s i o n a t i t yr e d u c t i o nm e t h o d sa r e a p p l i e dt ot e x tc a t e g o r i z a t i o na n dt h eu s a b i l i t yo f t e x tc a t e g o r i z a t i o nb a s e do nn l d r i sv a li d a t e d t h es i m u l a t i o ne x p e r i m e n t st o l dt l s ，f o rt h en o n n o i s ed a t as e t ，t h e r e c o n s t r u c t i o nq u a n t i t yo fi s o m a pi ss i m i l a rt ot h a to fs i e ，a n df o rt h ed a t as e tw h i c h c o n t a i n i n gn o i s e ，t h e r e c o n s t r u c t i o n q u a n t i t i e s o fg l o b a ln o n l i n e a r d i m e n s i o n a l i t y r e d u c t i o na l g o r i t h m s ，s u c ha sl l e a n d s o m a p ，a r eh e a v i l yd e s c e n d i n g b e c a u s eo ft h e r e c o n s t r u c t i o nm a n i f o l d sa r ed i s t o r t e d b yt h e n o i s e w h e r e a ss i ec a nk e e pg o o d 1 1 e c o n s t r u c t i o nq u a n t i t yb ys h i e l d i n gaf e wn o i s ep o i n t sf o rt h en a t u r a ld a t as e t s ，t h e r e c o n s t r u c t i o nq u a n t i t i e so fn l d rm e t h o d sa r ed i f f e r e n c ew h e nt h e ya r ea p p l i e dt o d i f f e r e n c ea p p l i c a t i o n s k e yw o r d s ：m a c h i n e l e a r n i n g ，n o n l i n e a rd i m e n s i o n a l i t yr e d u c t i o n ，l o c a l l i n e a re m b e d d i n g ，i s o m e t r i cm a p p i n g ，s e l f - o r g a n i z i n gi s o m e t r i c e m b e d d i n g ，t e x tc a t e g o r i z a t i o n 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成粜，除了文中特别加以标注和致谢之处外，论文中不包含其他入已经发表 或撰写过的研究成果，也不包含为获得叁盗盘堂或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文作者签名：今从滓签字f 1 期：。弘年上月琴同 学位论文版权使用授权书 夺学位沦文作者完全了解叁垄盘鲎 有关保留、使用学位论文的规定。 特授权墨鲞盘茎可以将学位论文的全部或部分内容编入有关数据库进行检 索，j 十采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位沦文作者签名；豪凯聿 签亨厂1 期：d 嵋年一z 月弓同 导师签名 饲劲本 签字日期：冲y 月哆f i 第一章绪论 1 1 研究的目的和意义 第一章绪论 f l 丽人类社会r 益深入到信息时代，在进行科学研究的过程中，不可避免地 公遇到大量的高维数据，虫全球气候模型、人类基因分布、文本聚类中的词频等， 所以经常会面临维数约减( d i m e n s i o n a l i t yr e d u c t i o n ) 的问题，维数约减的目的 足要找i _ h 隐藏在高维数据中的低维结构。人脑u 王面临着同样的问题：人脑在每天 的感知活动中要从3 0 ，0 0 0 个听觉神经的输入和1 ，0 0 0 ，0 0 0 个视觉神经的输入 - 0 耿h 有意义的信息。 刈维数约减的研究是机器学习的重要主题，维数约减较中肯地把握了人类韵 9 2 i 纳学习和抽象思维过程的形式特征。世界的整体可理解性和公共知识的可能性 杓 ? 纷繁的事件之削存在高度的相关性。利学和同常智慧的根本任务在于利用这 种相关性，寻求对世界的压缩表示和抽象解释，并据其进行有实际意义的预测和 砹汁。 1 2 机器学习 机器学习是研究获取新知识、新技巧、重组已经出现的知识的方法，是人工 钎能的基本问题之一，其理论基础涉及人工智能、统计学、适应性控制理论、心 州。学校弘、进化模型( 如遗传算法) 。 n s o 年代，机器学习中采用了两种4 ；同的研究方法：一种是以控制论为基 砌，使用多项式等为基本函数，用优化的方法建立机器学习模型；另一种是以 r o s e n b l a t l 的感知机为代表的研究，从m p 模型出发，将其扩展为多个神经元的 m ) 模型作为优化算法的数学基函数。但是，从数学的角度上看，其区别仅仅是 它们使川了不同的基函数。这两种以优化为基甜：的方法至今还影响着机器学习的 发腱。 存6 0 年代术，m i n s k y 对感知机的批评使这类研究陷于停顿。但是，他运用 数学方法对当时的人工神经网络模型进行了精辟的分析，指出了人工神经网络求 觯问题的能力有一定的局限性，这个思想对8 0 年代兴起的人工神经网络的研究 足有意义的。从5 0 年代未到8 0 年代仞，机器学习的研究完全脱离了这种基于传 第一章绪论 统优化弹沦的研究方法，提出一种以符号运算为基础的机器学习。 “这个时期，人工智能的研究者根据认知心理学的原理研究各种机器学习的 力法，以符号运算为基础的机器学刊代管了以统计为基础的机器学习，成为人工 智能_ i 究的主流。这个时期，从学习的机制来说，主要是归纳机器学习。其中的 代表性的学习算法有a q l l 与i d 3 。同时，使用不同学习机制的研究也接连被捉 。柙：8 ( ) 年代中期，基于解释的学列( e x p l a n a t io n b a s e dl e a r n i n g ) 与类比 。# 爿( l e t n i n gb ya n a l o g y ) 1 电引起人们的极大的兴趣。特别是与类比学习 棘理棚近的基于范例的学习( c a s e b a h e d1 e a r n i n g ) 2 ，解决实际问题的能力 蚀。这些研究丰富了机器学习的研究。 1 9 8 4 年v a l i a n t 提出了可学习理论，并将学习性与计算复杂性联系在一起。 】q 年u l l l o r 等人证明了v c 维度与v a l i a nl 的“大概逼近f 确( p a c ) ”的可 学习理沦之问的联系。p a c 的理论课题也派生出“计算学习理论”( c o m p u t a t i o n a i ，e a r n i n g7 h e o r y ，简称“c 0 1 t ”) 。1 9 9 5 年，v a p n i k 在统计学习理论研究的基础 j ：，指l i 了经营风险最小的问题，提出结构风险最小化。在这一理论框架指导下， o 牛了吏持向量机( s u p p o r tv e c t o rm a c h jn e ，简称s v m ) 学习方法，这是一种 构造，胜的学习方法。 受达尔文的进化论的影响，美固m i c h i g a n 大学的i i o l l a n d 逐渐认识到在机 器学刊中，为获得一个好的学习算法，仅靠单个策略的建立和改进是不够的，还 婪依赖于一个包含许多候选策略的群体的繁殖，考虑到他们的研究想法起源于遗 传进化，i i o ll a n d 就将这个领域取名为遗传算法( g e n e t i ca 】g o r i t h m ) 。 红8 0 年代，基于试错方法、动念规划和瞬时误差方法形成了强化学习 ( r e jnf o r e e m e n tl e a r n i n g ) 。1 9 8 4 年，s u t t o n 提出了一种基于m a r k o v 过程的 强化学习。1 9 9 6 年，k a e l b i n g 在总结强化学习的研究时指出，实现这种学习的 手段就是自适应机制。 hi i ，比较常见的机器学习的方法有：规则归纳、决策树、范例推理、贝叶 斯信念网络、遗传算法等等。 1 3 维数约减( d i m e n s i o n a l i t yr e d u c t i o n l 维数约减足机器学习的重要主题。本文主要研究维数约减算法及其应用。 真实1 1 ；| = 界的数据往往是高维的，因为高维而难于被人理解、表示和处理。目 的干j 多利- 维数约减的方法，经过维数约减的数据可以更好地进行分析，更容易可 视化。维数约减算法大致可以分为两类，一类是线性的方法，如主成分分析法和 经典多维尺度算法，另一类是非线性的方法，如等距映射法、局域线性嵌入法和 凡汁人学硕十学位论文第一章绪论 自组织等距嵌入法。 经典的维数约减算法有主成分分析法( 艮i n c jp a lc o m p o n e n ta n a y s is ，缩 与为p c a ) 1 3 ，4 和经典多维尺度算法( c l a s s j c mm u t i d i m e n s i o n a ls c a i i n g ， 缩1 j 为c m i ) s ) 3 。主成分分析法是由h o l e l l i n g 于1 9 3 3 年提出的，因此又被 称为h o t e l ir t g 变换，该方法是利用维数约减的思想，把多指标转化为几个综合 指标的多元统计分析方法。由于各评价指标之问有一定的相关性，必然存在着起 支配作用的共同因素，因此，通过主成分分析法对原始指标变量相关矩阵内部结 构关系进行研究，找出影响过程的几个综合指标，使综合指标变为原来指标变量 的线忡组合，它们小仪保留了原始变景的主要信息，彼此之削又不相关，更有助 j 抓t l j 二要矛盾。 绎9 u 多维尺度分析【c m d s ) 用于反映多个研究事物问的相似( 不相似) 程度， 通过适当的降维方法，将这种相似( 不相似) 程度在低维度空间中用点与点之问 的距离表示出来，并有可能帮助识别那些影响事物间相似性的潜在因素。 绎虬的维数约减方法，如p c a 和c m d s ，丈现简单，可以确保发现处于高维 l l l j b 。叫的线陆f 空间上的数据集的真实几何结构。但是这类算法的线性本质使 其无法揭示复杂的非线性流形( 流形是这样一种拓扑空间，它是局域欧式的，例 如在每。个点的周围有个邻域，该邻域从拓扑上等同于n 维空训的一个开球) 结构。为此， o s h u ab 1 e n e n b a u me ta l 和s a mt r o w e i se ta l 提出了各自 的j l ：线性维数约减算法：i s o m a p 5 ，6 ，7 和l l ，e 8 ，9 ，1 0 ，1 1 ，1 2 。 等距 映射( i s o m e t r i cm a p p i n g ，简写为1 s o m a p ) 使用测地线距离( 所谓测地 线距离即两点在流形上的实际距离，例如我们在地面上以直线行走，实际上走的 是地球球体表面的大圆上的一段弧，这段弧称为测地线。这是地球表面最接近直 线的轨迹。) 替代欧式距离，克服了c m d s 的局限性。它是一种全局优化算法，建 、7 ：nc m d s 基础之上，试图保持数掘的内在的几何特性，获得流形上数据点之问 的测地线距离。算法的关键是估计远鼠( 非邻域点) 之f 皤的测地线距离。对于邻 域点，i s o m a p 由输入空怕j 直接得到其测地线距离；对于非邻域点，其测地线距 离町近似为系列邻域点的测地线距离之和。 局域线性嵌入算法( l o c a l l yl i n e a re m b e d d i n g ，简写为l l e ) ，是一种无监督 的学习算法，该算法是基于一种几何直觉，它将每个输入向量看作是高维空l l 自j 中 的 个点，在其周围有k 个邻居，我f f j 称之为邻域点，l l e 利用陔点的邻域点 的线r 嗍l 台束重构这个点。映射山一个对称的局部线性重构而得，实际的嵌入计 算简化为求一个稀疏特征函数的问题。 s i e 1 3 则是基于一种几何的观点：一。个全局等距的嵌入必然是局域等距的， 凡洋人t 孙p 学位沦文 第一章绪论 l 司样，适当选定一组局域等距约束条件，可以蕴含全局等距；s i g 综合了全局算 法利自绀织算法的优势，利用点集的距离分布作为等距约束条件，通过适当选耿 保持局域距离分甸的局域等距映象，在概率意义上强迫出全局等距嵌入映象。s i e 的卜要计算过程是局域的，回避了特征值闯题的计算，可以直接分布式实现。 1 4 本文结构 本文t 要对维数约减算法进行研究矛u 分析，为了评价各种维数约减的算法， 分划采用无噪仿真数据集和含曝的仿真数据集测试各个算法的重构质量；此外， 采用多视角图像数掘、相同时间周期的股票数据、文本词频数扼：对各种维数约 减算浊进行了应用研究。 本文的创新之处在于将非线性维数约减的方法引入到文本分类当中，并验证 了丛 非线性维数约减的文本分类的可用性。 本文的内容概要如下： 第章对维数约减算法进行介绍，分析各种维数约减算法的内核。 第一卓简单介绍神经网络。 第四章介绍了文本分类的相关概念及常用算法。 第缸章介绍本文实验所用平台m a t l a b 的特点。 第六章对本文所做的非线性维数约减实验进行分析和讨论。实验分为两个部 分。第部分是仿真实验，首先应用各种非线性维数约减算法对无嗓s w i s s 数据 集【6 ：】进行重构，然后应用各种非线性维数约减算法对含噪s w i s s 数据集进行重 构，考察算法的鲁棒性。第二部分是真实数据的实验，研究算法的目的是为了更 好地应用，所以本文对三种真实数据用非线性维数约减算法进行处理。 第七章是全文的总结和对未来工作的展望。 火7 ”人学硕十学位论文第一章维数约减算法 第二章维数约减算法 存进行科学研究时，所处理的数据通常是高维数据，每个对象都表示为大量 特 _ 【j ：，、。1 岛维数据的维数达n j l 百甚至儿千时，算法会很耗时，此外，高维数据 的存储和检索也是在进行科学研究时的难题。 对待高维数据，通常的方法是首先对数据进行维数约减，通过维数约减识别 出其中的最重要的特性，然后再对数据加以处理，以保证处理过程简单化，并保 i j r 最终结果的质量不会降低。在本文中介绍四种维数约减算法：p c a 、i s o m a p 、 i 。i ，e 和s i e 。p c a 是种常用的线性维数约减的方法，一般认为，在线性维数约 减算法中，还没有一种算法超越p c a 。i s o m a p 和l l e 是近来倍受关注的两个非 线性维数约减算法，s i e 是最近提出的一种非线性维数约减算法基于自组织 等距嵌入算法。 2 1 主成分分析法( p c a ) 科学研究所涉及的课题往往比较复杂，这是冈为影响客观事物的因素多，需 。婴考察的变量多。在大部分实际问题中，变量之问是有一定的相关性的，人们自 然希掣找到较少的几个彼此不相关的综合指标尽可能多地反映原来众多变量的 信息。1 9 3 3 年h o t e l l i n g 提出的主成分分析( p c a ) 方法f 是实现这一目的的有 效途径之。 仙为e 成分? 简而言之，主成分实际上就是由原变量x 。x 。线性组合出来的 个j 小相关、且未丢失任伺信息的新变量也称为综合变量。多指标的主成分 分析常被用来寻找判断某种事物或现象的综合指标，并给综合指标所蕴藏的信息 以恰当解释，以便更深刻地揭示事物内在的规律。 ： _ 棚父矩阵为r 以及与之同阶的单位矩阵为i 、原始变量的个数为h t ，则r 就足m 阶方阵，特征值为 ，求各特征值 ，的过程就是求解下列特征方程：i 限 f | = ( ) ，此方程的左边展丌后实际上是一。个 的m 阶多项式，其解由大到小 依次排列为x i - 。 。 0 。主成分分析的基本条件与主成分的基本性质 l u 概述如下： 各l 成分之问互不相关，若原变量服从正态分布，则各主成分之间互相独 ： 第一二章维数约减算法 全部m 个主成分所反映的n 例样品的总信息，等于m 个原变量的总信息。 信息齄的多少，用变量的方差来度量。若将m 个原变量标准化后，每个变量的方 筹都为1 ，故方差之和为【n ，此时，求得的m 个主成分的方差之和也为m ； 各主成分的作用大小是：z z 。z ； 第j 个t 成分的贡献率是( m ) 1 0 0 ； 品 曲 ) 个主成分的累计贡献率是( 2 。 ) m 1 0 0 。在应用时， 般取 # 1 累计贡献率为7 0 8 0 或以 所对应的前p 个主成分即可。在资料所含的变量 个数、样品数及累计贡献率固定的前提下，p m 的比值越小，则浇明此资料和主 成分分析越合适。 r ( z x ) = c ，晚明第i 个主成分7 与第j 个标准化变量x 之间的相关系 数就足表达式( 3 ) 中系数c ； yr ! ( z - x 。) = ，说明第i 个主成分z 与m 个标准化变量中的每个变量 ， 之f u j 的干h 关系数的平方和为由大到小排列后的第i 个特征值 ； f t r ! ( z x ，) = l ，说明m 个主成分分别与第j 个标准化变量的相关系数 蚓 的甲方和为1 ，即每个标准化变量的信息由全部主成分完全包含。 从上述过程可以看出，特征值是由小到大依次排列的，在进行维数约减时， 墩最大几个特征值所对应的特征向量，就可以将原数据约减到几维。 c m d s 与p c a 是很相似的算法，只是它们的输入矩阵不相同，p c a 要求输 入的是协方差矩阵，而c m d s 要求输入的是点到点的距离构成的矩阵。相同点 是两者要求的输入矩阵都应为对称的、半正定的。 2 2 等距映射算法i s o m a p i s o m a p 是+ 种全局优化算法，建立在c m d s 基础之上，试图保持数据的内 在的几何特性，获得流形上数据点之f 日j 的测地线距离。算法的关键是估计远点( 非 邻域点) 之阳j 的测地线距离。对于邻域点，由输入空间直接得到其测地线距离； 刈r 怍邻域点，其测地线距离可近似为系列邻域点的测地线距离之和。 l s o m a p 的算法有三个步骤： 第 个步骤是确定在流形m 上，那些点是邻域。对于输入空阳jx 中的点i , j 其欧式距离为d x ( i j ) 。将每一个点与所有的点进行比较，当两点之间的距离+ t - 固定的半径e ( 或i 是j 的k - 邻域) 就认为它们是相邻的，将其连接起来，边长 为d x ( i ，j ) ，得到有权图g 大汁人学硕十学位论文第二章维数约减算法 第二个步骤是通过计算最短路径d o ( i d ) 的方法估计流形m 上的测地线距离 d m ( i j ) 。仞始【卜：f ! i , j 之问有一条边，则d ( ，( i j ) = d x ( l j ) ；否则d o ( i j ) = 。对所有的 k = 1 ，2 n 、d o ( i , j ) = m i n ( d g ( i , j ) ，d o ( i k 卜d g ( k j ) ) ，这样得到矩阵d c l = d g ( i j ) ，它是 g 中所有点对的最短路径组成的。 g g _ 5 个步骤是应用c m d s 构造d 维嵌入。令山是矩阵t ( d g ) 的第p 个特征 值( 特征值已按降序排列) ，一是第p 个特征向量的第i 个分量，令d 维嵌入向 r 量j - 的第，个分量等于a r 吖。 2 3 局域线性嵌入( l l e ) l l e 是基于一种几何直觉，它将每个输入向量看作是高维空间中的一个点， 加其剖圳有k 个邻居，l l e 利用该点的邻域点的线性组合来重构这个点，最后 利川r 筒维输入向量x 的重构权值w 。来算高维数据的低维嵌入坐标 虬i f 算法的第一步是鉴定每个数掘点的邻域。简单地说，就是鉴定与每个数 钳点比较接近的邻域点数k 计算其欧式距离，只要两个结点的欧式距离小于 某个规定的值，就认为那个结点是已知数据点的邻域点，所有这样点的集合被称 为是已知数据点的邻域。除欧氏距离外有一些标准也可以被用来选择邻域，一种 ，。法就是将指定半径的球域中所包含的数据点作为邻域。例如，可以将邻域点定 义为某个、卜径之内的所有点，直到达到某个预定的邻域点数的上界。一般来说， j ，1 ，f 算法中邻域的选择需要利用先验知识。 算法的第二步是从邻域中重构每个点。优化重构权值可以被计算出来。考虑 巢一个数据点。，它有k 个邻域口，和重构权值w ，n n , t 权值矩阵每一行的重 构权值w 的和是1 ( 保证每个数据点的所有邻居权值加和为1 ) 。这样我们就可以 将最构跌麓写为： s = p s ws 计= l ，w 正一训一= 。w m g 。 ( 2 1 ) g m = ( x 7 ，) 一仇) ( 2 2 ) 通过重构，该矩阵是对称的并且是半正定的。利用拉格朗同乘子来加强权值 的和为l ( 即，w ，= 1 ) 这种约束，可以使误差达到最小。在g r a m 矩阵求逆后， 域优权值由下式给出： 夫7 ，j 一 硕斗学忙论文第一章维数约减算法 vn j i 鱼 !( 2 3 ) 。g 一 其践h 有一利- 更有效、更稳定的方法来使误差达到最小，那就是解线性方 程绷，e ；( ：i k w k ：1 然后重新调整权值w ，使其和为1 。 i ，【。f 算法n n n - 步是利用高维输入向量咒的重构权值w ，来计算高维数据 的低维嵌入坐标。注意这种计算仅仅是通过权值w 来构造，实际的输入向量x r 不参加这一步运算。注意邻域所起的作用通常根据输入向量x ，来决定，通过使下 | f | 1 等式达到最小化来建立低维向量 ，。 咖( y ) y 扎y 。l 2 为了优化嵌入费用函数( 2 4 ) ，我们将其写为这种形式 巾( y ) = m ，炒，y j ) ( 2 4 ) ( 2 5 ) j l = ，包括输出l a j 量y , 的内积，n 阶矩阵m 为： m i j = a1 jw i j w j i + ek w k i w k j ( 2 6 ) 当l = j 时，6 i j 2 l ；否则5i j2 0 。矩阵m 是稀疏的、对称的和半正定的 2 4 自组织等距嵌入s i e 自h 硅廿介绍的非线性维数约减算法，如l l e 和i s o m a p ，面临一些共同的问题： 首先，上述算法需要求解大尺度特征值问题或特征值问题的变形。由于特征值问 题至少= 次的计算复杂性，算法在大样本集情形下的应用较受限制。其次，上述 弹法的优化机制是全局的，在某些情形f 对于噪声极为敏感，且需要考虑“病态 她一阿”的i 算精度问题。侯越先等提出了基于自组织的非线性维数约减方法：白 组彰 等距嵌入( s i e ，s e l f - o r g a n jz j r l gi s o m e t r i ce m b e d d i n g ) 。 s t e 的出发点基于如下的几何的观点：一个全局等距的嵌入必然也是局域等 距的；同样，适当选定一组局域等距约束条件，可以蕴含全局等距。具体地，考 虑利用由点集的距离分布作为等距约束条件。b o u t i n 和k e m p e r 的结果表明，在 概率巷义 ：，由点集的距离分布可以等距地恢复出点集。在此基础上，作者注意 到通过适、_ i _ j 选取保持局域距离分布的局域等距映象，可以在概率意义上强迫出全 局等距芡入映象。 苎鲨叁。兰竺! 堂竺堕兰 苎= 兰二兰塑丝! ! ! 里堡 s l e 算法包括两个阶段：第一个阶段是求锚点集到所有样本点的测地线距离， 笫- 阶段，s i e 算法需要由各个样本点到铺点集的测地线距离，重构出全局等距 嵌入。算法描述如下： 算法输入：原空问中n 点设置鼻、， ”，f ，的点到点欧氏距离 d w ( f i ，) ， 1 i ，7 ： 嵌入维研、学习步数s t e p s * 口学习率五。 算法输出：嵌入空间r 中的n 点设置鸟，蜴，q ，。 1 ) 【1 i 嵌入维用，设定锚点数n 月。应至少大于等于州+ 2 2 ) 在只，只，只中随机选择n 。个点作为锚点，记为 a ， ，i = 1 , 2 ，h 。 ： ) 利用类似l s o m a p 的过程，计算出锚点集中的各点到露，只的测地线距 离 。，o ，) ，1 i ，2 1 f t 一 ，1 j 随十j l 初始化一个r ”1 的”点设置甜，蹦，硝 5 ) 利用自组织恢复算法，由点到点测地线距离设置，在r ”中恢复出锚点集 a ，j 的全局等距嵌入 口， 6 ) 循环执行i = 0 ：】：印s 7 ) x = m o d ( i ，月) h ) 循环执行y = 1 ：1 m ，。 9 ) 引算q ：和口：之i n j 的恢氏距离d ：；( 联，占；) l ( ) ) 计算距离误差e 。= 矗j 。( z ，y ) 一以( g ，b ：) 1 1 )计算偏移向量q ：= 一 、t a n h ( e ，。) ( b ：，一q ：) 】2 ) 娥“= g + g 。 1 ： )结束循环 1 1 ) 绌束循环 15 ) q l = 鳄“，l 曼x n 1 6 ) 返回 这啭t a n h ( 。) ：三二三。，用于约束偏移向量的长度；算法的具体实现通常采用 】+ e 。 线一陀衰减的可变学习率a 。 s l i i 的u 寸f , j 复杂性为o ( n l o g ) ，在处理大样本集时优于全局算法至少二次 f 内| 卜j 问复杂性：s i e 的主要计算过程是局域的，可提高算法对于噪声的鲁棒性， 并可甑接分布式实现，从而回避病态矩阵的计算精度问题。 2 5 几种维数约减算法的比较 线性维数约减的两个典型的算法是主元素分析法p c a 和经典多维尺度法 c m d s 。p c a 和c m d s 都是用的特征向量的方法，当采用的是欧氏距离时，p c a 等价rc m d s 。p c a 和c m d s 的优化很容易理解，不会导致局域极小。这些优 第二章维数约减算法 点使p c a 和c m d s 得到广泛的应用，尽管p c a 和c m d s 作为线性方法有一定 的局限性。p c a 和c m d s 是为嵌入的子流形是线性的或近似线性的情况设计的， 流形比较复杂时，这些算法就失败了。例如处理s w i s s r o l l 数据时，不能真实 地揭示流形的几何特征【6 。 局域线性嵌入( l l e ) 是一种强大的特征向量方法，采用一科t 无监督的学习 钎法，揭示非线性流形的全局结构，l l e 使用一种局域对称和线性重构的方法计 辫：低维的、保持高维数据邻域关系的嵌入。l l e 将输入空间的点集映射为一个单 + 低维全局坐标系，并保持点的邻域关系。 i s o m a p 算法用测地线距离替代欧式距离，一个流形上的测地线距离可以表 尔为1 系列邻域点之间的距离之和，并应用c m d s 计算测地线距离。 l l e 和l s o m a p 算法效率高、参数少，是非迭代的全局优化算法，具有揭示 m 线性数 ! ( 流形的内在特性的能力。 s i e 综合了全局算法和自组织算法的优势，利用局域等距的约束条件，以自 组织的方式，强迫出全局等距嵌入。在处理大样本时优于全局算法，s i e 的主要 讨算过程是局域的，回避了特征值问题的计算，可以直接分布式实现，并且可提 高钟珐的鲁棒性。 人泮人学颂h 学位论文第三章神经网络 3 1 神经网络概述 第三章神经网络 人i 神经网络是一门活跃的边缘性交叉学科，以工程技术手段模拟人脑神经 网络的结构和功能，其特色在于信息的分布式存储和并行协同处理，是巨量信息 并行处删和大规模乎行计算的基础，既是高度非线性动力系统，又是自适应组织 系统。神经网络是人脑的某种抽象、简化和模拟，反映了人脑功能的若干基本特 征：第 ，网络的信息处理，是由处理单元间的相互作用来实现，并具有并行处 圳n q 特血；第一知识与信息的存储，表现为处理单元之阳j 分布式的物理联系： 笫- ，网络的学习和识别，决定于处理单元连接权系的动态演化过程；第四，具 何联想记忆的特性。神经网络的工作方式有两个阶段组成学习期和工作期。 学习期是指神经元之蒯的连接权值可由学刊规则进行修改，以使目标函数达到最 小；工作期则是连接权值不变，由网络的输入得到相应的输出的过程。一一般而言， 神经i 删络书要分为四类：自u 馈、反馈、自组织和随机型。人工神经网络可用来描 述认u 、决策及控制的智能行为，广泛用于模式识别、分类、聚类、控制系统和 动态系统建模等领域。 3 2 感知机模型 感f r l * ；l 1 4 1 是美国学者r o s e n b l a t t 于1 9 5 7 年为研究大脑的存储、学习和认知 过程【向提出的一类具有自学习能力的神经网络模型。 感知机足种具有分层结构的前向酬络模型，它可分为单层、两层及多层结 构。感知机中的神经网络是线性闽值单元。当输入信息的加权和大于或等- ? i n 值 时，输出为1 ，否则输出为0 或一1 。神经元之l 训的连接权值是可变的，这种可变 性保证了感知机具有学习的能力。 单层感女h * j l 是山输入层和输出层构成，只有输出层可作为计算层。在单层感 知机t h 输入层和输出层都可由多个神经元纠成，输入层将输入模式传送给连接 的输出单兀；输出层对所有输入数据进行加权求和，经阈值型作用函数产生一组 输出模式。单层感知机的两层神经元之i 到采用全互连方式，即输入层各单元与输 i5 层各单元之间均有连接。 火讨r 人学顺十学位论文第二章神经网络 如果在输入层和输出层之问再加入一层或多层处理单元，就构成了二层或多 层感知机。具中，新加入的各层称为隐含层，隐含层的处理单元称为隐单元。隐 i 、l 的作用是提取输入模式中包含的有效特征信息，使输出币元所处理的模式是 线m l j 分的。在多层感知机中，只允盼层连接权值可调。 3 3 误差反向传播网络 跌麓反i 句传播( e r r o rb a c k p r o p a g a t i o n ) 网络 1 5 通常简称为b p ( b a c k p r o p a g a t i o n ) 网络。是当今神经网络模型中使用最广泛的一种。 荚因加州大学的鲁梅尔哈特( r u m e l h a l t