局部线性嵌入LLE课件

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,局部线性嵌入（,LLE,）,张 昕,局部线性嵌入（LLE）,1,基本概念,有监督学习：假设有一个可用的训练数据集，并通过先验已知信息来设计分类器。,无监督学习：没有已知类别标签的训练数据可用，给定一组特征向量,x,来揭示潜在的相似性，并且将相似性的特征向量分为一组。,LLE就是一种无监督学习的方法。,基本概念 有监督学习：假设有一个可用的训练数据集，并通过,2,流形学习,假设数据是均匀采样于一个高维欧式空间中的低维流形，流形学习就是从高维空间采样数据中恢复低维流形的结构，即找到高维空间中的低维流形，并求出相应的嵌入映射，以实现维数约减或者数据可视化，它是从观测的现象中去寻找事物的本质，找到数据的内在规律。,流形：是一个局部可坐标化的拓扑空间。从拓扑空间的开集（邻域）到欧式空间的子空间的同胚映射，使得每个局部可坐标化。它的本质是分段线性处理。,流形学习 假设数据是均匀采样于一个高维欧式空间中的低维流,3,降维定义,假设D维空间上的一个样本集为X=x,1,x,2,x,3,.,x,n,|x,i,R,D,定义降维问题的模型（X，F），其中，X为数据集，降维映射F F：X-Y,Y R,d,y,j,=f(x,i,)称为X到低维空间的嵌入映射。,降维定义假设D维空间上的一个样本集为X=x1,x2,x,4,数据降维的方法,主成分分析PCA,线性 线性判别分析LDA,LLE,保留局部 LE,非线性 LTSA ISOMAP,基于距离,不保留局部 MDS,基于核函数 KPCA,数据降维的方法 主成分分,5,流形框架,1.寻找局部邻域；a.希望邻域足够大。,b.希望邻域确保局部的线性特征,2.寻找邻域的局部线性结构；,3.计算全局线性结构，保持2所构造的线性结构,流形框架1.寻找局部邻域；a.希望邻域足够大。,6,非线性降维实例：B是从A中提取的样本点（三维），通过非线性降维算法（LLE），将数据映射到二维空间中（C）。从C图中的颜色可以看出通过LLE算法处理后的数据，能很好的保持原有数据的邻域特性,非线性降维实例：B是从A中提取的样本点（三维），通,7,LLE算法描述,LLE算法可以由图所示的一个例子来描述。在图中，LLE能成功地将三维非线性数据映射到二维空间中。如果把图（B）中红颜色和蓝颜色的数据分别看成是分布在三维空间中的两类数据，通过LLE算法降维后，则数据在二维空间中仍能保持相对独立的两类。在图（B）中的黑色小圈中可以看出，如果将黑色小圈中的数据映射到二维空间中，如图（C）中的黑色小圈所示，映射后的数据任能保持原有的数据流形，这说明LLE算法确实能保持流形的领域不变性。,LLE算法描述 LLE算法可以由图所示的,8,LLE算法描述,由此LLE算法可以应用于样本的聚类。而线性方法，如PCA和MDS，都不能与它比拟的。LLE算法操作简单，且算法中的优化不涉及到局部最小化。该算法能解决非线性映射，但是，当处理数据的维数过大，数量过多，涉及到的稀疏矩阵过大，不易于处理。在图中的球形面中，当缺少北极面时，应用LLE算法则能很好的将其映射到二维空间中，如图中的C所示。如果数据分布在整个封闭的球面上，LLE则不能将它映射到二维空间，且不能保持原有的数据流形。那么我们在处理数据中，首先假设数据不是分布在闭合的球面或者椭球面上。,LLE算法描述由此LLE算法可以应用于样本的聚类。而线性方法,9,LLE算法介绍,LLE 算法是基于几何直觉的，即把高维空间数据点按维数映射到低维嵌入空间，即XiYi。步骤为：计算或寻找数据点Xi 的邻居数据点，计算权值矩阵Wij 并通过Wij 与邻居数据点构造数据点，通过权值矩阵Wij 计算低维向量Yi。,LLE算法介绍 LLE 算法是基于几何直觉的，即把高维空,10,LLE算法,LLE算法,11,LLE算法,LLE算法认为在局部意义下，数据的结构是线性的，或者说局部意义下的点在一个超平面上，一次任取一个点，可以使用它的邻近点的线性组合表示。,步骤1：计算或寻找数据点Xi 的邻居数据点,设原始数据由N 个D维的实值向量组成，对于每一个点x,i,i=1,2,3,n;寻找最邻近的点。由于数据由真正光滑的多面体取样而来，故每个数据点和它的邻居近位于或近似位于该多面体的局部线性平面上。这样就能通过线性组合系数刻画出局部平面的几何特征。在LLE中，通过度量欧氏距离的方法可找到每个数据点的K 个最近邻居数据点。,LLE算法 LLE算法认为在局部意义下，数据的,12,LLE算法,步骤2：计算权值，W,ij,i,j=1,2,3,n,权值由与x,i,最邻近点重构得到，这样可以得到最小化核：,其中，X,j,表示第i个点的第j个近邻。其权值被限制为：（a）W,ij,=0,对于非邻近点。,（b）j W,ij,=1,对于邻近点。即覆盖所有邻近点的权值之和为1。,LLE算法 步骤2：计算权值，Wij,13,关于权值,W,ij,用邻近点逼近,Xi,关于权值Wij 用邻近点逼近Xi,14,权值（W,ij,）的计算,权值Wij 说明第j 个数据点对重构第i 个数据点所做的贡献。为了得到合适的权值，在下面两个条件下，对成本函数进行最小值计算：,条件一，每个数据点只能通过它的邻近数据点来构造，并且当某个数据点不属于所重构数据点的邻近数据点时，Wij0；,条件二，权值矩阵每行的所有元素之和等于1，即jWij1。最优权值Wij 将通过计算其最小平方得到。,权值（Wij）的计算权值Wij 说明第j 个数据点对重,15,权值（W,ij,）的特性,在限制条件下，通过最小化重构错误得到的最优权值遵循如下对称特性，即对于特定的数据点，在其本身和其邻居数据点有旋转、缩放、平移操作时将保持其原有性质不变。旋转和缩放不变性从式,得到，而平移的不变性则由条件二保证。由于这种对称性，重构权值能够刻画每一个邻居数据点的几何 属性，而不是依据特定的参考框架的属性。,权值（Wij）的特性在限制条件下，通过最小化重构错误得到,16,假定数据位于或近乎位于一个维数dD 的光滑的非线性多面体上，为了得到好的近似，存在一个线性映射（包含平移、旋转、缩放），这个映射能映射该多面体上每个邻近数据点的高维坐标值到一个单一的内部坐标系统（也即多面体本质属性所确定的内部坐标系统）。故重构权值Wij 能反映旋转不变的内在几何属性，而重构原始D 维空间的权值Wij 也能用于在低维d 空间中重构对应的数据点。,假定数据位于或近乎位于一个维数dD 的光滑的非线性,17,附：三个不变性证明,旋转不变性,缩放不变性,平移不变性,附：三个不变性证明旋转不变性,18,LLE算法,步骤3，使用前面步骤所得到的权值计算相关的点Yi,R,d,i=1,2,3,n,这样，可以最小化未知点Y=y,i,i=1,2,3,n的代价：,该成本函数是基于局部线性重构误差的。式中的嵌入成本函数是向量Yi 的一个二次方的形式，为简化，可通过求解稀疏矩阵的特征向量求解最小值。它的最下面的d 个非零特征向量提供了一组有序的以原点为中心的正交坐标系统。,LLE算法 步骤3，使用前面步骤所得到的权值计,19,结果显示，对上式求解Yi等价于：,对矩阵(I-W),T,(I-W)进行特征值分解。,丢弃与最小特征值相关的特征向量。,选取那些与下一个（更低的）特征值相关特征向量，他们带来低维空间的输出 Yi,R,d,i=1,2,3,n,结果显示，对上式求解Yi等价于：,20,(I-W),T,(I-W)解释,LLE算法的最后一步是将所有的样本点映射到低维空间中。映射条件满足如下所示,其中，为损失函数值，是的输出向量，是 的k个近邻点，且要满足两个条件，即,(I-W)T(I-W)解释LLE算法的最后一步是将所有的样,21,LLE的降维结果,Punctured sphere,LLE的降维结果Punctured sphere,22,LLE的降维结果,Gaussian,LLE的降维结果Gaussian,23,LLE的降维结果,Corner planes,LLE的降维结果Corner planes,24,LLE的降维结果,Twin peaks,LLE的降维结果Twin peaks,25,K-邻域的选择,K-邻域的选择,26,K-邻域的选择,在参数设置中，k只作为一个经验参数，并没有提出很好的办法，通常算法规定K必须大于样本输出的维数。K值的取法是很有讲究的，如果取值太大，算法会出现PCA的效果输出结果很容易让不同的类别叠加在一起。K如果取的太小，则不能保持样本在低维空间中的拓扑结构。,K-邻域的选择 在参数设置中，k只作为一个经验参数，并,27,LLE的K值过大的情况,LLE的K值过大的情况,28,LLE的K值过小的情况,LLE的K值过小的情况,29,最优化选取K,选取的最优K应满足，在选取K条件下，应用LLE算法，使得输入点的相对位置与输出点的相对位置尽量保持一致。通常映射的好坏，可以通过输入点与输出点之间的偶合情况来表示。（输入点之间的距离矩阵和输出点之间的距离矩阵的关系系数衡量）,通过上式求解最优K，其中,表示两个矩阵间的标准线性相关系数。Dx表示输入样本（高维）,之间的距离矩阵，Dr表示输出样本（低维）之间的距离矩阵,最优化选取K选取的最优K应满足，在选取K条件下，应用LLE算,30,降维维数d的选择,降维维数d的选择,31,LLE与PCA降维的比较,LLE与PCA降维的比较,32,Matlab仿真比较,Matlab仿真比较,33,特征值个数不同时出错率比较,特征值个数不同时出错率比较,34,LLE应用手写数字,LLE应用手写数字,35,