谱聚类详细入门级介绍.ppt

文档介绍：谱聚类详细入门级介绍
图的表示
表示 与 之间的关系，称作权重，对于无向图
而且
表示无向图， 表示点集，E表示边集
Spectral Clustering 谱聚类
1
2
3
6
4
5








Spectral Clustering 谱聚类
图的划分
图划分是指将图完全划分为假设干个子图，各子图无交集
同子图内的点相似度高
不同子图的点相似度低
1
2
3
6
4
5








划分要求
G1
G2
Spectral Clustering 谱聚类
划分时子图之间被“截断〞的边的权重和
1
2
3
6
4
5








G1
G2
损失函数
Laplacian矩阵
损失函数
定义 是一个n维向量，用来表示划分方案
Spectral Clustering 谱聚类
假设 G(V，E)被划分成 两个子图（设G有n个顶点）
其中D为对角矩阵
Spectral Clustering 谱聚类
Laplacian矩阵
再定义一个 L 矩阵
L 称为拉普拉斯矩阵，W 为权重矩阵〔也称邻接矩阵〕，D 为度矩阵
Spectral Clustering 谱聚类
Laplacian矩阵
L为半正定矩阵（即所有特征值非负值），最小特征值为0， 且对应的特征向量为单位向量
损失函数
Spectral Clustering 谱聚类
Laplacian矩阵
图的划分问题转化为 条件最小值问题
Spectral Clustering 谱聚类
条件
1
2
3
6
4
5








1
2
3
4
5
6
1





0. 0
2






3






4






5






6






邻接矩阵W
1
2
3
4
5
6
1





0. 0
2






3






4






5






6






度矩阵D
举例
Spectral Clustering 谱聚类