【学习】谱聚类

我的很多关于机器学习的想法都源于量子力学微扰理论(Quantum Mechanical Perturbation Theory)，因此在介绍它们之前，我们有必要先回顾一下机器学习中的相关概念。例如机器学习中的谱聚类技术，本质上与量子力学光谱学是一致的。同往常一样，我会用几篇博客来阐述这个话题。

或许不久， 我将会对这部分内容重写，在其中加入对 Robust andScalable Graph-Based Semisupervised Learning http://www.ee.columbia.edu/ln/dvmm/publications/12/IEEE_Semisupervise.pdf 这一文章的的综述。 

谱聚类（又称子空间聚类）

谱聚类作为一种聚类方法，目的是聚类空间分布上连通（connected）， 但并不要求数据具有紧密聚集（compact）或者具有凸边界的聚集（clustered）的特征。

基本思想如下:

1.   将数据映射到n维空间

2.   定义关联矩阵（affinity matrix）A , 可以使用高斯核 K， 或直接使用邻接矩阵(例如， Aij = δij )

3.   基于邻接矩阵A， 构造图拉普拉斯算子(例如， 是否要选择归一化)

4.   求解特征值问题 ， 例如Lv = λv  (或广义特征值问题Lv = λDv )

5.    选择最小（或最大）的k个特征值（λ 1...k）所对应的特征向量 （v 1...k） , 从而定义出k维的子空间P^T L P

6.   在这个k维子空间上进行聚类，例如使用k-means算法

原文链接：

http://mp.weixin.qq.com/s/IO0sCrCCwi1TXtIyQEVY9w