Ding 等［100，149⁃150，156］将非负矩阵三分解（Non⁃negative Matrix Tri⁃factorization，NMTF）应用到Co⁃clustering 中。假设聚类目标是将矩阵X的行向量聚成k 类，将X 的列向量聚成l 类。当矩阵X 可能包含负值时，NMTF 的优化问题为［100］

其中，G∈Rn×k，S∈Rk×l和H∈Rm×l，‖·‖F代表矩阵的Frobenius 范式，定义为‖A‖F＝tr（AAT）。从式（4.1）可以看出，非负矩阵三分解的目标是用矩阵G，S 和H 的乘积近似表示矩阵X，其中，S 可看作数据矩阵X 的一种简单表示。矩阵GS∈Rn×l的列向量形成了一组针对X 样本空间的基，其中的每一个列向量对应于一个样本类。H 是列系数矩阵，可以根据H 的数值，来判断X 的样本所属的样本类。以X 的第i 列为例，如果

那么，X 的第i 列就属于第r 个列类，SHT∈Rk×m的行向量形成了一组针对X 行空间的基，SHT的每一个列向量对应于一个特征类。G 是行系数矩阵，可以根据G 的数值来判断X 行向量所属的类。

当数据矩阵X 为非负时，可以在式（4.1）中添加S 为非负矩阵的约束，得到目标函数为

其中，矩阵S 的元素代表了特征类和样本类之间的相似度。

为了使矩阵G 和H 更加符合实际要求，Ding 等［100］在NMTF 中增加了正交约束，得到目标函数为

为了在Co⁃clustering 中考虑流式数据形的几何结构，Gu 等［129］引入了双图正则约束非负矩阵三分解的DRCC 算法，其目标函数为(www.daowen.com)

其中，LH为特征空间内的Laplacian 矩阵；LG为样本空间的Laplacian矩阵。

当样本数或者特征数非常大的时候，基于NMTF 的Co⁃clustering 算法［100，149⁃150］的计算复杂度会显著提高。此外，这些算法往往假设数据矩阵X 可存储在内存中。

奇异值分解（Singular Value Decomposition，SVD）［157］作为线性代数中一种重要的低秩矩阵近似技术，用途是解最小平方误差法和数据压缩。但是，SVD 在时间消耗上是QR 分解［158］的近10 倍的计算时间。

CUR 分解技术［159］首先根据行和列的概率分布选择表示行和列的左右矩阵，然后通过左右矩阵对中间矩阵进行计算。为降低Co⁃clustering算法的计算效率，Pan 等［160］应用CUR 分解技术选择矩阵X 的n′个行向量，m′个列向量，提出了基于行列分解的Co⁃clustering 算法（co⁃clustering based on Column and Row Decomposition，CRD）。

CMD［161］和Colibri［120］低秩矩阵近似方法是通过CUR 的改进而来。与CUR 相比，在同样的时间空间开销下，CMD 可以得到更高的精度。Colibri 方法［120］可以有效处理规模比较大的静态和动态网络的分析。