该文章主要整理自珠穆拉玛峰的文章《从拉普拉斯矩阵说到谱聚类》，添加了少部分个人理解的文字和公式推导
该文章同步发表于 github 和 github homepage
目录
- 一堆基础概念
- 拉普拉斯矩阵
- 拉普拉斯矩阵的性质
- 谱聚类
- 4.1. 算法思想及优化目标
- 4.2. 构造Laplacian图
- 4.3. 用Cut/Ratio Cut分割子图
- 4.3.1. 优化目标
- 4.3.2. 求解优化问题：最小化RatioCut与最小化 f'Lf 等价
- 补充知识
- *1. 向量的乘法运算
- *1.1. 向量内积（点积）
- *1.2. 向量内积的用途
- *1.3. 向量外积
- *1.4. 向量外积的用途
1. 一堆基础概念
-
单位矩阵
在矩阵中，n阶单位矩阵，是一个 nxn 的方形矩阵，其主对角线元素为1，其余元素为0。单位矩阵以 In 表示；如果阶数可忽略，或可由前后文确定的话，也可简记为I（或者E）。 如下图所示，便是一些单位矩阵：
单位矩阵中的第i列即为单位向量vi，单位向量同时也是单位矩阵的特征向量，特征值皆为1，因此这是唯一的特征值，且具有重数n。由此可见，单位矩阵的行列式为1，且迹数为n。
-
单位向量
向量空间中的单位向量就是长度为 1 的向量
两个单位向量的点积就是它们之间角度的余弦（因为它们的长度都是 1）：
补充知识——向量的乘法运算（见后文补充知识）
一个非零向量u→的正规化向量（即单位向量）u^就是平行于u→的单位向量，记作：
这里||u→||是u→的范数（长度）
-
正交与正交矩阵
正交是垂直这一直观概念的推广，若内积空间中两向量的内积（即点积）为0，则称它们是正交的，相当于这两向量垂直，换言之，如果能够定义向量间的夹角，则正交可以直观的理解为垂直
正交矩阵（orthogonal matrix）是一个元素为实数，而且行与列皆为正交的单位向量的方块矩阵（方块矩阵，或简称方阵，是行数及列数皆相同的矩阵）
2. 拉普拉斯矩阵
拉普拉斯矩阵（Laplacian matrix)），也称为基尔霍夫矩阵，是表示图的一种矩阵
给定一个有n个顶点的图 G=(V,E)，其拉普拉斯矩阵被定义为 L = D-A，D其中为图的度矩阵，A为图的邻接矩阵
例如给定下图G=(V,E)
把此“图”转换为邻接矩阵的形式，记为A（假设每条边的连接权重均为1）：
把W的每一列元素加起来得到N个数，然后把它们放在对角线上（其它地方都是零），组成一个N×N的对角矩阵，记为度矩阵D，如下图所示
根据拉普拉斯矩阵的定义L = D-A，可得拉普拉斯矩阵L 为：
显然，拉普拉斯矩阵都是对称
3. 拉普拉斯矩阵的性质
介绍拉普拉斯矩阵的性质之前，首先定义两个概念，如下：
- 对于邻接矩阵，定义图中A子图与B子图之间所有边的权值之和如下：
其中，定义 w ij为节点 i 到节点 j 的权值，如果两个节点不是相连的，权值为零
- 与某结点邻接的所有边的权值和定义为该顶点的度d，多个d 形成一个度矩阵（对角阵）
拉普拉斯矩阵L具有如下性质：
-
L 是对称半正定矩阵；
-
L * v1→ = 0 * v1→，即 L 的最小特征值是 0，相应的特征向量是 v1→
证明： L * v1→ = (D-W) * v1→ = 0 = 0 * v1→
特征值和特征向量的定义：
若数字λ和非零向量v→满足
则v→为A的一个特征向量，λ是其对应的特征值
-
L 有n个非负实特征值
-
对于任何一个属于实向量 f∈Rn，有以下式子成立
其中
下面，来证明下上述结论，如下：
4. 谱聚类
4.1. 算法思想及优化目标
谱聚类本质上就是将聚类问题转换为图论问题
从图论的角度来说，聚类的问题就相当于一个图的分割问题。即给定一个图G = (V, E)，顶点集V表示各个样本，带权的边表示各个样本之间的相似度，谱聚类的目的便是要找到一种合理的分割图的方法，使得分割后形成若干个子图，连接不同子图的边的权重（相似度）尽可能低，同子图内的边的权重（相似度）尽可能高。物以类聚，人以群分，相似的在一块儿，不相似的彼此远离。
至于如何把图的顶点集分割/切割为不相交的子图有多种办法，如：
cut/Ratio Cut
Normalized Cut
不基于图，而是转换成SVD能解的问题
优化目标为：让被割掉各边的权值和最小
因为被砍掉的边的权值和越小，代表被它们连接的子图之间的相似度越小，隔得越远，而相似度低的子图正好可以从中一刀切断。
4.2. 构造Laplacian图
（1）先要构造相似度矩阵，任意两个对象xi和xj，其相似度基于高斯核函数（也称径向基函数核）计算相似度定义为：
距离越大，代表其相似度越小
相似度矩阵就是Laplacian图的邻接矩阵W
根据邻接矩阵W可以得到度矩阵
最后Laplacian矩阵为L=D-W
（2）子图A的指示向量如下：
4.3. 用Cut/Ratio Cut分割子图</a>
4.3.1. 优化目标
如何切割才能得到最优的结果呢？
要把图片分割为几个区域（或若干个组），要求是分割所得的 Cut 值最小，相当于那些被切断的边的权值之和最小
设 A1, A2, ..., Ak 为图的几个子集（它们没有交集） ，为了让分割的Cut 值最小，谱聚类便是要最小化下述目标函数：
但很多时候，最小化cut 通常会导致不好的分割。以分成2类为例，这个式子通常会将图分成了一个点和其余的n-1个点。如下图所示，很明显，最小化的smallest cut不是最好的cut，反而把{A、B、C、H}分为一边，{D、E、F、G}分为一边很可能就是最好的cut：
为了让每个类都有合理的大小，目标函数尽量让 A1, A2, ..., Ak 足够大。改进后的目标函数为：
其中| A i |表示 A i 组中包含的顶点数目
或者也可以将优化目标定义为最小化Ncut：
其中
4.3.2. 求解优化问题：最小化RatioCut与最小化 f'Lf 等价
现在来研究一下将图划分为两个子图A和A-的问题
目标函数：
定义向量 f = (f1, f22, ..., fm ) ∈ R n，且
根据之前得到的拉普拉斯矩阵矩阵的性质，已知
现在把 f i 的定义式代入上式，我们将得到一个非常有趣的结论！推导过程如下：
我们竟然从 f'Lf 推出了 RatioCut ，换句话说，拉普拉斯矩阵L 和我们要优化的目标函数RatioCut 有着密切的联系，于是我们的优化目标变成了：
补充知识
*1. 向量的乘法运算
*1.1. 向量内积（点积）
使用矩阵乘法并把（纵列）向量当作n×1 矩阵，点积还可以写为：
向量内积性质
向量内积的物理意义
向量内积的物理意义是，力通过位移做功
*1.2. 向量内积的用途
-
求两个非零向量的夹角
-
判断两个非零向量是否垂直
简单的对应坐标相乘再求和，结果为0就垂直，否则就不垂直
*1.3. 向量外积
通过坐标进行外积的直接计算比较复杂，写成行列式的形式，再展开，方便记忆
向量外积的性质
向量外积的几何意义
再除以2的话，就是以 a，b 为边的三角形的面积
*1.4. 向量外积的用途
求与三角形面积相关的问题
参考资料：
网友评论