【无监督聚类方法（一）】谱聚类（基于图论的聚类方法）

该文章主要整理自珠穆拉玛峰的文章《从拉普拉斯矩阵说到谱聚类》，添加了少部分个人理解的文字和公式推导

该文章同步发表于 github 和 github homepage

目录

• 1. 一堆基础概念
• 2. 拉普拉斯矩阵
• 3. 拉普拉斯矩阵的性质
• 4. 谱聚类
  • 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。单位矩阵以 I_n 表示；如果阶数可忽略，或可由前后文确定的话，也可简记为I（或者E）。 如下图所示，便是一些单位矩阵：

  

  单位矩阵中的第i列即为单位向量v_i，单位向量同时也是单位矩阵的特征向量，特征值皆为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. 拉普拉斯矩阵的性质

介绍拉普拉斯矩阵的性质之前，首先定义两个概念，如下：

1. 对于邻接矩阵，定义图中A子图与B子图之间所有边的权值之和如下：

其中，定义 w _ij为节点 i 到节点 j 的权值，如果两个节点不是相连的，权值为零

2. 与某结点邻接的所有边的权值和定义为该顶点的度d，多个d 形成一个度矩阵（对角阵）

拉普拉斯矩阵L具有如下性质：

• L 是对称半正定矩阵；

• L * v₁^→ = 0 * v₁^→，即 L 的最小特征值是 0，相应的特征向量是 v₁^→

  证明： L * v₁^→ = (D-W) * v₁^→ = 0 = 0 * v₁^→

  特征值和特征向量的定义：

  若数字λ和非零向量v^→满足

  

  则v^→为A的一个特征向量，λ是其对应的特征值

• L 有n个非负实特征值

  

• 对于任何一个属于实向量 f∈Rⁿ，有以下式子成立

  

  其中

  

  下面，来证明下上述结论，如下：

  

4. 谱聚类

4.1. 算法思想及优化目标

谱聚类本质上就是将聚类问题转换为图论问题

从图论的角度来说，聚类的问题就相当于一个图的分割问题。即给定一个图G = (V, E)，顶点集V表示各个样本，带权的边表示各个样本之间的相似度，谱聚类的目的便是要找到一种合理的分割图的方法，使得分割后形成若干个子图，连接不同子图的边的权重（相似度）尽可能低，同子图内的边的权重（相似度）尽可能高。物以类聚，人以群分，相似的在一块儿，不相似的彼此远离。

至于如何把图的顶点集分割/切割为不相交的子图有多种办法，如：

• cut/Ratio Cut

• Normalized Cut

• 不基于图，而是转换成SVD能解的问题

优化目标为：让被割掉各边的权值和最小

因为被砍掉的边的权值和越小，代表被它们连接的子图之间的相似度越小，隔得越远，而相似度低的子图正好可以从中一刀切断。

4.2. 构造Laplacian图

（1）先要构造相似度矩阵，任意两个对象x_i和x_j，其相似度基于高斯核函数（也称径向基函数核）计算相似度定义为：

距离越大，代表其相似度越小

相似度矩阵就是Laplacian图的邻接矩阵W

根据邻接矩阵W可以得到度矩阵

最后Laplacian矩阵为L=D-W

（2）子图A的指示向量如下：

4.3. 用Cut/Ratio Cut分割子图</a>

4.3.1. 优化目标

如何切割才能得到最优的结果呢？

要把图片分割为几个区域（或若干个组），要求是分割所得的 Cut 值最小，相当于那些被切断的边的权值之和最小

设 A₁, A₂, ..., A_k 为图的几个子集（它们没有交集） ，为了让分割的Cut 值最小，谱聚类便是要最小化下述目标函数：

但很多时候，最小化cut 通常会导致不好的分割。以分成2类为例，这个式子通常会将图分成了一个点和其余的n-1个点。如下图所示，很明显，最小化的smallest cut不是最好的cut，反而把{A、B、C、H}分为一边，{D、E、F、G}分为一边很可能就是最好的cut：

为了让每个类都有合理的大小，目标函数尽量让 A₁, A₂, ..., A_k 足够大。改进后的目标函数为：

其中| A _i |表示 A _i 组中包含的顶点数目

或者也可以将优化目标定义为最小化Ncut：

其中

4.3.2. 求解优化问题：最小化RatioCut与最小化 f'Lf 等价

现在来研究一下将图划分为两个子图A和A^-的问题

目标函数：

定义向量 f = (f₁, f2₂, ..., f_m ) ∈ R ⁿ，且

根据之前得到的拉普拉斯矩阵矩阵的性质，已知

现在把 f _i 的定义式代入上式，我们将得到一个非常有趣的结论！推导过程如下：

我们竟然从 f'Lf 推出了 RatioCut ，换句话说，拉普拉斯矩阵L 和我们要优化的目标函数RatioCut 有着密切的联系，于是我们的优化目标变成了：

补充知识

*1. 向量的乘法运算

*1.1. 向量内积（点积）

使用矩阵乘法并把（纵列）向量当作n×1 矩阵，点积还可以写为：

向量内积性质

向量内积的物理意义

向量内积的物理意义是，力通过位移做功

*1.2. 向量内积的用途

• 求两个非零向量的夹角

  

• 判断两个非零向量是否垂直

  

  简单的对应坐标相乘再求和，结果为0就垂直，否则就不垂直

*1.3. 向量外积

通过坐标进行外积的直接计算比较复杂，写成行列式的形式，再展开，方便记忆

向量外积的性质

向量外积的几何意义

再除以2的话，就是以 a，b 为边的三角形的面积

*1.4. 向量外积的用途

求与三角形面积相关的问题

---

参考资料：

(1) CSDN·珠穆拉玛峰《从拉普拉斯矩阵说到谱聚类》

(2) CSDN·鹅城惊喜师爷《【线性代数】向量的乘法运算》

(3) 行者无疆兮.csdn【图论】拉普拉斯矩阵（Laplacian matrix）