LLE(局部线性嵌入)

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

2、是线性的，也就是说一个数据可以由它邻域的几个样本来线性表示。 假设有样本 ，我们在该样本的原始邻域中用K近邻的思想找到其中的K个样本 ，假设 可以由 线性表示，即： 其中， 为权重系数，我们通过LLE降维后，希望 在低维空间对应的投影 和 对应的投影 也尽量保持同样的线性关系，即： 从上面看出，线性关系只在样本附近起作用，离样本远的样本对局部样本的线性关系没有影响，大大降低了降维的难度。1x132,.,xkxx1x132,.,xkxx1113132121.xkkxwxwxw111312,.,wkww1x1x132,.,xkxx121x,.,x,xk1113132121xw.xwxwxkk LL

3、E的推导 对于LLE，首先需要确定邻域的大小，即需要多少的邻域样本来线性表示某个样本。假设这个值为K,我们可以通过欧式距离来选择样本点的K个邻居。 找到K个邻近样本后，需要找到 与K个样本点的线性关系，也就是找到线性关系中的权重系数。因此我们可以通过回归来求权重系数。假设我们有N个D维样本 我们用均方差来定义损失函数：为了后面计算方便，先对系数进行归一化限制，即有ix211)(NiKjjijixwxwJx,.x,xN21Kjijw11 LLE算法推导iTjiNiTjiTiNiijiNiKjjijKjiijNiKjjijiNiKjjijiWxxxxWWxxxwxwxwxxwxwJ)()()()(

4、1212111211211ijiiKiiKiiiKjjiijKjjijKjiijWxxwwwxxxxxxxxwxwxw)(.)(2121111ijiNiTjiTiiKiiKiiiKiiiNiiKiiiKiiKiiiiKiiNiKiiiNiijiWxxxxWwwwxxxxxxxxxxxxwwwwwwxxxxxxwwwxxxxxxWxx)()(.)(121212112121212112121 令 则 为 的局部协方差矩阵 ， 为 的局部重建权值)()(jiTjiixxxxZiiNiTiNiKjjijiWZWxwxwJ1211)(iZixiWixLLE的算法推导 因此，我们最终的目的是使得 取得最小

5、值情况下 的值。 又因为： 可以化简为根据约束条件，可以用拉格朗日乘子法：iiNiTiWZWWJ1)(iW11.11.121KiKiiKTiwwwW11Kjjw11)(1KTiiiNiTiWWZWWJ) 11()(L1KTiiiNiTiWWZWW LLE算法推导 对W求导并令其值为0 ,求得 ： （1） 前面已知 ，则 连立（1）式得解得：因为 ，因此可以根据上述公式，迭代K个近邻数据点，依次可以求得 ，然后在迭代所有的数据点，求得W的权重矩阵。01Z2iKiW11 KTiWTiKiWKT1111WKiTKKiiZZW11111)()(jiTjiixxxxZ,.,21iKiiiwwwWLLE算

6、法推导 得到权重矩阵后，将原始的数据映射到低维空间中。映射的条件满足： 此时，权重系数我们上一步已经求得，要求得满足最小损失函数条件下的数据 ,而且满足以下条件： （1） 其中， 是单位矩阵211)(minNiKjjijiywyYJy,.,y,YyN21Niiy10I1TiNiiyyILLE算法推导T1212)()()(minYWIWIYWIYYWYIYJTNiiiNiii令结合上述约束条件： TWIWIM)(I0)(min11TiNiiNiiTyyyYMYYJ 根据拉格朗日乘子法有：对Y进行求导令其为0，得： 根据矩阵特征值得定义： 设A为n阶矩阵，若存在常数 和n维 非零向量， 使得则 为

7、A的一个特征值， 为 对应的特征向量。 因此， 为M矩阵的特征向量组成的矩阵。)N-()(IYYYMYYLTT-M02M2TTTTTTYMYYYYYxxAxTY 将 带入到 得: 即：若要求 最小，则 最小，即取M的最小特征值。 TTYY-M)N-()(IYYYMYYLTTNIYL)( -NIYL)()(YLnnnnnnnndnnnnnnnyyymmmmmmmmmmkkkmmmmmmmmmm.,.,.213212222111211213212222111211 SLLE 传统的LLE在第一步时根据样本点间欧式距离来寻找k个近邻点，而SLLE在处理这一步增加了样本的类别的信息，SLLE算法的其余步骤与LLE相同。 SLLE在计算点与点之间的距离采用以下两种方法： 1.第一种是采用以下公式来修正点与点之间的距离公式： 是直接采用欧式距离计算出的距离， 表示类与类之间的最大距离； 取0或者1，当两个点属于同一类时 否则 是控制点集之间的距离参数， ，是一个经验参数。)max(DDDD)ma