1 引言

在实际应用中将来自多个源或者通过不同的采集器采集到的数据, 称为是多视图数据^[1]. 例如, 我们可以通过人脸、指纹、签名或虹膜来进行人物识别; 通过颜色、纹理或图注特征来表示一张图像. 多视图聚类就是利用隐藏在多个视图数据中的互补信息和一致信息来提高聚类性能^[2,3]. 最直接的方式就是将多视图数据的特征进行简单拼接, 然后执行单视图聚类算法. 然而, 在实际应用中, 特别是多媒体领域, 每个视图的数据都是一个高维的特征空间, 将各视图特征拼接显然会带来“维度诅咒”. 另外, 对于高维数据, 特征分布通常更稀疏, 传统欧式距离来进行相似性度量的方法根本不适用^[4]. 为了解决这个问题, 本文使用了低秩约束的方法从高维数据中学习低维的子空间, 这样既缩减了计算的复杂度, 也提高了对噪声数据的鲁棒性.

另外, 目前的多视图聚类方法主要分为基于潜在一致信息、基于多样互补信息和综合潜在一致和互补信息三大类. 这些方法都有一个共同的缺点, 它们平等的对待各视图. 由于各视图表征数据的能力有强弱之分, 故赋予各视图不同的权重更具合理性^[5]. 洪敏等^[6]考虑到不同样本存在的“全局”信息的差异, 提出了样本加权的K-means多视图聚类算法; Xu等^[7]提出了在各视图间和视图内特征都进行加权的K-means多视图聚类算法; 聂飞平等致力于研究自动加权的多图学习模型, 主要有AMGL^[8]和SwMC^[9]模型, 还有Huang和Wang等^[10,11]提出无需引入任何权值和惩罚参数自动为各视图分配权重的多视图聚类算法, 但这些方法主要是针对基于K-means或基于图的多视图聚类. 本文针对基于子空间的多视图聚类方法提出的自适应权重学习方法, 在目标函数中设置了权重参数, 且在函数优化的过程中以自动学习的方式同时优化各权值.

2 本文方法 2.1 自表示的子空间聚类

自表示的子空间聚类可以有效处理高维数据, 它是基于这样的假设: 空间中的任何数据点都可以通过其他样本点的线性组合得到. 设 ${X^{(v)}} = [x_1^{(v)},x_2^{(v)},\cdots,x_n^{(v)}] \in {{\mathbb{R}}^{{d_v} \times n}}$ 为第v个视图的数据矩阵, 其中每一列为一个样本, ${d_v}$ 为特征空间的维度. 自表示方式的子空间聚类方程如下所示:

$ \mathop {\min }\limits_Z {\cal{L}}({X^{(v)}},{X^{(v)}}{Z^{(v)}}) + \lambda \Omega ({Z^{(v)}}) $

(1)

其中, ${\cal{L}}( \cdot , \cdot )$ 表示数据重构的误差损失函数, $\Omega ( \cdot )$ 表示正则项, 并且λ用于平衡公式中的两项. Z^(v)为潜在的自表示系数矩阵, 当求得Z^(v)后, 就可以通过式(2)来得到用于谱聚类输入的亲邻矩阵S.

$S{\rm{ = }}\sum\nolimits_{v = 1}^V {\left( {\left| {{Z^{(v)}}} \right| + \left| {{Z^{(v)}}^{\rm{T}}} \right|} \right)} \Bigg/2$

(2)

2.2 低秩约束

正如前面讨论的, 对于高维数据, 构造一个低秩的矩阵可以很好地捕获数据的特征. Liu等^[12]提出了用于单视图数据的低秩表示方法, 即将数据样本表示为基的线性组合, 然后从这些候选对象中寻找最低的秩表示. 本文将它扩展到多个视图, 也就是每个视图数据都进行最低秩表示, 如式(3)所示.

$ \mathop {\min }\limits_Z \sum\limits_{v = 1}^V {\left( {{{\left\| {{Z^{(v)}}} \right\|}_*} + \lambda {{\left\| {{E^{(v)}}} \right\|}_{2,1}}} \right)} \;{\rm{s}}.{\rm{t}}.\;{X^{(v)}} = {X^{(v)}}{Z^{(v)}} + {E^{(v)}} $

(3)

其中, ${\left\| {{Z^{(v)}}} \right\|_*}$ 为Z的核范数, 也就是对Z进行秩约束; ${\left\| {{E^{(v)}}} \right\|_{2,1}}$ 是自表示重构误差项, 用L−2, 1范数约束可以使E的列元素为0; λ是用于平衡这两项的正值参数.

2.3 加权融合

由于多视图数据描述的是同一事物, 所以这些视图数据有潜在相同的数据结构^[13], 那么多视图聚类的目的就是要从不同视图数据中挖掘出潜在一致的数据结构. 类似的, 本文假设潜在一致数据结构Z是由各视图低秩表示Z^(v)线性组合得到的. 另外, 考虑到数据的噪声、缺失等因素, 还有不同视图数据表征能力的差异性, 表征能力强的数据可以很好助力聚类, 而表征能力差的数据含有大量噪声和冗余特征阻碍了聚类性能. 因此, 我们利用了加权的方法来融合得到潜在一致矩阵Z, 如式(4)为本文提出的目标函数.

$\left\{\begin{split} & \mathop {\min }\limits_Z \displaystyle\sum\limits_{v = 1}^V {\left\{ {{\left\| {{Z^{(v)}}} \right\|}_*} + \lambda {{\left\| {{E^{(v)}}} \right\|}_{2,1}}{\rm{ + }}\dfrac{{{\pi _v}}}{2}\left\| {{Z^{(v)}} - Z} \right\|_F^2\right\} } + \gamma {\left\| \Pi \right\|^{\rm{2}}} \\ & {\rm s.t.}\;{\rm{ }}{X^{(v)}} \!\!=\!\! {X^{(v)}}{Z^{(v)}} \!\!+\!\! {E^{(v)}}, \; \Pi\!\! = \!\!{({\pi _1},\cdots,{\pi _v})^{\rm{T}}},{\rm{ }}{\pi _v}\!\! >\!\! 0,{\rm{ }}\sum\limits_{v = 1}^V {{\pi _v}}\!\! = \!\!1 \\ \end{split} \right.$

(4)

式中, $\left\| {{Z^{(v)}} - Z} \right\|_F^2$ 用来测量潜在一致低秩矩阵Z和第v个视图的低秩表示 ${Z^{(v)}}$ 之间的差异, ${\pi _v}$ 为各视图权重, 从目标函数整体来看, $\left\| {{Z^{(v)}} - Z} \right\|_F^2$ 值大, 对应的权重值就小. γ为平衡参数, 添加最后一项是为了防止权重过拟合到一个视图, 也就是避免出现平凡解.

3 优化

式(4)是典型的低秩优化问题, 本文利用了增广拉格朗日乘子法来进行优化. 为了变量可分, 引入了辅助变量R^(v)代替Z^(v)得到式(5).

$\left\{ \begin{array}{l} \mathop {\min }\limits_{{Z^*}} \displaystyle\sum\limits_{v = 1}^V {\left\{ {{{\left\| {{R^{(v)}}} \right\|}_*} + \lambda {{\left\| {{E^{(v)}}} \right\|}_{2,1}}{\rm{ + }}\frac{{{\pi _v}}}{2}\left\| {{Z^{(v)}} - Z} \right\|_F^2} \right\}} + \gamma {\left\| \Pi \right\|^{\rm{2}}}\\ {\rm{s}}.{\rm{t}}.\;\left\{ \begin{array}{l} {X^{(v)}} = {X^{(v)}}{Z^{(v)}} + {E^{(v)}},{R^{(v)}} = {Z^{(v)}}\\ \Pi = {({\pi _1}, \cdots ,{\pi _V})^{\rm{T}}},{\pi _v} > 0,\displaystyle\sum\limits_{v = 1}^V {{\pi _v}} = 1 \end{array} \right.{\rm{ }} \end{array} \right.$

(5)

对应的增广拉格朗日函数如式(6), 其中 $Y_1^{(v)}$ 和 $Y_{\rm{2}}^{(v)}$ 为拉格朗日乘子, $\left\langle { \cdot , \cdot } \right\rangle $ 表示两个矩阵的内积, μ>0为可适应的惩罚参数.

$\left\{ \begin{array}{l} \mathop {\min }\limits_{{Z^*}} \displaystyle\sum\limits_{v = 1}^V {\left\{ {{{\left\| {{R^{(v)}}} \right\|}_*} + \lambda {{\left\| {{E^{(v)}}} \right\|}_{2,1}}{\rm{ + }}\frac{{{\pi _v}}}{2}\left\| {{Z^{(v)}} - Z} \right\|_F^2} \right\}} + \gamma {\left\| \Pi \right\|^{\rm{2}}}\\ {\rm{s}}.{\rm{t}}.\;\left\{ \begin{array}{l} {X^{(v)}} = {X^{(v)}}{Z^{(v)}} + {E^{(v)}},{R^{(v)}} = {Z^{(v)}}\\ \Pi = {({\pi _1}, \cdots ,{\pi _V})^{\rm{T}}},{\pi _v} > 0,\displaystyle\sum\limits_{v = 1}^V {{\pi _v}} = 1 \end{array} \right. \end{array} \right.\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!$

(6)

3.1 更新R^{(v )}

固定除R之外的其他所有变量, 得到关于R的子问题如式(7):

$O({R^{(v)}}) = \min {\left\| {{R^{(v)}}} \right\|_{\rm{*}}}{\rm{ + }}\dfrac{\mu }{{\rm{2}}}\left\| {{R^{(v)}} - ({Z^{(v)}} + Y_2^{(v)}/\mu )} \right\|_F^2$

(7)

上式可以通过奇异值阈值法^[14]来求解如式(8), 获得闭形式的解. 其中 ${S_\tau }[ \cdot ]$ 是收缩阈值操作符.

${R^{(v)}} = {S_{{\rm{1}}/\mu }}\left[ {{Z^{(v)}} + Y_2^{(v)}/\mu } \right]$

(8)

3.2 更新Z^{(v )}

固定除Z^(v)之外的其他所有变量, 得到关于Z^(v)的子问题如式(9):

$\begin{split} O({Z^{(v)}}) =& \min \dfrac{{{\pi _v}}}{2}\left\| {{Z^{(v)}} - Z} \right\|_F^2 \\ &+ \dfrac{\mu }{{\rm{2}}}\left\| {{X^{(v)}}{Z^{(v)}} - \left( {{X^{(v)}} - {E^{(v)}}{\rm{ + }}Y_1^{(v)}{\rm{/}}\mu } \right)} \right\|_F^2 \\ & +\dfrac{\mu }{{\rm{2}}}\left\| {{Z^{(v)}} - \left( {{R^{(v)}}{\rm{ + }}Y_2^{(v)}/\mu } \right)} \right\|_F^2 \\ \end{split} $

(9)

对式(9)求关于Z^(v)的导数, 并令其为0, 得到了下面的优化解.

$\begin{split} {Z^{(v)}} =& \left( {{{\left( {({\pi _v} + \mu )I + \mu {{\left( {{X^{(v)}}} \right)}^{\rm{T}}}{X^{(v)}}} \right)}^{ - 1}}} \right.\\ &\left. {{{\left( {{\pi _v}{Z^*} + \mu ({X^{(v)}}} \right)}^{\rm{T}}}\left( {{X^{(v)}} - {E^{(v)}}{\rm{ + }}Y_1^{(v)}{\rm{/}}\mu } \right){\rm{ + }}\mu {R^{(v)}} - Y_2^{(v)}} \right) \end{split} $

(10)

3.3 更新E^{(v )}

固定除E之外的所有变量, 得到关于E的子问题如式(11):

$\begin{split} O({E^{(v)}}) = &\min \lambda {\left\| {{E^{(v)}}} \right\|_{2,1}}{\rm{ + }}\\ &\dfrac{\mu }{{\rm{2}}}\left\| {{E^{(v)}}{\rm{ - }}\left( {{X^{(v)}} - {X^{(v)}}{Z^{(v)}}{\rm{ + }}Y_1^{(v)}{\rm{/}}\mu } \right)} \right\|_F^2 \end{split}$

(11)

参照文献[12]中引理3.3得到下面的优化解.

${\left[ {{E^{(v)}}} \right]_{:,k}} = \left\{ \begin{array}{l} \frac{{{{\left\| {{{\left[ {{Q^{(v)}}} \right]}_{:,k}}} \right\|}_2} - 1/\mu }}{{{{\left\| {{{\left[ {{Q^{(v)}}} \right]}_{:,k}}} \right\|}_2}}}{\left[ {{Q^{(v)}}} \right]_{:,k}},\;{\rm{if}}\;{\left\| {{{\left[ {{Q^{(v)}}} \right]}_{:,k}}} \right\|_2} > 1/\mu \\ 0,\;{\rm else} \\ \end{array} \right.$

(12)

其中, ${Q^{(v)}} = ({X^{(v)}} - {X^{(v)}}{Z^{(v)}} + Y_1^{(v)}/\mu )$ 并且 ${\left[ {{Q^{(v)}}} \right]_{:,k}}$ 为 ${Q^{(v)}}$ 的第k列.

3.4 更新Z

固定除Z外的其他变量, 得到了关于Z的子问题:

$O({Z^*}) = \min \sum\limits_{v = 1}^V {{\pi _v}\left\| {{Z^{(v)}} - Z} \right\|_F^2} $

(13)

对式(13)求关于Z的导数, 并令其为零, 得到了下面的优化公式:

$Z = \sum\nolimits_{v = 1}^V {{\pi _v}} {Z^{(v)}}\Bigg/\sum\nolimits_{v = 1}^V {{\pi _v}} $

(14)

3.5 更新Π

固定Π之外的其他变量, 得到了关于Π的子问题.

$\left\{\begin{split} & O(\omega ) = \min \displaystyle\sum\limits_{v = 1}^V {\dfrac{{{\pi _v}}}{{\rm{2}}}\left\| {{Z^{(v)}} - Z} \right\|_F^2} + \gamma {\left\| \Pi \right\|^2} \\ & {\rm s.t.}\;\Pi = {({\pi _1},\cdots,{\pi _V})^{\rm{T}}},{\rm{ }}{\pi _v} > 0,{\rm{ }}\sum\limits_{v = 1}^V {{\pi _v}} = 1 \\ \end{split} \right.$

(15)

令 ${f^{(v)}} = \left\| {{Z^{(v)}} - Z} \right\|_F^2$ , 我们可以通过下面的公式来求解上述问题.

$\left\{ \begin{split} & O = \mathop {\min }\limits_\omega {\left\| {\Pi + \frac{1}{\gamma }{{f}}} \right\|^2}\\ & {\rm{s.t.}}\;{\pi _v} \ge 0,{1^{\rm T}}\Pi = 1,{{f}} = \left[ {{f^1},{f^2}, \cdots ,{f^v}} \right] \end{split}\right. $

(16)

这是经典的二次规划问题, 可以通过Matlab中现有的凸优化工具CVX来解决.

3.6 更新拉格朗日乘子

$\left\{\begin{split} & Y_1^{(v)} = Y_1^{(v)} + \mu \left( {{X^{(v)}} - {X^{(v)}}{Z^{(v)}} - {E^{(v)}}} \right) \\ & Y_2^{(v)} = Y_2^{(v)} + \mu \left( {{Z^{(v)}} - {R^{(v)}}} \right) \\ \end{split} \right.$

(17)

我们重复迭代上述6个步骤, 直到满足收敛条件 ${\left\| {{X^{(v)}} - {X^{(v)}}{Z^{(v)}} - {E^{(v)}}} \right\|_\infty } \le \varepsilon $ 并且 ${\left\| {{Z^{(v)}} - {R^{(v)}}} \right\|_\infty } \le \varepsilon $ , 或者达到预先设定的最大迭代次数, 然后将得到的 $Z$ 进行谱聚类操作. 具体的优化过程如算法1所示.

算法1. 优化过程

输入: 多视图数据集X={X⁽¹⁾, …, X^(V)}, 类簇数k, 参数 $\scriptstyle \lambda ,\gamma $ , 最大迭代次数maxIter, $\scriptstyle{\mu _{\max }}{\rm{ = 1}}{{\rm{0}}^{\rm{6}}}$ , ρ=1.1.

1: 　 Repeat

2: 　　 For v∈V do

3: 　　　　利用求解式(8)更新 $\scriptstyle{R^{(v)}}$

4: 　　　　利用求解式(10)更新 $\scriptstyle{Z^{(v)}}$

5: 　　　　利用求解式(12)更新 $\scriptstyle{E^{(v)}}$

6: 　　　　利用求解式(16)更新权重Π

7: 　　　　利用式(17)更新拉格朗日乘子 $\scriptstyle{Y_1}^{(v)}$ , $\scriptstyle{Y_2}^{(v)}$

8: 　　 end

9: 　　利用求解式(14)更新Z

10: 　　更新 $\scriptstyle \mu = \min (\rho \mu ,{\mu _{\max }})$

11: 　 Until 收敛或达到最大迭代次数

输出: Z.

4 实验 4.1 数据集及评价指标

为了验证所提多视图聚类算法的有效性, 本文选取了5个公开的数据集进行实验, 各数据集描述如下:

(1) Digits数据集包含2000张手写的0–9数字图像数据, 每个数字包含200条样本, 共有6个视图. 本实验选择了Fourier和pixel两个视图.

(2) Caltech101-7是一个广泛使用的图像数据集, 包含7个类别共441张图像, 由CENTRIST、CMT、GIST、HOG、LBP和SIFT 6个视图组成.

(3) 3-source数据集包含BBC、Reuters和Guardian 3个源的新闻数据, 共169条分为6个类别.

(4) WebKB数据集包含Texas、Cornell、Washington和Wisconsin 4个大学的网页数据. 每个网页由内容、链入信息、视角和城市4个视图. 由于4个子数据集是相似的, 本文采用了Texas数据集进行实验, 它包含187条样本共5个类别.

(5) MRSCV1 数据集包含240张共8个类别的图像, 本实验选择常用的牛、树、建筑、飞机、人脸、汽车和自行车7个物体, 包含与Caltech101-7数据集相同的6个视图.

另外, 本文采用了两个通用的聚类评价指标ACC和NMI来对实验结果进行评价.

4.2 比较实验及讨论

将所提算法与现有相关算法进行比较, 包括单视图的子空间聚类模型(LRR)、协同正则的多视图谱聚类模型(CoregSPC)^[15]还有潜在的多视图子空间聚类模型(LMSC)^[16]. 对于单视图的LRR模型, 我们进行了两次实验, 在每个视图上执行LRR算法, 从得到的结果中取最好的记为LRR_best; 另外, 我们将各视图的特征进行直接拼接后, 在其上执行LRR算法, 得到的结果记为LRR_catFea. 对于比较算法, 涉及到的参数都按照原论文中作者建议的值进行设置. 另外, 为了避免算法中随机初始化引起的误差, 每个算法在各数据集上都重复进行10次实验, 然后取均值作为最后结果. 表1就是各算法在相应数据集上的聚类准确率和NMI值.

从表中可以看出本文所提算法在5个公开的数据集均优于其他的模型, 可见算法发挥出了它应有的效果, 将表征能力强的视图赋予了大的权重, 且摒弃了冗余的特征和噪声特征.

4.3 参数敏感性分析

在所提算法中存在λ和γ两个参数, 我们采用网格搜索的策略来选择最优的参数组合, 设置λ的取值范围均为[10^–4, 10⁴], γ的取值范围为[1, 10⁵], 图1分别展示了两个参数在设定范围内所提算法在3个数据集上的准确率和NMI值. 从图中可以看出参数在给定的范围内对应的ACC与NMI值变化都不是特别大, 说明该算法在给出的取值范围内对参数λ和γ不敏感; 不过从MRSCV1和3-sources数据集的结果可以看出γ取值在[1, 10⁵], λ取[10^–2, 10²]聚类结果相对较好, 故在其他数据集上进行实验时, 我们固定γ值为10, 然后让λ取[10^–2, 10²].

5 总结与展望

文章提出了一个低秩约束的自适应权重的多视图子空间聚类算法, 由于高维数据的特征分布比较稀疏, 所以利用低秩约束来进行各视图子空间的自表示矩阵, 然后学习各视图共享的潜在一致数据结构, 另外, 在寻找各视图的一致结构时对各视图设置权值, 在算法优化的过程中该权值会随着目标函数优化. 在公开的数据集上进行实验证明了所提算法的优越性.