谱聚类详细、入门级介绍

谱聚类：是一种基于图论的聚类方法，通过对样本数据的拉普拉斯矩阵的特征向量进行聚类。图（Graph）：由若干点及连接两点的线所构成的图形，通常用来描述某些事物之间的某种关系，用点代表事物，线表示对应两个事物间具有这种关系。1236450.80.80.80.80.60.10.20.7SpectralClustering谱聚类概念图的表示表示与之间的关系，称作权重，对于无向图jiijwwijwivjv00ijiiww而且表示无向图，表示点集，E表示边集),(EVG}{,...,2,1nvvvVSpectralClustering谱聚类1236450.80.80.80.80.60.10.20.7SpectralClustering谱聚类图的划分图划分是指将图完全划分为若干个子图，各子图无交集同子图内的点相似度高不同子图的点相似度低1236450.80.80.80.80.60.10.20.7划分要求G1G2GGGk...1jiGGSpectralClustering谱聚类划分时子图之间被“截断”的边的权重和1236450.80.80.80.80.60.10.20.7G1G221,21),(GjGiijwGGCut损失函数Laplacian矩阵GiGi2211ccqi221112,21)(2)(),(21ccqqwwGGCutninjjiijGjGiij损失函数定义是一个n维向量，用来表示划分方案],...,,[21nqqqqSpectralClustering谱聚类假设G(V，E)被划分成两个子图（设G有n个顶点）21,GG],,,,,[222111ccccccqninjjiijqqw112)(ninjjiijninjjiijqqwqqw112211)(2ninjijininjjiijwqqqw1121122qWDqT)(2其中D为对角矩阵njijiiwD1SpectralClustering谱聚类ninjjjiiijqqqqw1122)2(Laplacian矩阵qWDqqqwTninjjiij)(2)(112再定义一个L矩阵WDLL称为拉普拉斯矩阵，W为权重矩阵（也称邻接矩阵），D为度矩阵LqqqqwTninjjiij2)(112SpectralClustering谱聚类Laplacian矩阵0)(21112ninjjiijTqqwLqqL为半正定矩阵（即所有特征值非负值），最小特征值为0，且对应的特征向量为单位向量T1...1122121)(),(ccLqqGGCutT损失函数221112,21)(2)(),(21ccqqwwGGCutninjjiijGjGiijSpectralClustering谱聚类Laplacian矩阵图的划分问题转化为条件最小值问题LqqTSpectralClustering谱聚类22121)(),(ccLqqGGCutT条件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方法GicGi21cqi)min(LqqT求：条件：212ncqqqniiTSpectralClustering谱聚类)min(LqqT2..ncqqtsTqqLqqqLRTT),(瑞利商:性质：的最小值，次小值……最大值分别在q为L的最小特征值，次小特征值……最大特征值对应的特征向量时取得),(qLR求L次小特征值所对应的特征向量SpectralClustering谱聚类MinimumCut方法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拉普拉斯矩阵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方法21212111),(),(nnGGCutGGRcut1n、划分到子图1和子图2的顶点个数2n),(21GGRcut21,1121nnwGjGiij21221,21nnnnnnwGjGiijnnnnnwGjGiij21221,)(212121,)(21nnnnwGjGiij221222121,21nnnnnnnnwGjGiijSpectralClustering谱聚类212121GinnnGinnnqi令niiTqqq1221221,21nnnnnnwGjGiij),(21GGRcutLqqqqwTjiGjGiij2,21),(21GGRcutSpectralClustering谱聚类2122GiiGiiqq1212121nnnnnnnnRatioCut方法)min(LqqT1..qqtsTqqLqqqLRTT),(瑞利商SpectralClustering谱聚类RatioCut方法21212111),(),(ddGGCutGGNcut21dd、子图1和子图2的权重和LqqqqwGGNcutTjiGjGiij2,2121),(212121GidddGidddqi令SpectralClustering谱聚类NormalizedCut方法njijniiTwqDqq112211212GinjijiGinjijiwqwq1221112dddddddd)min(LqqT1..DqqtsTDqqLqqqLRTT),(广义瑞利商SpectralClustering谱聚类NormalizedCut方法DqqLqqqLRTT),(广义瑞利商qDDLq21212121DDD2121LDDLqDq212121LDDqD21qD21规范拉普拉斯矩阵，对角元素全为1LSpectralClustering谱聚类DqLq为L的广义特征值IDD2121NormalizedCut方法RatiocutNcut与Ratiocut区别顶点数权重和1、同子图内所有点相似度高2、不同子图的点相似度低MinimumCut、Ratiocut只考虑了1个要求212111),(ddGGCut212111),(nnGGCutNcutNcut考虑了上面2个要求SpectralClustering谱聚类UnnormalizedSpectralClustering步骤输入：样本及类别数K1、根据样本建立权重矩阵W；2、根据W，计算度矩阵D，进而计算拉普拉斯矩阵L；3、计算L的特征值及特征向量；eneevvvVe,...,,214、取出前K小特征值对应的特征向量并对矩阵的行向量进行聚类，得到K个ClusterekeeKvvvV,...,,21KVSpectralClustering谱聚类NormalizedSpectralClustering步骤输入：样本及类别数K1、根据样本建立权重矩阵W；4、取出前K小特征值对应的特征向量并对矩阵的行向量进行聚类，得到K个ClusterekeeKvvvV,...,,21KV谱聚类可以理解为：降维过程+其他聚类方法，最终对矩阵的行向量聚类时，仍会用其他聚类方法，比如K-meansKN2、计算拉普拉斯矩阵L及2121LDDL3、计算的特征值及特征向量；eneevvvVe,...,,21LSpectralClustering谱聚类图表示图像图像每个像素对应图的一个顶点}{252,...,,1vvvV25,251,2525,21,225,11,1......::::............222)(,jixxjiew为第i和j像素点的灰度值jixx,SpectralClustering谱聚类实例1、对图像进行超像素分割；2、根据各超像素区域灰度平均值的相似度计算矩阵W及L；3、计算L的特征值及特征向量；eneevvvVe,...,,214、取出次小特征值对应的特征向量，并对进行K-means聚类，得到2个Cluster2evSpectralClustering谱聚类SpectralClustering谱聚类实例附加：松弛问题)min(LqqT2..ncqqtsTqqLqqqLRTT),(瑞利商原问题是离散问题，而瑞利商计算最小值是连续问题GicGi21cqi-0.408-0.442-0.3710.3710.4050.445Thereasonwhythespectralrelaxationissoappealingisnotthatitleadstoparticularlygoodsolutions.Itspopularityismainlyduetothefactthatitresultsinastandardlinearalgebraproblemwhichissi