（计算数学专业论文）自相交流形学习方法.pdf

摘要 数据降维是用低维结构来表达高维数据之间关系的方法。许多非线性降维 和流形学习方法如等距映射算法( i s o m a p ) ，局部线性嵌入法( l l e ) 以及局部切 空间排列法f l t s a ) 都是通过欧氏距离下的邻域来获得局部线性结构，然后将 这些局部信息非线性地映射到一个全局的低维嵌入空间。然而，当高维数据所 逼近或近似的一个低维流形自相交时，欧氏距离意义上的邻域不能完全反映低 维点的相邻关系，往往难以体现真实的局部线性结构。此时，原有的这些降维 方法失去作用。为了解决这个问题，本文提出一种自相交流形学习算法，其核心 内容是基于切空间分类的邻域选取方法，主要是通过逐步建立分层邻域图储存 正确的邻域关系，以获取有效的局部低维结构。我们首先根据邻域的低维线性 逼近来定义具有可靠切空间的正则点，然后根据正则点切空间的分类对正则点 的邻域进行强正则化，从而建立正则点之间正确的邻域关系。然后以此为基础， 逐步对非正则点邻域中的邻点进行鉴别和筛选，最终建立所有样本点之间正确 的邻域关系。我们还给出了两维和三维欧氏空间中自相交曲线和曲面的例子， 以及更高维空间中的实际例子，以说明该算法的有效性。 关键词：流形学习，数据降维，自相交，切空间分类 a b s t r a c t d i m e n s i o n a lr e d u c t i o nt e c h n i q u e sa r eu s e df o rr e p r e s e n t i n gt h er e l a t i o n - s h i pa m o n gh i g h e r - d i m e n s i o n a ld a t ab yal o w e r d i m e n s i o n a ls t r u c t u r e m a n y a l g o r i t h m sf o rm a n i f o l dl e a r n i n ga n dn o n l i n e a rd i m e n s i o n a lr e d u c t i o ns u c ha s i s o m e i t r i cm a p p i n g ( i s o m a p ) ，l o c a ll i n e a re m b e d d i n g ( l l e ) a n dl o c a lt a n g e n t s p a c ea l i g n m e n t ( l t s a ) , m e r g et h el o c a ll i n e a rg e o m e t r yo b t a i n e db ye u c l i d e a n n e i g h b o r h o o dt oag l o b a le m b e d d i n gs p a c e h o w e v e r ，w h e nt h eu n d e r l y i n gl o w e r - d i m e n s i o n a lm a n i f o l di ss e l f - i n t e r s e c t i n ga ts o m ep o i n t s ，i t sd i f f i c u l tt oo b t a i n l o c a ll o w e r - d i m e n s i o n a ls t r u c t u r ef r o mt h ee u c l i d e a nn e i g h b o r h o o d s i nt h i s c a s e ，t h e s ed i m e n s i o n a lr e d u c t i o nm e t h o d sc a nn o tb eu s e dd i r e c t l y t os o l v e t h i sp r o b l e m ，w ep r e s e n tam e t h o do fs e l f _ i n t e r s e c t i n gm a n i f o l dl e a r n i n g t h e c o r eo ft h i sm e t h o di st os e l e c tn e i g h b o r h o o dp o i n t sb a s e do nt a n g e n ts p a c e c l u s t e r i n g w ec o n s t r u c tal a y e r e dn e i g h b o r g r a p ht os t o r a g et h et r u s t e di n f o r m a t i o no fl o wd i m e n s i o n a ln e i g h b o r h o o d w ef i r s td e f i n er e g u l a rp o i n t sb yl o - c a ll o w d i n l e n s i o n a la p p r o x i m a t i o n ，s t r o n g l yr e g u l a r i z et h e i rn e i g h b o r h o o db a s e d o nc l u s t e r i n gt a n g e n ts p a c e s ，a n db u i l dt h en e i g h b o rr e l a t i o n s h i pa m o n gt h e s e r e g u l a rp o i n t s b a s e do nt h i sr e l a t i o n s h i p ，w eg r a d u a l l yc o n f i r mo t h e rp o i n t s n e i g h b o r h o o d ，a n db u i l dt h en e i g h b o rr e l a t i o n s h i pa m o n ga l lt h ep o i n t s w ei l l u s t r a t eo u rm e t h o d su s i n gd a t af r o ms e l f - i n t e r s e c t i n gc u r v e s ，s u r f a c e si n2 d 3 d a n dh i g h e r - d i m e n s i o n a ls p a c e s k e y w o r d s ：d i m e n s i o n a lr e d u c t i o n ，m a n i f o l dl e a r n i n g ，s e l f - i n t e r s e c t i n g ，t a n g e n t s p a c e sc l u s t e r i n g 第一章引言 1 1 流形学习的意义与应用背景 现代信息科学研究过程中经常会遇到大量的高维数据，如全球气候模型， 图形图像分类，文本分类及基因序列信息系统等。比如天气状况，随着气象学 的发展，用来描述天气特征的指标越来越多，如温度，湿度，气压，风力，降雨 量，辐射强度等等，将这些用多个变量描述的数据抽象出来就是高维数据。高 维数据一方面为客观现象提供了丰富详细的信息，但另一方面也给数据处理带 来了困难。如何从大量的数据特征中提取本质的，或者用户感兴趣的信息，是 一个具有挑战性的课题。数据降维的目的就是希望在保持某种本质特征如流形 距离的情况下，从这些大量的，无序的，有噪声的，随机的，不完全的数据中提 取隐含在数据背后的潜在的有用信息。 考虑由n 张人脸图像组成的数据集。每张图像都是2 5 6 2 5 6 大小的灰度图 矩阵，图像矩阵的每个元素对应相应位置的灰度值大小。如果将每张图像按 行或列排列成一个列向量，即用一个高维向量来表示一张图像，其向量维数 为2 5 6 2 5 6 = 6 5 5 3 6 。因而这n 张图像构成了一个非常高维的数据集。对如此高 维数的数据，通常无法直接采用常用的数据处理方法( 如分类，识别等) 。而人脸 采样图像往往由光线亮度，人与相机的距离，人的头部姿势，人的脸部肌肉等因 素决定，这些特征的个数要比图像对应的列向量维数小的多。对这些高维数据 进行非线性降维，即，用低维向量表示每个图像并且尽可能地保持图像之间所 隐藏的相关联的本质的非线性关系( 如图像的光线亮度，拍摄角度等) ，在分类、 识别、以及关联性的数据分析中，显得尤其重要。 数据降维问题可以模型化为这样一个流形学习问题：给定m 维欧氏空 间中n 个样本点x l ，z 2 ，z 。，其中孔r ”近似地采自于一个d ( d m ) 维流 形m 4 c r m ，即， x i = ，( n ) + c i ，i = 1 ，凡， 其中矗表示相应的扰动。数据降维的目标是保持数据之间某种关系如流形距离 不变，寻找样本点z 。对应的低维嵌入几。 第一章引言 2 1 2 降维方法及其局限性 真实世界的数据往往是高维的，高维数据往往难以被人分析，而经过 降维的数据却比较容易分析，所以数据降维成为现代机器学习和数据挖掘 研究中的一个热点。数据降维算法大致分为两类：一类是线性降维，如主分 量分析( 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 5 ) ，多尺度变换( m u l t i d i m e n s i o n a l s c a l i n g 目1 m d s 6 , 7 1 ) 另一类是非线性降维或者流形学习，如等距映射算法 ( i s o m a p ) 1 ，局部线性嵌入法( l l e ) 【3 以及局部切空间排列法( l t s a ) h 。 主分量分析方法( p c a ) 5 】是使用最广泛的线性降维方法之一。h o t e l l i n g 在1 9 3 3 年提出了p c a 算法，这种方法将方差的大小作为衡量信息量多少的标 准，认为方差越大，信息量越多。p c a 通过原分量的线性组合构造方差大、信息 量多的分量，从而达到降维的目的。p c a 的计算过程通过奇异值分解f s i n g u l a - v a l u ed e c o m p o s i t i o n 即s v d ) 来实现。从高维到低维投影距离最小这个意义上来 讲，p c a 是最佳的线性映射。它的主要不足之处在于，当样本点具有非线性性 质时，采用p c a 得到的降维结果无法反映出样本点所隐藏的非线性信息。 多尺度变换( m d s ) 6 ，7 也是广泛应用的线性降维方法。它的基本思想是， 降维后的低维空间中任意两点之间的距离，应该与在原高维空间中的距离相 同。由于欧氏距离不能真正反映出非线性的样本点之间的距离关系，而m d s 的 嵌入结果是保持高维样本点之间的欧氏距离，因此对于非线性流形上的数据， m d s 不能恢复出其中的低维结构。 经典的线性降维方法，通过特征的线性组合来降维，可以确保发现处于高 维线性空间的数据集的几何结构，并且实现起来简单，容易计算。但是这类算 法无法揭示复杂的非线性流形结构。为此，人们提出了非线性降维方法以处理 非线性的高维空间中的数据点。 近些年来，流形学习作为一种非线性降维方法，在图像处理( 如人脸图像、 手写数字图像处理) 以及语言处理等方面得到了广泛应用。关于流形学习，最具 影响力的是2 0 0 0 年j b t e n e n b a u m 等和s t r o w e i s 等人在s c i e n c e 上发表的两 篇文章。他们提出了各自的流形学习算法：等距映射( i s o m e i t r i c m a p p i n g ，简称 为i s o m a p 】1 ) 以及局部线性嵌入( l o c a l l yl i n e a xe m b e d d i n g ，简称为l l e 3 1 ) 等距映射( 1 s o m a p ) 1 建立在多维尺度变换( m d s ) 阳，7 1 的基础上，力求保 持数据点的内在几何性质，即保持两点间的测地距离。它用两点的最短路径逼 近流形距离，并构造距离矩阵，作为经典的m d s 方法中的差异性矩阵，从而构 第一章引言 3 造高维数据空间到低维参数空间的等距映射。i s o m a p 的缺陷在于，它要求所对 应的低维等距子集是一个凸集。此外，当样本点的密度不大，或分布不均匀时， 测地距离的计算有较大的误差，这使得i s o m a p 的计算结果有较多的空洞现象。 局部线性嵌入( l l e ) 3 的基本思想是在样本点和它的邻域点之间构造一个 重构权向量，并在低维空间中保持每个邻域中的权值不变，即假设嵌入映射在 局部是线性的条件下，最小化重构误差。l l e 认为所构造的重构权能掌握局 部邻域的本质上的几何性质一即那些在平移、旋转、缩放中保持不变的性质。 l l e 首先在每个样本点寻找它的最近邻域，然后通过求解一个有约束的最小二 乘问题以获得重构权。求出重构权后，利用这些重构权可以构造一个稀疏矩阵， l l e 通过求解这个稀疏矩阵的最小的几个特阵向量来获得全局的低维嵌入。其 缺陷在于，对于样本密度稀疏，有噪音，或者相互关联较弱的数据集，l l e 很可 能将相隔较远的点映射到邻近点的位置。 在i s o m a p 和l l e 之后，产生出许多对它们的修正改进算法= 2 ，1 0 ，以及 一些新的流形学习算法，如拉普拉斯特征映射( l a p l a c i a ne i g e n m a p 8 ，9 1 ) 、海 赛局部线性嵌入( h e s s i a nl o c a l l yl i n e a re m b e d d i n g ，简称为h l l e 1 1 ) 、局部 切空间排列( l o c a lt a n g e n ts p a c ea l i g n m e n t ，简称为l t s a 4 和其他各种统计方 法】2 ，】3 ，】4 1 。这里我们仅简要介绍l t s a 。 l t s a 1 1 的基本思想是利用样本点邻域的切空间来表示局部的几何结构， 然后将这些局部切空间排列起来构造流形的全局坐标。首先，【t s a 寻找出样 本点的局部邻域并对每个邻域进行低维逼近以获得样本点的切空间以及邻域在 这个切空间上的投影坐标。其次，i t s a 认为理想的低维嵌入同局部的投影坐 标之间应该只相差一个仿射变换，并由此构造一个最小化重构误差。而求解这 个最小化重构误差问题也可以转化成求解一个稀疏矩阵的特征值问题。 这些流形学习方法的共同的特征是，首先在每个样本点附近寻找一个邻域， 并找出这个局部邻域的几何结构，然后利用这些局部信息将流形非线性的映射 到一个低维空间上。他们的不同之处在于收集的邻域的局部信息不同，以及利 用这些局部信息构造全局嵌入的方式不同。这些算法共同的局限性在于，所有 的学习算法均假定流形非自相交。对于自相交流形，这些算法往往会失效。 1 3 自相交流形及学习算法失败的主要原因 在引出自相交流形之前，有必要给出流形学习中的某些重要的数学定 第一章引言 4 义团，1 7 】。 拓扑空间拓扑空间是一个集对( m ，t ) ，其中集合m 为一非空集合，拓 扑t 是m 的满足以下性质的子集族： ( 1 ) t 关于属于它的任意多元素的并运算是封闭的 一 ( 2 ) t 关于属于它的有限多元素的交运算是封闭的 ( 3 ) t 含有空集0 和m 本身作为其元素。 h a u s d o r f f 空间如果对m 中任意两个不同点茁，y ，都存在z 的邻域u 以 及y 的邻域y 使得ynu = 0 。此时，称( m ，t ) 为h a u s d o r f f 空问。 流形设m 为h a u s d o r 刷石扑空间。若对任意p m ，都有p 的一个邻域u 和研“) 的 一个开集同胚，则称m 为m 维拓扑流形。 坐标卡设妒：u 一妒( u ) 即是同胚，其中l p c v ) 是r ”中的开集，则称 ( 以妒) 为流形m 的一个坐标卡。 伊相容设( ，札) ，( ，咖) 是n 维流形m 的两个坐标卡。若n 0 时，双射 o 1 ：即( n ) 一( n u z ) 和它的逆映射都是r 次可微的，则称( ，妒。) ，( ，即) 是伊相容的。， 微分结构设m 是仡维流形，假定a = ( ，) ) ：o a 是m 上坐标卡 的一个子集合，且满足以下条件： ( 1 ) ：q a ) 构成m 的一个开覆盖； ( 2 ) 属于a 的任意两个坐标卡都是c 相容的 ( 3 ) a 是极大的， 则称a 是m 上的一个微分结构。 微分流形设m 是n 维流形，若在m 上指定了一个微分结构a ，则 称( m ，a ) 为一个r , 维伊微分流形。属于a 的坐标卡( 阢妒) 称为该微分流形的 容许坐标卡。当r = o 。时，称m 为光滑流形。 第一章引言 5 光滑函数设f ：m r 是定义在光滑流形m 上的连续函数。若在点 z m ，存在m 的一个容许坐标卡( u 妒) 使得z u ，f 。妒- 1 ： p ( 矿) 一r 是 在点妒( z ) 处光滑的函数，则称函数，在点x 处是光滑的。 、 光滑映射设m ，分别是m ，7 1 , 维光滑流形，：m 一是连续映射。设 z m ，若存在m 在点z 处的容许坐标卡( 以妒) 及在点，( z ) 处的容许坐标 卡( k 砂) ，使得 砂。，oq o 一1 ：妒( u n f - t ( y ) ) + 妒( v ) 是在点妒( z ) 处光滑的映射，则称映射，在点x 处是光滑的。处处光滑的映射称 为光滑映射。 切向量和切空间光滑流形m 在点z 的切向量就是一个映射v 。：g o 。一r ， 且对v ，g c 0 。，a ，b r 满足： ( 1 ) ( 。，+ b g ) = 口( ，) + 6 扫) ； ( 2 ) v z ( f 9 ) = ( _ 厂) g ) + ，) 0 ) 。 光滑流形的切向量是曲线的切向量的一种推广。z 点的切向量全体记为咒( m ) ， 它是一个实线性空间，称之为m 在点x 的切空间。 黎曼流形如果在光滑流形m 的每个切空间疋( m ) 中定义一个内积，则 称m 为黎曼流形。 弧长设c ( ) ，a 冬t 6 是黎曼流形m 中的一条曲线，在g 上每点的切向量 记为，则e 的弧长定义为c | | v t | | d t 测地距离设p ，q 是黎曼流形m 中任意两点，则这两点的测地距离d m ( p ，q ) 是 m 中连接i ，g 两点的所有分段光滑曲线的弧长的下确界。测地距离又称流形距 离。 下面我们给出本文研究的自相交流形的定义： 定义1 3 1 自相交流形：设q 是剃中的一个开集，d m j ，：q r ”是 q 上的光滑映射。如果存在互异点p q q ，使得，( p ) = f ( q ) = z r ”，则 称，( 蚴为r m 中的d 维自相交流形，同时称x 为d 维流形的自相交点。对于自相交 点。f ( a ) ，如果有且仅有n 个互异点p 1 ，p 。q ，使得f ( p 1 ) 一= ，( m ) = x ，则称为n 一1 重自相交点。 第一章引言6 图1 1 ：左一，二是两维欧氏空间中一维自相交流形；左三是三维欧氏空间中一 维自相交流形；左四是三维欧氏空间中两维自相交流形。 图1 3 是两维( m = 2 ) 和三维( m = 3 ) 欧氏空间中一维( d = 1 ) 和两维( d = 2 ) 自相交 流形( 陆线曲面) 例子。有许多实际例子也可以表述为自相交流形。比如，固定 拍摄物体，沿着平面上一条自相交曲线，改变相机的或光源的位置，拍摄所得到 的图片集，可以看成是一个取在高维空间中的自相交流形。 本文研究自相交流形的学习问题，即对给定的来自于自相交流形的有限个 样本z ：f ( a ) ，i = 1 ，礼，其5 h f 未知，确定p i n ，使得 墨= ，嘛) ，i 1 , - ，n 在本文的讨论中，我们假设高维数据所在的自相交流形的维数d 已经给定，并假 定自相交流形只有1 重自相交点。 自相交流形的学习，是一个非常困难的问题。目前所存在的流形学习算法 都无法得到理想的学习结果。实际上，这些流形学习算法共同的关键步骤是： 根据每个样本点欧氏距离下的邻域f 简称欧氏邻域，包括k 邻域及e 邻域两种取 法) 获得局部几何结构的信息，然后将这些局部信息以某种方式整合到低维空间 中去。 对于非自相交流形，当样本点的局部邻域适当选定，样本点的邻域关系，与 其低维点的邻域一一对应( 同胚) 。因而可以通过样本点的邻点关系，确定其低 维点的邻点关系。然而，在自相交流形中的自相交点附近，由于自相交性，我们 无法通过其邻点的关系，得到低维点的相邻关系。实际上，d 维自相交流形在自 相交点的欧氏邻域，常常呈现出更高维的依赖关系，而非近似的d 维线性关系。 因此现有的降维算法往往会失效。比如在用i s o m a p 时，i s o m a p 认为一个欧氏 邻域内两点间的欧氏距离可以近似作为它们之间的流形距离。事实上，对于自 相交点附近的点而言，这一等同性并不成立。在一个欧氏邻域里的两个点，虽然 鎏 蹙。蝗妊 第一章引言 7 欧氏距离很小，但是流形距离可能远远比这个大。这说明高维空间上的( 欧氏) 邻域，不能反映流形距离意义上的邻近关系。又如在l l e 中，高维空间中的点 与其邻域点的线性组合表示的近似关系，在其相应的低维空间中并不成立。在 1 s a 中，由自相交点附近欧氏邻域点集，无法得到d 维切空间的有效逼近。 简言之，对于自相交流形，高维空间中的欧氏邻域点的近似线性关系，不能 体现它们的低维局部结构。所以有必要对欧氏邻域进行某种修正，找出流形距 离意义上的邻域f 称低维邻域) ，反映出对应的低维结构。 1 4 本文的工作 如上文所说，原有的流形算法在处理自相交流形时存在缺陷。自相交流形 的学习的核心或者说关键问题，是如何确定正确的邻域关系，使之能够正确地 反映出低维点的邻近关系。为了解决这个问题，本文提出一种迭代方法，来判 别或删选正确的邻域关系。我们主要是想建立一个分层邻域图来储存邻域信息， 逐步获取有效的局部线性结构。这一分层进行的邻点鉴别和筛选过程，是一种 迭代过程。它可以不断提高鉴别和筛选过程的准确性，逐步完善之后，最终得 到理想的邻点集。 本文的组织结构现介绍如下： 第二章先定义具有可信切空间的1 一正则点，并通过强正则化1 正则点的邻 域，建立正则点之间正确的邻域关系，然后以此为基础逐步修正非正则点的邻 域。第三章给出自相交流形学习的算法，并对该算法进行数值计算上的分析。第 四章给出一些数值例子，包括两维_ - - 维欧氏空间里的自相交曲线曲面的例子 和一个实际例子。第五章总结本文，并指出算法需要改进的地方。 第二章正则点与邻域修正 自相交流形学习的关键问题在于，自相交点附近的欧氏邻域不能正确反映 出低维点的邻域关系。对于一个d 维的自相交流形，这些欧氏邻域不具备低维邻 域应有的两个特征：1 ) d 维局部线性；2 ) 同一邻域里各点对应的切空间之间的 偏差小。 应注意到，仅仅具有d 维线性性质的邻域还不足以用来降维。假设两个流 形距离很大的点鼢和z f 的各自邻域近似地具有d 维线性关系，但共有一个欧氏 邻点，即。k 同时属于z i 和z j 的各自邻域。由于翰和z f 通过邻域里的x k 而互相 关联，降维结果就会被扭曲，如图2 1 右图所示。而用流形距离意义上的理想 邻域来对左图的数据进行降维，结果为2 1 的中图所示，是一条直线。实际上 点x k 在z ，的低维邻域中，不在轨的低维邻域中，我们现在人为地将x k 也放在毛的 邻域中。注意到，o k 的加入并没有对x i 邻域的线性程度产生大的影响，但降维结 果并未反映真实的低维结构。如右图所示，降维结果中，x i 与x j ，z k 的低维坐标 很接近，这是因为筑和z t 通过邻域中的x k 拉近了距离。如果能够保证每个点的邻 域都是局部线性的，并且邻城里各点对应的切空间偏差很小，这样的邻域就可 以用在l t s a ，l l e 或i s o m a p 里进行降维了。 为解决上述问题，我们需要考虑下面问题： 1 如何区分哪些欧氏邻域具有d 维线性结构，而哪些不具有d 维线性结构； 2 如何将那些不具有d 维线性结构的欧氏邻域修正为d 维线性的邻域，同时 保证每个邻域里点的切空间偏差不大。 这一章里，我们将集中分析和解决这两个问题。 另外，考虑到，研若在如的邻域里，则将如2 n a x j 的邻域并不会对降维有影 响。欧氏邻域f 如k 邻域) 可能不具备这样的性质，为了使得邻域修正更加严密可 信，可能需要首先对欧氏邻域进行对称化修正，即，如果z 。在x 。的欧氏邻域里， 则将x i 加入茁；的欧氏邻域。 2 1邻域的局部线性逼近 给定某欧氏邻域，我们需要从中获得相应的局部d 维线性结构，即最佳映射 第二章正则点与邻域修正 9 ；添 ，| | 魁j jj 余i | | j 图2 1 ：左图：x k ，托，关系示意图；中图：根据理想的低维邻域产生的降维结果 右图：将。k 人为放入翰的邻域里，产生的降维结果。 到d 维线性空间上的坐标及其他相关信息。 假设数据点z 。，。近似地采自d 维仿射空间，即 观= c + u t + e ，i = l ，n 其中c r m ，n r “，c i 表示扰动，u 舻。4 是这个仿射空间的一组正交基组成 的矩阵。记 x = x l ，z 。】，t = h ，】，e = 【e l ， 则数据点可以用如下矩阵形式表示，即 x = c e t + u t + e ， 其中e 表示所有分量为1 的n 维列向量。最佳逼近的目的就是寻找c ，t 以极小化 重建误差 m i n l i e i i = ，m ，i n ，l i x 一( c e 7 + u t ) i i f ， 其中”l i f 表示矩阵的f r o b e n i u s 范数。这个极小化问题通过s v d 很容易的求解： 1 选取c = x e n = 面； 2 选取低秩矩阵矿丁为中心化矩阵贾；x 一孟e 7 = x ( ，一e e f n ) 的最佳 秩d 逼近。这样，最优解可以通过矩阵贾的奇异值分解得到，即 震= p e v r ，p r m “m ，r m “，v f 酽“” l | f i u t = p d e d 呀，其中d = d i a g ( a , ，) 为矩阵贾的d 个最大奇异值所构成 的对角矩阵，p d 和k 分别为对应的左右奇异值向量所组成的矩阵。这样，最 第二章正则点与邻域修正 1 0 优逼近的切空间是最优解u = p d 的列张成的空间，降维后的低维坐标t = u t 僻( 一e e t 竹) = d 圩。 此时，逼近误差矩阵e = p s ；y t b a 曙。设= ( 言舀0 ) ，则 e = p ( ：兰) y t = 扇或吃r ， 其中扇，优是对应a d + 1 ) ，的左右奇异向量构成的矩阵。记线性逼近的相对 误差为 差 局d k l 怯 p d ：d 曙i i f 某个d 维仿射空间时，其d 维线性逼近的相对误 0 。因此，它的数值可以说明样本点和d 维仿射空 间的逼近程度。 从黎曼流形理论可以知道，对于d 维流形m ，其任意一点处的切空间维数也 是d 维 2 1 。因为数据点所在的流形是d 维的，所以包含自相交点在内的任何一个 点的切空间都是d 维的。对戤的邻域墨进行局部d 维逼近得到的切空间如果不是 md 近似d 维的，即盯i 和a ；相差不大，则表明该邻域五不具备d 维线性结构。 ，= d 十1，= 1 因此，邻域五所对应的可以作为度量该邻域是否具有d 维线性结 构的指标，我们将会在下一节里详细说明。 2 2 正则性度量 这一节里，我们将根据邻域的低维线性逼近来定义d 维奇异度，用来度量 其d 维线性程度，即邻域中的样本点逼近于一个d 维仿射空间的程度。 夏静 第二章正则点与邻域修正 假设样本数据集x = 恤1 ，。z ，z 。 取样于未知自相交d 维流形m 4c r “( d m ) ，即， x i = ，( t ) + 矗，i = 1 ，佗 其中6 豫表示扰动。 定义2 2 1d 维奇异度对于取样于d 维流形的数据集x 中的任何一个样本 点翰，记它的邻域为五= k 小z 奶，x i k ，以及中心化矩阵兄；五( ，一e e t ) 该邻域五的d 维奇异度定义为： 其中( 茏) 表示茏的第j 大个奇异值。 当某邻域的d 维奇异度很小( 接近0 ) 时，意味着对该邻域d 维线性逼近的相对 误差很小，该邻域具备d 维线性结构，获得的切空间也相对可靠。如果其d 维奇 异度很大，意味着对该邻域d 维逼近相对误差很大，该邻域不具备d 维线性结构， 逼近所得的切空间不可靠。 注意到， ：幽兰一1 d e 霹( 墨) j = l 因此，计算邻域五的奇异度，只需要计算对应茏的前d 个奇异值及其f 范数即 可。 下面给出几个例子来说明用d 维奇异度来衡量邻域是否具有d 维线性结构的 有效性。我们从下面三个自相交曲线中分别随机地取n = 4 0 0 个样本点，采取k 邻 域选取方法选定邻域，即，对每个点耽，找出在欧氏距离下与其最近的k 个点( 包 括玩本身) ，作为的邻域五，然后计算奇异度。 g ( t ) = i t 3 3 t ，t 2 1 t ，t 一2 ，2 ， = 1 0 9 2 ( t ) = 一1 0 s i n ( 2 t ) ，6s i n ( 3 t ) t ，t 0 ：7 5 7 r ，2 2 7 r ，七= 8 ， 卯( t ) = 陋33 t ，t 2 ，名i i 山。( 札) 1 1 2 孔 t ， - 2 ，2 ， k = 1 0 第二章正则点与邻域修正 1 2 图2 2 ：第一行：颜色表示每个样本点盘邻域的奇异度：第二行：每个样本点对应 的弧长参数r + 与其胁f 域奇异度的关系。 另外，从下面的自相交曲面随机取n = 1 0 0 0 个样本点 乳( u ， ) = ( 一s i n ( 2 u ) ，3 s i n ( u ) ， 7 ；u 0 7 5 n ，2 2 7 r 1 ， = r a n d ( 1 ，几) ，k = 2 0 我们分别对每组数据每个样本点的k 邻域进行d 维线性逼近，计算出各点对 应的d 维奇异度。在图2 2 的第一行，曲线曲面图上的颜色表示每个样本点k 邻 域的d 维奇异度。图2 2 的第二行中各组数据的奇异度分布图，表示每个样本点 对应的弧长参数与其欧氏邻域奇异度的关系。从图中可以看到，在自相交点附 近，奇异度明显较大，即其欧氏邻域d 维线性程度差。可以看出，奇异度能起到 区分自相交点的作用。 对每个点的邻域赋予奇异度之后，我们还需要设定一个合理的阀值1 ，来区 分可信的与不可信的邻域切空间。下面给出午正则点的定义： 定义2 2 2 ，y - 正则点设定阀值7 ，如果托对应的奇异度s 。 7 ，则称x i 为7 一正 则点。 1 一般根据奇异度分布合理选取，我们将会在第三章中做详细的分析。d 维 奇异度是衡量样本点的欧氏邻域是否具备d 维线性结构的一个指标。d 维奇异度 越接近0 ，该邻域具备d 维线性结构的可能性就越大。对于于正则点，我们认为它 们的欧氏邻域已经具备或者近似具备d 维线性结构，获得的切空间可信。当蹰不 。i专摹。争黪、 一 。 j 吣一 。 一一一 一一一。：!j鬻一 0_p一 懑簿一_ 。撵 第二章正则点与邻域修正1 3 是千正则时，其欧氏邻域不能近似具备d 维线性结构，d 维逼近得到的切空间也 不可信。7 - 正则点的切空间是所能获得的可信的信息，我们将由此逐步鉴别和 筛选邻域点，获得正确的邻域信息。 2 3 切空间分类 邻域的d 维奇异度是衡量邻域d 维线性程度强弱的指标。千正则点具备可信 的切空间，但其邻域里可能出现流形距离很远的点。因此，我们需要另外一个 指标来衡量流形距离的大小。 切空间n ，r ，作为r m 的两个d 维子空间，它们之间的距离由下式定义f 2 2 ， 圳： d i s t ( f i ，f j ) = ( 1 一吒2 i 。( w 。) ) ， 其中矾，是分别张成两个切空间的标准正交基，盯。t 。( 呼屿) 表示矩阵呼屿的 最小奇异值。切空间距离的几何意义即为两空间夹角的正弦。两个空间n ，n 的 距离也可以通过m a t l a b 里的函数s u b s p a c e ( u t ，) 来计算。 对于一个光滑流形，如果各点的曲率都不大，则在任何一个低维小邻域里， 各点对应的切空间的变化都是微小的。在1 重自相交点附近的样本点的邻点，可 能可以按照它们之间的切空间距离分为两类。对于这些样本点，在寻找低维邻 域时，必须筛除其中的一类点，使得剩余一类点的切空间彼此距离很小，如图 2 3 所示。 假定z 1 1 ，巩对应的切空间r ，n 可以分为两类，它们的标准正交基矩 阵“，仉豫m d 均已知，目标是将这些切空间分成两类。 定义了两个切空间之间的距离之后，就可以用聚类分析方法，如k 平均聚类 法对切空间进行分类2 剖。我们也可以对这些切空间进行降维分类，比如借助于 切空间的距离建立距离矩阵，用m d s 6 ，7 1 将它们降维，然后再进行分类。本文 中需要分类的切空间个数比较小，所以计算量并不大。 2 4 正则点的邻域修正 我们将吖一正则点全体记为y 。考虑正则点观v 的邻域m 。如果孔的任何邻 点都是千正则的，我们称m 是一个t 正则邻域，简称正则邻域。 第二章正则点与邻域修正 1 l i 图2 3 ：切空间分类：红色点可以根据切空间分为两类 正则点可以得到其可以信赖的近似切空间，因此，正则邻域意味着其每个 邻点都有可以信赖的近似切空间。一般而言，一个正则邻域内不同点的切空间 应该是比较接近的，这时，其所有的邻点都是可靠的，即相互间都有相近的流形 距离。然而，例外的情形可能存在：同一正则邻域内的两个正则点具有差异较 大的近似切空间。对于这样的正则邻域，其邻点并非都是可靠的。因此，有必要 对同一正则邻域内的所有正则邻点进行筛选，筛除某些不可靠的正则邻点。在 正则点的当前邻域中筛除不可靠正则邻点的过程，我们称为对该正则点的强正 则化。 正则邻域的强正则化可以通过对切空间的分类来实现。假设戤的现有邻 域m 是正则的。采用上节提到的方法，对抚的所有邻点。i m ( 包括观本身) 的 近似切空间 r fj m 作分类，如果然巧的切空间1 1 f 与现的切空间r 。属于同 类，则在m 中筛除z ，。我们将强正则化后的邻域称为强正则领域，仍记为，同 时称孔为强正则点。如果有必要，我们将对强正则邻域重新进行d 维逼近，得到 强正则点更为准确的切空间。 当所有的正则邻域都已经强正则化后，我们将这样的正则点的全体记为m ： k = 故v - lm 是强正则的) 我们建立一个无向邻域图毋= ( ke ) 来储存所有7 一正则点的邻域关系。将 成为9 的第一层( 核心层) 。并在此基础上，逐步建立其他层级。分层建立邻域 图9 的过程如下： 第二章正则点与邻域修正 首先，定义由强正则邻域中非强正则点构成的第二层k k = x j v i 存在，使得m ) 显然，如果z ，则z ，是正则的。现在考虑每个z ，及其邻域m 。m 中除 了强正则的邻点外，还有属于k 的邻点和其他正则或非正则邻点。由于的邻 点与强正则点的相邻关系确定且不会改变，我们有可能需要改变z ；与其某邻 点x b k 的相邻关系。为此，我们根据m 中属于muk 的邻点( 包括巧本身) 的 切空间的分类，在m 中筛除不可靠的k 类邻点。仍将修正后的邻域( 包括其他 未考虑的邻点) 记为人。此时，m 里还可能存在不可靠的其他正则点，我们将 继续对o i 进行强正则化。 现在考虑三层 k = z 女v ( uuk ) 1 存在，使得z 女m ) 同样，对每个。，根据人丘中属于kuk 的邻点( 包括x k 本身) 的切空间的分 类，在 丘中筛除不可靠的类和类邻点，同时在这些不可靠k 类邻点的邻域 里筛除。将。女修正后的邻域( 包括其他未考虑的邻点) 仍记为m 。修正完中 每一个点的邻域之后，在层点的邻域里也同时筛除了不可靠的k 层正则点。 至此，k 层正则点的强正则化完成，层正则点的强正则化将继续进行。 上述扩展过程可以继续进行。一般的，第i 1 层为 k = z v ( u 垤u uk 一1 ) i 存在k 乩使得。k m ) 容易根据定义证明，各层之间互不相交，并且任意层k 中的点只可能与 层k 一1 ，k ，k + l 的点有邻域关系。扩展过程直到+ - = o 终止，此时迭代 进行了m 步。一般情况下，此时所有的正则点之间的邻域关系已经被考虑，即 v = u k u u 在自相交点个数有多个时( 如图13 左二图所示) ，可能会遇到下列情况 k 三v ( k uk u - - - u ) 口 因为k 层中的点都不在的邻域里，因此，也不可能在m ，k ，一1 层点的 邻域里。这表明k 层中的正则点与muk u uv 中的正则点不存在邻域关 第二章正则点与邻域修正1 6 图2 4 ：邻域图9 中的分层示意图：h ，k ，k 系，即不能根据核心层的强正则点来加强其邻域的可靠性。虽然如此，因为k 类 点本身已经具有可信的切空间，所以可以将其单独作为一类，然后讨论该类点 之间的邻域关系。对于样本点x k k ，根据人丘中属于k 的邻点( 包括x k 本身) 的 切空间分类，在人丘中筛除不可靠的k 类邻点。修正后的邻域( 包括其他未考虑 点) 记为m 。 显然，邻域的修正，将改变各正则点奇异度的数值。若有必要，我们将对正 则点的邻域重新进行d 维逼近，计算奇异度的数值，并得到正则点更为准确的切 空间。对每一个正则点强正则化后，其邻域中的正则点都是可靠的，这些邻域 信息储存在邻域图9 中。我们将由此逐步考虑非正则点的邻域。毋的分层示意 图如图2 4 所示。在实际计算中，如果扰动不太大，9 的层数往往在2 5 层之间。 2 5 非正则点的邻域修正 邻域图9 中储存了所有1 一, w n 点之间正确的邻域关系。我们将以此为依据， 逐步考查非正则点的邻域，建立无向邻域图5 - = ( l ，e 7 ) 来储存所有数据点之间 的邻域关系。 将邻域图9 中的所有点即正则点全体作为邻域图，的第一层( 核心层) ，即 l 1 = 矿 并在此基础上，逐步建立厂的其他层级。注意到，的建立与9 的建立将会有所 第二章正则点与邻域修正 1 7 图2 5 ：邻域图f 中的分层示意图? l 1 ，l 2 ，工3 不同，这是因为中所有的点都是1 一正则点，具有可以信赖的切空间，而，中除 了核心层之外，其他的节点都是非正则点，这意味着这些点的切空间都不可靠。 分层建立邻域图，的过程如下： 首先考虑位于正则点邻域中的非正则点，将其作为，的第二层，即 l 2 = 。j l l 1i 存在茁。l t ，使得z j 人) 现在确立邻域图，中l ，层与l 。层点之间的邻域关系。考虑每个x j l z ，其当前 邻域为m 。根据l 2 的定义，茁f 至少在l 1 层中一个点的邻域里。设q 在x l ，z “ l ，的邻域m ，m 里。注意到，这些点都具有可信的切空间。如果这些点的 切空间相差不大，则确立这些点与z f 的邻域关系。否则，将x i ，x i 。根据 切空间分为两类。对两类点分别进行d 维线性逼近，得到两个超平面，分别 为只：龟+ 阢7 - ，r 删，t = 1 ，2 。z f 到超平面r 的距离为， ( 一巩u 丁) ( 一如) i i 。 其中i 是单位矩阵。如果z ，与超平面b 距离近，我们认为z ，与超平面只对应的 那类点构成同类点，并将这类点的切空间作为z j 的( 近似) 切空间r ，即将阢作 为z i 的切空间n 的标准正交基。然后从异类点的邻域里筛除。，同时从m 中筛 除这些异类点。o 。，耽。修正后的邻域仍记为m ，m 。，z i 修正后的邻域 仍记为 ( 包括其他l 。层点和其他未考虑邻点) 。这样，就确立了l 。层点与所 有厶层点之间的邻域关系，并且此时l 2 层中所有点已经具备可信的切空间。 第二章正则点与邻域修正 1 8 接下来，我们考虑l 2 层点之间的邻域关系。x j l 2 的当前邻域为m 。对 于m 中所有的l 2 层点，为了避免这些邻点中某个与其他邻点有较大的流形距 离，需要筛除某些邻点，使得余下的邻点均具有相近的切空间。注意到，这时 所有的三2 层点都具有可信的切空间。我们将m 中所有l 2 层点( 包括z f ) 进行分类， 从m 中筛除那些与z j 不属于同类的邻点。剩下的邻点( 包括其他未考虑的非正 则点) 一起构成新的邻域集，仍记为m 。这样，就确立了邻域图，中l z 层点之 间的邻域关系。必要时我们重新计算x j 的( 近似) 切空间1 1 ，。 考虑第三层 l 3 亍 吼l ( l 1u 上2 ) i 存在l 2 ，使得x k m ) 按照建立l 。层与l 。层点的邻域关系的方法，确立l 2 层与l 3 层点之间的邻域关 系；按照建立l 2 层点之间邻域关系的方法，确立l 3 层点之间的邻域关系。 上述扩展的方法可以继续进行。一般地，第n 层为 l 。= z l ( l 1ul 2u ul 。一1 ) i 存在l