机器学习中的降维方法——局部线性嵌入(Locally Linear Embedding,LLE)

局部线性嵌入是一种非常重要的降维方法。和传统的如PCA等关注样本方差的降维方法相比,LLE关注降维时保持样本局部的线性特征,由于LLE在降维时保持了样本的局部特征,他广泛用于图像识别,高维数据可视化等
本文学习自

流形学习概述

LLE属于流形学习(Mainfold learning)的一种。流形学习是一大类基于流形的框架。数学意义上流形比较抽象,不过我们可以认为LLE中的流形是一个不闭合的曲面。这个流形曲面有数据分布比较均匀且比较稠密的特征,有点像流水的味道。基于流形的降维方法就是将流形从高维到低维的降维过程,在降维过程中我们希望流形在高维的一些特征可以得到保留。
一个形象的流形降维过程如下图。我们有一块卷起来的布,我们希望将其展开到一个二维平面,我们希望展开后的布能够在局部保持布结构的特征,其实也就是将其展开的过程,就想两个人将其拉开一样。

关于等距映射
在局部保持布结构的特征,或者说数据特征的方法有很多种,不同的保持方法对应不同的流形算法。比如等距映射(ISOMAP)算法在降维后希望保持样本之间的测地距离而不是欧式距离,因为测地距离更能反映样本之间在流形中的真实距离。
但是等距映射算法有一个问题就是他要找所有样本全局的最优解,当数据量很大,样本维度很高时计算非常耗时。基于这个问题,局部线性嵌入LLE通过放弃所有样本全局最优的降维,只是通过保证局部最优来降维。同时假设样本集在局部是满足线性关系的,进一步减少降维的计算量

LLE思想

LLE首先假设数据在较少局部是线性的,也就是说某一个数据可以由其邻域中的几个样本线性表示。比如我们有一个样本$x_1$,我们在它的原始高维邻域里用K近邻的思想找到和它最近的三个样本$x_2,x_3,x_4$,然后我们假设$x_1$可以由$x_2,x_3,x_4$线性表示:
$ x_1 = w_{12}x_2 + w_{13}x_3 +w_{14}x_4$其中$ w_{12}, w_{13}, w_{14}$为权重系数。
在我们通过LLE降维后,我们希望$x_1$在低维空间对应的投影$x_1’$和 $x_2,x_3,x_4$对应的投影$x_2’,x_3’,x_4’$也尽量保持同样的线性关系,即$x_1’ \approx w_{12}x_2’ + w_{13}x_3’ +w_{14}x_4’ $
也就是,最后从高维投影到低维空间后$w_{12},w_{13},w_{14}$是尽量不变或者最小改变的
从上面看出,线性关系只在样本的附近起作用,离样本远的对局部的线性关系没有影响,因此降维的复杂度就低了很多

LLE算法推导

对于LLE算法我们首先要确定邻域大小的选择,即我们需要多少个邻域样本来表示某个样本。假设这个值为k,我们可以通过和KNN一样的思想通过距离度量(比如欧式距离)来选择某个样本的K个最近邻。
在寻找到某个样本$x_i$的邻域样本后我们就需要该样本和其k个最近邻之间存在的线性关系是什么,说白了就是找权重系数。很明显找权重系数是一个回归问题。
假设我们有m个n维的样本$\{x_1,x_2,…,x_m\}$,我们可以用均方差作为回归问题的损失函数,即:

其中,$Q(i)$表示i的k个近邻样本集合。一般我们也会对权重系数$w_{ij}$做归一化的限制,即权重系数需要满足

对于不在$x_i$邻域内的样本$x_j$我们设$w_{ij} = 0$.这样可以把w扩展到整个数据集的维度。
我们就需要利用上面两个式子求出我们的权重系数,一般我们可以通过 矩阵和拉格朗日乘子法来解决这个问题。
对于第一个式子,我们先将其矩阵化:

其中$W_i = (w_{i1},w_{i2},…w_{ik})^T$
我们令矩阵$Z_i=(x_i-x_j)^T(x_i-x_j)$则第一个式子进一步简化为$J(W) = \sum\limits_{i=1}^{m} W_i^TZ_iW_i$
对于第二个式子我们可以简化为:

其中1k为k维全1向量。
现在我们将矩阵化的两个式子用拉格朗日子乘法合为一个优化目标:

对$W$求导并令其值为0,我们得到

即我们的$W_i = \lambda’Z_i^{-1}1_k$
其中$\lambda’ = -\frac{1}{2}\lambda$为一个常数,利用$W_i^T1_k = 1$对$W_i$归一化,那么最终我们的权重系数$W_i$为$ W_i = \frac{Z_i^{-1}1_k}{1_k^TZ_i^{-1}1_k}$
现在我们得到了高维的权重系数,那么我们希望这些权重系数对应的线性关系在降维后的低维一样得到保持。假设我们的n维样本集$\{x_1,x_2,…,x_m\}$在低维的d维度对应投影为$ \{y_1,y_2,…,y_m\}$ , 则我们希望保持线性关系,也就是希望对应的均方差损失函数最小,即最小化损失函数$J(Y)$如下:

可以看到这个式子和我们在高维的损失函数几乎相同,唯一的区别是高维的式子中,高维数据已知,目标是求最小值对应的权重系数W,而我们在低维是权重系数W已知,求对应的低维数据。注意,这里的W已经是$m\times m$维度,之前的W是$m\times k$维度,我们将那些不在邻域位置的W的位置取值为0,将W扩充到$m\times m$维度。
为了得到标准化的低维数据,一般我们也会加入约束条件如下:

首先我们将目标损失函数矩阵化:

这里$Y$是$d \times m$的矩阵,$I_i$是单位矩阵$I(m \times m)$的第i列也就是$m \times 1$,$W_i$是$m \times m$矩阵W的第i列,也是$ m\times 1$。
如果我们令$ M=(I-W)(I-W)^T$ 则优化函数转变为最小化下式:$J(Y) = tr(YMY^T)$tr为迹函数。约束函数矩阵化为:$ YY^T=mI$
当然我们也可以通过拉格朗日函数来得到这个:

对Y求导并令其为0,我们得到$ 2MY^T + 2\lambda Y^T =0$这样我们就很清楚了,要得到最小的d维数据集,我们需要求出矩阵M最小的d个特征值所对应的d个特征向量组成的矩阵$ Y=(y_1,y_2,…y_d)^T$
一般的由于M的最小特征值为0$不能反映数据的特征 我们通常选择M的第2个到第$d + 1$个最小特征值对应的特征向量$ M=(y_2,y_3,…y_{d+1}) $ 来得到最终的Y
为什么M的最小特征值为0呢?这是因为对于每一个$W_i$我们有 $ \sum_j^m w_{ij} = 1$,所以对于$ m \times m$的矩阵W,有$W^Te = e$,e是全1的向量,$ m \times 1$所以我们得到$ |W^T-I|e =0$ 由于$e \neq 0$,所以只有$ W^T - I = 0$即$(I - W)^T = 0$,两边同左乘$(I - W)$得,$ (I - W )(I - W)^Te = 0e$,即 M的最小特征值为0,对应的特征向量为全1

LLE算法流程

整个LLE算法用一张图可以表示如下:
LLE算法主要分三步:第一步是求k近邻的过程,这个过程使用了和KNN算法一样的求最近邻的方法。第二步就是对每个样本求它在邻域里K个近邻的线性关系,得到线性关系的权重系数W。第三步就是利用权重系数在低维里重构样本数据。具体过程如下:
输入:样本集$ D=\{x_1,x_2,…,x_m\} $, 最近邻数k,降维到的维数d
输出:低维样本集矩阵D’
1.for i to m.以欧氏距离为度量,计算和$x_i$最近邻的k个最近邻构成邻域$Q(i)$
2.for i to m,求出局部协方差矩阵$Z_i=(x_i-x_j)^T(x_i-x_j)$,并求出对应的权重系数向量。

3.由权重系数向量$W_i$组成权重系数矩阵$W$,计算矩阵$M = (I - W)(I - W)^T$
4.计算矩阵M的前d+1个特征值,并计算这d+1个特征值对应的特征向量$ \{y_1,y_2,…y_{d+1}\}$
5.由第二个特征向量到第d+1个特征向量所张成的矩阵即为输出低维样本集矩阵$ D’ = (y_2,y_3,…y_{d+1})$

LLE的一些改进算法

LLE算法存在一个问题当我们的近邻数K大于输入数据的维度m时,会导致我们的局部协方差矩阵$Z_i$不满秩,即这时$Z_i$不存在逆,导致我们在计算时会存在问题
证明: 我们求解每个$W_{ij}$时需要计算每个点与它的K个最近邻的结点所组成的局部协方差矩阵$Z_i$的逆,我们知道$Z_i = (x_i - x_j)^T(x_i - x_j)$,其中$x_i - x_ij$是$ m \times k$的,所以$Z_i$是$ k \times k$的。根据秩的不等式$R(AB)<= min(R(A),R(B))$那么如果$k > m$那么$R(x_i - x_j) < m < k$ 则$R(Z_i)< k $则肯定不是满秩的。
为了解决这样类似的问题,有一些LLE的变种产生出来。比如:Modified Locally Linear Embedding(MLLE)和Hessian Based LLE(HLLE)。
另一个比较好的LLE的变种是Local tangent space alignment(LTSA),它希望保持数据集局部的几何关系,在降维后希望局部的几何关系得以保持,同时利用了局部几何到整体性质过渡的技巧。

LLE总结

LLE是广泛使用的图形图像降维方法,它实现简单,但是对数据的流形分布特征有严格的要求。比如不能是闭合流形,不能是稀疏的数据集,不能是分布不均匀的数据集等等,这限制了它的应用。下面总结下LLE算法的优缺点。

  LLE算法的主要优点有:

  1)可以学习任意维的局部线性的低维流形

  2)算法归结为稀疏矩阵特征分解,计算复杂度相对较小,实现容易。

  LLE算法的主要缺点有:

  1)算法所学习的流形只能是不闭合的,且样本集是稠密均匀的。

  2)算法对最近邻样本数的选择敏感,不同的最近邻数对最后的降维结果有很大影响。


-------------本文结束感谢您的阅读-------------


本文标题:机器学习中的降维方法——局部线性嵌入(Locally Linear Embedding,LLE)

文章作者:Statusrank

CSDN博客欢迎来访!

发布时间:2018年11月02日 - 20:11

最后更新:2018年12月20日 - 21:12

原始链接:https://statusrank.xyz/articles/f5abd121.html

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

万水千山总是情,就给五毛行不行!

相关文章: