【论文阅读】Multi-view co-clustering with multi-similarity
摘要
多视图共聚类（Multi-view co-clustering）是一种同时对多视图数据的样本和特征两个维度进行聚类的方法，近年来受到广泛关注。其目标是利用多视图数据的双重性，以获得更优的聚类结果。然而，大多数现有的多视图共聚类算法仅考虑数据的样本-特征信息，而忽略了样本-样本、特征-特征信息，因此无法充分挖掘数据中潜在的信息。
为此，本文提出了一种基于多重相似性的多视图共聚类方法。特别地，在谱聚类的基础上，我们提出了一种构造图的方法，以提升聚类性能，使其不再局限于样本与特征之间的相关性。同时，受集成算法的启发，采用多种共聚类算法来计算各视图数据的相似性信息，从而提高算法的鲁棒性。
与现有的多视图共聚类方法相比，所提出的算法能够更全面地利用各视图数据中的相似性信息，包括样本-样本、特征-特征及样本-特征的相似性信息。在多个基准数据集上进行了实验。由于充分挖掘并利用了更多的相似性信息，实验结果在三项评价指标上均优于对比方法。特别是在包含共现特征（如“单词-文档”）的数据上，方法取得了更优的结果，并能够实现更高的准确率。
引言
共聚类（Co-clustering），又称双聚类（Bi-clustering）或双向聚类（Two-way clustering），是一种针对具有双重特征数据的聚类方法 [1–4]。与传统聚类不同，共聚类能够同时对样本和特征进行聚类，从而挖掘数据矩阵中的局部模式。由于数据的双重性，共聚类已被广泛应用于多个领域。例如，在文档聚类中，相似的文档通常对应于相似的主题，共聚类的目标是发现属于相似主题的相似文档 [1]。在电影推荐系统中，具有相同兴趣的用户通常会对相同类型的电影打出相似的评分，共聚类则用于识别喜好相似电影的用户群体 [5]。近年来，研究人员提出了许多基于不同理论的共聚类方法，如基于图论的共聚类方法 [1]、基于信息论的新型聚类技术 [4]、基于矩阵分解的共聚类方法 [6] 等。
如今，越来越多的数据集来自多个来源或以不同视角表示。例如，文档可以用多种语言描述 [7]，图像可以由不同特征提取器（如 HOG、LBP、SIFT、GIST 等）提取的特征集表示 [8]，网页可以用其自身内容以及指向该网页的超链接内容来表示 [9]。每种表示方式被称为一个“视图”（View），每个视图描述相同的对象，但从不同的角度出发，不同视图间的信息往往是互补的。多视图学习（Multi-view learning）是机器学习中的重要研究领域，已广泛应用于推荐系统 [10]，近年来，研究人员也成功将其应用于其他领域，如疾病与 miRNA 关联关系的发现 [11]。
多视图聚类（Multi-view clustering）[12] 旨在利用视图间的互补信息，以获得更精确和稳健的聚类结果。为了充分利用多视图的互补性，一些研究人员提出了协同正则化（Co-regularization）[13] 和协同训练（Co-training）[14] 等方法。此外，还提出了多视图加权融合（Multi-view weighted fusion）方法，以考虑各视图信息的重要性差异 [15–17]。与单视图聚类相比，多视图聚类能够获得更优的聚类效果，同时已成功应用于图像分类、文本分类 [7]，甚至阿尔茨海默病诊断 [18]。
然而，大多数现有的多视图聚类方法仅基于样本维度，忽略了数据的双重特性，例如样本与特征之间的共现关系。鉴于共聚类的优势，近年来，研究人员发展了多视图共聚类算法 [19–21]。相比传统的多视图聚类，多视图共聚类能够同时对多视图数据的样本和特征两个维度进行聚类，从而进一步挖掘数据的潜在信息，提升聚类效果。
尽管已有一些多视图共聚类算法利用了数据的双重特性，但大多数方法仅关注样本与特征的共现关系，而未考虑样本-样本和特征-特征的关系信息，这可能限制其性能。例如，基于二部图的多视图共聚类算法 [19] 使用每个视图的原始数据构建二部图，并利用谱聚类算法进行聚类，但它未考虑样本-样本和特征-特征之间的相似性信息。事实上，所有信息都会对聚类结果产生影响 [22, 23]，若仅考虑样本-特征之间的信息，数据的潜在信息无法被充分挖掘和利用，从而限制聚类性能。因此，聚类过程中应充分考虑数据中的所有信息。
为此，本文提出了一种基于多重相似性（Multi-similarity）的多视图共聚类算法，以最大化数据及其特征之间的相似性信息利用率。其核心思想如下（如图 1 所示）：首先，考虑到集成算法（Ensemble algorithm）较强的鲁棒性，我们采用集成方法计算各视图数据的样本-样本、特征-特征和样本-特征三种相似性矩阵，并基于这些矩阵构建图结构，以充分挖掘数据的潜在信息，随后采用谱聚类进行聚类。然后，为了区分各视图的重要性，对不同视图对应的图进行多视图加权融合 [17]，并采用谱聚类完成最终聚类任务。
本文的主要贡献如下：
- 提出了一种基于多重相似性的多视图共聚类算法，能够充分挖掘数据中的潜在信息；
- 在谱聚类的基础上，提出了一种用于多视图共聚类的数据图构建方法，该方法不局限于样本-特征相关性；
- 在多个基准数据集上的实验结果表明，该方法优于现有方法，具有更优的聚类效果。
模型
谱共聚类（Spectral Co-clustering）
谱聚类是一种基于图论的聚类方法，常用于解决共聚类问题 [2, 3, 27, 28]。它将数据表示为图中的节点，节点之间的边权重表示它们的相似性。权重越高，表示两个节点对应的数据属于同一类别的可能性越大。
假设输入数据为 X∈Rn×d，其中 n 表示样本数，每个样本具有 d 个特征。构造的二部图 G=(S,F,W)由样本和特征组成，其中：
- S={S1,S2,...,Sn} 表示样本节点集，
- F={F1,F2,...,Fd}表示特征节点集，
- W表示节点之间的边的权重。
将 X 视为图的权重矩阵，Xij代表节点 i（第 i个样本）与节点 j（第 j 个特征）之间的边的权重，则 G 的邻接矩阵 W 可表示为：
该问题可转换为图 G 的节点划分问题，其目标是在最大化子图内部边权重的同时，最小化子图之间的边权重。谱聚类的目标是找到图的最小标准割（minimum standard tangent），其目标函数可表示为：
其中，Pr∈Rn×k和 Pc∈Rd×k 分别表示样本和特征的聚类划分结果（k 为簇的数量）。 如果第 i 个节点属于第 j个簇，则 Pij=1，否则 Pij=0。
由于求解上述问题是 NP-Hard（非确定性多项式难）问题，通常对 P 进行松弛处理，使其满足约束 PTP=I。于是，问题转换为以下优化问题的最优解：
其中，L 是图的拉普拉斯矩阵，定义为 L=D−W，其中 D 为度矩阵，计算方式如下：
根据 [22] 和 [28]，矩阵 P可通过计算特征值获得。最后，对 P 应用传统聚类方法（如 k-means）以获得最终的聚类标签。
基于二部图的多视图共聚类
给定一个多视图数据集 {X(1),X(2),…,X(v)}，其中 v 表示视图的数量。基于谱聚类的多视图共聚类算法 [19] 为每个视图构建一个二部图，然后将多个图融合为一个图，并最终通过谱聚类获得聚类结果。其目标函数可表示如下：
指示矩阵 P 在所有视图中保持统一。二部图对应的拉普拉斯矩阵为：
L(q)=D(q)−W(q)
其中，W(q)是二部图的邻接矩阵，与公式 (1) 相同，W(q)可表示为：
对应的度矩阵 D(q) 计算方式为：
由于 P 是共享的，问题可以转换为：
根据公式 (6)，使用已获得的 P 来更新 α，并根据公式 (8) 更新 P，然后迭代更新直到收敛。
综上，该算法的流程如下：
- 初始化每个视图的权重 α，并根据公式 (7) 计算每个视图的二部图邻接矩阵；
- 根据公式 (8) 计算 P；
- 根据公式 (6) 更新 α；
- 重复步骤 2) 和 3)，直至收敛。同时，作者提供了收敛性分析。
显然，该方法的权重矩阵是原始数据，同时，样本之间（sample-sample）和特征之间（feature-feature）的权重为 0，即未考虑它们之间的相似性信息。基于此，提出了一种基于多相似性的多视图共聚类算法，该算法充分考虑了所有图的连接，并将二部图转换为混合图。
相似性计算
协同聚类集成旨在通过结合多个基本协同聚类方法，生成更稳健的结果。
本文采用集成方法获取数据矩阵两个维度之间的相似性信息，包括特征-特征、样本-样本及样本-特征相似性矩阵，并将该信息作为权重矩阵。
为了更好地表示样本-特征相似性，提出了一种基于 [29] 的聚类集成方法。该方法指出，样本的聚类结果依赖于局部特征集（子空间）。根据多个聚类结果，构建基本概率矩阵，以表示每个特征对每个样本提供信息的概率。最终结果基于该矩阵计算得到。第 q 视角数据的概率矩阵计算如下：
由于该矩阵包含样本与特征之间的相关信息，因此将其作为光谱聚类中样本与特征节点之间边的权重，即样本与特征之间的相似度。同时，在集成过程中引入均方残差（Mean Sum-squared Residue, MSR）[30] 以评估协同聚类方法得到的结果。给定协同聚类块 X，其 MSR 计算如下：
其中，xiJ 表示行 I 的平均值，xIj表示列 J 的平均值，xIJ表示总体平均值。MSR 值越小，表明基本协同聚类方法所得结果的相关性越高；反之，MSR 越大，相关性越低。因此，定义一个样本-特征相关性矩阵 Θ∈Rk×d，其中
在这种情况下，值越大，表明特征与样本的相关性越高。通过整合所有基本协同聚类方法的信息，可以定义以下样本-特征关联矩阵：
大多数协同聚类算法仅考虑样本与特征之间的相似性。然而，根据 [22]，样本与样本之间、特征与特征之间的相互信息也会影响协同聚类的结果。传统的聚类算法（如 k-means）仅考虑样本之间的相似性，即沿特征维度的相似性。而与传统聚类方法不同，不仅考虑样本之间的相似性，还考虑特征之间的相似性。
受 PCE [29] 和 CSPA 算法 [31] 计算样本-特征相似性方法的启发，定义了样本-样本和特征-特征的相似性为两个对象在同一聚类中的比例，并得到如下相似性计算公式：
其中，Sss代表样本之间的相似性，而 Sff代表特征之间的相似性。
目标函数
在计算相似度矩阵后，这三个矩阵被组合形成混合图的邻接矩阵，并构建数据矩阵的数据图，即：
充分考虑了样本与特征之间的所有相关信息，从而获得了理想的聚类结果。在为每个视角构建数据图之后，可以得到每个视角的谱聚类目标函数：
根据公式 (6)，计算出每个视角的权重，最终问题被转化为求解以下目标函数的最优解：
最优解是 L的最小 k 个特征值所对应的特征向量。根据文献 [17]，利用该结果更新权重，并最终收敛。图 1 展示了整体 MVCCMS 框架的流程，而完整算法流程如算法 1 所示。
实验
co-clustering可以再思考思考。。。