谱聚类spectral clustering
2021-9-30
| 2023-8-6
0  |  阅读时长 0 分钟
type
status
date
slug
summary
tags
category
icon
password
Property

原理

谱聚类概述

谱聚类是从图论中演化出来的算法，后来在聚类中得到了广泛的应用。它的主要思想是把所有的数据看做空间中的点，这些点之间可以用边连接起来。距离较远的两个点之间的边权重值较低，而距离较近的两个点之间的边权重值较高，通过对所有数据点组成的图进行切图，让切图后不同的子图间边权重和尽可能的低，而子图内的边权重和尽可能的高，从而达到聚类的目的
 

谱聚类基础之一：无向权重图

对于一个图，一般用点的集合和边的集合来描述，即为 。其中即为数据集里面所有的点。对于中的任意两个点，可以有边连接，也可以没有边连接。定义权重 为点 和点 之间的权重。由于是无向图，所以。
对于有边连接的两个点 和， ，对于没有边连接的两个点和， 。对于图中的任意一个点，它的度定义为和它相连的所有边的权重之和，即
利用每个点度的定义，可以得到一个的度矩阵它是一个对角矩阵，只有主对角线有值，对应第行的第个点的度数，定义如下：
利用所有点之间的权重值，可以得到图的邻接矩阵，一个的矩阵，第 行的第个值对应权重
除此之外，对于点集的的一个子集，定义：

谱聚类基础之二：相似矩阵

邻接矩阵是由任意两点之间的权重值 组成的矩阵。通常可以自己输入权重，但是在谱聚类中，只有数据点的定义，并没有直接给出这个邻接矩阵，那么怎么得到这个邻接矩阵呢？
基本思想是，距离较远的两个点之间的边权重值较低，而距离较近的两个点之间的边权重值较高，不过这仅仅是定性，需要定量的权重值。一般来说，可以通过样本点距离度量的相似矩阵来获得邻接矩阵
 
构建邻接矩阵的方法有三类： -邻近法，K邻近法和全连接法
对于 -邻近法，它设置了一个距离阈值 ，然后用欧式距离度量任意两点和的距离。即相似矩阵的，然后根据 和 的大小关系，来定义邻接矩阵如下：
从上式可见，两点间的权重要不就是要不就是0，没有其他的信息了。距离远近度量很不精确，因此在实际应用中，很少使用-邻近法
 
邻近法，利用算法遍历所有的样本点，取每个样本最近的个点作为近邻，只有和样本距离最近的个点之间的。但是这种方法会造成重构之后的邻接矩阵非对称，后面的算法需要对称邻接矩阵。为了解决这种问题，一般采取下面两种方法之一：
第一种邻近法是只要一个点在另一个点的近邻中，则保留
第二种邻近法是必须两个点互为近邻中，才能保留
 
 
全连接法，相比前两种方法，全连接法所有的点之间的权重值都大于0。可以选择不同的核函数来定义边权重，常用的有多项式核函数，高斯核函数和Sigmoid核函数。最常用的是高斯核函数RBF，此时相似矩阵和邻接矩阵相同：
实际应用中，使用全连接法来建立邻接矩阵是最普遍的，在全连接法中使用高斯径向核RBF是最普遍的。
 

谱聚类基础之三：拉普拉斯矩阵

拉普拉斯矩阵(Graph Laplacians)的定义很简单，拉普拉斯矩阵：。为度矩阵，它是一个对角矩阵，为邻接矩阵。
 
拉普拉斯矩阵有一些很好的性质如下：
  • 拉普拉斯矩阵是对称矩阵，这可以由和都是对称矩阵而得
  • 由于拉普拉斯矩阵是对称矩阵，则它的所有的特征值都是实数
  • 对于任意的向量 ，有
这个利用拉普拉斯矩阵的定义很容易得到如下：
  • 拉普拉斯矩阵是半正定的，且对应的 个实数特征值都大于等于0，即， 且最小的特征值为0，这个由性质3很容易得出
 

谱聚类基础之四：无向图切图

对于无向图的切图，目标是将图 切成相互没有连接的个子图，每个子图点的集合为： ，它们满足，且
 
对于任意两个子图点的集合 ， ，定义和之间的切图权重为：
那么对于个子图点的集合：，定义切图cut为：
其中 为的补集，意为除子集外其他 的子集的并集
那么如何切图可以让子图内的点权重和高，子图间的点权重和低呢？一个自然的想法就是最小化, 但是可以发现，这种极小化的切图存在问题，如下图：
notion image
选择一个权重最小的边缘的点，比如 和 之间进行，这样可以最小化，但是却不是最优的切图，如何避免这种切图，并且找到类似图中"Best Cut"这样的最优切图呢？
 

谱聚类之切图聚类

为了避免最小切图导致的切图效果不佳，需要对每个子图的规模做出限定，一般来说，有两种切图方式，第一种是RatioCut，第二种是Ncut。

RatioCut切图

RatioCut切图为了避免最小切图，对每个切图，不光考虑最小化，它还同时考虑最大化每个子图点的个数，即：
那么怎么最小化这个RatioCut函数呢？牛人们发现，RatioCut函数可以通过如下方式表示。
引入指示向量，对于任意一个向量 , 它是一个维向量（ 为样本数），定义为：
那么对于 ，有：
上述第（1）式用了拉普拉斯矩阵的性质，第二式用到了指示向量的定义。可以看出，对于某一个子图，它的RatioCut对应于 ，那么 个子图呢？对应的RatioCut函数表达式为：
其中 为矩阵的迹。也就是说，RatioCut切图实际上就是最小化我们的。注意到 ，则切图优化目标为：
注意到矩阵里面的每一个指示向量都是维的，向量中每个变量的取值为0或者，就有 种取值，有个子图的话就有个指示向量，共有 种，因此找到满足上面优化目标的是一个NP难的问题。那么是不是就没有办法了呢？
注意观察中每一个优化子目标，其中是单位正交基， 为对称矩阵，此时的最大值为的最大特征值，最小值是的最小特征值。如果对PCA很熟悉的话，很好理解，在PCA中，目标是找到协方差矩阵（对应此处的拉普拉斯矩阵）的最大的特征值，而在谱聚类中，目标是找到目标的最小的特征值，得到对应的特征向量，此时对应二分切图效果最佳。也就是说，这里要用到维度规约的思想来近似去解决这个NP难的问题。
 
对于 ，目标是找到最小的 的特征值，而对于，目标就是找到个最小的特征值，一般来说， 远远小于 ，也就是说，此时进行了维度规约，将维度从 降到了 ，从而近似可以解决这个NP难的问题。
通过找到L的最小的 个特征值，可以得到对应的 个特征向量，这 个特征向量组成一个维度的矩阵，即为我们的。一般需要对矩阵按行做标准化，即
由于在使用维度规约的时候损失了少量信息，导致得到的优化后的指示向量对应的现在不能完全指示各样本的归属（用的是近似方法可能是局部最优解），因此一般在得到维度的矩阵后还需要对每一行进行一次传统的聚类，比如使用K-Means聚类
 

Ncut切图

Ncut切图和RatioCut切图很类似，但是把Ratiocut的分母 换成 。由于子图样本的个数多并不一定权重就大，切图时基于权重也更合我们的目标，因此一般来说Ncut切图优于RatioCut切图。Ncut是对拉普拉斯矩阵做了归一化再求特征向量，而RadioCut是没有做归一化就求了特征向量
对应的，Ncut切图对指示向量 做了改进。RatioCut切图的指示向量使用的是 标示样本归属，而Ncut切图使用了子图权重 来标示指示向量 ，定义如下:
这里是样本序号， 是类别序号。根据定义，每一个样本会被分到 个类别中的一个。假设这里样本数大于类别数，那么肯定某一个类别有不止一个样本，那么对应的指示向量不应该都只有一个样本被分到，指示向量也不应该只有一个标量维度是1。
那么对于 ，有：
推导方式和RatioCut完全一致，优化目标仍然是
但是此时 ，而是 ：
也就是说，此时优化目标最终为：
此时中的指示向量并不是标准正交基，所以在RatioCut里面的降维思想不能直接用。怎么办呢？其实只需要将指示向量矩阵做一个小小的转化即可。
令，则： ，优化目标变成了:
可以发现这个式子和RatioCut基本一致，只是中间的变成了 。这样就可以继续按照RatioCut的思想，求出的最小的前个特征值，然后求出对应的特征向量，并标准化，得到最后的特征矩阵最后对进行一次传统的聚类（比如K-Means）即可。
一般来说， 相当于对拉普拉斯矩阵做了一次标准化，即
 

谱聚类算法流程

一般来说，谱聚类主要的注意点为相似矩阵的生成方式，切图的方式以及最后的聚类方法
最常用的相似矩阵的生成方式是基于高斯核距离的全连接方式，最常用的切图方式是Ncut。而到最后常用的聚类方法为K-Means。下面以Ncut总结谱聚类算法流程。
输入：样本集 ，相似矩阵的生成方式，降维后的维度, 聚类方法，聚类后的维度
输出： 簇划分
  1. 根据输入的相似矩阵的生成方式构建样本的相似矩阵
  1. 根据相似矩阵构建邻接矩阵，构建度矩阵
  1. 计算出拉普拉斯矩阵
  1. 构建标准化后的拉普拉斯矩阵
      2. 令，有：
      这样就可以说标准化后的拉普拉斯矩阵是
      标准化的效果就是减少单点权重对整个聚类效果的影响
  1. 计算 最小的 个特征值所各自对应的特征向量
  1. 将各自对应的特征向量组成的矩阵按行标准化，最终组成 维的特征矩阵
      2. 注： 是对原始拉普拉斯矩阵在低维的一个近似，这个近似可以使Ncut的损失函数局部最小。对聚类可以使在低维近似的基础上得到一个最好的局部最优解
  1. 对 中的每一行作为一个 维的样本，共 个样本，用输入的聚类方法进行聚类，聚类维数为（理论上这一步不是必选的，这样做只是为了聚类效果更佳健壮）
  1. 得到簇划分
 

谱聚类算法总结

谱聚类算法的主要优点有：
  • 谱聚类只需要数据之间的相似度矩阵，因此对于处理稀疏数据的聚类很有效。这点传统聚类算法比如K-Means很难做到
  • 由于使用了降维，因此在处理高维数据聚类时的复杂度比传统聚类算法好
谱聚类算法的主要缺点有：
  • 如果最终聚类的维度非常高，则由于降维的幅度不够，谱聚类的运行速度和最后的聚类效果均不好
  • 聚类效果依赖于相似矩阵，不同的相似矩阵得到的最终聚类效果可能很不同
 
理论上拉普拉斯矩阵可以用于有向图的，那么谱聚类肯定也可以用上。不过这个拉普拉斯矩阵定义就会复杂很多，关于有向图聚类，目前比较常见的是马尔科夫聚类。
做谱聚类的数据不需要单独再做标准化了，因为一般使用Ncut，他在已经帮你做了拉普拉斯矩阵标准化了
 

代码

在scikit-learn的类库中，sklearn.cluster.SpectralClustering实现了基于Ncut的谱聚类，没有实现基于RatioCut的切图聚类。同时，对于相似矩阵的建立，也只是实现了基于K邻近法和全连接法的方式，没有基于-邻近法的相似矩阵。最后一步的聚类方法则提供了两种:K-Means算法和 discretize算法。
对于SpectralClustering的参数，主要需要调参的是相似矩阵建立相关的参数和聚类类别数目，它对聚类的结果有很大的影响。当然其他的一些参数也需要理解，在必要时需要修改默认参数。
 

SpectralClustering的重要参数:

n_clusters
对谱聚类切图时降维到的维数（），同时也是最后一步聚类算法聚类到的维数()，也就是说scikit-learn中的谱聚类对这两个参数统一到了一起。简化了调参的参数个数。虽然这个值是可选的，但是一般还是推荐调参选择最优参数。
affinity
相似矩阵的建立方式。可以选择的方式有三类，第一类是 'nearest_neighbors'即K邻近法；第二类是'precomputed'即自定义相似矩阵。选择自定义相似矩阵时，需要自己调用set_params来自己设置相似矩阵；第三类是全连接法，可以使用各种核函数来定义相似矩阵，还可以自定义核函数。最常用的是内置高斯核函数'rbf'。其他比较流行的核函数有‘linear’即线性核函数, ‘poly’即多项式核函数, ‘sigmoid’即sigmoid核函数。如果选择了这些核函数， 对应的核函数参数在后面有单独的参数需要调。
affinity默认是高斯核'rbf'。一般来说，相似矩阵推荐使用默认的高斯核函数。
核函数参数gamma
如果在affinity参数使用了多项式核函数 'poly'，高斯核函数‘rbf’, 或者'sigmoid'核函数，那么就需要对这个参数进行调参。
  • 多项式核函数（Polynomial Kernel）是线性不可分SVM常用的核函数之一：
      • ，其中 都需要自己调参定义,比较麻烦
  • 高斯核函数（Gaussian Kernel），在SVM中也称为径向基核函数（Radial Basis Function,RBF），它是libsvm默认的核函数，当然也是scikit-learn默认的核函数： 其中，大于0，需要自己调参定义。一般情况下，对非线性数据使用默认的高斯核函数会有比较好的效果
  • Sigmoid核函数（Sigmoid Kernel）也是线性不可分SVM常用的核函数之一：
      • ， 其中 都需要自己调参定义
      默认值为1.0，如果affinity使用'nearest_neighbors'或者是'precomputed'，则这么参数无意义。
核函数参数degree
如果在affinity参数使用了多项式核函数 'poly'，那么就需要对这个参数进行调参。
这个参数对应 中的默认是3。一般需要通过交叉验证选择一组合适的
核函数参数coef0
如果在affinity参数使用了多项式核函数 'poly'，或者sigmoid核函数，那么就需要对这个参数进行调参，对应，coef0默认为1
kernel_params
如果affinity参数使用了自定义的核函数，则需要通过这个参数传入核函数的参数。
n_neighbors
如果affinity参数指定为'nearest_neighbors'即K邻近法，则可以通过这个参数指定KNN算法的K的个数。默认是10。需要根据样本的分布对这个参数进行调参。如果affinity不使用'nearest_neighbors'，无需理会这个参数。
eigen_solver
在降维计算特征值特征向量的时候，使用的工具。有None, ‘arpack’, ‘lobpcg’, 和‘amg’4种选择。如果样本数不是特别大，无需理会这个参数，使用''None暴力矩阵特征分解即可，如果样本量太大，则需要使用后面的一些矩阵工具来加速矩阵特征分解。它对算法的聚类效果无影响。
eigen_tol
如果eigen_solver使用了arpack’，则需要通过eigen_tol指定矩阵分解停止条件。
assign_labels
最后的聚类方法的选择，有K-Means算法和 discretize算法两种算法可以选择。一般来说，默认的K-Means算法聚类效果更好。但是由于K-Means算法结果受初始值选择的影响，可能每次都不同，如果需要算法结果可以重现，则可以使用discretize。
n_init
即使用K-Means时用不同的初始值组合跑K-Means聚类的次数，这个和K-Means类里面n_init的意义完全相同，默认是10，一般使用默认值就可以。如果n_clusters值较大，则可以适当增大这个值。
 
 
 
相关文章 :
数据分析
  • Scikit-Learn
    • DBSCAN密度聚类AutoML
    目录