算法系列——无监督学习——16.LLE

一、概述

LLE 是一种被称为流形学习（manifold learning）的算法，它的目标是对具有非线性结构的数据进行降维。

下面来看一下具体的例子。图a 是经常作为非线性数据的例子的瑞士卷（Swiss rolls）数据集的图形。瑞士卷数据集就像一个二维结构（长方形）被卷曲后埋藏在三维空间中的数据集。我们将LLE和PCA应用于该数据集，降维至二维后的结果分别如图b和图c所示。LLE可以把埋藏在三维空间中的二维结构取出，将其以二维数据表示。PCA则采取像是将原始数据压扁的方式进行降维。由于PCA适用于变量之间存在相关性的数据，所以在对瑞士卷数据集这种非线性数据降维时，更适合采用LLE这样的方法。

二、算法说明

LLE算法要求数据点由其近邻点的线性组合来表示。

我们看一个例子：对于数据点x1，以最接近x1的两个点x2和x3的线性组合来表示它。下图中的左图是当x1=(1, 1, 1)，x2=(-1, 0, -1)，x3= (2, 3, 2) 时的情况，如果x2 和 x3 的权重分别为w12=-1/3，w13=1/3，那么x1 可以表示为x1=w12*x2 + w13*x3。如果在不扭转三维空间的3个点之间的关系的前提下把它们移动到二维空间，我们就可以继续使用这些权重来以近邻点表示x1。实际的数据虽然在三维空间上呈现瑞士卷那样的卷曲结构，但LLE将其视为局部的点与点的关系，即近邻点之间是不弯曲的空间，所以仍使用近邻点来表示数据点。

下面对LLE算法进行说明。假设在D维空间内存在一个d维空间的结构（d < D），使用如下图所示的步骤进行降维。

考虑数据点xi的近邻点是LLE的特点。

三、示例代码

下面是对瑞士卷数据集应用LLE的代码，其中设置的近邻点的数量为12。

from sklearn.datasets import make_swiss_roll
from sklearn.manifold import LocallyLinearEmbedding
data, color = make_swiss_roll(n_samples=1500)
n_neighbors = 12  # 近邻点的数量
n_components = 2  # 降维后的维度
model = LocallyLinearEmbedding(n_neighbors=n_neighbors,
n_components=n_components)
model.fit(data)
print(model.transform(data))  # 变换后的数据

四、详细说明

1.关于流形学习

LLE和下一篇将介绍的t-SNE等针对非线性数据的降维算法被统称为流形学习。流形指的是可以将局部看作没有弯曲的空间。类似地，地球虽然是球体，但是我们可以对地球的局部绘制平面地 图。简单来说， 只要理解“所谓的流形就是从局部来看是低维空间的结构被埋藏在高维空间里”就足够了。通过以 LLE为首的各种各样的流形学习算法，可以找到（在弯曲或扭曲的状态下）埋藏在高维空间中的低维的数据结构。

2.近邻点的数量

LLE 的近邻点数量需要被定义为超参数。在对上图所示的瑞士卷数据应用LLE时，将近邻点的数量分别设置为5和50，结果如下图所示。当近邻点的数量被设置为5时（图a），LLE没能取出连贯的结构，所以降维后的点的分布显得不是很宽，看上去聚集在一个狭窄的区域，这并不能反映太多的信息。当近邻点的数量被设置为50（图b）时，不同颜色的点离得很近。这是由于近邻点的数量太多，无法把握局部的结构。因为近邻点的数量对LLE结果影响较大，所以必须慎重设置。