从拉普拉斯矩阵说到谱聚类
日期 : 2021年10月01日
正文共 :3381字
1、拉普拉斯矩阵
1.1 、Laplacian matrix的定义
1.2、 拉普拉斯矩阵的性质
②与某结点邻接的所有边的权值和定义为该顶点的度d,多个d 形成一个度矩阵 (对角阵)
是对称半正定矩阵;
,即 的最小特征值是0,相应的特征向量是 。证明: * = ( - ) * = 0 = 0 * 。(此外,别忘了,之前特征值和特征向量的定义:若数字和非零向量满足,则为的一个特征向量,是其对应的特征值)。
有n个非负实特征值
且对于任何一个属于实向量,有以下式子成立
2、谱聚类
cut/Ratio Cut
Normalized Cut
不基于图,而是转换成SVD能解的问题
2.1、 相关定义
无向图,顶点集V表示各个样本,带权的边表示各个样本之间的相似度
与某结点邻接的所有边的权值和定义为该顶点的度d,多个d 形成一个度矩阵(对角阵)
邻接矩阵,A子图与B子图之间所有边的权值之和定义如下:
其中,定义为节点到节点的权值,如果两个节点不是相连的,权值为零。
相似度矩阵的定义。相似度矩阵由权值矩阵得到,实践中一般用高斯核函数(也称径向基函数核)计算相似度,距离越大,代表其相似度越小。
子图A的指示向量如下:
2.2、 目标函数
2.3、最小化RatioCut 与最小化等价
定义向量,且:
若数字和非零向量满足,则为的一个特征向量,是其对应的特征值。
2.4、谱聚类算法过程
根据数据构造一个Graph,Graph的每一个节点对应一个数据点,将各个点连接起来(随后将那些已经被连接起来但并不怎么相似的点,通过cut/RatioCut/NCut 的方式剪开),并且边的权重用于表示数据之间的相似度。把这个Graph用邻接矩阵的形式表示出来,记为 。
把的每一列元素加起来得到个数,把它们放在对角线上(其他地方都是零),组成一个的对角矩阵,记为度矩阵,并把 - 的结果记为拉普拉斯矩阵。
求出的前个特征值(前个指按照特征值的大小从小到大排序得到),以及对应的特征向量。
把这个特征(列)向量排列在一起组成一个的矩阵,将其中每一行看作维空间中的一个向量,并使用 K-means 算法进行聚类。聚类的结果中每一行所属的类别就是原来 Graph 中的节点亦即最初的个数据点分别所属的类别。
— THE END —