图谱聚类的等价模型研究

Research on Equivalent Model of Graph Clustering

摘要: 聚类分析作为一类非监督学习方法，能够有效挖掘数据中的各类潜在关系。图谱聚类是一种基于相似矩阵的聚类算法，一般转化为无向图的划分问题。为扩展图谱聚类在大数据分析中的应用性，从拉普拉斯矩阵出发，结合邻接矩阵与度矩阵的特点，对图谱聚类的目标函数进行松弛，得到了一类更一般形式的图谱聚类模型。此外，还从理论上证明了松弛后的模型与原问题的等价性及其迭代点列的收敛性。

Abstract: As an unsupervised learning method, clustering analysis can effectively mine various potential re-lationships in data. Graph clustering is a clustering algorithm based on similarity matrix, which is generally transformed into the problem of undirected graph partition. In order to expand the ap-plication of atlas clustering in big data analysis, starting from Laplace matrix, combining the char-acteristics of adjacency matrix and degree matrix, the objective function of atlas clustering is re-laxed, and a more general form of atlas clustering model is obtained. In addition, the equivalence between the relaxed model and the original problem and the convergence of the iterative point se-quence are proved theoretically.

1. 引言

数据聚类是根据数据之间的相似性或特点，将数据划分为不同类别，使类内相似度大，类间相似度小。如今，聚类分析迅速成为各领域研究人员的研究方向之一，是人们进行信息挖掘、提取的重要手段，在计算机视觉有着广泛应用 [1] 。作为一种非监督学习方式，数据聚类也应用于数据挖掘、信号处理、图像压缩、信息储存等 [2] 。常见的聚类方法有k-means聚类 [3] 、非负矩阵聚类 [4] 、图谱聚类 [5] 等。

在处理高维且具有复杂结构的数据时，图谱聚类表现优异。实验数据和结论表明，图谱聚类算法在任意形状空间中得到的聚类效果收敛甚至全局最优 [6] ，计算复杂度低、对噪声数据不敏感 [7] 等优点都是我们优先考虑的聚类方法之一。图谱聚类(Spectral Clustering)基于图论中的谱图论原理，将聚类问题转化为图的最优划分问题，是一种点对聚类算法，聚类效果更优秀、适用性更广泛 [8] 。将数据转化为点对集合，构建合适的相似矩阵就显得尤为重要。

数据集 $X=\left\{x_1,x_2,\cdots ,x_n\right\}$ ，常见相似矩阵的构造可以通过图集中点与点之间的距离确定邻接矩阵(Adjacency Matrix) W：

$W_{i,j}=\exp \left(-\frac{d^2\left(x_i,x_j\right)}{2{\sigma }^2}\right)$ (1)

其中 $d\left(x_i,x_j\right)$ 表示两样本点之间的距离，常用欧式距离表示， $\sigma$ 为尺度参数，W是一个对称的非负矩阵。

度矩阵D (Degree Matrix)是一个对角矩阵，称对角线上的元素为度，表示点与其他点的连接和，通常写作：

$D_{i,j}={\displaystyle \underset{j}{\sum }{W}_{i,j}}$ (2)

定义拉普拉斯矩阵(Laplacian Matrix) $L=D-W$ 。

无向加权图 $G=\left(V,E\right)$ ，将G分为两个不相交的子图A、B，使得 $A\cap B=\varnothing$ ， $A\cup B=V$ ，在图论中，写作:

$Cut\left(A,B\right)={\displaystyle \underset{a\in A,b\in B}{\sum }w\left(a,b\right)}$ (3)

图像分割问题是根据点之间的相似程度来确定不同的区域。定义相邻点之间的相似程度为边，相似程度越大，从而所占权值就越大，由于不同区域之间的差异较大，所以相邻区域连通边的权值，一定是较小的值。

为了保证切图效果，一般有三种常用的切割方法：

$M-Cut$ (Minimum Cut) [9] ，也称作最小割图准则，使得所切边的权重最小，计算过程简单，从割图的效果来看，切割会向着小的区域偏移。目标函数表达式如下：

$MCut\left(A,B\right)=\min {\displaystyle \underset{u\in A,t\in V}{\sum }w\left(u,t\right)}$ (4)

$R-Cut$ (Ratio Cut) [10] ，也称作比例切割准则，最大化各子图中所含点数，降低过分切割的可能性。不同子集中，如果顶点个数差异过大，切割的结果会偏向一方，在实际聚类中运算时间较长。目标函数表达式如下：

$RCut\left(A,B\right)=\frac{Cut\left(A,V\right)}{\min \left\{\left|A\right|,\left|V\right|\right\}}$ (5)

其中 $\left|A\right|$ ， $\left|V\right|$ 分别表示图A，V中顶点的个数。

$N-Cut$ (Normalized Cut) [4] 也称作规范割集准则，将图的各边进行加权正则化，计算复杂度小，速度快，对处理稀疏矩阵数据聚类优异。聚类效果往往依赖相似矩阵的选择，不同相似矩阵最后得到的聚类结果也可能不同。目标函数表达式：

$NCut\left(A,B\right)=\frac{Cut\left(A,B\right)}{{\displaystyle \underset{a\in A,v\in V}{\sum }w\left(a,v\right)}}+\frac{Cut\left(A,B\right)}{{\displaystyle \underset{b\in B,v\in V}{\sum }w\left(b,v\right)}}$ (6)

其中 ${\displaystyle \underset{a\in A,v\in V}{\sum }w\left(a,v\right)}$ 是连接A中的节点的边的总权重。

本文结合已有的图谱聚类模型，利用拉普拉斯矩阵对 $N-Cut$ 目标函数进行变形，松弛 $DN-Cut$ (Direct Normalized Cut)目标函数，提出一种与 $DN-Cut$ 目标函数等价的模型，并补充了等价模型中解的可行性理论。

2. 图谱聚类中的拉普拉斯矩阵

图谱聚类最开始是使用邻接矩阵W中前c个最大特征值对应的特征向量进行聚类，但邻接矩阵W不能有效地表示各点之间的权重。拉普拉斯矩阵L很好地克服了这个问题。作为一种半正定矩阵，L中的任意行或者任意列元素相加为零，特征值为0对应的特征向量为1。常见两种标准型拉普拉斯矩阵：

$L_{nor}=D^{-1}L=I-D^{-1}W$

$L_{sym}=D^{-1/2}L{D}^{-1/2}=I-D^{-1/2}W{D}^{-1/2}$ .

如果行向量 $y^{\text{T}}$ 中有且仅有一个元素为1，其余元素为0，那么称这个向量为指标向量。由向量组 $y_l$ 构成的矩阵称为指标簇矩阵， $Y=\left\{y_1,y_2,\cdots ,y_c\right\}\in R^{n\times c}$ ， $y_{il}=1$ 表示 $x_i$ 分配到第j个簇里，对 $y_{il}$ 定义：

$y_{il}=\{\begin{array}{l}1,x_i\in A_i\\ 0,其他\end{array}$

$\epsilon$ -邻近法( $\epsilon$ -neighborhood)，确定 $\epsilon$ 的阈值，两点之间的权重要么为0，要么为 $\epsilon$ ，其中包含的信息较少，对距离的远近度量不够明确。k-邻域(k-near neighborhood)，利用KNN算法，取遍所有的样本点，距离每个样本最近的k个点作为近邻，但是这种取法会造成构建之后的邻接矩阵W非对称。

如何改进相似矩阵也是近几年 $N-Cut$ 算法研究的热点方向之一。Xie [11] 等人采用样本点的邻域和样本点之间的欧式距离作为局部标准差构造相似矩阵；杨婷 [12] 等人充分利用监督信息，借助L2,1范数的鲁棒性，学习得到合理的相似矩阵；Nie [13] 等人根据点的自适应性特点，局部连通地为每个数据点分配自适应和最优邻居点来学习得到相似矩阵。

扩充先验信息的数目也会提高聚类效果。同一聚类内的数据往往向着密度比较高的区域靠近,而在不同聚类之间存在一个数据分布相对稀疏的现象，由数据密度的特点，王玲 [14] 等人提出由密度敏感函数定义相似矩阵。

密度可调节长度：

$L\left(x_i,x_j\right)={\rho }^{dist\left(x_i,x_j\right)}-1$ (7)

其中 $dist\left(x_i,x_j\right)$ 为数据点 $x_i$ 与 $x_j$ 点之间的欧式距离， $\rho$ 为伸缩因子，密度敏感的距离测度定义为：

$D_{i,j}={\min }_{p\in P_{i,j}}{\displaystyle \underset{k=1}{\overset{\left|p\right|-1}{\sum }}L\left(p_k,p_{k+1}\right)}$ (8)

$P_{i,j}$ 表示数据点 $x_i$ 到 $x_j$ 的所有路径的集合，数据点之间的距离线段L作为权重E，表示图上长度为 $p\in V^l$ 的连接点和 $p_{\left|p\right|}$ 的路径。相似矩阵表示为：

$S_{i,j}=\frac{1}{{\min }_{p\in P_{i,j}}{\displaystyle \underset{k=1}{\overset{\left|p\right|-1}{\sum }}L\left(p_k,p_{k+1}\right)P_{i,j}}+1}$ (9)

$N-Cut$ 作为一种经典的聚类算法，目标是极小化各子图连边的和，先将图分成两个部分，之后的每一个步骤均将其中一个部分分成两个部分，直到满足某个条件之后停止分割。目标函数常写作：

${\min }_{Y^{\text{T}}DY=I}Tr\left(Y^{\text{T}}LY\right)$ (10)

为了求解目标函数(10)，研究人员也提出了关于(10)的算法优化过程。单位化拉普拉斯矩阵 $L_{sym}$ 前c个最大特征值对应的特征向量，对特征向量进行聚类 [15] 。构造矩阵 $P=D^{-1}W$ ，取矩阵P前c个最大特征值对应的特征向量。从实际聚类结果来看，当度矩阵D中的对角元素差距小的时候，聚类效果较佳。KVV算法则是求解 $R-Cut$ 目标函数值的最小值，减小了过分割图的可能性，算法时间较长。

3. 图谱聚类中的DN-Cut模型等价

等价替换 $N-Cut$ 目标函数也是求解图谱聚类问题的一个重要方向。利用拉普拉斯矩阵L，目标函数重新写作：

${\max }_{Y^{\text{T}}DY=I}Tr\left(Y^{\text{T}}WY\right)$ (11)

Yu [16] 等人提出 $N-Cut$ 的多分类算法，比例划分矩阵Z替换Y，即 $Z=Y{\left(Y^{\text{T}}WY\right)}^{-1/2}$ ，目标函数：

${\max }_{Z=Y{\left(Y^{\text{T}}WY\right)}^{-1/2},Y^{\text{T}}DY=I}Tr\left(Z^{\text{T}}WZ\right)$ (12)

作为比例划分矩阵的一种改进方法，Chen [17] 等人重写式子(12)：

${\max }_{F^{\text{T}}F=I}Tr\left(F^{\text{T}}{D}^{-1/2}W{D}^{-1/2}F\right)$ (13)

相比之前确定 $D^{-1/2}W{D}^{-1/2}$ 与 $D^{-1}W$ 前c个最大特征值对应的特征向量，Chen [18] 等人直接将其用矩阵M替换，提出直接规范谱切割(Direct Normalize Cut)模型，目标函数写作：

${\max }_{Y\in R^{n\times c},F=D^{-1/2}Y\left(Y^{\text{T}}DY\right)}Tr\left(F^{\text{T}}MF\right)$ (14)

其中 $M=D^{-1/2}W{D}^{-1/2}+\lambda I$ ， $D^{1/2}Y{\left(Y^{\text{T}}DY\right)}^{-1/2}$ ，I为单位矩阵，规定 $\lambda$ 是一个足够大的数值，可以使得M为半正定矩阵。

矩阵F、M带入目标函数(14)，有

$F^{\text{T}}MF={\left(Y^{\text{T}}DY\right)}^{-1/2}{Y}^{\text{T}}{D}^{1/2}\left(D^{-1/2}W{D}^{-1/2}+\lambda I\right)D^{1/2}Y{\left(Y^{\text{T}}DY\right)}^{-1/2}=\frac{Y^{\text{T}}WY}{Y^{\text{T}}DY}+\lambda I$ (15)

现求矩阵G。

$\begin{array}{c}G=MF=\left(D^{-1/2}W{D}^{-1/2}+\lambda I\right)D^{1/2}Y{\left(Y^{\text{T}}DY\right)}^{-1/2}\\ =D^{-1/2}WY{\left(Y^{\text{T}}DY\right)}^{-1/2}+\lambda I{D}^{1/2}Y{\left(Y^{\text{T}}DY\right)}^{-1/2}\\ =D^{-1/2}WY{\left(Y^{\text{T}}DY\right)}^{-1/2}+\lambda D^{1/2}Y{\left(Y^{\text{T}}DY\right)}^{-1/2}\end{array}$ (16)

等式(16)两边同时左乘 $D^{1/2}$ ，有

$D^{-1/2}G=WY{\left(Y^{\text{T}}DY\right)}^{-1/2}+\lambda DY{\left(Y^{\text{T}}DY\right)}^{-1/2}$ (17)

式子(17)两边同时右乘 ${\left(Y^{\text{T}}DY\right)}^{1/2}$ ，有

$D^{-1/2}G{\left(Y^{\text{T}}DY\right)}^{1/2}=WY+\lambda DY$ (18)

整理得到，

$WY=D^{1/2}G{\left(Y^{\text{T}}DY\right)}^{1/2}-\lambda DY$ (19)

$WY$ 的表达式带入(15)，有

$F^{\text{T}}MF=\frac{Y^{\text{T}}\left(D^{1/2}G{\left(Y^{\text{T}}DY\right)}^{1/2}-\lambda DY\right)}{Y^{\text{T}}DY}+\lambda I$ (20)

所以，

$F^{\text{T}}MF=\frac{Y^{\text{T}}{D}^{1/2}G}{{\left(Y^{\text{T}}DY\right)}^{1/2}}$ (21)

最后， $Tr\left(F^{\text{T}}MF\right)=Tr\left(\frac{Y^{\text{T}}{D}^{1/2}G}{{\left(Y^{\text{T}}DY\right)}^{1/2}}\right)$ 。矩阵 $Y^{\text{T}}DY$ 是一个对角矩阵， ${\left(Y^{\text{T}}DY\right)}^{1/2}$ 的第l行、第j列元素可表示为 $\sqrt{{\displaystyle \underset{i=1}{\overset{n}{\sum }}{d}_{ii}{y}_{il}{y}_{ij}}}$ ，由于向量 $y_l$ 中元素只能取0或者1，当 $j\ne l$ 时， $y_{il}{y}_{ij}=0$ ；当 $j=l$ 时，对角线上

第l个元素为 ${\left(Y^{\text{T}}DY\right)}^{1/2}=\sqrt{d_{ii}{y}_{il}^2}=\sqrt{d_{ii}}$ 。所以，有下列等式：

${\max }_{Y\in R^{n\times c}}{\displaystyle \underset{l=1}{\overset{c}{\sum }}\frac{y_l^{\text{T}}\sqrt{D}{g}_l}{\sqrt{y_l^{\text{T}}D{y}_l^{\text{T}}}}}={\max }_{Y\in R^{n\times c}}{\displaystyle \underset{l=1}{\overset{c}{\sum }}\frac{y_l^{\text{T}}\sqrt{D}{g}_l}{\sqrt{d_{ii}}}}$ (22)

求(21)式的最大值，采用放缩法松弛式子(22)，放缩分母，找到原目标函数的上界。观察发现 $\sqrt{d_{ii}}\ge \min \left\{\sqrt{d_{ii}}\right\}$ ，存在不等式：

${\max }_{Y\in R^{n\times c}}{\displaystyle \underset{l=1}{\overset{c}{\sum }}\frac{y_l^{\text{T}}\sqrt{D}{g}_l}{\sqrt{d_{ii}}}}\le {\max }_{Y\in R^{n\times c}}{\displaystyle \underset{l=1}{\overset{c}{\sum }}\frac{y_l^{\text{T}}\sqrt{D}{g}_l}{\min \left\{\sqrt{d_{ii}}\right\}}}$ (23)

因此，松弛后的目标函数可写做：

${\max }_{Y\in R^{n\times c}}Tr\left(Y^{\text{T}}\frac{\sqrt{D}}{\min \left\{\sqrt{d_{ii}}\right\}}G\right)$ (24)

式子(24)减少目标函数中出现指标向量 $y_l^{\text{T}}$ 次数的同时，也满足了对目标函数求最大值的目的。再对不等式(23)的右边进行整理，得到，

${\max }_{Y\in R^{n\times c}}{\displaystyle \underset{l=1}{\overset{c}{\sum }}\frac{y_l^{\text{T}}\sqrt{D}{g}_l}{\min \left\{\sqrt{d_{ii}}\right\}}}={\max }_{Y\in R^{n\times c}}{\displaystyle \underset{l=1}{\overset{c}{\sum }}{y}_l^{\text{T}}\sqrt{\frac{D}{\min \left\{\sqrt{d_{ii}}\right\}}}}{g}_l$ (25)

4. 图谱聚类中等价模型中解的理论研究

为了解决第l列的 $y_l$ ，我们采取固定矩阵Y某一列求解其他列的方式和迭代计算的方法。考虑目标函数中 $y_{ij}$ 从0到1的增量函数：

${s^{\prime }}_{il}=y_l^{\text{T}}\sqrt{\frac{D}{\min \left\{\sqrt{d_{ii}}\right\}}}{g}_l-y_{il}\sqrt{\frac{d_{ii}}{\min \left\{\sqrt{d_{ii}}\right\}}}{g}_{il}$ (26)

最优解 $y^{\prime }$ 中元素构成可表示为：

${y^{\prime }}_{il}=\langle l={\max }_{l^{\prime }\in \left[1,c\right]}\arg s_{i{l}^{\prime }}\rangle$ (27)

参数 $\langle .\rangle$ 如果为真，那么 ${y^{\prime }}_{il}=1$ ，若为假，那么 ${y^{\prime }}_{il}=0$ 。

现在证明等价模型中目标函数 ${\max }_{Y\in R^{n\times c}}Tr\left(Y^{\text{T}}\sqrt{\frac{D}{\min \left\{\sqrt{d_{ii}}\right\}}}G\right)$ 的收敛性。

设矩阵Y在第t次与第 $t+1$ 次迭代后的矩阵分别为 $Y_t$ 、 $Y_{t+1}$ 。带入G的表达式(16)，得到：

$Tr\left(Y^{\text{T}}\sqrt{\frac{D}{\min \left\{\sqrt{d_{ii}}\right\}}}{D}^{-1/2}WY{\left(Y^{\text{T}}DY\right)}^{-1/2}+Y^{\text{T}}\sqrt{\frac{D}{\min \left\{\sqrt{d_{ii}}\right\}}}\lambda D^{1/2}Y{\left(Y^{\text{T}}DY\right)}^{-1/2}\right)$ (28)

展开，

$Tr\left(Y^{\text{T}}\frac{W}{\sqrt{D\min \left\{\sqrt{d_{ii}}\right\}}}Y+\lambda \frac{{\left(Y^{\text{T}}DY\right)}^{1/2}}{\sqrt{\min \left\{\sqrt{d_{ii}}\right\}}}\right)=Tr\left(Y^{\text{T}}\frac{W}{\sqrt{D\min \left\{\sqrt{d_{ii}}\right\}}}Y\right)+Tr\left(\lambda \frac{Y^{\text{T}}{D}^{1/2}Y}{\sqrt{\min \left\{\sqrt{d_{ii}}\right\}}}\right)$ (29)

$Tr\left(\lambda \frac{Y^{\text{T}}{D}^{1/2}Y}{\sqrt{\min \left\{\sqrt{d_{ii}}\right\}}}\right)$ 中的 $\lambda$ 是一个足够大的数值，并且 $\min \left\{\sqrt{d_{ii}}\right\}$ 可以直接确定，与矩阵Y无关，所

以迭代过程无论进行到哪一次， $\lambda$ 和 $\min \left\{\sqrt{d_{ii}}\right\}$ 都不会对目标函数的收敛性产生影响。仿照文献 [18] 中定理1的证明过程，能够得出：

$Tr\left(\lambda \frac{Y_t^{\text{T}}{D}^{1/2}{Y}_t}{\sqrt{\min \left\{\sqrt{d_{ii}}\right\}}}\right)\le Tr\left(\lambda \frac{Y_{t+1}^{\text{T}}{D}^{1/2}{Y}_{t+1}}{\sqrt{\min \left\{\sqrt{d_{ii}}\right\}}}\right)$ (30)

为了方便书写，记 $Q=\frac{W}{\sqrt{D\min \left\{\sqrt{d_{ii}}\right\}}}$ ，那么，

$Tr\left(Y^{\text{T}}\frac{W}{\sqrt{D\min \left\{\sqrt{d_{ii}}\right\}}}Y\right)=Tr\left(Y^{\text{T}}QY\right)$ (31)

通过等式(29) (30)，易知

$Tr\left(Y_t^{\text{T}}Q{Y}_t\right)\le Tr\left(Y_{t+1}^{\text{T}}Q{Y}_t\right)$ (32)

由迹的性质，

$Tr\left(Y_{t+1}^{\text{T}}Q{Y}_t\right)-Tr\left(Y_{t+1}^{\text{T}}Q{Y}_{t+1}\right)=Tr\left(Y_{t+1}^{\text{T}}Q\left(Y_t-Y_{t+1}\right)\right)$ (33)

当 $Y_t=Y_{t+1}$ 时， $Tr\left(Y_{t+1}^{\text{T}}Q\left(Y_t-Y_{t+1}\right)\right)=0$ ，此时， $Tr\left(Y_{t+1}^{\text{T}}Q{Y}_t\right)=Tr\left(Y_{t+1}^{\text{T}}Q{Y}_{t+1}\right)$ ，所以，

$Tr\left(Y_t^{\text{T}}Q{Y}_t\right)\le Tr\left(Y_{t+1}^{\text{T}}Q{Y}_{t+1}\right)$ (34)

$Y_t\ne Y_{t+1}$ 时，仍然采取固定某一列求解其他列的迭代计算的方法。 $Y_{t+1}^{\text{T}}Q$ 是一个非负矩阵，根据式子(26)、(27)，有

$Tr\left(Y_{t+1}^{\text{T}}Q\left(Y_t-Y_{t+1}\right)\right)\le 0$ (35)

综上所述，成立不等式：

$Tr\left(Y_t^{\text{T}}\frac{W}{\sqrt{D\min \left\{\sqrt{d_{ii}}\right\}}}{Y}_t\right)+Tr\left(\lambda \frac{Y_t^{\text{T}}{D}^{1/2}{Y}_t}{\sqrt{\min \left\{\sqrt{d_{ii}}\right\}}}\right)\le Tr\left(Y_{t+1}^{\text{T}}\frac{W}{\sqrt{D\min \left\{\sqrt{d_{ii}}\right\}}}{Y}_{t+1}\right)+Tr\left(\lambda \frac{Y_{t+1}^{\text{T}}{D}^{1/2}{Y}_{t+1}}{\sqrt{\min \left\{\sqrt{d_{ii}}\right\}}}\right)$ (36)

算法实现流程可总结为：

1) 输入聚类个数k，构造相似矩阵，将数据集 $X=\left\{x_1,x_2,\cdots ,x_n\right\}$ 转化为度矩阵与邻接矩阵；

2) 找到一个足够大的数值 $\lambda$ ，使得 $M=D^{-1/2}W{D}^{-1/2}+\lambda I$ 为半正定矩阵；

3) 重复运算 $G=D^{-1/2}WY{\left(Y^{T}DY\right)}^{-1/2}+\lambda D^{1/2}Y{\left(Y^{T}DY\right)}^{-1/2}$ ，并且通过等式(27)更新矩阵Y的数值；

4)目标函数(24)收敛，输出矩阵Y。

不同于传统的选择相似矩阵 $D^{-1}W$ 与 $D^{-1/2}W{D}^{-1/2}$ 的前k个最大特征值对应的特征向量进行聚类，该等价模型只需要初始化矩阵Y，直接对数据集进行相似矩阵的构造，得出度矩阵与邻接矩阵。同时，在算

法流程中， $y_l^{\text{T}}\sqrt{\frac{D}{\min \left\{\sqrt{d_{ii}}\right\}}}{g}_l$ 与 $y_{il}\sqrt{\frac{d_{ii}}{\min \left\{\sqrt{d_{ii}}\right\}}}{g}_{il}$ 的数值结果可由前一次的迭代过程直接得出，通过等式

(27)，在之后的迭代过程中根据上一次得出的数值结果更新矩阵Y。目标函数(24)在迭代运算中，是一个单调递增的过程，对有限数据集 $X_n$ 进行图谱聚类，当数据集分到所有簇时，迭代过程停止。

5. 结束语

算法过程的优化、目标函数的选择、相似矩阵的构造、谱切割的切割方法等都是当前图谱聚类研究的重要方向。本文从拉普拉斯矩阵出发，结合邻接矩阵与度矩阵的特点，对图谱聚类的目标函数进行松弛，得到了一类更具有一般形式的图谱聚类模型。采用放缩的方法，提出一种可与 $DN-Cut$ 等价的数学模型，并证明了等价模型的收敛性，对下一步数值实验测试的可行性提供了理论依据。