Spectral Clustering

Spectral ClusteringSpectral Clustering（谱聚类）是一种基于图论的聚类方法，它能够识别任意形状的样本空间且收敛于全局最有解，其基本思想是利用样本数据的相似矩阵进行特征分解后得到的特征向量进行聚类，可见，它与样本feature无关而只与样本个数有关。一、图的划分图划分的目的是将有权无向图划分为两个或以上子图，使得子图规模差不多而割边权重之和最小。图的划分可以看做是有约束的最优化问题，它的目的是看怎么把每个点划分到某个子图中，比较不幸的是当你选择各种目标函数后发现该优化问题往往是NP-hard的。怎么解决这个问题呢？松弛方法往往是一种利器（比如SVM中的松弛变量），对于图的划分可以认为能够将某个点的一部分划分在子图1中，另一部分划分在子图2中，而不是非此即彼，使用松弛方法的目的是将组合优化问题转化为数值优化问题，从而可以在多项式时间内解决之，最后在还原划分时可以通过阈值来还原，或者使用类似K-Means这样的方法，之后会有相关说明。二、相关定义1、用表示无向图，其中和分别为其顶点集和边集；2、说某条边属于某个子图是指该边的两个顶点都包含在子图中；3、假设边的两个不同端点为和，则该边的权重用表示，对于无向无环图有且，为方便以下的“图”都指无向无环图；4、对于图的某种划分方案的定义为：所有两端点不在同一子图中的边的权重之和，它可以被看成该划分方案的损失函数，希望这种损失越小越好三、Laplacian矩阵这个等式的核心价值在于：将最小化划分的问题转变为最小化二次函数；从另一个角度看，实际上是把原来求离散值松弛为求连续实数值。它所对应的矩阵为： [,1][,2] [,3] [,4] [,5] [,6][1,]0.00.8 0.6 0.00.1 0.0[2,] 0.8 0.0 0.8 0.0 0.0 0.0[3,] 0.6 0.8 0.0 0.2 0.0 0.0[4,] 0.0 0.0 0.2 0.0 0.8 0.7[5,] 0.1 0.0 0.0 0.8 0.0 0.8[6,] 0.0 0.0 0.0 0.7 0.8 0.0矩阵为： [,1] [,2] [,3] [,4] [,5] [,6][1,] 1.5 0.0 0.0 0.0 0.0 0.0[2,] 0.0 1.6 0.0 0.0 0.0 0.0[3,] 0.0 0.0 1.6 0.0 0.0 0.0[4,] 0.0 0.0 0.0 1.7 0.0 0.0[5,] 0.0 0.0 0.0 0.0 1.7 0.0[6,] 0.0 0.0 0.0 0.0 0.0 1.5Laplacian矩阵为： [,1] [,2] [,3] [,4] [,5] [,6][1,] 1.5 -0.8 -0.6 0.0 -0.1 0.0[2,] -0.8 1.6 -0.8 0.0 0.0 0.0[3,] -0.6 -0.8 1.6 -0.2 0.0 0.0[4,] 0.0 0.0 -0.2 1.7 -0.8 -0.7[5,] -0.1 0.0 0.0 -0.8 1.7 -0.8[6,] 0.0 0.0 0.0 -0.7 -0.8 1.5Laplacian矩阵是一种有效表示图的方式，任何一个Laplacian矩阵都对应一个权重非负地无向有权图，而满足以下条件的就是Laplacian矩阵：1、为对称半正定矩阵，保证所有特征值都大于等于0；2、矩阵有唯一的0特征值，其对应的特征向量为，它反映了图的一种划分方式：一个子图包含原图所有端点，另一个子图为空。四、SpectralClustering对照图的划分方法，有下列两类Spectral Clustering算法，他们的区别在于Laplacian矩阵是否是规范化的：1、Unnormalized Spectral Clustering算法算法输入：样本相似矩阵S和要聚类的类别数K。●根据矩阵S建立权重矩阵W、三角矩阵D；●建立Laplacian矩阵L；●求矩阵L的前K小个特征值及其对应的特征向量，注意最小的那个特征值一定是0且对应的特征向量为；●以这K组特征向量组成新的矩阵，其行数为样本数，列数为K，这里就是做了降维操作，从N维降到K维，(实际上除去那个全为1的向量维度降为了K-1)；●使用K-Means算法进行聚类，得到K个Cluster。2、Normalized Spectral Clustering算法算法输入：样本相似矩阵S和要聚类的类别数K。●根据矩阵S建立权重矩阵W、三角矩阵D；●建立Laplacian矩阵L以及；●求矩阵的前K小个特征值及其对应的特征向量，注意最小的那个特征值一定是0且对应的特征向量为；●利用求得矩阵L前K小个特征向量；●以这K组特征向量组成新的矩阵，其行数为样本数N，列数为K；●使用K-Means算法进行聚类，得到K个Cluster。3、以图1为例，取K=2，使用Unnormalized Spectral Clustering算法，此时聚类的对象其实就是矩阵L的第二小特征向量(使用R模拟)：●L矩阵为：[,1] [,2] [,3] [,4] [,5] [,6] [1,]1.5 -0.8 -0.6 0.0 -0.1 0.0 [2,] -0.8 1.6 -0.8 0.0 0.0 0.0 [3,] -0.6 -0.8 1.6 -0.2 0.0 0.0 [4,] 0.0 0.0 -0.2 1.7 -0.8 -0.7 [5,] -0.1 0.0 0.0 -0.8 1.7 -0.8 [6,] 0.0 0.0 0.0 -0.7 -0.8 1.5●q<-eigen(L) 求得L的特征值和特征向量分别为：$values[1] 2.573487e+00 2.469025e+00 2.285298e+00 2.084006e+00 1.881842e-01 1.776357e-15$vectors [,1] [,2] [,3] [,4] [,5] [,6][1,] -0.10598786 -0.3788245748 -0.30546656 0.64690880 0.4084006 -0.4082483[2,] -0.21517718 0.7 0.30450981 -0. 0.4418249 -0.4082483[3,] 0.36782805 -0.3884382495 0. -0.63818761 0.3713186 -0.4082483[4,] -0.61170644 -0. -0.45451793 -0.33863293 -0.3713338 -0.4082483[5,] 0.65221488 0.35 -0.30495543 0.16645901 -0.4050475 -0.4082483[6,] -0. -0.2890305075 0.71581349 0.17786774 -0.4451628-0.4082483●q$vectors[,5]取第二小特征向量：[1] 0.4084006 0.4418249 0.3713186 -0.3713338 -0.4050475 -0.4451628●kmeans(q$vectors[,5],2)利用K-Means算法聚类：K-means clustering with 2 clusters of sizes 3, 3Cluster means: [,1] 1 -0.4071814 2 0.4071814Clustering vector:[1] 2 2 2 1 1 1Within cluster sum of squares by cluster:[1] 0. 0.(between_SS / total_SS = 99.5 %)从结果上可以看到顶点1、2、3被聚为一类，顶点4、5、6被聚为一类，与实际情况相符。