使用谱聚类划分数据
本主题提供了光谱聚类的介绍和一个估计聚类数量并执行光谱聚类的示例。
谱聚类简介
谱聚类是一种基于图的算法,用于将数据点或观测值划分为k集群。统计和机器学习工具箱™功能spectralcluster
对输入数据矩阵或对象执行聚类相似度矩阵由数据推导出的相似图。spectralcluster
返回集群索引,包含k的特征向量拉普拉斯算子的矩阵,以及与特征向量相对应的特征值向量。
spectralcluster
要求您指定集群的数量k.但是,您可以验证您的估计k使用以下方法之一是正确的:
计算拉普拉斯矩阵零特征值的个数。零特征值的多重性是数据中集群数量的一个指示器。
利用MATLAB计算相似矩阵中连通分量的个数®函数
conncomp
.
算法描述
谱聚类是基于图的查找算法吗k数据中任意形状的簇。该技术涉及用低维表示数据。在低维中,数据中的集群被更广泛地分开,使您能够使用诸如k——或k-medoids集群。这个低维是基于特征向量对应于k拉普拉斯矩阵的最小特征值。拉普拉斯矩阵是表示相似图的一种方法,它将数据点之间的局部邻域关系建模为无向图。谱聚类算法从你的数据中导出相似图的相似矩阵,找到拉普拉斯矩阵,并使用拉普拉斯矩阵来寻找k特征向量用于分割相似图k分区。当您知道聚类的数量时,您可以使用谱聚类,但该算法还提供了一种估计数据中的聚类数量的方法。
缺省情况下,算法为spectralcluster
用Shi-Malik描述的方法计算归一化随机游走拉普拉斯矩阵[1].spectralcluster
还支持非归金宝app一化拉普拉斯矩阵和采用Ng-Jordan-Weiss方法的归一化对称拉普拉斯矩阵[2].的spectralcluster
函数实现聚类,如下所示:
中的每个数据点
X
属性指定的半径搜索方法或最近邻方法定义局部邻域“SimilarityGraph”
名称-值对参数(参见相似度图)。然后,求出成对距离 对于所有点我而且j在附近。使用核变换将距离转换为相似度量 .矩阵年代是相似度矩阵,σ内核的比例因子,是否如使用
“KernelScale”
名称-值对参数。计算非归一化拉普拉斯算子的矩阵l,归一化随机游走拉普拉斯矩阵lrw或归一化对称拉普拉斯矩阵l年代的值
“LaplacianNormalization”
名称-值对参数。创建一个矩阵 包含列 ,其中列为k特征向量对应于k拉普拉斯矩阵的最小特征值。如果使用l年代,归一化每一行V有单位长度。
处理每一行V作为一个点,集群n点使用k-means集群(默认)或k类指定的medoids集群
“ClusterMethod”
名称-值对参数。将原点赋值
X
中对应行的相同的集群V.
估计聚类数量并执行谱聚类
这个示例演示了执行光谱聚类的两种方法。
第一种方法使用拉普拉斯矩阵的特征值估计聚类的数量,并在数据集上执行谱聚类。
第二种方法利用相似图估计聚类的数量,并对相似矩阵进行谱聚类。
生成样本数据
随机生成一个样本数据集,其中包含三个分离良好的集群,每个集群包含20个点。
rng (“默认”);%用于再现性N = 20;X = [randn(n,2)*0.5+3;randn (n, 2) * 0.5;randn (n, 2) * 0.5 3];
对数据进行谱聚类
利用拉普拉斯矩阵的特征值估计数据中的聚类数量,并对数据集进行谱聚类。
计算拉普拉斯矩阵的五个最小特征值(大小)spectralcluster
函数。默认情况下,该函数使用归一化随机游走拉普拉斯矩阵。
[~,V_temp,D_temp] = spectralcluster(X,5)
V_temp =60×5-0.2236 -0.0000 -0.0000 - 1534 -0.2236 -0.0000 -0.0000 -0.2236 -0.0000 -0.0000 -0.0000 0.1776 -0.0000 -0.2236 -0.0000 -0.0000 -0.0000 0.1331 -0.0000 -0.2236 -0.0000 -0.0000 -0.0000 0.2176 -0.2236 -0.0000 -0.0000 0.1967 0.0000 -0.2236 -0.0000 -0.0000 -0.0000 -0.0088 0.000 -0.2236 -0.0000 -0.0000 -0.2236 -0.0000 -0.0000 -0.2844 -0.2236 -0.0000 -0.0000 -0.0000 -0.0000 -0.3275 -0.0000
D_temp =5×10.0000 -0.0000 -0.0000 0.0876 0.1653
只有前三个特征值近似为零。零特征值的数量可以很好地指示相似图中连接组件的数量,因此可以很好地估计数据中的聚类数量。所以,k = 3
是否可以很好地估计集群的数量X
.
方法对观测结果进行光谱聚类spectralcluster
函数。指定k = 3
集群。
K = 3;[idx1,V,D] = spectralcluster(X,k)
idx1 =60×11 1 1 1 1 1 1 1 1 1 1
V =60×30.2236 -0.0000 -0.0000 0.2236 -0.0000 -0.0000 0.2236 -0.0000 -0.0000 0.2236 -0.0000 -0.0000 0.2236 -0.0000 -0.0000 0.2236 -0.0000 -0.0000 0.2236 -0.0000 -0.0000 0.2236 -0.0000 -0.0000 0.2236 -0.0000 -0.0000 0.2236 -0.0000 -0.0000⋮
D =3×110-16年× 0.6142 -0.1814 -0.3754
的元素D
对应于拉普拉斯矩阵的三个最小特征值。的列V
中的特征值对应的特征向量D
.对于分离良好的聚类,特征向量是指示向量。对于不属于特定聚类的点,特征向量的值为零(或接近于零),而对于属于特定聚类的点,特征向量的值为非零。
可视化聚类结果。
gscatter (X (: 1) X (:, 2), idx1);
的spectralcluster
函数正确地识别数据集中的三个集群。
而不是使用spectralcluster
再次函数,可以通过V_temp
到kmeans
函数对数据点进行聚类。
idx2 = kmeans(V_temp(:,1:3),3);gscatter (X (: 1) X (:, 2), idx2);
中的群集分配顺序idx1
而且idx2
是不同的,即使数据点以相同的方式聚集。
执行光谱聚类关于相似矩阵
利用相似度图估计聚类数量,并对相似度矩阵进行谱聚类。
求每对观测值之间的距离X
通过使用pdist
而且squareform
函数使用默认的欧几里得距离度量。
dist_temp = pdist(X);Dist = squareform(dist_temp);
由成对距离构造相似矩阵,并确认相似矩阵是对称的。
S = exp(-dist.^2);issymmetric (S)
ans =逻辑1
将相似值限制为0.5
这样,相似度图只会连接成对距离小于搜索半径的点。
S_eps = S;S_eps(S_eps<0.5) = 0;
创建一个图
对象从年代
.
G_eps = graph(S_eps);
可视化相似图。
情节(G_eps)
识别图中连通组件的数量G_eps
通过使用独特的
而且conncomp
功能。
独特的(conncomp (G_eps))
ans =1×31 2 3
相似度图显示了三组相互连接的组件。相似度图中连接组件的数量可以很好地估计数据中的聚类数量。因此,k = 3
选择集群的个数是否合适X
.
对从数据集得到的相似矩阵进行谱聚类X
.
K = 3;idx3 = spectralcluster(S_eps,k,“距离”,“预算”);gscatter (X (: 1) X (:, 2), idx3);
的spectralcluster
函数正确地识别数据集中的三个集群。
参考文献
[1] Shi, J.和J. Malik。“标准化切割和图像分割。”模式分析与机器智能汇刊.卷22,2000,第888-905页。
吴恩达、A.Y、M.乔丹和Y.韦斯。关于谱聚类:分析和算法在神经信息处理系统进展.麻省理工学院出版社,2001,第849-856页。
另请参阅
spectralcluster
|pdist2
|pdist
|squareform
|邻接
|conncomp