英语原文共 25 页，剩余内容已隐藏，支付完成后下载完整资料
用于降维和数据表示的拉普拉斯特征映射
Mikhail Belkin
芝加哥大学数学系，芝加哥，IL 60637，美国
Partha Niyogi
芝加哥大学计算机科学与统计系，芝加哥，IL 60637 USA
机器学习和模式识别的核心问题之一是为复杂数据开发适当的表示。我们考虑构建位于嵌入在高维空间的低维流形上的数据的表示问题。利用图拉普拉斯算子，流形上的Laplace Beltrami算子与热方程的连接之间的对应关系，我们提出了一种基于几何驱动的高维数据的表示算法。该算法提供了一种计算高效的非线性降维方法，该方法具有局部保持特性和与集群的自然连接。讨论了一些潜在的应用和说明性示例。
1 介绍
在人工智能，信息检索和数据挖掘的许多领域中，人们经常面对位于超高维空间上的数据本质上是低维的。例如，考虑使用移动相机在固定照明条件下拍摄的物体的灰度图像。每个这样的图像通常由每个像素处的亮度值表示。如果总共存在n2个像素（对应于ntimes;n图像），则在R n2中每个图像产生一个数据点。然而，同一物体的所有图像的空间的固有维度等于相机的自由度数。在这种情况下，Rn2中所考虑的空间具有低维流形的自然结构。
最近，随着来自于流形的概率分布采样的数据增多，对于开发低维表示的问题，已经有了一些新的兴趣（Tenenbaum，de Silva，＆Langford，2000; Roweis＆Saul，2000）。本文中，我们提出了几何驱动算法和一个伴随问题的分析框架。
降维的一般问题有很长的历史。经典方法包括主成分分析（PCA）和多维尺度。还考虑了生成非线性映射的各种方法。其中大多数，例如自组织映射和其他基于神经网络的方法（如Haykin，1999），建立了非线性优化问题，其解决方案通常通过梯度下降获得，该梯度下降仅保证产生局部最优;通过有效手段难以实现全局最优。但是请注意，最近的基于核技术的PCA的推广方法（Schokkf，Smola，＆ Muller，1998）并没有这个缺点。这些方法中的大多数没有明确地考虑数据可能存在的流形的结构。
在这封信中，我们探索了一种方法，该方法构建了一个包含数据集邻域信息的图表。使用图的拉普拉斯算子的概念，然后我们计算数据集的低维表示，其在某种意义上最优地保留局部邻域信息。由算法生成的表示映射可以看作是对从流形的几何结构自然产生的连续映射的离散逼近。
值得强调的是算法的这几个方面以及此处提供的分析框架：
核心算法非常简单。它有一些局部计算和一个稀疏特征值问题。该解决方案反映了流形的内在几何结构。但是，它确实需要搜索高维空间中的相邻点。我们注意到有几种高效的近似技术可用于寻找最近邻居（如Indyk，2000）。
该算法来自于Laplace-Beltrami算子在为流形提供最佳嵌入方面的作用。通过从数据点计算的邻接图来近似流形。Laplace-Beltrami算子通过邻接图的加权拉普拉斯算子来近似，其中权重被适当地选择。 Laplace Beltrami算子在热方程中的关键作用使我们能够使用热核以原则性方式选择重量衰减函数。因此，数据的嵌入映射近似于拉普拉斯Beltrami算子的本征图，这是本质上在整个流形上定义的映射。
这里给出的分析框架明确地使用这些连接来以几何方式解释维数减少算法。在此框架内除了本书中提出的算法之外，我们还能够重新解释最近Roweis和Saul（2000）提出的局部线性嵌入算法。
拉普拉斯图已被广泛用于不同的聚类和分区问题（Shi＆Malik，1997; Simon ， 1991; Ng ， Jordan ， ＆ Weiss ， 2002 ） 。 虽 然 LaplaceBeltrami算子和图拉普拉斯算子之间的联系是光谱图理论中的几何学家和专家所熟知的（ Chung ， 1997; Chung ， Grigor#39;yan ，＆ Yau ，2000），但到目前为止我们还没有意识到其在降维或数据表示中的应用。然而，我们注意到最近在图形和其他离散结构上使用扩散核的工作（Kondor＆Lafferty，2002）。
拉普拉斯特征映射算法的局部保持特性使其对异常值和噪声相对不敏感。它也不容易短路，因为只使用局部距离。我们通过尝试在嵌入中保留本地信息来证明，该算法隐含地强调了数据中的自然聚类。与学习和计算机视觉中开发的谱聚类算法的密切联系（特别是Shi＆Malik，1997的方法）然后变得非常清楚。从这个意义上说，降维和聚类是同一枚硬币的两面，我们会详细探讨这种联系。相比之下，像Tenenbaum等人那样的全局方法。（2000），不显示任何聚类倾向，因为试图保持点之间的所有成对测地距离。
但是，并非所有数据集都必须具有有意义的集群。在这种情况下，其他方法（如PCA或Isomap）可能更合适。然而，我们将证明，至少在这种数据集的一个例子中（“瑞士卷”），我们的方法产生了合理的结果。
由于Seung和Lee（2000），Roweis和Saul（2000）以及Tenenbaum等人的大部分讨论源于非线性维数减少在人类感知和学习中可能发挥的作用，值得考虑前一章在这种背景下的含义。生物感知装置面临高维刺激，必须从中恢复低维度结构。如果恢复这种低维结构的方法本质上是局部的（如本文提出的算法），那么将出现自然聚类并且可以作为生物感知中类别出现的基础。
由于我们的方法基于流形的固有几何结构，因此它在嵌入方面表现出稳定性。只要嵌入是等距的，表示就不会改变。在使用移动摄像机的示例中，摄像机的不同分辨率（即nn图像网格中n的不同选择）应该导致将相同的底层歧管嵌入到非常不同维度的空间中。我们的算法将产生与分辨率无关的类似表示。
降维的一般问题如下。给定Rl中k个点的x1，...，xk ，在Rm中找到一组y1，...，yk （mlaquo;l）这样yi “代表”xi。本文之中，我们考虑特殊情况，其中x1，...，xk isin;M并且是嵌入在Rl中的流形。
我们现在考虑为这种特殊情况构造代表性yi的算法。在这封信的后面，这种表示的优越性将变得清晰。
2 算法
给定Rl中的k个点x1，...，xk ，我们构造具有k个节点的加权图，包括每个节点，以及一组连接近邻点的边。现在通过计算图拉普拉斯算子的特征向量来提供嵌入映射。算法程序在下面正式陈述。
步骤1（构建邻接图）。如果xi 和xj “接近”，我们则在节点i和j之间放置一条边。有两种变化：
ԑ邻域（参数ԑisin;R）。如果lxi - xjl2lt;ԑ，则节点i和j通过边连接，其中标准是通常的Rl中的欧几里德范数。优点：几何驱动，这种关系自然是对称的。缺点：经常导致带有多个连接组件的图形，很难选择ԑ
n个最近邻居（参数nisin;N）。如果i在j的n个最近邻居中，则节点i和j通过边连接，或者j是i的n个最近邻居。请注意，这种关系是对称的。优点：更易于选择;不会导致图表断开连接。缺点：几何直观性较差。
步骤2（选择权重）。在这里，我们有两种权重来加权边缘：
加热内核（参数t R）。如isin;果节点i和j连接，则令
否则，取Wij，这种权重选择的理由将在稍后说明。
简单方法（没有参数t）。如果顶点i=和j通过边连接则取Wij =1。如果顶点i和j没有通过边连接则取Wij=0。这种简化避免了选择t的过程。
第3步（特征映射）。假设连接了上面构造的图G.否则，对每个连接的组件继续执行步骤3。计算广义特征向量问题的特征值和特征向量，
其中D是对角线权重矩阵，并且其条目是列（或行，因为W是对称的）W的和，即。L = D - W是拉普拉斯矩阵。拉普拉斯算子是一个对称的正半定矩阵，可以被认为是G顶点上定义的函数的算子。
设f0，...，fkminus;1 为方程2.1的解，按其特征值排序：
我们省略了与特征值0对应的特征向量f0 ，并使用下一个m个特征向量嵌入到m维欧几里德空间中：
xi → (f1(i), ..., fm(i)).
3理由
3.1最佳嵌入。
让我们首先说明拉普拉斯特征映射算法提供的嵌入在某种意义上最佳地保留了局部信息。
以下部分基于标准的谱图理论。（参见Chung，1997，作为综合参考。）
回想一下，给定一个数据集，我们构造一个加权图G=（V，E），边缘将相邻点相互连接起来。出于本讨论的目的，假设图形已连接。考虑将加权图G映射到线的问题，以使连接点尽可能保持紧密。令是这样的映射。合理
选择“好”地图的标准是最小化以下目标函数，
在适当的限制下。如果相邻点xi 和xj 相距很远，则我们选择权重Wij 的目标函数会产生严重麻烦。因此，确保如果xi 和xj “接近”，则 yi 和yj 也接近，是一个减少麻烦的方式。
事实证明，对于任何y，我们都有
和之前一样，L = D - W.要看到这一点，请注意Wij 是对称的，并且，从而，
注意，该计算还表明L是半正定的。因此，问题简化为
约束ytDy=1去除嵌入中的任意缩放因子。矩阵D提供图的顶点的自然度量。值Dii （对应于第i个顶点）越大，该顶点越“重要”。从方程式3.1得出L是半正定矩阵，最小化目标函数的向量y由广义特征值问题的最小特征值解给出：
Ly =lambda;Dy
设1是每个顶点取1的常数函数。很容易看出1是具有特征值0的特征向量。如果图连接，1是lambda;=0的唯一特征向量。为了消除这个将G的所有顶点折叠到实数1上的平凡解，=我们放了一个额外的正交性约束和寻找
因此，现在由具有最小非零特征值的特征向量给出解决方案。条件ytD1=0 可以被解释为去除y中的平移不变性。
现在考虑将图形嵌入到m维欧氏空间中的更普遍的问题。嵌入由km矩阵Y [y1y2，...，ym]给出，其中第i行提供第i个顶点的嵌入坐标。同样地，我们需要尽量简化
其中y(i) = [y1（i），...，ym（i）]t是m维表示的ith顶点。这减少了发现
对于一维嵌入问题，约束可防止崩溃到某一点。对于m维嵌入问题，上面给出的约束可以防止折叠到维度小于m-1的子空间（m，如果在一维情况下，我们需要其与常数向量的正交性）。标准方法表明，该解由特征向量矩阵提供，minus;该矩阵对应于广义特征值问题Ly =lambda;Dy的最低特征值。
3.2 Laplace Beltrami算子。
图的拉普拉斯算子类似于流形上的拉普拉斯贝尔特拉米算子。在本节中，我们提供了一个理由，说明为什么Laplace Beltrami算子的特征函数具有嵌入所需的特性。
让M成为一个平滑，紧凑的m维黎曼流形。如果流形嵌入在Rl中，则流形上的黎曼结构（度量张量）由R上的标准黎曼结构l引发。
正如我们对图形所做的那样，我们在这里寻找从流形到实线的地图，使得在流形上靠近在一起的点在线上紧密地映射在一起。设f就是这样一张地图。假设M→R是两次可微分。
考虑两个相邻点x，zisin; M .它们映射到f（x）和f（z），分别。我们首先说明
梯度nabla;f（x）是切线空间TMx中的矢量，使得给定另一个矢量visin;TMx，df（v）=（nabla;f（x），v）m。
令l = distm（x，z）。设c （t）是通过连接x = c（0）和z = c（l）的长度参数化的测地曲线。则
现在由施瓦茨不等式，
由于c（t）是按长度参数化的，我们有我们也有 （由泰勒近似）。最后，通过整合，我们有
其中O和o都为无穷小量。
如果M等距嵌入Rl，那么有和
因此，我们看到了这一 点为我们提供了映射附近的点相距多远的估计。
因此，我们通过以下尝试找到一个平均最佳保留地点的地图
其中积分是相对于Rie-上的标准尺度采取的曼尼尔流形。注意，最小化 对应于图中最小化。这里，f是顶点上的函数，且fi 是图的第i个节点上的f的值。
事实证明，最小化方程3.3的目标函数减少了找到Laplace-Beltrami算子L的本征函数。回想一下
其中div是矢量场的分歧。根据斯托克斯定理， - div和nabla;是形式上的伴随算子，即f是a函数和X是矢量场，然后 ，从而，
我们看到L是半正定的。最小时f必须是一个特征函数。光谱L 在紧凑的流形上 M 已知是离散的（ Rosenberg ，1997）。设特征值（递增次序）为 0=lambda;0 le;lambda;1 le;lambda;2le;...，并且令fi 为对应于特征值lambda;i的本征函数。很容易看出f0 是将整个流形映射到单个点的常数函数。为了避免这种可能性，我们要求（就像在图形设置中一
全文共6565字，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[783]
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
