拉普拉斯特征映射.pdf

发布时间：2022-05-31 发布人：admin 分类：说明书资料大小：1.13M 资料格式：pdf 举报版权申诉

qq_23856699-10827428-4744300845378091261.pdf-第1页.png

第1页 / 共18页

qq_23856699-10827428-4744300845378091261.pdf-第2页.png

第2页 / 共18页

qq_23856699-10827428-4744300845378091261.pdf-第3页.png

第3页 / 共18页

qq_23856699-10827428-4744300845378091261.pdf-第4页.png

第4页 / 共18页

qq_23856699-10827428-4744300845378091261.pdf-第5页.png

第5页 / 共18页

qq_23856699-10827428-4744300845378091261.pdf-第6页.png

第6页 / 共18页

qq_23856699-10827428-4744300845378091261.pdf-第7页.png

第7页 / 共18页

qq_23856699-10827428-4744300845378091261.pdf-第8页.png

第8页 / 共18页

文本预览

拉普拉斯特征映射 Laplacian Eigenmaps 2018 年 12 月 4 日一、引言信息化时代的到来，伴随着大量高维数据的产生。现实生活中许多数据，比如文本数据、图形数据、视频数据、语言数据，在计算机当中都是以高维向量的形式进行存储的。面对如此众多高维的数据，如何对其进行维数约简，挖掘出其本质信息，寻找出其内在规律，是当前数据挖掘和机器学习的研究重点。目前的数据降维方法，主要分为两类：一类是线性降维方法，代表方法有：主成分分析法（PCA），多维尺度变换（MDS），局部嵌入分析 (LEA)，局部保持嵌入（LPP）等，这些方法能够发现数据中的线性结构，找出数据间的线性关系，具有简单性、易解释性和可延展性等优点，但是对于非线性数据，这些方法则无法挖掘出其内在的非线性关系；另一类就是非线性降维方法，主要方法有：等距嵌入（Isomap）、局部线性嵌入（LLE）、局部切空间排列（LTSA）、拉普拉斯特征映射（LE）等，这些流形学习的方法通过构造出高维数据点的局部邻域结构，再利用这些局部邻域结构将其全局映射到低维空间，挖掘出数据间的非线性关系。与传统的线性降维方法相比较，流形学习的方法具有参数少、计算快、易求全局最优解等优点。因此，近年来，这些流形学习方法在数据挖掘、机器学习、计算机视觉等方面都引起了广泛的关注。传统的流形学习方法，都属于无监督的机器学习方法。但在实际生活中，有些高维数据的低维信息是可以提前获得的，这些低维信息可以是高维数据的本征低维坐标，也可以是高维数据的类别号等等。如何有效地利用这些已知低维信息的数据，去学习出其它数据的低维信息，即把传统的流形学习方法与半监督的机器学习方法结合起来，进一步优化流形学习算法的性能，是流形学习研究领域的一个热点。 2006 年，Yang 等提出了半监督非线性降维方法（semi-supervised nonlinear dimensionality reduction），通过把等距嵌入（Isomap）、局部线性嵌入（LLE）、局部切空间排列（LTSA）3 种经典的流形学习算法与半监督的机器学习相结合，提出了半监督等距嵌入（SSIsomap）、半监督局部线性嵌入（SSLLE）、半监督局部切空间排列（SSLLE）等方法，为这一领域的研究开辟了一个方向。这些半监督的流形学习算法在分类识别等问题上，比起传统的流形学习方法，具有更好的效果。其中，作为流形学习经典算法之一的拉普拉斯特征映射算法（LE），在这里利用这个交流机会与大家一起学习。二、预备知识流形学习 (Manifold Learning) 这一术语的首次提出是在《Science》上连续发表的 3 篇关于流形的文章里首次引用了“流形学习”这个概念，它的出现为解决维数约简提供了一个研究方向，开创了流形学习的里程碑。在这几篇论文中 Seung 等人认为人们认知事物是通过他们的低维流形而不是高维流形， Tenenbaum 和 Saul 等人提出了流形的几种算法。 1

拉普拉斯特征映射 1. 流形与流形学习当人们在高维研究中面临着” 维数灾害” 问题，就需要对高维数据进行降维，即维数约简。线性主成分分析法（PCA）是 Spearman 于 1904 年提出的，它是多元数据分析的重要工具之一，适用于数据结构呈现全局线性结构的情况下，如果数据呈现非线性结构，则不能有效地呈现其内部结构。若要在欧氏空间的非线性数据集中获得有用的信息，最有效的方法就是将这些线性数据集看作是存在于欧氏空间中具有低维结构的流形中，这就是一个流形学习问题。流形是拓扑学的一个概念，首先了解一下拓扑学的基础知识。拓扑空间是拓扑学最基本的研究对象，拓扑空间就是上面被赋予了拓扑结构的一个集合，多个拓扑空间之间是可以定义连续映射。假设 x,y 是两个拓扑空间,f : x ! y 是一个连续映射，而且它的逆映射也是连续的，那么就是说 f 是一个同胚映射，并且 x,y 是同胚的。拓扑学是研究几何体在同胚映射下的数学分支。拓扑空间与流形的关系：如果拓扑空间 M 满足以下条件就称 M 为 m 维流形。条件如下： M 是豪斯多夫空间，它是拓扑学中的一个分支空间，并且满足以下分离定理：在 M 中的任意两个点 x 和 y，存在 x 的领域 U 和 y 的领域 V，U 与 V 之间没有交集。对于 M 中的任意一点 p，存在一个包含它的一个 M 维坐标领域 (U; ϕ), 其中坐标领域是拓扑空间中的开集与开集在欧几里德空间里的映射的有序对。在拓扑学中流形表示一个局部处处为欧几里德的拓扑空间。由上可知，流形是微分几何的一个基本概念，它是一种特殊的连通仿射拓扑空间，也就是说它的本质是局部可坐标化的拓扑空间，可以把它看作是欧氏空间的非线性推广。由此可以得出流形的定义。其定义为：首先假设存在于 Rd 欧氏空间中 d 维域 Y ，令 f : Y ! RN 为该空间中的光滑嵌入，令 N > d. 数据点 yi Y 在随机过程中生成，然后再经 f 映射形成空间数据 xi = f (yi) RN 。称 Y 为隐空间，yi 为隐数据，从观测数据 xi 中重构 f 和 yi 就是流形的目标。流形学习的本质就是当某一空间为一低维光滑流形时，要从该空间中的采样数据中找出低维的内在规律。根据以上对流形的定义，下面对流形学习的简约过程进行形式化概括。假设所有的数据都是来源于一个高维欧氏空间中的低维流形，那么流形学习就是根据这些数据把高维恢复到低维空间，也就是说在高维空间中找到低维空间，并在此过程中得出相关的映射，从而实现数据简约以及数据的可视化。可以把这个过程看作是从现象中寻找本质的过程，进而找出全部数据的内在规律。三、算法的说明利用图的拉普拉斯算子、流形上的拉普拉斯-贝尔特拉米算子与热方程之间的对应关系，提出了一种几何激励算法，用于构造高维空间中低维流形采样数据的表示形式。该算法提供了一种计算效率高的非线性降维方法，具有保局部性和与聚类的自然联系。核心算法非常简单，有几个局部计算和一个稀疏特征值问题。这个问题的解反映了流形的固有几何结构。这种合理性来自于拉普拉斯算子在提供最优嵌入中的作用。从数据点得到的图的拉普拉斯算子可以看作是流形上定义的拉普拉斯-贝尔特拉米算子的近似。数据的嵌入映射来自于对整个流形上定义的自然映射的近似。拉普拉斯特征映射算法的局部性保持特性使其对离群值和噪声不敏感。这样做的一个副产品是，该算法隐式地强调了数据中的自然集群。与学习和计算机视觉中开发的谱聚类算法的联系变得非常清楚。在 Roweis and Saul(2000) 和 Tenenbaum et al(2000) 的讨论之后，我们注意到生物感知器官是面对高维刺激的，它必须从高维刺激中恢复低维结构。有人可能会说，如果恢复这种低维度结构的方法本身是局部的，那么自然的聚类就会出现，从而可能成为生物感知范畴发展的基础。 2

拉普拉斯特征映射 1. 算法给定 k 个点 x1; x2; : : : ; xk 在 Rl 中，我们构造了一个有 k 个节点的加权图，每个节点对应一个点，以及相邻点之间的边集. 1. Step 1.[构造图] 如果 xi; xj 是接近的，我们在节点 i; j 之间添加一条边，有两种变化： (a) ϵ 邻点.[参数 ϵ 2 R] 如果 ∥ xi xj ∥2< ϵ 那么节点 i; j 是连接的。优点：几何驱动，关系自然对称. 缺点：往往会导致图形具有多个连接的组成部分，很难选择 ϵ. (b) n 个最近邻.[参数 n 2 N] 如果 i 是 j 的 n 个最近的邻点或者 j 是 i 的 n 个最近的邻点，那么 i 与 j 是连通的. 优点: 选择简单，容易产生连通图。缺点: 几何上不太直观。 2. Step 2.[选择权重] 这里也有两种选择权重的方法： (a) 热核.[参数 t 2 R] 如果节点 i; j 是连接的，使 ∥xi xj ∥2 t Wij = e (1) 对于权重选择的选择的原因将会在后面解释。 (b) 最简单思维.[没有参数] 如果 i; j 之间是有边连接的，那么 Wij = 1. 这种简化避免了选择参数 t. 3. Step 3.[特征映射] 假设上面构造的图 G 是连通的，否则对每个连通的分量进行步骤 3。计算广义特征向量问题的特征值和特征向量: (2) 其中 D 为对角权矩阵，其元素为该列元素 W 的和 (或行，因为 W 是对称的),Dii = j Wji. L = D W 是拉普拉斯矩阵。拉普拉斯算子是一个对称的正半定矩阵，它可以看作是 G 顶点上函数的算子。让 y0; : : : ; yk1 为方程 2 的解，根据特征值排序，y0 为最小特征值 (实际上是 O). 图像 xi 在低维空间 Rm 的嵌入由 (y1(i); : : : ; ym(i)) 给出. Ly = Dy ∑ 2. 解释回想一下，给定一个数据集，我们构造了一个加权图 G = (V; E)，它的边连接着相邻的点。考虑将加权连通图 G 映射到一条直线的问题，以便连通点尽可能地保持在一起。我们希望在适当的约束下选择 yi 2 R 来最小化让 y = (y1; y2; : : : ; yn)T 成为从图到实线的映射. 首先，注意对于任何一个 y 我们都有 (yi yj)2Wij ∑ ∑ i;j i;j 3 (yi yj)2Wij = yT Ly 1 2 (3) (4)

拉普拉斯特征映射 ∑ 与之前一样，L = D W. 看到这个，注意 Wij 是对称的并且 Dii = ∑ 也可以写成如下：∑ ∑ ∑ 2yiyj)Wij = y2 i Dii + j Djj 2 y2 (y2 i + y2 j i;j i j i;j ∑ ij(yi yj)2Wij j Wji。因此 yiyjWij = 2yT Ly (5) 因此，最小化问题减小到寻找 argmin2yT Dy=12yT Ly. 约束 yT Dy = 1 移除嵌入中的任意缩放因子。矩阵 D 提供了对图形顶点的自然度量。由式 4 可知，L 是一个半正定矩阵，使目标函数最小的向量 y 由广义特征值问题 Ly = Dy 的最小特征值解给出. 设 1 是在每个顶点取 1 的常数函数。很容易看出 1 是特征向量的特征值为 0。如果图是连通的，1 是当 = 0 时唯一的特征向量。为了消去这个不重要的点将会引起 G 上的顶点为 1 时的坍塌，我们增加了正交性的约束条件得到： (6) 因此，解 yopt 由所给出的最小非零特征值所对应的特征向量，更一般地，图嵌入 Rm(m > 1) 由 i 表示，提供了第 i 个顶点的嵌入坐标。因此 n m 矩阵 Y = [y1; y2; : : : ; ym] 给出。其中第 i 行，由 Y T yopt = argminyT Dy=1;yT D1=0yT Ly ∥ Yi Yj ∥2 Wij = tr(yT Ly) (7) ∑ i;j 我们需要最小化简化为 (8) 对于一维的嵌入问题，约束条件避免了倒塌到一个点上。对于 m 维的嵌入问题，约束避免了子空间的维数坍塌少于 m。 Yopt = argminY T DY =1tr(yT Ly) (1) 拉普拉斯贝尔特拉米算子拉普拉斯图与流形上的帕普拉斯贝尔特拉米算子是类似的。考虑到嵌入到 Rk 上的 m 维流形 M。流形上的黎曼结构 (度量张量) 是由 Rk 上的标准黎曼结构 @xi）导出的。假设我们有一个映射 f : M ! R。梯度 ∇f (x)(在局部坐标下可以写成 ∇f (x) = 是流形上的向量场，类似于 x(在局部坐标图中). n i=1 @f @xi ∑ jf (x + x) f (x)j j⟨∇f (x); x⟩j ⩽∥ ∇f (x) ∥∥ x ∥ (9) 因此我们知道如果 ∥ ∇f (x) ∥ 很小的时候，x 点附近的邻点将会映射到 f(x) 附近。因此，我们通过寻找一种平均上最能保持局部性的映射 ∫ argmin∥f∥ ∥ ∇f (x) ∥2 与最小化在图上 Lf = 1 ∑ (10) ij(fi fj)2Wij 是一致的。最小化梯度的平方变为找最小化拉布拉斯贝尔特拉米算子的特征方程 L . L = div∇f (x),div 是散度。根据 Stokes 定理，-div 和 ∇ 是 ∫ 形式上的伴随算子，即如果 f 是一个函数，X 是一个向量场，那么 M div(X)f. 因此 ⟨X;∇f⟩ = ∥ ∇f (x) ∥2 L2(M )=1 ∫ ∫ ∫ M M M 2 我们知道，L 是一个正半定的并且最小化了 ∥ ∇f ∥2 的 f 必须是 L 的特征函数. L(f )f M M ∫ ∥ ∇f ∥2= M (11) ∫ 4

拉普拉斯特征映射 (2) 热核和权重矩阵的选择 ∫ 流形 M 上可微函数上的拉普拉斯-贝尔特拉米算子 m 与热场的时间相关。设 f : M ! R 为初 @t = Lu。解由 u(x; t) = 始热分布，u(x,t) 为 t (u(x,0) =f(x)) 时刻的热分布。热方程为偏微分方程 @u M Ht(x; y)f (y) 给出, 其中 Ht 是热核，即这个偏微分方程的格林函数。因此。 @[ Lf (x) = Lu(x; 0) = ( (12) @t 4t ，其中 ∥ x y ∥ 和 t 都足够的小并且在局部，热核近似等于高斯函数 Ht(x; y) (4t) ∥xy∥2 n = dimM,x,y 为局部坐标。注意，当 t 趋于 0 时，热核 Ht(x; y) 趋于局域化，趋于狄拉克函数，即 ∫ limt!0 M Ht(x; y)f (y) = f (x) 因此，对于小 t 从导数的定义我们有 M Ht(x; y)f (y)] )t=0 ∫ n 2 e ∫ (13) (14) Lf (xi) 1 [f (x) (4t) n 2 t ∥xy∥2 4t ] e M ∑ 如果 x1; : : : ; xk 是 M 上的数据点，最后一个表达式可以近似为 Lf (xi) 1 t [f (xi) (4t) n 2 ∥xy∥2 4t e f (xi)] xj ;0<∥xixj∥<ϵ 是全局的，不会影响离散拉普拉斯算子的特征向量。由于 M 的固有维度可能是未知的，所以 2 。注意到常数函数的拉普拉斯变换是零，我们不需要注意，因此拉普拉斯 L 将该系数 1 t 我们将 = 1 为我们选择正确的乘数。最后了解了如何选择邻接矩阵 W 的边权值 k (4pit) n { ∥xy∥2 4t e if 0 <∥ xi xj ∥< ϵ 0 otherwise (15) Wij = 四、实验上面介绍了算法的具体过程，也解释了算法更细节方面的事情，我们在这里利用从网上找到的程序对拉普拉斯特征嵌入算法在图像上的表现进行更深层次的理解。 1. 实验一在参数为总数据点 10000，欧氏距离，邻点数量为 5，随机采样。对分布可近似看做在三维坐标中的直线、一个平面、Swiss roll、S-curve、Severd sphere 型的数据进行拉普拉斯特征嵌入，并观察效果。 5

拉普拉斯特征映射 6

拉普拉斯特征映射 2. 实验二这里我们产生在 Swiss roll 形上具有些许噪声的数据 10000 个分布在三维坐标系中，我们分别使用邻点 N 为 5、10、15、20、25、50、100、200 的参数进行拉普拉斯特征映射，将其映射到二维坐标系中，生成如下为实验图像： N=5 N=10 N=15 N=20 N=25 N=50 7

拉普拉斯特征映射 N=100 N=200 同样的，这里产生随机数据在 Severed sphere 形上，10000 个数据点，三维坐标系，我们分别使用邻点 N 为 5、10、15、20、25、50、100、200 的数据进行拉普拉斯特征映射，将其映射到二维坐标系中，生成如下为实验图像： N=5 N=10 N=15 8

分享到：

赞收藏

资料库

拉普拉斯特征映射.pdf

相关推荐

人工智能

热门标签

最新资料