谱聚类详细、入门级介绍讲课稿.ppt

《谱聚类详细、入门级介绍讲课稿.ppt》由会员分享，可在线阅读，更多相关《谱聚类详细、入门级介绍讲课稿.ppt（28页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、谱聚类详细、入门级介绍Spectral Clustering 谱聚类图的划分图的划分图划分是指将图完全划分为若干个子图，各子图无交集同子图内的点相似度高不同子图的点相似度低1236450.80.80.80.80.60.10.20.7划分要求划分要求G1G2Spectral Clustering 谱聚类划分时子图之间被“截断”的边的权重和1236450.80.80.80.80.60.10.20.7G1G2损失函数损失函数Laplacian矩矩阵阵损失函数定义 是一个n维向量，用来表示划分方案Spectral Clustering 谱聚类假设 G(V，E)被划分成 两个子图（设G有n个顶点）其中D

2、为对角矩阵Spectral Clustering 谱聚类Laplacian矩矩阵阵再定义一个 L 矩阵L 称为拉普拉斯矩阵，W 为权重矩阵（也称邻接矩阵），D 为度矩阵Spectral Clustering 谱聚类Laplacian矩矩阵阵L为半正定矩阵（即所有特征值非负值），最小特征最小特征值为值为0，且且对应对应的特征向量的特征向量为单为单位向量位向量损失函数损失函数Spectral Clustering 谱聚类Laplacian矩矩阵阵图的划分问题转化为 条件条件最小值问题Spectral Clustering 谱聚类条件条件1236450.80.80.80.80.60.10.20.71

3、2345610.00.80.60.00.10.020.80.00.80.00.00.030.60.80.00.20.00.040.00.00.20.00.80.750.10.00.00.80.00.860.00.00.00.70.80.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.00.00.01.70.060.00.00.00.00.01.5度矩阵D举举例例Spectral Clustering 谱聚类12345610.00.80.60.00.10.0

4、20.80.00.80.00.00.030.60.80.00.20.00.040.00.00.20.00.80.750.10.00.00.80.00.860.00.00.00.70.80.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.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

5、.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方法方法求：条件：Spectral Clustering 谱聚类瑞利商:性质：的最小值，次小值最大值分别在q为L的最小特征值，次小特征值最大特征值对应的特征向量时取得求求L次小次小特征特征值值所所对应对应的特征向量的特征向量Spectral Clustering 谱聚类Minimum Cut方法方法12345611.5-0.8-0.60.0-0.10.02-0.81.6-0.80

6、.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拉普拉斯矩阵L1234560.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

7、.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.4451236450.80.80.80.80.60.10.20.7G1G2次小次小特征特征值值的特征向量的特征向量Spectral Clustering 谱聚类举举例例2316450.30.80.80.60.20.20.770.70.6Minimum Cut划分不均衡Spectral Clustering 谱聚类Minimum Cut方法方法Ratio Cut 方法方法、划分到子图1和子图2的顶点个

8、数Spectral Clustering 谱聚类令Spectral Clustering 谱聚类Ratio Cut 方法方法瑞利商Spectral Clustering 谱聚类Ratio Cut 方法方法子图1和子图2的权重和令Spectral Clustering 谱聚类Normalized Cut 方法方法广义瑞利商Spectral Clustering 谱聚类Normalized Cut 方法方法广义瑞利商 规范拉普拉斯矩阵，对角元素全为1Spectral Clustering 谱聚类为L的广义特征值Normalized Cut 方法方法Ratio cutNcut与与Ratio cut区

9、区别别顶点数权重和1、同子图内所有点相似度高2、不同子图的点相似度低Minimum Cut、Ratio cut只考只考虑虑了了1个要求个要求NcutNcut考考虑虑了上面了上面2个要求个要求Spectral Clustering 谱聚类Unnormalized Spectral Clustering步步骤骤输入：样本及类别数K1、根据样本建立权重矩阵W；2、根据W，计算度矩阵D，进而计算拉普拉斯矩阵L；3、计算L的特征值及特征向量 ；4、取出前K小特征值对应的特征向量 并对矩阵 的行向量进行聚类，得到K个ClusterSpectral Clustering 谱聚类Normalized Spec

10、tral Clustering步步骤骤输入：样本及类别数K1、根据样本建立权重矩阵W；4、取出前K小特征值对应的特征向量 并对矩阵 的行向量进行聚类，得到K个Cluster谱聚类可以理解为：降维过程+其他聚类方法，最终对 矩阵的行向量聚类时，仍会用其他聚类方法，比如K-means2、计算拉普拉斯矩阵L及3、计算 的特征值及特征向量 ；Spectral Clustering 谱聚类图表示图像图表示图像图像每个像素对应图的一个顶点为第i和j像素点的灰度值Spectral Clustering 谱聚类实例实例1、对图像进行超像素分割；2、根据各超像素区域灰度平均值的相似度计算矩阵W及L；3、计算L的

11、特征值及特征向量 ；4、取出次小特征值对应的特征向量 ，并对进行K-means聚类，得到2个ClusterSpectral Clustering 谱聚类Spectral Clustering 谱聚类实例实例附加：松弛问题附加：松弛问题瑞利商原问题是离散问题，而瑞利商计算最小值是连续问题-0.408-0.442-0.3710.3710.4050.445The reason why the spectral relaxation is so appealing is not that it leads to particularly good solutions.Its popularity is mainly due to the fact that it results in a standard linear algebra problem which is simple to solve.Spectral Clustering 谱聚类-c-c-cccc此课件下载可自行编辑修改，仅供参考！此课件下载可自行编辑修改，仅供参考！感谢您的支持，我们努力做得更好！谢谢感谢您的支持，我们努力做得更好！谢谢