【机器学习】谱聚类

本文介绍了一种定义在图上聚类算法-谱聚类。首先介绍谱聚类其实是保持图上节点之间的相似性对节点进行向量表示。然后介绍了谱聚类的目标函数-最小化原始相似性矩阵与样本向量表示,相似性的乘积，由此导出谱聚类与拉普拉斯矩阵的关系。最后介绍了谱聚类算法特点，其实际为成对相似性保持（pair-wise）算法。

图聚类-谱聚类

谱聚类是一种定义在图上的聚类算法，与其说是聚类算法，更像是一种图的向量表示。基于向量表示之后，一般可以采用其他的聚类方法完成最后聚类结果。所以谱聚类的类表示既依赖于向量表示也与之后采用的聚类算法有关。

对于一个图，我们一般用点的集合和边的集合来描述。即为。其中即为我们数据集里面所有的点。谱聚类根据图上节点之间的关系（关系度量：邻域，近邻图，全连接图），构建一个邻接矩阵来描述个节点之间的相似性：

由节点之间关系的对称性，显然相似性矩阵是对称矩阵。现在，我们希望学习到节点的向 量表示，使得相似性越大的两个节点的向量表示的差异尽可能的小。

因此，我们可以定义如下损失函数：

即当大时，相似性越大，尽可能小。上式经过如下变换，也就得到了谱聚类与拉普拉斯矩阵的关系：

其中是按行求和（按列求和），因此矩阵为的按行求和（按列求和)的对角矩阵。

其中其中，我们称为拉普拉斯矩阵。

因此，当我们约束时，我们的目标函数为：

其中表示所有样本在维构成的向量，由.所以目标函数右乘有，因此，最小化目标函数等价的前个最小特征值相加，对应的为前个最下特征值对应的特征向量构成。就此目标函数求解问题转变为特征向量求解问题。

得到图节点的向量表示之后，后面就可以采用常用的聚类算法进行聚类，比如Kmeans。

谱聚类算法流程

1. 确定图上节点关系度量，得到相似性度量矩阵；
2. 根据相似性度量矩阵得到拉普拉斯矩阵；
3. 对拉普拉斯矩阵求解前个最小特征值对应的特征向量，即为节点的向量表示；
4. 采用聚类算法对节点向量进行聚类。

谱聚类特点：

1）相似性度量矩阵限制了数据的表示为。

2）谱聚类对相似性度量矩阵的向量表示存在损失。

3）谱聚类的向量表示数学形式非常漂亮，代码实现方便。

4）聚类的效果与相似性度量矩阵的计算，表示，以及最终采用的聚类算法有关。