闫金涛, 李钟毓, 唐启凡, 周志豪

(西安交通大学软件学院, 710049, 西安)

在图像处理或者文本处理任务中,往往需要处理高维数据,子空间聚类算法是一种处理高维数据的常用聚类算法。高维数据一般嵌入在低维子空间中,子空间聚类利用这一特性在不同的子空间中寻找合理的聚类划分[1]。具体而言,给定一个来自多个子空间并集的数据集,子空间聚类的任务就是计算出子空间的数目、维度、每个子空间对应的基和数据分割[1]。因为子空间聚类算法在处理高维数据时效果很好,所以被广泛应用于运动分割[2-3]、面部分类[4-5]和电影推荐[6-7]等领域。

基于稀疏表示和低秩表示的子空间聚类算法[8]受到学者们的广泛关注,这些算法利用无噪声样本点具有自表达的特性,实现对样本点的重建,即每个样本点可以被表示为其他样本点的线性组合[9-13]。SSC算法在数据重建过程中添加l1正则化约束,保留更加关键的信息[11];针对实际采样过程中噪声难以避免的问题,Liu等将低秩表示约束引入到目标函数中[12];部分学者认为,实际的样本点之间的自表达关系并不一定仅仅是线性的,也有可能是非线性的[14-15]。DSC算法[14]、DLRSC算法[15]将深度神经网络引入到模型中,需要更加合适的自表达关系。实验证明,基于深度学习的子空间聚类算法往往可以更有效地挖掘数据点之间的复杂关系,找到更恰当的自表达方式,从而获得更优的聚类性能。

多视角数据是从多个来源或者不同测量方法得到的,在实际应用中很常见[16]。例如:同一幅图像可以用不同的特征(SIFT[17]、LBP[18]和HOG[19]等)来描述;同一个新闻可以由不同的叙述方式来表达。由于多视角数据具有相关性和互补性,多视角聚类算法可以在单视角聚类的基础上获得更好的效果[20-24]。Abavisani等的DMSC算法在深度自编码器的基础上提出一种基于亲和融合的深度卷积神经网络,该网络中不同视角对应的自表达层是相同的,并且取得了很好的效果[23]。

为了在深度多视角子空间聚类算法中添加低秩表示约束,本文提出了一种新的基于深度学习的低秩多视角子空间聚类算法(DLRMSC)。该算法通过矩阵分解的思想,将自表达层的矩阵分解为两个低秩矩阵,在深度多视角子空间聚类模型基础上实现了对样本点之间自表达关系的低秩表示约束,能够在保持计算复杂度基本不变的情况获取更加鲁棒的聚类结果。本文算法把自表达模块划分为一致性信息层和特异性信息层,一致性信息层学习各视角的一致性信息,特异性信息层获取每个视角的独特信息,兼顾了不同视角的一致信息和互补信息。实验表明,本文提出的双层自表达模块可以有效降低深度子空间聚类模型的参数数量,并获得比较好的性能。

1 相关工作

1.1 子空间聚类算法

SSC算法[11]和LRR算法[12]都利用了无噪声样本点的自表达特性,即每个样本点都可以被其他样本点的线性组合表示。因此,这类算法计算自表达矩阵C的一般求解公式为

(1)

式中:λ表示正则化参数;矩阵C满足稀疏约束或者低秩约束。在稀疏子空间聚类算法SSC[11]中,‖·‖p表示l1范数;在低秩子空间聚类算法LRR[12]中,‖·‖p表示核范数。在SSC算法中,为防止得到平凡解C=I,需要添加约束diag(C)=0。

求解出自表达矩阵C之后,可以得到亲和矩阵W=(|C|+|C|T)/2,最后通过谱聚类算法[25]得到X的聚类结果。

1.2 基于深度学习的子空间聚类算法

Ji等认为实际的样本点之间的自表达关系是非线性的,提出了基于深度模型的DSC算法[14]。DSC算法通过深度自编码器把数据投影到隐空间中,再利用原始数据的隐空间表示得到自表达矩阵。DSC算法通过将自表达层嵌入在编码器和解码器之间来计算自表达矩阵。求解DSC算法的目标函数为

(2)

DLRSC算法在DSC算法的基础上改进自表达层,通过双层自表达模块(一个低秩自表达层和其转置)隐性地对自表达矩阵添加了低秩表达约束,提高了算法的鲁棒性[15];MLRDSC算法在DSC算法的基础上加入多层级自表达层以挖掘多层次特征信息,促进自表达特性学习,提高了聚类性能[26];SCMSFSC算法引入了多层级自表达模块融合模块,并且采用自监督方法对模型加入相似性约束,从而提高聚类性能[27]。实验证明,基于深度学习的子空间聚类算法往往可以更有效地挖掘数据点之间的复杂关系,找到更恰当的自表达方式,从而获得更优的聚类性能。

1.3 基于深度学习的多视角聚类算法

DMSC算法[23]将DSC算法拓展到了多视角聚类,是一种经典的深度多视角子空间聚类算法。DMSC算法提出亲和融合的方法,用相同的自表达层将不同视角融合起来,得到亲和融合自表达矩阵[23];在基于自编码器的多视角聚类算法基础上,Zhang等提出了一种端到端的深度多模态聚类框架,实现了特征学习和多模态聚类的联合优化[28];Zhou等提出了一种端到端的对抗注意力网络,利用对抗学习和注意力机制对潜在特征分布进行对齐和各视角重要性的量化,将融合特征投影到适合聚类划分的空间中去,获得了很好的聚类效果[29];何士豪等则提出了一种新的互补与一致的多视角子空间聚类网络,利用自监督的方法来探索多视角数据的互补性,并且取得了很好的效果[30]。

与传统多视角子空间聚类算法相比较,深度算法具有更好的聚类性能。因为深度模型能够更加有效地挖掘数据特征,捕捉到样本点之间的关系。值得注意的是,传统多视角聚类使用低秩表示约束来提高模型的鲁棒性[14,20],深度多视角子空间聚类算法只对自表达矩阵采用稀疏表示约束,却没有采用低秩表示约束。一个主要原因是低秩约束需要计算SVD分解,这会导致深度模型在训练中产生很高的计算复杂度。单视角算法DLRSC[15]采用双层自表达模块,隐性地实现了对自表达矩阵的低秩表示约束,并且避免计算复杂度过高的SVD分解。受到DLRSC算法[15]启发,本文将双层自表达模块引入到深度多视角子空间聚类算法中,实现了深度低秩多视角子空间聚类算法。与DLRSC算法不同,DLRMSC算法是应用于多视角聚类的。为充分利用多视角数据的一致性和互补性,DLRMSC算法将双层自表达模块分为一致性自表达层和特异性自表达层,分别用来捕捉不同视角的一致性信息和各视角的独特性信息。

2 深度低秩多视角子空间聚类

2.1 问题描述

给定一个多视角数据集{X(1),…,X(M)},其中,X(m)∈Rdm×N表示第m个视角下的数据矩阵,M表示视角数,N表示样本数,dm表示第m个视角的特征空间维度。

(3)

各视角的自编码器负责提取原始数据特征,自表达层嵌入在编码器和解码器之间。DMSC算法[23]首先通过自编码器捕捉原始数据的非线性关系,然后通过亲和融合的方式学习所有视角在隐空间中的公共自表达矩阵C,最后通过谱聚类算法确定最后的聚类划分。

低秩表示约束能够提高子空间聚类的鲁棒性,帮助模型获得更好的聚类效果。因此,本文提出深度低秩多视角子空间聚类算法,在深度多视角聚类算法中添加隐性的低秩表示约束。DLRMSC算法能够将样本点非线性地投影到一个适合于求解自表达特性的隐空间中,并且通过空间融合学习到低秩表示的公共自表达矩阵。

2.2 深度低秩多视角子空间聚类

本文提出的DLRMSC算法框架包含特征提取模块和双层自表达模块共两个模块。本小节着重介绍双层自表达模块的低秩表示约束以及在学习多视角数据互补性的优势。

为了向自表达矩阵中添加低秩表示约束,最常用的做法是直接在损失函数中添加自表达矩阵C的核范数正则化项‖C‖*。但是,在反向传播算法中核范数约束的梯度难以计算,这使得这一方法行不通。为此,本文在DMSC算法[23]的目标函数中直接添加约束rank(C)≤r,其中r是一个常量且满足r≪N。由此,得到目标函数

(4)

为了在深度多视角子空间聚类网络中实现rank(C)≤r,本文采用矩阵分解的方法,使用两个低秩矩阵U∈Rn×m、V∈Rm×n的乘积来替代自表达矩阵C。这样自表达层就分解成了两个低秩线性全连接层,参数分别是两个低秩矩阵U和V。由于rank(UV)≤min(rank(U),rank(V))≤r,并且r≪N,因此自表达矩阵UV满足低秩表示约束。得到新的损失函数

(5)

如果式(5)满足对自表达矩阵的低秩表示约束rank(UV)≤r,那么就避免了自表达矩阵的平凡解UV=I,因此可以去掉约束diag(UV)=0。基于多视角数据的一致性,多视角子空间聚类算法通常假设所有视角共享同一个自表达矩阵[20,23,31-32]。但是,实际应用中不同视角的数据还具有独特性,所有视角共享同一个自表达矩阵的做法并不恰当[4,22-33]。为了充分挖掘多视角数据的互补性,本文将双层自表达模块分为一致性自表达层和特异性自表达层。所有视角共享一致性自表达层,但是拥有不同的特异性自表达层。最终,得到损失函数

(6)

图1是DLRMSC模型框架。图中:a、b、c分别表示每个视角的特征提取模块,由深度自编码器组成;d表示双层自表达模块,由两个低秩全连接层组成。双层自表达模块的第一层是一致性自表达层,所有视角的系数矩阵都是U;第二层是特异性自表达层,各个视角的系数矩阵不相同,分别是V1、V2、V3。将各个视角的原始数据分别输入到各自的编码器中,编码器的输出被输入到一致性自表达层中,得到的结果再分别输入到对应的特异性自表达层中,计算隐空间中样本点的重构结果。分别把自表达模块的输出输入到各自解码器中,得到最终的重构数据。

图1 DLRMSC模型框架Fig.1 Architecture of proposed DLRMSC model

DLRMSC算法具有与DMSC算法[23]相似的结构,主要区别在于自表达模块的不同。在DMSC算法自表达层的基础上,DLRMSC算法将自表达层的系数矩阵分解为两个低秩矩阵,隐性地实现对样本点自表达关系的低秩表示约束。直接在深度多视角聚类模型中添加低秩表示约束项的做法将会给模型的训练带来巨大的复杂度,导致模型参数无法训练。但是,DLRMSC算法通过这种矩阵分解的方法巧妙地降低了模型训练的复杂度,可以在保持计算复杂度基本不变的情况下提高深度多视角子空间聚类算法的鲁棒性。

值得注意的是,DLRMSC算法的双层自表达模块有助于降低深度多视角子空间的计算复杂度,双层自表达模块中的参数数量2rMN要小于单层自表达模块的参数数量N2(2rM≪N)。因此,模型训练中计算2M个大小为r×N矩阵梯度的复杂度要小于计算一个大小为N×N矩阵梯度的复杂度。

2.3 模型求解

模型训练包括预训练和微调两个阶段。预训练阶段的目标是得到性能良好的特征提取模块,这里只训练特征提取模块,第v个视角下解码器的输入是Z(m),目标函数是

(7)

微调阶段,训练整个深度低秩多视角子空间聚类网络,第v个视角下解码器的输入是Z(m)UV(m),目标函数是式(6)。

模型训练结束之后,提取自表达模块的参数矩阵V(m)、U,即可得到一个包含多视角数据一致性信息和互补性信息的低秩自表达矩阵C

(8)

获得低秩自表达矩阵C后,可以得到相似性矩阵W=(C+CT)/2,最后通过谱聚类算法[25]得到多视角数据的聚类结果。DLRMSC算法伪代码如下。

输入:数据集{X(1),…,X(M)};

随机初始化超参数:r、λ1、λ2;

输出:聚类划分

1.使用目标函数式(7)训练网络;

2.使用目标函数式(6)训练网络;

4.通过式(8)计算低秩自表达矩阵C;

5.计算相似性矩阵W=(C+CT)/2;

6.使用谱聚类算法对相似性矩阵W做出聚类划分;

7.输出聚类划分。

3 实验对比与分析

3.1 实验设定

3.1.1 数据集 为验证算法的有效性,采用多特征图像、多视角新闻文本和多视角电影文本等6个常用的公开数据集来测试DLRMSC算法,具体情况如下。

(1)Yale数据集包含15个对象的人脸图像,每个对象有11幅图像,共165幅图像。使用灰度、LBP[18]、Gabor[34]共3种特征来描述图像。

(2)3-sources数据集是多视角文本数据集,来源于BBC、路透社、卫报这3个知名在线新闻网站,共有6个种类、169个样本。

(3)Movies数据集是电影数据集,包含了17种类型的617个样本,共有关键词描述和演员描述两个视角。

(4)ORL数据集包含40个对象的人脸图像,每个对象有10幅图像,共400幅图像。使用灰度、LBP[18]、Gabor[34]共3种特征来描述图像。

(5)Caltech-101数据集[35]。本文使用Caltech-101数据集的部分数据,包括7个对象,共441个样本。使用HOG[19]、LBP[18]、SIFT[17]共3种特征来描述图像。

(6)UCI数据集是图像数据集,包含2 000幅图像、10个对象。使用傅里叶系数、像素平均值和形态特征共3种特征来描述图像。

3.1.2 评价指标 为评估算法的有效性,本文选取聚类准确度和标准化互信息这两个常用的聚类评价指标。这两个指标的数值越大,则聚类效果越好。

聚类准确度(A)表示聚类结果的正确率,计算公式为

(9)

式中:wi表示第i个样本的聚类结果标签;τi表示对应的真实标签;map(wi)表示聚类标签的最佳重新分配函数,由Kuhn-Munkres算法[36]实现;σ(x,y)表示指示函数,若x=y,则σ(x,y)=1,否则,σ(x,y)=0。

标准化互信息(N)计算公式为

(10)

式中:P和T分别表示聚类结果标签和真实标签;I(P;T)表示P和T之间的互信息;H(P)和H(T)分别为P和T的信息熵。

3.2 对比算法

为了验证本文算法的有效性,选取11种优秀的聚类算法作为对比算法,具体情况如下。

(1)经典的单视角聚类算法。

BSV使用谱聚类算法分别在每个视角上做聚类,然后选取最佳聚类结果[25]。谱聚类算法是一种经典单视角聚类算法。

FeaCon将所有视角的数据简单拼接成一个向量,然后使用谱聚类算法对简单拼接表示做聚类[25]。

Co-Reg[37]是基于联合正则化的多视角谱聚类算法。

LRRbest[12]是使用LRR算法在每个视角上做聚类,然后选取最佳聚类结果。低秩表示约束有助于提高聚类算法的鲁棒性。

(2)传统的多视角聚类算法。

RMSC[2]是一种基于马尔可夫链的多视角谱聚类算法,具有低秩稀疏分解的特点,鲁棒性较好。

LMSC[21]从多视角数据中挖掘出互补信息以获得样本的隐表示,然后在隐表示的基础上对样本进行聚类。

CSMSC[22]在传统子空间聚类模型的基础上,同时考虑了视角间的一致性和视角本身的特异性,能够有效整合多视角信息,提升聚类效果。

(3)基于深度多视角子空间的聚类算法。

DMSC[23]是一种基于卷积神经网络的多视角子空间聚类算法,在深度自编码器中间加入自表达层来获取各视角下样本点的公共亲和自表达矩阵。DMSC通过深度卷积神经网络充分地挖掘了样本点之间的复杂关系,并且通过亲和融合的方法兼顾了各视有的互补性,可以获得更中合适的自表达关系矩阵。

AE2-Nets[24]将一个退化网络嵌套入自编码器模型中,实现了不同视角信息集成到一个完整表示中,更加充分地利用多了多视角数据的互补性。

DMSCNet[38]也是一种基于卷积神经网络的多视角子空间聚类算法,与DMSC[23]不同之处在于该算法分别计算每个视角下的深度自表达矩阵,然后通过范数约束等方法来计算公共自表达矩阵。

DMSC-UDL[39]利用自编码器将数据映射到非线性空间,通过约束多视角数据潜在特征和自表达系数,同时挖掘多视角数据的互补与一致信息,是一种最新的深度多视角子空间聚类算法。

3.3 参数设置

对于单视角算法,一律选取所有视角的最好聚类结果作为最终结果。对于多视角聚类算法的参数设置,本文采用网格法,在{0.01,0.1,1,10,100}中搜索最佳参数。为了公平地比较结果,基于深度学习的聚类算法都采用相同的自编码器结构、预训练方法和微调策略,都使用Adam优化器[40],参数设置为β1=0.9,β2=0.999。

所有深度聚类算法的训练都分为预训练和微调两个阶段。预训练阶段的学习率设置为0.001,微调阶段的学习率为0.001。

DLRMSC算法中包含了两个平衡参数λ1、λ2,最大秩约束m以及深度自编码器的网络结构。对于平衡参数λ1、λ2,采用网格法,在{0.01,0.1,1,10,100}中搜索。对于最大秩约束,假设每个子空间的维度是相同的,令K是数据集中簇的数量,那么m=m0K,其中m0是正整数,采用网格法在区间[1,16]中搜索每个数据集的最佳参数设置。深度自编码器的网络结构则借鉴了DLRSC算法[15]中的设置,所有模型的解码器和编码器的结构完全对称,都是3层卷积神经网络,对应的超参数也都相同。各数据集上的具体参数设置见表1～3。

表1 各数据集上的平衡参数和最大秩约束

表2 各数据集上人工神经网络的通道数

表3 各数据集上人工神经网络的卷积核尺寸

3.4 结果分析

每种算法在各数据集上分别进行15次实验,统计每次实验的指标。将每种算法在不同数据集上实验结果的平均值和标准差记录下来,作为对比依据。表4和表5分别给出了各算法在不同数据集上的正确率和标准化互信息,表中数据使用“平均值(标准差)”的形式。

分析表4和表5可以得到如下结论。

(1)单视角聚类算法中:LRRbest算法[12]的表现是最好的,在Yale数据集上的正确率为0.713,验证了低秩表示约束的确可以提高谱聚类的效果;基于谱聚类的简单拼接算法表现最差,在Yale数据集上的正确率只有0.593,说明简单拼接的方法不仅不能够有效利用多视角信息,甚至还对聚类效果起到负面作用。在传统多视角聚类算法中,兼顾视角间一致性和视角本身特异性的CSMSC算法[22]表现优于其他注重视角间一致性的算法,体现了各视角的特异性信息对于多视角聚类算法的重要性。

表4 各数据集上的标准化互信息

表5 各数据集上的正确率

(2)在整体上,深度多视角聚类算法表现最好,传统多视角聚类算法其次,体现了多视角聚类算法可以有效利用不同视角的互补性信息,发现更加准确聚类划分。与传统多视角算法相比,深度多视角算法可以通过非线性映射将原始数据投影到更加易于子空间聚类的隐空间中,适合处理存在非线性关系的多视角数据。

(3)本文提出的DLRMSC算法在各种类型的多视角数据集上明显优于其他的多视角算法,基本上都达到了最好或第二好的水平。在数据集3-sources上,本文算法的正确率比第二的DMSC-UCL[39]的高0.097,标准化互信息比第二的DMSC-UCL[39]的高0.103。更加值得注意的是,DLRMSC算法在各数据集上均优于DMSC算法[23],这说明本文提出的方法的确可以改进DMSC算法。与其他算法相比较,DLRMSC算法结合了3个优势:①借助深度模型强大的数据挖掘能力,可以处理样本点间复杂的非线性关系;②通过双层自表达模块的隐性低秩约束,可以有效降低噪声点对聚类结果影响;③将自表达模块分为一致性信息层和特异性信息层,可以充分利用多视角数据的一致性信息和互补性信息,从而提高算法性能。

3.5 特异性自表达层分析

为研究DLRMSC算法中特异性自表达层的作用,本文实现了DLRMSC-v1算法。与DLRMSC算法相比,DLRMSC-v1算法中所有视角的双层自表达模块相同,而其他模块保持一致。DLRMSC-v1算法的目标函数是式(5),可以被认为是没有特异性自表达层的DLRMSC算法。保持其他参数设置相同,在4个数据集上测试DLRMSC-v1的性能,与DLRMSC算法和DMSC算法[23]对比的结果如图2和图3所示。可以看出,DLRMSC-v1算法的性能强于DMSC算法[23]的,但是弱于DLRMSC算法的。这验证了DLRMSC算法的低秩表示约束和特异性自表达层都可以有效提高算法的聚类性能。

此外,从图2和图3中还可以观察出,在文本数据集3-sources上,DLRMSC算法的性能明显强于DLRMSC-v1算法的。本文分析认为,3sources数据集是由BBC、路透社、卫报这3家知名新闻网站围绕6个主题报导的169篇文章所组成的,不同的新闻网站往往具有不同的立场与叙事风格。因此,与其他多视角数据集相比,3-sources数据集的各视角信息具有更强的互补性。与DLRMSC-v1算法相比,DLRMSC算法的特异性自表达层可以较好地利用多视角数据的互补性,所以在3-sources数据集上的效果有了明显的提升。

图2 特异性表达层对正确率的影响Fig.2 Clustering accuracy comparison of three methods

图3 特异性自表达层对于标准化互信息的影响Fig.3 Clustering NMI comparison of three methods

3.6 参数敏感性分析

为测试DLRMSC算法中关键参数最大秩约束的敏感性,在数据集Caltech-101[35]上测试了不同m0(m=m0K)取值下的准确率和标准化互信息,结果如图4所示。可以看出,当m0的取值在区间[2,12]内时,DLRMSC算法可以保持一个比较好的效果,正确率在0.69到0.74之间波动。这验证了本文算法处理多视角低秩子空间聚类问题的良好性能。

图4 Caltech-101数据集最大秩约束对算法性能的影响Fig.4 Changes of A an N with m0 on dataset Caltech-101

3.7 收敛性分析

在数据集Caltech-101[35]上,DLRMSC算法微调阶段每次迭代后的正确率和标准化互信息如图5所示。可以看出:随着迭代次数的增加,正确率和标准化互信息都在逐步上升;经过1 200次迭代后,算法逐步收敛,最终正确率保持在0.74左右,标准化互信息保持在0.62左右。

图5 数据集Caltech-101上的算法收敛性分析Fig.5 Convergence analysis on dataset Caltech-101

4 结 论

本文在DMSC算法[23]的基础上提出了一种新的深度低秩多视角子空间聚类算法DLRMSC。DLRMSC算法中的双层自表达模块能够得到具有低秩表示约束的自表达矩阵,获得更加鲁棒的聚类结果。基于深度模型的优势,DLRMSC算法具有很好的数据关系挖掘能力。通过将双层自表达模块划分为一致性自表达层和特异性自表达层,DLRMSC算法能够获取多视角数据的一致性信息和每个视角的特异性信息,更充分地利用多视角数据的互补性。

DLRMSC算法可以看作深度多视角子空间聚类算法DMSC[23]的改进版本。与DMSC算法[23]相比,DLRMSC算法的鲁棒性更强,并且可以更有效利用多视角数据的互补性。实验表明,DLRMSC算法所引入的双层自表达模块具有很好的鲁棒性以及捕捉多视角数据互补性的能力。

在未来工作中,将考虑如何更加具体地分析不同视角之间的关系和每个视角对于聚类的贡献程度,以获得更好的信息融合能力,更加充分地利用多视角数据的互补性。另外,在大数据背景下,如何使深度多视角子空间聚类算法适应海量数据的聚类任务,也将是下一步研究的重点。