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

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

两个子图（设G有n个顶点）其中D为对角矩阵SpectralClustering谱聚类Laplacian矩阵再定义一个L矩阵L称为拉普拉斯矩阵，W为权重矩阵（也称邻接矩阵），D为度矩阵SpectralClustering谱聚类Laplacian矩阵L为半正定矩阵（即所有特征值非负值），最小特征值为0，且对应的特征向量为单位向量损失函数SpectralClustering谱聚类Laplacian矩阵图的划分问题转化为条件最小值问题SpectralClustering谱聚类条件1236450.80.80.80.80.60.10.20.712345610.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举例SpectralClustering谱聚类12345610.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度矩阵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-WSpectralClustering谱聚类举例MinimumCut方法求：条件：SpectralClustering谱聚类瑞利商:性质：的最小值，次小值……最大值分别在q为L的最小特征值，次小特征值……最大特征值对应的特征向量时取得求L次小特征值所对应的特征向量SpectralClustering谱聚类MinimumCut方法12345611.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拉普拉斯矩阵L1234560.408-0.408-0.647-0.306-0.3790.1060.408-0.4420.0140.3050.7060.2150.408-0.3710.6380.045-0.388-0.3680.4080.3710.339-0.455-0.0010.6120.4080.405-0.167-0.3050.351-0.6520.4080.445-0.1780.716-0.2890.087-0.408-0.442-0.3710.3710.4050.4451236450.80.80.80.80.60.10.20.7G1G2次小特征值的特征向量SpectralClustering谱聚类举例2316450.30.80.80.60.20.20.770.70.6MinimumCut划分不均衡SpectralClustering谱聚类MinimumCut方法RatioCut方法、划分到子图1和子图2的顶点个数SpectralClustering谱聚类令SpectralClustering谱聚类RatioCut方法瑞利商SpectralClustering谱聚类RatioCut方法子图1和子图2的权重和令SpectralClustering谱聚类NormalizedCut方法广义瑞利商SpectralClustering谱聚类NormalizedCut方法广义瑞利商

规范拉普拉斯矩阵，对角元素全为1SpectralClustering谱聚类为L的广义特征值NormalizedCut方法RatiocutNcut与Ratiocut区别顶点数权重和1、同子图内所有点相似度高2、不同子图的点相似度低MinimumCut、Ratiocut只考虑了1个要求NcutNcut考虑了上面2个要求SpectralClustering谱聚类UnnormalizedSpectralClustering步骤输入：样本及类别数K1、根据样本建立权重矩阵W；2、根据W，计算度矩阵D，进而计算拉普拉斯矩阵L；3、计算L的特征值及特征向量；4、取出前K小特征值对应的特征向量并对矩阵的行向量进行聚类，得到K个ClusterSpectralClustering谱聚类NormalizedSpectralClustering步骤输入：样本及类别数K1、根据样本建立权重矩阵W；4、取出前K小特征值对应的特征向量并对矩阵的行向量进行聚类，得到K个Cluster谱聚类可以理解为：降维过程+其他聚类方法，最终对矩阵的行向量聚类时，仍会用其他聚类方法，比如K-means2、计算拉普拉斯矩阵L及3、计算

的特征值及特征向量；SpectralClustering谱聚类图表示图像图像每个像素对应图的一个顶点为第i和j像素点的灰度值SpectralClustering谱聚类实例1、对图像进行超像素分割；2、根据各超像素区域灰度平均值的相似度计算矩阵W及L；3、计算L的特征值及特征向量；4、取出次小特征值对应的特征向量，并对进行K-means聚类，得到2个ClusterSpectralClustering谱聚类SpectralClustering谱聚类实例附加：松弛问题瑞利商原问题是离散问题，而瑞利商计算最小值是连续问题-0.408-0.442-0.3710.3710.4050.445Thereasonwhythespectralrelaxationissoappealingisnotthatitleadstoparticularly