谱聚类详细、入门级介绍.ppt

《谱聚类详细、入门级介绍.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、谱聚类：是一种基于图论的聚类方法，通过对样本数据的拉普拉斯矩阵的特征向量进行聚类。图（Graph）：由若干点及连接两点的线所构成的图形，通常用来描述某些事物之间的某种关系，用点代表事物，线表示对应两个事物间具有这种关系。1236450.80.80.80.80.60.10.20.7SpectralClustering谱聚类概念图的表示表示与之间的关系，称作权重，对于无向图而且表示无向图，表示点集，E表示边集SpectralClustering谱聚类1236450.80.80.80.80.60.10.20.7SpectralClustering谱聚类图的划分图划分是指将图完全划分为若干个

2、子图，各子图无交集同子图内的点相似度高不同子图的点相似度低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为权重矩阵（也称邻接矩阵）

3、，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

4、.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.5

5、0.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方

6、法求：条件：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.64

7、7-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.8