LLE 及其改进算法介绍 Locally linear embedding (LLE) (Sam T.Roweis and Lawrence K.Saul, 2000)以及Supervised locally linear embedding (SLLE) (Dick and Robert, 2002) 是最近提出的非线性降维方法，它能够使降维后的数据保持原有拓扑结构。 LLE 算法可以有图 1 所示的一个例子来描述。在图 1 所示中，LLE 能成功地将三维非线性数据映射到二维空间中。如果把图 1（B）中红颜色和蓝颜色的数据分别看成是分布在三维空间中的两类数据，通过 LLE 算法降维后，则数据在二维空间中仍能保持相对独立的两类。在图 1（B）中的黑色小圈中可以看出，如果将黑色小圈中的数据映射到二维空间中，如图 1（C）中的黑色小圈所示，映射后的数据任能保持原有的数据流形，这说明 LLE 算法确实能保持流形的领域不变性。由此 LLE 算法可以应用于样本的聚类。而线性方法，如 PCA 和 MDS，都不能与它比拟的。 LLE 算法操作简单，且算法中的优化不涉及到局部最小化。该算法能解决非线性映射，但是，当处理数据的维数过大，数量过多，涉及到的稀疏矩阵过大，不易于处理。在图 1 中的球形面中，当缺少北极面时，应用 LLE算法则能很好的将其映射到二维空间中，如图 1 中的C 所示。如果数据分布在整个封闭的球面上，LLE 则不能将它映射到二维空间，且不能保持原有的数据流形。那么我们在处理数据中，首先假设数据不是分布在闭合的球面或者椭球面上。 图1 非线性降维实例：B 是从A 中提取的样本点（三维），通过非线性降维 算法（LLE），将数据映射到二维空间中（C）。从C 图中的颜色可以看出 通过LLE 算法处理后的数据，能很好的保持原有数据的邻域特性 LLE 算法是最近提出的针对非线性数据的一种新的降维方法，处理后的低维数据均能够保持原有的拓扑关系。它已经广泛应用于图像数据的分类与聚类、文字识别、多维数据的可视化、以及生物信息学等领域中。 1 LLE 算法 LLE 算法可以归结为三步: (1)寻找每个样本点的k 个近邻点；（2）由每个样本点的近邻点计算出该样本点的局部重建权值矩阵；（3）由该样本点的局部重建权值矩阵和其近邻点计算出该样本点的输出值。具体的算法流程如图2所示。 图2 LLE 算法流程 算法的第一步是计算出每个样本点的k 个近邻点。把相对于所求样本点距离最近的k 个样本点规定为所求样本点的 个近邻点。k 是一个预先给定值。Sam T.Roweis 和 Lawrence K.Saul 算法采...
