谱聚类算法

谱聚类算法建立在谱图理论基础上，与传统的聚类算法相比，它具有能在任意形状的样本空间上聚类且收敛于全局最优解的优点。

该算法首先根据给定的样本数据集定义一个描述成对数据点相似度的亲合矩阵,并j计算矩阵的特征值和特征向量 ， 然后选择合适 的特征向量聚类不同的数据点。谱聚类算法最初用于计算机视觉 、VLS I 设计等领域， 最近才开始用于机器学习中，并迅速成为国际上机器学习领域的研究热点。

谱聚类算法建立在图论中的谱图理论基础上，其本质是将聚类问题转化为图的最优划分问题，是一种点对聚类算法，对数据聚类具有很好的应用前景。

【参考文献】《A Tutorial on Spectral Clustering》

【算法简述】

Step.1:根据数据构造一个 Graph ，Graph 的每一个节点对应一个数据点，将相似的点连接起来，并且边的权重用于表示数据之间的相似度。把这个 Graph 用邻接矩阵的形式表示出来，记为 W 。

Step.2:把W的每一列元素加起来得到N(N为节点个数)个数，把它们放在对角线上（其他地方都是零），组成一个 的矩阵，记为D。并令L=D-W。

Step.3:求出L的前k个特征值（按照特征值的大小从小到大的顺序） 以及对应的特征向量 。

Step.4:把这 k个特征（列）向量排列在一起组成一个 N*k的矩阵，将其中每一行看作 k 维空间中的一个向量，并使用 K-means 算法进行聚类。聚类的结果中每一行所属的类别就是原来 Graph 中的节点亦即最初的 N 个数据点分别所属的类别。