谱聚类方法推导和对拉普拉斯矩阵的理解

谱聚类可以看作是基于图的一种聚类方法，在各大论坛有许多介绍谱聚类算法的博客，但是在看的过程中，总是会存在各种各样的困惑，尤其是拉普拉斯矩阵的引入等一些列问题上介绍的不是很清楚。这里基于 Ncut 文章中的推导，给出谱聚类算法的一个整体的推导过程和一些重要细节。

首先有必要简单介绍一些图的基本知识，为了尽可能的简单，我们仅仅介绍必要的概念：

其中红色数字表示节点的标号，图中的每一行和每一列是对称的，他们都反映了该节点与其他节点的连接情况。

度：

定义顶点的度为该顶点与其他顶点连接权值之和：

度矩阵 D 为对角矩阵，上面图对对应的度矩阵为：

子图和子图的连接权

我们可以将上面的图划分成两个子图，如下图所示：

定义 A 和 B 是图G

中两个不相交的子图，则定义子图的连接权值:

对于上面的图，我们希望通过一种最优的划分将其分为两个部分，实际上 A 和B

两个子图的划分就是一种最优的划分：

我们定义这样的划分满足

聚类的定义： 聚类就是对大量未知标注的数据集，按数据的内在相似性将数据划分成多个类别，使得类别内数据相似度较大而类别间的数据相似度较小。

Normalized cut