目标是划分两个不相交的类别。我们的数据就有这种 “两个环 “的形状。你可以看到，由于数据不是线性可分离的，K-means解决方案没有太大意义。

（3）计算拉普拉斯矩阵；

（4）计算L的特征值，将特征值从小到大排序，取前k个特征值，并计算前k个特征值的特征向量；

（5）将上面的k个列向量组成矩阵，；

（6）令是的第行的向量，其中；

（7）使用k-means算法将新样本点聚类成簇；

（8）输出簇，其中，.

上面就是未标准化的谱聚类算法的描述。也就是先根据样本点计算相似度矩阵，然后计算度矩阵和拉普拉斯矩阵，接着计算拉普拉斯矩阵前k个特征值对应的特征向量，最后将这k个特征值对应的特征向量组成的矩阵U，U的每一行成为一个新生成的样本点，对这些新生成的样本点进行k-means聚类，聚成k类，最后输出聚类的结果。这就是谱聚类算法的基本思想。相比较PCA降维中取前k大的特征值对应的特征向量，这里取得是前k小的特征值对应的特征向量。但是上述的谱聚类算法并不是最优的，接下来我们一步一步的分解上面的步骤，总结一下在此基础上进行优化的谱聚类的版本。

编码示例

环数据在代码中是对象dat。下面的几行只是简单地生成K-means解决方案，并将其绘制出来。

plot(dat, col= kmeans0cluster)

# 计算距离矩阵
dist(dat, method = "euclidean", diag= T, upper = T)  
sig=1 # 超参数
#  一个点与自身的距离为零
diag(tmpa) <- 0 #设置对角线为零
# 计算程度矩阵
# 因为D是一个对角线矩阵，所以下面一行就可以了:
diag(D) <- diag(D)^(-0.5)
# 现在是拉普拉斯的问题:
# 特征分解
eig_L <- eigen(L, symmetric= T)
K <- 4 # 让我们使用前4个向量
# 它是相当稳健的--例如5或6的结果不会改变
x <- eig_L$vectors\[,1:K\]
# 现在进行归一化处理:
sqrt( apply(x^2, 1, sum) ) #  临时分母
# 临时分母2：转换为一个矩阵
# 创建Y矩阵
# 在y上应用聚类
# 可视化:
plot(dat, col= spect0$cluster)

* 在我们的例子中，的条目不仅是0和1（连接或不连接），而且是量化相似性的数字。

参考资料

Ng, Andrew Y., Michael I. Jordan, and Yair Weiss. “On spectral clustering: Analysis and an algorithm.” Advances in neural information processing systems. 2002.