谱聚类算法讲解

SpectralClustering谱聚类1谱聚类概述谱聚类基本原理谱聚类基础谱聚类算法应用举例总结目录SpectralClustering谱聚类2SpectralClustering谱聚类谱聚类基本概念3谱：𝑌=𝐴𝑋,方阵A作为线性算子，它的所有特征值的集合称为方阵的谱。聚类(Clustering):就是要把一堆样本合理地分成两份或者K份。从图论的角度来说，聚类的问题就相当于一个图的分割问题。谱聚类：是一种基于图论的聚类方法，通过对样本数据的拉普拉斯矩阵的特征向量进行聚类。SpectralClustering谱聚类谱聚类基本思想4谱聚类目的：找到一种合理的分割图的方法，使得分割后形成若干个子图，连接不同子图的边的权重(相似度)尽可能低，同子图内的边的权重(相似度)尽可能高。5图（Graph）：由若干点及连接两点的线所构成的图形，通常用来描述某些事物之间的某种关系，用点代表事物，线表示对应两个事物间具有这种关系。1236450.80.80.80.80.60.10.20.7谱聚类基础一：图SpectralClustering谱聚类表示与之间的相似性，称作权重，对于无向图ijwivjv00ijiiww而且表示无向图，表示点集，E表示边集。(,)GVE12{,,...,}nVvvvSpectralClustering谱聚类61236450.80.80.80.80.60.10.20.7ijjiww谱聚类基础一：图•邻接矩阵：又称权重矩阵，是由任意两点之间的权重值组成的矩阵。•构建邻接矩阵的基本思想：距离较远的两个点之间的边权重值较低，而距离较近的两个点之间的边权重值较高，可以通过样本点距离度量的相似矩阵S邻接矩阵W。SpectralClustering谱聚类7W（）ijw谱聚类基础一：图-邻接矩阵SpectralClustering谱聚类8谱聚类基础一：图-邻接矩阵构建邻接矩阵主要有三种方法：•近邻法•K近邻法•全连接法W-SpectralClustering谱聚类9（1）近邻法：设置一个距离阈值，然后用欧式距离度量任意两点和的距离（相似度），然后根据与的关系来构建邻接矩阵，如下：0ijijijsws-ijsixjxijsW谱聚类基础一：图-邻接矩阵SpectralClustering谱聚类10（2）K近邻法：利用KNN算法遍历所有的样本点，取每个样本最近的K个点作为近邻，只有和样本距离最近的K个点之间的。这种方法会造成构建的权重矩阵非对称，而后面的算法需要对称邻接矩阵，为了解决这个问题，一般采取下面两种方法之一。0ijwW谱聚类基础一：图-邻接矩阵SpectralClustering谱聚类11方法一：只要一个点在另一个点的K近邻中，则保留。ijs0()()()()ijjiijjiijijjixKNNxandxKNNxwwsxKNNxorxKNNx方法二：必须两个点互为K近邻时，才保留。ijs0()()()()ijjiijjiijijjixKNNxandxKNNxwwsxKNNxandxKNNx谱聚类基础一：图-邻接矩阵SpectralClustering谱聚类12（3）全连接法：通过核函数定义边权重，常用的有多项式核函数，高斯核函数和Sigmoid核函数。使用高斯核函数构建邻接矩阵：相比前两种方法，此方法构建的邻接矩阵中所有点之间的权重值都大于0，且被普遍使用。W22exp2ijijijxxws谱聚类基础一：图-邻接矩阵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邻接矩阵W邻接矩阵：举例SpectralClustering谱聚类13SpectralClustering谱聚类14对于图中的任意一个点，它的度定义为和它相连的所有边的权重之和，即：ivid1niijjdw谱聚类基础一：图-度矩阵SpectralClustering谱聚类15利用每个点度的定义，可以得到一个的度矩阵。它是一个对角矩阵，只有主对角线有值，对应第i行第i个点的度数，如下所示：nnD12.......................................ndddD1niiijjwD谱聚类基础一：图-度矩阵1236450.80.80.80.80.60.10.20.712345611.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谱聚类16L=D-WL称为拉普拉斯矩阵，W为权重矩阵，D为度矩阵。SpectralClustering谱聚类17谱聚类基础二：Laplacian矩阵L为对称矩阵，半正定矩阵（即所有特征值非负值），最小特征值为0，且对应的特征向量为单位向量T1...11任意一个n维向量，有],...,,[21nqqqqninjjiijqqw112)(𝑞𝑇𝐿𝑞=SpectralClustering谱聚类ninjjiijqqw112)(ninjjiijninjjiijqqwqqw112211)(2ninjijininjjiijwqqqw1121122qWDqT)(2ninjjjiiijqqqqw1122)2(18谱聚类基础二：Laplacian矩阵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度矩阵DSpectralClustering谱聚类19Laplacian矩阵：举例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.5Laplacian矩阵L=D-WSpectralClustering谱聚类Laplacian矩阵：举例201236450.80.80.80.80.60.10.20.7SpectralClustering谱聚类谱聚类基础三：切图Cut图划分是指将图完全划分为若干个子图，各子图无交集：1...kGGGijGG21对于任意两个子图的集合，，定义和之间的切图权重为划分时子图之间被“截断”的边的权重和：,ABGABAB,(,)ijiAjBWABwSpectralClustering谱聚类221236450.80.80.80.80.60.10.20.7G1G212,ijiGjGw1534ww0.321211(,),2iiiCutGGWGG切图Cut:举例SpectralClustering谱聚类对于k个子图的集合，定义切图Cut为：231211(,,...),2kkiiiCutGGGWGG12{,,...}kGGG其中为的补集。iGiG谱聚类基础三：切图Cut=𝑞𝑇𝐿𝑞𝑀2图的划分问题转化为最优值问题LqqT分割要求：类内权重和最大，类间权重和最小。SpectralClustering谱聚类24如何做到上述要求？谱聚类-切图聚类谱聚类-切图聚类SpectralClustering谱聚类25MinimumCutRatioCutNormalizedCut(1)MinimumCutGicGi21cqi)min(LqqT求：212ncqqqniiTSpectralClustering谱聚类26MinimumCut划分不均衡SpectralClustering谱聚类272316450.30.80.80.60.20.20.770.70.62316450.30.80.80.60.20.20.770.70.6Cut=0.3SmallestcutCut=0.4Bestcut(1)MinimumCut(2)RatioCut21212111),(),(nnGGCutGGRcut1n、划分到子图1和子图2的顶点个数2n),(21GGRcut21,1121nnwGjGiij21221,21nnnnnnwGjGiijnnnnnwGjGiij21221,)(212121,)(21nnnnwGjGiij221222121,21nnnnnnnnwGjGiijSpectralClustering谱聚类28212121GinnnGinnniq令LqqqqwTjiGjGiij2,21),(21GGRcutSpectralClustering谱聚类29𝑅𝑐𝑢𝑡𝐺1,𝐺2,…,𝐺𝑘=𝑞𝑇𝐿𝑞=(𝑄𝑇𝐿𝑄)𝑖𝑖=𝑡𝑟𝑄𝑇𝐿𝑄𝑘𝑖=1𝑘𝑖=1二分类：k分类：𝑞𝑇𝑞=1Q矩阵中每一个指示向量都是n维的,k分类目的是找到k个最小的特征值。维度规约：n→kqqLqqqLRTT),((2)RatioCut21212111),(),(ddGGCutGGNcut21dd、表示子图1和子图2的权重和SpectralClustering谱聚类(3)NormalizedCut30212121GidddGidddqi令LqqqqwGGNcutTjiGjGiij2,2121),(LqqqqwGGNcutTjiGjGiij2,2121),(SpectralClustering谱聚类(3)NormalizedCut31)min(LqqT1..DqqtsTDqqLqqqLRTT),(广义瑞利商njijniiTwqDqq112211212GinjijiGinjijiwqwq1221112ddddddddDqqLqqqLRTT),(广义瑞利商qDDLq21212121LDDLqDq21规范拉普拉斯矩阵，对角元素全为1LSpectralClustering谱聚类DqLq为L的广义特征值2121LDDqD21qD21IDD212132(3)NormalizedCut分类输入根据Laplacian矩阵是否规范，可将谱聚类分为两种：UnnormalizedSpectralClustering•RatioCut•MinimumCutNormalizedSpectralClustering•NormalizedCutSpectralClustering谱聚类33UnnormalizedSpectralClustering步骤输入：样本及类别数K1、根据样本建立