谱聚类算法

第一章 简介

        谱聚类是一种基于图论和线性代数的聚类方法，它利用数据的相似性构造图结构，并通过谱分解（特征值分解）来进行聚类。相较于传统的 K-Means 方法，谱聚类能够更好地处理非凸形状的簇，尤其适用于高维、非线性可分的数据。
        谱聚类的发展经历了多个关键阶段，从早期的图划分问题到现代机器学习中的应用，主要包括以下几个方面：
1）图划分理论的起源
        谱聚类的思想起源于图割问题，研究如何将图划分为若干个连通性较强的子图。早期方法包括 最小割、均衡割和归一化割等。
2）线性代数方法的引入
        研究者发现，基于拉普拉斯矩阵的特征值分解可以有效解决图划分问题。Shi & Malik提出了基于归一化切割的谱聚类方法。Ng, Jordan & Weiss提出了基于无向图拉普拉斯矩阵的谱聚类方法，使谱聚类在机器学习领域成为主流算法之一。

第二章 图的概述

2.1 图的基本定义

在数学上，图是由顶点以及连接顶点的边构成，顶点表示研究对象，边表示两个对象之间的特定关系。图可以表示顶点和边的集合，记为 $G=(V,E)$，其中 $V$ 表示顶点的集合，$E$ 表示边集合。假设图 $G$ 的顶点个数为 n，边数为 m。一条连接顶点 $v_i，v_j\in V$ 的边，记为 $e_{ij}$。如图 2-1 所示， V = { v 1 ， v 2 ， v 3 ， v 4 } V=\{v_1，v_2，v_3，v_4\} V={v1​，v2​，v3​，v4​}， E = { e 12 ， e 23 ， e 13 ， e 24 } E=\{e_{12}，e_{23}，e_{13}，e_{24}\} E={e12​，e23​，e13​，e24​}。

2.1.1 图的类型

2.1.1.1 有向图和无向图

如果图中的边存在方向，则称边为有向边，记为 $e_{ij}=<v_i，v_j>$，其中 $v_i$ 是这条有向边的起点，$v_j$是这条有向边的终点，包含有向边的图称为有向图，如下图所示。与有向图对应的是无向图，无向图中的边都是无向边，即 $e_{ij}=e_{ji}$。

图 2-2 无向图

图 2-3 有向图

2.1.1.2 非加权图和加权图

若图中的每条边都有一个实数与之对应，我们称这样的图为加权图，如图 2-4所示，该实数称为对应边上的权重。在工程应用中，权重可以表示两地之间的距离或运输成本。一般情况下，我们习惯把权重看作两个顶点之间的连接强度。与之相反，非加权图上权重是一样的。

2.1.1.3 连通图与非连通图

若图中存在孤立的顶点，没有任何边与之相连，这样的图称为非连通图，反之称为连通图，如图2-5所示。

2.1.1.4 二部图

二部图是一类特殊的图。我们将图 $G$ 中的顶点集合 $V$ 划分为两个子集 $A$ 和 $B$，如果对图中的任意一条边 $e_{ij}$均有 $v_i\in A,v_j\in B$ 或者 $v_j\in A,v_i\in B$，则称图 $G$为二部图，如图2-6所示。

2.1.2 邻居和度

        如果存在一条边连接顶点 $v_i$ 和$v_j$ ，则称 $v_j$ 是 $v_i$ 的邻居，反之亦然。我们记 $v_i$ 的所有邻居为集合 $N(v_i)$，即 N ( v i ) = { v j ∣ ∃ e i j ∈ E 或 e j i ∈ E } N(v_i) = \{v_j| \exists e_{ij} \in E 或 e_{ji} \in E\} N(vi​)={vj​∣∃eij​∈E或eji​∈E} 以 $v_i$为端点的边的数目称为 $v_i$ 的度，记为 $\mathrm{deg}(v_i)$，即 $$\mathrm{deg}(v_i)=|N(v_i)|$$
        在图中，所有节点的度之和与边数存在如下关系：$$\sum _{v_i}\mathrm{deg}(v_i)=2|E|$$
在有向图中，我们同时定义出度和入度顶点的度数等于该顶点出度和入度之和。其中，顶点$v_i$ 的出度是以 $v_i$ 为起点的有向边的数目，顶点 $v_i$ 的入度是以 $v_i$ 为终点的有向边数目。

2.2 图的表示方法

        在图论中，邻接矩阵(Adjacency Matrix)和关联矩阵(Incidence Matrix)是两种常见的表示图结构的方法。它们分别用于描述顶点之间的连接关系和顶点与边之间的关系。
邻接矩阵与关联矩阵

2.2.1 邻接矩阵

邻接矩阵用于表示图中顶点之间的连接关系，适用于有向图和无向图。假设图 $G=(V，E)$是一个具有 n 个顶点的图，则邻接矩阵 A 是一个 n $\times$ n 的矩阵，其中，无向图与有向图的邻接矩阵为：
$$A_{ij}=\{\begin{array}{l}1，如果顶点v_i和v_j之间存在边\\ 0，否则\end{array}$$
注意：由于无向图的边没有方向性，因此邻接矩阵是对称矩阵，有向图的邻接矩阵一般不是对称矩阵。
        加权图的邻接矩阵为：
$$A_{ij}=\{\begin{array}{l}{w}_{ij}，如果顶点v_i和v_j之间存在边\\ 0，否则\end{array}$$
式中，$A_{ij}$ 表示 $v_i$ 到 $v_j$ 边的权重。

2.2.1 关联矩阵

关联矩阵用于描述顶点与边之间的关系，适用于有向图和无向图。假设图 $G=(V，E)$是一个具有 n 个顶点和 m 条边的图，则关联矩阵 B 是一个 n $\times$ m 的矩阵，其中，无向图的关联矩阵为：

$$B_{ij}=\{\begin{array}{l}1，如果顶点v_i是边e_j的一个端点\\ 0，否则\end{array}$$
        有向图的关联矩阵为：
$$B_{ij}=\{\begin{array}{l}1，如果顶点v_i是边e_j的起点\\ -1，如果顶点v_i是边e_j的终点\\ 0，否则\end{array}$$
         设无向图 $G=(V，E)$，其中边集编号为 $e_1，e_2，\cdots ，e_6$，对应的图结构、邻接矩阵和关联矩阵如下所示。

图 2-7 无向图

图 2-8 邻接矩阵

图 2-9 关联矩阵

第三章 偏微分方程数值解法

3.1 微分算子

图 3-1 微分几何解释

        微分算子几何解释如图 3-1 所示。当自变量由 $x_0$ 增加到 $x_0+\Delta x$ 时，函数增量 $\Delta y=f(x_0+\Delta x)-f(x_0)=RQ$，而微分则是在点 $P$ 处切线上与 $\Delta x$ 所对应的增量：
$$dy=f^{{}^{\prime }}(x_0)\Delta x=R{Q}^{{}^{\prime }}$$
并且
$$\underset{x\to x_0}{\lim }\frac{\Delta y-dy}{\Delta x}=\underset{x\to x_0}{\lim }\frac{Q^{{}^{\prime }}Q}{PR}=f^{{}^{\prime }}(x_0)\underset{x\to x_0}{\lim }\frac{Q^{{}^{\prime }}Q}{Q^{{}^{\prime }}R}$$
其中，
$$\underset{x\to x_0}{\lim }\frac{Q^{{}^{\prime }}Q}{Q^{{}^{\prime }}R}=\underset{x\to x_0}{\lim }\frac{QR-Q^{{}^{\prime }}R}{Q^{{}^{\prime }}R}=\underset{x\to x_0}{\lim }\frac{\Delta x\tan \alpha -\Delta x\tan \beta }{\Delta x\tan \beta }=\underset{x\to x_0}{\lim }\frac{\tan \alpha -\tan \beta }{\tan \beta }=\underset{x\to x_0}{\lim }\frac{\tan \alpha }{\tan \beta }-1=0$$
        若函数 $y=f(x)$ 在区间上每一点都可微，则称 $f$ 为该区间上的可微函数。函数 $f(x)$ 在区间上任一点 $x$ 处的微分记为：
$$dy=f^{{}^{\prime }}(x)\Delta x$$

3.1 Taylor公式

        多项式函数是各类函数中最简单的一种，用多项式逼近函数是近似计算和理论分析的一个重要内容。
        我们在学习导数和微分概念时已经知道，如果函数 $f$ 在点 $x_0$ 可导，则有
$$f(x)=f(x_0)+f^{{}^{\prime }}(x-x_0)+o(x-x_0)$$

3.2 导数的差分近似

        有限差分法求解微分方程的基本思想是用离散的、只含有限个未知量的差分方程去近似代替连续变量的微分方程和定解条件，并把相应的差分方程的解作为微分方程的定解问题的近似解。本节以常微分方程为例讨论导数的有限差分近似。
        对于函数 $y=f(x)$ ，利用 Taylor 展开有
$$f(x+h)=f(x)+h{f}^{{}^{\prime }}(x)+\frac{h^2}{2!}{f}^{{}^{\prime \prime }}(x)+\frac{h^3}{3!}{f}^{{}^{\prime \prime \prime }}(x)+\cdots \text{\hspace{1em}(2-1)}$$
$$f(x-h)=f(x)-h{f}^{{}^{\prime }}(x)+\frac{h^2}{2!}{f}^{{}^{\prime \prime }}(x)-\frac{h^3}{3!}{f}^{{}^{\prime \prime \prime }}(x)+\cdots \text{\hspace{1em}(2-2)}$$
通过上式，可得
$$\begin{gathered} f^{{}^{\prime }}(x)=\frac{f(x+h)-f(x)}{h}-\frac{h}{2!}{f}^{{}^{\prime \prime }}(x)-\frac{h^2}{3!}{f}^{{}^{\prime \prime \prime }}(x)+\cdots \\ {f}^{{}^{\prime }}(x)=\frac{f(x)-f(x-h)}{h}+\frac{h}{2!}{f}^{{}^{\prime \prime }}(x)-\frac{h^2}{3!}{f}^{{}^{\prime \prime \prime }}(x)+\cdots \end{gathered}$$
于是得到一阶导数的近似表达式
$$f^{{}^{\prime }}(x)=\frac{f(x+h)-f(x)}{h}+O(h)\text{\hspace{1em}(2-3)}$$
$$f^{{}^{\prime }}(x)=\frac{f(x)-f(x-h)}{h}+O(h)\text{\hspace{1em}(2-4)}$$
其中，$O(h)$ 为截断误差项，可分别表示为
$$O(h)=-\frac{h}{2}{f}^{{}^{\prime \prime }}(\xi )(x<\xi <x+h)和O(h)=\frac{h}{2}{f}^{{}^{\prime \prime }}(\xi )(x-h<\xi <x)$$
式(2-3)和式(2-4)分别称为 $f^{{}^{\prime }}(x)$ 的向前差分公式和向后差分公式，它们都具备一阶精度。为了获取具有更高精度的近似表达式，将式(2-1)和式(2-2)相减可得
$$f(x+h)-f(x-h)=2h{f}^{{}^{\prime }}(x)+\frac{2h^3}{3!}{f}^{{}^{\prime \prime \prime }}(x)+\cdots$$
于是，有
$$f^{{}^{\prime }}(x)=\frac{f(x+h)-f(x-h)}{2h}+O(h^2)\text{\hspace{1em}(2-5)}$$
其中，$O(h^2)$ 为截断误差项，可表示为
$$O(h)=-\frac{h^2}{6}{f}^{{}^{\prime \prime \prime }}(\xi )(x-h<\xi <x+h)$$
式(2-5)称为 $f^{{}^{\prime }}(x)$ 的中心差分公式，它具备二阶精度。 $f^{{}^{\prime }}(x)$ 的差分近似表达式的几何意义如下图所示。

        若将式(2.1)和式(2.2)相加，得
$$f(x+h)+f(x-h)=2f(x)+h^2{f}^{{}^{\prime \prime }}(x)+\frac{h^4}{12}{f}^{(4)}(x)+\cdots$$
于是，有
$$f^{{}^{\prime \prime }}(x)=\frac{f(x+h)-2f(x)+f(x-h)}{h^2}+O(h^2)$$
其中，$O(h^2)$ 为截断误差项，可表示为
$$O(h^2)=-\frac{h^2}{12}{f}^{(4)}(\xi )(x-h<\xi <x+h)$$

3.3 偏微分方程有限差分原理

        考虑区域 $\Omega$ 上的二维问题 $L[u(x，y)]=f(x,y)$，使其在 $\Omega$ 的边界 $\Gamma$ 上满足给定的边界条件，如下图所示，其中 $L$ 是微分算子，$u=u(x，y)$ 是未知函数。采用有限差分方法求解这个边界问题。

        与常微分方程的处理方法一样，其基本思想是将偏微分方程离散化，即用差商代替偏导数，把偏微分方程边值问题转换为代数方程问题，然后求解所得的代数方程组。
        在 $xOy$ 平面上作两组平行线，使得
$$x=x_i=il，y=y_j=jh(i，j=0，\pm 1，\pm 2，\cdots )$$
这样就得到矩形网络。其中，$l>0$ 和 $h>0$ 称为步长；网格线的交点称为结点，记为(i，j)。我们只关心属于 $\Omega =D+T$ 的结点，若两个结点沿着坐标轴方向只相差一个步长，则称这两个结点为相邻结点。若一个属于 $\Omega$ 结点，其它4个相邻结点都属于 $\Omega$ ，则称此结点为内点，若4个相邻结点中至少有一个不属于 $\Omega$ ，则称此结点为边界点。
        在上述构造的网格基础上，需要偏微分方程离散化，将偏导数以有限差商的形式表示。对变量 $x$ 的偏导数如下：
$$\begin{gathered} \frac{\partial u(x，y)}{\partial x}=\frac{u(x+\Delta x，y)-u(x，y)}{\Delta x}+O(\Delta x) \\ \frac{\partial u(x，y)}{\partial x}=\frac{u(x，y)-u(x-\Delta x，y)}{\Delta x}+O(\Delta x) \\ \frac{{\partial }^{2}u(x，y)}{\partial x^2}=\frac{u(x+\Delta x，y)-2u(x，y)+u(x-\Delta x，y)}{\Delta x^2}+O(\Delta x^2) \end{gathered}$$
以及对变量 $y$ 的偏导数
$$\begin{gathered} \frac{\partial u(x，y)}{\partial y}=\frac{u(x，y+\Delta y)-u(x，y)}{\Delta y}+O(\Delta y) \\ \frac{\partial u(x，y)}{\partial y}=\frac{u(x，y)-u(x，y-\Delta y)}{\Delta y}+O(\Delta y) \\ \frac{{\partial }^{2}u(x，y)}{\partial y^2}=\frac{u(x，y+\Delta y)-2u(x，y)+u(x，y-\Delta y)}{\Delta y^2}+O(\Delta y^2) \end{gathered}$$
        将空间点 $(i,j)$ 的变量记为 $u_{i,j}$ ，将空间点 $(i+1,j)$ 的变量记为 $u_{i+1,j}$ 等等，则可在 $x$ 方向上对点 $(i，j)$ 的邻域进行Taylor展开，得到
$$\begin{gathered} (\frac{\partial u}{\partial x}{)}_{i,j}=\frac{u_{i+1，j}-u_{i，j}}{l}+O(l) \\ (\frac{\partial u}{\partial x}{)}_{i,j}=\frac{u_{i，j}-u_{i-1，j}}{l}+O(l) \\ (\frac{\partial u}{\partial x}{)}_{i,j}=\frac{u_{i+1，j}-u_{i-1，j}}{2l}+O(l^2) \\ (\frac{{\partial }^{2}u}{\partial x^2}{)}_{i,j}=\frac{u_{i+1，j}-2u_{i，j}+u_{i-1，j}}{l^2}+O(l^2) \end{gathered}$$
同理可得微商 $\frac{\partial u}{\partial y}$，$\frac{{\partial }^{2}u}{\partial y^2}$。