（计算机应用技术专业论文）流形学习算法的研究与应用.pdf

中文摘要 在信息时代，人们常要面对海量数据进行处理，且这样大量的数据仍在以几 何级的速度增长。这些海量数据中往往存在着大量的冗余，因此如何对数据进行 有效处理，找到数据间内在的规律并有效减少数据量，提取隐含信息，成为人工 智能、机器学习、数据挖掘等领域的核心问题之一。流形学习算法可以有效的发 现高维数据集的内在维度，对高维数据去粗取精，从而提高海量信息的处理效率。 本文主要关注于适用于海量数据的快速流形学习算法及其应用。 主流的流形学习算法分为线性和非线性两大类。出现较早的以p c a 算法为 代表的线性流形学习算法，其实现简单，但只适合具有线性流形结构的数据集； 以i s o m a p 、l l e 等为代表的非线性流形学习算法可以有效的发现非线性数据中 的流形，但这些流形学习算法的时间复杂度普遍较高，不适合处理海量的数据集。 基于锚点集的最小平方误差等距嵌入算法a i e 具有o ( n l o g ( n ) ) 的时间复杂性， 而在获得测地线距离后的计算时间复杂度达到对嵌入点数线性，且可以完全并行 实现，所以a i e 可以有效提高海量数据的处理速度。 传统搜索引擎技术主要依赖于用户输入的查询词提供搜索结果，这种方法在 查询词较短含义模糊的情况下无法准确把握用户需求所属的领域，因而降低了搜 索结果的质量。基于点击数据的查询扩展系统，通过对用户点击行为的捕获实时 判别用户需求，并采用a i e 压缩点击数据中隐含的网页差异性信息，大幅减少 了搜索引擎调用网页差异性信息的空间开销。 关键词：流形学习搜索引擎点击数据 a b s t i 认c t i l lt h ei n f o r m a t i o na g e ，p e o p l eo f t e nn e e dt of a c em a s s i v ed a t at op r o c e s s ，a n dt h i s l a r g ea m o u n to fd a t ai s s t i l li n c r e a s i n gi nag e o m e t r i c a lr a t e h o w e v e r , r e d u n d a n c y o f t e ne x i s t si nt h em a s s i v ed a t a s oh o wt oe f f e c t i v e l yp r o c e s st h e s ed a t a , f i n dt h e i n t e r n a ll a w sa n de f f e c t i v e l yr e d u c et h ev o l u m eo ft h ed a t aa n de x t r a c tt h eh i d d e n i n f o r m a t i o nb e c o m eo n eo f t h ec o r ei s s u e si na r t i f i c i a li n t e l l i g e n c e 、m a c h i n el e a r n i n g 、 d a t am i n i n ga n do t h e rf i e l d s t h em a n i f o l d - l e a r n i n ga l g o r i t h mc a ne f f e c t i v e l yf i n dt h e i n t e r n a ld i m e n s i o no ft h eh i 曲d i m e n s i o n a ld a t a , d i s c a r dt h ed r o s sa n dd i s c o v e rt h e e s s e n t i a lo ft h eh i g h - d i m e n s i o n a ld a t a ，a n dt h ep r o c e s s i n ge f f i c i e n c yo ft h em a s s i v e i n f o r m a t i o nc a nb ee n h a n c e d t h i sp a p e rf o c u s e so nt h er a p i dm a n i f o l d l e a r n i n g a l g o r i t h m ，w h i c hi sa p p l i c a b l et ot h em a s s i v e d a t a t h em a i n s t r e a mm a n i f o l d - l e a r n i n ga l g o r i t h mc a nb ed i v i d e di n t ot w oc l a s s e s 。 l i n e a ra n dn o n l i n e a r t h ee a r l i e rm a n i f o l d l e a r n i n ga l g o r i t h m sa r el i n e a ra l g o r i t h m s r e p r e s e n t e db yp c a ，t h ei m p l e m e n t a t i o no f t h i sc a t e g o r yo fa l g o r i t h m si ss i m p l e ，b u t i ti so n l ys u i t a b l ef o rt h el i n e a rd a t as e t s t h en o n l i n e a rm a n i f o l d l e a r n i n ga l g o r i t h m s r e p r e s e n t e db yi s o m a p 、l l ec a ne f f e c t i v e l yd i s c o v e rt h em a n i f o l d i nn o n l i n e a rd a t a , b u tt h e s em a n i f o l d l e a r n i n ga l g o r i t h m sg e n e r a l l yh a v eh i g ht i m ec o m p l e x i t y , n o t s u i t a b l ef o rp r o c e s s i n gm a s s i v ed a t as e t s t h ee m b e d d e da l g o r i t h ma n c h o rp o i n t s b a s e di s o m e t r i ce m b e d d i n gu n d e rl e a s ts q u a r ee r r o rc r i t e r i o n ( a i e ) h a sat i m e c o m p l e x i t yo fo ( nl o g ( n ) ) ，a n da f t e ro b t a i n e dg e o d e s i cd i s t a n c e si t h a sl i n e a rt i m e c o m p l e x i t yf o re m b e d d e dp o i n t sa n dc a nb ef u l l yr e a l i z e di np a r a l l e l ，s oa i ec a n e f f e c t i v e l yi m p r o v e t h ep r o c e s s i n gs p e e do fm a s s i v ed a t a t r a d i t i o n a ls e a r c he n g i n et e c h n o l o g i e sm a i n l yr e l yo nt h eu s e r si n p u ti n q u i r yt o p r o v i d et h es e a r c hr e s u l t s ，s oi nt h es i t u a t i o no f s h o r t e na n da m b i g u o u st e r mt h ef i e l d s o ft h eu s e r s d e m a n d sc a nn o tb ea c c u r a t e l yg r a s p e db yt h i sm e t h o d ，a n dt h eq u a l i t yo f t h es e a r c hr e s u l t si sl o w e r e d q u e r ye x p a n ds y s t e mb a s e do nc l i c k t h r o u g hd a t ac a n e s t i m a t et h er e q u i r e m e n t so ft h eu s e r si nr e a l - t i m et h r o u g ht h ec a p t u r eo ft h eu s e r s c l i c ka c t i o n a n db ya d o p t i n ga i et oc o m p r e s st h eh i d d e nw e b p a g ed i f f e r e n c e s i n f o r m a t i o ni nc l i c k t h r o u g hd a t as e t s ，i tc a ns i g n i f i c a n t l yr e d u c et h es p a c ec o s t sw h e n s e a r c he n g i n ec a l l st h ew e b p a g ed i f f e r e n c e si n f o r m a t i o n k e yw o r d s m a n i f o l d l e a r n i n g ，s e a r c he n g i n e ，c l i c k t h r o u g hd a t a 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得鑫盗盘堂或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文作者虢糯乙签字吼吲年w1 日 学位论文版权使用授权书 本学位论文作者完全了解墨洼苤堂有关保留、使用学位论文的规定。 特授权丕鲞盘堂可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：协激勉 签字日期：硼年2 月7 同 导师签名： 、 r _ 2 一， ) l ) 锡 签字嗍：p 7 年硼同 第一章绪论 1 1 研究背景和目的 第一章绪论 在当今快速发展的信息时代，人们在社会生活中获取的信息正在以几何级的 速度增长，随着信息技术深入到各个行业，各种高维的数据也开始以前所未有的 方式错综复杂的交织在一起。如何能够合理高效的处理这些海量数据，并从中挖 掘事物的本质规律成为了信息时代的重要课题。然而有时即便是通过很高性能的 计算机来处理这些海量数据其速度和准确率也不能令人满意。解决这个问题的关 键在于，原始的海量数据中有太多虚假的或者不能体现本质的噪声数据，只要计 算机能够自动去除这些噪声数据，只保留关键部分，那么就可以高效快速的挖掘 出数据的内部特征，并且对各类数据进行针对性的计算，达到机器学习、数据挖 掘的目的。找到适用于海量数据的这样的快速方法是本文要研究的重点。 随着网络环境的蓬勃发展，网络搜索引擎已经成为人们信息生活中不可或缺 的重要工具。如今的搜索引擎技术往往面临海量的数据进行处理。在用户使用搜 索引擎的过程中也产生了海量的点击数据，这些点击数据蕴含了用户对网页间差 异性的潜在评价。本文将研究利用这种网页差异性优化搜索引擎查询结果的方 法，并尝试将流形学习算法应用于处理这种数据。 1 2 研究现状 1 2 1 机器学习 机器学习是人工智能研究领域古老而又常新的课题。学习是一种具有多侧面 的现象。学习的过程有：获取新的陈述性知识、通过教育或实践发展机械技能和 认知能力、将新知识组织成为通用化和有效的表示形式、借助观察和实验发现新 的事实和新的理论。对多种形式的学习过程的研究以及对它们进行计算机模型化 构成了机器学习的主要内容【l j 。 机器学习其理论和应用涵盖了近年来人工智能领域的主要发展方向，机器学 习综合应用心理学、生物学和神经生理学以及数学、自动化和计算机科学形成机 器学习理论基础。结合各种学习方法，取长补短的多种形式的集成学习系统研究 正在兴起。特别是连接学习符号学习的耦合可以更好地解决连续性信号处理中知 第一章绪论 识与技能的获取与求精问题而受到重视。机器学习与人工智能各种基础问题的统 一性观点正在形成。 机器学习有以下三种不同的学习理论：基于连接的机器学习理论、基于符号 的机器学习理论和基于统计的机器学习理论。 1 基于连接的机器学习理论从人的大脑神经系统结构出发，研究非程序的、 适应性的、大脑风格的信息处理的本质和能力，研究大量简单的神经元 的集团信息处理能力及其动态行为。 2 基于符号主义的机器学习理论是最具人工智能色彩的机器学习研究，它 以物理符号系统假设为基础，认为物理符号系统是智能行为充分和必要 的条件。基于符号的机器学习理论建立的模型不具有统计性质而使其应 用受到很大的制约，在理论上，这类方法几乎没有理论基础，经验实现 远比理论分析重要。 3 基于统计的机器学习理论是利用事物之间的相关性，做出统计意义上的 推断和预测，但相关不是因果，单纯的统计方法无法挖掘出相关性背后 的隐参量和内在的因果机制，无法提供合理的本体解释。因而，单纯的 统计方法不具备创造性地运用知识和构建抽象概念的能力。 流形机器学习是重要的机器学习方法之一。很多问题的表示方法使得信息十 分稀疏，如何将信息稠密化是一个十分困难的问题，即著名的“维数灾难”。传 统的主成分分析是一种得到成功应用的方法，但是其只对线性情况有效。非线性 流形学习则可以有效的解决非线性问题。2 0 0 0 年，在科学上发表了三篇学 术论文【“】，从认知上讨论了流形学习，并首次使用了m a n i f o l dl e a r n i n g 术语， 标志着以非线性为主要特征的流形学习方法的诞生。在随后的这几年中涌现出许 多关于流形学习的研究论文，并在模式识别、语言处理等方面进行了实验性研究 和应用。在流形学习中，为了可以计算，一般需要对嵌入映射或者数据集所在的 低维流形作出不同的限制，或者以保持嵌入映射或者以保持低维流形的不同性质 为目标，就可以得到不同的流形学习方法。流形学习最重要的特点就是考虑观测 数据整体的性质，同时，又可以从局部出发，来完成对这个整体的计算。 1 2 2 机器学习方法介绍 目前，大量的时间问题不能使用已有的方法进行表示，在这些问题的驱动下， 提出了众多的机器学习方法。目前的机器学习方法种类繁多，研究思路多样【5 。1 0 】， 以下简单介绍几种机器学习方法【1 1 1 ： 1 强化学习( r e i n f o r c e m e n tl e a r n i n g ) 不同于其他大多数机器学习方法，强化学习不是建立在对问题世界一组观察 第一章绪论 的样本集合的基础上，而是将学习过程考虑为对变化环境的“适应 。目前，强 化学习主要是将变化环境的适应考虑为一类随机过程。由此，将学习建立在 m a r k o v 过程之上，以优化“环境一适应模型，并提出了一系列的优化方法。 这些方法的研究主要集中在计算效率上。 2 多示例学习( m u l t i i n s t a n c el e a r n i n g ) 在此类学习中，训练集由若干个具有概念标记的包( b a g ) 组成，每个包包 含了若干没有概念标记的示例。若一个包中至少有一个正例，则该包被标记为正 ( p o s i t i v e ) ；若一个包中所有示例都是反例，则该包被标记为反( n e g a t i v e ) 。通 过对训练包的学习，希望学习系统尽可能正确的对训练集之外的包的概念标记进 行预测。多示例学习中的训练样本的岐义性与其他机器学习方法完全不同。特别 重要的是在以往的各种学习框架中，一个样本就是一个示例，即样本和示例是一 对一的对应关系；在多示例学习中，一个样本( 即包) 包含了多个示例，即样本 和示例是一对多的对应关系。这就使得以往得学习方法难以很好得解决此类问 题。多示例学习具有的独特性质使其具有广泛的应用前景。 3 半监督学习( s e m i s u p e r v i s e dl e a r n i n g ) 传统的监督学习需要使用很多具有概念标记的训练样本，然而，在很多实际 的机器学习和数据挖掘应用中，虽然可以很容易的获得大量训练样本，但是为训 练样本提供概念标记却往往需要大量的人力和物力。例如在进行w e b 网页分类 时，可以很容易的从网络中获得大量的网页，但却很难要求用户花费大量时间来 为网页提供类别信息。如果能够充分利用大量的无标记的训练样本，也许可以弥 补标记训练样本的不足，正是这一需求导致了半监督学习的出现。目前已经出现 了很多有效的半监督学习方法，这些方法的共同特点是先基于有标记的训练样本 训练出一个学习器，利用该学习器来挑选一些合适的无标记的样本并对其进行学 习，然后利用新的有标记的样本来对学习器进行进一步的精化。 4 关系学习( r e l a t i o n a ll e a r n i n g ) 关系学习是伴随数据挖掘的兴起而开始被人们关注的一类机器学习方法，这 里的学习是将观测数据抽象为一阶谓词表示的形式。目前研究此类机器学习的方 法有四类：( 1 ) 一阶谓词方法，根据背景知识将观测数据抽象为一阶谓词表示的 假设；( 2 ) 从命题到关系；( 3 ) 从关系到命题；( 4 ) 概率方法，这类方法的焦点 是获得“关系”的结构。 5 r a n k i n g 学习( 1 e a r n i n gf o rr a n k i n g ) 这类机器学习来源于信息检索中提出的一个问题：用户查询获得的某个文 档，对其是否可以简单的处理为“需要或拒绝 ? 如果可以这样处理，经过对这 个用户一段时间的观察，可以形成一个样本集合，为其专门提供一个查询模型应 第一章绪论 该不是很困难的。然而，前提条件是用户的需求非常单一，显然这个条件是很难 达到的。绝大多数的用户其需求都复杂的多，他们可能同时具有多个兴趣，在查 询时，他们对这些兴趣有不同的优先顺序，这就是r a n k i n g 。这样，对机器学习 来说，问题就变成如何去学习这个r a n k i n g 的问题。目前在这类问题上机器学习 主要使用支持向量机。 6 数据流学习( d a t as t r e a ml e a r n i n g ) 在网络数据分析与处理中，有时从一个用户节点上流过的数据大多数是无意 义的，且由于数据量巨大而无法全部存储，因此只能简单的判断流过的文件是否 有用而无法细致的分析。如何学习一个模型可以完成这个任务，同时可以增量的 学习，可以保证从数据流中不断改善用户需求的模型，这是这类机器学习需要解 决的问题。 机器学习的发展到现在，不同的机器学习研究者相互启发与借鉴，将各种方 法取长补短，已经呈现出相互学习、相互交融的发展趋势 1 2 q 3 。 1 3 本文结构 依据本论文的研究内容和创新性，安排论文结构如下： 第一章介绍课题的研究背景、目的，综述了目前机器学习领域研究的现状和 一般的机器学习方法。 第二章介绍了多种有代表性的或后文涉及到的线性流形学习算法和非线性 流形学习算法。 第三章介绍了适用于处理海量数据的基于锚点集的最小平方误差等距嵌入 算法，对算法作了时间复杂性分析，并将该算法与其他主流算法作了实验比较。 第四章阐述了基于点击数据的搜索引擎查询扩展系统，从原理上论证了系统 的可行性和有效性，并且用仿真数据对差异性矩阵的性质作了实验验证。 第五章对全文的研究工作进行了总结，并且对未来研究工作的方向提出了建 议和展望。 第二章流形学习算法介绍 第二章流形学习算法介绍 流形学习就是要有效描述具有嵌入流形结构的数据集的相关性和发现数据 集内在规律。流形学习假定数据集在未知但存在的低维内在变量作用下，在观测 空间会形成高维流形。这一问题具有普遍性，在图像处理、语音、文本分析都存 在这一现象。 在计算机科学中，探索数据集流形结构可以追溯到图形识别的研究。而近年 来流形学习( m a n i f o l dl e a r n i n g ) 研究开始受到机器学习和其他领域研究人员的 广泛关注，这与2 0 0 0 年在s c i e n c e 上发表的三篇论文有密切的关系【列。流形学 习受到关注的另外一个原因是应用驱动。可以看到，随着计算能力的日益增强和 存储容量的增长，大规模的数据集开始越来越普遍，伴随着这些现象的是高维数 据的大量产生。这种高维的性质一方面导致维数灾难的出现，另一方面使人们不 能直接感知数据集内在的规律，而流形学习为学习这种隐藏在高维数据中的内在 低维结构和重构提供了解决方法。 流形学习算法目前主要分为线性和非线性两类，本章将分别进行介绍。 2 1 线性流形学习算法 2 1 1 主成分分析法( p c a ) 现代科学的研究过程往往是多学科交叉的，所涉及的实验非常复杂，尤其在 实际的统计实验中得到的数据维度很高，这些维度总有些是相关的、有些是不相 关的，人们当然希望找出其中彼此独立的指标，用尽量少的维度描述问题的变化 规律。 多变量分析最古老和最著名的技术当属主成分分析法( p r i n c i p a lc o m p o n e n t a n a l y s i s ，p c a ) 。最早i 扫p e a r s o n 1 4 】在1 9 0 1 年的生物学理论研究中引入。1 9 3 3 年，h o t e l l i n g 1 5 】将此想法应用于心理学研究。19 4 7 年，k a r h u n e n 1 6 1 用概 率论的形式再次将其显现出来。 p c a 的基本思想是t 将数量众多的原始的相关变量转换为数量较少的不相关 变量。通常的做法是将原始变量进行线性组合为若干综合变量，这些综合变量之 间不相关，并且尽可能表示原始变量包含的信息，选取最大的几个主成分进行分 析，这样就可以在尽可能少损失原有信息的基础上，降低数据的维度，提高运算 第二章流形学习算法介绍 的效率。 p c a 数学模型如下 1 7 】： 设有力个样品，每个样品观测p 项变量：x l ，x ：，x p ，得到原始数据资 料矩阵： 其中x i = 而， x 2 f ： x h l ， x = f = 1 ，p 浔和一圳 i 互= 口l l x l + a 2 1 x 2 + + 口p l x p j 疋2q 2 x 1 + a 2 2 x 2 + + 口，2 x p 【2 口l p x l + 口2 p x 2 + + 口伊x ， 上式可以简写成： e = q ，x i + a 2 ，五+ + 口x p f = 1 ，p 上述方程组要求： 口：+ 口刍+ + 口硝2 = 1 f = 1 ，p 系数a 打由下列原则决定： ( 1 ) 只与互( i ，f ，= 1 ，p ) 不相关； ( 2 ) 互是五，x ：，劫的一切线性组合中方差最大的，最是与互不相关的 x 。，z 2 ，坳一切线性组合中方差次大的，依此类推。 下面求解方程组的系数a 设f = a l x l + 口2 k + + 口p 石p 乡公 其中口= ( 口。，口：，口。) ，x = ( x z ，砭，x p ) 7 ，求主成分就是寻找x 的线性 函数a x 使相应的方差最大，且满足d a = 1 ，即： v a r ( a x ) = e ( a x e ( 口x ) ) 0 彳一e ( 口公) ) 7 = a e ( x e x ) ( x - e x ) 口 = a f 口 设协方差矩阵的特征根为a 如名。 0 ，相应的单位特征向量为 u 1 ) “2 ，u 口，令 第二章流形学习算法介绍 u a ( u l ，u 2 ，甜p ) = 0 九p p u = 饥“： ，= l 因此 口j 口= 乃口掣；口= 丑( 口“，) 2 又因为： a z 口 ( 口7 甜，) 2 = 口叫红= 五而且当口= u 1 使胁( 口达到最大值，且 v a r ( u lx ) = “l 越l = 五 同理 v a r ( u ，x ) = 以 而且 c o v ( “，彳，“，x ) ：“，甜，：p 九( “，“。) ( “j ) ：0 ，f 上述推导表明：x 。，x ：，x p 的主成分就是以的特征向量为系数的线性 组合，互不相关，方差为特征根。 从上述过程可以看出，特征值是从大到小依次排列，为衡量各个主成分对原 始变量的解释能力，将总方差中属于第i 个主成分的比例： 乃 五 称为第i 个主成分的贡献率。第一个主成分的贡献率最大，其次是第二个主成分， 再次是第三，在解决实际问题时一般取前面几个主要的成分，前珑个主成分 的贡献率之和 丑 兰! 五 称为m 个主成分的累计贡献率。通常取一个较小的所值使得累计贡献率达到一 个较高的百分比( 8 0 9 0 ) ，既达到了降维的目的，信息的损失也不是很大。 妒印； 刀 ” “ “ 第二章流形学习算法介绍 p c a 对椭球状分布的样本集有较好的效果，学习得到的主方向就是椭球的主 轴方向。该算法是一种非监督的算法，可以找到能最好的代表所有样本的方向， 但这个方向对于分类未必是最有利的。 2 1 2 经典多维尺度分析( c s ) 经典多维尺度分析( c l a s s i cm u l t i d i m e n s i o n a ls e a l i n g ，c m d s ) 研究这样的 问题：已知玎个研究样本点，每个研究样本点都可以表示为欧氏空间中的一个点。 假设已知研究样本点两两间的相异性度量( 可以是相似性度量) ，求出这刀个样本 点在该空间的散布图，使图中点间的欧氏距离与已知的相异性度量吻合得尽可能 好。 c m d s 的数学模型【1 8 】： 假设d = 儡 。是刀”维的距离矩阵，在d 维空间r d 中求刀个点毛，x 2 ，乇， 使得疗个点的距离与矩阵d 中的距离在某种意义下尽量接近。设求得的刀个点为 五，x 2 ，吒，表不为2 x = ( 而，为，而) 7 则称x 为距离矩阵d 的一个低维嵌入，由这玎个点之间的距离构成的距离阵 称为d 的拟合距离阵西。为证明方便，先引入中心矩阵的概念，其定义如下： 1 设中心矩阵h = i - - j ，其中厶是一个f n 维的单位矩阵，以是一个所 仃 有元素均为1 的刀玎维矩阵，于是 h = 并引入如。f = 两个简记符号： 彳= 【】，其中吻= 一寺如 b ：h a h 则b 中的一个元素由下式给出： = q ，一言喜一言喜+ 吉喜喜 定理：假设矩阵b 的p 个非零特征值a 五芝乙 o ( 乃+ 。= 乃= o ) 对应 的特征向量为五，五9o ，x 。，即有 r_j 。一玎。一露。一万 一 一 ； 一 第二章流形学习算法介绍 b x j = 五置 ( 2 - 1 ) 若五( f = 1 ，2 ，p ) 满足，五r 五= 五，令彳r = ( 五，五，x 。) ，则x r 是原始 距离矩阵d 的一个低维嵌入。 证明： 已知b x 7 一x r a = 0 以及r = 人( 人为由b 的p 个非零特征值构成的对角 矩阵) ， 令 m = 匕2 ) 匕譬 以及 y 7 = ( 五，4 ，小，艺) 其中，】，= ( + p ，) 中列向量标准正交，且正交于五( f = l ，2 ，p ) ，于是 有y 口y = 1 ，也就是说，y 是对应于召的以一p 个零特征值的特征向量。 于是( 2 1 ) 式转换为： byryrm=0(2-2) 令 其中 则 1 n2 = 2 l r ；，1 ll r ，= ，1 n i y = i 。， j 2 l 1 _。一一一 r tf = n2 y y ln 2 = i 。 l ( 2 2 ) 式两边同乘以1 ，即可得 1 b f y r 埘1 ：0 对上式进行数学变换，可以得到： =耐心琅1b y y r m n 。i y = y r ( ：r 1 胁r 1 】，：。：i 。， - 9 - d 。y 第二章流形学习算法介绍 = ( 五，五，4 0 ，o l 。 其中x r = ( 墨，五，砟) 在此认为x r 是嵌入空间坐标矩阵，x r 是一个l x p 的向量，即 n 下面证明x r 中的力个点构造的距离矩阵与原始距离矩阵d 相同。以d x ( f ，) 表示嵌入空间中第f 个点和第，个点之间的距离，有 d x ( f ，) = ( 薯一) 2 ( 五一x j ) = x 、- 2 x j t x j + x j t x j = 钆一2 岛j + = o n 一2 a g + 8 u = _ 2 = 略 证毕。 c m d s 通过计算高维空间中样本之间的相似性，并把这种相似性尽可能的在 低维空间得到保持，通过这种表示空间的转换，能有效降低高维空间中的数据表 示，并有可能帮助识别那些影响向量间相似度的潜在因素。 2 1 3 线性流形学习算法小结 作为最经典的线性流形学习算法，p c a 和c m d s 思路直观简洁，有严格的 数学基础，编码实现简单，可以确保发现处于高维向量空间的线性子空间上的数 据集的真实几何结构，在工程、化学和医学等科学研究中有着广泛的应用并取得 较好的实际效果。但是这类算法的线性本质使其无法解决高维空间的非线性流形 学习问题。 雕 r ，j。1 印 、厶 砟五 r 0 x 置 矿 似 x = = 第二章流形学习算法介绍 2 2 非线性流形学习算法 2 2 1 等距映射算法( i s o m a p ) 等距映射算法( i s o m e t r i cm a p p i n g ，i s o m a p ) 是一种全局优化算法，建立在 c m d s 基础之上。其基本思想是当数据集的分布具有低维嵌入流形结构时，可以 通过保距映射获得观测空间数据集在嵌入空间的表示。为此，算法利用样本间的 测地线距离来替代c m d s 中的欧氏距离，试图保持数据的内在几何特性，从而 使样本之间内部的距离信息在从高维到低维的流形学习过程中能够得到最大的 重构和恢复。测地线距离如图2 - 2 蓝色实线所示： 图2 - 2i s o m a p 测地线距离示意 i s o m a p 存在两个前提假设：1 高维数据中的低维流形与欧氏空间的一个子 集是整体等距的；2 与数据所在的流形等距的欧氏子空间的子集是一个凸集。 算法的关键问题是计算远点( 非邻域点) 之间的测地线距离。对于邻域点， 由输入空间可直接得到其测地线距离( 即以欧氏距离表示) ：对于非邻域点，其 测地线距离可近似为最短路径上的一系列邻域点的测地线距离之和。 i s o m a p 算法的步骤如下【1 9 】： 1 构造邻域图：可以采用k 邻域或e 邻域，以占邻域为例。将与当前样本 点的距离小于固定邻域半径占的所有点都认为是样本点的邻域点，则根 据输入空间z 中每两个样本点间的欧氏距离可以确定流形m 上点之间 的邻域关系。这些样本点之间的邻域关系通过一个加权无向图g 来表 示，邻域点之间的权为距离d r ( f ，) ； 2 估算点之间的测地线距离：将流形m 上点之间的测地线距离用图g 上 的最短路径距离作为近似估计。具体做法如下：若初始时点f 和点，之 第二章流形学习算法介绍 间存在连线，则吃( f ，j ) = 以( f 力；否则a o ( f ，) mo o 。对所有的样本点 k = 1 ，2 9 , o o ，n ，需要依次更新 靠( f ，)的值： a o ( f ，j ) = m i n d g ( f ，) ，如( f ，k ) + 如( k ，) ) ，这样最终得到的距离矩阵 d o ( f _ ，) = 如( f ，肼表示了图g 中每两点之间的最短距离； 3 构造低维嵌入：将c m d s 算法应用于最短距离矩阵d g ( f ，j ) = d g ( f ，) ) ， 构造d 维欧氏空间中的嵌入】，这个嵌入空间能够最大限度的保持流形 的内在几何特征。则d 维嵌入向量”的第p 个分量等于旯，嘭，其中旯， 是矩阵f ( d g ) 的第p 个特征值( 特征值已按降序排列) ，吃是第p 个特 征向量的第f 个分量。 i s o m a p 算法中使用d i j k s t r a 算法求锚点集到所有样本点的测地线距离的时间 开销为o ( n l o g ( n ) ) 【2 0 】，最后矩阵的特征值求解过程的复杂度为o ( n 2 ) ，因此 i s o m a p 算法的总体复杂度近似为o ( n 2 ) 。 作为一种非线性的流形学习算法，i s o m a p 适用于学习内部平坦的低维流形， 但不适合内在曲率较大的流形。因为对于内在曲率较大的流形，算法中的领域半 径选择会比较难以把握，选择过大的领域会产生短路现象，而过小的领域虽然能 保证整体结构的稳定但低维投影结果会产生大量的“空洞”，或使最短路径算法 重构的图不连通。 2 2 2 局域线性嵌入( l l e ) 局域线性嵌入算法( l o c a ll i n e a re m b e d d i n g ，l l e ) 是一种无监督的非线性 学习算法。该算法认为在局部意义下，数据的结构使线性的，或者所局部意义下 的点在一个超平面上。因此任意取一点，可以使用它周围的点( 称为邻域点) 的 线性组合来表示。映射由一个对称的局部线性重构而得，实际的嵌入计算简化为 求一个稀疏特征函数问题。 l l e 算法可以分为三个步骤【2 l 忽j ： 1 寻找每个样本点的k 个邻域点； 2 由每个样本点的邻域点计算出该样本点的局部重建权值矩阵； 3 由该样本点的局部重建权值矩阵和其邻域点计算出该样本点的输出值。 具体的算法流程如图2 3 所示。 第二章流形学习算法介绍 图2 3 l l e 算法流程 算法步骤分析如下： u 正算法的第一步：根据预先给定的k 值寻找每个点的邻域点。邻域点的确 定过程是非常复杂的，根据是否存在先验知识，可以将选择领域点的算法分为无 监督的和有监督的；在距离计算上，可以根据欧氏距离进行计算，也可以根据测 地线距离进行计算；此外还存在其他能够自适应的调整邻域点数目的方法。一般 情况下，只要选择的邻域点数在一定范围内就不会对结果有太大的影响，但是选 择的邻域点数如果太多或太少也会影响到嵌入结果，因此选择合适的邻域点数能 够有效的保证算法重构的低维流形嵌入质量。计算邻域点的过程虽然简单但相当 耗时，最坏情况下其复杂度为o ( d n ：1 ，其中d 为高维空间维数，为样本点数。 算法的第二步：由每个点的邻域点计算出最优的重构权值矩阵形，为此定 义最小费用函数如下： ( 聊= 防一，计 f 其中，霉是高维空间的输入向量，矿，是低维空间的输出向量。这一步的算法复杂 度是o ( d n k 3 ) 。 算法的第三步：保持权值矩阵形，不变，求样本点在低维空间中的嵌入映象 使得低维重构误差最小。在此可以重写最小费用函数为： 第二章流形学习算法介绍 ( y ) = m ，( 霉e ) ( 2 _ 3 ) 其中m 驴= 8 , j 一一+ 睨，显然m o 是- - + n x n 的稀疏对称矩阵。 k 式2 3 满足如下两个条件： 霉= 石，寺霉霉r = j ， ， ， 据此，可以将m 。变换成如下形式： m = ( ，一形) r ( j 一矽) 将m 的所有非零特征值从小到大排列，如果第一个特征值几乎接近于零， 那么舍去第一个特征值。为使费用函数最小，可取y 为m 的最小d 个非零特征 值所对应的特征向量，通常为m 的第2 个到第d + 1 个非零特征值所对应的特征 向量。该步算法复杂度为o ( d n 2 ) 。 与i s o m a p 算法保持全局测地线距离不变的思想不同，l l e 算法是通过局部 线性拟合来获得内在的全局线性结构。所以当局部流形近似成线性时l l e 算法 可取得满意的低维嵌入。另外l l e 算法提供了可以学习任意维的局部线性的低 维流形的能力。然而l l e 算法只适用于非闭合的流形学习并要求对样本采样充 分且平滑，此外该算法对噪音比较敏感。 2 2 3 拉普拉斯特征映像( l a p l a c i a ne i g e n m a p s ) 拉普拉斯特征映像( l a p l a c i a ne i g e n m a p s ) 的基本思想是在高维空间流形中 距离很近的点投影到低维空间中的流形映象也应该距离很近，通过两点间的加权 距离作为代价函数，可求得相应的结果。拉普拉斯特征映像最大的特点是计算效 率高，并且能够局域保持集合的属性和自然联结不变【2 3 】。 算法共分三步，对于d 维空间中的k 个点z 。，z ：，以所构成的高维流形， 要将其嵌入d 维空间中，得到d 维空间上的k 个点】j ；，e ，e ，描述如下： 1 构造邻域图。如果点i 和点是邻域点则将两点连接，我们有两种方法来寻 找一个点的邻域点： 1 ) s 一邻域法陋9 t 】。s 是一个正实数，如果两点间的距离小于占，则认为 这两点为邻域点。这种方法的优点是它是基于几何观点的，并且得到的 邻接矩阵是对称的，缺点是占的大小不容易确定。 2 ) | j 丘邻法【k 吼 。求出该点与其余点的距离，取前k 个距离最小的点，则 这个点就是k 近邻点。这种方法参数选取简单，所以我们通常采用这种 方法来获取邻域点。 第二章流形学习算法介绍 2 构造权值矩阵。仍然有两种方法构造权值矩阵： 1 ) 热核法。该方法是受到热核理论的启发而得出的，如果点f 和点j 是邻域 点，则两点间的权值设为： i i1 1 2 ：e x p ( 一嗵 f 2 ) 简单权值法。如果点f 和点j 是邻域点则两点间的权值设为1 ，否则可以 设为0 。 计算d 维嵌入。由第二步求得的权值矩阵形是一个d d 维的矩阵，对该矩 阵求特征值并把求得的特征值升序排列，然后求出这些特征值对应的特征向量， 取这些特征向量的前d 个分量作为嵌入低维空间上的流形映射。 拉普拉斯特征映像是局部的非线性算法，其突出特点是与谱图理论有着紧密 的联系。算法通过求解稀疏矩阵的特征值问题解析的求出整体最优解。由于该算 法可以使原空间中离的很近的点在低维空间中仍然保持很近，所以可以用于聚类 算法的数据预处理过程。 2 2 4 随机邻域嵌入 随机邻域嵌入( s t o c h a s t i cn e i g h b o re m b e d d i n g ，s n e ) 2 4 1 ，该算法没有采用 类似c m d s 的保距的思想，而是在高维空间数据点的欧氏距离基础上，定义了 邻域概率函数，使高维空间中构成邻域的点在低维空间中也能构成邻域。 算法分三步： 1 选择邻域。可以使用k 邻域法或者占邻域法。 2 计算p f 和g 玎。p 扩为在高维观测空间中，点属于f 邻域的概率函数( 非 对称) 由下面的公式确定： e x p ( - d ；) p u = 丽 其中露：呼，标准觏依据经验人为粮 根据该算法的思想，在低维空间，期望使原本在高维空间中临近的数据点接 近，原本在高维空间中远离的数据点彼此远离，因此，低维嵌入空间与高维观测 空间应该有相似的概率分布。所以与p 类似，得到低维空间中的邻域概率函数q 定义为： 驴一 第二章流形学习算法介绍 3 定义费用函数。低维嵌入的目标是使上面两个分布尽可能匹配，可利用 k u l l l e i b l e r 散度和来构造损失函数为： j = e z p 妒1 0 9 争= e 也( p , i i q , ) ( 2 - 4 ) t j 生0 i 4 最小化( 2 4 ) 式，相当于其求微分： 詈= 2 。一y ，b 扩一q o + p 鸣) v ，t i 上式可以理解为让远点尽可能分开同时使近点尽可能接近的动力总和。因此 可以通过梯度方法来调整低维空间中数据点集的相应位置。 这种方法是依赖于观测空间的数据集来调整内在的低维结构，而迭代法容易 使其损失函数的最小化陷入局部极小，这一方面需要进一步改善。 2 2 5 非线性流形学习算法小结 非线性流形学习方法自从提出以来收到广泛关注，上述的算法被提出后引发 了一系列的后续的研究。相对而言i s o m a p 算法是一种全局性算法，充分考虑了 所有样本点之间的相互作用信息，在认知上强调整体性，因而对于无噪声数据的 嵌入效果优于其他非线性流形学习算法，但是该算法仅适用于学习内部平坦的低 维流形，不适合学习具有较大的内在曲率的流形；l l e 和l a p l a e i a ne i g e n m a p s 算法是局部非线性算法，l l e 把高维空间中的流形看成局部线性结构，其低维嵌 入就是将“流形片 按照