本文是作者毕业设计<<基于用户物品成对分块的协同过滤算法>>的节选，现粘贴在此为的是重温，如果对读者有益，倍感荣幸。

  谱聚类将对象映射成无向图中的点，对象之间的相似度做为点之间的边的权值，然后基于一些准则设计出合适的图划分算法。谱聚类在图像分割，电路设计，文档分析中都得到了广泛的应用。著名的谱聚类方法有：ratio-cut[1]和normalized-cut[2]。

  Normalized-cut算法力图将无向图的顶点集划分成多个不相交的类，使得类间的相似度很低，类内的相似度很高，同时类的大小要尽量平衡。将图 $G=(V,W)$ ( $W$ 为边权矩阵)划分成两个部分

$\mathcal{V}_1,\mathcal{V}_2,\mathcal{V}_1\bigcup \mathcal{V}_2=V, \mathcal{V}_1\bigcap \mathcal{V}_2=\emptyset$

那么划分的代价为：

$cut(\mathcal{V}_1,\mathcal{V}_2)=\sum_{u\in \mathcal{V}_1,v \in \mathcal{V}_2}w(u,v)$

不过这样的目标函数将导致孤立的点自成一类，所以修改目标函数为：

$Ncut(\mathcal{V}_1,\mathcal{V}_2)=\frac{cut(\mathcal{V}_1,\mathcal{V}_2)}{assoc(\mathcal{V}_1,V)}+\frac{cut(\mathcal{V}_1,\mathcal{V}_2)}{assoc(\mathcal{V}_2,V)}$

其中 $assoc(\mathcal{V}_1,V)=\sum_{u\in \mathcal{V}_1,v \in V}w(u,v)$ ，也就是 $\mathcal{V}_1$ 中所有点的关联的边的权值之和。我们最小化 $Ncut(\mathcal{V}_1,\mathcal{V}_2)$ 就是希望划分的cut最小同时划分的两个类大小比较均匀，这里类的大小用 $assoc(\mathcal{V}_1,V)$ 表示。 $Ncut(\mathcal{V}_1,\mathcal{V}_2)$ 度量了类间距离距离，而类内距离定义为：

$Nassoc(\mathcal{V}_1,\mathcal{V}_2)=\frac{assoc(\mathcal{V}_1,\mathcal{V}_1)}{assoc(\mathcal{V}_1,V)}+\frac{assoc(\mathcal{V}_2,\mathcal{V}_2)}{assoc(\mathcal{V}_2,V)}$

因为有关系：

$Ncut(\mathcal{V}_1,\mathcal{V}_2)=2-Nassoc(\mathcal{V}_1,\mathcal{V}_2)$

所以最小化 $Ncut(\mathcal{V}_1,\mathcal{V}_2)$ 等价于最大化 $Nassoc(\mathcal{V}_1,\mathcal{V}_2)$ ，也就是最小化类间距离等价于同时最大化类内距离。而Ratio-cut算法的目标函数为：

$\text{Ratio-cut}(\mathcal{V}_1,\mathcal{V}_1)=\frac{cut(\mathcal{V}_1,\mathcal{V}_2)}{|\mathcal{V}_1|}+\frac{cut(\mathcal{V}_1,\mathcal{V}_2)}{|\mathcal{V}_2|}$

即类的大小等于类中点的个数。

可以看出Ratio-cut算法和Normalized-cut算法的不同在于类的大小的定义，进一步讲，我们觉得是每个顶点在聚类中的影响力的定义不同。Normalized-cut算法中顶点关联边的权值和越大，这个点在聚类中的影响力就越大，而Ratio-cut算法中所有点的影响力是一样的。问题是，究竟怎么理解顶点的聚类影响力呢？在我们看来，所谓点在聚类过程中的影响力其实就是指这个顶点能够担任类领导角色的能力大小。Normalized-cut算法中一个点关联边的权值和越大，那么他成为类领导的能力也就越大，也就是他单独领导一个类的机会越大。当一个点的领导力越大时，那么周围的一些点就越容易进入该点所在的类。Normalized-cut算法中两个关联边权值和都很大的顶点几乎不可能在同一个类中，因为这样会导致该类的大小大大增加，从而破坏追求平衡类划分的目标。相反，两个关联边权值和都很大的顶点很容易在两个不同的类中。领导力很大顶点几乎很难再同一个类中，而是分布在不同的类中，从而在各自的类中充当领导角色。这样的理解对于我们针对具体应用问题的谱聚类具有重要的指导意义。

在中[3]，作者给每个顶点v赋一个正权重 $weight(v)$ ，并令

$\mathbf{W_g}=\left[ \begin{array}{cccc} weight(1) &0 & \cdots & 0 \\ 0 & weight(2) & & 0\\ \vdots & & \ddots & \vdots\\ 0 & 0 & \cdots & weight(|V|) \end{array} \right]$

然后最小化如下目标函数：

$\mathcal{Q}(\mathcal{V}_1,\mathcal{V}_2)=\frac{cut(\mathcal{V}_1,\mathcal{V}_2)}{weight(\mathcal{V}_1)}+\frac{cut(\mathcal{V}_1,\mathcal{V}_2)}{weight(\mathcal{V}_2)}$

其中 $weight(\mathcal{V}_i)=\sum_{v \in \mathcal{V}_i}weight(v)$ ，这其实也是一种类大小的定义方法。当我们用如下方式定义一个顶点划分时：

$q_i=\left\{ \begin{array}{c} +\sqrt{\frac{\eta_2}{\eta_1}},i \in \mathcal{V}_1\\ -\sqrt{\frac{\eta_1}{\eta_2}},i \in \mathcal{V}_2 \end{array} \right.$   (1)

其中， $\eta_i=weight(\mathcal{V}_i)$ ，那么我们就可以重新表示,

$\mathcal{Q}(\mathcal{V}_1,\mathcal{V}_2)=\frac{\mathbf{q}^T\mathbf{L}\mathbf{q}}{\mathbf{q}^T\mathbf{W_g}\mathbf{q}}$

其中 $\mathbf{L}$ 是图的Laplacian矩阵， $\mathbf{L}=\mathbf{D}-\mathbf{W}$%uFF0C$\mathbf{D}$ ， $\mathbf{D}$ 是一个对角阵，第i个主对角元素是 $\mathbf{W}$ 的第i行元素之和。我们的目的就是希望最小化 $\mathcal{Q}(\mathcal{V}_1,\mathcal{V}_2)$ 。当我们不再限定 $\mathbf{q}$ 的取值如(1)式而是允许他在实数范围内取任意值时，这就变成了广义Rayleigh商，而广义Rayleigh商的最小化解就是广义特征值问题:

$\mathbf{L}\mathbf{x}=\lambda\mathbf{W_g}\mathbf{x}$

的最小特征值对应的特征向量。然而，我们可以发现 $\mathbf{e}$ 是最小特征值 $\lambda=0$ 对应的特征向量，但是这是一个平凡的划分，没有意义。所以我们的问题变为：

$\left\{ \begin{aligned} \text{min}\qquad & \frac{\mathbf{q}^T\mathbf{L}\mathbf{q}}{\mathbf{q}^T\mathbf{W_g}\mathbf{q}}\\ \text{s.t}\qquad & \mathbf{q}\neq 0,\mathbf{q}^T\mathbf{W_g}\mathbf{e}=0\\ \end{aligned} \right.$

这个问题的解就是广义特征值问题:

$\mathbf{L}\mathbf{x}=\lambda\mathbf{W_g}\mathbf{x}$

的第二小特征值对应的特征向量。顺便指出的是，因为 $\mathbf{W_g}$ 正定， $\mathbf{L}$ 半正定，所以上述广义特征值问题的解存在且均为大于等于0的实数。由于广义特征值求解起来比标准特征值问题更加费时，所以我们可以将其转换为标准特征值问题：

$\mathbf{W_g}^{-\frac{1}{2}}\mathbf{L}\mathbf{W_g}^{-\frac{1}{2}}\mathbf{x}=\lambda\mathbf{x}$

这里注意因为 $\mathbf{W_g}$ 是对角矩阵，逆矩阵 $\mathbf{W_g}^{-\frac{1}{2}}$ 很容易求得，并且 $\mathbf{W_g}^{-\frac{1}{2}}$ 也是对角矩阵，从而在与其他矩阵的乘法中是可交换的，而这里交换矩阵乘法的顺序的目的在于使得 $\mathbf{W_g}^{-\frac{1}{2}}\mathbf{L}\mathbf{x}\mathbf{W_g}^{-\frac{1}{2}}$ 是对称矩阵，这将更有利于求解。

参考文献：

[1].Hagen L, Kahng A B. New spectral methods for ratio cut partitioning and clustering. Computer-aided design of integrated circuits and systems, ieee transactions on, 1992, 11(9):1074–1085.

[2].Shi J, Malik J. Normalized cuts and image segmentation. Pattern Analysis and Machine Intelligence, IEEE Transactions on, 2000, 22(8):888–905.

[3].Dhillon I S. Coclustering documents and words using bipartite spectral graph partitioning. Proceedings ofProceedings of the seventh ACMSIGKDD international conference on Knowledge discovery and data mining.ACM, 2001. 269–274.