拉普拉斯矩阵及谱聚类(Laplacian Matrix and Spectral Clustering)
与相似性度量相关的论文中经常出现拉普拉斯矩阵(Laplacian Matrix),根据维基百科的描述,该矩阵在图论中运用较多。本文主要介绍在谱聚类中的应用。首先给出一个谱聚类的直观结果,然后介绍Laplacian Matrix的一些性质,最后讨论谱聚类。
通过模拟生成一系列的数据分别用k-means和谱聚类的方法进行聚类,结果如下:
通过结果便可以直观的看出两种聚类的差异了。对于都聚成3类的情况,k-means是随机的选择3个聚类中心,然后将其他的样本点归到离自己最近的中心,对分好的3类求出均值作为新的聚类中心,如此迭代,直至聚类中心收敛。而谱聚类首先求出相似度矩阵W,可以选择高斯相似度函数:
。然后计算出Laplacian matrix L (L = D - W, 其中D是degree matrix,是一个对角阵,每一个值对应相似度矩阵W中每一行的和)。计算L的前k个最小的特征向量,把这k个列向量排列在一起组成一个n*k的矩阵,其中每一行看作k维空间中的一个向量,并使用k-means算法进行聚类,其原理文章后面会进行推导。
通过不同的聚类方法可以得到不同的结果,评价聚类结果需要根据现实场景。比如上图像是两个pizza,每一圈代表不同的馅料,最里面是一圈海鲜,中间是烤肉,最外一圈是芝士。要将其分给3个人,如果这3个人都想尝尝不同的味道,那么可以按k-means分,如果一个只喜欢吃芝士,一个只喜欢烤肉,一个只喜欢海鲜,那么当然spectral cluster靠谱。多一种聚类方式多适应一种场景。
1. Unnormalized Laplacian Matrix
首先介绍没有正则化的拉普拉斯矩阵的性质。拉普拉斯矩阵L定义为:
L有如下一些性质:
举个例子:如下两幅图,图中连接的边的权重都为1。由此可以得到图1和图2的拉普拉斯的矩阵L1和L2。
求得L1的特征值为0, 1, 1, 4,0特征值对应的特征向量为(-0.5 -0.5 -0.5 -0.5)L2的特征值为0, 0, 1, 1, 2, 4,0特征值对应的特征向量为(-0.5 -0.5 -0.5 -0.5 0 0)和(0 0 0 0 -0.707 -0.707)。验证了前面第三条性质。对于一个有n个连通分部的图而言,其对应的拉普拉斯矩阵有n个为零的特征值。
Unnormalized Laplacian Matrix和Unnormalized Laplacian Matrix的区别只在于对矩阵L的是否进行了规范化,规范化的方式有以下两种,对应的谱聚类方式也分为Unnormalized Spectral Clustering和Normalized Spectral Clustering。
2. Spectral Clustering
Unnormalized Spectral Clustering的聚类算法描述如下,Matlab代码在最后给出。
下面是一个比较有趣的实验,图片来自论文A Tutorial on Spectral Clustering [PDF]。实验生成了200个样本点,来自于4个混合高斯分布,其均值分别是2、4、6、8。这里解释最复杂的最后一行。
最后一行中,采用了full graph计算相似度,所以样本点整体形成了一个网络,因此对应的拉普拉斯矩阵中含有一个为0的特征值,且该特征值对应的Eigenvector 1为常向量,向量中的各元素都相等。我们选择最小的4个特征值进行聚类,从图中可以看到,除第一个特征值外,其余Eigenvector 2-4 包含了聚类信息。以0作为阈值,Eigenvector 2可以将2、4和6、8分开;Eigenvector 3可以将2、8和4、6分开;Eigenvector 4可以将2、6和4、8分开。至此,样本可以被完美的分为4类,分别是2、4、6、8各一类。
谱聚类的原理可以通过Graph Cut、Random Walks以及Perturbation Theory来解释。以后的博文中会做相应的补充。
3. 谱聚类的Matlab实现
谱聚类的Matlab实现比较简单,下面给出的代码中求相似度矩阵部分对for循环进行了向量化(提高了运行效率但是比较难看懂)。通过运行该代码便可以得到本文开头的图片。
function spectral_cluster() %% Generate sample data points_per_cluster = 500; num_cluster = 3; bandwidth = 0.1; data = zeros([num_cluster*points_per_cluster, 2]); index = 1; for k = 1 : num_cluster for n = 1 : points_per_cluster theta = 2 * pi * rand; rho = k + randn(1) * bandwidth; [x, y] = pol2cart(theta, rho); data(index,:) = [x, y]; index = index + 1; end end %% Kmeans mincenter = kmeans(data, num_cluster); group1 = (mincenter == 1); group2 = (mincenter == 2); group3 = (mincenter == 3); figure; hold on; plot(data(group1,1), data(group1,2), 'r.'); plot(data(group2,1), data(group2,2), 'b.'); plot(data(group3,1), data(group3,2), 'y.'); axis square; grid on; hold off; %% Spectral Clustering sigma = 0.1; s1s2 = -2 * data * (data'); ss = sum(data.^2,2); % similarity matrix (vectorlized) % s(x_i, x_j) = exp(-|x_i - x_j|^2 /(2 * sigma^2)) A = exp( -(s1s2 + repmat(ss, 1, length(ss)) + repmat(ss', length(ss), 1))/(2*sigma^2)); D = diag(sum(A')); L = D - A; [X, ~] = eigs(L, num_cluster, 'SM'); Y = X ./ repmat(sqrt(sum(X.^2, 2)), 1, num_cluster); mincenter = kmeans(Y, num_cluster); group1 = (mincenter == 1); group2 = (mincenter == 2); group3 = (mincenter == 3); figure; hold on; plot(data(group1,1), data(group1,2), 'r.'); plot(data(group2,1), data(group2,2), 'b.'); plot(data(group3,1), data(group3,2), 'y.'); axis square; grid on; hold off; end
本文的引用链接为:http://www.iwenchao.com/machine-learning/laplacian-matrix-and-spectral-clustering.html,转载请注明出处。
扫码关注腾讯云开发者
领取腾讯云代金券
Copyright © 2013 - 2025 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号:粤B2-20090059 深公网安备号 44030502008569
腾讯云计算(北京)有限责任公司 京ICP证150476号 | 京ICP备11018762号 | 京公网安备号11010802020287
Copyright © 2013 - 2025 Tencent Cloud.
All Rights Reserved. 腾讯云 版权所有