近年来，现代信息系统产生了大量包含多种类型数据的数据集，并且不同类型数据之间相互关联^{[1, 2]}。如在论文出版系统中包含4种类型的数据^{[1, 2]}，分别是作者、论文、会议和关键词。将这种相互关联的多种类型数据称为高阶异构数据^{[3, 4]}。为了有效挖掘高阶异构数据隐藏的模式，有学者提出了高阶异构数据联合聚类 (简称为高阶联合聚类)方法^{[3, 4]}。已有的高阶联合聚类算法包括基于图划分的方法^{[3, 5, 6]}，主要有CBGC^[3]和CIHC^[6]；基于信息论的方法^{[4, 7]}，如CIT^[4]和AD-HOCC^[7]；基于k部图学习的方法^{[8, 9]}，包括RSN ^[8]和SKGC^[9]；基于矩阵分解的方法^{[1, 2, 10, 11]}，代表算法有SRC^[10]和SS-NMF^[11]；基于Goodman Kruskal的方法CoStar^[12]；基于排名的聚类方法，代表算法有NetClus^[13]。这些聚类算法都是硬划分方法，一个数据要么“属于”或“不属于”一个聚簇。然而在实际应用中，有些数据同时属于多个聚簇，聚簇结构之间存在重叠的部分，硬划分方法并没有考虑这种聚簇重叠问题。为此，本文提出了一种基于最小平方和残差的高阶模糊联合聚类算法(minimum sum-squared residue for high-order fuzzy co-clustering,MSR-HFCC)。MSR-HFCC算法利用平方和残差衡量不同聚簇数据之间关系的相异度^{[14, 15]}，评估聚类质量。为了更好地描述重叠聚簇的聚类结果^{[16, 17]}，在平方和残差中引入模糊概念，将聚类问题转化为最小化模糊平方和残差的优化问题。

1 MSR-HFCC算法 1.1 MSR-HFCC算法目标函数

由X¹={x₁¹,…,x_n1¹}，X²={x₁²,…,x_n2²}，…，X^m={x₁^m,…,x_n^mm}共m种类型数据组成高阶异构数据，n_i(1≤i≤m)表示第i种类型数据Xⁱ的数据个数。Xⁱ与X^j的关系矩阵是 D ^(ij)=(d_pq^(ij))_ni×nj，p行q列元素d_pq^(ij)表示x_pⁱ与x_q^j之间的关系强度。设Xⁱ(1≤i≤m)划分为K_i个聚簇，残差h_pqkikj^(ij)是一种衡量关系d_pq^(ij)与x_pⁱ和x_q^j所在聚簇内所有数据之间的关系相异度的指标^{[14, 15]}。高阶联合聚类的目标是寻找每种类型数据最优的划分，使得不同聚簇内数据之间的关系相异度最低。可见，高阶联合聚类问题可以转化为不同聚簇内的数据之间关系残差h_pqkikj^(ij)的平方和最小化问题。另外，MSR-HFCC算法利用隶属度描述对象属于某聚簇的程度。其目标函数定义如下：

式中，β_ij为数据{Xⁱ,X^j}之间关系的权值，满足=1；隶属度u_kip⁽ⁱ⁾满足如下限制条件：

数据项为模糊项；T_u⁽ⁱ⁾为模糊度参数，用于调节隶属度u_kip⁽ⁱ⁾的模糊程度；关系强度d_pq^(ij)的残差h_pqkikj^(ij)有如下两种定义方式^{[14, 15]}：

其中,

通过拉格朗日乘子法求解u_kip⁽ⁱ⁾的更新规则，构造如下拉格朗日函数：

其中,λ_p⁽ⁱ⁾为对应限制条件(2)的拉格朗日乘子。由拉格朗日最优解的必要条件，分别求L关于λ_p⁽ⁱ⁾和u_kip⁽ⁱ⁾的偏导数，并令其为零，则：

结合式(9)和式(10)可得u_kip⁽ⁱ⁾的更新迭代规则：

综上所述，根据式(3)、式(4)两种残差计算方式，设计MSR-HFCC算法的两种计算形式MSR-HFCC_H1和MSR-HFCC_H2。其中，MSR-HFCC_H1算法的计算步骤描述如下：

MSR-HFCC_H2与MSR-HFCC_H1的计算步骤类似，不同之处在于MSR-HFCC_H2利用式(5)、式(6)、式(7)和式(4)分别更新 (a_kikj^(ij))^τ+1、(a_pkj^(ij))^τ+1、(a_kiq^(ij))^τ+1和(h_pqkikj^(ij))^τ+1。

根据式(11)计算u_kip⁽ⁱ⁾的时间复杂度为O(n_iK_i；根据式(5)、式(6)、式(7)计算a_kikj^(ij)的时间复杂度分别为O(n_in_j)、O(n_j)和O(n_i)。高阶异构数据涉及m种类型的数据，MSR-HFCC_H1和MSR-HFCC_H2的时间复杂度均为，τ其中τ为迭代次数。

2 实验分析 2.1 数据集

采用文献^[13]的方法，利用Cora论文数据集，由会议、论文和单词组成高阶异构数据集T1和T2，每个类别包含300篇论文；采用文献^[12]的方法，利用Corel图像数据集，由图像、单词和图像分割组构建高阶异构数据集I1和I2，每个类别包含100张图像；采用文献^[5]的方法，利用IAPR TC-12 Benchmark数据集，由图像、特征和单词构建高阶异构数据集P1，每个类别包含300张图像。论文和图像类别、单词数见表 1。

图 1为MSR-HFCC算法在I1数据集上挖掘的聚簇结构可视化结果，可以看出存在明显的 聚簇重叠结构，T1、T2、I2和P1数据集中也具有类似的现象。图 2为P1数据集中图像对于第一个聚簇的隶属度值，260～376之间的图像为聚簇重叠部分，隶属度值接近于0.5。表 2为P1数据集中聚簇重叠部分图像的隶属度示例。这些图像既属于traveler聚簇，又属于animal聚簇，因此难以严格地将数据划分到traveler聚簇或者animal聚簇中。可见，MSR-HFCC_H算法更客观地描述了现实世界数据的聚类结果，能够有效地分析具有聚簇重叠结构的数据。

图 1 聚簇结构可视化结果 Fig. 1 Results of Visual Cluster Structures

图选项

图 2 P1数据集图像隶属度值分布 Fig. 2 Distribution of Memberships of Images in P1 Dataset

图选项

表 2 P1数据集中重叠聚簇部分图像隶属度值示例 Tab. 2 Examples of Membership of Images at the Overlaps of Clusters

表选项

将MSR-HFCC_H1和MSR-HFCC_H2算法与目前已有的5种“硬划分”高阶联合聚类算法进行准确率对比，包括CBGC^[3]、CIT^[4]、RSN^[8]、NMF^[11]和CoStar^[12]。图 3所示为以上算法聚类结果的正则化互信息(normalized mutual information,NMI)值。首先，MSR-HFCC_H1和MSR-HFCC_H2算法的聚类结果明显优于目前已有的5种“硬划分”高阶联合聚类算法，这一定程度上是由于模糊方法能更有效地描述具有重叠聚簇结构数据的聚类结果。其次，MSR-HFCC_H2算法的聚类结果略优于MSR-HFCC_H1的。其原因在于MSR-HFCC_H2算法在计算残差时不仅考虑了某对数据之间的关系与数据所在聚簇内其他关系的差异，而且考虑了与此对数据相关的其他关系的差异。

图 3 不同算法聚类结果的NMI值 Fig. 3 NMI Values of Clustering Results

图选项

从图 4可以看出，MSR-HFCC_H1和MSR-HFCC_H2算法在5个数据集上迭代40次左右达到收敛状态，具有较好的收敛性。

图 4 MSR-HFCC算法的收敛性 Fig. 4 Convergence of MSR-HFCC Algorithm

图选项

本文提出了基于最小平方和残差的高阶模糊联合聚类算法MSR-HFCC_H1和MSR-HFCC _H2，该算法能够更有效地描述和分析具有聚簇重叠结构的高阶异构数据，获得更加符合实际的聚类结果。