聚类(clustering)是机器学习、模式识别和数据挖掘等领域的一项基础性任务, 其本质是根据样本之间的相似性将样本划分为不同的簇, 使簇内样本的相似度高, 簇间样本的相似度低. 在聚类过程中, 所有类别标签都是未知的, 聚类算法仅能生成簇结构, 因此, 聚类是一种无监督的数据分析方法.

在大数据时代, 随着信息技术的发展, 多视角数据在现实生活中越来越普遍, 来自视角的数据通常通过不同的源或不同特征提取方式得到. 例如: 一个人可以通过他的指纹、面部特征、虹膜等生物信息来识别; 一张图像可以通过其颜色或纹理等特征进行描述. 多视角数据的出现, 使得多视图学习也应运而生并得到了广泛的研究. 其中, 多视角聚类作为多视图学习中的一个主要应用方向, 越来越受到重视. 多视角聚类算法假设不同视图中同一数据样本属于相同的簇, 在一致性原则和互补性原则辅助下, 融合多个视角的信息, 从而提升聚类效果. 多视角聚类方法大致分为以下5类^[1]: (1) 协同训练方法^{[2, 3]}; (2) 多核学习^[4]; (3) 多视角图聚类^[5]; (4) 多视角子空间聚类^{[6, 7]}; (5) 多任务多视图聚类^[8]. 其中, 多视角子空间聚类是近年来较为流行的高维多视角数据聚类方法. 这类算法通过假设所有视图都是从潜在子空间生成的, 来获得多个视图的共享潜在子空间. 潜在子空间的维度低于所有视角的维度, 因此, 多视角子空间聚类有效地规避了维度灾难.

虽然现有的基于子空间框架的多视角聚类算法已经取得了一定进展, 但是这些方法通常还存在以下两个问题.

(1) 如何利用不同视角的差异性学习到一个优质的共享系数矩阵. 多视角聚类通常以单视角聚类为基础, 分别处理每个视角的特征, 再通过一致性原则和互补性原则将不同视图的特征融合起来. 在融合过程中, 一些方法^{[9, 10]}只是简单地将各个视角的数据表示直接相加, 忽略了不同视角的重要性;

(2) 如何增强共享系数矩阵的低秩性. 基于低秩表示的子空间聚类^[11]是在给定的字典中寻找所有数据点最低秩的表示, 核范数作为秩极小化问题的凸松弛对秩进行约束. 然而, 标准的核范数最小化将每个奇异值平均化, 不能很好地逼近最低秩.

针对上述两个问题, 本文提出了一种基于自适应视角加权和核范数加权的多视角子空间聚类算法(dual weighted multi-view subspace clustering, DWMSC). 如图 1所示, 该方法首先将多视角数据通过子空间模型得到各个视角的自表达系数矩阵. 考虑到不同视角之间的差异性, 本文采用自适应加权策略动态地更新每个视角的权重α, 从而构造出一个共享的潜在子空间表达, 即共享系数矩阵. 再通过对共享的系数矩阵采用加权核范数(WNN)进一步逼近矩阵的秩, 使得共享系数矩阵更加低秩. 最后对求得的共享系数矩阵进行谱聚类, 得到最终的聚类结果.

本文的主要贡献有以下3点: (1) 提出了一种新的构造公共系数矩阵的方法, 在构造过程中对每个视角的系数矩阵进行加权, 将每个视角和共享的系数矩阵联合学习, 有效降低了噪声的影响; (2) 考虑了较大的奇异值通常对应于数据矩阵中更重要的子空间成分, 利用矩阵奇异值的先验知识更好地逼近矩阵的秩, 得到了更优的公共系数矩阵; (3) 我们将自加权策略和核范数加权策略整合到一个统一的基于低秩表示的子空间框架中, 采用增广拉格朗日交替方向乘子法^[12]优化目标函数, 在6个基准数据集上进行了实验, 验证了本文提出的双加权多视角子空间聚类算法的有效性和优越性.

本文第1节对子空间聚类的框架进行总结, 并对一些相关工作进行回顾. 第2节对双加权多视角子空间聚类模型(DWMSC)进行详细的介绍, 同时讨论目标函数的优化算法和算法复杂度问题. 第3节对本文提出的方法进行广泛的实验, 验证算法的有效性和收敛性. 第4节总结本文并对下一步工作进行展望.

符号描述: 本文中, 斜体字母表示标量(例如m或M), 斜体加粗小写字母表示向量(例如m), 斜体加粗大写字母表示矩阵M, 对于矩阵M∈${\mathbb{R}^{d \times n}}$, M的第i行和第j列所对应的元素表示为M_{i, j}. Tr(M)和||M||分别表示矩阵M的迹和矩阵M的不同范数. ||M||_*是矩阵M的核范数, ||M||_F是矩阵M的F范数. ||M||_{w, ^*}是矩阵M的加权核范数.

1 相关工作 1.1 子空间聚类算法

基于谱聚类的子空间聚类方法是通过给定一组数据样本, 每个样本都可以表示为字典中基的线性组合, 这样的线性组合称为系数矩阵; 然后, 根据系数矩阵来构建相似度矩阵; 最后, 通过谱聚类对相似度矩阵处理得到聚类结果. 通常, 基于自表达的子空间聚类是将数据本身作为字典, 这样避免了初始化字典的困难. 该模型可以表示为

$\mathop {\min }\limits_\mathit{\boldsymbol{Z}} \mathit{\Psi } (\mathit{\boldsymbol{X}}, \mathit{\boldsymbol{XZ}}) + \lambda \mathit{\Omega} (\mathit{\boldsymbol{Z}})$

(1)

其中, X∈${{\mathbb{R}}^{d\times n}}$是数据矩阵, 也作为自表达中的字典矩阵; Z∈${{\mathbb{R}}^{n\times n}}$是系数矩阵, 是基于数据矩阵的线性表示; λ是用于平衡重构误差和正则项的惩罚因子; Ψ(·, ·)和Ω(·)分别表示损失函数和正则化项.

稀疏子空间聚类(SSC)^[13]方法采用l₁范数约束系数矩阵, 寻找来自同一子空间数据点相对应的稀疏表示. 而低秩子空间聚类(LRR)^[11]算法通过求解核范数正则优化问题, 找出所有数据的最低秩表示. 基于l₂范数的加权低秩子空间聚类(GLMC)^[14]算法通过欧氏距离的加权策略求得系数矩阵, 然后通过系数矩阵构造相似度矩阵, 最后对相似度矩阵S进行谱聚类操作得到最终的聚类结果. 这些算法在聚类问题中均取得很好的效果, 但它们只能处理单视角数据, 如果数据受损或观测不足, 会严重影响聚类结果. 而多视角数据包含更丰富的信息, 因此, 多视角子空间聚类算法通过利用丰富的多视角信息能够进一步提升聚类性能. 基于子空间的多视角聚类算法假设公共表示是由多个视角共享的一个潜在的低维子空间生成的. Gao等人提出的MVSC算法^[6]同时对每个视图的子空间表示进行聚类, 保证了不同视图之间的聚类结构一致. 而Zheng等人提出的基于特征拼接的多视角子空间聚类算法(FCMSC)^[15]首先将多视角数据拼接为一个联合的表示, 然后通过处理多视角的拼接误差和聚类误差提高聚类性能. Zhang等人提出的LMSC聚类算法^[7]在潜在表示下同时学习对应于不同视图的投影. 虽然这些研究在一定程度上取得了良好的聚类效果, 但对于每个视角都是同等对待, 忽略了不同视角的重要性.

1.2 WNNM算法

基于低秩表示的子空间聚类算法是在所有字典中基的线性组合中寻找最低秩表示, 采用核范数最小化(NNM)约束系数矩阵的秩. 但是标准的核范数将每个奇异值平均化, 不能很好地逼近系数矩阵的秩. Zhai等人^[16]提出(PSMSC)通过奇异值部分和最小化实现多视角聚类, 由于PSMSC算法对某些特定的奇异值正则化, 因此其灵活性不够. 加权核范数最小化(WNNM)^[17]有效地解决了这些问题, 将奇异值赋予不同权重, 提高了核范数的灵活性. 矩阵X的加权核范数表示如下:

$||\mathit{\boldsymbol{X}}|{|_{\mathit{\boldsymbol{w}}, ^*}} = \sum\nolimits_i {|{\mathit{\boldsymbol{w}}_i}{\mathit{\boldsymbol{\sigma}} _i}(\mathit{\boldsymbol{X}}){|_1}}$

(2)

其中, σ_i(X)表示X的第i个奇异值, w=[w₁, w₂, …, w_n], w_i≥0是σ_i(X)的非负权重. 核范数可以看作是加权核范数的特殊化, 其权重都相同且等于1.

2 DWMSC算法

本节详细介绍了双加权多视角子空间聚类(DWMSC)算法, 同时给出了对目标函数的优化过程, 最后分析了算法复杂度.

2.1 DWMSC聚类模型

对于具有v个视角的多视角数据集, 设X⁽¹⁾, …, X^(v)是v个视角的数据矩阵, 则${\mathit{\boldsymbol{X}}}^{(k)}\in {\mathbb{R}}^{{d}_{k}\times n}$表示第k个视角的数据, d_k是第k个视角的维度, n是样本点个数. 该算法的目的是通过平衡不同视角的重要性找到统一的共享系数矩阵, 并通过核范数加权进一步逼近共享系数矩阵的低秩特性, 从而提高最后的聚类效果. 为了找到共享系数矩阵, 首先求得各个视角的自表达系数矩阵, 然后将它们融合起来. 具体公式如下:

$\left. \begin{array}{l} \mathop {\min }\limits_{{\mathit{\boldsymbol{Z}}^*}, {\mathit{\boldsymbol{Z}}^{(k)}}} \lambda \sum\limits_{k = 1}^v {||{\mathit{\boldsymbol{X}}^{(k)}} - {\mathit{\boldsymbol{X}}^{(k)}}{\mathit{\boldsymbol{Z}}^{(k)}}||_F^2} + \sum\limits_{k = 1}^v {||{\mathit{\boldsymbol{Z}}^*} - {\mathit{\boldsymbol{Z}}^{(k)}}||_F^2} \\ {\text{s}}{\text{.t}}{\text{. }}{\mathit{\boldsymbol{Z}}^*}, {\mathit{\boldsymbol{Z}}^{(k)}} \geqslant 0 \end{array} \right\}$

(3)

其中, Z^(k)是第k个视角的子空间表示矩阵, Z^*是共享系数矩阵, λ是权衡参数.

然而, 在上述公式中, 不同视角对于求得的共享系数矩阵的贡献相同. 通常情况下, 一些包含局外点或有噪声点的视图可能会严重损坏数据, 导致聚类性能下降. 考虑到不同视角的重要性, 该模型提出了一种新的融合系数矩阵的策略:

$\left. \begin{array}{l} \mathop {\min }\limits_{{\mathit{\boldsymbol{Z}}^*}, {\mathit{\boldsymbol{Z}}^{(k)}}, {\mathit{\boldsymbol{\alpha}} ^{(k)}}} \lambda \sum\limits_{k = 1}^v {||{\mathit{\boldsymbol{X}}^{(k)}} - {\mathit{\boldsymbol{X}}^{(k)}}{\mathit{\boldsymbol{Z}}^{(k)}}||_F^2} + \sum\limits_{k = 1}^v {{\mathit{\boldsymbol{\alpha}} ^{(k)}}||{\mathit{\boldsymbol{Z}}^*} - {\mathit{\boldsymbol{Z}}^{(k)}}||_F^2} \\ {\text{s}}{\text{.t}}{\text{. }}{\mathit{\boldsymbol{Z}}^*}, {\mathit{\boldsymbol{Z}}^{(k)}} \geqslant 0 \end{array} \right\}$

(4)

其中, α^(k)是权重, 表示第k视角的重要性. 当权重α^(k)固定时, 对于等式(4)的求解等同于:

$\left. \begin{array}{l} \mathop {\min }\limits_{{\mathit{\boldsymbol{Z}}^*}, {\mathit{\boldsymbol{Z}}^{(k)}}, {\mathit{\boldsymbol{\alpha}} ^{(k)}}} \lambda \sum\limits_{k = 1}^v {||{\mathit{\boldsymbol{X}}^{(k)}} - {\mathit{\boldsymbol{X}}^{(k)}}{\mathit{\boldsymbol{Z}}^{(k)}}||_F^2} + \sum\limits_{k = 1}^v {||{\mathit{\boldsymbol{Z}}^*} - {\mathit{\boldsymbol{Z}}^{(k)}}|{|_F}} \\ {\text{s}}{\text{.t}}{\text{. }}{\mathit{\boldsymbol{Z}}^*}, {\mathit{\boldsymbol{Z}}^{(k)}} \geqslant 0 \end{array} \right\}$

(5)

证明1: 公式(5)的拉格朗日函数如下所示, 我们在文中交替更新每一个子问题, 因为每一个问题都会被建模成为一个方程:

$\mathop {\min }\limits_{{\mathit{\boldsymbol{Z}}^*}, {\mathit{\boldsymbol{Z}}^{(k)}}, {\mathit{\boldsymbol{\alpha}} ^{(k)}}} \lambda \sum\limits_{k = 1}^v {||{\mathit{\boldsymbol{X}}^{(k)}} - {\mathit{\boldsymbol{X}}^{(k)}}{\mathit{\boldsymbol{Z}}^{(k)}}||_F^2} + \sum\limits_{k = 1}^v {||{\mathit{\boldsymbol{Z}}^*} - {\mathit{\boldsymbol{Z}}^{(k)}}|{|_F}} + \mathit{\Psi } (\mathit{\Lambda } , {\mathit{\boldsymbol{Z}}^*})$

(6)

其中, Λ是拉格朗日乘子, Ψ(Λ, Z^*)是正式的约束术语. 取等式(6)对于Z^*的导数, 并将其值设置为0, 则有:

$\sum\limits_{k = 1}^v {\frac{1}{{2\sqrt {||{\mathit{\boldsymbol{Z}}^*} - {\mathit{\boldsymbol{Z}}^{(k)}}||_F^2} }}} \cdot \frac{{\partial ||{\mathit{\boldsymbol{Z}}^*} - {\mathit{\boldsymbol{Z}}^{(k)}}||_F^2}}{{\partial {\mathit{\boldsymbol{Z}}^*}}} + \frac{{\partial \mathit{\Psi } (\mathit{\Lambda } , {\mathit{\boldsymbol{Z}}^*}) }}{{\partial {\mathit{\boldsymbol{Z}}^*}}} = 0$

(7)

当权重α^(k)固定时, 可以令:

${\mathit{\boldsymbol{\alpha}} ^{(k)}} = \frac{1}{{2||{\mathit{\boldsymbol{Z}}^*} - {\mathit{\boldsymbol{Z}}^{(k)}}|{|_F}}}$

(8)

公式(7)可以转换为如下公式:

$\sum\limits_{k = 1}^v {{\mathit{\boldsymbol{\alpha}} ^{(k)}}} \cdot \frac{{\partial ||{\mathit{\boldsymbol{Z}}^*} - {\mathit{\boldsymbol{Z}}^{(k)}}||_F^2}}{{\partial {\mathit{\boldsymbol{Z}}^*}}} + \frac{{\partial \mathit{\Psi } (\mathit{\Lambda } , {\mathit{\boldsymbol{Z}}^*}) }}{{\partial {\mathit{\boldsymbol{Z}}^*}}} = 0$

(9)

如果当α^(k)固定时, 公式(4)的拉格朗日函数的导数等于公式(9). 因此, 公式(4)与公式(5)相等. 权重也通过公式(8)进行更新.

显然, α^(k)的更新依赖于Z^(k)和Z^*, 可以近似地基于迭代方法计算Z^(k)、Z^*、α^(k). 通过解决上述问题, 我们可以自适应地获得每个视角的系数矩阵和共享矩阵. 权重α可以在学习共享矩阵的过程中对视角进行动态加权, 从而有效降低了受损系数矩阵的不利影响. 尽管可以直接通过等式(4)计算出的Z^*构造相似度矩阵S以实现聚类结果, 但是由于当前获得的相似度矩阵对后续聚类任务可能不是最佳选择, 因此需要继续考虑对Z^*结构的约束.

通常使用l₁范数约束Z^*稀疏性或者核范数约束其低秩性, 其中, 核范数||Z^*||_*表示Z^*奇异值的总和, 即为$||{\mathit{\boldsymbol{Z}}^*}|{|_*} = \sum\nolimits_i {|{\sigma _i}({\mathit{\boldsymbol{Z}}^*}){|_1}} .$矩阵的奇异值总是按降序排列的, 较大的奇异值通常对应于数据矩阵中更重要的成分, 因此将较大的奇异值赋予较大的权重, 以保留共享系数矩阵重要成分的子空间结构; 将较小的奇异值赋予较小的权重, 更好地保证了共享系数矩阵的低秩性. 所以本文采用权重降序排列. 结合公式(4)与加权核范数正则项, 得到最终的目标函数为

$\left. \begin{array}{l} \mathop {\min }\limits_{{\mathit{\boldsymbol{Z}}^*}, {\mathit{\boldsymbol{Z}}^{(k)}}, {\mathit{\boldsymbol{\alpha}} ^{(k)}}} \lambda \sum\limits_{k = 1}^v {||{\mathit{\boldsymbol{X}}^{(k)}} - {\mathit{\boldsymbol{X}}^{(k)}}{\mathit{\boldsymbol{Z}}^{(k)}}||_F^2} + \sum\limits_{k = 1}^v {{\mathit{\boldsymbol{\alpha}} ^{(k)}}||{\mathit{\boldsymbol{Z}}^*} - {\mathit{\boldsymbol{Z}}^{(k)}}||_F^2} + \beta ||{\mathit{\boldsymbol{Z}}^*}|{|_{\mathit{\boldsymbol{w}}, ^*}} \\ {\text{s}}{\text{.t}}{\text{. }}{\mathit{\boldsymbol{Z}}^*}, {\mathit{\boldsymbol{Z}}^{(k)}} \geqslant 0 \end{array} \right\}$

(10)

其中, β和λ同为权衡参数.

2.2 目标函数优化

本文使用基于增广拉格朗日交替方向乘子法最小化(ALM-ADM)方法^[12]解决此问题, 并使用交替迭代优化其目标函数. 为了有效地优化目标函数, 在加权核范数中引入辅助变量Q, 从而将目标函数(8)写为

$\left. \begin{array}{l} \mathop {\min }\limits_{{\mathit{\boldsymbol{Z}}^*}, {\mathit{\boldsymbol{Z}}^{(k)}}, {\mathit{\boldsymbol{\alpha}} ^{(k)}}} \lambda \sum\limits_{k = 1}^v {||{\mathit{\boldsymbol{X}}^{(k)}} - {\mathit{\boldsymbol{X}}^{(k)}}{\mathit{\boldsymbol{Z}}^{(k)}}||_F^2} + \sum\limits_{k = 1}^v {{\mathit{\boldsymbol{\alpha}} ^{(k)}}||{\mathit{\boldsymbol{Z}}^*} - {\mathit{\boldsymbol{Z}}^{(k)}}||_F^2} + \beta ||\mathit{\boldsymbol{Q}}|{|_{\mathit{\boldsymbol{w}}, ^*}} \\ {\text{s}}{\text{.t}}{\text{. }}{\mathit{\boldsymbol{Z}}^*}, {\mathit{\boldsymbol{Z}}^{(k)}} \geqslant 0 , {\mathit{\boldsymbol{Z}}^*} = \mathit{\boldsymbol{Q}} \end{array} \right\}$

(11)

方程(9)的增广拉格朗日函数形式为

$\left. \begin{array}{l} \mathit{\Gamma } ({\mathit{\boldsymbol{Z}}^*}, {\mathit{\boldsymbol{Z}}^{(k)}}, \mathit{\boldsymbol{Q}}) = \lambda \sum\limits_{k = 1}^v {||{\mathit{\boldsymbol{X}}^{(k)}} - {\mathit{\boldsymbol{X}}^{(k)}}{\mathit{\boldsymbol{Z}}^{(k)}}||_F^2} + \sum\limits_{k = 1}^v {{\mathit{\boldsymbol{\alpha}} ^{(k)}}||{\mathit{\boldsymbol{Z}}^*} - {\mathit{\boldsymbol{Z}}^{(k)}}||_F^2} + \beta ||\mathit{\boldsymbol{Q}}|{|_{\mathit{\boldsymbol{w}}, ^*}} + \mathit{\Phi } (Y, {\mathit{\boldsymbol{Z}}^*} - \mathit{\boldsymbol{Q}}) \\ {\text{s}}{\text{.t}}{\text{. }}{\mathit{\boldsymbol{Z}}^*}, {\mathit{\boldsymbol{Z}}^{(k)}} \geqslant 0, {\mathit{\boldsymbol{Z}}^*} = \mathit{\boldsymbol{Q}} \end{array} \right\}$

(12)

其中, Y是拉格朗日乘子. Φ(Y, Z^*−Q)定义为下式:

$\mathit{\Phi } (\mathit{\boldsymbol{Y}}, {\mathit{\boldsymbol{Z}}^*} - \mathit{\boldsymbol{Q}}) = \langle \mathit{\boldsymbol{Y}}, {\mathit{\boldsymbol{Z}}^*} - \mathit{\boldsymbol{Q}}\rangle + \mu /2||{\mathit{\boldsymbol{Z}}^*} - \mathit{\boldsymbol{Q}}||_F^2$

(13)

其中, μ是正则惩罚参数, $\left\langle { \cdot , \cdot } \right\rangle$是矩阵内积. 为了优化增广拉格朗日函数(12), 可将问题分为以下子问题.

(1) 固定Z^*、Z^(k)、α^(k), 更新Q: 保留方程(12)中有关Q的公式:

$\mathop {\min }\limits_\mathit{\boldsymbol{Q}} \beta ||\mathit{\boldsymbol{Q}}|{|_{\mathit{\boldsymbol{w}}, ^*}} + \langle \mathit{\boldsymbol{Y}}, {\mathit{\boldsymbol{Z}}^*} - \mathit{\boldsymbol{Q}}\rangle + \mu /2||{\mathit{\boldsymbol{Z}}^*} - \mathit{\boldsymbol{Q}}||_F^2$

(14)

上式可以化简为

$\mathop {\min }\limits_\mathit{\boldsymbol{Q}} \beta ||\mathit{\boldsymbol{Q}}|{|_{\mathit{\boldsymbol{w}}, ^*}} + \frac{\mu }{2}\left\| {{\mathit{\boldsymbol{Z}}^*} - \mathit{\boldsymbol{Q}} + \frac{\mathit{\boldsymbol{Y}}}{\mu }} \right\|_F^2$

(15)

在公式(13)中, 对于加权核范数正则项的求解, 本文采用权重降序排列^[18], 权重可以表示为

$\mathit{\boldsymbol{w}} = \mathit{\boldsymbol{\sigma}} _i^\gamma (\mathit{\boldsymbol{X}})$

(16)

其中, γ是确定权重分布的参数. 从等式(14), 我们可以看出, 权重与矩阵的奇异值成正比. 因此, 等式(14)的优化问题仍是凸优化问题, 并有如下闭式解:

$\mathit{\boldsymbol{Q}} = \mathit{\boldsymbol{U}}{\mathit{\boldsymbol{S}}_{\mathit{\boldsymbol{w}}/\mu }}(\mathit{\Sigma }){\mathit{\boldsymbol{V}}^T}$

(17)

其中, UΣV=Z^*+Y/μ, S_ε(x)=max(x−ε, 0)是广义软阈值算子.

(2) 固定Z^*、Q、Z^(k), 更新α^(k): 当其他变量固定时, 用于更新α^(k)的优化问题等同于优化问题(5), 因此, α^(k)通过第2.1节的公式(7)更新.

(3) 固定Z^*、Q、α^(k), 更新Z^(k): 更新Z^(k)问题(12)可以转化为

$\left. \begin{array}{l} \mathop {\min }\limits_{{\mathit{\boldsymbol{Z}}^{(k)}}} \lambda \sum\limits_{k = 1}^v {||{\mathit{\boldsymbol{X}}^{(k)}} - {\mathit{\boldsymbol{X}}^{(k)}}{\mathit{\boldsymbol{Z}}^{(k)}}||_F^2} + \sum\limits_{k = 1}^v {{\mathit{\boldsymbol{\alpha}} ^{(k)}}||{\mathit{\boldsymbol{Z}}^*} - {\mathit{\boldsymbol{Z}}^{(k)}}||_F^2} \\ {\text{s}}{\text{.t}}{\text{. }}{\mathit{\boldsymbol{Z}}^{(k)}} \geqslant 0 \end{array} \right\}$

(18)

通过对Z^(k)求导, 并将其导数设为0, 我们得到:

${\mathit{\boldsymbol{Z}}^{(k)}} = {(\lambda {\mathit{\boldsymbol{X}}^{{{(k)}^T}}}{\mathit{\boldsymbol{X}}^{(k)}} + {\mathit{\boldsymbol{\alpha}} ^{(k)}}I)^{ - 1}}(\lambda {\mathit{\boldsymbol{X}}^{{{(k)}^T}}}{\mathit{\boldsymbol{X}}^{(k)}} + {\mathit{\boldsymbol{\alpha}} ^{(k)}}{\mathit{\boldsymbol{Z}}^*})$

(19)

(4) 固定Z^(k)、Q、α^(k), 更新Z^*: 通过固定其他变量, 关于Z^*的优化问题如下:

$\left. \begin{array}{l} \mathop {\min }\limits_{{\mathit{\boldsymbol{Z}}^*}, {\mathit{\boldsymbol{Z}}^{(k)}}, {\mathit{\boldsymbol{\alpha}} ^{(k)}}} \sum\limits_{k = 1}^v {{\mathit{\boldsymbol{\alpha}} ^{(k)}}||{\mathit{\boldsymbol{Z}}^*} - {\mathit{\boldsymbol{Z}}^{(k)}}||_F^2} + \langle \mathit{\boldsymbol{Y}}, {\mathit{\boldsymbol{Z}}^*} - \mathit{\boldsymbol{Q}}\rangle + \mu /2||{\mathit{\boldsymbol{Z}}^*} - \mathit{\boldsymbol{Q}}||_F^2 \\ {\text{s}}{\text{.t}}{\text{. }}{\mathit{\boldsymbol{Z}}^*} \geqslant 0 \end{array} \right\}$

(20)

与Z^(k)相同, 求导得到:

${\mathit{\boldsymbol{Z}}^*} = {{\left( {2\lambda \sum\limits_{k = 1}^v {{\mathit{\boldsymbol{\alpha}} ^{(k)}}{\mathit{\boldsymbol{Z}}^{(k)}}} - \mathit{\boldsymbol{Y}} + \mu \mathit{\boldsymbol{Q}}} \right)} / {\left( {2\sum\limits_{k = 1}^v {{\mathit{\boldsymbol{\alpha}} ^{(k)}}} + \mu } \right)}}$

(21)

(5) 更新乘子Y和μ: 根据文献[12]更新拉格朗日乘子和μ:

$\left\{ {\begin{array}{*{20}{l}} {\mathit{\boldsymbol{Y}} = \mathit{\boldsymbol{Y}} + \mu ({\mathit{\boldsymbol{Z}}^*} - \mathit{\boldsymbol{Q}})} \\ {\mu = \min (\rho \mu , {\mu _{\max }})} \end{array}} \right.$

(22)

其中, μ_max是一个阈值, ρ表示非负标量.

DWMSC算法优化步骤如算法1所示.

算法1. 双加权多视角子空间聚类算法.

输入: 多视角数据${\left\{{\mathit{\boldsymbol{X}}}^{(k)}\right\}}_{k=1}^{v}\in {\mathbb{R}}^{{d}_{k}\times n},$平衡参数λ、β、γ;

初始化: Z^*随机初始化, Q=0, Z^(k)=0, α^(k)=1/v, Y=0, ρ=1.9, μ=10⁻⁴, μ_max=10⁶, ε=10⁻⁶;

重复:

1: 根据公式(15)更新辅助变量Q;

2: 利用公式(8)更新每个视角的权重α^(k);

3: 利用公式(19)计算每一个视角的系数矩阵Z^(k);

4: 根据公式(21)计算共享系数矩阵Z^*;

5: 根据公式(22)更新拉格朗日乘子和μ;

直到:

$\min (||{\mathit{\boldsymbol{Z}}^*} - \mathit{\boldsymbol{Q}}|{|_\infty }, ||{\mathit{\boldsymbol{Z}}^*} - \mathit{\boldsymbol{Z}}_{old}^*|{|_\infty }, ||{\mathit{\boldsymbol{Z}}^{(k)}} - \mathit{\boldsymbol{Z}}_{old}^{(k)}|{|_\infty }) < \varepsilon .$

输出: Z^*.

将学习到的共享系数矩阵Z^*通过S=|Z|+|Z^T|构建相似度矩阵, 最后通过谱聚类得到最终的聚类结果.

2.3 算法复杂度分析

该方法主要由4个子问题组成, 具体来说: 更新Q的时间复杂度为O(n³); 对于更新权重α^(k), 复杂度为O(vn²); 更新Z^(k)主要的复杂度是矩阵求逆, 因此其复杂度为O(n³); Z^*的更新主要利用了矩阵的乘法, 所以时间复杂度也是O(vn²). 总体而言, 每次迭代的整体算法复杂度约为O(n³+vn²).

3 实验结果与分析 3.1 实验设置

本文与两个变体算法及8个对比算法在6个数据集上, 利用了5个评估指标来评估所提出方法的有效性.

1. 数据集说明

● 3-Sources数据集^[19]来自3个著名的在线新闻资源: BBC、Reuters、Guardian. 这个数据集在3个来源中共报道169篇, 分为6个主题标签, 每篇新闻都有一个主题标签;

● Yale Face数据集^[15]由耶鲁大学计算视觉与控制中心创建, 包含了15个人的165张GIF格式的灰度图像, 每个对象在不同心情、不同条件下提供11张照片, 图 2展示了Yale Face的部分数据样例;

● Newsgroups(NGs)数据集^[19]是20Newsgroups的子集, 包含了500个新闻组文档, 每个原始文档都使用3种不同的方式进行了预处理;

● MSRCV1数据集^[15]包含240张图像和8个对象类别. 我们选择7种类别的数据, 并提取6种类型的特征, 分别构成6个视角的数据;

● Texture-25数据集^[20]由1 000个未校准的图像组成, 分为25种不同纹理, 每个纹理包含40个样本;

● Olympics数据集^[15]包含464个用户, 涵盖了参与2012年伦敦夏季奥运会的运动员和组织. Groundtruth对应28种不同种类的运动.

2. 评估指标

本文采用5个度量指标评估算法的聚类性能^[21], 分别为归一化互信息(NMI)、聚类准确率(ACC)、F-score值、簇内样本的平均距离(AVG)、随机指数(RI).

(Ⅰ) 归一化互信息(NMI)描述了聚类划分结果和实际样本划分结果的相似程度, NMI定义为

$NMI = \frac{{\sum\nolimits_{s, t = 1}^k {\log (N{n_{st}}/{n_s}{n_t})} }}{{\sqrt {(\sum\nolimits_{s = 1}^k {{n_s}\log ({n_s}/N)} )(\sum\nolimits_{t = 1}^k {{n_t}\log ({n_t}/N)} )} }}$

(23)

其中, N是数据集包含的所有样本总数, n_s表示真实簇标签为第s簇的样本个数, n_t表示聚类结果为第t簇的样本个数, n_st表示聚类结果为第t簇而真实簇标签为第s簇的样本个数;

(Ⅱ) 聚类准确率(ACC)应用准确率来评估每个聚类中包含来自相应类的数据点, 其定义如下:

$ACC = \frac{{\sum\nolimits_{i = 1}^N {\delta ({s_i}, map({t_i}))} }}{N}$

(24)

其中, t_i和s_i分别表示聚类标签和真实簇标签; map(t_i)是排列映射函数, 将聚类标签和真实标签一一对应. 当s_i=map(t_i)时, δ(s_i, map(t_i))=1; 否则为0;

(Ⅲ) F-score的具体计算如下:

$F{\text{ - }}score = \frac{{2 \times P \times R}}{{P + R}}$

(25)

其中, P是准确率, R是召回率, λ用来权衡准确率和召回率;

(Ⅳ) 簇内样本的平均距离(AVG)计算了各个簇内样本间距离的平均值, 该值越小, 表示聚类结果越好. 假设聚类结果的簇划分C={C₁, C₂, …, C_k}其定义如下:

$AVG(\mathit{\boldsymbol{C}}) = \frac{2}{{|\mathit{\boldsymbol{C}}|(|\mathit{\boldsymbol{C}}| - 1)}}\sum\limits_{1 \leqslant i < j \leqslant |\mathit{\boldsymbol{C}}|} {dist({\mathit{\boldsymbol{x}}_i}, {\mathit{\boldsymbol{x}}_j})}$

(26)

(Ⅴ) 随机指数(RI)用来度量聚类结果和真实标签的相似性:

$RI = \frac{{TP + TN}}{{TP + FP + FN + TN}}$

(27)

其中, TP(true positive)是指实际是正样本被判定为正样本, TN(true negative)是指实际是负样本被判定为负样本, FP(false positive)是指实际是正样本被判定为负样本, FN(false negative)是指实际是负样本被判定为正样本.

除了簇内样本的平均距离(AVG)值越低表示聚类结果越好, 其余指标较高的值都表示较好的聚类性能.

3. 对比算法说明

本文提出的DWMSC方法的两个变体如下.

● MSC: 该方法是一个基础的多视角子空间算法, 具体公式如等式(3)所示;

● WMSC: 在MSC的基础上, 采用自适应权重策略对视角进行加权, 对应公式如等式(4)所示.

与DWMSC方法进行对比的8个多视角聚类算法如下所示.

● RMSC^[22]: 通过低秩分解和稀疏分解恢复共享的低秩转移概率矩阵, 然后通过马尔可夫链应用谱聚类以获得聚类结果;

● DiMSC^[9]: 利用希尔伯特·施密特(Hilbert Schmidt)独立标准(HSIC)作为多样性正则化来探索多视图表示的互补性;

● AMGL^[23]: 该算法将谱聚类扩展到多视图聚类, 通过无参数的自适应加权策略, 将不同视角的图融合成一个公共的表示;

● LMSC^[7]: 根据多个视图的互补性原则, 学习多视角数据的潜在表示, 并利用子空间模型对学习到的潜在表示进行聚类, 从而得到聚类结果;

● MLAN^[24]: 一种自适应多视角学习模型, 可以同时进行聚类和局部流形结构的学习;

● MLRSSC^[25]: 该方法通过低秩约束和稀疏约束来构造所有视图共享的相似度矩阵, 进而学习到联合的子空间表示;

● GMC^[19]: 使用自适应的加权策略共同构建每个视图的相似度矩阵并进行融合, 对融合后的图的拉普拉斯矩阵的秩进行约束, 使得该图能够直接指示聚类结果;

● DMF^[26]: 通过半非负矩阵分解建立深层结构, 寻求一个更一致的共同特征表示, 然后进行聚类得到聚类结果.

实验过程中, 我们对上述所有数据集都进行统一的归一化处理; 同时, 所有对比算法都进行参数调优选取最好结果. 为了消除随机性, 针对每一个基准数据集进行了30次实验, 并计算各指标的平均值和标准差. 实验结果以平均值(标准差)的形式展示.

3.2 实验结果分析

1. 消融性实验结果分析

具体实验结果见表 1.

相比于无加权MSC方法, 视角加权MSC在各个数据集的各项指标中均取得了更优的结果. 说明视角加权MSC利用视角的不同重要程度学习到更好的共享矩阵, 得到了较好的聚类结果. 相比于视角加权MSC方法, 本文所提出的DWMSC算法具有更好的聚类效果, 验证了引入加权核范数的必要性, 同时验证了所提出算法的优越性. 为了更加直观地呈现不同视角的重要程度, 验证了每个视角权重学习的差异性. 我们将目标函数收敛后得到的视角权重值进行了归一化处理. 各个数据集上不同视角的归一化权重值见表 2.

以Yale Face数据集为例, 图 3展现了该数据集通过DWMSC算法学习到的归一化视角权重, 以及每一个视角在DWMSC算法下的聚类结果, 即NMI和ACC指标. 我们可以发现: 该数据集上第2个视角相比于第1个、第3个视角具有更好的聚类效果, 聚类结果的好坏与视角权重的大小是一致的, 验证了引入视角加权的重要性. 图 4展示了DWMSC及变种方法的相似度矩阵的可视化结果, 其中, 相似度矩阵S=|Z|+|Z^T|. 3张图片分别代表MSC、WMSC和DWMSC算法的相似度矩阵可视化结果. 很明显, DWMSC更清楚地揭露了子空间的底层结构, 证明了我们的双加权策略的有效性.

2. 对比实验结果分析

表 3展现了DWMSC算法与其他对比算法在6个基准数据集上的实验结果. 通过观察可以得到:

● 对于RMSC算法, DWMSC在所有数据集的各项评价指标上均表现出更好的性能. 其中, 我们的算法在NMI指标中至少比RMSC算法高出了9.47%. 主要由于DWMSC方法中的双加权策略学习到了更准确、更低秩的公共表示;

● 与基于相似度诱导构图的多视角聚类算法(AMGL、MLAN、GMC)相比, 本文提出的方法能够更好地捕获数据的全局结构, 因此获得了更好的聚类性能;

● 与多视角子空间聚类算法(DiMSC、LMSC、MLRSSC)相比, 我们在各项指标上均具有优势, 尽管这些方法采用自表达方式构建图, 但它们并未通过加权核范数学习更低秩的共享系数矩阵.

总之, 这些对比结果验证了本文的自适应加权策略和核范数加权策略的有效性.

3.3 算法时间性能对比

我们在相同的计算环境下对每种算法进行了30次实验, 并记录了每种方法在每个数据集上的平均运行时间. 结果见表 4, 从表中我们可以看出, 谱聚类算法(如RMSC、AMGL、MLAN)的执行效率通常比子空间算法(如DiMSC、LMS、MLRSSC、DWMSC)更高, 主要原因是谱聚类算法的子问题较少, 运算相对简单. 在所有的聚类算法中, 我们在6个数据集上优于LMSC和DMF算法, 在3个数据集上优于RMSC和GMC. 结果表明, 该方法的计算效率中等. 原因是, 我们的方法需要计算矩阵的特征值和特征向量. 虽然我们计算的子问题较多, 但是整个算法收敛非常快, 这将在下一小节给出进一步的分析.

3.4 参数设置与收敛性实验

表 5展示了本文提出的算法与其他8个对比算法在6个不同数据集上的参数设置. 其中, 算法AMGL、MLAN、GMC不需要调试参数, 因此没有列出. 其他对比算法均选取最佳结果所对应的参数设置. 本文提出的方法引入了3个参数: λ、β、γ. 本文在集合{0.001, 0.01, 0.1, 1, 10, 100, 1000}中选择平衡参数λ和β的值. 针对权重分布参数γ的值, 本文尝试在集合{0.1, 0.5, 1.5, 2}中选取. 通过观察表单可以得到: 通常在γ=2时, DWMSC算法在不同数据集上基本取得了最优的结果, 由于λ调度误差项所以通常会小一些.

同时, 我们探究了所提出的DWMSC算法的收敛速度. 由于该算法子问题较多, 我们很难给出收敛性证明, 但实验结果表明了该算法的有效性和收敛性. 图 5显示了该算法在所有6个数据集上的收敛曲线.

可以看出, 我们提出的算法都可以在50次迭代内实现收敛, 表明该算法具有良好的收敛特性.

4 结论

本文提出了一种新的多视角聚类算法, 称为双加权多视角子空间聚类(DWMSC). 该方法引入了无参数加权策略以区分不同视图的贡献; 同时, 该方法采用加权核范数将共享系数矩阵不同奇异值赋予不同权重, 使得共享系数矩阵更加低秩. DWMSC方法将视角加权和核范数加权集成到统一的子空间框架中, 通过在6个不同基准数据集上的实验, 验证了本文所提方法的有效性和优越性. 我们未来的工作包括将此框架与深度框架融合, 并运用于处理实际问题.