LLE(局部线性嵌入).pptx

LLE 杨浩 LLE的背景意义 传统的降维方法主要有PCA、LDA。PCA的基本思想是通过线性变换寻找一组最优的基，来重构原始数据样本，以使重构后的样本与原始样本误差最小。LDA是以样本的可区分性为主要目标，通过线性变换以达到类内的散度最小，类间的散度最大的目的。但是当数据集在高维空间呈现高度扭曲时，它们很难发现嵌入在数据集中的非线性结构和恢复内在结构。 LLE算法 LLE算法是是流形学习的一种。流形学习方法提供了一种新的研究途径，它能够对数据集中高维数据空间进行非线性降维，揭示其中的流形分布。LLE是属于流形学习的一种。 一个流形降维的过程如下图： LLE的算法思想 LLE首先假设数据在较小的局部是线性的，也就是说一个数据可以由它邻域的几个样本来线性表示。 假设有样本 ，我们在该样本的原始邻域中用K近邻的思想找到其中的K个样本 ，假设 可以由 线性表示，即： 其中， 为权重系数，我们通过LLE降维后，希望 在低维空间对应的投影 和 对应的投影 也尽量保持同样的线性关系，即： 从上面看出，线性关系只在样本附近起作用，离样本远的样本对局部样本的线性关系没有影响，大大降低了降维的难度。 LLE的推导 对于LLE，首先需要确定邻域的大小，即需要多少的邻域样本来线性表示某个样本。假设这个值为K,我们可以通过欧式距离来选择样本点的K个邻居。 找到K个邻近样本后，需要找到 与K个样本点的线性关系，也就是找到线性关系中的权重系数。因此我们可以通过回归来求权重系数。假设我们有N个D维样本 我们用均方差来定义损失函数： 为了后面计算方便，先对系数进行归一化限制，即有 LLE算法推导 令 则 为 的局部协方差矩阵 ， 为 的局部重建权值 LLE的算法推导 因此，我们最终的目的是使得 取得最小值情况下 的值。 又因为： 可以化简为 根据约束条件，可以用拉格朗日乘子法： LLE算法推导 对W求导并令其值为0 ,求得 ： （1） 前面已知 ，则 连立（1）式得解得： 因为 ，因此可以根据上述公式，迭代K个近邻数据点，依次可以求得 ，然后在 迭代所有的数据点，求得W的权重矩阵。 LLE算法推导 得到权重矩阵后，将原始的数据映射到低维空间中。映射的条件满足： 此时，权重系数我们上一步已经求得，要求得满足最小损失函数条件下的数据 ,而且满足以下条件： （1） 其中， 是单位矩阵 LLE算法推导 令 结合上述约束条件： 根据拉格朗日乘子法有： 对Y进行求导令其为0，得： 根据矩阵特征值得定义： 设A为n阶矩阵，若存在常数 和n维 非零向量， 使得 则 为A的一个特征值， 为 对应的特征向量。 因此， 为M矩阵的特征向量组成的矩阵。 将 带入到 得: 即： 若要求 最小，则 最小，即取M的最小特征值。 SLLE 传统的LLE在第一步时根据样本点间欧式距离来寻找k个近邻点，而SLLE在处理这一步增加了样本的类别的信息，SLLE算法的其余步骤与LLE相同。 SLLE在