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

结果如下

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

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

•构建拉普拉斯矩阵；

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

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

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

（1）利用点对之间的相似性，构建亲和度矩阵，

构建图时，顶点的度为 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详见下面链接