谱聚类：图论遇见聚类算法
谱聚类（Spectral Clustering）是一种基于图论的聚类算法。 它将数据点视为图中的节点，通过相似度构造边， 然后对图的拉普拉斯矩阵进行谱分解， 在低维谱空间中完成聚类。
谱聚类的最大优势是能够发现任意形状的簇（包括非凸簇）， 这是传统K-means等基于距离的算法难以做到的。
✦
23
谱聚类完整流程
从距离矩阵到拉普拉斯谱分解
谱聚类算法包含7个关键步骤：原始数据 →距离矩阵D →相似度矩阵S →无向图G →拉普拉斯矩阵L →特征值分解 →聚类结果。 每一步都将数据的结构信息进一步提炼。
🔑 算法核心思想
1. 图的视角
将聚类问题转化为图分割问题。 相似的点在图中通过高权重边连接， 聚类等价于切断低权重边。
2. 谱的视角
拉普拉斯矩阵的特征向量编码了图的结构。 低频特征向量（小特征值对应）揭示了簇的边界。
3. 降维的视角
特征向量构成新的特征空间。 在这个低维空间中，原本复杂的簇结构变得简单， 易于用传统方法（如K-means）分离。
4. 连通性的视角
通过图的连通性而非欧氏距离判断相似性。 即使两点距离较远，只要通过高相似度路径连接， 也可能被聚为一类。
✦
算法细节解析
📏 距离 → 相似度
欧氏距离
dij = ||xi - xj||2
计算所有点对之间的距离
高斯核函数
sij = exp(-dij² / 2σ²)
距离越近，相似度越高（→1）
距离越远，相似度越低（→0）
距离越远，相似度越低（→0）
🔄 图 → 拉普拉斯矩阵
度矩阵 G
G = diag(S · 1)
对角矩阵，G[i][i] = Σ sij
归一化拉普拉斯
L = G-1/2(G - S)G-1/2
= I - G-1/2SG-1/2
归一化消除度数不平衡
归一化消除度数不平衡
✨ 特征值分解：揭示图的谱结构 ✨
特征值 λ
• λ₁ = 0（最小）
• λ₂ 代数连通度
• 特征值越小，对应簇的信息越强
特征向量 v
• v₁ 常向量 [1,1,...,1]
• v₂ Fiedler向量
• 取前k个特征向量投影
聚类
• 在谱空间中用K-means
• 簇的边界变得线性可分
• 原空间非凸 → 谱空间凸
✦
本章小结
本章介绍了谱聚类（Spectral Clustering）， 一种基于图论的强大聚类算法。 它将聚类问题转化为图分割问题， 通过拉普拉斯矩阵的谱分解揭示数据的簇结构。
🔄 算法流程回顾
1
计算距离矩阵D
欧氏距离 d_ij
2
构造相似度矩阵S
高斯核 s_ij = exp(-d²/2σ²)
3
绘制无向图G
S作为邻接矩阵
4
计算度矩阵G
G = diag(S·1)
5
拉普拉斯矩阵L
L = G^(-1/2)(G-S)G^(-1/2)
6
特征值分解
L = VΛV^(-1)
7
聚类
在谱空间中用K-means
💡 关键洞察
图论视角
聚类 = 图分割，切断低权重边
谱分析视角
特征向量编码图结构，低频特征向量揭示簇
降维视角
谱空间中非凸簇变凸，简化聚类任务
连通性视角
基于图连接而非欧氏距离，发现任意形状簇
🌉 图论 + 线性代数 + 聚类 = 谱聚类 🌉
将三大数学工具完美融合
图论
节点、边、连通性
线性代数
拉普拉斯矩阵、特征分解
机器学习
无监督学习、聚类
谱聚类：能发现任意形状簇的强大算法