Question

1. 谱聚类spectral clustering 是一种基于图论的聚类方法。

2. 谱聚类的主要思想是：基于数据集 $ MathJax-Element-544 $ 来构建图 $ MathJax-Element-555 $ ，其中：

   • 顶点 $ MathJax-Element-556 $ ：由数据集中的数据点组成： $ MathJax-Element-576 $ 。

   • 边 $ MathJax-Element-557 $ ：任意一对顶点之间存在边。

     距离越近的一对顶点，边的权重越高；距离越远的一对顶点，边的权重越低。

   通过对图 $ MathJax-Element-558 $ 进行切割，使得切割之后：不同子图之间的边的权重尽可能的低、各子图内的边的权重尽可能的高。这样就完成了聚类。

   

5.1 邻接矩阵

1. 在图 $ MathJax-Element-555 $ 中，定义权重 $ MathJax-Element-586 $ 为顶点 $ MathJax-Element-612 $ 和 $ MathJax-Element-615 $ 之间的权重，其中 $ MathJax-Element-619 $ 。

   定义 $ MathJax-Element-590 $ 为邻接矩阵：

   $ \mathbf W=\begin{bmatrix} w_{1,1}&w_{1,2}&\cdots&w_{1,N}\\ w_{2,1}&w_{2,2}&\cdots&w_{2,N}\\ \vdots&\vdots&\ddots&\vdots\\ w_{N,1}&w_{N,2}&\cdots&w_{N,N} \end{bmatrix} $

   由于 $ MathJax-Element-558 $ 为无向图，因此 $ MathJax-Element-591 $ 。即： $ MathJax-Element-592 $ 。

   • 对图中顶点 $ MathJax-Element-612 $ ，定义它的度 $ MathJax-Element-190 $ 为：所有与顶点 $ MathJax-Element-612 $ 相连的边的权重之和： $ MathJax-Element-595 $ 。

     定义度矩阵 $ MathJax-Element-596 $ 为一个对角矩阵，其中对角线分别为各顶点的度：

     $ \mathbf D=\begin{bmatrix} d_1&0&\cdots&0\\ 0&d_2&\cdots&0\\ \vdots&\vdots&\ddots&\vdots\\ 0&0&\cdots&d_N\\ \end{bmatrix} $

   • 对于顶点集合 $ MathJax-Element-556 $ 的一个子集 $ MathJax-Element-597 $ ，定义 $ MathJax-Element-598 $ 为子集 $ MathJax-Element-601 $ 中点的个数；定义 $ MathJax-Element-624 $ ，为子集 $ MathJax-Element-601 $ 中所有点的度之和。

2. 事实上在谱聚类中，通常只给定数据集 $ MathJax-Element-544 $ ，因此需要计算出邻接矩阵 $ MathJax-Element-609 $ 。

   • 基本思想是：距离较近的一对点（即相似都较高），边的权重较高；距离较远的一对点（即相似度较低），边的权重较低。

   • 基本方法是：首先构建相似度矩阵 $ MathJax-Element-603 $ ，然后使用 $ MathJax-Element-397 $ -近邻法、 $ MathJax-Element-554 $ 近邻法、或者全连接法。

     $ \mathbf S=\begin{bmatrix} s_{1,1}&s_{1,2}&\cdots&s_{1,N}\\ s_{2,1}&s_{2,2}&\cdots&s_{2,N}\\ \vdots&\vdots&\ddots&\vdots\\ s_{N,1}&s_{N,2}&\cdots&s_{N,N} \end{bmatrix} $
     • 通常相似度采用高斯核： $ MathJax-Element-763 $ 。此时有 $ MathJax-Element-605 $ 。即： $ MathJax-Element-606 $ 。
     • 也可以选择不同的核函数，如：多项式核函数、高斯核函数、sigmoid 核函数。

3. $ MathJax-Element-397 $ -近邻法：设置一个距离阈值 $ MathJax-Element-397 $ ，定义邻接矩阵 $ MathJax-Element-609 $ 为：

   $ w_{i,j}=\begin{cases} 0, & s_{i,j} \gt \varepsilon\\ \varepsilon , & s_{i,j} \le \varepsilon \end{cases} $

   即：一对相似度小于 $ MathJax-Element-397 $ 的点，边的权重为 $ MathJax-Element-397 $ ；否则边的权重为 0 。

   $ MathJax-Element-397 $ -近邻法得到的权重要么是 0 ，要么是 $ MathJax-Element-397 $ ，权重度量很不精确，因此实际应用较少。

4. $ MathJax-Element-554 $ 近邻法：利用 KNN 算法选择每个样本最近的 $ MathJax-Element-554 $ 个点作为近邻，其它点与当前点之间的边的权重为 0 。

   这种做法会导致邻接矩阵 $ MathJax-Element-609 $ 非对称，因为当 $ MathJax-Element-367 $ 是 $ MathJax-Element-523 $ 的 $ MathJax-Element-554 $ 近邻时， $ MathJax-Element-523 $ 不一定是 $ MathJax-Element-367 $ 的 $ MathJax-Element-554 $ 近邻。

   为了解决对称性问题，有两种做法：

   • 只要一个点在另一个点的 $ MathJax-Element-554 $ 近邻中，则认为是近邻。即：取并集。

     $ w_{i,j}=w_{j,i}=\begin{cases} 0,&\mathbf{\vec x}_i \notin KNN(\mathbf{\vec x}_j) \;\text{and}\;\mathbf{\vec x}_j \notin KNN(\mathbf{\vec x}_i) \\ s_{i,j},&\mathbf{\vec x}_i \in KNN(\mathbf{\vec x}_j) \;\text{or}\;\mathbf{\vec x}_j \in KNN(\mathbf{\vec x}_i) \end{cases} $

   • 只有两个点互为对方的 $ MathJax-Element-554 $ 近邻中，则认为是近邻。即：取交集。

     $ w_{i,j}=w_{j,i}=\begin{cases} 0,&\mathbf{\vec x}_i \notin KNN(\mathbf{\vec x}_j) \;\text{or}\;\mathbf{\vec x}_j \notin KNN(\mathbf{\vec x}_i) \\ s_{i,j},&\mathbf{\vec x}_i \in KNN(\mathbf{\vec x}_j) \;\text{and}\;\mathbf{\vec x}_j \in KNN(\mathbf{\vec x}_i) \end{cases} $

5. 全连接法：所有点之间的权重都大于 0 ： $ MathJax-Element-781 $ 。

5.2 拉普拉斯矩阵

1. 定义拉普拉斯矩阵 $ MathJax-Element-632 $ ，其中 $ MathJax-Element-596 $ 为度矩阵、 $ MathJax-Element-609 $ 为邻接矩阵。

2. 拉普拉斯矩阵 $ MathJax-Element-640 $ 的性质：

   • $ MathJax-Element-640 $ 是对称矩阵，即 $ MathJax-Element-635 $ 。这是因为 $ MathJax-Element-636 $ 都是对称矩阵。

   • 因为 $ MathJax-Element-640 $ 是实对称矩阵，因此它的特征值都是实数。

   • 对任意向量 $ MathJax-Element-638 $ ，有： $ MathJax-Element-639 $ 。

   • $ MathJax-Element-640 $ 是半正定的，且对应的 $ MathJax-Element-400 $ 个特征值都大于等于0，且最小的特征值为 0。

     设其 $ MathJax-Element-400 $ 个实特征值从小到大为 $ MathJax-Element-641 $ ，即： $ MathJax-Element-642 $ 。

5.3 谱聚类算法

1. 给定无向图 $ MathJax-Element-555 $ ，设子图的点的集合 $ MathJax-Element-601 $ 和子图的点的集合 $ MathJax-Element-647 $ 都是 $ MathJax-Element-556 $ 的子集，且 $ MathJax-Element-644 $ 。

   定义 $ MathJax-Element-601 $ 和 $ MathJax-Element-647 $ 之间的切图权重为： $ MathJax-Element-658 $ 。

   即：所有连接 $ MathJax-Element-601 $ 和 $ MathJax-Element-647 $ 之间的边的权重。

2. 对于无向图 $ MathJax-Element-555 $ ，假设将它切分为 $ MathJax-Element-306 $ 个子图：每个子图的点的集合为 $ MathJax-Element-648 $ ，满足 $ MathJax-Element-649 $ 且 $ MathJax-Element-650 $ 。

   定义切图cut 为： $ MathJax-Element-651 $ ，其中 $ MathJax-Element-652 $ 为 $ MathJax-Element-653 $ 的补集。

5.3.1 最小切图

1. 引入指示向量 $ MathJax-Element-663 $ ，定义：

   $ q_{j,i}=\begin{cases} 0,& i \not \in \mathbb A_j\\ 1,& i \in\mathbb A_j \end{cases} $

   则有：

   $ \mathbf{\vec q}_j^T\mathbf L\mathbf{\vec q}_j=\frac 12 \sum_{m=1}^N\sum_{n=1}^N w_{m,n}(q_{j,m}-q_{j,n})^2\\ =\frac 12 \sum_{m\in \mathbb A_j}\sum_{n\in \mathbb A_j} w_{m,n}(1-1)^2+ \frac 12 \sum_{m\not\in \mathbb A_j}\sum_{n\not\in \mathbb A_j} w_{m,n}(0-0)^2+\\ \frac 12 \sum_{m\in \mathbb A_j}\sum_{n\not\in \mathbb A_j} w_{m,n}(1-0)^2+\frac 12 \sum_{m\not\in \mathbb A_j}\sum_{n\in \mathbb A_j} w_{m,n}(0-1)^2\\ =\frac 12\left(\sum_{m\in \mathbb A_j}\sum_{n\not\in \mathbb A_j} w_{m,n}+\sum_{m\not\in \mathbb A_j}\sum_{n\in \mathbb A_j} w_{m,n}\right)\\ =\frac 12(cut(\mathbb A_j,\bar{\mathbb A}_j)+cut(\bar{\mathbb A}_j,\mathbb A_j))=cut(\mathbb A_j,\bar{\mathbb A}_j) $

   因此 $ MathJax-Element-664 $ 。其中 $ MathJax-Element-665 $ ， $ MathJax-Element-666 $ 为矩阵的迹。

   考虑到顶点 $ MathJax-Element-612 $ 有且仅位于一个子图中，则有约束条件：

   $ q_{j,m}\in \{0,1\},\quad \mathbf{\vec q}_i\cdot\mathbf{\vec q}_j=\begin{cases} 0,&i\ne j\\ |\mathbb A|_j,&i = j \end{cases} $

2. 最小切图算法： $ MathJax-Element-667 $ 最小的切分。即求解：

   $ \min_{\mathbf Q} tr(\mathbf Q^T\mathbf L\mathbf Q)\\ s.t. q_{j,m}\in \{0,1\},\quad \mathbf{\vec q}_i\cdot\mathbf{\vec q}_j=\begin{cases} 0,&i\ne j\\ |\mathbb A|_j,&i = j \end{cases} $

3. 最小切图切分使得不同子图之间的边的权重尽可能的低，但是容易产生分割出只包含几个顶点的较小子图的歪斜分割现象。

   

5.3.2 RatioCut 算法

1. RatioCut 切图不仅考虑最小化 $ MathJax-Element-667 $ ，它还考虑最大化每个子图的点的个数。即：

   $ RatioCut(\mathbb A_1,\cdots,\mathbb A_k)= \sum_{i=1}^k\frac{W(\mathbb A_i,\bar{\mathbb A}_i)}{|\mathbb A_i|} $
   • 最小化 $ MathJax-Element-667 $ ：使得不同子图之间的边的权重尽可能的低。
   • 最大化每个子图的点的个数：使得各子图尽可能的大。

2. 引入指示向量 $ MathJax-Element-677 $ ，定义：

   $ h_{j,i}=\begin{cases} 0,& i \not \in \mathbb A_j\\ \frac{1}{\sqrt{|\mathbb A_j|}},& i \in\mathbb A_j \end{cases} $

   则有：

   $ \mathbf{\vec h}_j^T\mathbf L\mathbf{\vec h}_j=\frac 12 \sum_{m=1}^N\sum_{n=1}^N w_{m,n}(h_{j,m}-h_{j,n})^2\\ =\frac 12 \sum_{m\in \mathbb A_j}\sum_{n\not\in \mathbb A_j} w_{m,n}(\frac{1}{\sqrt{|\mathbb A_j|}}-0)^2+\frac 12 \sum_{m\not\in \mathbb A_j}\sum_{n\in \mathbb A_j} w_{m,n}(0-\frac{1}{\sqrt{|\mathbb A_j|}})^2\\ =\frac 12\left(\sum_{m\in \mathbb A_j}\sum_{n\not\in \mathbb A_j} \frac{w_{m,n}}{|\mathbb A_j|}+\sum_{m\not\in \mathbb A_j}\sum_{n\in \mathbb A_j} \frac {w_{m,n}}{|\mathbb A_j|}\right)\\ =\frac 12\times\frac{1}{|\mathbb A_j|}(cut(\mathbb A_j,\bar{\mathbb A}_j)+cut(\bar{\mathbb A}_j,\mathbb A_j))=RatioCut(\mathbb A_j,\bar{\mathbb A}_j) $

   因此 $ MathJax-Element-678 $ 。其中 $ MathJax-Element-679 $ ， $ MathJax-Element-666 $ 为矩阵的迹。

   考虑到顶点 $ MathJax-Element-612 $ 有且仅位于一个子图中，则有约束条件：

   $ \mathbf{\vec h}_i\cdot\mathbf{\vec h}_j=\begin{cases} 0,&i\ne j\\ 1,&i = j \end{cases} $

3. RatioCut算法： $ MathJax-Element-680 $ 最小的切分。即求解：

   $ \min_{\mathbf H} tr(\mathbf H^T\mathbf L\mathbf H)\\ s.t. \mathbf H^T\mathbf H=\mathbf I $

   因此只需要求解 $ MathJax-Element-640 $ 最小的 $ MathJax-Element-306 $ 个特征值，求得对应的 $ MathJax-Element-306 $ 个特征向量组成 $ MathJax-Element-437 $ 。

   通常在求解得到 $ MathJax-Element-437 $ 之后，还需要对行进行标准化： $ MathJax-Element-681 $

4. 事实上这样解得的 $ MathJax-Element-437 $ 不能完全满足指示向量的定义。因此在得到 $ MathJax-Element-437 $ 之后，还需要对每一行进行一次传统的聚类（如：k-means 聚类）。

5. RatioCut 算法：

   • 输入：

     • 数据集 $ MathJax-Element-544 $
     • 降维的维度 $ MathJax-Element-695 $
     • 二次聚类算法
     • 二次聚类的维度 $ MathJax-Element-696 $

   • 输出：聚类簇 $ MathJax-Element-697 $

   • 算法步骤：

     • 根据 $ MathJax-Element-548 $ 构建相似度矩阵 $ MathJax-Element-685 $ 。

     • 根据相似度矩阵构建邻接矩阵 $ MathJax-Element-609 $ 、度矩阵 $ MathJax-Element-596 $ ，计算拉普拉斯矩阵 $ MathJax-Element-632 $ 。

     • 计算 $ MathJax-Element-640 $ 最小的 $ MathJax-Element-695 $ 个特征值，以及对应的特征向量 $ MathJax-Element-689 $ ，构建矩阵 $ MathJax-Element-701 $ 。

     • 对 $ MathJax-Element-437 $ 按照行进行标准化： $ MathJax-Element-681 $ ，得到 $ MathJax-Element-707 $ 。

     • 将 $ MathJax-Element-707 $ 中每一行作为一个 $ MathJax-Element-695 $ 维的样本，一共 $ MathJax-Element-400 $ 个样本，利用二次聚类算法来聚类，二次聚类的维度为 $ MathJax-Element-696 $ 。

       最终得到簇划分 $ MathJax-Element-697 $ 。

5.3.3 Ncut 算法

1. Ncut 切图不仅考虑最小化 $ MathJax-Element-667 $ ，它还考虑最大化每个子图的边的权重。即：

   $ Ncut(\mathbb A_1,\cdots,\mathbb A_k)= \sum_{i=1}^k\frac{W(\mathbb A_i,\bar{\mathbb A}_i)}{vol(\mathbb A_i)} $
   • 最小化 $ MathJax-Element-667 $ ：使得不同子图之间的边的权重尽可能的低。
   • 最大化每个子图的边的权重：使得各子图内的边的权重尽可能的高。

2. 引入指示向量 $ MathJax-Element-677 $ ，定义：

   $ h_{j,i}=\begin{cases} 0,& i \not \in \mathbb A_j\\ \frac{1}{\sqrt{vol(\mathbb A_j)}},& i \in\mathbb A_j \end{cases} $

   则有：

   $ \mathbf{\vec h}_j^T\mathbf L\mathbf{\vec h}_j=\frac 12 \sum_{m=1}^N\sum_{n=1}^N w_{m,n}(h_{j,m}-h_{j,n})^2\\ =\frac 12 \sum_{m\in \mathbb A_j}\sum_{n\not\in \mathbb A_j} w_{m,n}(\frac{1}{\sqrt{vol(\mathbb A_j)}}-0)^2+\frac 12 \sum_{m\not\in \mathbb A_j}\sum_{n\in \mathbb A_j} w_{m,n}(0-\frac{1}{\sqrt{vol(\mathbb A_j)}})^2\\ =\frac 12\left(\sum_{m\in \mathbb A_j}\sum_{n\not\in \mathbb A_j} \frac{w_{m,n}}{vol(\mathbb A_j)}+\sum_{m\not\in \mathbb A_j}\sum_{n\in \mathbb A_j} \frac {w_{m,n}}{vol(\mathbb A_j)}\right)\\ =\frac 12\times\frac{1}{vol(\mathbb A_j)}(cut(\mathbb A_j,\bar{\mathbb A}_j)+cut(\bar{\mathbb A}_j,\mathbb A_j))=Ncut(\mathbb A_j,\bar{\mathbb A}_j) $

   因此 $ MathJax-Element-722 $ 。其中 $ MathJax-Element-679 $ ， $ MathJax-Element-666 $ 为矩阵的迹。

   考虑到顶点 $ MathJax-Element-612 $ 有且仅位于一个子图中，则有约束条件：

   $ \mathbf{\vec h}_i\cdot\mathbf{\vec h}_j=\begin{cases} 0,&i\ne j\\ \frac{1}{ vol(\mathbb A_j)},&i = j \end{cases} $

3. Ncut算法： $ MathJax-Element-723 $ 最小的切分。即求解

   $ \min_{\mathbf H} tr(\mathbf H^T\mathbf L\mathbf H)\\ s.t. \mathbf H^T\mathbf D\mathbf H=\mathbf I $

4. 令 $ MathJax-Element-724 $ ，则有：

   $ \mathbf H^T\mathbf L\mathbf H=\mathbf F^T\mathbf D^{-1/2}\mathbf L\mathbf D^{-1/2}\mathbf F\\ \mathbf H^T\mathbf D\mathbf H=\mathbf F^T\mathbf F=\mathbf I $

   令 $ MathJax-Element-725 $ ，则最优化目标变成：

   $ \min_{\mathbf H} tr(\mathbf F^T\mathbf L^\prime\mathbf F)\\ s.t. \mathbf F^T\mathbf F=\mathbf I $

   因此只需要求解 $ MathJax-Element-687 $ 最小的 $ MathJax-Element-306 $ 个特征值，求得对应的 $ MathJax-Element-306 $ 个特征向量组成 $ MathJax-Element-691 $ 。然后对行进行标准化： $ MathJax-Element-692 $ 。

   与RatioCut 类似，Ncut 也需要对 $ MathJax-Element-691 $ 的每一行进行一次传统的聚类（如：k-means 聚类）。

5. 事实上 $ MathJax-Element-726 $ 相当于对拉普拉斯矩阵 $ MathJax-Element-640 $ 进行了一次标准化： $ MathJax-Element-727 $ 。

6. Ncut 算法：

   • 输入：

     • 数据集 $ MathJax-Element-544 $
     • 降维的维度 $ MathJax-Element-695 $
     • 二次聚类算法
     • 二次聚类的维度 $ MathJax-Element-696 $

   • 输出：聚类簇 $ MathJax-Element-697 $

   • 算法步骤：

     • 根据 $ MathJax-Element-548 $ 构建相似度矩阵 $ MathJax-Element-685 $ 。

     • 根据相似度矩阵构建邻接矩阵 $ MathJax-Element-609 $ 、度矩阵 $ MathJax-Element-596 $ ，计算拉普拉斯矩阵 $ MathJax-Element-632 $ 。

     • 构建标准化之后的拉普拉斯矩阵 $ MathJax-Element-686 $ 。

     • 计算 $ MathJax-Element-687 $ 最小的 $ MathJax-Element-695 $ 个特征值，以及对应的特征向量 $ MathJax-Element-689 $ ，构建矩阵 $ MathJax-Element-690 $ 。

     • 对 $ MathJax-Element-691 $ 按照行进行标准化： $ MathJax-Element-692 $ ，得到 $ MathJax-Element-694 $ 。

     • 将 $ MathJax-Element-694 $ 中每一行作为一个 $ MathJax-Element-695 $ 维的样本，一共 $ MathJax-Element-400 $ 个样本，利用二次聚类算法来聚类，二次聚类的维度为 $ MathJax-Element-696 $ 。

       最终得到簇划分 $ MathJax-Element-697 $ 。

5.4 性质

1. 谱聚类算法优点：

   • 只需要数据之间的相似度矩阵，因此处理稀疏数据时很有效。
   • 由于使用了降维，因此在处理高维数据聚类时效果较好。

2. 谱聚类算法缺点：

   • 如果最终聚类的维度非常高，则由于降维的幅度不够，则谱聚类的运行速度和最后聚类的效果均不好。
   • 聚类效果依赖于相似度矩阵，不同相似度矩阵得到的最终聚类效果可能不同。