3986.net
小网站 大容量 大智慧
当前位置:首页 >> 数学 >>

谱聚类


Spectral Clustering(谱聚类)是一种基于图论的聚类方法,它能够识别任意形状的样本空间且收敛于全局 最有解,其基本思想是利用样本数据的相似矩阵进行特征分解后得到的特征向量进行聚类,可见,它与样 本 feature 无关而只与样本个数有关。

一、图的划分

图划分的目的是将有权无向图划分为两个或以上子图,使得子图规模差不多而割边权重之和最小。图 的划分可以看做是有约束的最优化问题,它的目的是看怎么把每个点划分到某个子图中,比较不幸的是当 你选择各种目标函数后发现该优化问题往往是 NP-hard 的。 怎么解决这个问题呢?松弛方法往往是一种利器(比如 SVM 中的松弛变量),对于图的划分可以认 为能够将某个点的一部分划分在子图 1 中,另一部分划分在子图 2 中,而不是非此即彼,使用松弛方法的 目的是将组合优化问题转化为数值优化问题,从而可以在多项式时间内解决之,最后在还原划分时可以通 过阈值来还原,或者使用类似 K-Means 这样的方法,之后会有相关说明。

二、相关定义

1、用

表示无向图,其中



分别为其顶点集和边集;

2、说某条边属于某个子图是指该边的两个顶点都包含在子图中;

3、假设边 的两个不同端点为 和 ,则该边的权重用 ,为方便以下的“图”都指无向无环图; 4、对于图的某种划分方案的

表示,对于无向无环图有



定义为:所有两端点不在同一子图中的边的权重之和,它可以被看 被划分为

成该划分方案的损失函数, 希望这种损失越小越好, 本文以二分无向图为例, 假设原无向图 和 ,那么有:

三、Laplacian 矩阵

假设无向图

被划分为



两个子图,该图的顶点数为:

,用 表示

维指示向量,

表明该划分方案,每个分量定义如下:

于是有:

又因为:

其中,

为对角矩阵,对角线元素为:

为权重矩阵:





重新定义一个对称矩阵

,它便是 Laplacian 矩阵:

矩阵元素为:

进一步观察:

如果所有权重值都为非负,那么就有

,这说明 Laplacian 矩阵 是半正定矩阵;而当无向图为

连通图时 有特征值 0 且对应特征向量为 个为其本身,另一个为空时,

,这反映了,如果将无向图

划分成两个子图,一

为 0(当然,这种划分是没有意义的)。

其实上面推导的目的在于得到下面的关系:

这个等式的核心价值在于:将最小化划分

的问题转变为最小化二次函数

;从另一个角度看,

实际上是把原来求离散值松弛为求连续实数值。 观察下图:

图1

它所对应的

矩阵为:

[,1] [,2] [,3] [,4] [,5] [,6]

[1,] 0.0 0.8 0.6 0.0 0.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.5 Laplacian 矩阵为: [,1] [,2] [,3] [,4] [,5] [,6] [1,] 1.5 -0.8 -0.6 0.0 -0.1 [3,] -0.6 -0.8 1.6 -0.2 0.0 0.0 0.0 [2,] -0.8 1.6 -0.8 0.0 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

Laplacian 矩阵是一种有效表示图的方式,任何一个 Laplacian 矩阵都对应一个权重非负地无向有权图,而 满足以下条件的就是 Laplacian 矩阵: 1、 为对称半正定矩阵,保证所有特征值都大于等于 0; 2、 矩阵有唯一的 0 特征值,其对应的特征向量为 包含原图所有端点,另一个子图为空。 ,它反映了图的一种划分方式:一个子图

四、划分方法

1、Minimum Cut 方法

考虑最简单情况,另

,无向图划分指示向量定义为:

要优化的目标为

,由之前的推导可以将该问题松弛为以下问题:

从这个问题的形式可以联想到 Rayleigh quotient:

原问题的最优解就是该 Rayleigh quotient 的最优解, 而由 Rayleigh quotient 的性质可知: 它的最小值, 第二小值,......,最大值分别对应矩阵 的最小特征值,第二小特征值,......,最大特征值,且极值 在相

应的特征向量处取得,即需要求解下特征系统的特征值和特征向量:

这里需要注意约束条件

,显然

的最小特征值为 0,此时对应特征向量为

,不满足这个约束条件(剔除了无意义划分),于是最优解应该在第二小特征值对应的特征向量 处取得。 当然,求得特征向量后还要考虑如何恢复划分,比如可以这样:特征向量分量值为正所对应的端点划 分为 ,反之划分为 ;也可以这样:将特征向量分量值从小到大排列,以中位数为界划分 和 ;

还可以用 K-Means 算法聚类。 2、Ratio Cut 方法

实际当中,划分图时除了要考虑最小化

外还要考虑划分的平衡性,为缓解出现类似一个子图包含

非常多端点而另一个只包含很少端点的情况,出现了 Ratio Cut,它衡量子图大小的标准是子图包含的端点 个数。 为子图 1 包含端点数, 为子图 2 包含端点数,

定义

,则优化目标函数为:

其中:

做一个简单变换:

其中:

看吧,这形式多给力,原问题就松弛为下面这个问题了:

依然用 Rayleigh quotient 求解其第二小特征值及其特征向量。 3、Normalized Cut 方法 与 Ratio Cut 类似,不同之处是,它衡量子图大小的标准是:子图各个端点的 Degree 之和。 定义: 为子图 1Degree 之和:

为子图 2Degree 之和:

则优化目标函数为:

其中:

原问题就松弛为下面这个问题了:

用泛化的 Rayleigh quotient 表示为:

那问题就变成求解下特征系统的特征值和特征向量:

——式子 1

(注:

是一个对角矩阵,且

)

(其中:



)

——式子 2

显然,式子 1 和式子 2 有相同的特征值,但是对应特征值的特征向量关系为: 可以先求式子 2 的特征值及其特征向量,然后为每个特征向量乘以

,因此我们

就得到式子 1 的特征向量。

哦,对了,矩阵

叫做 Normalized Laplacian,因为它对角线元素值都为 1。

五、Spectral Clustering

上边说了这么多,其实就是想将图的划分应用于聚类,而且这种聚类只需要样本的相似矩阵即可,把 每个样本看成图中的一个顶点,样本之间的相似度看成由这两点组成的边的权重值,那么相似矩阵就是一 幅有权无向图。

对照图的划分方法,有下列两类 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 [3,] -0.6 -0.8 1.6 -0.2 0.0 0.0 0.0 [2,] -0.8 1.6 -0.8 0.0 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.7063206485 0.30450981 -0.01441501 0.4418249 -0.4082483 [3,] 0.36782805 -0.3884382495 0.04461661 -0.63818761 0.3713186 -0.4082483 [4,] -0.61170644 -0.0009962363 -0.45451793 -0.33863293 -0.3713338 -0.4082483 [5,] 0.65221488 0.3509689196 -0.30495543 0.16645901 -0.4050475 -0.4082483 [6,] -0.08717145 -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, 3 Cluster means: [,1] 1 -0.4071814 2 0.4071814 Clustering vector: [1] 2 2 2 1 1 1 Within cluster sum of squares by cluster: [1] 0.002732195 0.002487796 (between_SS / total_SS = 99.5 %) 从结果上可以看到顶点 1、2、3 被聚为一类,顶点 4、5、6 被聚为一类,与实际情况相符。 在 Mahout 中已经有相应实现,放在下次学习吧。

六、总结

1、图划分问题中的关键点在于选择合适的指示向量 并将其进行松弛化处理,从而将最小化划分 问题转变为最小化二次函数 ,进而转化为求 Rayleigh quotient 极值的问题;



2、 Spectral Clustering 的各个阶段为: ● 选择合适的相似性函数计算相似度矩阵; ●计算矩阵 L 的特征值及其特征向量,比如可以用 Lanczos 迭代算法; ●如何选择 K,可以采用启发式方法,比如,发现第 1 到 m 的特征值都挺小的,到了 m+1 突然变成较大的 数,那么就可以选择 K=m; ● 使用 K-Means 算法聚类,当然它不是唯一选择; ● Normalized Spectral Clustering 在让 Cluster 间相似度最小而 Cluster 内部相似度最大方面表现要更好, 所以首选这类方法。


推荐相关:

谱聚类算法(Spectral Clustering) 谱聚类(Spectral Clustering, SC)是一种基于图论的聚类方法——将带权无向图划分为两个或两个以上的最优子图,使子图内部尽量...


1 谱聚类谱聚类算法建立在图论中的谱图理论基础上, 其本质是将聚类问题转化为图的最优划分问题,假定将每个 数据样本看作图中的顶点 V, 根据样本间的相似度将...


谱聚类算法 算法简介_数学_自然科学_专业资料。谱聚类算法 算法简介 谱聚类算法建立在谱图理论基础上, 与传统的聚类算法相比, 它具有能在任意形状的样 本空间上聚...


谱聚类报告_学习总结_总结/汇报_实用文档。机器学习报告 一.绪论聚类是探索性数据分析中广泛采用的一种技术,其应用范围包括统计学、 计算机科学、生物学、社会科学...


3 谱聚类算法在图像分割中的应用谱聚类方法最初是在图像分割中应用 shi 和 Malik[4]将像素作为顶点,根据 像素的亮度和空间位置确定连接像素点问边的权值, 利用 ...


谱聚类算法的Maltab仿真设计_数学_自然科学_专业资料。谱聚类谱聚类算法的 Matlab 仿真设计薛方 (长安大学理学院,陕西 西安 710064) 摘要:本文从理论、程序设计和...


谱聚类算法及其在图像分割... 11页 5财富值 聚类算法讲解 51页 免费如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 ...


8 几种聚类的算法 | 2012/12/5 1 一、 增量谱聚类 1.1 谱聚类谱聚类的思想是将样本看作顶点,样本间的相似度看作带权的边,从而将聚类问题转为 图分割...


这其实也就告 诉了我们, 对传统的谱聚类算法可以根据它的物理意义进行改进, 根据本征值对本征矢量进 行加权,而不是同一对待。这样,不重要的模式即便被考虑进来...


图˙˙马尔可夫过程˙聚类结构_计算机软件及应用_IT/计算机_专业资料 暂无评价|0人阅读|0次下载|举报文档 图˙˙马尔可夫过程˙聚类结构_计算机软件及应用_IT/...

网站首页 | 网站地图
3986 3986.net
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@qq.com