谱聚类详细入门级介绍PPT学习教案

1、会计学1 谱聚类详细入门级介绍谱聚类详细入门级介绍 图的表示图的表示 表示 与 之间的关系，称作权重，对于无向图 jiij ww ij w i v j v 0 0 ijii ww 而且 表示无向图， 表示点集，E表示边集 ),(EVG,., 2 , 1n vvvV Spectral Clustering 谱聚类 1 2 3 64 5 0.8 0.8 0.80.8 0.6 0.1 0.2 0.7 Spectral Clustering 谱聚类 图的划分图的划分 图划分是指将图完全划分为若干个子图，各子图无交集 同子图内的点相似度高 不同子图的点相似度低 1 2 3 64 5 0.8 0.8 0.

2、80.8 0.6 0.1 0.2 0.7 划分要求划分要求 G1 G2 GGG k . 1 ji GG Spectral Clustering 谱聚类 划分时子图之间被“截断”的边的权重和 1 2 3 64 5 0.8 0.8 0.80.8 0.6 0.1 0.2 0.7 G1 G2 21, 21 ),( GjGi ij wGGCut 损失函数损失函数 Laplacian矩阵矩阵 Gi Gi 22 11 c c qi 2 21 11 2 , 21 )( 2 )( ),( 21 cc qqw wGGCut n i n j jiij GjGi ij 损失函数 定义 是一个n维向量，用来表示划分方案

3、 ,., 21n qqqq Spectral Clustering 谱聚类 假设 G(V，E)被划分成 两个子图（设G有n个顶点） 21,G G , 222111 ccccccq n i n j jiij qqw 11 2 )( n i n j jiij n i n j jiij qqwqqw 11 22 11 )(2 n i n j iji n i n j jiij wqqqw 11 2 11 22 qWDqT)(2 其中D为对角矩阵 n j ijii wD 1 Spectral Clustering 谱聚类 n i n j jjiiij qqqqw 11 22 )2( Laplacian矩

4、阵矩阵 qWDqqqw T n i n j jiij )(2)( 11 2 再定义一个 L 矩阵 WDL L 称为拉普拉斯矩阵，W 为权重矩阵（也称邻接矩阵），D 为度矩阵 Lqqqqw T n i n j jiij 2)( 11 2 Spectral Clustering 谱聚类 Laplacian矩阵矩阵 0)( 2 1 11 2 n i n j jiij T qqwLqq L为半正定矩阵（即所有特征值非负值），最小特征值为最小特征值为0， 且对应的特征向量为单位向量且对应的特征向量为单位向量 T 1.11 2 21 21 )( ),( cc Lqq GGCut T 损失函数损失函数 2

5、21 11 2 , 21 )(2 )( ),( 21 cc qqw wGGCut n i n j jiij GjGi ij Spectral Clustering 谱聚类 Laplacian矩阵矩阵 图的划分问题转化为 条件条件最小值问题 Lqq T Spectral Clustering 谱聚类 2 21 21 )( ),( cc Lqq GGCut T 条件条件 1 2 3 64 5 0.8 0.8 0.80.8 0.6 0.1 0.2 0.7 123456 10.00.80.60.00.10. 0 20.80.00.80.00.00.0 30.60.80.00.20.00.0 40.00

6、.00.20.00.80.7 50.10.00.00.80.00.8 60.00.00.00.70.80.0 邻接矩阵W 123456 11.50.00.00.00.00. 0 20.01.60.00.00.00.0 30.00.01.60.00.00.0 40.00.00.01.70.00.0 50.00.00.00.01.70.0 60.00.00.00.00.01.5 度矩阵D 举例举例 Spectral Clustering 谱聚类 123456 10.00.80.60.00.10. 0 20.80.00.80.00.00.0 30.60.80.00.20.00.0 40.00.00.

7、20.00.80.7 50.10.00.00.80.00.8 60.00.00.00.70.80.0 邻接矩阵W 123456 11.50.00.00.00.00. 0 20.01.60.00.00.00.0 30.00.01.60.00.00.0 40.00.00.01.70.00.0 50.00.00.00.01.70.0 60.00.00.00.00.01.5 度矩阵D 123456 1 1.5-0.8-0.60.0-0.10. 0 2 -0.81.6-0.80.00.00.0 3 -0.6-0.81.6-0.20.00.0 4 0.00.0-0.21.7-0.8-0.7 5 -0.10

8、.00.0-0.81.7-0.8 6 0.00.00.0-0.7-0.81.5 拉普拉斯矩阵L=D-W Spectral Clustering 谱聚类 举例举例 Minimum Cut方法方法 Gi c Gi 2 1 c qi )min(LqqT 求： 条件： 2 1 2 ncqqq n i i T Spectral Clustering 谱聚类 )min(LqqT 2 . .ncqqts T qq Lqq qLR T T ),( 瑞利商: 性质： 的最小值，次小值最大值分别在q为L的最小特征值，次小特征值最大特征值对应的特征向量时取得 ),(qLR 求求L次小次小特征值所对应的特征向量特征值

9、所对应的特征向量 Spectral Clustering 谱聚类 Minimum Cut方法方法 GG 123456 1 1.5-0.8-0.60.0-0.10. 0 2 -0.81.6-0.80.00.00.0 3 -0.6-0.81.6-0.20.00.0 4 0.00.0-0.21.7-0.8-0.7 5 -0.10.00.0-0.81.7-0.8 6 0.00.00.0-0.7-0.81.5 拉普拉斯矩阵L 123456 0.408-0.408-0.647-0.306-0.3790.106 0.408-0.4420.0140.3050.7060.215 0.408-0.3710.638

10、0.045-0.388-0.368 0.4080.3710.339-0.455-0.0010.612 0.4080.405-0.167-0.3050.351-0.652 0.4080.445-0.1780.716-0.2890.087 -0.408 -0.442 -0.371 0.371 0.405 0.445 1 2 3 64 5 0.8 0.8 0.8 0.8 0.6 0.1 0.2 0.7 G1 G2 次小次小特征值的特征向量特征值的特征向量 Spectral Clustering 谱聚类 举例举例 2 3 1 64 5 0.3 0. 8 0. 8 0. 6 0. 2 0.2 0.7 7

11、 0.7 0.6 Minimum Cut划分不均衡 Spectral Clustering 谱聚类 Minimum Cut方法方法 Ratio Cut 方法方法 21 2121 11 ),(),( nn GGCutGGRcut 1 n 、 划分到子图1和子图2的顶点个数 2 n ),( 21 GGRcut 21 , 11 21 nn w GjGi ij 2 1 2 2 1 , 21 nn n nn n w GjGi ij nnn nn w GjGi ij 21 2 21 , )( 21 21 21 , )( 21 nn nn w GjGi ij 2 21 2 2 21 2 1 , 21 nnn

12、 n nnn n w GjGi ij Spectral Clustering 谱聚类 2 1 2 1 2 1 Gi nn n Gi nn n qi 令 n i i T qqq 1 2 2 1 2 2 1 , 21 nn n nn n w GjGi ij ),( 21 GGRcut Lqqqqw T ji GjGi ij 2 , 21 ),( 21 GGRcut Spectral Clustering 谱聚类 21 22 Gi i Gi i qq1 2 1 2 1 2 1 nn n n nn n n Ratio Cut 方法方法 )min(LqqT 1 . .qqts T qq Lqq qLR

13、T T ),( 瑞利商 Spectral Clustering 谱聚类 Ratio Cut 方法方法 21 2121 11 ),(),( dd GGCutGGNcut 21 dd、 子图1和子图2的权重和 LqqqqwGGNcut T ji GjGi ij 2 , 21 21 ),( 2 1 2 1 2 1 Gi dd d Gi dd d qi 令 Spectral Clustering 谱聚类 Normalized Cut 方法方法 n j ij n i i T wqDqq 11 2 21 1 2 1 2 Gi n j iji Gi n j iji wqwq 1 2 2 1 1 1 2 d

14、dd d d dd d )min(LqqT 1 . .Dqqts T Dqq Lqq qLR T T ),( 广义瑞利商 Spectral Clustering 谱聚类 Normalized Cut 方法方法 Dqq Lqq qLR T T ),( 广义瑞利商 qDDLq 2 1 2 1 2 1 2 1 DDD 2 1 2 1 LDDL qDq 2 1 2 1 2 1 LDD qD 2 1 qD 2 1 规范拉普拉斯矩阵，对角元素全为1 L Spectral Clustering 谱聚类 DqLq 为L的广义特征值 IDD 2 1 2 1 Normalized Cut 方法方法 Ratio c

15、ut Ncut与与Ratio cut区别区别 顶点数权重和 1、同子图内所有点相似度高 2、不同子图的点相似度低 Minimum Cut、Ratio cut只考虑了只考虑了1个要求个要求 21 21 11 ),( dd GGCut 21 21 11 ),( nn GGCut Ncut Ncut考虑了上面考虑了上面2个要求个要求 Spectral Clustering 谱聚类 Unnormalized Spectral Clustering步骤步骤 输入：样本及类别数K 1、根据样本建立权重矩阵W； 2、根据W，计算度矩阵D，进而计算拉普拉斯矩阵L； 3、计算L的特征值及特征向量 ； enee

16、vvvVe,., 21 4、取出前K小特征值对应的特征向量 并对 矩阵 的行向量进行聚类，得到K个Cluster ekeeK vvvV,., 21 K V Spectral Clustering 谱聚类 Normalized Spectral Clustering步骤步骤 输入：样本及类别数K 1、根据样本建立权重矩阵W； 4、取出前K小特征值对应的特征向量 并对 矩阵 的行向量进行聚类，得到K个Cluster ekeeK vvvV,., 21 K V 谱聚类可以理解为：降维过程+其他聚类方法，最终对 矩阵的行向量聚类时，仍会用其他聚类方法，比如K-means KN 2、计算拉普拉斯矩阵L及

17、2 1 2 1 LDDL 3、计算 的特征值及特征向量 ； enee vvvVe,., 21 L Spectral Clustering 谱聚类 图表示图像图表示图像 图像每个像素对应图的一个顶点 252,.,1vvvV 25,251 ,25 25,21 ,2 25,11 ,1 . : : . . ww ww ww W 2 2 2 )( , ji xx ji ew 为第i和j像素点的灰度值 ji xx, Spectral Clustering 谱聚类 实例实例 1、对图像进行超像素分割； 2、根据各超像素区域灰度平均值的相似度计算矩阵W及L； 3、计算L的特征值及特征向量 ； enee vvvVe,., 21 4、取出次小特征值对应的特征向量 ，并对进行K-means聚类， 得到2个Cluster 2e v Spectral Clustering 谱聚类 Spectral Clustering 谱聚类 实例实例 附加：松弛问题附加：松弛问题 )min(LqqT 2 . .ncqqts T qq Lqq qLR T T ),( 瑞利商 原问题是离散问题，而瑞利商计算最小值是连续问题 Gi c Gi 2 1 c qi -0.408 -0.442 -0.371 0.37