局部线性嵌入LLE课件

局部线性嵌入（LLE）张昕局部线性嵌入（LLE）1基本概念

有监督学习：假设有一个可用的训练数据集，并通过先验已知信息来设计分类器。无监督学习：没有已知类别标签的训练数据可用，给定一组特征向量x来揭示潜在的相似性，并且将相似性的特征向量分为一组。LLE就是一种无监督学习的方法。基本概念有监督学习：假设有一个可用的训练数据集，并通过2流形学习

假设数据是均匀采样于一个高维欧式空间中的低维流形，流形学习就是从高维空间采样数据中恢复低维流形的结构，即找到高维空间中的低维流形，并求出相应的嵌入映射，以实现维数约减或者数据可视化，它是从观测的现象中去寻找事物的本质，找到数据的内在规律。

流形：是一个局部可坐标化的拓扑空间。从拓扑空间的开集（邻域）到欧式空间的子空间的同胚映射，使得每个局部可坐标化。它的本质是分段线性处理。流形学习假设数据是均匀采样于一个高维欧式空间中的低维流3降维定义假设D维空间上的一个样本集为X={x1,x2,x3,….xn|xi∈RD}定义降维问题的模型（X，F），其中，X为数据集，降维映射FF：X->Y,Y∈Rd,yj=f(xi)称为X到低维空间的嵌入映射。降维定义假设D维空间上的一个样本集为X={x1,x2,x4数据降维的方法

主成分分析PCA线性线性判别分析LDA

LLE

保留局部LE

非线性LTSAISOMAP基于距离不保留局部MDS基于核函数KPCA

数据降维的方法主成分分5流形框架1.寻找局部邻域；a.希望邻域足够大。b.希望邻域确保局部的线性特征2.寻找邻域的局部线性结构；3.计算全局线性结构，保持2所构造的线性结构流形框架1.寻找局部邻域；a.希望邻域足够大。6

非线性降维实例：B是从A中提取的样本点（三维），通过非线性降维算法（LLE），将数据映射到二维空间中（C）。从C图中的颜色可以看出通过LLE算法处理后的数据，能很好的保持原有数据的邻域特性

非线性降维实例：B是从A中提取的样本点（三维），通7LLE算法描述

LLE算法可以由图所示的一个例子来描述。在图中，LLE能成功地将三维非线性数据映射到二维空间中。如果把图（B）中红颜色和蓝颜色的数据分别看成是分布在三维空间中的两类数据，通过LLE算法降维后，则数据在二维空间中仍能保持相对独立的两类。在图（B）中的黑色小圈中可以看出，如果将黑色小圈中的数据映射到二维空间中，如图（C）中的黑色小圈所示，映射后的数据任能保持原有的数据流形，这说明LLE算法确实能保持流形的领域不变性。LLE算法描述LLE算法可以由图所示的8LLE算法描述由此LLE算法可以应用于样本的聚类。而线性方法，如PCA和MDS，都不能与它比拟的。LLE算法操作简单，且算法中的优化不涉及到局部最小化。该算法能解决非线性映射，但是，当处理数据的维数过大，数量过多，涉及到的稀疏矩阵过大，不易于处理。在图中的球形面中，当缺少北极面时，应用LLE算法则能很好的将其映射到二维空间中，如图中的C所示。如果数据分布在整个封闭的球面上，LLE则不能将它映射到二维空间，且不能保持原有的数据流形。那么我们在处理数据中，首先假设数据不是分布在闭合的球面或者椭球面上。LLE算法描述由此LLE算法可以应用于样本的聚类。而线性方法9LLE算法介绍

LLE算法是基于几何直觉的，即把高维空间数据点按维数映射到低维嵌入空间，即Xi→Yi。步骤为：计算或寻找数据点Xi的邻居数据点，计算权值矩阵Wij并通过Wij与邻居数据点构造数据点，通过权值矩阵Wij计算低维向量Yi。LLE算法介绍LLE算法是基于几何直觉的，即把高维空10LLE算法

LLE算法11LLE算法

LLE算法认为在局部意义下，数据的结构是线性的，或者说局部意义下的点在一个超平面上，一次任取一个点，可以使用它的邻近点的线性组合表示。步骤1：计算或寻找数据点Xi的邻居数据点设原始数据由N个D维的实值向量组成，对于每一个点xi,i=1,2,3,…,n;寻找最邻近的点。由于数据由真正光滑的多面体取样而来，故每个数据点和它的邻居近位于或近似位于该多面体的局部线性平面上。这样就能通过线性组合系数刻画出局部平面的几何特征。在LLE中，通过度量欧氏距离的方法可找到每个数据点的K个最近邻居数据点。

LLE算法LLE算法认为在局部意义下，数据的12LLE算法步骤2：计算权值，Wij,i,j=1,2,3,…,n,权值由与xi最邻近点重构得到，这样可以得到最小化核：

其中，Xj表示第i个点的第j个近邻。其权值被限制为：（a）Wij=0,对于非邻近点。（b）∑jWij=1,对于邻近点。即覆盖所有邻近点的权值之和为1。LLE算法步骤2：计算权值，Wij,13关于权值Wij用邻近点逼近Xi关于权值Wij用邻近点逼近Xi14权值（Wij）的计算权值Wij说明第j个数据点对重构第i个数据点所做的贡献。为了得到合适的权值，在下面两个条件下，对成本函数进行最小值计算：条件一，每个数据点只能通过它的邻近数据点来构造，并且当某个数据点不属于所重构数据点的邻近数据点时，Wij＝0；条件二，权值矩阵每行的所有元素之和等于1，即ΣjWij＝1。最优权值Wij将通过计算其最小平方得到。权值（Wij）的计算权值Wij说明第j个数据点对重15权值（Wij）的特性在限制条件下，通过最小化重构错误得到的最优权值遵循如下对称特性，即对于特定的数据点，在其本身和其邻居数据点有旋转、缩放、平移操作时将保持其原有性质不变。旋转和缩放不变性从式得到，而平移的不变性则由条件二保证。由于这种对称性，重构权值能够刻画每一个邻居数据点的几何属性，而不是依据特定的参考框架的属性。权值（Wij）的特性在限制条件下，通过最小化重构错误得到16假定数据位于或近乎位于一个维数d＜＜D的光滑的非线性多面体上，为了得到好的近似，存在一个线性映射（包含平移、旋转、缩放），这个映射能映射该多面体上每个邻近数据点的高维坐标值到一个单一的内部坐标系统（也即多面体本质属性所确定的内部坐标系统）。故重构权值Wij能反映旋转不变的内在几何属性，而重构原始D维空间的权值Wij也能用于在低维d空间中重构对应的数据点。假定数据位于或近乎位于一个维数d＜＜D的光滑的非线性17附：三个不变性证明旋转不变性缩放不变性平移不变性附：三个不变性证明旋转不变性18LLE算法步骤3，使用前面步骤所得到的权值计算相关的点Yi

∈Rd,i=1,2,3,…,n,这样，可以最小化未知点Y={yi,i=1,2,3,…,n}的代价：该成本函数是基于局部线性重构误差的。式中的嵌入成本函数是向量Yi的一个二次方的形式，为简化，可通过求解稀疏矩阵的特征向量求解最小值。它的最下面的d个非零特征向量提供了一组有序的以原点为中心的正交坐标系统。LLE算法步骤3，使用前面步骤所得到的权值计19结果显示，对上式求解Yi等价于：对矩阵(I-W)T(I-W)进行特征值分解。丢弃与最小特征值相关的特征向量。选取那些与下一个（更低的）特征值相关特征向量，他们带来低维空间的输出Yi

∈Rd,i=1,2,3,…,n结果显示，对上式求解Yi等价于：20(I-W)T(I-W)解释

LLE算法的最后一步是将所有的样本点映射到低维空间中。映射条件满足如下所示其中，为损失函数值，是的输出向量，是的k个近邻点，且要满足两个条件，即

(I-W)T(I-W)解释

LLE算法的最后一步是将所有的样21LLE的降维结果PuncturedsphereLLE的降维结果Puncturedsphere22LLE的降维结果GaussianLLE的降维结果Gaussian23LLE的降维结果CornerplanesLLE的降维结果Cornerplanes24LLE的降维结果TwinpeaksLLE的降维结果Twinpeaks25K-邻域的选择

K-邻域的选择26K-邻域的选择在参数设置中，k只作为一个经验参数，并没有提出很好的办法，通常算法规定K必须大于样本输出的维数。K值的取法是很有讲究的，如果取值太大，算法会出现PCA的效果输出结果很容易让不同的类别叠加在一起。K如果取的太小，则不能保持样本在低维空间中的拓扑结构。K-邻域的选择在参数设置中，k只作为一个经验参数，并27LLE的K值过大的情况

LLE的K值过大的情况28LLE的K值过小的情况

LLE的K值过小的情况29最优化选取K选取的最优K应满足，在选取K条件下，应用LLE算法，使得输入点的相对位置与输出点的相对位置尽量保持一致。通常映射的好坏，可以通过输入点与输出点之间的偶合情况来表示。（输入点之间的距离矩阵和输出点之间的距离矩阵的关系系数衡量）通过上式求解最优K，其中