谱聚类算法

发布时间： 2022-05-17 15:08:45

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

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

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

(3)求出L的前k个特征值(按照特征值的大小从小到大的顺序)及对应的特征向量。

(4)把这k个特征(列)向量排列在一起组成一个N×k的矩阵，将其中每一行看做是k维空间中的一个向量，并使用k-Means算法进行聚类。聚类结果中的每一行所属的类别为原来图中的节点，也即最初的N个数据点的类别。

谱聚类算法最初用于计算机视觉、VLSI设计等领域，最近才开始用于机器学习中，并迅速成为国际上机器学习领域的研究热点。谱聚类算法建立在图论中的谱图理论基础上，其本质是将聚类问题转化为图的最优划分问题，为一种点对聚类算法，对数据聚类具有很好的应用前景。