五、谱聚类

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

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

   • 顶点 ：由数据集中的数据点组成： 。

   • 边 ：任意一对顶点之间存在边。

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

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

   

5.1 邻接矩阵

1. 在图 中，定义权重 为顶点 和 之间的权重，其中 。

   定义 为邻接矩阵：

   

   由于 为无向图，因此 。即： 。

   • 对图中顶点 ，定义它的度 为：所有与顶点 相连的边的权重之和： 。

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

     

   • 对于顶点集合 的一个子集 ，定义 为子集 中点的个数；定义 ，为子集 中所有点的度之和。

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

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

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

     

     • 通常相似度采用高斯核： 。此时有 。即： 。
     • 也可以选择不同的核函数，如：多项式核函数、高斯核函数、sigmoid 核函数。

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

   

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

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

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

   这种做法会导致邻接矩阵 非对称，因为当 是 的 近邻时， 不一定是 的 近邻。

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

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

     

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

     

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

5.2 拉普拉斯矩阵

1. 定义拉普拉斯矩阵 ，其中 为度矩阵、 为邻接矩阵。

2. 拉普拉斯矩阵 的性质：

   • 是对称矩阵，即 。这是因为 都是对称矩阵。

   • 因为 是实对称矩阵，因此它的特征值都是实数。

   • 对任意向量 ，有： 。

   • 是半正定的，且对应的 个特征值都大于等于0，且最小的特征值为 0。

     设其 个实特征值从小到大为 ，即： 。

5.3 谱聚类算法

1. 给定无向图 ，设子图的点的集合 和子图的点的集合 都是 的子集，且 。

   定义 和 之间的切图权重为： 。

   即：所有连接 和 之间的边的权重。

2. 对于无向图 ，假设将它切分为 个子图：每个子图的点的集合为 ，满足 且 。

   定义切图cut 为： ，其中 为 的补集。

5.3.1 最小切图

1. 引入指示向量 ，定义：

   

   则有：

   

   因此 。其中 ， 为矩阵的迹。

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

   

2. 最小切图算法： 最小的切分。即求解：

   

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

   

5.3.2 RatioCut 算法

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

   

   • 最小化 ：使得不同子图之间的边的权重尽可能的低。
   • 最大化每个子图的点的个数：使得各子图尽可能的大。

2. 引入指示向量 ，定义：

   

   则有：

   

   因此 。其中 ， 为矩阵的迹。

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

   

3. RatioCut算法： 最小的切分。即求解：

   

   因此只需要求解 最小的 个特征值，求得对应的 个特征向量组成 。

   通常在求解得到 之后，还需要对行进行标准化：

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

5. RatioCut 算法：

   • 输入：

     • 数据集
     • 降维的维度
     • 二次聚类算法
     • 二次聚类的维度

   • 输出：聚类簇

   • 算法步骤：

     • 根据 构建相似度矩阵 。

     • 根据相似度矩阵构建邻接矩阵 、度矩阵 ，计算拉普拉斯矩阵 。

     • 计算 最小的 个特征值，以及对应的特征向量 ，构建矩阵 。

     • 对 按照行进行标准化： ，得到 。

     • 将 中每一行作为一个 维的样本，一共 个样本，利用二次聚类算法来聚类，二次聚类的维度为 。

       最终得到簇划分 。

5.3.3 Ncut 算法

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

   

   • 最小化 ：使得不同子图之间的边的权重尽可能的低。
   • 最大化每个子图的边的权重：使得各子图内的边的权重尽可能的高。

2. 引入指示向量 ，定义：

   

   则有：

   

   因此 。其中 ， 为矩阵的迹。

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

   

3. Ncut算法： 最小的切分。即求解

   

4. 令 ，则有：

   

   令 ，则最优化目标变成：

   

   因此只需要求解 最小的 个特征值，求得对应的 个特征向量组成 。然后对行进行标准化： 。

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

5. 事实上 相当于对拉普拉斯矩阵 进行了一次标准化： 。

6. Ncut 算法：

   • 输入：

     • 数据集
     • 降维的维度
     • 二次聚类算法
     • 二次聚类的维度

   • 输出：聚类簇

   • 算法步骤：

     • 根据 构建相似度矩阵 。

     • 根据相似度矩阵构建邻接矩阵 、度矩阵 ，计算拉普拉斯矩阵 。

     • 构建标准化之后的拉普拉斯矩阵 。

     • 计算 最小的 个特征值，以及对应的特征向量 ，构建矩阵 。

     • 对 按照行进行标准化： ，得到 。

     • 将 中每一行作为一个 维的样本，一共 个样本，利用二次聚类算法来聚类，二次聚类的维度为 。

       最终得到簇划分 。

5.4 性质

1. 谱聚类算法优点：

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

2. 谱聚类算法缺点：

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