论文粗读“Highly-efficient Incomplete Large-scale Multi-view Clustering with Consensus Bipartite Graph”

2024-04-10 10:10:38 阅读数 1003

Wang S, Liu X, Liu L, et al. Highly-efficient incomplete large-scale multi-view clustering with consensus bipartite graph[C]//Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. 2022: 9776-9785.

摘要导读

多视图聚类任务因为可以融合来自不同视图的信息用于提交聚类性能，近年来受到了很多的关注。现有的多视图聚类方法大多有个假设，即：每个样本在所有的视图都是可见的。而实际的生活中，不完整的多视图无处不在，这就催生了不完整多视图聚类的研究。但现有的不完整多视图聚类较为复杂，在面对大规模数据集时通常会耗费大量的计算资源和时间。本文提出了一个基于二部图的不完整多视图聚类方法来解决上述问题。具体来说，通过将多视图锚点学习和不完整二部图统一到一个框架中，以相互配合实现性能的提升。通过尝试使用灵活的二部图来处理不完整多视图聚类，本文提出的方法只需要样本数的线性复杂度，很容易应用到大规模的数据集上。

二部图&多视图

二部图一种已经被广泛的应用于大规模数据集的多视图谱聚类中。二部图主要的优点是从代表样本点中选择/采样较少比例，并且来探索这些锚点与每个样本之间的关系。传统的多视图二部图框架中每个视图的计算可以写成：

其中

C^{(i)} \in \mathbb{R}^{d_i \times m}

代表在

i

-th视图中选择或采样了

m

个样本（锚点）。这样一来，要学习的表示图就可以从

\mathbb{R}^{n \times n}

减少到了

\mathbb{R}^{m \times n}

。在正则项的地方，只要学习与每个视图都相似的共享图矩阵

Z

就可以达到目的。
但从正则项也可以看出，该框架是没有办法直接应用到不完整多视图聚类中的，因为每个视图学习的

Z^{(i)}

在不完整多视图数据集中可能是不一致的，因此后续的正则项无效。

模型浅析（IMVC-CBG）

对于给定视图 $i$ 对应的 $X^{(i)} \in \mathbb{R}^{d_i \times n}$ ，首先通过构造 $A^{(i)} \in \mathbb{R}^{n \times n_i}$ 来定义视图的不完整性，

其中

h^{(i)} \in R^{n_i}

包含的是按顺序排列的、在

i

视图存在的样本的索引。

例如对于包含5（n=5）个样本的整体数据，若在第 $i$ 个视图缺失第 $1$ 个和第 $4$ 个样本即 $h^{(i)} \in R^{3}=\{2, 3, 5\}$ ，则 $A^{(i)} \in \mathbb{R} ^{5 \times 3}$ 表示为：
$\begin{pmatrix} 0&0&0\\ 1&0&0 \\ 0&1&0 \\ 0&0&0 \\ 0&0&1 \\ \end{pmatrix}$

由上述定义，可以得出 $X^{(i)}A^{(i)} \in \mathbb{R}^{d_i \times n_i}$ 包含了 $i$ -th视图内的所有完整样本。按照二部图的定义，单是图的二部图的构建可以写成：

C^{(i)}

和

Z^{(i)}

分别是该视图的代表性锚点信息以及其对应的代表性图矩阵。然而，当确实的比例较大时，由于当前视图的可见样本所包含的信息不充足，势必会影响所选的锚点的质量。
因此，本文利用各视图所有可见样本来迭代的进行锚点的选择，也就是说，学习共识的二部图结构信息，即在提出的方法中

C \in \mathbb{R}^{k \times m}

和

Z \in \mathbb{R}^{m \times n}

的构建是所有视图共享的。首先，将

X^{(i)}A^{(i)} \in \mathbb{R}^{d_i \times n_i}

映射到一个共同的潜在空间：

W^{(i)} \in \mathbb{R}^{k \times d_i}

是

i

-th视图对应的映射矩阵，

k

是聚类个数。其目标形式如下：

\alpha \in \mathbb{R}^{v \times 1}

是视图相关向量。

\lambda

是平衡共识二部图学习和正则项的超参数。
上述目标函数直接引入

A^{(i)}

使得空间复杂度为

\mathcal{O}(n^2)

，时间复杂度为

\mathcal{O}(n^3)

。
因此本文又引入了以下：

在优化的部分中揭示了 $X^{(i)}A^{(i)}{A^{(i)}}^T \in \mathbb{R}^{d_i \times n}=X^{(i)} \bigotimes P^{(i)}$ ，其中 $P^{(i)}=1_{d_i}a^{(i)} \in R^{d_i \times n}$ ， $a^{(i)}=[a_1^{(i)}, \cdots, a_n^{(i)}]^T$ ， $a_j^{(i)}=\sum_{l=1}^{n_i}A_{j,l}^{(i)}$ 。

对应上面的例子， $a^{(i)} \in R^{1 \times 5}=[0,1,1,0,1]$ ，而 $P^{(i)}$ 是 $d_i$ 个 $[0,1,1,0,1]$ stack在一起。 $X^{(i)} \bigotimes P^{(i)}$ 的对位相乘结果的每一行为当前这个特征维度在每个样本的表示，每一列为当前样本的表示，全 $0$ 代表该样本在给定视图中缺失。

通过这样的设计，原本空间复杂度 $\mathcal{O}(vn^2)$ 降低到了 $\mathcal{O}(dn)$ ，其中 $d=\sum_i^{v} d_i$ 。

将不完整多视图聚类和二部图进行了第一次结合，用于大规模数据集。

基于概率模型的解释

本文建立了具有转移概率矩阵的一步平稳马尔可夫随机游走模型。其转移概率矩阵

M=Z^T \in \mathbb{R}^{n \times m}

，因此，经由一步从第

i

个样本到第

j

个锚点的概率表示为：

上图中，缺失的样本与锚点之间连线都是虚线，意味着转移概率为

0

。通过将它们融合到具有适当拉伸的完整二部图

Z

中，两步转移概率矩阵可以表示为：

其中，

\Lambda

为

Z

对应的对角矩阵：

很容易证明，

S \in \mathbb{R}^{n \times n}

是一个双随机矩阵（每行或每列之和均为1），因此我们可以简单地对

Z

进行SVD分解，得到聚类标签。

参数更新

参数更新是使用的交替更新的方式，因为能力有限，这里不做推导。

感觉框架关于锚点 $C$ 的更新和 $Z$ 的计算是重点。是否可以将其使用深度学习框架进行优化将会是一个思考方向。