谱聚类算法将数据集中的每个对象看作是图的顶点V，将顶点间的相似度量化作为相应顶点连接边E的权值，这样就得到一个基于相似度的无向加权图G(V, E)，于是聚类问题就可以转化为图的划分问题。基于图论的最优划分准则就是使划分成的子图内部相似度最大，子图之间的相似度最小。
虽然根据不同的准则函数及谱映射方法，谱聚类算法有着不同的具体实现方法，但是这些实现方法都可以归纳为下面三个主要步骤：
1) 构建表示对象集的相似度矩阵W；
2) 通过计算相似度矩阵或拉普拉斯矩阵的前k个特征值与特征向量，构建特征向量空间；
3) 利用K-means或其它经典聚类算法对特征向量空间中的特征向量进行聚类。
上面的步骤只是谱聚类算法的一个总体框架，由于划分准则、相似度矩阵计算方法等因素的差别，具体的算法实现同样会有所差别，但其本质依然是图划分问题的连续放松形式。
R语言中实现层次聚类模型大家好！在这篇文章中，我将向你展示如何在R中进行层次聚类。
什么是分层聚类？
分层聚类是一种可供选择的方法，它可以自下而上地构建层次结构，并且不需要我们事先指定聚类的数量。
该算法的工作原理如下：
将每个数据点放入其自己的群集中。
确定最近的两个群集并将它们组合成一个群集。
重复上述步骤，直到所有数据点位于一个群集中。
一旦完成，它通常由树状结构表示。
让我们看看分层聚类算法可以做得多好。我们可以使用hclust这个。hclust要求我们以距离矩阵的形式提供数据。我们可以通过使用dist。默认情况下，使用完整的链接方法。
这会生成以下树形图：
从图中我们可以看出，群集总数的最佳选择是3或4：
要做到这一点，我们可以使用所需数量的群集来切断树cutree。
现在，让我们将它与原始物种进行比较。
它看起来像算法成功地将物种setosa的所有花分为簇1，并将virginica分为簇2，但是与花斑杂交有困难。如果你看看显示不同物种的原始图，你可以理解为什么：
让我们看看我们是否可以通过使用不同的连接方法更好。这一次，我们将使用平均连接方法：
这给了我们以下树状图：
我们可以看到，群集数量的两个最佳选择是3或5.让我们用cutree它来将它降到3个群集。
我们可以看到，这一次，该算法在聚类数据方面做得更好，只有6个数据点出错。
我们可以如下绘制它与原始数据进行比较：
这给了我们下面的图表：
内部颜色与外部颜色不匹配的所有点都是不正确聚类的点。
聚类三种方法：k-means聚类、密度聚类、层次聚类和 谱聚类Spectrum Clustering
谱聚类 是一种基于图论的聚类方法——将带权无向图划分为两个或两个以上的最优子图，使子图内部尽量相似，而子图间距离尽量距离较远，以达到常见的聚类的目的。其中的最优是指最优目标函数不同，可以是割边最小分割,也可以是分割规模差不多且割边最小的分割。
谱聚类算法首先根据给定的样本数据集定义一个描述成对数据点相似度的亲合矩阵,并且计算矩阵的特征值和特征向量 ， 然后选择合适 的特征向量聚类不同的数据点。谱聚类算法最初用于计算机视觉 、VLS I 设计等领域， 最近才开始用于机器学习中，并迅速成为国际上机器学习领域的研究热点。谱聚类算法建立在谱图理论基础上，其本质是 将聚类问题转化为图的最优划分 问题，是一种 点对聚类算法 ，与传统的聚类算法相比，它具有能在任意形状的样本空间上聚类且收敛于全局最优解的优点。
根据不同的图拉普拉斯构造方法，可以得到不同的谱聚类算法形式。 但是，这些算法的核心步骤都是相同的：
谱聚类是从图论中演化过来的。主要思想是把所有的数据看做是空间中的点，这些点之间可以用边链接起来。距离比较远的两个点之间的边权重比较低，距离较近的两点之间权重较高，通过对所有的数据点组成的图进行切割，让切图后不同的子图间权重和尽可能低，而子图内的边权重和尽可能高，从而达到聚类的目的。
对于有边连接的两个点v i 和v j ,w ij >0，若没有边连接，w ij =0，度d i 定义为和它相连的所有边的权重之和，即
谱聚类中，通过样本点距离度量的相似矩阵S来获得邻接矩阵W。
构造邻接矩阵W的方法有 ϵ -邻近法，K邻近法和全连接法 。
ϵ -邻近法 :设置距离阈值ϵ，然后用欧氏距离s ij 度量任意两点x i 和x j 的距离，即s ij =||x i -x j || 2 2
邻接矩阵W定义为：
L=D-W,D为度矩阵，是一个对角矩阵。W为邻接矩阵。
其性质如下：
对于无向图G的切图，我们的目标是将图G(V,E)切成相互没有连接的k个子图，每个子图点的集合为：A 1 ,A 2 ,..A k ，它们满足A i ∩A j =∅,且A 1 ∪A 2 ∪...∪A k =V
对于任意两个子图点的集合A,B⊂V, A∩B=∅, 我们定义A和B之间的切图权重为：
RatioCut切图为了避免最小切图，对每个切图，不光考虑最小化cut(A 1 ,A 2 ,..A k )，它同时还考虑最大化每个子图点的个数，即：
Ncut切图和RatioCut切图很类似，但是把Ratiocut的分母|Ai|换成vol(Ai). 由于子图样本的个数多并不一定权重就大，我们切图时基于权重也更合我们的目标，因此一般来说Ncut切图优于RatioCut切图。
这样我们就可以继续按照RatioCut的思想，求出D -1/2 LD -1/2 的最小的前k个特征值，然后求出对应的特征向量，并标准化，得到最后的特征矩阵F,最后对F进行一次传统的聚类（比如K-Means）即可。
D -1/2 LD -1/2 相当于对拉普拉斯矩阵L做了一次标准化，
谱聚类主要的注意点为相似矩阵的生成方式，切图的方式以及最后的聚类方法。
最常用的相似矩阵的生成方式是基于高斯核距离的全连接方式，最常用的切图方式是Ncut。而到最后常用的聚类方法为K-Means。下面以Ncut总结谱聚类算法流程。
输入：样本集D=(x1,x2,...,xn)，相似矩阵的生成方式, 降维后的维度k1, 聚类方法，聚类后的维度k2
输出： 簇划分C(c1,c2,...ck2)
谱聚类算法的主要优点有：
1）谱聚类只需要数据之间的相似度矩阵，因此对于处理稀疏数据的聚类很有效。这点传统聚类算法比如K-Means很难做到
2）由于使用了降维，因此在处理高维数据聚类时的复杂度比传统聚类算法好。
谱聚类算法的主要缺点有：
1）如果最终聚类的维度非常高，则由于降维的幅度不够，谱聚类的运行速度和最后的聚类效果均不好。
转自： https://www.cnblogs.com/pinard/p/6221564.html
