谱聚类——相似度
1、图的最短距离 任意两点之间的最短距离。我们用两点之间的最短距离表示相似度 2、边聚类系数——两点共存三角形的个数 / 两点度的最小值 3、边稠密度系数： 与两点相邻的边数 / [(1/2)n(n-1)] 4、 Betweenness: 图中任意两点的最短路径经过这条边的数
5、图像中加入位置信息和亮度信息
可知
所以得到
Laplacian矩阵特点: 1、L为半正定矩阵，所有的特征值都大于0 2、L矩阵有唯一的0特征值，其对应的特征向量为[1,1,……1]T
谱聚类——聚类原理(分割方法)
1、Minimum Cut 定义 ，此时的Cut函数变为
q T Lq Cut(G1, G 2) 4
从这个问题的形式可以联想到Rayleigh quotient(瑞利商) R(L,q)的最大值和最小值分别在矩阵L的最大特征值和最小特征值处取得，且q的值取 在相对应的特征向量 所以原式可化为求解下下特征系统的特征值和特征向量：
Cut(G1, G 2) Cut(G1, G 2) Ncut(G1, G 2) Cut(G1, G) Cut(G 2, G)
公式可变为如下形式：
Ncut(G1, G 2) 2 (
Cut(G1, G1) Cut(G 2, G 2) ) Cut(G1, G) Cut(G 2, G)
所以在减少了子图之间的Cut值的同时也增加了子图内部的相似度。保证了分割的平衡性
由数据点间相似关系建立矩阵，获取该矩阵的前n个特征向量，并且 用它们来聚类不同的数据点。
谱聚类——步骤
1）根据数据构造一个 Graph ，并用W表示这个Graph的邻接矩阵 Graph 的每一个节点对应一个数据点，将相似的点连接起来，并且边的权重用于表 示数据之间的相似度。把这个 Graph 用邻接矩阵的形式表示出来，记为 W 。 2) 构造出Laplacian矩阵L 把每一列元素加起来得到N 个数，把它们放在对角线上（其他地方都是零），组成 一个N*N的矩阵，记为D 。并令L = D - W 。 3) 求出L的前k个特征值以及对应的特征向量 在本文中，除非特殊说明，否则“前k个”指按照特征值的大小从小到大的顺序 4) 将这K个特征向量组成N*K的矩阵进行聚类 把这k个特征（列）向量排列在一起组成一个N*k的矩阵，将其中每一行看作k维空间 中的一个向量，并使用 相应算法进行聚类。聚类的结果中每一行所属的类别就 是原来 Graph 中的节点亦即最初的N个数据点分别所属的类别。
谱聚类——聚类原理
相关定义： 1、用G = (V,E)表示无向图，其中V和E分别为其顶点集和边集； 2、某条边属于某个子图是指该边的两个顶点都包含在子图中 3、假设某边的两个端点为 i, j，则该边的权重为wi,j,可知对于谱聚类中wi,j=wj,i,且 wi,i=0
4、对于图的某种划分方法Cut：所有两端点不在同一子图中的边的权重之和，
谱聚类——聚类原理(分割方法)
2、Normalized Cut 定义d1 = Cut（G1,G）,d2 = Cut(G2,G) 所以Ncut(G1,G2) =
其中
用泛化的Rayleigh quotient表示为
那问题就变成求解下特征系统的特征值和特征向量：
谱聚类——求特征向量及聚类
3 、求出L的前k个特征值以及对应的特征向量 a．2-way：将原始样本数据映射到一维空间(k=1); 求出最小的两个特征值，由于最小的特征值为0，所以实际只剩下一个特征值和一 对应的n维特征向量，将这个特征向量进行分类，分为两类。再到每一个子图中迭 代的进行2-way分类。 b. k-way；将原始样本数据映射到由k个正交向量组成的k维空间S。 求出最小的k个特征值，用k-means等聚类方法将n*k矩阵进行分类，第i行表示的数 字即为第i个顶点属于的类别 如何选择K，可以采用启发式方法，比如，发现第1到m的特征值都挺小的，到了 m+1突然变成较大的数，那么就可以选择K=m； ’
「 Graph Cut 」
Graph Cut ——Spectral Clustering
图像分割——谱聚类 李翔 2014/4/4
谱聚类——Spectral Clustering
谱聚类算法： 1、建立在图论中的谱图理论基础上的一种分类算法
2、本质是将聚类问题转化为图的最优划分问题
3、是一种点对聚类算法
显而易见L的最小特征值是0，对应的特征向量为[1,1……1]T，于是最优解应该是在第 二小的特征向量处开始取
谱聚类——聚类原理(ห้องสมุดไป่ตู้割方法)
2、Normalized Cut 实际当中，划分图时除了要考虑最小化Cut外,还要考虑划分的平衡性，为缓解出现类 似一个子图包含非常多端点而另一个只包含很少端点的情况,还要考虑到子图内部的相似 性。
它可以被看成该划分方案的损失函数，希望这种损失越小越好,即在图像分割的过程 中找到这个函数对应的最小值，即找到了最好的分割方式 以二分无向图为例
谱聚类——聚类原理(Laplacian)
Laplacian矩阵 假设无向图G被划分为G1和G2两个子图，该图的定点数为：n = |V|,用q表示n维指示向 量，每个分量定义如下
Thank
You
11