LLE(局部线性嵌入)课件.ppt

《LLE(局部线性嵌入)课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、LLE杨浩LLE的背景意义传统的降维方法主要有PCA、LDA。PCA的基本思想是通过线性变换寻找一组最优的基，来重构原始数据样本，以使重构后的样本与原始样本误差最小。LDA是以样本的可区分性为主要目标，通过线性变换以达到类内的散度最小，类间的散度最大的目的。但是当数据集在高维空间呈现高度扭曲时，它们很难发现嵌入在数据集中的非线性结构和恢复内在结构。LLE算法LLE算法是是流形学习的一种。流形学习方法提供了一种新的研究途径，它能够对数据集中高维数据空间进行非线性降维，揭示其中的流形分布。LLE是属于流形学习的一种。一个流形降维的过程如下图：LLE的算法思想

2、LLE首先假设数据在较小的局部是线性的，也就是说一个数据可以由它邻域的几个样本来线性表示。假设有样本，我们在该样本的原始邻域中用K近邻的思想找到其中的K个样本，假设可以由线性表示，即：其中，为权重系数，我们通过LLE降维后，希望在低维空间对应的投影和对应的投影也尽量保持同样的线性关系，即：从上面看出，线性关系只在样本附近起作用，离样本远的样本对局部样本的线性关系没有影响，大大降低了降维的难度。LLE的推导对于LLE，首先需要确定邻域的大小，即需要多少的邻域样本来线性表示某个样本。假设这个值为K,我们可以通过欧式距离来选择样本点的K个邻居。找到K个邻近样本

3、后，需要找到与K个样本点的线性关系，也就是找到线性关系中的权重系数。因此我们可以通过回归来求权重系数。假设我们有N个D维样本我们用均方差来定义损失函数：为了后面计算方便，先对系数进行归一化限制，即有LLE算法推导令则为的局部协方差矩阵，为的局部重建权值LLE的算法推导因此，我们最终的目的是使得取得最小值情况下的值。又因为：可以化简为根据约束条件，可以用拉格朗日乘子法：LLE算法推导对W求导并令其值为0,求得：（1）前面已知，则连立（1）式得解得：因为，因此可以根据上述公式，迭代K个近邻数据点，依次可以求得，然后在迭代所有的数据点，求得W的权重矩阵。LLE

4、算法推导得到权重矩阵后，将原始的数据映射到低维空间中。映射的条件满足：此时，权重系数我们上一步已经求得，要求得满足最小损失函数条件下的数据,而且满足以下条件：（1）其中，是单位矩阵LLE算法推导令结合上述约束条件：根据拉格朗日乘子法有：对Y进行求导令其为0，得：根据矩阵特征值得定义：设A为n阶矩阵，若存在常数和n维非零向量，使得则为A的一个特征值，为对应的特征向量。因此，为M矩阵的特征向量组成的矩阵。将带入到得:即：若要求最小，则最小，即取M的最小特征值。SLLE传统的LLE在第一步时根据样本点间欧式距离来寻找k个近邻点，而SLLE在处理这一步增加了样本

5、的类别的信息，SLLE算法的其余步骤与LLE相同。SLLE在计算点与点之间的距离采用以下两种方法：1.第一种是采用以下公式来修正点与点之间的距离公式：是直接采用欧式距离计算出的距离，表示类与类之间的最大距离；取0或者1，当两个点属于同一类时否则是控制点集之间的距离参数，，是一个经验参数。2.SLLE求距离的第二种方法不同于LLE的是SLLE不是在全局范围内寻找近邻点，而是在每个点所在的类的样本中寻找样本点。这种方法的缺点是当我们确定近邻点个数为K时，如果某一类的样本数小于K，那么这种方法会失败。