Locally Linear Embedding (LLE)

Locally Linear Embedding (LLE)

Locally Linear Embedding (LLE) 是一种非线性降维算法，通常用于高维数据的流形学习。其核心思想是：假设数据点在局部是线性结构，通过保留每个数据点的局部线性结构关系，将数据嵌入到低维空间中。这种方法特别适合处理非线性分布的数据集，例如流形或非平坦结构的数据。

LLE算法主要包括三个步骤：

1. 寻找最近邻点：对于每个数据点，找到其在高维空间中的最近邻居。
2. 构建线性重构权重矩阵：在保持局部结构的前提下，用邻居的线性组合来表示每个点。
3. 计算低维嵌入：在低维空间中重构各点的位置，确保局部重构关系不变。

import numpy as np
from sklearn.datasets import make_swiss_roll
from scipy.spatial import distance_matrix
import matplotlib.pyplot as plt

# 1. 生成数据集（使用Swiss Roll数据集）
X, color = make_swiss_roll(n_samples=1000, noise=0.2)

# 参数设置
n_neighbors = 10  # 每个点的最近邻个数
n_components = 2  # 降至的维度

# 2. 寻找每个点的最近邻
distances = distance_matrix(X, X)  # 计算距离矩阵
neighbors = np.argsort(distances, axis=1)[:, 1:n_neighbors+1]  # 排序后取前n_neighbors个

# 3. 计算重构权重矩阵
W = np.zeros((X.shape[0], X.shape[0]))  # 初始化权重矩阵

for i in range(X.shape[0]):
    Z = X[neighbors[i]] - X[i]  # 计算邻居相对位置
    C = np.dot(Z, Z.T)  # 计算协方差矩阵
    C += np.identity(n_neighbors) * 1e-3 * np.trace(C)  # 加入正则项以保证矩阵可逆
    
    w = np.linalg.solve(C, np.ones(n_neighbors))  # 求解线性方程
    w /= np.sum(w)  # 归一化权重
    W[i, neighbors[i]] = w  # 将权重填入矩阵

# 4. 计算嵌入的低维表示
M = np.eye(X.shape[0]) - W
M = np.dot(M.T, M)  # 构建矩阵 M

# 计算 M 的特征值和特征向量
eig_vals, eig_vecs = np.linalg.eig(M)
idx = np.argsort(eig_vals)[1:n_components+1]  # 选取最小的非零特征值对应的特征向量
Y = eig_vecs[:, idx].real  # 提取对应的特征向量

# 5. 绘图显示
plt.figure(figsize=(12, 6))

# 原始高维数据
ax = plt.subplot(121, projection='3d')
ax.scatter(X[:, 0], X[:, 1], X[:, 2], c=color, cmap=plt.cm.Spectral)
ax.set_title("Original 3D data (Swiss Roll)")

# 降维后的2D数据
plt.subplot(122)
plt.scatter(Y[:, 0], Y[:, 1], c=color, cmap=plt.cm.Spectral)
plt.title("2D representation after LLE")
plt.xlabel("LLE Component 1")
plt.ylabel("LLE Component 2")

plt.show()