在机器学习领域，经常遇到具有成千上万甚至数百万特征的数据集。这些特征使得训练过程变得非常缓慢。此外，高维空间中存在大量的空间，使得高维数据集变得非常稀疏，因为大多数训练实例很可能彼此相距甚远。这增加了过拟合的风险，因为预测将基于比低维数据更大的外推。这种现象被称为“维度的诅咒”。
流形是一个可以在更高维空间中通过扭曲或弯曲来适应的二维形状，这是从广义上说的。流形假设指出，现实世界中的高维数据位于嵌入在高维空间中的低维流形上。简而言之，这意味着更高维的数据大多数时间位于一个更接近的低维流形上。建模训练实例所在的流形的过程被称为流形学习。
局部线性嵌入（LLE）是一种用于非线性降维的流形学习技术。它是一种无监督学习算法，可以产生高维输入的低维嵌入，将每个训练实例与其最近的邻居联系起来。
对于每个训练实例x(i)，算法首先找到其k个最近邻居，然后尝试将x(i)表示为它们的线性函数。一般来说，如果有m个训练实例，那么它试图找到一组权重w，这些权重最小化了x(i)与其线性表示之间的平方距离。
因此，代价函数由下式给出：
minimize ||x(i) - Σ w(i,j) * x(j)||^2
其中w(i,j) = 0，如果j不是i的k个最近邻居之一。此外，它还对每个训练实例x(i)的权重进行归一化。
最后，每个高维训练实例x(i)被映射到一个低维（比如说d维）向量y(i)，同时保持邻域关系。这是通过选择d维坐标来完成的，这些坐标最小化了代价函数。这里，权重w被固定，同时试图找到最优坐标y(i)。
以下是使用scikit-learn的LocallyLinearEmbedding类实现LLE的代码：
from sklearn.manifold import LocallyLinearEmbedding
lle = LocallyLinearEmbedding(n_neighbors=5, n_components=2)
#X_transformed = lle.fit_transform(X)
X_transformed = lle.fit_transform(X)
现在，将比较LLE与PCA和t-SNE在瑞士卷数据集上的表现。
from collections import OrderedDict
from functools import partial
from time import time
import matplotlib.pyplot as plt
from mpl_toolkits.mplot3d import Axes3D
from matplotlib.ticker import NullFormatter
from sklearn import manifold, datasets
from sklearn.decomposition import PCA
# 导入所需的库
Axes3D
# 然后加载瑞士卷数据集
n_points = 1000
X, color = datasets.make_swiss_roll(n_points, random_state=0)
n_neighbors = 10
n_components = 2
# 创建图表
fig = plt.figure(figsize=(15, 8))
fig.suptitle("Manifold Learning with %i points, %i neighbors"
% (1000, n_neighbors), fontsize=14)
# 添加3D散点图
ax = fig.add_subplot(231, projection='3d')
ax.scatter(X[:, 0], X[:, 1], X[:, 2], c=color, cmap=plt.cm.Spectral)
ax.view_init(4, -72)
# 创建包含LLE、t-SNE和PCA的字典'methods'
LLE = partial(manifold.LocallyLinearEmbedding,
n_neighbors, n_components, eigen_solver='auto')
methods = OrderedDict()
methods['LLE'] = LLE(method='standard')
methods['t-SNE'] = manifold.TSNE(n_components=n_components, init='pca',
random_state=0)
methods['PCA']=PCA(n_components=2)
# 绘制结果
for i, (label, method) in enumerate(methods.items()):
t0 = time()
Y = method.fit_transform(X)
t1 = time()
print("%s: %.2g sec" % (label, t1 - t0))
ax = fig.add_subplot(2, 3, 2 + i+(i>1))
ax.scatter(Y[:, 0], Y[:, 1], c=color, cmap=plt.cm.Spectral)
ax.set_title("%s (%.2g sec)" % (label, t1 - t0))
ax.xaxis.set_major_formatter(NullFormatter())
ax.yaxis.set_major_formatter(NullFormatter())
ax.axis('tight')
plt.show()
本文介绍了流形学习的概念，并讨论了其技术之一——局部线性嵌入（LLE）。然后看到了它的Python实现，并比较了LLE与t-SNE和PCA在瑞士卷数据集上的表现。
Roweis, S. T., & Saul, L. K. (2000). Nonlinear dimensionality reduction by locally linear embedding. Science (New York, N.Y.), 290(5500), 2323–2326.
Manifold Hypothesis Definition | Deep AI