特征抽取 局部线性嵌入LLEtype
status
date
slug
summary
tags
category
icon
password
Property
原理
流形学习概述
LLE属于流形学习(Manifold Learning)的一种，因此首先看看什么是流形学习。
流形学习是一大类基于流形的框架。数学意义上的流形比较抽象，不过可以认为LLE中的流形是一个不闭合的曲面。这个流形曲面有数据分布比较均匀，且比较稠密的特征，有点像流水的味道。基于流行的降维算法就是将流形从高维到低维的降维过程，在降维的过程中我们希望流形在高维的一些特征可以得到保留。
一个形象的流形降维过程如下图。有一块卷起来的布，希望将其展开到一个二维平面，展开后的布能够在局部保持布结构的特征，其实也就是将其展开的过程，就想两个人将其拉开一样。
在局部保持布结构的特征，或者说数据特征的方法有很多种，不同的保持方法对应不同的流形算法。比如等距映射（ISOMAP）算法在降维后希望保持样本之间的测地距离而不是欧式距离，因为测地距离更能反映样本之间在流形中的真实距离。
但是等距映射算法有一个问题就是他要找所有样本全局的最优解，当数据量很大，样本维度很高时，计算非常的耗时，鉴于这个问题，LLE通过放弃所有样本全局最优的降维，只是通过保证局部最优来降维。同时假设样本集在局部是满足线性关系的，进一步减少的降维的计算量。
LLE思想
LLE假设数据在较小的局部是线性的，也就是说某一个数据可以由它邻域中的几个样本来线性表示。比如有一个样本，在它的原始高维邻域里用K-近邻思想找到和它最近的三个样本。然后假设可以由线性表示：
为权重系数。在通过LLE降维后，希望在低维空间对应的投影和对应的投影 也尽量保持同样的线性关系，即：
也就是说投影前后线性关系的权重系数是尽量不变或者最小改变的。
从上面可以看出，线性关系只在样本的附近起作用，离样本远的样本对局部的线性关系没有影响，因此降维的复杂度降低了很多。
LLE推导
对于LLE算法，首先要确定邻域大小的选择，即需要多少个邻域样本来线性表示某个样本。假设这个值为，可以通过和KNN一样的思想通过距离度量比如欧式距离来选择某样本的个最近邻。
在寻找到某个样本的的个最近邻之后就需要找到找到和这个最近邻之间的线性关系，也就是要找到线性关系的权重系数。找线性关系，这显然是一个回归问题。
假设有个维样本，可以用均方差作为回归问题的损失函数：
表示的个近邻样本集合。一般也会对权重系数做归一化的限制，即权重系数需要满足：
对于不在样本邻域内的样本，令对应的，这样可以把扩展到整个数据集的维度。
一般可以通过矩阵和拉格朗日子乘法来求解这个最优化问题。对于第一个式子，将其矩阵化：
其中
令矩阵，则进一步简化为
对于第二个式子，可以矩阵化为：
其中为维全1向量。
将矩阵化的两个式子用拉格朗日子乘法合为一个优化目标：
对求导并令其值为0，得到
其中为一个常数。利用，对归一化，那么最终的权重系数为：
现在得到了高维的权重系数，那么希望这些权重系数对应的线性关系在降维后的低维一样得到保持。假设维样本集在低维的维度对应投影为，则希望保持线性关系，也就是希望对应的均方差损失函数最小，即最小化损失函数如下：
可以看到这个式子和高维的损失函数几乎相同，唯一的区别是高维的式子中，高维数据已知，目标是求最小值对应的权重系数，而在低维是权重系数已知，求对应的低维数据。注意，这里的已经是维度，之前的是维度，我们将那些不在邻域位置的的位置取值为0，将扩充到维度。
为了得到标准化的低维数据，一般也会加入约束条件如下：
将目标损失函数矩阵化：
如果令，则优化函数转变为最小化下式：
约束函数矩阵化为：
这里的优化过程和PCA的优化几乎一样。其实最小化对应的就是的最小的个特征值所对应的个特征向量组成的矩阵。当然也可以通过拉格朗日函数来得到这个:
对求导并令其为0，得到，即 ，要得到最小的维数据集，需要求出矩阵最小的个特征值所对应的个特征向量组成的矩阵即可。
一般的，由于的最小特征值为0不能反应数据特征，此时对应的特征向量为全1。通常选择的第个到第个最小的特征值对应的特征向量来得到最终的。为什么的最小特征值为0呢？这是因为，得到
，由于，所以只有，即，两边同时左乘，即可得到 ，即的最小特征值为0。
算法流程
整个LLE算法用一张图可以表示如下：
LLE算法主要分为三步
- 求 近邻的过程，这个过程使用了和KNN算法一样的求最近邻的方法
- 对每个样本求它在邻域里的 个近邻的线性关系，得到线性关系权重系数
- 利用权重系数来在低维里重构样本数据
具体过程如下：
输入：样本集，最近邻数，降维到的维数
输出： 低维样本集矩阵
- for i 1 to m，按欧式距离作为度量，计算和最近的的个最近邻
- for i 1 to m，求出局部协方差矩阵，并求出对应的权重系数向量：
- 由权重系数向量组成权重系数矩阵，计算矩阵
- 计算矩阵的前个特征值，并计算这个特征值对应的特征向量
- 由第二个特征向量到第个特征向量所张成的矩阵即为输出低维样本集矩阵
LLE的改进算法
LLE算法很简单高效，但是有一些问题，比如如果近邻数k大于输入数据的维度时，权重系数矩阵不是满秩的。为了解决这样类似的问题，有一些LLE的变种产生出来。
比如：Modified Locally Linear Embedding(MLLE)和Hessian Based LLE(HLLE)。对于HLLE，它不是考虑保持局部的线性关系，而是保持局部的Hessian矩阵的二次型的关系。而对于MLLE，它对搜索到的最近邻的权重进行了度量，一般都是找距离最近的个最近邻就可以了，而MLLE在找距离最近的 个最近邻的同时要考虑近邻的分布权重，它希望找到的近邻的分布权重尽量在样本的各个方向，而不是集中在一侧。
另一个比较好的LLE的变种是Local tangent space alignment(LTSA)，它希望保持数据集局部的几何关系，在降维后希望局部的几何关系得以保持，同时利用了局部几何到整体性质过渡的技巧。
优缺点
LLE是广泛使用的图形图像降维方法，它实现简单，但是对数据的流形分布特征有严格的要求。比如不能是闭合流形，不能是稀疏的数据集，不能是分布不均匀的数据集等等，这限制了它的应用。
主要优点：
- 可以学习任意维的局部线性的低维流形
- 算法归结为稀疏矩阵特征分解，计算复杂度相对较小，实现容易
主要缺点：
- 算法所学习的流形只能是不闭合的，且样本集是稠密均匀的
- 算法对最近邻样本数的选择敏感，不同的最近邻数对最后的降维结果有很大影响
代码
locally_linear_embedding- n_neighbors：即搜索样本的近邻的个数，默认是5。个数越大，建立样本局部关系的时间会越大，也就意味着算法的复杂度会增加。当然，降维后样本的局部关系会保持的更好。一般来说，如果算法运行时间可以接受，可以尽量选择一个比较大一些的n_neighbors。
- n_components：即降维到的维数。如果降维的目的是可视化，则一般可以选择2-5维。
- reg ：正则化系数，在n_neighbors大于n_components时，即近邻数大于降维的维数时，由于样本权重矩阵不是满秩的，LLE通过正则化来解决这个问题。默认是0.001。一般不用管这个参数。当近邻数远远的大于降维到的维数时可以考虑适当增大这个参数。
- eigen_solver：特征分解的方法。有‘arpack’和‘dense’两者算法选择。当然也可以选择'auto'让scikit-learn自己选择一个合适的算法。‘arpack’和‘dense’的主要区别是‘dense’一般适合于非稀疏的矩阵分解。而‘arpack’虽然可以适应稀疏和非稀疏的矩阵分解，但在稀疏矩阵分解时会有更好算法速度。当然由于它使用一些随机思想，所以它的解可能不稳定，一般需要多选几组随机种子来尝试。
- method： 即LLE的具体算法。LocallyLinearEmbedding支持4种LLE算法，分别是'standard'对应标准的LLE算法，'hessian'对应HLLE算法，'modified'对应MLLE算法，‘ltsa’对应LTSA算法。默认是'standard'。一般来说HLLE/MLLE/LTSA算法在同样的近邻数n_neighbors情况下，运行时间会比标准的LLE长，降维的效果会稍微好一些。如果对降维后的数据局部效果很在意，那么可以考虑使用HLLE/MLLE/LTSA或者增大n_neighbors，否则标准的LLE就可以了。需要注意的是使用MLLE要求n_neighbors > n_components，而使用HLLE要求n_neighbors > n_components * (n_components + 3) / 2
- neighbors_algorithm：这个是k近邻的搜索方法，和KNN算法的使用的搜索方法一样。算法一共有三种，第一种是蛮力实现，第二种是KD树实现，第三种是球树实现。对于这个参数，一共有4种可选输入，‘brute’对应第一种蛮力实现，‘kd_tree’对应第二种KD树实现，‘ball_tree’对应第三种的球树实现， ‘auto’则会在上面三种算法中做权衡，选择一个拟合最好的最优算法。需要注意的是，如果输入样本特征是稀疏的时候，无论选择哪种算法，最后scikit-learn都会去用蛮力实现‘brute’。如果样本少特征也少，使用默认的 ‘auto’就够了。 如果数据量很大或者特征也很多，用"auto"建树时间会很长，效率不高，建议选择KD树实现‘kd_tree’，此时如果发现‘kd_tree’速度比较慢或者已经知道样本分布不是很均匀时，可以尝试用‘ball_tree’。而如果输入样本是稀疏的，无论选择哪个算法最后实际运行的都是‘brute’。
