谱聚类
聚类方法是使用最为广泛的数据分析方法之一,可以被应用到各种不同的领域上。实际操作中,在处理各领域内的数据时,人们的第一反应是通过衡量样本间的相似度来对数据进行聚类。与传统方法相比,谱聚类方法具有许多突出的优点,聚类效果经常比传统方法好很多。
以上谱聚类的介绍来自参考资料[1]。
聚类与最小割问题
对于如下给定的样本数据
我们可以使用这些数据建出一个相似度图,其中
- 每个样本为图中的一个节点
- 每个样本与它的个最近邻邻居相连
- 连边的权值为这两个样本的相似度(可用欧氏距离等)
建好图之后,对这些数据聚类可以看作是一个求这个图的最小割的过程:通过去掉这个图的一些连边,使这个图分成个不连通的分量,并且去掉的连边的权值和最小。
但是,对于使用上述数据和方法构建的相似度图,最小割算法的结果可能会是这样的
显然,这种只把其中一个顶点分离开的结果达不到聚类的目的。因此,我们不仅要把图分成个分量,还必须要求每个分量具有一个合理的大小。接下来我们会解决这一问题。
最小割问题及其扩展
最小割问题:对于一个图,通过去掉这个图的一些连边,使这个图分成个不连通的分量,并且去掉的连边的权值和最小。最小割问题可以定义为最小化如下目标函数
其中
- 为图的第个分量;
- 为的补集;
- ,表示两个分量之间的连接的权值的和;
为了使分割的每个分量具有合理的大小,在目标函数中引入图的大小相关项,扩展如下:
RatioCut:使用每个分量的顶点数量作为这个分量的大小,目标函数如下:
Ncut:使用每个分量的容量作为这个分量的大小,目标函数如下:
很遗憾,上面两个问题是NP-Hard的。我们会尝试近似求解上面两个问题
预备知识
Graph Laplacian
未归一化的Graph Laplacian矩阵定义如下
其中为图的度数矩阵,为图的权值邻接矩阵.
Graph Laplacian矩阵具有如下性质
- 对于任意向量
- 是一个对称矩阵,并且是半正定的。
- 最小的特征值为,对应的特征向量为。
- 的所有特征值都为非负实数,。
Reyleigh-Ritz定理
见参考资料[2]
RatioCut近似求解
先近似求解的问题。
问题的目标函数如下:
对于一个子集,定义向量,这个向量的元素取值如下:
可以证明(推导见参考资料[1])
注意到
问题变成了
这是一个离散优化问题,仍然是NP-Hard的。我们忽略离散约束,使,问题转化为
根据Rayleigh-Ritz定理我们可以直接得出,当等于矩阵的第二个特征值所对应的特征向量时,上述目标函数的取值最小。
求得后,我们只需按照的符号分配顶点的类即可,即
对于任意大小的问题,定义,,其中,其中
可以证明
结合前面两条公式,得出
目标函数为
忽略离散约束,目标函数变成
根据Rayleigh-Ritz定理我们可以直接得出,当矩阵的第列为矩阵的第个特征值所对应的特征向量时,上述目标函数的取值最小。
求得矩阵后,取矩阵的第行作为顶点的embedding,再运行k-means算法聚类即可。
谱聚类算法流程
(1) 求图的Graph Laplacian矩阵;
(2) 对矩阵特征值分解,使,其中,对角线上的元素为矩阵的特征值,并且;
(3) 取矩阵的前个特征向量组成;
(4) 取矩阵的第行作为顶点的embedding,运行k-means算法得到聚类结果。
讨论: Graph Laplacian矩阵的特征向量
通过上述问题可以看出,Graph Laplacian矩阵的特征向量在区分顶点的类别上起重要作用,可作为顶点的embedding使用。所以可以看到这个矩阵和它的特征向量被广泛用在很多其它图学习的算法中。
来自sklearn文档的聚类算法对比图
详细请访问参考资料[3]
参考资料
[1] A Tutorial on Spectral Clustering.
[2] Rayleigh Ratios and the Courant-Fischer Theorem.
[3] Comparing different clustering algorithms on toy datasets.