谱聚类Ng算法的Matlab简单实现

谱聚类Ng算法的Matlab简单实现

请编写一个谱聚类算法,实现“Normalized Spectral Clustering—Algorithm 3 (Ng 算法)”

结果如下

谱聚类Ng算法的Matlab简单实现

谱聚类算法核心步骤都是相同的:

•利用点对之间的相似性,构建亲和度矩阵;

•构建拉普拉斯矩阵;

•求解拉普拉斯矩阵最小的特征值对应的特征向量(通常舍弃零特征所对应的分量全相等的特征向量);

•由这些特征向量构成样本点的新特征,采用K-means等聚类方法完成最后的聚类。

采用K-means等聚类方法完成最后的聚类  意思是,对特征向量构成的矩阵T,每一行作为一个样本点,进行K均值聚类。

(1)利用点对之间的相似性,构建亲和度矩阵,

谱聚类Ng算法的Matlab简单实现

构建图时,顶点的度为 simK=10,分两类kNearNum=2

simK=10;
Wij=zeros(r,r);% weight
% calculate the weight Matrix
for k=1:r
for n=1:r
Wij(k,n)=exp(-norm(X(k,:)-X(n,:))^2/2/sigma);% 计算权重
end
end % find the Knear for W
Wsort=zeros(r,r);
index=zeros(r,r);
for k=1:r
% 对每一行权重排序
[Wsort(k,:),index(k,:)]=sort(Wij(k,:)); %这句话经常不会用,记住了。
end W=Wij

(2) 构建Laplace Matrix

首先需要个对角阵D,其对角元素是亲和度矩阵的每行的和,这里也就是simK*eye(r)

% D
D=simK.*eye(r);
% Laplace Matrix
L=eye(r)-D^(-0.5)*W*D^(-0.5);
% L=D-W

(3) 求解拉普拉斯矩阵最小的特征值(lamda)对应的特征向量)(通常舍弃零特征所对应的分量全相等的特征向量);

把特征向量 Vect里最小的kNearNum(聚类的个数)个用u来存储。

[Vect,lamdaMat]=eig(L);
lamda=zeros(k,1);
u=zeros(r,kNearNum);
% lamda是特征值
for k=1:r
lamda(k)=lamdaMat(k,k);
end
% lamda
% 对lamda排序,找出最小的K个lamda对应的特征向量组成u
[sortLamda,indexLamda]=sort(lamda);
countu=0;
for k=1:kNearNum
countu=countu+1;
u(:,countu)=Vect(:,indexLamda(k));
end
% % T
T=zeros(r,kNearNum);% 归一化后的u
sumU=zeros(1,kNearNum);% 为了归一化u,对每列求了平方和sumU
for n=1:kNearNum
for k=1:r
sumU(1,n)=sumU(1,n)+u(k,n)^2;
end
end for k=1:r
for n=1:kNearNum
T(k,n)=u(k,n)./sqrt(sumU(1,n));
end
end

(4)由这些特征向量构成样本点的新特征,采用K-means等聚类方法完成最后的聚类

意思是,对特征向量构成的矩阵T,每一行作为一个样本点聚类

A=Kmeans(T)  % key words

Kmeans详见下面链接

上一篇:startActivity跳转失败而且没有异常信息


下一篇:html-有趣的标签-会移动的文字