（计算机应用技术专业论文）基于非线性维数约减的模式识别.pdf

中文摘要 通过各种捕捉设备获取的多媒体数据通常是高维的，它们不适合通常在少 量特征上能够准确分类的分类器。因此需要基于维数约减的特征抽取过程来去 除或弱化那些不重要的特征，而保留或加强那些对于分类有意义的特征。决定 现实世界 演化的背景机制通常是非线性的， 传统的线性维数约减方法( 如主 成分 分析法( p c a ) ) 在把数据映 射到 低维空间时， 通常不能 保留原高维数据的内 在非线 性结构和特征。 因此非线性的方法( 如等距映射法( 工 s o m a p ) 、 局域线性嵌入法( l l e ) 等) 应运而生，它们的优点是具有较少的参数需要设置，而且使用非迭代的方法 去求解从而可以避免陷入局部极小。 原始的非线性维数约减算法是无监督的，不能直接用于模式识别。在本文 中我们对原始的算法进行修改， 加入样本的分类信息进行维数约减，然后对一 个简单的分类器进行训练，这就形成了一个简单的模式识别原型系统。通过使 用人脸库等数据进行测试，取得了比传统的线性特征提取方式更好的效果。 关键词: 模 式 识 别 ， 非 线 性 维 数 约 减 ， 人 脸 识 别 ， 特 征 提 取 ， 工 s o m a p , l l e abs tract i m a g e d a t a t a k e n w i t h v a r i o u s c a p t u r i n g d e v i c e s a r e u s u a l ly m u l t i d i m e n s i o n al a n d t h e r e f o r e t h e y a r e n o t v e r y s u i t a b l e f o r a c c u r a t e c l a s s i f i c a t i o n n o r m al l y e x p e c t i n g t o o p e r a t e o n l y o n a s m a l l s e t o f r e l e v a n t f e a t u r e s . h e n c e , t h e t a s k o f d i m e n s i o n al i t y r e d u c t i o n h a s e m e r g e d w it h a n a i m t o r e d u c e o r e l i m i n a t e i n f o r m a t i o n b e a r i n g s e c o n d a r y i m p o r t a n c e a n d r e t a i n o r h i g h l i g h t m e a n i n g f u l o n e . s i n c e t h e n a t u r e o f r e a l - w o r l d d a t a a r e o ft e n n o n l i n e a r , t h e 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 t e c h n i q u e s , s u c h a s p r i n c i p al c o m p o n e n t a n a l y s i s ( p c a ) , f a i l t o p r e s e r v e a s t r u c t u r e a n d r e l a t i o n s h i p s i n a h i g h - d i m e n s i o n a l s p a c e w h e n d a t a a r e m a p p e d i n t o a l o w d i m e n s i o n al o n e . i t m e a n s t h a t n o n l i n e a r d i m e n s i o n al i t y r e d u c t i o n m e t h o d s a r e o n d e m a n d i n t h i s c a s e , s u c h a s i s o m e t r i c m a p p i n g ( i s o m a p ) a n d l o c a l l y l i n e a r e m b e d d i n g ( l l e ) . t h e i r m a in a t t r a c t i v e c h a r a c t e r i s t i c s a r e . f e w fr e e p a r a m e t e r s t o b e s e t a n d a n o n - it e r a t i v e s o l u t i o n a v o i d i n g t h e c o n v e r g e n c e t o a l o c a l m i n im u m . t h e o r i g i n al n o n l in e a r d i m e n s i o n a l it y r e d u c t i o n a l g o r i t h m s a r e n o n - s u p e r v i s e d , w h i c h c a n t d i r e c t l y b e a p p l i e d i n p a tt e rn r e c o g n i t i o n . i n t h i s p a p e r , w e f ur t h e r e x p l o re a n d e x t e n d o r i g i n al m e t h o d s , a d d s a m p l e c l a s s i f i c a t i o n in f o r m a t i o n t o i m p l e m e n t d i m e n s io n al i t y r e d u c t i o n , a n d t h e n t r a i n a s i m p l e c l a s s i f i e r . i n t h i s w a y , w e g e t a s i m p l e p a tt e rn r e c o g n i t i o n p r o t o t y p e . w e t e s t t h i s s y s t e m o n s o m e r e al - w o r l d f a c e i m a g e s a n d o b t a i n m u c h b e tt e r r e s u l t s t h a n t r a d i t i o n a l l i n e a r m e t h o d s . k e y wo r d s : p a tt e rn r e c o g n i t i o n , n 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 , f a c e r e c o g n i t i o n , f e a t u r e t r a n s l a t i o n , i s o m a p , l l e 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人己 经发 表 或 撰 写 过 的 研 究 成 果 ， 也 不 包 含 为 获 得k *k f.或 其 他 教 育 机 构 的 学 位 或 证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均己在论 文中作了明确的说明并表示了 谢意。 学 位 论 文 作 者 签 名 : 年 麟 签 字 日 、 二年 月 / 日 学位论文版权使用授权书 本 学 位 论 文 作 者 完 全 了 解- a l- 生k 生. 有 关 保 留 、 使 用 学 位 论 文 的 规 定 。 特 授 权 一 孟生垫史可 以 将 学 位 论 文 的 全 部 或 部 分 内 容 编 入 有 关 数 据 库 进 行 检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学 校向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学 位 论 文 作 者 签 名 : a /if 签 字 。 期 : _mq 年( 月 1 z 日 导 师 签 “ : )可乙 11 签 字 日 期 : 7 / l v 4 年 月 z 日 天津大学硕士学位论文第一章 绪论 第一章 绪论 1 . 1 研究的目的和意义 维数约减是处理高维数据的一种重要手段， 它的目的是获得关于原始数据的 紧凑表示。这样的压缩表示消除了 那些可能混淆和隐藏原始数据有意义关系的 冗余因素，对于后续处理是有益的。维数约减对于成功的模式识别也是非常必 要的，它可以 克服众所周知的维数灾难问题即训练的样本点个数小于样本点的 维数 i ,随着数据维数的增长这种效应会严重影响识别准确性。 为了阐述维数 约减的有用性，想象这样一个实验:拍摄镜头固定而三维被拍摄物体在一个平 面旋转， 也就是它具有一个自由 度。 如果每幅图片都是nx n个象素，同时每个 象素被选作一个特征， 这 就意味着有n z 个不同的 特征， 它的维数是n z 。 另一方 面， 这些图片能被考虑为 嵌入在n 2 空间的一 维流形的 数据点。 这个流形的 唯一 维数就是物体旋转的角度，这个本质的维数对于图象识别已经足够，而其它维 数就可以被丢掉。 从几何的观点来看， 维数约减可以看成是挖掘嵌入在高维数据中的低维线性 或非线性流形。 这种嵌入保留了原始数据的几何特性，即在高维空间中靠近的 点在嵌入空间中也相互靠近。 1 . 2 模式识别 我们在生活中时时刻刻都在进行模式识别。 环顾四周， 我们能认出周围的物 体是桌子、椅子，能认出 对面的人是张三、李四;听到声音，我们能区分出是 汽车驶过还是玻璃碎裂，是猫叫还是人语，是谁在说话，说的是什么内容;闻 到气味，我们能知道是炸带鱼还是臭豆腐。我们所具备的这些模式识别的能力 看起来极为平常，谁也不会对此感到惊讶，就连猫狗也能认识它们的主人，更 低等的动物也能区别食物和敌害。因此过去的心理学家也没有注意到模式识别 的能力是个值得研究的问题，就像苹果落地一样见惯不惊。只有在计算机出现 之后，当人们企图用计算机来实现人或动物所具备的模式识别的能力时，它的 难度才逐步为人们所认识。由于日 前计算机的模式识别在多数方面还远不如人， 天津大学硕士学位论文第一章 绪论 第一章 绪论 1 . 1 研究的目的和意义 维数约减是处理高维数据的一种重要手段， 它的目的是获得关于原始数据的 紧凑表示。这样的压缩表示消除了 那些可能混淆和隐藏原始数据有意义关系的 冗余因素，对于后续处理是有益的。维数约减对于成功的模式识别也是非常必 要的，它可以 克服众所周知的维数灾难问题即训练的样本点个数小于样本点的 维数 i ,随着数据维数的增长这种效应会严重影响识别准确性。 为了阐述维数 约减的有用性，想象这样一个实验:拍摄镜头固定而三维被拍摄物体在一个平 面旋转， 也就是它具有一个自由 度。 如果每幅图片都是nx n个象素，同时每个 象素被选作一个特征， 这 就意味着有n z 个不同的 特征， 它的维数是n z 。 另一方 面， 这些图片能被考虑为 嵌入在n 2 空间的一 维流形的 数据点。 这个流形的 唯一 维数就是物体旋转的角度，这个本质的维数对于图象识别已经足够，而其它维 数就可以被丢掉。 从几何的观点来看， 维数约减可以看成是挖掘嵌入在高维数据中的低维线性 或非线性流形。 这种嵌入保留了原始数据的几何特性，即在高维空间中靠近的 点在嵌入空间中也相互靠近。 1 . 2 模式识别 我们在生活中时时刻刻都在进行模式识别。 环顾四周， 我们能认出周围的物 体是桌子、椅子，能认出 对面的人是张三、李四;听到声音，我们能区分出是 汽车驶过还是玻璃碎裂，是猫叫还是人语，是谁在说话，说的是什么内容;闻 到气味，我们能知道是炸带鱼还是臭豆腐。我们所具备的这些模式识别的能力 看起来极为平常，谁也不会对此感到惊讶，就连猫狗也能认识它们的主人，更 低等的动物也能区别食物和敌害。因此过去的心理学家也没有注意到模式识别 的能力是个值得研究的问题，就像苹果落地一样见惯不惊。只有在计算机出现 之后，当人们企图用计算机来实现人或动物所具备的模式识别的能力时，它的 难度才逐步为人们所认识。由于日 前计算机的模式识别在多数方面还远不如人， 天津大学硕士学位论文第一章 绪论 因此研究人脑中的模式识别过程对提高机器的能力是有益的;反之，研究机器 模式识别的能力对于理解人脑中的过程也有很大帮助，认知心理学的很多新模 型即得益于此。 什 么是 模式 ( t - ) 呢 ? 广义地 说， 存在于 时间 和空间中 可 观察的 事 物， 如果 我们可以区别它们是否相同 或是否相似， 都可以 称之为 模式。但模式所指的不 是事物本身，而是我们从事物获得的信息。因 此，模式往往表现为具有时间或 空间分市的信息。如果是用计算机进行模式识别，信息进入计算机之前通常要 经过取样和量化，在计算机中具有时空分布的信息表现为向量即数组。数组中 元素的序号可以对应时间与空间，也可以对应其它的标识。例如，在医生根据 各项化验指标判断疾病种类的模式识别过程中，各种化验项目 并不一定对应实 际的时间或空间。有些化验项目是对应于时间的，例如血沉。因此，对于上面 所说的时间与空间应作更广义、更抽象的理解。 人们为了 掌握客观事 物， 通常按事物相似的 程度组成类别。 模式识别的作用 和目 的就在于面对某一具体事物时将其正 确地归入某一类别。 例如，数字 “ 4 可以有几种不同的字体或写法，但它们都属于同一类，即使我们看到从未见过 的一种写法的“ 4 ， 也能正确地将其分到“ 4 ” 这一类别中。 从不同角度看人脸， 视网膜上的成像也不同，但我们可以识别出这个人是谁，把所有不同角度的像 都归入到一类。如果给每个类命名，并且用特定的符号来表达这个名字，那么 模式识别 ( p a tt e r n r e c o g n it i o n ) 2 可以 看成是从具有时间和空间分市的信息向 着符 号所作的映射。 通常， 我们把通过对具体的个别事物进行观测所得到的具有时n j 和空间分布 的 信息称为模式， 而把模式所属的 类别或同一类中 模式的总体称为模式 类( 或简 称为 类) 。 也有人习 惯于把模式类称为 模式，而把个别具体的 模式称为 样本， 这 种用词的不同 可以从上下文弄清其含义，并不会引 起误解。 图1 - 1模式识别流程简图 一个模式识别系统可以 用上图来表示，它包括以下几个部分: 天津大学硕士学位论文 第一章 绪论 。 信息的获取: 是通过传感器， 将光或声音等信息转化为电信息。信息可 以是二维的图 像如文字，图像等; 可以是一维的波形如声波，心电图， 脑电图; 也可以是物理量与逻辑值。 预处理: 包括a / d转换，二 值化，图 像的 平滑， 变换， 增强， 恢复， 滤 波等， 主要指图象处理。 特征抽取和选择:在模式识别中，需要进行特征的抽取和选择，例如， 一 幅6 4 x 6 4的图 像可以 得到1 2 8 个数据， 这种在测量空间的原始数据通过变换 获得在特征空间最能反映分类本质的特征。这就是特征提取和选择的过程。 分类器设计:分类器设计的主要功能是通过训练确定判决规则，使按此 判决规则分类时， 错误率最低，然后把这些判决规则建成标准库。 分类决策:在特征空间中对被识别对象进行分类。 1 . 3维数约减( d i m e n s i o n a l i t y r e d u c t i o n ) 维数约减是机器学习的重要主题。 真实世界的数据往往是高维的， 难于被人 理解、 表示和处理， 而经过维数约减的数据可以更好地进行分析， 更容易可视化。 目 前维数约减算法大致可以分为两类，一类是线性的方法，如主成分分析法和 经典多维尺度算法，另一类是非线性的方法，如等距映射法、局域线性嵌入法 和自 组织等距嵌入法。 经典的 维数约 减 算法 有主 成分分 析法 ( p r i n c ip a l c o m p o n e n t a n a l y s i s , 缩写 为 p c a ) 3 , 4 和经典多维尺度算法 ( c l a s s i c a l m u lt i d im e n s i o n a l s c a l i n g , 缩写为 c m d s ) 。 主 成分分析法是由h o t e l l i n g 于1 9 3 3 年提出的， 因 此又被称为h o t e l l i n g 变换，该方法是利用维数约减的 思想， 把多指标转化为几个综合指标的多元统 计分析方法。由于各评价指标之间有一定的相关性，必然存在着起支配作用的 共同因素，因 此， 通过主成分分析法对原始指标变量 相关矩阵内部结构关系进 行研究，找出影响过程的几个综合指标， 使综合指标变为原来指标变量的线性 组合，它们不仅保留了原始变量的主要信息，彼此之间又不相关，更有助于抓 住主要矛盾。 经典多维尺度分析 ( c k d s ) 用于反映多个研究事物间的相似 ( 不相似) 程度， 通过适当的降维方法， 将这种相似 ( 不相似) 程度在低维度空间中用点与点之 间的 距离表示出来，并有可能帮助识别那些影响事物间相似性的 潜在因素。 天津大学硕士学位论文 第一章 绪论 。 信息的获取: 是通过传感器， 将光或声音等信息转化为电信息。信息可 以是二维的图 像如文字，图像等; 可以是一维的波形如声波，心电图， 脑电图; 也可以是物理量与逻辑值。 预处理: 包括a / d转换，二 值化，图 像的 平滑， 变换， 增强， 恢复， 滤 波等， 主要指图象处理。 特征抽取和选择:在模式识别中，需要进行特征的抽取和选择，例如， 一 幅6 4 x 6 4的图 像可以 得到1 2 8 个数据， 这种在测量空间的原始数据通过变换 获得在特征空间最能反映分类本质的特征。这就是特征提取和选择的过程。 分类器设计:分类器设计的主要功能是通过训练确定判决规则，使按此 判决规则分类时， 错误率最低，然后把这些判决规则建成标准库。 分类决策:在特征空间中对被识别对象进行分类。 1 . 3维数约减( d i m e n s i o n a l i t y r e d u c t i o n ) 维数约减是机器学习的重要主题。 真实世界的数据往往是高维的， 难于被人 理解、 表示和处理， 而经过维数约减的数据可以更好地进行分析， 更容易可视化。 目 前维数约减算法大致可以分为两类，一类是线性的方法，如主成分分析法和 经典多维尺度算法，另一类是非线性的方法，如等距映射法、局域线性嵌入法 和自 组织等距嵌入法。 经典的 维数约 减 算法 有主 成分分 析法 ( p r i n c ip a l c o m p o n e n t a n a l y s i s , 缩写 为 p c a ) 3 , 4 和经典多维尺度算法 ( c l a s s i c a l m u lt i d im e n s i o n a l s c a l i n g , 缩写为 c m d s ) 。 主 成分分析法是由h o t e l l i n g 于1 9 3 3 年提出的， 因 此又被称为h o t e l l i n g 变换，该方法是利用维数约减的 思想， 把多指标转化为几个综合指标的多元统 计分析方法。由于各评价指标之间有一定的相关性，必然存在着起支配作用的 共同因素，因 此， 通过主成分分析法对原始指标变量 相关矩阵内部结构关系进 行研究，找出影响过程的几个综合指标， 使综合指标变为原来指标变量的线性 组合，它们不仅保留了原始变量的主要信息，彼此之间又不相关，更有助于抓 住主要矛盾。 经典多维尺度分析 ( c k d s ) 用于反映多个研究事物间的相似 ( 不相似) 程度， 通过适当的降维方法， 将这种相似 ( 不相似) 程度在低维度空间中用点与点之 间的 距离表示出来，并有可能帮助识别那些影响事物间相似性的 潜在因素。 天津大学硕士学位论文 第一章 绪论 经典的维数约减方法，如p c a 和 c m d s ，实现简单，可以 确保发现处于高维 向量空间的线性子空间上的数据集的真实几何结构。但是这类算法的线性本质 使其无法揭示复杂的非线性流形 ( 流形是这样一种拓扑空间， 它是局域欧式的， 例如在每一个点的周围有一个邻域，该邻域从拓扑上等同于 n维空间的一个开 球) 结构。为 此， j o s h u a b . t e n e n b a u m e t a l 和s a m t . r o w e i s e t a l 提出了 各自 的 非 线性 维 数约减算 法: i s o m a p 5 , 6 , 7 和l l e 8 , 9 , 1 4 , 1 1 , 1 2 1 a 等距映射 ( i s o m e t ri c m a p p i n g ， 简写为i s o m a p ) 使用测地线距离 ( 所谓测地 线距离即两点在流形上的实际距离，例如我们在地面上以直线行走，实际上走 的是地球球体表面的大圆上的一段弧，这段弧称为测地线。 这是地球表面最接 近直线的轨迹。 )替代欧式距离，克服了 c m d s的局限性。它是一种全局优化算 法，建立在c m d s 基础之上，试图保持数据的内 在的几何特性，获得流形上数 据点之间的测地线距离。 算法的关键是估计远点 ( 非邻域点) 之间的测地线距 离。对于邻域点，工 s o m a p由 输入空间直接得到其测地线距离; 对于非邻域点， 其测地线距离可近似为一系列邻域点的测地线距离之和。 局域线性嵌入算法 ( l o c a l l y l i n e a r e m b e d d i n g ， 简写为l l e ) ，是一种无监 督的学习算法，该算法是基于一种几何直觉，它将每个输入向量看作是高维空 间中的一个点， 在其周围 有k个邻居，我们称之为邻域点， l l e利用该点的邻 域点的线性组合来重构这个点。映射由一个对称的局部线性重构而得，实际的 嵌入计算简化为求一个稀疏特征函数的问题。 s 工 e 1 3 则是基于一种几何的观点:一个全局等距的嵌入必然是局域等距 的，同样， 适当选定一组局域等距约束条件， 可以蕴含全局等距;s i e 综合了全 局算法和自 组织算法的优势，利用点集的距离分布作为等距约束条件，通过适 当 选取保持局域距离分布的局域等距映像，在概率意义上强迫出全局等距嵌入 映像。 s i e 的主要计算过程是局域的， 回避了 特征值问 题的计算， 可以直接分布 式实现。 14本文结构 本文首先对现有维数约减算法和统计模式识别的传统方法进行回顾和分析， 然后对两个具有良 好性能的非线性维数约减方法进行扩展和修改以适用于 分类 识别，最后通过仿真数据以及真实的人脸数据对算法进行测试。 天津大学硕士学位论文 第一章 绪论 经典的维数约减方法，如p c a 和 c m d s ，实现简单，可以 确保发现处于高维 向量空间的线性子空间上的数据集的真实几何结构。但是这类算法的线性本质 使其无法揭示复杂的非线性流形 ( 流形是这样一种拓扑空间， 它是局域欧式的， 例如在每一个点的周围有一个邻域，该邻域从拓扑上等同于 n维空间的一个开 球) 结构。为 此， j o s h u a b . t e n e n b a u m e t a l 和s a m t . r o w e i s e t a l 提出了 各自 的 非 线性 维 数约减算 法: i s o m a p 5 , 6 , 7 和l l e 8 , 9 , 1 4 , 1 1 , 1 2 1 a 等距映射 ( i s o m e t ri c m a p p i n g ， 简写为i s o m a p ) 使用测地线距离 ( 所谓测地 线距离即两点在流形上的实际距离，例如我们在地面上以直线行走，实际上走 的是地球球体表面的大圆上的一段弧，这段弧称为测地线。 这是地球表面最接 近直线的轨迹。 )替代欧式距离，克服了 c m d s的局限性。它是一种全局优化算 法，建立在c m d s 基础之上，试图保持数据的内 在的几何特性，获得流形上数 据点之间的测地线距离。 算法的关键是估计远点 ( 非邻域点) 之间的测地线距 离。对于邻域点，工 s o m a p由 输入空间直接得到其测地线距离; 对于非邻域点， 其测地线距离可近似为一系列邻域点的测地线距离之和。 局域线性嵌入算法 ( l o c a l l y l i n e a r e m b e d d i n g ， 简写为l l e ) ，是一种无监 督的学习算法，该算法是基于一种几何直觉，它将每个输入向量看作是高维空 间中的一个点， 在其周围 有k个邻居，我们称之为邻域点， l l e利用该点的邻 域点的线性组合来重构这个点。映射由一个对称的局部线性重构而得，实际的 嵌入计算简化为求一个稀疏特征函数的问题。 s 工 e 1 3 则是基于一种几何的观点:一个全局等距的嵌入必然是局域等距 的，同样， 适当选定一组局域等距约束条件， 可以蕴含全局等距;s i e 综合了全 局算法和自 组织算法的优势，利用点集的距离分布作为等距约束条件，通过适 当 选取保持局域距离分布的局域等距映像，在概率意义上强迫出全局等距嵌入 映像。 s i e 的主要计算过程是局域的， 回避了 特征值问 题的计算， 可以直接分布 式实现。 14本文结构 本文首先对现有维数约减算法和统计模式识别的传统方法进行回顾和分析， 然后对两个具有良 好性能的非线性维数约减方法进行扩展和修改以适用于 分类 识别，最后通过仿真数据以及真实的人脸数据对算法进行测试。 天津大学硕士学位论文第一章 绪论 本文的创新之处在于将非线性维数约减的方法引入到模式识别当中， 并验证 了基于非线性维数约减的模式识别的可用性。 本文的内容概要如下: 第二章 对维数约 减算法进行介绍， 分析各种维数约减算法的内 核。 第三章简单介绍了 模式识别的概念及其传统的特征提取方法。 第四章介绍了针对模式识别进行扩展和改进的非线性维数约减算法。 第五章首先介绍了本文实验所用平台ma t l a b的特点，并且对非线性维数 约减的分类实验进行分析和讨论。实验分为两个部分:第，一 部分是多视角图像 实验，即应用非线性维数约减算法进行多视角图像新数据扩展实验;第二部分 是真实数据的实验，首先对人脸图片真实数据用非线性维数约减算法进行处理， 然后对其进行后续的分类识别。 第六章是全文的总结和对未来工作的展望。 天津大学硕士学位论文第二章 维数约减算法 第二章 维数约减算法 在进行科学研究时， 所处理的数据通常是高维数据， 每个对象都用大量特征 来表示，当高维数据的维数达到几百甚至几千时，算法会很耗时。此外，高维 数据的存储和检索也是在进行科学研究时的难题。 对待高维数据， 通常的方法是首先对数据进行维数约减， 识别出其中最重要 的特性，然后再对数据加以处理，以保证处理过程简单化，并保证最终结果的 质 量不 会明显降 低。 在本文中 介绍四 种维 数约减算法: p c a , i s o m a p , l l 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 ) 方法正是实现这一目 的的 有效途径之一。 何为主成分? 简而言之， 主成分实际上就是由 原变量x l -x 线性组合出 来的 m 个互不相关、 且未丢失任何信息的新变量， 也称为综合变量。 多指标的主成分 分析常被用来寻找判断某种事物或现象的综合指标，并给综合指标所蕴藏的 信 息以 恰当解释，以 便更深刻地揭示事物内 在的规律。 设相关矩阵为r以及与之同 阶的单位矩阵为1 ,原始变量的个数为m ，则r 就是 m阶方阵， 特征值为a ，求各特征值x 的过程就是求解下列特征方程: r -人 川 = a ， 此方程的 左边展开后实际 上是一个入 的m阶多项式，其解由 大到 小依次排列为入 。 )入 : )人 . o 。主 成分分析的基本条件与主成分的基本性 天津大学硕士学位论文第二章 维数约减算法 第二章 维数约减算法 在进行科学研究时， 所处理的数据通常是高维数据， 每个对象都用大量特征 来表示，当高维数据的维数达到几百甚至几千时，算法会很耗时。此外，高维 数据的存储和检索也是在进行科学研究时的难题。 对待高维数据， 通常的方法是首先对数据进行维数约减， 识别出其中最重要 的特性，然后再对数据加以处理，以保证处理过程简单化，并保证最终结果的 质 量不 会明显降 低。 在本文中 介绍四 种维 数约减算法: p c a , i s o m a p , l l 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 ) 方法正是实现这一目 的的 有效途径之一。 何为主成分? 简而言之， 主成分实际上就是由 原变量x l -x 线性组合出 来的 m 个互不相关、 且未丢失任何信息的新变量， 也称为综合变量。 多指标的主成分 分析常被用来寻找判断某种事物或现象的综合指标，并给综合指标所蕴藏的 信 息以 恰当解释，以 便更深刻地揭示事物内 在的规律。 设相关矩阵为r以及与之同 阶的单位矩阵为1 ,原始变量的个数为m ，则r 就是 m阶方阵， 特征值为a ，求各特征值x 的过程就是求解下列特征方程: r -人 川 = a ， 此方程的 左边展开后实际 上是一个入 的m阶多项式，其解由 大到 小依次排列为入 。 )入 : )人 . o 。主 成分分析的基本条件与主成分的基本性 天津大学硕士学位论文第二章 维数约减算法 质可概述如下: 各主成分之间互不相关， 若原变量服从正态分布， 则各主成分之间互相独 立; 全部m 个主成分所反映的n 例样品的总信息，等于m 个原变量的总信息。 信息量的多少，用变量的方差来度量。若将 。个原变量标准化后，每个变量的 方差都为 1 ，故方差之和为m ，此时，求得的m 个主成分的方差之和也为m ; 各主成分的作用大小是:z 7 2 - i 个主成分的贡献率是 ( 人 ; / m ) 妻z . ; x 1 0 0 % 。 个 主 成 分 的 累 计 贡 献 率 是 。 全x ;) / m i x 10 0% 。 在 应 用 时 ， 一 般 取 累计贡献率为7 0 % - 8 0 % 或以上所对应的前p 个主成分即可。在数据所含的变量 个数、 样品数及累计贡献率固定的 前提下， p / 。 的比 值越小， 则说明此数据越适 合于主成分分析; 6(j r ( z , x ;) = c ,; ， 说明第i 个主成分z ， 与第j 个标准化变量x , 之间的相关系 数就是原变量数据之间的 协方差c ; ; 艺 r ( z ; x i ) = x ,， 说 明 第i 个 主 成 分z ; 与 m 个 标 准 化 变 量 中 的 每 个 变 量 月 之间的相关系数的平方和为由大到小排列后的第i 个特征值人 ， : 艺 r 2 ( z , x ; ) = 1 , 说 明。 个 主 成 分 分 别 与 第j 个 标 准 化 变 量 的 相 关 系 数 目 的平方和为1 ,即每个标准化变量的 信息由 全部主成分完全包含。 从上述过程可以 看出， 特征值是由 大到小依次排列的，在进行维数约减时， 取最大的d 个特征值所对应的特征向量，就可以将原数据约减到d 维。 c m d s 与p c a是很相似的算法， 只是它们的输入矩阵不相同， p c a要求输 入的是协方差矩阵，而c md s要求输入的是点到点的距离构成的矩阵。相同点 是两者要求的输入矩阵都应为对称的、半正定的。 2 . 2等距映射算法i s o m a p i s o m a p 是 一 种全局优化算法， 建立在c m d s 基础之上， 试图 保持数据的内 在的儿何特性，获得流形上数据点之间的测地线距离。算法的关键是估计远点 天津大学硕士学位论文第二章 维数约减算法 质可概述如下: 各主成分之间互不相关， 若原变量服从正态分布， 则各主成分之间互相独 立; 全部m 个主成分所反映的n 例样品的总信息，等于m 个原变量的总信息。 信息量的多少，用变量的方差来度量。若将 。个原变量标准化后，每个变量的 方差都为 1 ，故方差之和为m ，此时，求得的m 个主成分的方差之和也为m ; 各主成分的作用大小是:z 7 2 - i 个主成分的贡献率是 ( 人 ; / m ) 妻z . ; x 1 0 0 % 。 个 主 成 分 的 累 计 贡 献 率 是 。 全x ;) / m i x 10 0% 。 在 应 用 时 ， 一 般 取 累计贡献率为7 0 % - 8 0 % 或以上所对应的前p 个主成分即可。在数据所含的变量 个数、 样品数及累计贡献率固定的 前提下， p / 。 的比 值越小， 则说明此数据越适 合于主成分分析; 6(j r ( z , x ;) = c ,; ， 说明第i 个主成分z ， 与第j 个标准化变量x , 之间的相关系 数就是原变量数据之间的 协方差c ; ; 艺 r ( z ; x i ) = x ,， 说 明 第i 个 主 成 分z ; 与 m 个 标 准 化 变 量 中 的 每 个 变 量 月 之间的相关系数的平方和为由大到小排列后的第i 个特征值人 ， : 艺 r 2 ( z , x ; ) = 1 , 说 明。 个 主 成 分 分 别 与 第j 个 标 准 化 变 量 的 相 关 系 数 目 的平方和为1 ,即每个标准化变量的 信息由 全部主成分完全包含。 从上述过程可以 看出， 特征值是由 大到小依次排列的，在进行维数约减时， 取最大的d 个特征值所对应的特征向量，就可以将原数据约减到d 维。 c m d s 与p c a是很相似的算法， 只是它们的输入矩阵不相同， p c a要求输 入的是协方差矩阵，而c md s要求输入的是点到点的距离构成的矩阵。相同点 是两者要求的输入矩阵都应为对称的、半正定的。 2 . 2等距映射算法i s o m a p i s o m a p 是 一 种全局优化算法， 建立在c m d s 基础之上， 试图 保持数据的内 在的儿何特性，获得流形上数据点之间的测地线距离。算法的关键是估计远点 天津大学硕士学位论文第二章 维数约减算法 ( 非邻域点)之间的测地线距离。对于邻域点，由输入空间直接得到其测地线 距离;对于非邻域点，其测地线距离可近似为一系列邻域点的测地线距离之和。 i s o m a p 的 算法有三个步骤: 第一个步骤是确定在流形m上， 哪些点是相互邻域点。 对于输入空间x中 的点幼， 其欧式距离为d x ( i j ) o 将每一个点与 所有的点进行比 较，当 两点 之间的 距离小于固 定的半径( 或i 是j的k - 邻域) 就认为 它们是相邻的， 将其连接起 来，边长为d x ( i j ) ， 得到 有权图g . 。 第二 个步骤是通过计算最短路径d g ( i j ) 的方 法估计流形m上的测地线距离 d m ( i j ) 。 初 始时当i j 之1f 7 有一条 边， 则d c ( i j ) 二d x ( i j ) ; 否则d g ( i j ) = 。 对 所有 的 k = 1 ,2 , n , d g ( i j ) = m i n 由( i j ) , d c ( i , k ) + d g ( k j ) ， 这样得到矩阵d g = d c ( i j ) , 它是由图g中所有点对的最短路径组成的。 第 三 个 步 骤 是 应 用c m d s 构 造d 维 嵌 入。 令a ， 是 矩 阵: ( d c ) 的 第p 个 特征 值( 特 征 值已 按 降 序 排 列 ) ， 叮是 第p 个 特 征 向 量 的 第i 个 分 量， 令d 维 嵌 入向 量 .y ， 的 第 夕 个 分 量 等 于 仄 v p 。 2 . 3 局域线性嵌入(l l e ) l l e是基于一种几何直觉，它将每个输入向量看作是高维空间中的一个点， 在其周围有k个邻居，l l e利用该点的邻域点的线性组合来重构这个点，最后 利 用高 维 输 入向 量x 的 重构 权 值w +i 来计 算 高 维 数 据的 低 维 嵌入 坐 标。 l l e 算法的 第一步是鉴定每个数据点的 邻域。 简单地说， 就是鉴定与 每个数 据点比 较接近的邻域点数k 计算其欧式距离， 只要两个结点的欧式距离小于 某个规定的值，就认为那个结点是已知数据点的邻域点，所有这样点的集合被 称为是己知数据点的邻域。除欧式距离外还有一些标准也可以被用来选择邻域， 一种方法就是将指定半径的球域中所包含的数据点作为邻域。例如，可以将邻 域点定义为某个半径之内的所有点，直到达到某个预定的邻域点个数的上界。 一般来说，l l e 算法中邻域的选择需要利用先验知识。 算法的第二步是从邻域中重构每个点。 优化重构权值可以被计算出 来。 考虑 某 一 个 数 据 点 妥 ， 它 有k 个 邻 域 石 ， 和 重 构 权 值 w j ， 同 时 权 值 矩 阵 每 一 行 的 重 构权值w j 的 和是 i( 保证每个数据点的所有邻居权值和为 i ) 。这样我们就可以 将重构误差写为: 天津大学硕士学位论文第二章 维数约减算法 ( 非邻域点)之间的测地线距离。对于邻域点，由输入空间直接得到其测地线 距离;对于非邻域点，其测地线距离可近似为一系列邻域点的测地线距离之和。 i s o m a p 的 算法有三个步骤: 第一个步骤是确定在流形m上， 哪些点是相互邻域点。 对于输入空间x中 的点幼， 其欧式距离为d x ( i j ) o 将每一个点与 所有的点进行比 较，当 两点 之间的 距离小于固 定的半径( 或i 是j的k - 邻域) 就认为 它们是相邻的， 将其连接起 来，边长为d x ( i j ) ， 得到 有权图g . 。 第二 个步骤是通过计算最短路径d g ( i j ) 的方 法估计流形m上的测地线距离 d m ( i j ) 。 初 始时当i j 之1f 7 有一条 边， 则d c ( i j ) 二d x ( i j ) ; 否则d g ( i j ) = 。 对 所有 的 k = 1 ,2 , n , d g ( i j ) = m i n 由( i j ) , d c ( i , k ) + d g ( k j ) ， 这样得到矩阵d g = d c ( i j ) , 它是由图g中所有点对的最短路径组成的。 第 三 个 步 骤 是 应 用c m d s 构 造d 维 嵌 入。 令a ， 是 矩 阵: ( d c ) 的 第p 个 特征 值( 特 征 值已 按 降 序 排 列 ) ， 叮是 第p 个 特 征 向 量 的 第i 个 分 量， 令d 维 嵌 入向 量 .y ， 的 第 夕 个 分 量 等 于 仄 v p 。 2 . 3 局域线性嵌入(l l e ) l l e是基于一种几何直觉，它将每个输入向量看作是高维空间中的一个点， 在其周围有k个邻居，l l e利用该点的邻域点的线性组合来重构这个点，最后 利 用高 维 输 入向 量x 的 重构 权 值w +i 来计 算 高 维 数 据的 低 维 嵌入 坐 标。 l l e 算法的 第一步是鉴定每个数据点的 邻域。 简单地说， 就是鉴定与 每个数 据点比 较接近的邻域点数k 计算其欧式距离， 只要两个结点的欧式距离小于 某个规定的值，就认为那个结点是已知数据点的邻域点，所有这样点的集合被 称为是己知数据点的邻域。除欧式距离外还有一些标准也可以被用来选择邻域， 一种方法就是将指定半径的球域中所包含的数据点作为邻域。例如，可以将邻 域点定义为某个半径之内的所有点，直到达到某个预定的邻域点个数的上界。 一般来说，l l e 算法中邻域的选择需要利用先验知识。 算法的第二步是从邻域中重构每个点。 优化重构权值可以被计算出 来。 考虑