图卷积神经网络

图网络

1. 谱聚类算法过程

• 综上可得谱聚类的算法过程如下

  • 根据数据构造一个Graph，Graph的每一个节点对应一个数据点，将各个点连接起来（随后将那些已经被连接起来但并不怎么相似的点，通过cut/RatioCut/NCut 的方式剪开），并且边的权重用于表示数据之间的相似度。把这个Graph用邻接矩阵的形式表示出来，记为 。
  • 把的每一列元素加起来得到个数，把它们放在对角线上（其他地方都是零），组成一个的对角矩阵，记为度矩阵，并把 - 的结果记为拉普拉斯矩阵。
  • 求出的前个特征值（前个指按照特征值的大小从小到大排序得到），以及对应的特征向量。
  • 把这个特征（列）向量排列在一起组成一个的矩阵，将其中每一行看作维空间中的一个向量，并使用 K-means 算法进行聚类。聚类的结果中每一行所属的类别就是原来 Graph 中的节点亦即最初的个数据点分别所属的类别。

或许你已经看出来，谱聚类的基本思想便是利用样本数据之间的相似矩阵（拉普拉斯矩阵）进行特征分解（ 通过Laplacian Eigenmap 的降维方式降维），然后将得到的特征向量进行 K-means聚类。此外，谱聚类和传统的聚类方法（例如 K-means）相比，谱聚类只需要数据之间的相似度矩阵就可以了，而不必像K-means那样要求数据必须是 N 维欧氏空间中的向量。