（基础数学专业论文）一种非线性降维方法的研究.pdf

一种非线性降维方法的研究专业：基础数学硕士生：郑杰导师：。姚正安教授摘要局部线性嵌入( l o c a l l yl i n e a re l b e d d i n g ，简称l l e ) 是一种较好的非线性降维方法，这种方法对于位于某种非线性流形上的数据的降维有着比较好的效果但是这种方法对于其中一个重要参数近邻个数，太过敏感本文将另一种非线性降维方法c o n f o 珈a 1 一i s o m a p 中的一种度量数据之间距离的方法引入到l l e 方法中经过实验发现，新引入的距离对于近邻个数的选择有比较好的效果，可以使得实验的结果对近邻个数的选择不那么敏感一般而言，改进后的l l e 算法在近邻个数五的取值比较小的时候就可以得到良好的效果，而原始的l l e 算法要达到相同的效果，近邻个数石的取值通常要大很多通过分析，我们发现新引入的距离度量著没有增加l l e 算法的算法复杂度，而l l e 算法的算法复杂度是同近邻个数x 相关的，因此，在取得相同较好效果时，改进后的l l e 算法所需的开销比原始的l l e 算法要低同时，本文还将l l e 方法同主成份分析( p c a ) 方法相结合，先用l l e 方法将高维空间中的数据降到一个相对较低的空间中，这样可以保持原始空间中的非线性结构不变，然后再用p c a 降到我们所期望的维数，去掉一些噪声信息的影响，保留方差较大的变量，使得有用信息尽量保留通过实验发现，这种相结合的方法可以取得较好的效果，它比直接用p c a 降维或只用l l e 降维所取得的效果都要好关键词：局部线性嵌入，降维，近邻，主成份分析，多维数据s o m er e s e a r c ho nan o n l i n e a rd i m e n s i o n a h t yr e d u c t i o nm e t h o dm a j o r ：p u r em a t h e m 融i c 8n a m e ：z h e n gj ks u p e r v i s o r ：p r o f e s s o ry a oz h e n ga na b s t r a c tl o c a l l yl i n e a re m b e d d i n g ( l l e ) i sa9 0 0 dn 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 ，t h i sm e t h o di sg o o df o r t h ed a t at h a tl y i n go n an o n l i n e a rm a n i f 0 1 d b u ti tw a st o os e n s i t i v et oo n eo ft h ei 呻o r t a n tp a r 硼e t e r s t h en u m b e ro fn e a r e s tn e i g h b o r s t h i sp a p e ru s e da nm e t h o dw h i c hw a si n t r o d u c e di na n o t h e rn o n l i n e a rd i 陬e n s i o n a l i t yr e d u c t i o nm e t h o dc a l l e dc o n f o n n a l i s o m 印t om e a s u r et h ed i s t a n c eb e t w e e nt w os a d p l e si nl l ea l g o r i t h m t h r d u g he x p e r i m e n t s ，w ef i n dt h a tt h i sd i s t a n c em e a s u r e m e n ti sg o o df o rs e l e c t i n gt h en u m b e ro fn e a r e s tn e i g h b o r s ，t h er e s u l t so fe x p e r i m e n t sa r en o ts os e n s i t i v et ot h en u m b e ro fn e a r e s tn e i g h b o r s g e n e r a l l ys p e a k i n g ，t h ei m p r o v e dl l ea l g o r i t h mc a no b t a i ng o o dr e s u l t sw h e nt h en u i n b e ro fn e a r e s tn e i g h b o r s足i s 鲫a l l ，w h i l et h eo r i g i n a ll l ea 1 9 6 r i t h mw a n t st oo b t a i nt h es a m er e s u l t s ，t h en u m b e ro fn e a r e s tn e i g h b o r s 足硼a yb em u c hl a g e r a f t e ra n a l y z i n g ，w ef i n dt h a tt h en e wd i s t a n c em e a s u r 铋e n td o e sn o ti n c r e a s et h ec o m l ) l e x i t yo fl j 正a l g o r i t h ma n dt h ec o m p l e x i t yi sr e l a t i v et ot h en u m b e ro fn e a r e s tn e i g h b o r 足，s ot h ec o s to ft h ei m p r o v e du 上a l g o r i t h mi sl o w e rt h a nt h ec o s to ft h eo r i g i n a lu 正a l g o r i t h mw h e no b t a i n i n gt h es 鲫eg o o dr e s u l t s a tt h es a m et i m e ，t h i sp a p e rc o m b i n e dt h el l ea n dp r i n c i p a lc o m p o n e n ta n a l y s is ( p c a ) m e t h o d s w eu s e dl l et or e d u c et h ed i i i l e n s i o no f t h ed a t ai n t h eh i g hd i m e n s i o ns p a c ef i r s t ，t h i sc a np r e s e r v et h en o n l i n e a rs t r u c t u r ei nt h eo r i g i ns p a c e ，a n dt h e nu s e dp c at or e d u c et h ed i m e n s i o nt ow h a tw eh o n e d p c ac a nr e m o v et h ei n f l u e n c eo fs o m eo u t l i e r s8 n dk e e pt h ev a r i a b l ew i t h1 a r g ec o v a r i a n c e ，s ot h a ti tc a nk e e pt h em o s tu s e f u li n f o r m a t i 。n a f t e rd o i n gs o m ee x p e r i m e n t sw ef i n dt h a tt h i sc o m b i n e dm e t h o dc a no b t a i n b e t t e rr e s u l t st h a ne i t h e rl l eo rp c am e t h o d k e y 们r d ：l o c a l l yl i n e a re i 出e d d i n g ，d i m e n s i o n a l i t yr e d u c t i o n ，n e a r e s tn e i g h b o r ，p r i n c i p a lc 唧o n e n ta n a l y s i s ，m u l t i d i m e n s i o n a ld a t ai i i中山大学硕士学位论文第一章引言第一章引言1 1 什么是数据挖掘与知识发现1 1 1 什么是数据挖掘与知识发现数据挖掘与知识发现是人工智能、机器学习与数据库技术相结合的产物机器学习( m a c h i n el e ”n i n g ) 是用计算机模拟人类学习的一门科学，它开始于6 0 年代末，而真正的发展则是在7 0 年代末由于在专家系统开发中存在知识获取的“瓶颈”现象，所以就用机器学习来完成知识的自动获取k d d 的全称是k n 0 w l e d g ed i s c o v e r yi nd a t a b a s e ，通常称之为知识发现，它是信息时代对数据库和人工智能研究者提出的更高要求随着数据库技术的不断发展以及数据库系统的广泛应用，数据库中存储的数据量急剧增大但目前数据库系统所能做到的一般只是对数据库中已有的数据进行存取，人们只能看到这些数据的一些表面的东西，而不能看到隐藏在这些数据之后的更重要的、更本质的信息，例如关于这些数据的整体特征的描述和发展趋势的预测等等而后一种信息对决策过程具有重要的意义这就要求我们将研究重点从数据的存储和传输能力转移到数据的分析能力上来k d d 研究是信息技术的汇总，它融数据库技术、人工智能技术、数理统计技术和可视化技术为一体，是一个多学科相互交叉融合所形成的一个新兴的具有广泛应用前景的研究领域1 1 2k d d 的核心数据挖掘数据挖掘是k d d 最核心的部分，是采用机器学习、统计以及其他数学、计算机方法进行知识学习的阶段数据挖掘算法的好坏将直接影响到所发现知识的好坏目前大多数的研究都集中在数据挖掘算法和应用上人们往往不严格区分数据挖掘和数据库中的知识发现，把两者混淆使用一般在科研领域中称为k d d ，而在工程领域则称为数据挖掘中山大学硕i 学位论文第一章引言数据挖掘的任务是从数据中发现模式模式是一个用语言l 来表示的一个表达式e ，它可用来描述数据集f 中数据的特性，e 所描述的数据是集合f 的一个子集f e e 作为一个模式要求它比列举数据子集f e 中所有元素的描述方法简单例如，“如果成绩在8 l 9 0 之间，则成绩优良”可称为一个模式，而“如果成绩为8 1 、8 2 、8 3 、8 4 、8 5 、8 6 、8 7 、8 8 、8 9 或9 0 ，则成绩优良”就不能称之为一个模式模式有很多种，按功能可分有两大类：预测型( p r e d i c t i v e ) 模式和描述型( d e s c r i p t i v e ) 模式，一预测型模式是可以根据数据项的值精确确定某种结果的模式，挖掘预测型模式所使用的数据也都是可以明确知道结果的例如，根据各种动物的资料，可以建立这样的模式：凡是胎生的动物都是哺乳类动物当有新的动物资料时，就可以根据这个模式判别此动物是否是哺乳动物一描述型模式是对数据中存在的规则做一种描述，或者根据数据的相似性把数据分组描述型模式不能直接用于预测例如。在地球上，7 0 的表面被水覆盖，3 0 是土地1 1 3 知识发现( 1 函d ) 的处理过程及其特点k d d 是一个多步骤的处理过程整个发现过程也不是简单的线性流程，步骤之间包含了循环和反复主要处理步骤如下：( 1 ) 准备：熟悉应用领域的数据和背景知识( 2 ) 确定k d d 的目标：根据用户要求。确定所要完成的k d d 是发现何种类型的知识，确定知识模式( 3 ) 数据收集和选择：根据发现任务从数据库中提取相关的数据集合( 4 ) 数据预处理：对与发现任务相关的数据集合进行再加工，检查数据的完整性和一致性。并消除数据中的噪音( 5 ) 确定知识发现方法：根据发现任务的目标和发现知识的模式，设计或选择合适的知识发现算法( 6 ) 发现模式：调用相应的算法发现所需的知识中山大学硕士学位论文第一章引言( 7 ) 模式解释和知识评价：对发现的模式进行解释，将发现的知识以一种适当的形式呈现给用户其中包括对知识一致性、新颖性和有效性的评价1 1 4k d d 过程采用的主要技术一个k d d 的具体过程需要采用的主要技术有：( 1 ) 特征提取：从与学习任务相关的一组数据中提取出关于这些数据的特征式这些特征式表达了该数据集的总体特征( 2 ) 分类：根据数据的不同特征式，将其划分为不同的数据类目前已有许多数据分类方法，如归纳法、决策树方法、神经网络方法和簇集方法等( 3 ) 聚类：根据所处理的数据的一些属性( 特征) ，对一些数据进行分类，经过分类以后的数据，在各类之间其相似程度很小，而在某一类内部，其数据之间的相似度则很大分类结束后，每类中的数据由唯一的标志进行标识，类中的数据的共同特征也被提取出来用于对该类的特征描述( 4 ) 相关性分析：发现特征之问或数据之间的相互依赖关系，常用技术有回归分析、信念网络等( 5 ) 偏差分析：如分类中的反常实例、例外模式、观测结果对期望值的偏离以及量值随时间的变化等等其基本思想是寻找观察结果与参照量之间的有意义的差别研究k d d 的方法有很多，各种方法都可能有自己的应用领域，并没有万能的k d d 方法能适合所有的应用所以在k d d 的研究和应用中，我们应该一方面进步深入研究我们自己提出的知识发现方法另一方面，k d d 是从现实世界的真实数据出发，从中抽取出能应用到现实世界中去的知识，而现实世界没有一成不变的模式因此在应用研究中更应该发挥本地化的优势，针对我们自己的应用领域，提出适应我国国情的背景知识和应用目标的k d d 方法和工具中山大学硕士学位论文第一章弓i 言1 2 降维在纷繁芜杂的自然界和人类社会中存在着大量的复杂事物及现象，长久以来，人们就一直不断的研究新的观察工具，发展新的观察技术，希望利用这些工具和技术能够获得对观察对象更加准确、更加完整的信息，从而揭示隐藏在丰富多彩的表面现象下的事物本质和客观规律由于采用了多种观察工具和方法，人们对于客观事物的描述往往是多方面的，比如在气象学上，用来描述气象特征的指标就非常多，例如温度，湿度，气压，风力，降雨量，辐射强度等等。这样对于每时每刻的天气状况，可以用这些变量组成的f 向量数据来细致的表示这些用多个变量描述客观事物和现象的数据，抽象出来就是高维数据毫无疑问，一方面高维数据提供了有关客观事物和现象的极其丰富、详细的信息；但是，另一方面，数据维数的大幅度提高也给随后人们的数据处理工作带来了巨大的困难“维数灾难”的概念是由b e l l m a n 在1 9 6 1 年提出的。它代表了这样一个事实：在给定逼近精度的条件下，估计一个多元函数所需的样本点数随着变量个数的增加以指数形式增长这个结论对高维数据统计方法的影响是极其深刻的例如，太多数的密度光滑函数是基于观察数据的局部均值，但由于“维数灾难”所引起的高维数据空间的稀疏性，为了保证精度就必须找足够多的点，从而使得多元光滑函数要延伸到很远的地方，从而失去了局部性考虑这样一个数据处理系统( 例如语言信号数据、图像数据或是各种模式数据处理系统) ，它要求输入是实值向量，这个系统只在每个输入数据的维数不太高时才能有效地工作而当向量维数过高时，就必须采取一定的措施，使得这些高维数据维数降低，才能使系统能够处理这些数据和正常工作，这类措施就是我们现在越来越多提及的降维方法在很多情形下，首先将数据的维数降低到一个合理的大小，同时尽可能多的保留原始的信息，然后褥将降维后的数据送入处理系统，这样的做法将是非常有用甚至是必须的图1 1 描述了一般的离维数据处理过程，降维是作为整个数据处理系统的预处理手段出现的中山大学硕士学位论文第一章引言融数据蛔一，瞵蚺一圈、一一砷蛙以直接处理有些时候，我们观察的现象表面上看是高维的、复杂的，实际上可以用很少的简单的变量来支配，例如：1 基因序列的建模蛋白质是由氨基酸组成的序列，氨基酸分子的个数从几十个到成千上万不等具有相同空间结构的蛋白质但氨基酸排列不同一一被分为同一组中，这就是所谓的蛋白质组( 类似于基因组) 通过蛋白质组模型可以了解不同蛋白质组的特殊的性质，能够有助于辨别和发现新组研究蛋白质组模型的概率方法包括隐马尔可夫模型和密度神经网络2 语音建模语音识别无疑是一个复杂的过程，- 但是据推测，这个过程可以用5 个变量就可以很好的实现在这种情况下降维方法是对这些现象进行建模的有力工具之所以能对高维数据进行降维，是因为数据的原始表示常常包含大量冗余信息：有些变量的变化比测量引入的噪声还要小，因此可以看作是无关的：有些变量和其他的变量有很强的相关性( 例如是其他变量的线性组合或是其他函数依赖关系) 。可以找到一组新的不相关的变量来代替原来的变萎；在许多情形下可以从一定程度上剔除这些冗余信息，获得更加经济的表示方式目前国内外对于降维问题的研究工作更多的是对具体降维方法的理论探索和应用研究，面对于降维基础理论及高维数据空间性质的研究尚不完善英国s h e f f i e l d 大学的c a r r e i r 8 一p e r p i n a n 博士 1 在综合分析各种降维方法的基础上，提出了一种抽象的模型，美国s t a n f o r d 大学的d o n o h o 3 教授等人对于高维数据空间和维数灾难现象进行了比较深入的研究，获得了很有指导意义的结果，中山大学硕士学位论文第一章引言国内则鲜有这方面研究工作的报道作为分析和研究高维数据的重要手段，降维问题具有重要的理论与应用价值，正引起越来越多的关注1 3 本文的结构在第二章中，介绍了一下有关降维的一些基本概念和方法第三章和第四章则具体介绍了本文主要研究对象，局部线性嵌入( l l e ) 1 2 ，1 3 ，1 5 方法的原理与算法，以及目前的一些相关研究结果第五章中，对l l e 算法进行了一点改进，使得该算法对近邻个数k 的取值不是那么敏感第六章则将l l e 方法和主成份分析( p c a ) 6 ，2 0 ，2 2 ，2 3 ，2 5 方法相结合，相关实验表明这种相结合的方法是具有一定优越性的中山大学硕士学位论文第二章降维方法的一些基本概念第二章降维方法的一些基本概念2 1 降维的定义假设我们得到d 维空间上的一个( 实向量) 样本集 t ) 兰降维问题基于如下之基本假设：高维数据( 样本) 实际上( 至少是非常近似地) 位于一个维数比数据空间的维数小得多的流形上降维的目的就是获得这流形的低维的坐标表示定义1 _ 1 降维问题的模型为( x ，f ) ，其中：x = “) ：! ：。是d 维空间中的一个数据集( 一般是r 。中的一个子集) ；映射砖x 哼y ，x h y = f ( x ) ，j ，是d 维空间( 一般是中的子集，d d ) 称f 为从x 到y 的一个降维定义l _ 2 称映射，：r _ m c 胪，y h x = ，o ) ，为嵌入映射同一高维数据通过不同的降维会得到不同的低维表示，而不同的高维数据通过降维可能得到相同的低维表示，因此对降维后具有相同低维表示的不同高维数据进行区分依赖于嵌入映射的区别降维后的低维表示和嵌入映射一起唯一的决定着一个高维数据2 2 降维方法的分类般将降维方法分为两类，一类是线性方法，另一类是非线性方法定义l3 设z = “，屯，) 7 是高维空间中的一个向量，通过降维中山大学硕士学位论文第= 章降维方法的一些基本概念瞧毛：为)，)，)得到低维空间中的向量y = ( m ，儿，儿) 7 如果f 的每个分量f 都是x 的线性函数，则称f 为线性降维；否则，称为非线性降维常用的线性降维方法一般有主成份分析( p c a ) 6 ，2 0 ，2 2 ，2 3 ，2 5 ，2 6 和线性判别分析( l d a ) 2 0 这一类方法思想比较直观，计算也比较简单，因此在很多问题中被经鬻采用但这类方法一般只适合处理线性数据，对于菲线性程度较高的数据效果却不是很好使用较多的非线性降维方法包括核主成份分析( k p c a ) 6 ，2 3 ，3 1 、自组织映射( s o m ) 1 9 ，2 1 等等它们对于非线性数据的处理都有较好的应用然而，这些方法都有一两个共同的缺点：1 ) 有太多的参数需要使用者去调试：2 ) 由于通常采用的是迭代的方法来求解，所以收敛速度比较慢或者收敛到的是局部极值非线性降维方法的另一个方向基于将原始空间划分为一些局部子空间的集合，这些子空间可以看成是近似线性的，然后在这些子空间上采用线性方法来降维，如：l 0 c a lp c a 7 ，2 6 这种方法会导致每一个子空闻都有自己的一个坐标系，这显然不如整个空间只使用一个坐标系方便但是，这种由局部来逼近全局的思想是值得借鉴的局部线性嵌入( l l e ) 就是这样一种方法，它保持局部几何结构不变，而相互重叠的局部邻域可以提供整体的几何结构信息从而傈持整体几何结构的不变局部线性嵌入方法的优点在于：1 ) 在嵌入空间中很好的保持了高维空间中的局部几何性质；2 ) 只有两个参数需要调整；3 ) 整个空间具有一个全局坐标系；4 ) 求解过程避免了迭代，褥到的结果是全局最优解2 3 主成份分析( p r i n c i p a lc o m p o n e n ta n a l y s i s ，简称p c a )下面我们来介绍一下一种最常用的线性降维方法主成份分析主成份分析就是寻找用较少的新变量代替原来较多的旧变量，而且使新变量尽可能多地保留原来信息的方法对同一个体进行多项观察时，必定涉及多个随机变=、，m 甲：巧五疋，。l=rf中山大学硕士学位论文第二章降维方法的一些基本概念量z ，五，嚣，它们都是具有相关性的，一时难以综合这时就需要借助主成份分析来概括诸多信息的主要方面我们希望有一个或几个较好的综合指标来概括信息，而且希望综合指标互相独立的各代表某一方面的性质任何一个度量指标的好坏除了可靠、真实之外，还必须能充分反映个体间的变异如果有一项指标，不同个体的取值都大同小异，那么该指标不能用来区分不同的个体由这一点来看，一项指标在个体间的变异越大越好因此我们把“变异大”作为“好”的标准来寻求综合指标而这种“变异”，在统计上我们可以用方差来表示，方差越大就表示个体之间的差异越大p c a 将方差的大小作为衡量信息量多少的标准，认为方差越大提供的信息越多，反之提供的信息就越少p c a 通过线性变换保留方差大、含信息多的分量，丢掉信息含量少的方向，从而降低数据的维数考虑原始数据空间五。中的样本 置，兰，其样本均值为i = 专置，协方- 毕l差矩阵为= 占( x 一飘z 一面7 它可以分解为= u a u 7 ，其中a 是由的特征值构成的对角阵，u 是正交阵，是a 对应的特征向量构成的特征矩阵构成u 的特征向量就称为主成份主成份变换y = u 7 ( z i ) ，得到一个新的数据集合 i ) 二，这个数据集的均值为o ，协方差矩阵为对角阵a ，这样就去除了原来变量之间的相关性我们丢掉那些方差较小的变量，就是将原数据投影到由前l 个最大的主成份张成的线性子空间上，从而降低数据的维数图2 1给出了p c a 的一个例子中山大学硕士学位论文第二章降维方法的一些基本概念在几何上，由个主成份张成的子空间是到原始数据距离最近的同归平面在这个意义下，p c a 是一种与标准的线性回归不同的对称的回归方法：p c a 中所有的分量在做变换时的地位是一样的；而在线性回归方法中有自变量和应变量的区别，自变量的选择不同，得到的结果也不同p c a 的关键性质是：它能得到一个从胄。到的最佳线性映射，这里最佳是指在均方误差最小意义下p c a 的不足之处是1 它是一种线性映射，不能正确处理位于非线性流形上的数据；2 我们不清楚应该保留多少个主成份，尽管有一些粗略规则可以使用，例如舍弃其中方差小于某个门限的成份中山大学硕士学位论文第三章局部线性嵌入第三章局部线性嵌入( l o c a yl i n e a re m b e d d i n g )我们对世界的感知是通过处理大量的感觉器官的输入信息而形成的，这些信息包括图像象素点的亮度，声音的功率谱，人体关节的连接角度等等虽然这种形式的复杂刺激可以简单的用高维空间中的点来表示，但是它们通常都有更加紧凑的描述事物结构的连续性导致了输入之间有很强的相关性，例如图像相邻的象索之间，因而观察值实际上位于一个低维的光滑流形上对这种非线性流形进行建模对于将这些观察进行比较和分类，进而研究客观世界起着至关重要的作用致力于探索性数据分析或是多元数据可视化的研究人员也面临同样的降维问题主成份分析和其他一些线性降维方法作为经典的降维方法，易于实现，算法高效，能够找出位于高维输入向量空间的一个线性子空间上数据的线性结构然而许多数据集合本质上含有用线性降维方法( 如p c a ) 不能发现的非线性结构，因而需要用非线性的降维方法来进行处理局部线性嵌入是s a u l 和r 伽e i s 1 2 ，1 3 ，15 在2 0 0 0 年时提出的一种非线性降维方法它的思想是用局部的线性来逼近全局的非线性，保持局部的几何结构不变，通过相互重叠的局部邻域来提供整体的信息，从而保持整体的几何性质我们假设样本集由个d 维实值向量置组成，所有样本点都处于一个d 维似伪流形上当样本点足够多( 流形被很好的采样) 时，我们可以近似认为每一个样本点和它的近邻是处在一个局部线性流形上在这种情况，每一个样本点都可以用它的近邻的带权线性组合来表示。而这些权重系数就反映了这一小块区域的局部几何信息利用这些信息，我们可以找到一个低维嵌入空间，使得在这一低维空间中仍然保持原来高维空间中的几何特性通过这些重叠的局部邻域，我们就可以得到整体的信息，从而得到一个全局坐标系统这方法的关键之处就在于：用局部的线性结构来逼近全局的非线性结构这种做法并不会产生显著的错误，因为在每小块局部上，流形的曲率并不是很大，即在每一小块局部上，流形可近似的看成是平坦的中山大学硕士学位论文第三章局部线性嵌入l l e 算法l l e 采用由个d 维向量组成的矩阵j 。_ 作为输入，输出则是一个由个d 维向量( d d ) 组成的矩阵l 。矩阵y 的第j 列对应的是矩阵x 中的第t列算法主要由三步构成：s t e p l 在高维空间中寻找每一个点的近邻点，构成一块块局部邻域对于高维空间中的每个样本点置，f = l ，2 ，我们计算它和其他一1 个样本点之间的距离根据它们之间距离的远近，我们可以找到每个置的近邻点。通常我们采用欧氏距离来度量两个点之间的距离，即嘭= 0 z 一肛而近邻点的选择般有两种方法：( 1 ) 选择前j ；：个离置最近的点作为其近邻；( 2 ) 所有位于以置为中心。为半径的超球面之内的点都作为z 的近邻两种方法都有一个参数需要调试，但是置近邻的方法一般采用的比较多，因为每个点具有相同的近邻个数，可以使褥计算上更为简便s t e p 2 计算每个点墨与它的近邻点之间的权重对于每个置，我们找到它的置个近邻之后，下一步的工作就是要给这个点和它的每个近邻之间赋上一个权重，这个权重刻画了两点之间的近似程度例如：如果墨和一是近邻t 那么它们之闯的权重可以定义为：一划= p2 。，其中仃是一个参数通常采用的方法是将权重看成是由置的近邻t 重构置时，一所做出的贡献，即最小化下式：中山大学硕士学位论文第三章局部线性嵌入。( 矽) ：兰0 _ 一窆矧0= lj l其中= o ，如果不是置的近邻；且= l( 为了保持平移不变- 1性) 要姒聊最小卿对每个州忖，要虹啥卜芸五卜、g c 彤，= i 卜一芸- ：峪( 五一埘i i 州( = l j - i= j ，= 彬彤”，( 彬= ( w j ，w ：2 ，一，咄) ，即形中不为零的k 个分量)其中：= ( 五一置) 7 ( 墨一以) ，c ：局部协方差矩阵最小化( 1 ) 即：m i n 形c 彤7w i t h彬。，= l ，由拉格朗日乘子法，得：m i n 工= 彬c 形7 + 丑( 彬，一1 )扭南，彬= 篙扣一i 研形2 丁万，= ( 1 ，l ，1 ) 7十枷叫咿旦剜坠越=，一一ccpp五一22 2一一=彰即中山大学硕士学位论文第三章局部线性嵌入当世 d 时，c 为奇异阵，需要加上一个正则项，即在对角线上加上一个正常数：c c 一瓠争吼其中：n ( c ) 为c 的迹，2 1 s t e p 3 计算低维嵌入空间中的僵l l e 的最后一个步骤是根据高维空间中的样本置和它的近邻置之间的权重h 来计算低维嵌入空间中的值由于我们的目标是在低维空间中尽量保持高维空间中的局部线性结构，而权重又代表着局部信息，因此我们将权重心固定，而使下面的损失函数最小化：妒c 砷= 喜肛一凳c z ，n1n我们要求= o且吉r p = ，以使得( y ) 对平移、旋转和i l ij f i i伸缩变换都具有不变性声t y ，= 善9 z 一芸峋= 打( ( y 一孵y ( y 一孵”= 加( y 7 y y 7 矿y y 7 矽7 y + y 7 矿7 y )= ，( ，u 一矽一矽7 + 矽7 ) 即= 护( y 7 ( j 一曲( ，一形) y )= 护( ，肘y ) ，其中：肘= ( ，一) 7 ( ，一) ，故，在i = o 且吉r f = ，条件下，最小化妒( y ) ，_ 1，= l1 4中山大学硕士学位论文第三章局部线性嵌入1即在r = o 且寺r f = 条件下，最小化护( y 7 胛)陪lvj e l由r a y l e i t z r i t z 定理：对h e r m i t i a n 矩阵彳= 4 + ，其特征值五s 五五，我们有：五x + x x + 出 x + x ，、寸k c ”矗：m a x 华：m a x x + 出， 2 珊百。赠一出 ：m i n 兰娑：m i n x + 出l - ox + x，+ x = 1故，使( 2 ) 式最小化的解为由矩阵m 的最小几个特征值所对应的特征向量构成的矩阵我们取m 的最小的d + 1 个特征值对应的特征向量，丢掉其中最小的特征值对应的特征向量，剩余的d 个特征向量组成的矩阵就是我们得到的低维空间中的样本我们之所以丢掉最小的特征值对应的特征向量，是因为最小特征值为零，其对应的特征向量的每个分量都为一丢掉这个特征向量可以满足条件耳= ol l下面我们小结一下l l e 算法的过程：1 找出高维空间中每个点置的置个近邻2 计算每一对近邻之间的权重，使得每个点置由它的足个近邻重构时的误差达到最小，即m t n c 矿，= 喜l f z ，一凳w 。x ，f | 2 ，其中且= o ，如果一不是五的近邻，= 1= l中山丈学硕士学位论文第三章局部线性嵌入3 保持上一步计算出的权重不变，计算出低维空间中的点使得损失函数( 2 ) 最小，即其中m t n c y ) = 喜怍一善i | 2 m i n ( y ) = 忆一刚，ih，- 1j jr = o 且整个过程如下图所示：专缸= ，图3 11 6中山丈学顽士学位论文第四章l l e 的一些相关研究第四章l l e 的一些相关研究在这一章中，我们回顾一下有关l l e 的一些相关研究，包括：如何处理新的数据；如何选择k 值；有监督的l l e 算法；基于核函数( k e r n e l ) 的l l e 算法4 1 如何扩展l l e 算法来处理新加入的数据原始的l l e 算法对数据来说是静态的，也就是说，它要求将整个样本集作为输入，然后将整个样本集映射到一个低维嵌入空间中，得到在嵌入空间中相应的样本当有新的样本点加入时，必须将这些新的样本点和原来的那些样本合并，一起作为l l e 的输入，重新运行一次l l e 算法显然，这对于一些处于经常变换、动态环境下的数据并不是很适用因为，如果每加入一个新的样本点，我们就要重新使用一次l l e 算法，这样所需要的开销太大 8 ，1 0 ，1 3 ，5 中提出了一些方法来处理新加入的数据。假设在加入新的数据之后，低维嵌入空间的维数d 依然保持不变k 表示原来的样本集，它一共包含了个样本我们先对如使用l l e 算法，计算出权重矩阵阡知和嵌入空间中的样本r 对于新来的一个样本x 。，只需计算h + 。到k 。中所有点的距离，取离z 。最近的足个样本作为h + 。的近邻，而j o 中所有样本点的近邻都不改变这样，”知“= o ，f = l ，2 ，我们只需要计算，= l ，2 ，根据( 1 )式，可以得到这些h 。，= 1 ，2 ，那么，降= u 降+ i 然后再由s t e p 3计算y 或者可以更加简单一点，y 。= w 州乃实验表明，这样做跟对j i l置。= 以。u 以+ 再使用l l e 计算所得到的结果非常近似这两种方法所得到的结果相差只有1 0 1 5 另一种方法基于这样一个假设：新来的数据是来自于已经被l l e 映射到嵌入空间的那部分高维空间设，= 1 ，2 ，为原始数据，= 如，二对，使用中山大学硕士学位论文第四章l l e 的一些相关研究l l e 算法，得到嵌入空间中的样本饥 二我们可以近似的认为乃= 乃，其中0是一个线性变换，乙= 乃巧1 对于新加入的样本x 。，先找到h + 。在原始样本集，中的最近邻，由于和h 。非常接近，那么，近似的有蜥。= ：h + r我们还可以采用神经网络的方法来处理新的数据对于原始样本集r 坞，先做l l e ，得到嵌入空间中的样本以) 兰然后，将“) 二作为输入， _ ! ：。作为输出，训练一个神经网络当有新的数据h + 。加入时，只需要将h + 。作为输入放迸已经训练好的神经网络当中，就可以得到蜘。4 2 如何选择近邻的个数在原始的l l e 算法中，我们有两个参数需要调试，一个是每个样本点的近邻个数足，另一个是嵌入空间的维数d 。在某些情况下，我们希望嵌入空间的维数固定，比如说，当我们对多维数据进行分析的目标是使得这些数据可视化时，我们要求d = 2 或d = 3 ，这时，就只需要考虑x 了但是该如何选择一个合适的k 值呢? 如果选择的置的值太大就会丢失原始数据所处的流形的局部信息；如果选择的k 的值太小，会导致原来连续的流形分裂成互不相连的子流形在 9 中，作者采用了一种度量来估计高维空间和低维嵌入空间结构的相似性，根据这个度量来选择最优的足这种度量称为剩余协方差：l 一露，4 p 为矩阵d i 和珥的相关系数珥和d r 分别表示高维空间和低维空间中样本点之间的距离矩阵1 一露，珥越小，就表示高维空间和低维空间的结构越相似因此，最优的置值，如可以定义为：k 咧2 a r g 哑n ( 1 一噍马)中山大学硕士学位论文第四章l l e 的一些相关研究4 3 有监督的l l e 算法( s u p e r v i s e dl l e )前面我们所介绍的各种l l e 算法都是基于无监督学习的这些方法通常是在我们不知道数据的类别和不同类之问关系的时候使用，用来观察数据的结构，以决定下一步该做什么由于是无监督学习，原始的l l e 算法没有考虑数据的类别信息而有监督的学习，则充分考虑数据的类别信息，在分类和预测问题上应用得更为广泛在 8 ，1 0 中，作者提出了两种有监督的l l e 算法，这两种方法都充分考虑了数据的类别信息第一种方法：对于每一个样本点葺，在找它的近邻的时候只考虑和置属于同一类的样本点，和薯不同类的样本点都不算是五的近邻，即使它和蕾之间的距离更近第二种方法：如果两个样本点分别属于不同的类，则扩大它们之间的距离，否则，保持它们之间的距离不变这样，在原始高维空间中属于不同的类的样本点之间就会分得越开，那么。当这些样本点映射到低维嵌入空间中之后，也会保持这种分得比较开的状况，这就更有利于分类设n 为高维空间中样本与样本之间的距离矩阵，定义改进的距离矩阵q 为：。，f q ，如果样本点属于同一类，n 。1 q + 口m 缸( q ) ，如果样本点不属于同一类，i q + 口m 缸( q ) ，如果样本点不属于同一类，其中口是属于 o ，1 的一个参数，口越大，类别信息对每个点的近邻的选择的影响就越大反之，贷越小，类别信息对每个点的近邻的选择的影响就越小这两种方法在寻找样本的近邻的时候都考虑了样本的类别信息，在试验中这两种方法都得到了较好的效果4 4 基于核函数( k e r n e l ) 的l l e 算法通常情况下，l l e 在计算样本点之间的距离的时候，一般采用的都是欧氏距离，我们同样也可以采用其他的一些距离 2 一文中，采用的基于m e r c e r 核的距离巾山大学硕士学位论文第四章l l e 的一些相关研究考虑一个d 维的样本集j ，m e r c e r 核足( 薯，x ，) 隐式的将两个d 维输入空间的样本投影到一个特征空间中，并且返回它们在特征空间的内积：世( 一，x ，) s ( 薯) ( x ，) ，表示从原始空间到特征空间的一个映射，但是通常情况下我们是无法知道这个映射的，而通过核函数足( ，) ，我们不需要知道庐，从原始空间的样本的值就可以求出样本在特征空间的内积这样，通过核函数我们可以将原始空间的数据投影到一个高维的非线性特征空间( 通常是无限维) ，但是可以避免可能会在高维空间中产生的维数灾难最简单的核函数是线性核，可以用内积表示：置( 地= w s 珥v采用线性核所得的结果和传统方法所得的结果是相同的，通常速度会更慢，因为一般情况下d 另一种常用的核函数是多项式核：足 ，v ) = q v + ，) 4 ，d 表示多项式的次数而最常用的核函数是径向基函数：足( “，d = p2 ”，仃表示方差那么原始空间中的样本和x ，在特征空间中的距离为：嘞；如，( 庐( 蕾) ，庐( _ ”s ( 眵( 玉) 一声( _ ) 8 2 ) ，这个距离可以由核函数直接求出吒s ( 8 妒( 葺) 一( _ ) 8 2 )2 ( ( 墨) 一声( ) ) ( ( ) 一声( ) )= ( 薯) 妒( t ) 一2 妒( 玉) 声( 一) + 矿( ) ( 一)2 足( 而，) 一2 置( ，) + 丘( ，)2 0中山大学硕士学位论文第四章l l e 的一些相关研究= 属i 丽，其中= 足( ，) 基于核函数的l l e 算法的思想是：在特征空间中寻找样本的近邻，而不是在原始空间中寻找近邻为了找到最优的权重向量使得用样本薯的置个近邻来重构时的误差最小，我们需要计算特征空间中的局部协方差矩阵：讥，坼e 玎( 薯) ，刁( ) 表示的置个近邻的集合原始的l l e 算法中，使用的是原始空间中的局部协方差矩阵：= ( 薯一) ( 一一托) 而特征空间中的局部协方差矩阵为：c 肚= ( ( 薯) 一声( ) ) ( 庐( ) 一矿( 耳) )= ( 薯) ( 蕾) 一( 五) 巾( ) 一矿( ) 妒( t ) + 声( ) ( )= 置( 薯，五) 一置( ，) 一足( 薯，t ) + 置( ，杖)= k h k b k * + x # -这样，对每个样本置，我们都可以求出它的局部协方差矩阵，然后按照原来的l l e算法，就可以计算出权重矩阵缈和嵌入空间的样本y 4 5 实验通常情况下最常采用的降维方法是主成份分析( p c a ) ，但是p c a 是一种线性的方法，对于那些非线性的数据来说，效果不是很好下面我们用u c i 的一个手写数字的数据库来作为实验数据，比较一下p c a 和l l e 的效果u c i 的这个手写数字数据库包含了一个训练集和个测试集，训练集中有3 8 2 3 个样本，测试集包含1 7 9 7 个样本，每个样本是一个6 5 维的向量，其中最后一维表示该样本的类标我们取了训练集中的1 0 0 0 个样本做训练，取测试集中的5 0 0 个样本做测试在实验中，我们采用的是最近邻方法对数据进行分类，即对每个测试样本，在训练集中找它的最近邻，然后将它归入其最近邻所属的那一类实验结果如下：p c a ：对1 0 0 0 个训练样本做主成份分析，找到前d 个最大特征值所对应的特征向量，即前d 个主成份然后将训练样本和测试样本都投影到这d 个主成份上，再用最近邻方法对测试数据进行分类，平均错误率如下表：维数d23456789平均错0 4 1 40 3 0 40 2 3 2o 1 7 60 1 1 80 1 0 4o 0 8 6o 0 7 4误率l l e ：对1 0 0 0 个训练样本做l l e ，计算出d 维嵌入空间中的样本值，然后根据 1 3 中所提出的处理新数据的方法，计算出5 0 0 个测试样本在嵌入空间的值，然后也用最近邻方法对钡4 试集进行分类，平均错误率如下表：d = 之d = 3d = 4d = 5k = 5o 1 4 6o 1 3 4o 0 9 0o 0 8 8k = 60 0 9 60 0 9 6o 0 7 40 0 5 8k = 70 1 7 00 1 3 00 0 8 20 0 7 2k - s0 1 3 00 1 3 0o 1 0 2o 0 7 2k = 9o 1 7 20 1 0 40 0 8 60 0 7 0k = l oo 2 2 4o 1 4 6o 1 1 60 1 0 2k = l lo 2 7 8o 1 5 4o 1 1 0o 0 8 6k = 1 2o _ 3 2 4o 2 1 40 1 7 20 1 1 2k = 1 3o 4 0 4o 1 9 6o 1 6 0o 1 3 2k = 1 40 3 0 40 1 9 6o 1 5 00 1 0 2k = 1 5o 3 5 4o 2 5 80 2 2 00 1 8 4d = 6d = 7d = 8d = 9k = 50 0 7 40 0 7 60 0 7 20 0 6 6k = 60 0 5 6o 0 6 40 0 6 6o 0 7 6中山大学硕士学位论文第四章l l e 的一些相关研究k = 70 0 7 40 0 6 80 0 7 4o 0 6 4k = 8o 0 7 4o 0 7 00 0 7 2o 0 7 0k = 9o 0 7 20 0 7 80 0 6 2o 0 5 6k = 1 0o 0 8 2o 0 8 0o 0 7 0o 0 7 6k = l l0 0 8o 0 8 6o 0 7 6o 0 8 2k = 1 2o 1 1 8o 0 9 40