《谱聚类算法讲解ppt课件.pptx》由会员分享，可在线阅读，更多相关《谱聚类算法讲解ppt课件.pptx（43页珍藏版）》请在三一办公上搜索。
1、Spectral Clustering 谱聚类,1,谱聚类概述谱聚类基本原理谱聚类基础谱聚类算法应用举例总结,目录,Spectral Clustering 谱聚类,2,Spectral Clustering 谱聚类,谱聚类基本概念,3,谱：=, 方阵 A 作为线性算子，它的所有特征值的集合称为方阵的谱。聚类(Clustering): 就是要把一堆样本合理地分成两份或者K份。从图论的角度来说，聚类的问题就相当于一个图的分割问题。,谱聚类：是一种基于图论的聚类方法，通过对样本 数据的拉普拉斯矩阵的特征向量进行聚类。,Spectral Clustering 谱聚类,谱聚类基本思想,4,谱聚类目的：
2、找到一种合理的分割图的方法，使得分割后形成若干个子图，连接不同子图的边的权重(相似度)尽可能低，同子图内的边的权重(相似度)尽可能高。,5,图（Graph）：由若干点及连接两点的线所构成的图形，通常用来描述某些事物之间的某种关系，用点代表事物，线表示对应两个事物间具有这种关系。,谱聚类基础一：图,Spectral Clustering 谱聚类,表示无向图， 表示点集，E表示边集。,Spectral Clustering 谱聚类,6,谱聚类基础一：图,邻接矩阵 ：又称权重矩阵，是由任意两点之间的权重值 组成的矩阵。构建邻接矩阵的基本思想： 距离较远的两个点之间的边权重值较低，而距离较近的两个点之
3、间的边权重值较高，可以通过样本点距离度量的相似矩阵S 邻接矩阵W。,Spectral Clustering 谱聚类,7,谱聚类基础一：图-邻接矩阵,Spectral Clustering 谱聚类,8,谱聚类基础一：图-邻接矩阵,构建邻接矩阵 主要有三种方法 ： 近邻法 K近邻法全连接法,Spectral Clustering 谱聚类,9,（1） 近邻法： 设置一个距离阈值 ，然后用欧式距离 度量任意两点 和 的距离（相似度），然后根据 与 的关系来构建邻接矩阵 ，如下：,谱聚类基础一：图-邻接矩阵,Spectral Clustering 谱聚类,10,（2）K近邻法： 利用KNN算法遍历所有的
4、样本点，取每个样本最近的K个点作为近邻，只有和样本距离最近的K个点之间的 。 这种方法会造成构建的权重矩阵 非对称，而后面的算法需要对称邻接矩阵，为了解决这个问题，一般采取下面两种方法之一。,谱聚类基础一：图-邻接矩阵,Spectral Clustering 谱聚类,11,方法一：只要一个点在另一个点的K近邻中，则保留 。,方法二：必须两个点互为K近邻时，才保留 。,谱聚类基础一：图-邻接矩阵,Spectral Clustering 谱聚类,12,（3）全连接法： 通过核函数定义边权重，常用的有多项式核函数，高斯核函数和Sigmoid核函数。使用高斯核函数构建邻接矩阵： 相比前两种方法，此方法
5、构建的邻接矩阵 中所有点之间的权重值都大于0，且被普遍使用。,谱聚类基础一：图-邻接矩阵,邻接矩阵W,邻接矩阵：举例,Spectral Clustering 谱聚类,13,Spectral Clustering 谱聚类,14,对于图中的任意一个点 ，它的度 定义为和它相连的所有边的权重之和，即：,谱聚类基础一：图-度矩阵,Spectral Clustering 谱聚类,15,利用每个点度的定义，可以得到一个 的度矩阵 。它是一个对角矩阵，只有主对角线有值，对应第i行第i个点的度数，如下所示：,谱聚类基础一：图-度矩阵,度矩阵D,度矩阵：举例,Spectral Clustering 谱聚类,16
6、,L 称为拉普拉斯矩阵，W 为权重矩阵，D 为度矩阵。,Spectral Clustering 谱聚类,17,谱聚类基础二：Laplacian矩阵,L为对称矩阵，半正定矩阵（即所有特征值非负值），最小特征值为0，且对应的特征向量为单位向量,任意一个n维向量，有, =,Spectral Clustering 谱聚类,18,谱聚类基础二：Laplacian矩阵,邻接矩阵W,度矩阵D,Spectral Clustering 谱聚类,19,Laplacian矩阵：举例,Laplacian矩阵L=D-W,Spectral Clustering 谱聚类,Laplacian矩阵：举例,20,Spectral
7、 Clustering 谱聚类,谱聚类基础三：切图Cut,图划分是指将图完全划分为若干个子图，各子图无交集：,21,对于任意两个子图的集合 ， ，定义 和 之间的切图权重为划分时子图之间被“截断”的边的权重和：,Spectral Clustering 谱聚类,22,切图Cut : 举例,Spectral Clustering 谱聚类,对于k个子图的集合 ，定义切图Cut为：,23,其中 为 的补集。,谱聚类基础三：切图Cut,= 2,图的划分问题转化为 最优值问题,分割要求 ： 类内权重和最大，类间权重和最小。,Spectral Clustering 谱聚类,24,如何做到上述要求？,谱聚类
8、- 切图聚类,谱聚类 - 切图聚类,Spectral Clustering 谱聚类,25,Minimum Cut Ratio Cut Normalized Cut,(1) Minimum Cut,求：,Spectral Clustering 谱聚类,26,Minimum Cut划分不均衡,Spectral Clustering 谱聚类,27,Cut = 0.3Smallest cut,Cut = 0.4Best cut,(1) Minimum Cut,(2) Ratio Cut,、 划分到子图1和子图2的顶点个数,Spectral Clustering 谱聚类,28,令,Spectral Cl
9、ustering 谱聚类,29, 1 , 2 , = =1 = =1 ( )= ,二分类：,k分类：, =1,Q矩阵中每一个指示向量都是n维的, k分类目的是找到k个最小的特征值。维度规约：n k,(2) Ratio Cut,表示子图1和子图2的权重和,Spectral Clustering 谱聚类,(3) Normalized Cut,30,令,Spectral Clustering 谱聚类,(3) Normalized Cut,31,广义瑞利商,广义瑞利商,规范拉普拉斯矩阵，对角元素全为1,Spectral Clustering 谱聚类,为L的广义特征值,32,(3) Normalized
10、 Cut,分类,输入根据Laplacian矩阵是否规范，可将谱聚类分为两种：,Unnormalized Spectral ClusteringRatio Cut Minimum CutNormalized Spectral ClusteringNormalized Cut,Spectral Clustering 谱聚类,33,Unnormalized Spectral Clustering步骤,输入：样本及类别数K,1、根据样本建立权重矩阵W；,2、根据W，计算度矩阵D，进而计算拉普拉斯矩阵L；,3、计算L的特征值及特征向量 ；,Spectral Clustering 谱聚类,34,Norma
11、lized Spectral Clustering步骤,输入：样本及类别数K,1、根据样本建立权重矩阵W；,谱聚类可以理解为：降维过程+其他聚类方法，最终对 矩阵的行向量聚类时，仍会用其他聚类方法，比如K-means,2、计算拉普拉斯矩阵L及,3、计算 的特征值及特征向量 ；,Spectral Clustering 谱聚类,35,实例展示,Spectral Clustering 谱聚类,36,首先生成500个3维的数据集，分为5个簇。,实例展示,Spectral Clustering 谱聚类,37,实例展示,Spectral Clustering 谱聚类,38,聚成5个类,实例展示,Spect
12、ral Clustering 谱聚类,39,使用高斯核函数，对n_clusters和gamma进行调参,实例展示,Spectral Clustering 谱聚类,40,使用高斯核函数，对n_clusters和gamma进行调参,优点：1）谱聚类只需要数据之间的相似度矩阵，因此对于处理稀疏数据的聚类很有效。这点传统聚类算法比如K-Means很难做到。2）由于使用了降维，因此在处理高维数据聚类时的复杂度比传统聚类算法好。,总结,41,缺点：1）如果最终聚类的维度非常高，则由于降维的幅度不够，谱聚类的运行速度和最后的聚类效果均不好。2) 聚类效果依赖于相似矩阵，不同的相似矩阵得到的最终聚类效果可能很不同。,42,总结,43,谢谢大家,
