资源描述：
《局部线性嵌入（LLE）课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、局部线性嵌入（LLE）张昕基本概念有监督学习：假设有一个可用的训练数据集，并通过先验已知信息来设计分类器。无监督学习：没有已知类别标签的训练数据可用，给定一组特征向量x来揭示潜在的相似性，并且将相似性的特征向量分为一组。LLE就是一种无监督学习的方法。流形学习假设数据是均匀采样于一个高维欧式空间中的低维流形，流形学习就是从高维空间采样数据中恢复低维流形的结构，即找到高维空间中的低维流形，并求出相应的嵌入映射，以实现维数约减或者数据可视化，它是从观测的现象中去寻找事物的本质，找到数据的内在规律。流形：是一个局部可坐标化的拓扑空间
2、。从拓扑空间的开集（邻域）到欧式空间的子空间的同胚映射，使得每个局部可坐标化。它的本质是分段线性处理。降维定义假设D维空间上的一个样本集为X={x1,x2,x3,….xn
3、xi∈RD}定义降维问题的模型（X，F），其中，X为数据集，降维映射FF：X->Y,Y∈Rd,yj=f(xi)称为X到低维空间的嵌入映射。数据降维的方法主成分分析PCA线性线性判别分析LDALLE保留局部LE非线性LTSAISOMAP基于距离不保留局部MDS基于核函数KPCA流形框架1.寻找局部邻域；a.希望邻域足够大。b.希望邻域确保局部的线性特征2.寻找
4、邻域的局部线性结构；3.计算全局线性结构，保持2所构造的线性结构非线性降维实例：B是从A中提取的样本点（三维），通过非线性降维算法（LLE），将数据映射到二维空间中（C）。从C图中的颜色可以看出通过LLE算法处理后的数据，能很好的保持原有数据的邻域特性LLE算法描述LLE算法可以由图所示的一个例子来描述。在图中，LLE能成功地将三维非线性数据映射到二维空间中。如果把图（B）中红颜色和蓝颜色的数据分别看成是分布在三维空间中的两类数据，通过LLE算法降维后，则数据在二维空间中仍能保持相对独立的两类。在图（B）中的黑色小圈中可以看出
5、，如果将黑色小圈中的数据映射到二维空间中，如图（C）中的黑色小圈所示，映射后的数据任能保持原有的数据流形，这说明LLE算法确实能保持流形的领域不变性。LLE算法描述由此LLE算法可以应用于样本的聚类。而线性方法，如PCA和MDS，都不能与它比拟的。LLE算法操作简单，且算法中的优化不涉及到局部最小化。该算法能解决非线性映射，但是，当处理数据的维数过大，数量过多，涉及到的稀疏矩阵过大，不易于处理。在图中的球形面中，当缺少北极面时，应用LLE算法则能很好的将其映射到二维空间中，如图中的C所示。如果数据分布在整个封闭的球面上，LLE
6、则不能将它映射到二维空间，且不能保持原有的数据流形。那么我们在处理数据中，首先假设数据不是分布在闭合的球面或者椭球面上。LLE算法介绍LLE算法是基于几何直觉的，即把高维空间数据点按维数映射到低维嵌入空间，即Xi→Yi。步骤为：计算或寻找数据点Xi的邻居数据点，计算权值矩阵Wij并通过Wij与邻居数据点构造数据点，通过权值矩阵Wij计算低维向量Yi。LLE算法LLE算法LLE算法认为在局部意义下，数据的结构是线性的，或者说局部意义下的点在一个超平面上，一次任取一个点，可以使用它的邻近点的线性组合表示。步骤1：计算或寻找数据点X
7、i的邻居数据点设原始数据由N个D维的实值向量组成，对于每一个点xi,i=1,2,3,…,n;寻找最邻近的点。由于数据由真正光滑的多面体取样而来，故每个数据点和它的邻居近位于或近似位于该多面体的局部线性平面上。这样就能通过线性组合系数刻画出局部平面的几何特征。在LLE中，通过度量欧氏距离的方法可找到每个数据点的K个最近邻居数据点。LLE算法步骤2：计算权值，Wij,i,j=1,2,3,…,n,权值由与xi最邻近点重构得到，这样可以得到最小化核：其中，Xj表示第i个点的第j个近邻。其权值被限制为：（a）Wij=0,对于非邻近点。（
8、b）∑jWij=1,对于邻近点。即覆盖所有邻近点的权值之和为1。关于权值Wij用邻近点逼近Xi权值（Wij）的计算权值Wij说明第j个数据点对重构第i个数据点所做的贡献。为了得到合适的权值，在下面两个条件下，对成本函数进行最小值计算：条件一，每个数据点只能通过它的邻近数据点来构造，并且当某个数据点不属于所重构数据点的邻近数据点时，Wij＝0；条件二，权值矩阵每行的所有元素之和等于1，即ΣjWij＝1。最优权值Wij将通过计算其最小平方得到。权值（Wij）的特性在限制条件下，通过最小化重构错误得到的最优权值遵循如下对称特性，即对
9、于特定的数据点，在其本身和其邻居数据点有旋转、缩放、平移操作时将保持其原有性质不变。旋转和缩放不变性从式得到，而平移的不变性则由条件二保证。由于这种对称性，重构权值能够刻画每一个邻居数据点的几何属性，而不是依据特定的参考框架的属性。假定数据位于或近乎位于一个维数d＜＜D的光滑
