《谱聚类与社区划分》PPT课件.pptx

《《谱聚类与社区划分》PPT课件.pptx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、谱聚类与社区划分谱聚类(SpectralClustering)谱聚类(SpectralClustering,SC)是一种基于图论的聚类方法：将带权无向图划分为两个或两个以上的最优子图，使子图内部尽量相似，而子图间距离尽量距离较远，以达到常见的聚类的目的。谱聚类(SpectralClustering)其中的最优是指最优目标函数不同（例如）：1.Smallestcut：割边最小分割2.Bestcut：分割规模差不多且割边最小的分割这样，谱聚类能够识别任意形状的样本空间且收敛于全局最优解，其基本思想是利

2、用样本数据的相似矩阵(拉普拉斯矩阵)进行特征分解后得到的特征向量进行聚类。谱聚类(SpectralClustering)谱聚类算法：求解RatioCut2图的分割问题1求解NormalizedCut3谱聚类(SpectralClustering)图的分割问题：谱聚类算法源于图的分割（cut），首先将所有的样本点连接成图，然后将图分割成不同的子图，使得不同子图之间的连接权值最小。谱聚类(SpectralClustering)图的分割问题：谱聚类(SpectralClustering)RatioCut

3、：谱聚类(SpectralClustering)RatioCut：谱聚类(SpectralClustering)NormalizedCut：谱聚类(SpectralClustering)NormalizedCut：谱聚类(SpectralClustering)小结：针对以上两种图分割方法，谱聚类算法的步骤如下：Step2：计算图的邻接矩阵W和拉普拉斯矩阵L；Step1：将每个样本看做图的顶点，构造无向加权图；Step3：根据图的分割准则计算拉普拉斯矩阵的前k个特征向量；Step4：将拉普拉斯矩阵的

4、前k个特征向量构成矩阵Y，把Y的每一行看做一个样本，然后用k-means方法对Y进行聚类。谱聚类(SpectralClustering)总结：谱聚类相当于先进行非线性降维，使原始数据点能够线性可分，最后再使用k-means聚类就可以得到比较好的聚类效果。谱聚类算法也存在以下几点不足：   （1）谱聚类的松弛条件是对原问题的一个近似，但是并不能保证该近似是合适的，其误差有可能非常大，而且导致聚类问题不稳定；   （2）构造相似度矩阵的尺度参数根据经验设定，尺度参数的选择对聚类效果影响较大；  

5、 （3）同其他聚类方法一样，聚类数目的选择难以确定；   （4）根据图最小分割的目标函数可知，谱聚类适用于均衡分类问题，即各簇之间点的个数相差不大，对于簇之间点个数相差悬殊的聚类问题，谱聚类则不适用。   以下一组图均为采用谱聚类方法进行聚类的结果，左侧一列的数据点个数分布比较均衡，聚类效果比较好，可以看出，右侧一列数据点的分布不均衡，谱聚类算法仍然将数据分成几个均衡的簇，而不能体现数据的分布结构。谱聚类(SpectralClustering)