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

谱谱聚类类与社区划分 谱谱聚类类(Spectral Clustering) 谱聚类(Spectral Clustering, SC)是一种基于图论的聚类方法：将带权无向 图划分为两个或两个以上的最优子图，使子图内部尽量相似，而子图间距 离尽量距离较远，以达到常见的聚类的目的。 谱谱聚类类(Spectral Clustering) 其中的最优是指最优目标函数不同（例如）： 1.Smallest cut：割边最小分割 2.Best cut：分割规模差不多且割边最小 的分割 这样，谱聚类能够识别 任意形状的样本空间且收敛于全局最优解，其基本思想是利用样本数据的相似矩 阵阵(拉普拉斯矩阵阵)进行特征分解后得到的特征向量进行聚类。 谱谱聚类类(Spectral Clustering) 谱聚类算法： 求解RatioCut 2 图的分割问题 1 求解Normalized Cut3 谱谱聚类类(Spectral Clustering) 图的分割问题： 谱聚类算法源于图的分割（cut），首先将所有的样本点连接成图，然后将图分 割成不同的子图，使得不同子图之间的连接权值最小。 谱谱聚类类(Spectral Clustering) 图的分割问题： 谱谱聚类类(Spectral Clustering) RatioCut ： 谱谱聚类类(Spectral Clustering) RatioCut ： 谱谱聚类类(Spectral Clustering) Normalized Cut ： 谱谱聚类类(Spectral Clustering) Normalized Cut ： 谱谱聚类类(Spectral Clustering) 小结： 针对以上两种图分割方法，谱聚类算法的步骤如下： Step2：计算图的邻接矩阵W和拉普拉斯矩阵L； Step1：将每个样本看做图的顶点，构造无向加权图； Step3：根据图的分割准则计算拉普拉斯矩阵的前k个特征向量； Step4：将拉普拉斯矩阵的前k个特征向量构成矩阵Y，把Y的每一行看 做一个样本，然后用k-means方法 对Y进行聚类。 谱谱聚类类(Spectral Clustering) 总结： 谱聚类相当于先进行非线性降维，使原始数据点能够线性可分，最后再使用k-means聚类就 可以得到比较好的聚类效果。 谱聚类算法也存在以下几点不足： （1） 谱聚类的松弛条件是对原问题的一个近似，但是并不能保证该近似是合适的，其误差有 可能非常大，而且导致聚类问题 不稳定； （2） 构造相似度矩阵的尺度参数根据经验设 定，尺度参数的选择对 聚类效果影响较大； （3） 同其他聚类方法一样，聚类数目的选择难 以确定； （4） 根据图最小分割的目标函数可知，谱聚类适用于均衡分类问题 ，即各簇之间点的个数相 差不大，对于簇之间点个数相差悬殊的聚类问题 ，谱聚类则不适用。 以下一组图均为采用谱聚类方法进行聚类的结果，左侧一列的数据点个数分布比较均衡，聚类 效果比较好，可以看出，右侧一列数据点的