-
摘要: 大规模多视图聚类旨在解决传统多视图聚类算法中计算速度慢、空间复杂度高, 以致无法扩展到大规模数据的问题. 其中, 基于锚点的多视图聚类方法通过使用整体数据集合的锚点集构建后者对于前者的重构矩阵, 利用重构矩阵进行聚类, 有效地降低了算法的时间和空间复杂度. 然而, 现有的方法忽视了锚点之间的差异, 均等地看待所有锚点, 导致聚类结果受到低质量锚点的限制. 为定位更具有判别性的锚点, 加强高质量锚点对聚类的影响, 提出一种基于加权锚点的大规模多视图聚类算法(Multi-view clustering with weighted anchors, MVC-WA). 通过引入自适应锚点加权机制, 所提方法在统一框架下确定锚点的权重, 进行锚图的构建. 同时, 为增加锚点的多样性, 根据锚点之间的相似度进一步调整锚点的权重. 在9个基准数据集上与现有最先进的大规模多视图聚类算法的对比实验结果验证了所提方法的高效性与有效性.Abstract: Large-scale multi-view clustering aims to solve the problem that traditional methods cannot scale to large-scale data due to slow computational speed and high complexity. Among them, the anchor-based multi-view clustering method constructs a reconstruction matrix for the entire dataset by utilizing a set of anchor points. Clustering with the reconstruction matrix effectively reduces the time and space complexity of the algorithm. However, existing methods ignore the differences among anchor points and treat them equally, resulting in clustering results limited by low-quality anchor points. In order to identify more discriminative anchor points and enhance the influence of high-quality anchors on clustering, a large-scale multi-view clustering algorithm based on weighted anchors (MVC-WA) was proposed. By introducing an adaptive anchor weighting mechanism, the proposed method determine the weights of anchors in a unified framework for the construction of anchor graphs. Meanwhile, in order to increase the diversity among anchors, the weights of anchors were further adjusted according to the similarity between them. Experimental results comparing with existing state-of-the-art large-scale multi-view clustering algorithms on nine benchmark datasets validate the efficiency and effectiveness of the proposed method.
-
Key words:
- Multi-view clustering /
- large-scale clustering /
- anchor /
- weight learning
-
聚类旨在将数据根据相似性划分成簇[1]. 作为一种无监督学习方法, 聚类在数据挖掘、模式识别等领域有着广泛应用[2]. 在现实世界中, 信息有多种呈现模式. 来自不同渠道的信息就构成了多视图数据. 与传统的单视图聚类方法相比, 多视图聚类通过探索各个视图间一致与互补的信息进一步提升了聚类效果[3-4]. 例如, 无监督条件下物体的轨迹追踪往往通过对不同时间下的同一目标进行聚类实现. 单个传感器提取的信息可能会导致目标难以区分甚至误判, 而融合多个传感器的信息则可以大大提升目标追踪的准确率[5].
现有的多视图聚类方法可以划分为4类, 协同训练、多核聚类、多视图图聚类和多视图子空间聚类[6]. 其中, 协同训练方法通过在不同视图间进行迭代学习来最大化视图间的一致性信息[7]. 多核聚类以不同的方式组合各个视图上的预定义核来得到统一的核, 再进一步执行聚类[8]. 多视图图聚类从获取数据结构信息的角度出发, 寻找融合了各个视图结构信息的图[9-11]. 上述3类方法从不同角度有效地处理了多视图数据, 但是它们难以解决高维数据聚类难的问题. 作为子空间聚类的扩展, 多视图子空间聚类方法提出从所有视图的低维子空间中学习统一的特征表示, 在高维多视图数据上取得了良好的效果[12-14]. 随着大数据时代的到来, 待处理的数据往往具有非常大的规模. 例如, 在社交网络分析中每个人都是一个节点, 而需要分析的节点往往数以亿计[15]. 然而现有的多视图子空间聚类算法耗时长、空间消耗大, 难以应用在大规模任务中[16-17].
为降低算法的复杂度, 一些相关研究提出将锚点应用在多视图子空间聚类中. 与传统算法构造所有样本点之间的相似度矩阵不同, 基于锚点的方法只学习锚点与样本点之间的关系, 大大降低了时间与空间消耗[18]. 现有基于锚点的方法根据其得到锚点的策略可以分为启发式采样和学习策略两类. 其中, 启发式采样策略由于可扩展性强、效果稳定, 近年来受到了广泛研究. 具体来说, 基于采样策略的方法通过K-means或随机采样等方式在构建相似度矩阵之前确定锚点, 根据固定的锚点进行后续的聚类过程[19]. 现有的方法忽视了采样得到的锚点质量层次不齐这一事实, 均等地看待所有锚点, 导致聚类效果受限. 此外, 不加选择地直接使用所有锚点没有充分考虑到锚点之间的相关性, 降低了具有不同代表性的锚点的利用率.
针对上述问题, 本文提出一种基于加权锚点的多视图聚类算法(Multi-view clustering with weighted anchors, MVC-WA). 具体来说, 我们根据每个视图中选取的锚点的重要性与冗余性来学习权重, 使得更具代表性和独特性的锚点具有更高的权重. 本文的贡献可以总结如下:
1) 引入自适应锚点加权机制, 区分不同重要性的锚点. 在统一的框架下进行锚图的构造与锚点权重的优化, 减少不相关锚点对后续聚类的影响, 加强可信锚点的权重.
2) 考虑锚点的多样性, 根据锚点彼此之间的联系来判断锚点信息是否冗余, 降低相似锚点的权重, 增加独特锚点的权重, 有效增强锚点的表示能力.
3) 设计两步迭代优化算法有效解决产生的优化问题, 在多个基准数据集上进行了实验. 实验结果证明了本文方法的有效性与效率.
1. 相关工作
在本节中, 首先介绍多视图子空间聚类及其基础模型, 然后从现有方法处理大规模数据的困境出发, 介绍基于锚点的多视图子空间聚类方法. 表1总结了本文中使用的主要符号.
表 1 本文使用的主要符号Table 1 Summary of notations符号 定义 $n$ 数据点数量 $k$ 类别数 $v$ 视图数 $m$ 锚点数 $d^{(p)}$ 第$p$个视图上数据的维度 ${\boldsymbol{X}}^{(p)} \in \mathbf{R}^{d^{(p)} \times n}$ 第$p$个视图的数据矩阵 ${\boldsymbol{A}}^{(p)} \in \mathbf{R}^{d^{(p)} \times m}$ 第$p$个视图的锚点矩阵 ${\boldsymbol{Z}}^{(p)} \in \mathbf{R}^{m \times n}$ 第$p$个视图上的锚图 ${\boldsymbol{W}}^{(p)} \in \mathbf{R}^{m \times m}$ 第$p$个视图上的权重矩阵 ${\boldsymbol{M}}^{(p)} \in \mathbf{R}^{m \times m}$ 第$p$个视图上锚点的相关性矩阵 1.1 多视图子空间聚类
子空间聚类假设每个数据点可以由同一子空间中其他点的线性组合表示[20]. 基于上述假设, 给定多视图数据$ \left\{{\boldsymbol{X}}^{(p)}\right\}_{p=1}^{v} $, 其中$ {\boldsymbol{X}}^{(p)} \in \mathbf{R}^{d^{(p)} \times n} $表示第$ p $个视图上维度为$ d^{(p)} $的数据, 多视图子空间聚类首先得到每个视图上的自表达矩阵$ {\boldsymbol{S}}^{(p)}\in \mathbf{R}^{n \times n} $
$$ \begin{equation} \min \limits_{{\boldsymbol{S}}^{(p)}}\|{\boldsymbol{X}}^{(p)}-{\boldsymbol{X}}^{(p)} {\boldsymbol{S}}^{(p)}\|_{{\rm{F}}}^{2}+\lambda f({\boldsymbol{S}}^{(p)}) \end{equation} $$ $$ \;\;\;\text{s.t.}\; {\boldsymbol{S}}^{(p)} \geq 0, ({{\boldsymbol{S}}^{(p)}})^{\rm{T}} \bf{1}=\bf{1}\qquad\qquad \quad $$ (1) 其中, $({{\boldsymbol{S}}^{(p)}})^{\rm{T}}\bf{1}=\bf{1}$确保$ {\boldsymbol{S}}^{(p)} $的每一列加起来为$ 1 $, 表示每个样本点可由其他样本的线性组合重构. $ {\boldsymbol{S}}^{(p)}_{i, j} $代表第$ i $个样本与第$ j $个样本之间边的权重, 因此可以将$ {\boldsymbol{S}}^{(p)} $视为一个$ n\times n $大小的无向图. $ f(\cdot) $是正则化函数, $ \lambda $是平衡系数. 不同的$ f(\cdot) $带来了满足不同约束的自表达矩阵$ {\boldsymbol{S}}^{(p)} $. 例如Lu等[21]提出对矩阵施加稀疏约束, 捕捉数据的局部结构; Wang等[22]提出寻找数据的低秩表示, 保证图的连通性.
在得到各个视图上的自表达矩阵$ \left\{{\boldsymbol{S}}^{(p)}\right\}_{p=1}^{v} $后, 将它们融合得到统一的自表达矩阵$ {\boldsymbol{S}}\in \mathbf{R}^{n \times n} $, 在一些方法中这一步也与各视图上的学习阶段共同进行. 将一致的$ {\boldsymbol{S}} $作为谱聚类的输入, 即得到最终的聚类结果. 由于$ {\boldsymbol{S}} $的大小为$ n\times n $, 构建自表达矩阵与谱聚类的时间复杂度都为$ {{\rm{O}}}\left(n^{3}\right) $, 空间复杂度则为${{\rm{O}}}\left(n^{2}\right)$.
基于上述框架, 最近提出了许多多视图子空间聚类方法. Gao等[23]建议在每个视图中学习一个独立的子空间表示, 然后使用统一的索引矩阵得到一个共同的聚类结果. 为了探索多视图表示的互补性, Cao等[24]建议引入Hilbert-Schmidt的独立性准则作为正则项. 考虑到从多个视图中学习到的子空间表示可能是多余的, Zhang等[25]将不同视图的子空间表示矩阵视为一个张量, 探索具有低秩约束的视图之间的交集信息. 另一个重点是对子空间表示施加适当的约束, 例如低秩约束[22]或稀疏约束[21]. Brbic等[26]建议建立一个同时满足低秩和稀疏性的共识亲和矩阵. 尽管现有的方法在聚类性能上已经取得了不错的效果, 但高额的时间消耗与空间需求限制了它们在大规模任务上的应用.
1.2 基于锚点的多视图子空间聚类
为了处理大规模的聚类任务, 近期一些文献提出将锚点引入到多视图子空间聚类中. 在传统的多视图子空间聚类中, 最重要的一步就是构造大小为$ n\times n $的自表达矩阵$ {\boldsymbol{S}} $, 而这个完整的关系图也带来了高计算复杂度. 基于锚点的方法首先从$ n $个样本点中选取$ m $个具有代表性的点作为锚点($ m $远小于$ n $), 然后构造一个大小为$ m\times n $的锚图$ {\boldsymbol{Z}} $来代替原有的自表达矩阵$ {\boldsymbol{S}} $, 从而大大降低了图构造阶段与谱聚类阶段的计算复杂度.
在基于锚点的多视图子空间聚类算法中, 锚点的选取对后续的聚类过程有关键的影响. 现有方法主要通过启发式采样和学习两种策略来得到锚点. 启发式采样是指通过启发式的策略从所有样本中选取或生成锚点, 根据固定的锚点构建锚图进行后续的聚类. 基于学习策略得到锚点的方法则将锚点的学习与锚图的构建统一到同一框架中, 采取轮替优化的方式对锚点进行更新. Wang等[27]提出将锚点学习与锚图构建统一到同一框架中, 两者相互协商以提升聚类性能; 基于文献[27], Liu等[28]对构建的锚图施加连通性约束, 直接从生成的锚图中生成聚类标签而无需后处理. 尽管通过学习得到锚点的方法有效解决了聚类效果受到初始锚点质量限制的问题, 但将锚点作为待更新变量引入优化过程中会带来额外的时间消耗. 目前, 基于启发式采样的方法由于可扩展性强、效果稳定, 受到了研究人员的广泛关注. Kang等[29]提出使用K-means得到每个视图上的锚点, 然后分别构建锚图; Li等[19]对所有样本进行打分, 然后选取评分排名靠前的样本点作为锚点. 虽然上述方法打破了多视图子空间聚类难以处理大规模问题的困境, 也取得了良好的聚类效果, 但是它们都不加区分地使用采样得到的锚点, 没有考虑锚点的质量差异. 此外, 现有方法仅从锚点与样本点的关系出发, 忽视了锚点彼此之间的相关性. 为解决上述问题, 在第2节中提出了一种对锚点进行自适应加权的多视图子空间聚类方法.
2. 基于加权锚点的多视图聚类算法
2.1 基于锚点的聚类模型
基于锚点的方法首先对每个视图上的数据$ \left\{{\boldsymbol{X}}^{(p)}\right\}_{p=1}^{v} $使用K-means, 得到由$ m $个锚点组成的锚点矩阵$ \left\{{\boldsymbol{A}}^{(p)}\right\}_{p=1}^{v} $, 其中$ {\boldsymbol{A}}^{(p)} \in \mathbf{R}^{d^{(p)} \times m} $. 与传统多视图子空间聚类构造完整的自表达矩阵$ {\boldsymbol{S}}^{(p)}\in \mathbf{R}^{n \times n} $不同, 基于锚点的方法构造$ {\boldsymbol{A}}^{(p)} $与$ {\boldsymbol{X}}^{(p)} $之间的关系矩阵$ {\boldsymbol{Z}}^{(p)}\in \mathbf{R}^{m \times n} $. 相应地, 目标函数转换为用锚点矩阵$ {\boldsymbol{A}}^{(p)} $重建$ {\boldsymbol{X}}^{(p)} $
$$ \begin{equation} \min \limits_{{\boldsymbol{Z}}^{(p)}}\sum\limits_{p=1}^{v}\|{\boldsymbol{X}}^{(p)}-{\boldsymbol{A}}^{(p)} {\boldsymbol{Z}}^{(p)}\|_{{\rm{F}}}^{2} \end{equation} $$ $$ \;\;\;\text{s.t.} \; {\boldsymbol{Z}}^{(p)} \geq 0, ({{\boldsymbol{Z}}^{(p)}})^{{\rm{T}}} \bf{1}=\bf{1}\quad\; $$ (2) 其中, $({{\boldsymbol{Z}}^{(p)}})^{{\rm{T}}} \bf{1}=\bf{1}$保证了每个原始样本点是由所有锚点的线性组合来重构的. 构造关系矩阵$ {\boldsymbol{Z}}^{(p)} $的复杂度从原来的$ {{\rm{O}}}\left(n^{3}\right) $降到了$ {{\rm{O}}}\left(nm^2\right) $, 而$ m $远小于$ n $, 因此这一步的复杂度为$ {{\rm{O}}}\left(n\right) $.
2.2 目标函数
注意到在上述模型中, 通过K-means得到的锚点质量难以保证, 因此不同锚点对重构样本点的贡献是不同的. 考虑到采样锚点的质量差异, 本文引入自适应加权矩阵$ \left\{{\boldsymbol{W}}^{(p)}\right\}_{p=1}^{v} $. $ {\boldsymbol{W}}^{(p)}\in \mathbf{R}^{m \times m} $是一个对角矩阵, 其中$ {\boldsymbol{W}}^{(p)}_{ii} $是第$ p $个视图上第$ i $个锚点的权重. 那么, 本文的目标式有以下形式:
$$ \begin{equation} \min \limits_{{\boldsymbol{W}}^{(p)}, {\boldsymbol{Z}}^{(p)}} \sum\limits_{p=1}^{v}\left\|{\boldsymbol{X}}^{(p)}-{\boldsymbol{A}}^{(p)}{\boldsymbol{W}}^{(p)} {\boldsymbol{Z}}^{(p)}\right\|_{{\rm{F}}}^{2} \end{equation} $$ $$ \begin{split} &\text{s.t.} \; {\boldsymbol{Z}}^{(p)} \geq 0, ({{\boldsymbol{Z}}^{(p)}})^{{\rm{T}}} \bf{1}=\bf{1}\\&\quad\;\;\sum\limits_{i=1}^{m}{\boldsymbol{W}}^{(p)}_{ii}=m, {\boldsymbol{W}}^{(p)}_{ii}\geq 0 \quad\quad\quad\;\;\end{split} $$ (3) 其中, $ {\boldsymbol{W}}^{(p)} $通过作用在锚点矩阵$ {\boldsymbol{A}}^{(p)} $的每一列上实现对锚点的加权, 加权后的锚点指导锚图的构建, 而构建好的锚图又反过来指导锚点权重的学习.
为了减少冗余, 增强锚点的多样性, 本文进一步对权重矩阵加入正则化项. 首先根据锚点矩阵计算出锚点之间的相关性矩阵${\boldsymbol{M}}^{(p)}=({{\boldsymbol{A}}^{(p)}})^{{\rm{T}}}{\boldsymbol{A}}^{(p)}$, $ {\boldsymbol{M}}^{(p)}_{i j} $越大意味着第$ i $个锚点与第$ j $个锚点之间的相关性越高. 为了使锚点包含的信息更丰富, 我们希望相关性高的锚点权重更低, 因此将正则化项定义为$({\boldsymbol{\omega}^{(p)}})^{{\rm{T}}}{\boldsymbol{M}}^{(p)}\boldsymbol{\omega}^{(p)}$. 通过最小化该正则化项, 可以大大降低同时赋予相似度很高的两个锚点较大权重的风险. 而当两个锚点的相关性较小时, 引入多样化正则化项将增加赋予它们较大权重的概率. 因此, 这一正则化项有利于提升所选锚点的多样性. 最终, 待求解的目标函数可以表述为
$$ \begin{equation} \begin{split} & \min\limits _{{\boldsymbol{W}}^{(p)}, {\boldsymbol{Z}}^{(p)}}\sum\limits_{p=1}^{v}\left\|{\boldsymbol{X}}^{(p)}-{\boldsymbol{A}}^{(p)}{\boldsymbol{W}}^{(p)} {\boldsymbol{Z}}^{(p)}\right\|_{{\rm{F}}}^{2}\;+ \\&\qquad\beta\sum\limits_{p=1}^{v}({\boldsymbol{\omega}^{(p)}})^{{\rm{T}}}{\boldsymbol{M}}^{(p)}\boldsymbol{\omega}^{(p)} \end{split} \end{equation} $$ $$ \begin{split} &\text{s.t.} \; {\boldsymbol{Z}}^{(p)} \geq 0, ({{\boldsymbol{Z}}^{(p)}})^{{\rm{T}}} \bf{1}=\bf{1}\\ &\qquad\sum\limits_{i=1}^{m}{\boldsymbol{W}}^{(p)}_{ii}=m, {\boldsymbol{W}}^{(p)}_{ii}\geq 0 \qquad\qquad\;\;\end{split} $$ (4) 其中, $ \boldsymbol{\omega}^{(p)}\in \mathbf{R}^{m \times 1} $是由$ {\boldsymbol{W}}^{(p)} $的对角元素组成的向量, $ \beta $是平衡正则化项影响的系数.
2.3 优化算法
为了解决上述优化问题, 本文提出一个两步的迭代算法轮替更新所有变量. 首先固定$ \left\{{\boldsymbol{Z}}^{(p)}\right\}_{p=1}^{v} $, 优化$ \left\{{\boldsymbol{W}}^{(p)}\right\}_{p=1}^{v} $; 然后固定$ \left\{{\boldsymbol{W}}^{(p)}\right\}_{p=1}^{v} $, 优化$ \left\{{\boldsymbol{Z}}^{(p)}\right\}_{p=1}^{v} $.
2.3.1 固定$ \left\{{\boldsymbol{Z}}^{(p)}\right\}_{p=1}^{v} $优化$ \left\{{\boldsymbol{W}}^{(p)}\right\}_{p=1}^{v} $
当$ \left\{{\boldsymbol{Z}}^{(p)}\right\}_{p=1}^{v} $固定时, 优化$ \left\{{\boldsymbol{W}}^{(p)}\right\}_{p=1}^{v} $等价于解决下面的问题:
$$ \begin{equation} \begin{split} \min \limits_{{\boldsymbol{W}}^{(p)}} \sum\limits_{p=1}^{v}&\left\|{\boldsymbol{X}}^{(p)}-{\boldsymbol{A}}^{(p)}{\boldsymbol{W}}^{(p)} {\boldsymbol{Z}}^{(p)}\right\|_{{\rm{F}}}^{2}\;+ \\&\beta\sum\limits_{p=1}^{v}({\boldsymbol{\omega}^{(p)}})^{{\rm{T}}}{\boldsymbol{M}}^{(p)}\boldsymbol{\omega}^{(p)} \end{split} \end{equation} $$ $$\text{s.t.}\;\sum\limits_{i=1}^{m}{\boldsymbol{W}}^{(p)}_{ii}=m, {\boldsymbol{W}}^{(p)}_{ii}\geq 0 \qquad $$ (5) 由于各个视图上的目标式相互独立, 没有交叉项, 可以在各个视图上依次独立更新$ {\boldsymbol{W}}^{(p)} $. 在第$ p $个视图上, 式(5)可以改写为
$$ \begin{equation} \min\limits_{\boldsymbol{\omega}^{(p)}} \frac{1}{2}({\boldsymbol{\omega}^{(p)}})^{{\rm{T}}}{\boldsymbol{G}}^{(p)}\boldsymbol{\omega}^{(p)}+({{\boldsymbol{a}}^{(p)}})^{{\rm{T}}}\boldsymbol{\omega}^{(p)} \end{equation} $$ $$ \text{s.t.}\;({\boldsymbol{\omega}^{(p)}})^{{\rm{T}}}\bf{1}=m, \boldsymbol{\omega}^{(p)}\geq 0 \qquad\;\;\;\; $$ (6) 其中, ${\boldsymbol{G}}^{(p)} = ({\boldsymbol{Z}}^{(p)}({{\boldsymbol{Z}}^{(p)}})^{{\rm{T}}})\otimes(({{\boldsymbol{A}}^{(p)}})^{{\rm{T}}}{\boldsymbol{A}}^{(p)})+\beta{\boldsymbol{M}}^{(p)}.$ ${\boldsymbol{a}}^{(p)}=[a_{1}^{(p)}, \cdots, a_{m}^{(p)}]^{{\rm{T}}}$是一个向量, 其中的第$i$个元素$a_{i}^{(p)}=-{\boldsymbol{H}}^{(p)}_{ii}$, ${\boldsymbol{H}}^{(p)} = {\boldsymbol{Z}}({{\boldsymbol{X}}^{(p)}})^{{\rm{T}}}{\boldsymbol{A}}^{(p)}$. 式(6) 是一个典型的二次规划问题, 可以使用现有的工具包进行求解.
2.3.2 固定$ \left\{{\boldsymbol{W}}^{(p)}\right\}_{p=1}^{v} $优化$ \left\{{\boldsymbol{Z}}^{(p)}\right\}_{p=1}^{v} $
当$ \left\{{\boldsymbol{W}}^{(p)}\right\}_{p=1}^{v} $固定时, 优化$ \left\{{\boldsymbol{Z}}^{(p)}\right\}_{p=1}^{v} $等价于解决下面的问题:
$$ \begin{equation} \min \limits_{{\boldsymbol{Z}}^{(p)}} \sum\limits_{p=1}^{v} \left\|{\boldsymbol{X}}^{(p)}-{\boldsymbol{A}}^{(p)}{\boldsymbol{W}}^{(p)} {\boldsymbol{Z}}^{(p)}\right\|_{{\rm{F}}}^{2} \end{equation} $$ $$\text{s.t.}\;{\boldsymbol{Z}}^{(p)} \geq 0, ({{\boldsymbol{Z}}^{(p)}})^{{\rm{T}}} \bf{1}=\bf{1}\qquad\quad\;$$ (7) 与优化$ {\boldsymbol{W}}^{(p)} $时一样, 上述问题可以在各个视图上独立求解. 去除掉无关项, 在第$ p $个视图上的问题等价于下列形式:
$$ \begin{equation} \min \limits_{{\boldsymbol{Z}}^{(p)}} \operatorname{tr}\left( ({{\boldsymbol{Z}}^{(p)}})^{{\rm{T}}}{\boldsymbol{Q}}^{(p)}{\boldsymbol{Z}}^{(p)}-2({{\boldsymbol{X}}^{(p)}})^{{\rm{T}}}{\boldsymbol{A}}^{(p)}{\boldsymbol{W}}^{(p)} {\boldsymbol{Z}}^{(p)}\right) \end{equation} $$ $$ \text{s.t.}\;{\boldsymbol{Z}}^{(p)} \geq 0, ({{\boldsymbol{Z}}^{(p)}})^{{\rm{T}}} \bf{1}=\bf{1}\qquad\qquad\qquad\qquad\quad $$ (8) 其中, ${\boldsymbol{Q}}^{(p)}=({{\boldsymbol{W}}^{(p)}})^{{\rm{T}}}({{\boldsymbol{A}}^{(p)}})^{{\rm{T}}}{\boldsymbol{A}}^{(p)}{\boldsymbol{W}}^{(p)}$. 注意到$ {\boldsymbol{Z}}^{(p)} $中的每一列之间是独立的, 将优化$ {\boldsymbol{Z}}^{(p)} $第$ j $列元素的问题表述为下列形式:
$$ \begin{equation} \begin{split} &\min \frac{1}{2} ({{\boldsymbol{Z}}^{(p)}_{:, j}})^{{\rm{T}}} {\boldsymbol{Q}}^{(p)} {\boldsymbol{Z}}^{(p)}_{:, j}+f^{{\rm{T}}} {\boldsymbol{Z}}^{(p)}_{:, j} \\ &\;{\text{s.t.} } \;({{\boldsymbol{Z}}^{(p)}_{:, j}})^{{\rm{T}}} \bf{1}={\bf{1}}, {\boldsymbol{Z}}^{(p)}_{:, j} \geq 0 \end{split} \end{equation} $$ (9) 其中, $ {\boldsymbol{Z}}^{(p)}_{:, j} $表示$ {\boldsymbol{Z}}^{(p)} $的第$ j $列元素组成的向量, $f^{{\rm{T}}}= -({{\boldsymbol{X}}_{:, j}^{(p)}})^{{\rm{T}}}{\boldsymbol{A}}^{(p)} {\boldsymbol{W}}^{(p)}$. 同样地, 通过二次规划求解式(9).
在迭代中止后, 根据文献[30]中的方法将所有视图上的$ {\boldsymbol{Z}}^{(p)} $按列拼接得到全局的表示矩阵$ {\boldsymbol{Z}}^* \in \mathbf{R}^{mv \times n} $:
$$ \begin{equation} {\boldsymbol{Z}}^*=\left[{\boldsymbol{Z}}^{(1)};\;\cdots;{\boldsymbol{Z}}^{(p)};\;\cdots;{\boldsymbol{Z}}^{(v)}\right] \end{equation} $$ (10) 根据文献[27], $ {\boldsymbol{Z}}^* $的右奇异向量等价于由其恢复的完整相似度矩阵的特征向量. 因此首先进行SVD分解${\boldsymbol{Z}}^*={\boldsymbol{U}}\boldsymbol{\Sigma}{\boldsymbol{V}}$, 其中${\boldsymbol{U}} $、${\boldsymbol{V}} $分别是左、右奇异矩阵, ${\boldsymbol{\Sigma}} $是由奇异值构成的对角矩阵, 然后对右奇异矩阵$ {\boldsymbol{V}} $进行K-means得到最终的聚类结果. 具体的算法流程如下:
算法1. 基于加权锚点的多视图聚类算法
输入. 多视图数据$ \left\{{\boldsymbol{X}}^{(p)}\right\}_{p=1}^{v} $, 相关性矩阵$ \left\{{\boldsymbol{M}}^{(p)}\right\}_{p=1}^{v} $, 参数$ \beta $, 类别数$ k $.
输出. 聚类标签.
初始化. 对$ \left\{{\boldsymbol{X}}^{(p)}\right\}_{p=1}^{v} $使用K-means得到锚点矩阵$ \left\{{\boldsymbol{A}}^{(p)}\right\}_{p=1}^{v} $, ${\boldsymbol{Z}}^{(p)}=\frac{1}{m}\bf{1}_m\bf{1}_n^{\rm{T}}$.
1) Repeat
2) 通过求解式(5)更新$ \left\{{\boldsymbol{W}}^{(p)}\right\}_{p=1}^{v} $;
3) 通过求解式(7)更新$ \left\{{\boldsymbol{Z}}^{(p)}\right\}_{p=1}^{v} $;
4) Until converged
5)将$ \left\{{\boldsymbol{Z}}^{(p)}\right\}_{p=1}^{v} $拼接得到$ {\boldsymbol{Z}}^* $;
6)进行奇异值分解${\boldsymbol{Z}}^*={\boldsymbol{U}}\boldsymbol{\Sigma}{\boldsymbol{V}}$;
7)在$ {\boldsymbol{V}} $上使用K-means得到聚类标签.
2.4 收敛性及复杂度分析
在迭代优化过程中, 固定一个变量优化另一个变量时, 算法目标式的值是单调递减的. 同时, 目标函数的下界是0. 因此, 本文算法可以保证收敛到最小值.
通过使用锚图代替传统多视图子空间聚类中的完整自表达矩阵, 本文算法的计算复杂度可以达到线性复杂度. 具体来说, 在优化$ {\boldsymbol{W}}^{(p)} $时, 计算$ {\boldsymbol{G}}^{(p)} $与$ {\boldsymbol{H}}^{(p)} $时执行矩阵乘法的复杂度为$ {{\rm{O}}}(nm^{2}d^{(p)}) $, 解式(6)的复杂度为$ {{\rm{O}}}(m^{3}) $. 因此优化$ \left\{{\boldsymbol{W}}^{(p)}\right\}_{p=1}^{v} $的总体复杂度为${{\rm{O}}}(nm^{2}d+m^{3}v) ,$ 其中$d=\sum\nolimits_{p=1}^{v} d^{(p)}$. 在优化$ {\boldsymbol{Z}}^{(p)} $时, 执行矩阵乘法的复杂度为${{\rm{O}}}(nm^{2}d^{(p)}\,+ m^3)$, 更新$ {\boldsymbol{Z}}^{(p)} $的复杂度为${{\rm{O}}}(nm^{3})$, 则优化$ \left\{{\boldsymbol{Z}}^{(p)}\right\}_{p=1}^{v} $的复杂度为${{\rm{O}}}(nm^{2}d+nm^3v)$. 在迭代终止后, 对拼接的矩阵$ {\boldsymbol{Z}}^* $进行奇异值分解的复杂度为${{\rm{O}}}(nm^2v^2)$. 最终本文算法的计算复杂度为${{\rm{O}}}(nm^2d+nm^3v\,+ nm^2v^2)$. 由于$ m\ll n $, $ d \ll n $且$ v \ll n $, 因此MVC-WA是一个线性复杂度算法.
3. 实验
3.1 数据集介绍
本文在9个广泛使用的多视图数据集上进行了实验, 表2列出了这些数据集的基本信息.
表 2 实验中使用的数据集Table 2 Description of datasets数据集 样本数 视图数 类别数 ProteinFold 694 12 27 Mfeat 2 000 6 10 BDGP 2 500 3 5 Wiki 2 866 2 10 CCV 6 773 3 20 ALOI 10 800 4 100 YTF10 38 654 4 10 YTF20 63 896 4 20 YTF50 126 054 4 50 具体来说, ProteinFold
1 包含了27种不同结构的蛋白质. Mfeat1 是一个手写数据集, 它由 0 到 9 的数字组成. BDGP1 是5种不同的果蝇胚胎样本组成的, 共2 500幅图像. Wiki1 包含了2 866个维基百科的条目, 每个条目由图像和文本两种形式标识. CCV1 是一个包含20类不同对象、场景、体育事件和社会活动的视频数据集. ALOI1 是关于生活中的各种小物件的图像数据集. YTF10, YTF20和YTF50是从YoutubeFace1 数据集上生成的3个子集, YoutubeFace是一个面部视频数据集.3.2 实验设置
在本文实验中, 将本文方法与以下12种最先进的多视图聚类方法进行对比.
1) 基于信息完整性的多视图子空间聚类(Multi-view subspace clustering with intactness-aware similarity, MSC-IAS)[30]. MSC-IAS通过整合视图的互补信息学习一个完整的空间, 同时利用希尔伯特−施密特独立准则保证构造的相似度与潜在的完整点具有最大的相关性.
2) 分区多视图子空间聚类(Partition level multiview subspace clustering, PMSC)[31]. PMSC提出在一个统一的框架下进行各个视图的图学习、基本分区的生成与共识分区的融合, 三者相互促进.
3) 基于二部图的大规模多视图谱聚类(Multi-view spectral clustering, MVSC)[18]. MVSC使用二部图近似相似图, 有效减少了传统多视图谱聚类的计算复杂度.
4) 基于灵活多视图表示学习的子空间聚类(Flexible multi-view representation, FMR)[32]. FMR灵活地对来自不同视图的互补信息进行编码, 从而避免使用部分信息进行数据重建.
5) 基于可扩展且无参数二部图融合的多视图聚类(Scalable and parameter-free multi-view graph clustering, SFMC)[19]. SFMC使用一种根据评分采样锚点的新颖策略, 同时对构造的锚图施加秩约束, 无需后处理过程直接输出聚类结果.
6) 低秩且稀疏的多视图子空间聚类(Multi-view low-rank sparse subspace clustering, MLRSSC)[26]. MLRSSC同时对构造的亲和矩阵施加低秩与稀疏两种约束, 以这种方式学习所有视图间共享的子空间表示.
7) 基于无参数自动加权多图学习的多视图聚类(Auto-weighted multiple graph learning, AMGL)[33]. AMGL提出一种自适应加权策略, 自动地学习每个视图的最佳权重, 并得到全局的最优结果.
8) 大数据多视图K均值聚类(Robust multi-view K-means, RMKM)[34]. RMKM提出一种有效处理大规模数据的多视图聚类方法, 可以集成大规模多视图数据的异构表示.
9) 二元多视图聚类(Binary multi-view clustering, BMVC)[35]. BMVC同时学习多视图二进制表示与统一的聚类结果, 有效地降低了计算复杂度与存储成本.
10) 大规模多视图子空间聚类(Large-scale multi-view subspace clustering, LMVSC)[29]. LMVSC使用K-means得到初始化锚点, 而后进行锚图的学习, 有效解决了大规模聚类问题.
11) 基于统一锚点的可扩展多视图子空间聚类(Scalable multi-view subspace clustering, SMVSC)[16]. SMVSC通过学习策略而不是采样的方式来得到锚点, 解决了聚类性能受初始锚点限制的问题.
12) 基于一致锚点的快速无参多视图子空间聚类(Fast parameter-free multi-view subspace clustering, FPMVS)[27]. FPMVS将锚点学习与锚图构建统一在统一框架中, 两者相互协同提升聚类性能.
在本文方法中, 待调整的超参数有锚点数$ m $与平衡系数$ \beta $. 其中, 锚点数$ m $是从$ \left[k, 2k, 3k\right] $中选择, $ k $是每个数据集上的类别数; $ \beta $遍历$[2^{-2}, 2^1, 2^4, 2^7, 2^{10}, 2^{13}]$. 对于对比算法, 根据对应文献中的设置, 搜索它们的最佳参数进行公平的比较. 此外, 对于在最后需要进行K-means得到聚类结果的实验, 运行50次K-means然后报告结果的平均值与方差. 在实验中, 采用4个标准评估聚类性能, 包括准确性(Accuracy, ACC)、归一化互信息(Normalized mutual information, NMI)、纯度(Purity)、F值(F-score). 所有的实验均在一台配置为Intel core i9-10900X CPU, 64 GB RAM的台式机上完成.
3.3 实验结果与分析
表3展示了MVC-WA与其他对比算法在9个基准数据集上的聚类结果. 其中, 将最优结果标记为粗体加下划线, 次优结果加粗, “—”代表算法由于内存不足无法在该数据集上运行.
表 3 对比算法在所有数据集上的聚类性能 (%)Table 3 Clustering performance of compared methods on all datasets (%)数据集 MSC-IAS PMSC MVSC FMR SFMC MLRSSC AMGL RMKM BMVC LMVSC SMVSC FPMVS 本文算法 ACC ProteinFold 28.45±1.31 12.06±0.41 24.83±1.35 32.85±1.75 26.22±0 11.10±0 10.96±1.23 23.63±0 26.22±0 28.29±1.57 29.26±1.52 30.03±1.06 32.57±1.88 Mfeat 85.95±6.81 32.48±2.11 45.40±3.03 59.63±3.21 85.85±0 20.00±0 83.08±7.58 67.10±0 58.45±0 81.50±5.30 67.64±3.86 46.34±3.11 88.97±6.42 BDGP 52.10±4.59 26.44±0.19 35.36±2.45 24.93±0.28 20.08±0 36.12±0 32.33±1.82 41.44±0 29.48±0 50.16±0.29 37.22±2.03 32.62±0.71 60.04±1.89 Wiki 23.91±0.58 49.93±3.46 20.99±0.50 41.97±1.26 35.45±0 15.77±0 12.21±0.16 17.34±0 15.11±0 56.05±2.65 52.47±3.53 51.18±2.54 56.55±2.03 CCV — — — 11.93±0.26 12.52±0 10.44±0 13.71±0.31 11.94±0 15.50±0 20.28±0.60 22.98±0.58 22.88±0.74 22.60±0.67 ALOI — — — — — 1.01±0 60.26±1.69 33.74±0 59.67±0 40.27±1.55 48.34±1.49 21.72±0.65 71.29±1.80 YTF10 — — — — — — — 75.68±0 60.43±0 66.74±3.69 72.93±3.96 67.09±2.80 79.15±8.39 YTF20 — — — — — — — 57.62±0 60.09±0 60.64±4.18 67.13±4.20 63.08±2.39 68.16±4.82 YTF50 — — — — — — — — 66.00±0 68.32±2.45 67.13±3.68 64.24±2.97 66.97±3.08 NMI ProteinFold 36.91±0.89 6.71±0.58 34.45±1.58 40.69±1.13 31.02±0 0±0 20.02±2.19 34.83±0 29.53±0 37.43±1.14 39.94±1.40 37.75±0.99 43.34±1.19 Mfeat 87.68±2.85 40.14±2.76 42.49±3.30 49.19±1.37 91.77±0 28.63±0 87.29±3.84 65.33±0 68.88±0 79.35±1.95 62.18±1.77 56.46±1.81 86.74±2.26 BDGP 33.07±2.81 3.70±0.20 10.25±2.15 0.99±0.08 2.25±0 26.33±0 13.42±2.29 28.12±0 4.60±0 25.41±0.15 9.85±1.22 10.02±0.38 33.78±0.43 Wiki 8.65±0.27 52.01±1.51 7.28±0.67 33.09±1.09 34.18±0 0.08±0 0.82±0.10 4.34±0 2.46±0 51.57±2.17 50.05±3.79 49.34±2.95 49.47±1.77 CCV — — — 7.04±0.32 5.44±0 0±0 12.52±0.40 7.76±0 11.70±0 16.28±0.46 17.55±0.32 16.96±0.68 17.02±0.49 ALOI — — — — — 0.02±0 75.29±0.90 63.55±0 75.67±0 54.38±1.88 72.51±0.50 55.39±0.29 83.15±0.53 YTF10 — — — — — — — 80.22±0 58.91±0 73.75±2.25 78.57±4.61 76.11±5.78 83.15±4.01 YTF20 — — — — — — — 73.84±0 71.67±0 75.57±1.88 78.36±3.96 74.30±5.99 78.63±1.90 YTF50 — — — — — — — — 81.90±0 82.43±0.78 82.56±1.42 82.08±1.07 83.19±0.90 Purity ProteinFold 32.99±1.37 14.37±0.41 31.26±1.19 38.46±1.60 28.96±0 11.10±0 11.71±1.20 33.86±0 28.53±0 35.90±1.63 36.00±1.16 34.95±0.66 39.21±1.56 Mfeat 87.20±6.10 33.27±2.29 47.92±3.08 60.99±2.47 88.25±0 20.00±0 83.94±6.13 75.95±0 74.98±0 82.08±4.59 68.80±2.87 49.44±2.92 89.97±5.26 BDGP 53.52±3.70 28.59±0.23 35.67±3.06 25.17±0.21 21.12±0 36.12±0 33.46±2.10 51.00±0 29.48±0 50.17±0.23 37.80±1.17 34.82±1.33 60.13±1.24 Wiki 26.68±0.76 51.85±2.91 24.03±0.94 46.06±1.31 37.68±0 15.77±0 12.46±0.19 24.08±0 17.62±0 60.45±2.69 57.63±4.19 55.97±3.30 59.54±1.68 CCV — — — 15.92±0.31 13.04±0 10.44±0 14.12±0.33 17.04±0 19.18±0 23.62±0.47 25.91±0.51 25.09±0.78 25.34±0.67 ALOI — — — — — 1.01±0 63.92±1.26 64.02±0 62.35±0 42.32±1.55 51.46±1.41 23.67±0.72 73.81±1.42 YTF10 — — — — — — — 80.70±0 60.43±0 71.52±3.25 77.35±5.70 69.43±3.06 83.57±5.78 YTF20 — — — — — — — 68.78±0 64.83±0 68.20±3.02 72.40±3.79 64.92±1.95 74.40±3.32 YTF50 — — — — — — — — 73.64±0 73.21±2.18 70.09±3.61 66.84±3.02 73.65±2.50 F-score ProteinFold 14.07±0.62 9.44±0.01 14.28±0.85 18.57±1.38 11.68±0 9.64±0 7.84±0.79 12.92±0 16.41±0 15.58±1.17 16.76±0.96 17.09±0.94 19.61±1.62 Mfeat 83.66±6.35 26.94±1.09 37.46±2.69 41.49±1.51 85.52±0 27.39±0 81.39±7.35 59.22±0 62.59±0 74.42±4.13 56.50±2.45 46.57±1.33 85.05±5.09 BDGP 40.44±2.22 29.55±0.10 29.08±0.61 21.00±0.07 33.15±0 41.19±0 32.62±0.81 36.28±0 26.51±0 37.81±0.06 28.81±1.23 28.79±0.58 45.31±0.50 Wiki 15.44±0.25 41.83±2.91 14.91±0.54 30.34±0.78 21.38±0 19.46±0 12.48±0.69 13.04±0 11.15±0 48.71±2.18 45.76±4.69 44.91±3.43 47.17±1.64 CCV — — — 7.50±0.07 10.81±0 10.84±0 10.93±0.41 8.66±0 9.79±0 11.43±0.31 12.93±0.21 13.16±0.31 12.51±0.30 ALOI — — — — — 1.96±0 13.58±2.28 28.82±0 48.29±0 29.91±1.49 31.22±0.85 10.21±0.13 61.96±1.48 YTF10 — — — — — — — 73.27±0 53.15±0 62.24±3.70 68.34±5.88 66.10±5.06 75.78±8.28 YTF20 — — — — — — — 53.89±0 48.06±0 55.39±4.25 61.68±3.83 57.81±4.00 63.66±4.34 YTF50 — — — — — — — — 57.09±0 62.49±2.45 57.97±5.08 56.89±3.18 60.54±3.26 从表3中可以得出以下结论: 1) 所提出的算法在所有数据集上的聚类效果均能达到最优或次优, 就ACC而言, 本文算法结果在除ProteinFold和YTF50之外的7个数据集上分别超出次优结果3.51%, 15.24%, 11.44%, 8.65%, 18.30%, 4.59%, 12.40%. 2) MSC-IAS在传统子空间聚类算法中效果突出, 但是本文算法仍然在所有数据集上效果更佳, 这体现了基于锚点的子空间聚类算法的有效性. 3) LMVSC基于K-means得到锚点然后进行聚类, 在各个数据集上都取得了很好的效果, 但它没有考虑锚点间的差异与多样性. 而本文方法引入自适应加权机制, 锚点权重学习与锚图的构建相互促进, 在聚类性能上取得了大幅提升. 4) SMVSC与FPMVS通过学习策略来解决固定锚点影响聚类性能的问题, 而本文提出的MVC-WA通过对锚点加权的方式改进采样策略的不足. 在效果上与更新锚点的策略相比, MVC-WA具有次优甚至更好的结果.
图1中展示了本文算法在4个数据集下各个视图上学习到的锚点权重. 从图中来看, 在各个视图上锚点的权重有显著性差异. 重要性低或冗余的锚点的权重接近0, 而信息丰富的锚点权重则很大. 这体现了本文学习锚点权重的有效性.
3.4 运行时间比较
表4比较了各个算法在所有数据集上的运行时间. 从表中可以看到, 随着数据集样本数量的增加, 各个算法的运行时间都不断增加. 大部分算法由于存储复杂度高, 受到内存的限制, 无法在大规模数据集上运行. 与大多数的多视图聚类方法相比, MVC-WA具有可观的运行效率. 虽然BMVC与LMVSC的运行时间较短, 但它们的聚类性能不具优势. 因此, 尽管运行时间较长, 但是对于信息的充分利用使得MVC-WA具有更好的效果.
表 4 对比算法在所有数据集上的运行时间 (s)Table 4 Running time of compared methods on all datasets (s)数据集 MSC-IAS PMSC MVSC FMR SFMC MLRSSC AMGL RMKM BMVC LMVSC SMVSC FPMVS 本文算法 ProteinFold 2.44 1 512.10 408.89 16.43 6.86 2.12 1.66 1.21 12.64 2.55 2.82 3.97 6.91 Mfeat 16.81 3 300.30 11 528.00 251.03 88.62 27.94 19.62 3.95 0.43 2.96 1.38 1.43 9.20 BDGP 13.26 15 215.00 34 800.00 1 070.40 39.00 26.89 73.71 7.53 0.35 2.86 1.63 3.38 7.18 Wiki 15.92 14 386.00 9 991.70 1 068.80 9.84 30.72 180.62 6.27 0.11 3.57 3.15 20.16 4.89 CCV — — — 10 287.00 39.51 486.68 1 250.00 25.00 0.88 20.46 13.79 10.54 47.37 ALOI — — — — — 3 358.90 10 594.00 202.32 8.41 68.53 66.24 61.46 581.28 YTF10 — — — — — — — 675.42 108.22 196.70 253.21 998.23 495.83 YTF20 — — — — — — — 1 780.50 80.53 513.52 720.15 1 680.34 1 516.70 YTF50 — — — — — — — — 65.71 3 535.72 2 254.48 9 175.31 4 868.40 3.5 收敛性与敏感性分析
图2展示了MVC-WA在8个数据集上目标函数值随迭代次数的变化曲线. 从图中可以看到, 本文算法目标函数值随迭代次数增长而单调下降, 且在有限次数内都达到了稳定值, 这证明了本文算法的收敛性.
图 2 目标函数值随迭代次数增长的变化曲线Fig. 2 The variation curves the objective function value with the increase of the number of iterations为了分析两个超参数对MVC-WA聚类性能的影响, 在8个数据集上进行对比实验. 从图3中可以看到, 在大部分数据集上, 固定同一组锚点数时, 算法的ACC随$ \beta$的变化都不大. 而在固定同一组$ \beta $的情况下, 在部分数据集上ACC会受到锚点数变化的影响而有波动, 如在YTF10 上, 当锚点数为$ k $时, 聚类性能最优.
3.6 消融实验
为证明多视图聚类的性能优于单视图聚类的性能, 对各视图上的$ {\boldsymbol{Z}}^{(p)} $进行谱聚类并选取最优结果. 表5中的结果验证了多视图方法具有更优的聚类效果. 为证明锚点加权机制和多样性正则化的有效性, 去除权重矩阵作为未加权的对比项, 去掉正则化项作为无正则化的对比项. 表5中的结果证明了加权机制与多样性正则化项对聚类效果的提升.
表 5 消融实验结果 (%)Table 5 Results of ablation experiments (%)聚类指标 对比方法 数据集 ProteinFold Mfeat BDGP Wiki CCV ALOI YTF10 YTF20 ACC 最优单视图 31.48±1.22 77.62±5.85 49.98±2.95 52.01±3.70 20.03±0.32 55.79±1.40 72.08±5.27 63.52±3.80 未加权 27.83±1.66 82.55±6.64 46.32±3.19 52.05±2.38 18.10±0.53 70.14±2.04 70.72±8.29 66.36±4.72 无正则化项 30.57±1.57 86.54±7.40 47.37±2.16 47.49±2.35 21.75±0.74 66.26±1.82 68.95±8.83 62.18±4.49 本文方法 32.57±1.88 88.97±6.42 60.04±1.89 56.55±2.03 22.60±0.67 71.29±1.80 79.15±8.39 68.16±4.82 NMI 最优单视图 41.08±0.82 74.73±2.25 27.61±2.33 50.01±3.12 16.67±0.40 73.59±0.44 74.87±2.52 69.70±1.55 未加权 36.98±1.18 84.10±2.64 24.28±3.34 49.25±1.88 13.90±0.36 83.17±0.51 76.34±4.74 75.09±1.74 无正则化项 42.10±1.08 87.26±2.59 26.89±2.87 36.51±2.07 16.83±0.49 79.91±0.51 76.77±4.39 75.65±1.70 本文方法 43.34±1.19 86.74±2.26 33.78±0.43 49.47±1.77 17.02±0.49 83.15±0.53 83.15±4.01 78.63±1.90 Purity 最优单视图 36.97±0.97 79.67±4.38 51.69±2.83 57.39±3.90 23.59±0.32 58.86±1.22 76.85±3.66 68.07±2.33 未加权 35.17±1.46 84.32±5.43 47.12±3.11 58.34±2.52 21.10±0.40 72.77±1.71 76.89±6.26 71.52±3.27 无正则化项 38.73±1.27 88.55±5.55 47.45±2.04 50.37±1.98 24.76±0.63 69.02±1.47 76.11±6.23 70.25±3.64 本文方法 39.21±1.56 89.97±5.26 60.13±1.24 59.54±1.68 25.34±0.67 73.81±1.42 83.57±5.78 74.40±3.32 F-score 最优单视图 19.63±1.10 69.72±4.28 37.83±2.14 45.07±3.62 11.50±0.20 43.10±1.38 67.00±4.92 52.49±3.96 未加权 15.68±1.38 78.80±5.59 35.78±2.64 44.79±2.01 10.64±0.23 60.72±1.60 66.43±8.78 58.07±4.43 无正则化项 18.65±1.24 83.90±5.96 38.61±2.13 37.17±1.75 12.06±0.32 54.92±1.47 67.00±8.70 54.88±3.74 本文方法 19.61±1.62 85.05±5.09 45.31±0.50 47.17±1.64 12.51±0.30 61.96±1.48 75.78±8.28 63.66±4.34 4. 结束语
在本文中, 提出了一种基于加权锚点的多视图聚类方法(MVC-CA). 与以往基于锚点的方法不同, 提出对锚点进行自适应加权, 在统一的框架下进行锚点权重的学习与锚图的构建. 此外, 考虑到锚点的多样性, 根据锚点之间的关系对锚点权重进行动态调整. 在基准数据集上与现有多视图聚类方法的对比实验验证了MVC-CA的高效性与有效性.
-
图 2 目标函数值随迭代次数增长的变化曲线
Fig. 2 The variation curves the objective function value with the increase of the number of iterations
表 1 本文使用的主要符号
Table 1 Summary of notations
符号 定义 $n$ 数据点数量 $k$ 类别数 $v$ 视图数 $m$ 锚点数 $d^{(p)}$ 第$p$个视图上数据的维度 ${\boldsymbol{X}}^{(p)} \in \mathbf{R}^{d^{(p)} \times n}$ 第$p$个视图的数据矩阵 ${\boldsymbol{A}}^{(p)} \in \mathbf{R}^{d^{(p)} \times m}$ 第$p$个视图的锚点矩阵 ${\boldsymbol{Z}}^{(p)} \in \mathbf{R}^{m \times n}$ 第$p$个视图上的锚图 ${\boldsymbol{W}}^{(p)} \in \mathbf{R}^{m \times m}$ 第$p$个视图上的权重矩阵 ${\boldsymbol{M}}^{(p)} \in \mathbf{R}^{m \times m}$ 第$p$个视图上锚点的相关性矩阵 
下载: 导出CSV
表 2 实验中使用的数据集
Table 2 Description of datasets
数据集 样本数 视图数 类别数 ProteinFold 694 12 27 Mfeat 2 000 6 10 BDGP 2 500 3 5 Wiki 2 866 2 10 CCV 6 773 3 20 ALOI 10 800 4 100 YTF10 38 654 4 10 YTF20 63 896 4 20 YTF50 126 054 4 50
下载: 导出CSV
表 3 对比算法在所有数据集上的聚类性能 (%)
Table 3 Clustering performance of compared methods on all datasets (%)
数据集 MSC-IAS PMSC MVSC FMR SFMC MLRSSC AMGL RMKM BMVC LMVSC SMVSC FPMVS 本文算法 ACC ProteinFold 28.45±1.31 12.06±0.41 24.83±1.35 32.85±1.75 26.22±0 11.10±0 10.96±1.23 23.63±0 26.22±0 28.29±1.57 29.26±1.52 30.03±1.06 32.57±1.88 Mfeat 85.95±6.81 32.48±2.11 45.40±3.03 59.63±3.21 85.85±0 20.00±0 83.08±7.58 67.10±0 58.45±0 81.50±5.30 67.64±3.86 46.34±3.11 88.97±6.42 BDGP 52.10±4.59 26.44±0.19 35.36±2.45 24.93±0.28 20.08±0 36.12±0 32.33±1.82 41.44±0 29.48±0 50.16±0.29 37.22±2.03 32.62±0.71 60.04±1.89 Wiki 23.91±0.58 49.93±3.46 20.99±0.50 41.97±1.26 35.45±0 15.77±0 12.21±0.16 17.34±0 15.11±0 56.05±2.65 52.47±3.53 51.18±2.54 56.55±2.03 CCV — — — 11.93±0.26 12.52±0 10.44±0 13.71±0.31 11.94±0 15.50±0 20.28±0.60 22.98±0.58 22.88±0.74 22.60±0.67 ALOI — — — — — 1.01±0 60.26±1.69 33.74±0 59.67±0 40.27±1.55 48.34±1.49 21.72±0.65 71.29±1.80 YTF10 — — — — — — — 75.68±0 60.43±0 66.74±3.69 72.93±3.96 67.09±2.80 79.15±8.39 YTF20 — — — — — — — 57.62±0 60.09±0 60.64±4.18 67.13±4.20 63.08±2.39 68.16±4.82 YTF50 — — — — — — — — 66.00±0 68.32±2.45 67.13±3.68 64.24±2.97 66.97±3.08 NMI ProteinFold 36.91±0.89 6.71±0.58 34.45±1.58 40.69±1.13 31.02±0 0±0 20.02±2.19 34.83±0 29.53±0 37.43±1.14 39.94±1.40 37.75±0.99 43.34±1.19 Mfeat 87.68±2.85 40.14±2.76 42.49±3.30 49.19±1.37 91.77±0 28.63±0 87.29±3.84 65.33±0 68.88±0 79.35±1.95 62.18±1.77 56.46±1.81 86.74±2.26 BDGP 33.07±2.81 3.70±0.20 10.25±2.15 0.99±0.08 2.25±0 26.33±0 13.42±2.29 28.12±0 4.60±0 25.41±0.15 9.85±1.22 10.02±0.38 33.78±0.43 Wiki 8.65±0.27 52.01±1.51 7.28±0.67 33.09±1.09 34.18±0 0.08±0 0.82±0.10 4.34±0 2.46±0 51.57±2.17 50.05±3.79 49.34±2.95 49.47±1.77 CCV — — — 7.04±0.32 5.44±0 0±0 12.52±0.40 7.76±0 11.70±0 16.28±0.46 17.55±0.32 16.96±0.68 17.02±0.49 ALOI — — — — — 0.02±0 75.29±0.90 63.55±0 75.67±0 54.38±1.88 72.51±0.50 55.39±0.29 83.15±0.53 YTF10 — — — — — — — 80.22±0 58.91±0 73.75±2.25 78.57±4.61 76.11±5.78 83.15±4.01 YTF20 — — — — — — — 73.84±0 71.67±0 75.57±1.88 78.36±3.96 74.30±5.99 78.63±1.90 YTF50 — — — — — — — — 81.90±0 82.43±0.78 82.56±1.42 82.08±1.07 83.19±0.90 Purity ProteinFold 32.99±1.37 14.37±0.41 31.26±1.19 38.46±1.60 28.96±0 11.10±0 11.71±1.20 33.86±0 28.53±0 35.90±1.63 36.00±1.16 34.95±0.66 39.21±1.56 Mfeat 87.20±6.10 33.27±2.29 47.92±3.08 60.99±2.47 88.25±0 20.00±0 83.94±6.13 75.95±0 74.98±0 82.08±4.59 68.80±2.87 49.44±2.92 89.97±5.26 BDGP 53.52±3.70 28.59±0.23 35.67±3.06 25.17±0.21 21.12±0 36.12±0 33.46±2.10 51.00±0 29.48±0 50.17±0.23 37.80±1.17 34.82±1.33 60.13±1.24 Wiki 26.68±0.76 51.85±2.91 24.03±0.94 46.06±1.31 37.68±0 15.77±0 12.46±0.19 24.08±0 17.62±0 60.45±2.69 57.63±4.19 55.97±3.30 59.54±1.68 CCV — — — 15.92±0.31 13.04±0 10.44±0 14.12±0.33 17.04±0 19.18±0 23.62±0.47 25.91±0.51 25.09±0.78 25.34±0.67 ALOI — — — — — 1.01±0 63.92±1.26 64.02±0 62.35±0 42.32±1.55 51.46±1.41 23.67±0.72 73.81±1.42 YTF10 — — — — — — — 80.70±0 60.43±0 71.52±3.25 77.35±5.70 69.43±3.06 83.57±5.78 YTF20 — — — — — — — 68.78±0 64.83±0 68.20±3.02 72.40±3.79 64.92±1.95 74.40±3.32 YTF50 — — — — — — — — 73.64±0 73.21±2.18 70.09±3.61 66.84±3.02 73.65±2.50 F-score ProteinFold 14.07±0.62 9.44±0.01 14.28±0.85 18.57±1.38 11.68±0 9.64±0 7.84±0.79 12.92±0 16.41±0 15.58±1.17 16.76±0.96 17.09±0.94 19.61±1.62 Mfeat 83.66±6.35 26.94±1.09 37.46±2.69 41.49±1.51 85.52±0 27.39±0 81.39±7.35 59.22±0 62.59±0 74.42±4.13 56.50±2.45 46.57±1.33 85.05±5.09 BDGP 40.44±2.22 29.55±0.10 29.08±0.61 21.00±0.07 33.15±0 41.19±0 32.62±0.81 36.28±0 26.51±0 37.81±0.06 28.81±1.23 28.79±0.58 45.31±0.50 Wiki 15.44±0.25 41.83±2.91 14.91±0.54 30.34±0.78 21.38±0 19.46±0 12.48±0.69 13.04±0 11.15±0 48.71±2.18 45.76±4.69 44.91±3.43 47.17±1.64 CCV — — — 7.50±0.07 10.81±0 10.84±0 10.93±0.41 8.66±0 9.79±0 11.43±0.31 12.93±0.21 13.16±0.31 12.51±0.30 ALOI — — — — — 1.96±0 13.58±2.28 28.82±0 48.29±0 29.91±1.49 31.22±0.85 10.21±0.13 61.96±1.48 YTF10 — — — — — — — 73.27±0 53.15±0 62.24±3.70 68.34±5.88 66.10±5.06 75.78±8.28 YTF20 — — — — — — — 53.89±0 48.06±0 55.39±4.25 61.68±3.83 57.81±4.00 63.66±4.34 YTF50 — — — — — — — — 57.09±0 62.49±2.45 57.97±5.08 56.89±3.18 60.54±3.26
下载: 导出CSV
表 4 对比算法在所有数据集上的运行时间 (s)
Table 4 Running time of compared methods on all datasets (s)
数据集 MSC-IAS PMSC MVSC FMR SFMC MLRSSC AMGL RMKM BMVC LMVSC SMVSC FPMVS 本文算法 ProteinFold 2.44 1 512.10 408.89 16.43 6.86 2.12 1.66 1.21 12.64 2.55 2.82 3.97 6.91 Mfeat 16.81 3 300.30 11 528.00 251.03 88.62 27.94 19.62 3.95 0.43 2.96 1.38 1.43 9.20 BDGP 13.26 15 215.00 34 800.00 1 070.40 39.00 26.89 73.71 7.53 0.35 2.86 1.63 3.38 7.18 Wiki 15.92 14 386.00 9 991.70 1 068.80 9.84 30.72 180.62 6.27 0.11 3.57 3.15 20.16 4.89 CCV — — — 10 287.00 39.51 486.68 1 250.00 25.00 0.88 20.46 13.79 10.54 47.37 ALOI — — — — — 3 358.90 10 594.00 202.32 8.41 68.53 66.24 61.46 581.28 YTF10 — — — — — — — 675.42 108.22 196.70 253.21 998.23 495.83 YTF20 — — — — — — — 1 780.50 80.53 513.52 720.15 1 680.34 1 516.70 YTF50 — — — — — — — — 65.71 3 535.72 2 254.48 9 175.31 4 868.40
下载: 导出CSV
表 5 消融实验结果 (%)
Table 5 Results of ablation experiments (%)
聚类指标 对比方法 数据集 ProteinFold Mfeat BDGP Wiki CCV ALOI YTF10 YTF20 ACC 最优单视图 31.48±1.22 77.62±5.85 49.98±2.95 52.01±3.70 20.03±0.32 55.79±1.40 72.08±5.27 63.52±3.80 未加权 27.83±1.66 82.55±6.64 46.32±3.19 52.05±2.38 18.10±0.53 70.14±2.04 70.72±8.29 66.36±4.72 无正则化项 30.57±1.57 86.54±7.40 47.37±2.16 47.49±2.35 21.75±0.74 66.26±1.82 68.95±8.83 62.18±4.49 本文方法 32.57±1.88 88.97±6.42 60.04±1.89 56.55±2.03 22.60±0.67 71.29±1.80 79.15±8.39 68.16±4.82 NMI 最优单视图 41.08±0.82 74.73±2.25 27.61±2.33 50.01±3.12 16.67±0.40 73.59±0.44 74.87±2.52 69.70±1.55 未加权 36.98±1.18 84.10±2.64 24.28±3.34 49.25±1.88 13.90±0.36 83.17±0.51 76.34±4.74 75.09±1.74 无正则化项 42.10±1.08 87.26±2.59 26.89±2.87 36.51±2.07 16.83±0.49 79.91±0.51 76.77±4.39 75.65±1.70 本文方法 43.34±1.19 86.74±2.26 33.78±0.43 49.47±1.77 17.02±0.49 83.15±0.53 83.15±4.01 78.63±1.90 Purity 最优单视图 36.97±0.97 79.67±4.38 51.69±2.83 57.39±3.90 23.59±0.32 58.86±1.22 76.85±3.66 68.07±2.33 未加权 35.17±1.46 84.32±5.43 47.12±3.11 58.34±2.52 21.10±0.40 72.77±1.71 76.89±6.26 71.52±3.27 无正则化项 38.73±1.27 88.55±5.55 47.45±2.04 50.37±1.98 24.76±0.63 69.02±1.47 76.11±6.23 70.25±3.64 本文方法 39.21±1.56 89.97±5.26 60.13±1.24 59.54±1.68 25.34±0.67 73.81±1.42 83.57±5.78 74.40±3.32 F-score 最优单视图 19.63±1.10 69.72±4.28 37.83±2.14 45.07±3.62 11.50±0.20 43.10±1.38 67.00±4.92 52.49±3.96 未加权 15.68±1.38 78.80±5.59 35.78±2.64 44.79±2.01 10.64±0.23 60.72±1.60 66.43±8.78 58.07±4.43 无正则化项 18.65±1.24 83.90±5.96 38.61±2.13 37.17±1.75 12.06±0.32 54.92±1.47 67.00±8.70 54.88±3.74 本文方法 19.61±1.62 85.05±5.09 45.31±0.50 47.17±1.64 12.51±0.30 61.96±1.48 75.78±8.28 63.66±4.34
下载: 导出CSV
-
[1] Vidal R. Subspace clustering. IEEE Signal Processing Magazine, 2011, 28(2): 52−68 doi: 10.1109/MSP.2010.939739 [2] 王卫卫, 李小平, 冯象初, 王斯琪. 稀疏子空间聚类综述. 自动化学报, 2015, 41(8): 1373−1384 doi: 10.16383/j.aas.2015.c140891Wang Wei-Wei, Li Xiao-Ping, Feng Xiang-Chu, Wang Si-Qi. A survey on sparse subspace clustering. Acta Automatica Sinica, 2015, 41(8): 1373−1384 doi: 10.16383/j.aas.2015.c140891 [3] 张祎, 孔祥维, 王振帆, 付海燕, 李明. 基于多视图矩阵分解的聚类分析. 自动化学报, 2018, 44(12): 2160−2169 doi: 10.16383/j.aas.2018.c160636Zhang Yi, Kong Xiang-Wei, Wang Zhen-Fan, Fu Hai-Yan, Li Ming. Matrix factorization for multi-view clustering. Acta Automatica Sinica, 2018, 44(12): 2160−2169 doi: 10.16383/j.aas.2018.c160636 [4] Wang S W, Liu X W, Zhu E, Tang C, Liu J Y, Hu J T, et al. Multi-view clustering via late fusion alignment maximization. In: Proceedings of the 28th International Joint Conference on Artificial Intelligence. Macao, China: Morgan Kaufmann, 2019. 3778−3784 [5] Zhou S H, Nie D, Adeli E, Yin J P, Lian J, Shen D G. High-resolution encoder-decoder networks for low-contrast medical image segmentation. IEEE Transactions on Image Processing, 2020, 29(1): 461−475 [6] Yang Y, Wang H. Multi-view clustering: A survey. Big Data Mining and Analytics, 2018, 1(2): 83−107 doi: 10.26599/BDMA.2018.9020003 [7] Du S D, Liu Z H, Chen Z L, Yang W Y, Wang S P. Differentiable bi-sparse multi-view co-clustering. IEEE Transactions on Signal Processing, 2021, 69(1): 4623−4636 [8] Liu X W, Zhou S H, Liu L, Tang C, Wang S W, Liu J Y, et al. Localized simple multiple kernel k-means. In: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. New York, USA: IEEE, 2021. 9293−9301 [9] Zhan K, Zhang C Q, Guan J P, Wang J S. Graph learning for multiview clustering. IEEE Transactions on Cybernetics, 2017, 48(10): 2887−2895 [10] Nie F P, Cai G H, Li J, Li X L. Auto-weighted multi-view learning for image clustering and semi-supervised classification. IEEE Transactions on Image Processing, 2017, 27(3): 1501−1511 [11] Jia Y H, Liu H, Hou J H, Kwong S, Zhang Q F. Multi-view spectral clustering tailored tensor low-rank representation. IEEE Transactions on Circuits and Systems for Video Technology, 2021, 31(12): 4784−4797 doi: 10.1109/TCSVT.2021.3055039 [12] Luo S R, Zhang C Q, Zhang W, Cao X C. Consistent and specific multi-view subspace clustering. In: Proceedings of the 32nd AAAI Conference on Artificial Intelligence. New Orleans, Louisiana, USA: AAAI, 2018. 3730−3737 [13] Ma Z R, Kang Z, Luo G C, Tian L, Chen W Y. Towards clustering-friendly representations: Subspace clustering via graph filtering. In: Proceedings of the 28th ACM International Conference on Multimedia. Seattle, USA: ACM, 2020. 3081−3089 [14] 赵博宇, 张长青, 陈蕾, 刘新旺, 李泽超, 胡清华. 生成式不完整多视图数据聚类. 自动化学报, 2021, 47(8): 1867−1875 doi: 10.16383/j.aas.c200121Zhao Bo-Yu, Zhang Chang-Qing, Chen Lei, Liu Xin-Wang, Li Ze-Chao, Hu Qing-Hua. Generative model for partial multi-view clustering. Acta Automatica Sinica, 2021, 47(8): 1867−1875 doi: 10.16383/j.aas.c200121 [15] Pan E, Kang Z. Multi-view contrastive graph clustering. Advances in Neural Information Processing Systems, 2021, 34: 2148−2159 [16] Sun M J, Zhang P, Wang S W, Zhou S H, Tu W X, Liu X W, et al. Scalable multi-view subspace clustering with unified anchors. In: Proceedings of the 29th ACM International Conference on Multimedia. Chengdu, China: ACM, 2021. 3528−3536 [17] Wang S W, Liu X W, Liu L, Tu W X, Zhu X Z, Liu J Y, et al. Highly-efficient incomplete large-scale multi-view clustering with consensus bipartite graph. In: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. New Orleans, Louisiana, USA: IEEE, 2022. 9776−9785 [18] Li Y Q, Nie F P, Huang H, Huang J Z. Large-scale multi-view spectral clustering via bipartite graph. In: Proceedings of the 29th AAAI Conference on Artificial Intelligence. Austin, Texas, USA: AAAI, 2015. 2750−2756 [19] Li X L, Zhang H, Wang R, Nie F P. Multiview clustering: A scalable and parameter-free bipartite graph fusion method. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2020, 44(1): 330−344 [20] Peng Z H, Liu H, Jia Y H, Hou J H. Adaptive attribute and structure subspace clustering network. IEEE Transactions on Image Processing, 2022, 31: 3430−3439 doi: 10.1109/TIP.2022.3171421 [21] Lu C Y, Yan S C, Lin Z C. Convex sparse spectral clustering: Single-view to multi-view. IEEE Transactions on Image Processing, 2016, 25(6): 2833−2843 doi: 10.1109/TIP.2016.2553459 [22] Wang Y, Wu L, Lin X M, Gao J B. Multiview spectral clustering via structured low-rank matrix factorization. IEEE Transactions on Neural Networks and Learning Systems, 2018, 29(10): 4833−4843 doi: 10.1109/TNNLS.2017.2777489 [23] Gao H C, Nie F P, Li X L, Huang H. Multi-view subspace clustering. In: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. Boston, MA, USA: IEEE, 2015. 4238−4246 [24] Cao X C, Zhang C Q, Fu H Z, Liu S, Zhang H. Diversity-induced multi-view subspace clustering. In: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. Boston, MA, USA: IEEE, 2015. 586−594 [25] Zhang C Q, Fu H Z, Liu S, Liu G C, Cao X C. Low-rank tensor constrained multiview subspace clustering. In: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. Boston, MA, USA: IEEE, 2015. 1582−1590 [26] Brbic M, Kopriva I. Multi-view low-rank sparse subspace clustering. Pattern Recognition, 2018, 73(1): 247−258 [27] Wang S W, Liu X W, Zhu X Z, Zhang P, Zhang Y, Gao F, et al. Fast parameter-free multi-view subspace clustering with consensus anchor guidance. IEEE Transactions on Image Processing, 2021, 31(1): 556−568 [28] Liu S Y, Wang S W, Zhang P, Xu K, Liu X W, Zhang C W, et al. Efficient one-pass multi-view subspace clustering with consensus anchors. Proceedings of the AAAI Conference on Artificial Intelligence, 2022, 36(7): 7576−7584 [29] Kang Z, Zhou W T, Zhao Z T, Shao J M, Han M, Xu Z L. Large-scale multi-view subspace clustering in linear time. In: Proceedings of the 29th AAAI Conference on Artificial Intelligence. New York, USA: AAAI, 2020. 4412−4419 [30] Wang X B, Lei Z, Guo X J, Zhang C Q, Shi H L, Li S Z. Multi-view subspace clustering with intactness-aware similarity. Pattern Recognition, 2019, 88(1): 50−63 [31] Kang Z, Zhao X J, Peng C, Zhu H Y, Zhou J T, Peng X, et al. Partition level multiview subspace clustering. Neural Networks, 2020, 122(1): 279−288 [32] Li R H, Zhang C Q, Hu Q H, Zhu P F, Wang Z. Flexible multi-view representation learning for subspace clustering. In: Proceedings of the 28th International Joint Conference on Artificial Intelligence. Macao, China: Morgan Kaufmann, 2019. 2916−2922 [33] Nie F P, Li J, Li X L. Parameter-free auto-weighted multiple graph learning: A framework for multiview clustering and semi-supervised classification. In: Proceedings of the 25th International Joint Conference on Artificial Intelligence. New York, USA: Morgan Kaufmann, 2016. 1881−1887 [34] Cai X, Nie F P, Huang H. Multi-view k-means clustering on big data. In: Proceedings of the 23rd International Joint Conference on Artificial Intelligence. Beijing, China: Morgan Kaufmann, 2013. 2598−2604 [35] Zhang Z, Liu L, Shen F M, Shen H T, Shao L. Binary multi-view clustering. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2018, 41(7): 1774−1782 期刊类型引用(3)
1. 区卓越，邓秀勤，陈磊. 基于加权锚点的自适应多视图互补聚类算法. 计算机应用. 2025(01): 115-126 . 
百度学术2. 尤运宁，唐厂，刘新旺，邹鑫，刘袁缘，蒋良孝，张长青. 基于高阶图融合的多视图聚类算法. 中国科学:信息科学. 2024(09): 2098-2115 . 百度学术3. 王煜，齐宏拓，杨整涛，程柯帏，伍洲. 基于点云分层融合架构的混凝土气孔缺陷量化评估方法. 仪器仪表学报. 2024(07): 86-98 . 百度学术其他类型引用(4)
-
下载:
计量
- 文章访问数: 1711
- HTML全文浏览量: 566
- PDF下载量: 244
- 被引次数: 7
