在处理非完全图的聚类时候,很难找到一个有效的聚类算法去做聚类。 对于下图来说,10号点和15号点的位置相隔并不是那么近,如用普通聚类算法对下图做聚类,通常会把10号点和15号点聚在一个类上,所以一般的聚类效果并没有那么好。
而谱聚类,就很能很好的处理这类问题。
下面我们来重点介绍谱聚类
谱聚类(SpectralClustering),就是要把样本合理地分成两份或者K份。从图论的角度来说,谱聚类的问题就相当于一个图的分割问题。即给定一个图G = (V, E),顶点集V表示各个样本,带权的边表示各个样本之间的相似度,谱聚类的目的便是要找到一种合理的分割图的方法,使得分割后形成若干个子图,连接不同子图的边的权重(相似度)尽可能低,同子图内的边的权重(相似度)尽可能高。物以类聚,人以群分。
(一) 算法步骤
根据数据构造一个Graph,Graph的每一个节点对应一个数据点,将各个点连接起来(随后将那些已经被连接起来但并不怎么相似的点,通过cut/RatioCut/NCut 的方式剪开),并 且边的权重用于表示数据之间的相似度。把这个Graph用邻接矩阵的形式表示出来,记为 W。 把W的每一列元素加起来得到N个数,把它们放在对角线上(其他地方都是零),组成一个的对角矩阵,记为度矩阵D,并把的结果记为拉普拉斯矩阵。 求出L的前k个特征值(前k个指按照特征值的大小从小到大排序得到),以及对应的特征向量。 把这k个特征(列)向量排列在一起组成一个的矩阵,将其中每一行看作k维空间中的一个向量,并使用 K-means 算法进行聚类。聚类的结果中每一行所属的类别就是原 来 Graph 中的,因此节点亦即最初的N个数据点分别所属的类别。
(二) 谱聚类的实现 python编程,利用sklearn.cluster 下的 SpectralClustering可以很轻易的实现
from sklearn.cluster import SpectralClustering
labels=SpectralClustering(affinity='nearest_neighbors',n_clusters=20, n_neighbors=3).fit_predict(route)
#labels= [ 3, 3, 5, 7, 8, 8, 9, 4, 4, 15, 15, 2, 2, 15, 16, 17, 18, 13, 1, 12, 2, 2, 2, 2, 2, 15, 15, 16, 16, 9, 4, 4, 4, 4, 17, 17, 17, 14, 14, 14, 18, 18, 3, 5, 4, 4, 9, 9, 8, 8, 8, 8, 8, 5, 5, 8, 19, 19, 8, 19, 8, 7, 7, 6, 6, 6, 6, 11, 3, 3, 3, 3, 3, 3, 11, 11, 11, 1, 1, 1, 13, 13, 13, 10, 12, 12, 0, 0, 10, 10, 0, 0]
其中: 1)n_clusters:代表我们在对谱聚类切图时降维到的维数。如分为20个聚类簇,n_clusters=20。
2) affinity: 也就是我们的相似矩阵的建立方式。可以选择的方式有三类,第一类是 'nearest_neighbors',即K邻近法;第二类是'precomputed',即自定义相似矩阵;第三类是全连接法,可以使用各种核函数来定义相似矩阵,还可以自定义核函数。基于对有向图的聚类,本文的参数选择是,affinity='nearest_neighbors', n_neighbors=3。
再把图画出来,完美解决类似于10号和15号坐标分成一类的问题。结果如下图