LLE算法的基本原理
局部线性嵌入，英文名Locally Linear Embedding，简称LLE，是2000年由Roweis和Saul提出的一种流形学习算法。它的核心思想是：高维空间中的一个数据点，可以由它的近邻点通过线性组合近似重建，而这种局部线性关系在降维到低维空间后依然保持不变。换句话说，每个点与邻居之间的相对位置关系是数据的本质结构，LLE要做的就是保留这种结构。
与PCA这种全局线性降维方法不同，LLE能够处理非线性结构的数据。比如著名的瑞士卷数据集，它本质上是一个二维曲面被卷曲成了三维形状。用PCA降维会把卷曲的面压扁，导致不同区域的点混叠在一起；而LLE沿着流形表面展开数据，可以把瑞士卷漂亮地摊平成二维平面。这就是流形学习的价值所在。
LLE的完整流程分为三步：第一步是为每个样本点寻找K个最近邻；第二步是假设每个点可以由其近邻线性表示，求解使重建误差最小的权重系数；第三步是固定权重矩阵，寻找低维嵌入坐标，使得每个点在低维空间中仍然被同样的权重线性重建。前两步是局部的、每个点独立计算的，第三步是一个全局的稀疏矩阵特征值问题。
在Node.js中搭建数值计算环境
Node.js本身并不擅长数值计算，标准库里没有矩阵运算相关的API，所以需要借助第三方库。最常用的是ml-matrix和mathjs。ml-matrix提供了矩阵的SVD分解、特征值分解、逆矩阵求解等功能，性能优于mathjs，更适合科学计算场景。本文以ml-matrix为例。安装方式如下：
npm install ml-matrix
除了矩阵运算库，还需要一个K近邻搜索工具。当数据量不大时，可以直接暴力计算欧氏距离并排序，代码简单且结果准确。如果数据量达到数万以上，建议使用kd-tree库来加速近邻查询，比如kd-tree-js。下面是暴力搜索的实现，返回每个点的K个近邻索引：
const { Matrix } = require('ml-matrix');
// 暴力搜索K近邻，data是n行d列的二维数组
function knnSearch(data, k) {
const n = data.length;
const neighbors = [];
for (let i = 0; i < n; i++) {
const dists = [];
for (let j = 0; j < n; j++) {
if (i === j) continue;
let sum = 0;
for (let d = 0; d < data[i].length; d++) {
const diff = data[i][d] - data[j][d];
sum += diff * diff;
}
dists.push({ idx: j, dist: sum });
}
dists.sort((a, b) => a.dist - b.dist);
neighbors.push(dists.slice(0, k).map(o => o.idx));
}
return neighbors;
}
这里有一个细节需要注意：搜索近邻时排除了自身点，因为自身与自身的距离恒为零，若包含进来会导致权重矩阵构造出现退化。另外距离平方即可用于比较，不必开方，可以节省一次sqrt运算。
核心步骤一：求解重建权重矩阵
对于每个样本点xi，我们希望找到一组权重wij，使得xi约等于其K个近邻的加权和，同时权重满足两个约束：所有权重之和为1，且非近邻点的权重为0。这是一个带约束的最小二乘问题。当某个点的近邻数大于数据维度时，局部协方差矩阵可能奇异，常规做法是给它加上一个小的正则项，通常是单位矩阵乘以一个极小的正则化系数。
推导过程简述如下：设第i个点的局部协方差矩阵为C，重建误差可写为w的二次型w转置乘C乘w，在约束w元素之和为1下求最小值，解析解为C的逆矩阵乘以全1向量，再整体除以归一化常数。加上正则项后就是C加上reg乘单位矩阵再求逆。代码实现如下：
const { Matrix, SingularValueDecomposition } = require('ml-matrix');
// 计算重建权重矩阵W
function computeWeights(data, neighbors, reg = 1e-3) {
const n = data.length;
const k = neighbors[0].length;
const d = data[0].length;
// 用稀疏思路存储：每行只有k个非零权重
const W = new Array(n).fill(null);
for (let i = 0; i < n; i++) {
// 构建局部协方差矩阵C (k x k)
const C = new Matrix(k, k);
const xi = data[i];
for (let a = 0; a < k; a++) {
const na = data[neighbors[i][a]];
for (let b = 0; b < k; b++) {
const nb = data[neighbors[i][b]];
let sum = 0;
for (let t = 0; t < d; t++) {
sum += (xi[t] - na[t]) * (xi[t] - nb[t]);
}
C.set(a, b, sum);
}
}
// 正则化处理：对角线加reg，必要时按行列和缩放
let trace = 0;
for (let a = 0; a < k; a++) trace += C.get(a, a);
const scale = trace > 0 ? reg * trace / k : reg;
for (let a = 0; a < k; a++) {
C.set(a, a, C.get(a, a) + scale);
}
// 解 Cw = 1，然后归一化
const rhs = new Matrix(k, 1).fill(1);
const w = solveLinear(C, rhs);
let total = 0;
for (let a = 0; a < k; a++) total += w.get(a, 0);
const row = new Array(n).fill(0);
for (let a = 0; a < k; a++) {
row[neighbors[i][a]] = w.get(a, 0) / total;
}
W[i] = row;
}
return W;
}
// 利用SVD求解线性方程组，比直接求逆更稳定
function solveLinear(A, b) {
const svd = new SingularValueDecomposition(A, { autoTranspose: true });
const U = svd.leftSingularVectors;
const V = svd.rightSingularVectors;
const s = svd.diagonal;
const k = s.length;
const y = new Matrix(k, 1);
for (let i = 0; i < k; i++) {
let sum = 0;
for (let r = 0; r < b.rows; r++) sum += U.get(r, i) * b.get(r, 0);
y.set(i, 0, s[i] > 1e-10 ? sum / s[i] : 0);
}
const x = V.mmul(y);
return x;
}
这里用SVD求解线性方程组而不是直接求逆矩阵，是因为当协方差矩阵接近奇异时，直接求逆会产生数值爆炸，而基于SVD的伪逆方法会自动截断极小的奇异值，数值上稳定得多。这是实现LLE时最容易踩坑的地方之一，如果发现降维结果出现NaN，优先检查这一步。
核心步骤二：通过特征值分解得到低维嵌入
得到权重矩阵W后，需要寻找d维的低维坐标Y，使得Y与WY的重建误差最小，同时约束Y的列正交且协方差为单位矩阵以消除平凡解。这个约束优化问题可以转化为求解矩阵M的广义特征值问题，其中M等于单位矩阵减去W再减去W的转置加上W转置乘W。最小的一个特征值恒为0，对应全1向量，我们跳过它，取接下来最小的d个特征值所对应的特征向量作为嵌入坐标。
当数据量较大时，M是一个n乘n的稠密矩阵，完整特征分解的开销是O(n的三次方)。对于几百到几千个样本，ml-matrix的EVD可以接受；更大的数据建议先用近邻图做稀疏化，或改用随机化特征值算法。以下是嵌入求解代码：
const { Matrix, EigenvalueDecomposition } = require('ml-matrix');
// 根据权重矩阵计算低维嵌入
function embed(W, dim) {
const n = W.length;
// 构建W的Matrix形式
const Wm = new Matrix(W);
const I = Matrix.identity(n, n);
const Wt = Wm.transpose();
// M = (I - W转置)(I - W)
const M = I.clone().subtract(Wt).mmul(I.clone().subtract(Wm));
const evd = new EigenvalueDecomposition(M, { assumeSymmetric: true });
const values = evd.realEigenvalues;
const vectors = evd.eigenvectorMatrix;
// 找出除最小0特征值之外最小的dim个特征值的索引
const order = values
.map((v, i) => ({ v, i }))
.sort((a, b) => a.v - b.v)
.slice(1, dim + 1)
.map(o => o.i);
const Y = new Matrix(n, dim);
for (let c = 0; c < dim; c++) {
const col = vectors.getColumn(order[c]);
for (let r = 0; r < n; r++) {
Y.set(r, c, col[r]);
}
}
return Y;
}
最后把三个步骤串起来，就得到了完整的LLE函数：
function lle(data, k, dim, reg = 1e-3) {
const neighbors = knnSearch(data, k);
const W = computeWeights(data, neighbors, reg);
return embed(W, dim);
}
// 示例：对三维瑞士卷数据降到二维
const { makeSwissRoll } = require('./swissRoll');
const data = makeSwissRoll(500);
const Y = lle(data, 10, 2);
console.log('降维后维度:', Y.rows, 'x', Y.columns);
参数调优与常见问题
LLE最敏感的参数是近邻数K。K太小的时候，局部邻域无法覆盖流形的线性区域，重建权重的约束失效，嵌入结果会出现严重的撕裂和断裂；K太大的时候，邻域跨越了流形的弯曲部分，不同曲面的点被强行拉到一起，导致嵌入结果被压扁，丧失流形结构。经验上K取在10到30之间比较稳妥，实际使用时可以结合重构残差曲线来选择：画出不同K值下平均重建误差的变化，选择曲线进入平台的拐点附近。
正则化系数reg的默认值通常取0.001，当数据的维度远小于近邻数K，或者数据中存在重复点导致协方差矩阵奇异时，需要适当调大。如果某次运行抛出矩阵不可逆的异常，或者嵌入结果里出现NaN，第一时间应该检查数据中是否有完全重复的样本点，必要时先去重，再加大reg。
另一个实用建议是对原始数据做标准化预处理，把每个特征缩放到零均值单位方差，否则量纲大的特征会主导距离计算，导致近邻选取失真。对于Node.js的应用场景，LLE常见的落地方向包括：对前端采集的用户行为特征做可视化降维、对传感器时序数据做特征压缩后再聚类、以及在机器学习流水线中作为Node端推理前的预处理步骤。如果数据量上万，建议把近邻搜索换成kd-tree实现，并把特征值分解放到Worker线程中执行，避免阻塞事件循环。
本文给出的实现覆盖了LLE的完整数学流程，代码总量不足两百行，易于理解和改造。读者可以在此基础上增加距离度量选项（如曼哈顿距离、余弦距离），或者实现有监督版本Supervised LLE以支持分类任务的降维需求。