谱聚类算法讲解课件.ppt

《谱聚类算法讲解课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、SpectralClustering谱聚类1谱聚类概述谱聚类基本原理谱聚类基础谱聚类算法应用举例总结目录SpectralClustering谱聚类2SpectralClustering谱聚类谱聚类基本概念3谱：,方阵A作为线性算子，它的所有特征值的集合称为方阵的谱。聚类(Clustering):就是要把一堆样本合理地分成两份或者K份。从图论的角度来说，聚类的问题就相当于一个图的分割问题。谱聚类：是一种基于图论的聚类方法，通过对样本数据的拉普拉斯矩阵的特征向量进行聚类。SpectralClustering谱聚类谱聚类基本思想4

2、谱聚类目的：找到一种合理的分割图的方法，使得分割后形成若干个子图，连接不同子图的边的权重(相似度)尽可能低，同子图内的边的权重(相似度)尽可能高。5图（Graph）：由若干点及连接两点的线所构成的图形，通常用来描述某些事物之间的某种关系，用点代表事物，线表示对应两个事物间具有这种关系。1236450.80.80.80.80.60.10.20.7谱聚类基础一：图SpectralClustering谱聚类表示与之间的相似性，称作权重，对于无向图而且表示无向图，表示点集，E表示边集。SpectralClustering谱聚类612

3、36450.80.80.80.80.60.10.20.7谱聚类基础一：图邻接矩阵：又称权重矩阵，是由任意两点之间的权重值组成的矩阵。构建邻接矩阵的基本思想：距离较远的两个点之间的边权重值较低，而距离较近的两个点之间的边权重值较高，可以通过样本点距离度量的相似矩阵S邻接矩阵W。SpectralClustering谱聚类7谱聚类基础一：图-邻接矩阵SpectralClustering谱聚类8谱聚类基础一：图-邻接矩阵构建邻接矩阵主要有三种方法：近邻法K近邻法全连接法SpectralClustering谱聚类9（1）近邻法：设置一

4、个距离阈值，然后用欧式距离度量任意两点和的距离（相似度），然后根据与的关系来构建邻接矩阵，如下：谱聚类基础一：图-邻接矩阵SpectralClustering谱聚类10（2）K近邻法：利用KNN算法遍历所有的样本点，取每个样本最近的K个点作为近邻，只有和样本距离最近的K个点之间的。这种方法会造成构建的权重矩阵非对称，而后面的算法需要对称邻接矩阵，为了解决这个问题，一般采取下面两种方法之一。谱聚类基础一：图-邻接矩阵SpectralClustering谱聚类11方法一：只要一个点在另一个点的K近邻中，则保留。方法二：必须两个点

5、互为K近邻时，才保留。谱聚类基础一：图-邻接矩阵SpectralClustering谱聚类12（3）全连接法：通过核函数定义边权重，常用的有多项式核函数，高斯核函数和Sigmoid核函数。使用高斯核函数构建邻接矩阵：相比前两种方法，此方法构建的邻接矩阵中所有点之间的权重值都大于0，且被普遍使用。谱聚类基础一：图-邻接矩阵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

6、.00.80.750.10.00.00.80.00.860.00.00.00.70.80.0邻接矩阵W邻接矩阵：举例SpectralClustering谱聚类13SpectralClustering谱聚类14对于图中的任意一个点，它的度定义为和它相连的所有边的权重之和，即：谱聚类基础一：图-度矩阵SpectralClustering谱聚类15利用每个点度的定义，可以得到一个的度矩阵。它是一个对角矩阵，只有主对角线有值，对应第i行第i个点的度数，如下所示：谱聚类基础一：图-度矩阵1236450.80.80.80.80.60.1

7、0.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称为拉普拉斯矩阵，W为权重矩阵，D为度矩阵。SpectralClustering谱聚类17谱聚类基础二：Laplacian矩阵L为对称矩阵，半正定矩阵（即所有特征值非负值），最小特征值为0，且对应的特征向量为单

8、位向量任意一个n维向量，有=SpectralClustering谱聚类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.0