谱聚类详细、入门级介绍

1、谱聚类：是一种基于图论的聚类方法，通过对样本数据的拉普拉拉普拉斯矩阵斯矩阵的特征向量特征向量进行聚类。图（Graph）：由若干点及连接两点的线所构成的图形，通常用来描述某些事物之间的某种关系，用点代表事物，线表示对应两个事物间具有这种关系。123640.20.7Spectral Clustering 谱聚类概念概念图的表示图的表示表示 与 之间的关系，称作权重，对于无向图jiijwwijwivjv0 0ijiiww而且表示无向图， 表示点集，E表示边集),(EVG,.,2,1nvvvV Spectral Clustering 谱聚类1236450.80.8

2、Spectral Clustering 谱聚类图的划分图的划分图划分是指将图完全划分为若干个子图，各子图无交集同子图内的点相似度高不同子图的点相似度低123640.20.7划分要求划分要求G1G2GGGk.1jiGGSpectral Clustering 谱聚类划分时子图之间被“截断”的边的权重和123640.20.7G1G221,21),(GjGiijwGGCut损失函数损失函数Laplacian矩阵矩阵 Gi Gi 2211ccqi221112,21)( 2)(),(21ccqq

3、wwGGCutninjjiijGjGiij损失函数定义 是一个n维向量，用来表示划分方案,.,21nqqqq Spectral Clustering 谱聚类假设 G(V，E)被划分成 两个子图（设G有n个顶点）21,GG,222111ccccccq ninjjiijqqw112)(ninjjiijninjjiijqqwqqw112211)(2ninjijininjjiijwqqqw1121122qWDqT)(2其中D为对角矩阵njijiiwD1Spectral Clustering 谱聚类ninjjjiiijqqqqw1122)2(Laplacian矩阵矩阵qWDqqqwTninjjiij)(

4、2)(112再定义一个 L 矩阵WDLL 称为拉普拉斯矩阵，W 为权重矩阵（也称邻接矩阵），D 为度矩阵LqqqqwTninjjiij2)(112Spectral Clustering 谱聚类Laplacian矩阵矩阵0)(21112ninjjiijTqqwLqqL为半正定矩阵（即所有特征值非负值），最小特征值为最小特征值为0， 且对应的特征向量为单位向量且对应的特征向量为单位向量T1.1122121)(),(ccLqqGGCutT损失函数损失函数221112,21)(2)(),(21ccqqwwGGCutninjjiijGjGiijSpectral Clustering 谱聚类Laplaci

5、an矩阵矩阵图的划分问题转化为 条件条件最小值问题LqqTSpectral Clustering 谱聚类22121)(),(ccLqqGGCutT条件条件123640.20.712345610.00.10. 020.80.00.80.00.00.00.20.00.040.00.00.20.00.80.750.10.00.00.80.00.860.00.00.0邻接矩阵W12345611.50.00.00.00.00. 020.01.60.00.00.00.030.00.01.60.00.00.040.

6、00.00.01.70.00.050.00.00.00.01.70.060.00.00.00.00.01.5度矩阵D举例举例Spectral Clustering 谱聚类12345610.00.10. 020.80.00.80.00.00.00.20.00.040.00.00.20.00.80.750.10.00.00.80.00.860.00.00.0邻接矩阵W12345611.50.00.00.00.00. 020.01.60.00.00.00.030.00.01.60.00.00.040.00.00.01.70.00.050.00.

7、00.00.01.70.060.00.00.00.00.01.5度矩阵D12345611.5-0.8-0.60.0-0.10. 02-0.81.6-0.80.00.00.03-0.6-0.81.6-0.20.00.040.00.0-0.21.7-0.8-0.75-0.10.00.0-0.81.7-0.860.00.00.0-0.7-0.81.5拉普拉斯矩阵L=D-WSpectral Clustering 谱聚类举例举例Minimum Cut方法方法 Gi c Gi 21cqi)min(LqqT求：条件：212ncqqqniiTSpectral Clustering 谱聚类)min(LqqT2

8、. .ncqqtsTqqLqqqLRTT),(瑞利商:性质： 的最小值，次小值最大值分别在q为L的最小特征值，次小特征值最大特征值对应的特征向量时取得),(qLR求求L次小次小特征值所对应的特征向量特征值所对应的特征向量Spectral Clustering 谱聚类Minimum Cut方法方法 GG12345611.5-0.8-0.60.0-0.10. 02-0.81.6-0.80.00.00.03-0.6-0.81.6-0.20.00.040.00.0-0.21.7-0.8-0.75-0.10.00.0-0.81.7-0.860.00.00.0-0.7-0.81.5拉普拉斯矩阵L12345

9、60.408-0.408-0.408-0.647-0.306-0.3790.1060.408-0.442-0.4420.0140.3050.7060.2150.408-0.371-0.3710.6380.045-0.388-0.3680.4080.3710.3710.339-0.455-0.0010.6120.4080.4050.405-0.167-0.3050.351-0.6520.4080.4450.445-0.1780.716-0.2890.087-0.408-0.408-0.442-0.442-0.371-0.3710.3710.3710.4050.4050.4450.44512364

10、0.20.7G1G2次小次小特征值的特征向量特征值的特征向量Spectral Clustering 谱聚类举例举例231640.770.70.6Minimum Cut划分不均衡Spectral Clustering 谱聚类Minimum Cut方法方法Ratio Cut 方法方法21212111),(),(nnGGCutGGRcut1n、 划分到子图1和子图2的顶点个数2n),(21GGRcut21,1121nnwGjGiij21221,21nnnnnnwGjGiijnnnnnwGjGiij21221,)(212121

11、,)(21nnnnwGjGiij221222121,21nnnnnnnnwGjGiijSpectral Clustering 谱聚类 212121Gi nnnGinnnqi令niiTqqq1221221,21nnnnnnwGjGiij),(21GGRcutLqqqqwTjiGjGiij2,21),(21GGRcutSpectral Clustering 谱聚类2122GiiGiiqq1212121nnnnnnnnRatio Cut 方法方法)min(LqqT1 . .qqtsTqqLqqqLRTT),(瑞利商Spectral Clustering 谱聚类Ratio Cut 方法方法212121

12、11),(),(ddGGCutGGNcut21dd、子图1和子图2的权重和LqqqqwGGNcutTjiGjGiij2,2121),( 212121Gi dddGidddqi令Spectral Clustering 谱聚类Normalized Cut 方法方法njijniiTwqDqq112211212GinjijiGinjijiwqwq1221112dddddddd)min(LqqT1 . .DqqtsTDqqLqqqLRTT),(广义瑞利商Spectral Clustering 谱聚类Normalized Cut 方法方法DqqLqqqLRTT),(广义瑞利商qDDLq21212121DD

13、D 2121LDDLqDq212121LDDqD21qD21 规范拉普拉斯矩阵，对角元素全为1LSpectral Clustering 谱聚类DqLq为L的广义特征值IDD2121Normalized Cut 方法方法Ratio cutNcut与与Ratio cut区别区别顶点数权重和1、同子图内所有点相似度高2、不同子图的点相似度低Minimum Cut、Ratio cut只考虑了只考虑了1个要求个要求212111),(ddGGCut212111),(nnGGCutNcutNcut考虑了上面考虑了上面2个要求个要求Spectral Clustering 谱聚类Unnormalized Spe

14、ctral Clustering步骤步骤输入：样本及类别数K1、根据样本建立权重矩阵W；2、根据W，计算度矩阵D，进而计算拉普拉斯矩阵L；3、计算L的特征值及特征向量 ；eneevvvVe,., 214、取出前K小特征值对应的特征向量 并对矩阵 的行向量进行聚类，得到K个ClusterekeeKvvvV,., 21KVSpectral Clustering 谱聚类Normalized Spectral Clustering步骤步骤输入：样本及类别数K1、根据样本建立权重矩阵W；4、取出前K小特征值对应的特征向量 并对矩阵 的行向量进行聚类，得到K个ClusterekeeKvvvV,., 21K

15、V谱聚类可以理解为：降维过程+其他聚类方法，最终对 矩阵的行向量聚类时，仍会用其他聚类方法，比如K-meansKN 2、计算拉普拉斯矩阵L及2121LDDL3、计算 的特征值及特征向量 ；eneevvvVe,., 21LSpectral Clustering 谱聚类图表示图像图表示图像图像每个像素对应图的一个顶点252,.,1vvvV 25,251 ,2525,21 ,225,11 ,1.:.wwwwwwW 222)(,jixxjiew为第i和j像素点的灰度值jixx,Spectral Clustering 谱聚类实例实例1、对图像进行超像素分割；2、根据各超像素区域灰度平均值的相似度计算矩阵W及L；3、计算L的特征值及特征向量 ；eneevvvVe,., 214、取出次小特征值对应的特征向量 ，并对进行K-means聚类， 得到2个Cluster2evSpectral Clustering 谱聚类Spectral Clustering 谱聚类实例实例附加：松弛问题附加：松弛问题)min(LqqT2 . .ncqqtsTqqLqqqLRTT),(瑞利商原问题是离散问题，而瑞利商计算最小值是连续问题 Gi c Gi 21cqi-0.408-0.442-0.3710.3710.4050.445The reaso