谱聚类：用拉普拉斯特征向量聚类，非凸形状自动展开

相似图：k-NN + RBF亲和度

将点云转化为加权图。每个点只连接到它的k个最近邻点——这样不同月牙上相距遥远的点永远不会直接连接——并用RBF核对每条保留的边进行加权，距离近=强，距离远=弱。对称化使亲和矩阵W对称。

const w = Math.exp(-d2(pts[i], pts[j]) / (2 * sigma * sigma));  // RBF affinity
W[i][j] = W[j][i] = Math.max(W[i][j], w);                       // kNN, symmetric

Laplacian L = D − W

度数Dᵢ是节点i处的总边权。非归一化Laplacian是L = D − W；演示使用归一化对称形式L_sym = I − D^-½ W D^-½（Ng–Jordan–Weiss选择），它平衡了不同密度的聚类。其特征值位于[0, 2]，特征值0的重数等于连通分量的个数。

L[i][j] = (i === j ? 1 : 0) - dinv[i] * W[i][j] * dinv[j];   // I − D^-½ W D^-½

最小特征向量嵌入点

整个方法依赖于最小特征值的特征向量。对于对称矩阵，经典的Jacobi旋转可以在没有库的情况下找到所有特征向量——反复用平面旋转Gᵀ L G将最大的非对角元素清零，累加到V中，当非对角元素消失时，对角线上是特征值，V的列是特征向量。将k个最小的特征向量作为列堆叠：第i行是点i的新坐标。将每一行归一化为单位长度，纠缠的形状就会坍缩成紧凑、分离良好的块。

const T = pts.map((_, i) => {                 // row i = point i in spectral space
  const row = vectors.slice(0, k).map(v => v[i]);
  const nrm = Math.hypot(...row) || 1;
  return row.map(v => v / nrm);               // NJW row-normalize -> onto a sphere
});

谱空间中的k-means和特征间隙选择k

在谱空间中运行普通的k-means，那个在原始坐标上失败的非凸混乱现在变得平凡地可分离——这个嵌入就是整个技巧的可视化。你不必猜测聚类数：有c个近似分离片段的图有c个接近零的特征值，所以最大的特征间隙——第k个最小特征值后的跳跃——投票选择k。特征向量#1是Fiedler向量，仅其符号就在任何k-means运行之前将图分成两部分。

const gaps = eig.slice(1).map((v, i) => v - eig[i]);   // λ_{i+1} − λ_i
const k = gaps.indexOf(Math.max(...gaps)) + 1;         // biggest jump = cluster count

在两月牙和同心圆数据集上，谱聚类达到~100%的准确率，而原始k-means接近随机；切换到凸形斑点，两者打成平手——谱聚类的优势仅在聚类不是圆形的地方显现，这正是你想要的合理性检验。这里的密集Jacobi求解器是O(n³)的，这就是演示保持N较小的原因；在生产中，你使用稀疏k-NN图和Lanczos/ARPACK求解器，它只返回少数几个最小特征向量——正是sklearn.cluster.SpectralClustering幕后所做的。

我现在要记住的是：当聚类不是圆形斑点时，停止测量到质心的距离——构建一个相似图，让Laplacian的谱为你展开形状。

选择两个月牙，看谱聚类以~100%的准确率精确命中它们，而k-means则从中间切开：https://dev48v.infy.uk/ml/day49-spectral-clustering.html

如需进一步操作，你可能会考虑屏蔽此人和/或举报滥用

普通k-means将每个点分配给最近的质心，所以两个聚类之间的边界总是一条直线——它能完美拟合凸形斑点。但真实结构往往是非凸的：两个交错的月牙形，一个圆环套着另一个圆环。没有任何质心集合能将它们分开，所以k-means（和GMM的椭圆）直接从中间切一刀，得到很坏的结果。谱聚类完全规避了几何——它将数据转化为图，从图Laplacian的特征向量中读出答案。我构建了一个演示，在浏览器中实时运行整个流程。以下是我学到的内容。