基于多视角自适应图正则的非负矩阵分解聚类

林虹燕, 杜元花, 周 楠, 田永强

(1.成都信息工程大学应用数学学院,四川 成都 610225;2. 成都大学电子信息与电气工程学院,四川 成都 610106;3.华为科技有限公司,云南 昆明 650011)

0 引言

多视角学习在近年成为机器学习的热门话题之一,在图像处理、卫星通信、模式识别等领域有广泛应用。 多视角学习能够整合多视角数据的互补性和异构性,并将其重构为一个共识表达,在越来越多的领域受到欢迎。

随着多视角数据在实际应用中的日益增多,提出了多种多视角聚类方法[1-4]。 Nie 等[5]通过探索拉普拉斯秩约束图来构建多视角聚类,可近似地为每个具有不同置信度的视角构建共识亲和图。 Zhan 等[6]提出一种多视图一致性聚类方法,通过学习一致性图,直接获得聚类标签,并且无需进行任何后处理。 Wen等[7]提出一种简单有效的不完备多视角聚类框架,该框架同时考虑了这些不完备多视角观测的局部几何信息并具备不平衡的判别能力。 Luo 等[8]提出一种多视角双聚类方法,该方法在统一的框架中同时探索共识表达和双聚类结构。 Liu 等[9]提出一种基于潜在表示空间近邻学习的新型多视角聚类方法。 其中,多视角非负矩阵分解通过对多个视角数据进行矩阵分解达到原数据矩阵的低秩逼近,从而可以发现每个视角的内在结构表达成一个基,并将互补信息融合成一个低维空间的共识表达。 上述大多数方法只重视原始空间数据的一致性,忽略了各个视角的独特性,得不到满意的数据表达。 同时,低维空间的数据表达跟聚类结果也有很强的联系,共识表达可以展现数据的内在结构,另一个矩阵则为低维空间的系数表达矩阵。 因此,在数据表达的同时可以对数据进行聚类。 最后,通过对拉普拉斯图进行秩约(constraint Laplacian rank,CLR)[10]来构造多视角图,该多视角图能很好地学习到数据内在结构。 受到该思想的启发,本文提出一种多视角自适应图非负矩阵分解(multi-view adaptive graph nonnegative matrix factorization, MAGNMF)的聚类方法。该方将多个视角共识图嵌入框架[11]与非负矩阵分解特征学习相结合,不仅考虑了多视角数据的全局重构信息,也考虑了多视角的局部结构信息,以此达到数据表达和聚类的效果。 本文主要贡献如下:

(1)提出了一种结合非负矩阵分解、CLR 和图嵌入的多视角特征学习聚类方法,使低维表达既能保持高维数据的内在局部结构信息,也能提取出多个视角的全局重构信息;

(2)提出了一个基于快速块坐标更新(block coordinate update, BCU)[12]迭代更新算法来求解所提出的优化模型;

(3)通过在4 个真实数据集上进行大量验证,结果表明本文所提出的多视角数据表达聚类方法MAGNMF 在多数情况下优于现有的方法。

1 相关工作

1.1 符号

本文用到的符号如表1 所示。

表1 符号

1.2 拉普拉斯秩约束算法

现有的多视角聚类方法多基于多图聚类,如协同训练[13],多视角谱聚类[14]等。 这些方法都是在固定输入的数据图上进行聚类,如果输入的图质量较差,则聚类结果也较差,其次需要进行后处理才能完成聚类。拉普拉斯秩约束定理通过限制拉普拉斯矩阵秩的个数(n-k)来约束数据的相似图的连通分量个数(k),给定亲和矩阵A,寻找相似矩阵S。 通过数据的原始亲和矩阵A,可以学习到相似矩阵S以及相应的拉普拉斯矩阵L=D-(ST+S)/2,它的秩为n-k,其中对角矩阵D的第i个元素为Σj(sij+sji)/2。 在这个限制之下,学习到的S是有合适排列的块对角矩阵,这样就可以直接将数据点划分到k簇。 其模型表示为

1.3 图正则化的非负矩阵分解算法

现实中的数据基本都是高维的,非负矩阵分解(nonnegative matrix factorization, NMF)[15]是将高维空间的数据矩阵近似表达成两个低维矩阵,U是基矩阵,F是低维表达矩阵。X是数据矩阵,其中X每一列表示一个样本点,每一行表示一个特征。

为了寻找一个高质量的近似,可以将NMF 的目标函数变成以下优化问题:

这样NMF 就可以学到局部表达。 为更好地学习数据空间的内部几何和判别结构,同时维持高维数据在低维空间的流型结构,避免过拟合,加入了图正则项。 于是,图正则化的非负矩阵分解[16]模型表示如下:

其中U≥0,F≥0 表示矩阵U与F中所有元素都是非负的,正则项参数λ≥0,用于控制低维表达对于高维数据局部结构的保持性,L=D-(ST+S)/2 为图拉普拉斯矩阵,其中S为数据矩阵的相似矩阵。 将图正则项与原始非负矩阵分解结合被称为图正则化非的负矩阵分解。

2 自适应图正则的非负矩阵分解

本文提出一种新的多视角自适应图非负矩阵分解模型。 根据拉普拉斯秩约束需要找到共识的拉普拉斯约束图,该图可以近似地作为每个视角的相似度图的质心。 图非负矩阵分解将数据从嵌入的高维环境空间中的低维流形中采样,得到在低维空间的表达。 本文模型还加入了惩罚项以防止平凡解的出现。

给定一个多视角数据集X= [X(1),X(2),…,X(m)],本文模型目标是找到共识相似矩阵S,共识低维表达矩阵F和每个视角的基矩阵U(v)。 因此,目标函数被表示成:

这里,λ>0 是CLR 和图正则项的平衡系数。 限制S、F、U(v)为非负矩阵,且S与F的每一行和为1,有效地避免了平凡解和减小计算复杂度。 最后,将K-means算法[17]应用到共低维表达矩阵,得到聚类结果。

3 求解算法

3.1 加速BCU 迭代方法

本文采用加速BCU 策略来推导模型(5)的求解算法。 在每次迭代中,更新目标函数的一个变量,将其他两个变量固定在其最近更新的值。 具体来说,每个变量通过迭代地执行以下的表达式来进行更新。

其中和分别是∇Sf(·)和∇Ff(·)的利普希茨(Lipchitz)常数,并且插值点

这里,∊[0,1)分别为插值点和的权重,文献[18-19]认为,通过该插值的办法可以明显提高BCU的求解效率。

3.2 更新S

消除式(5)中与S无关的项,式(6)可以被重新表示为

式(13)按照列可以分解为n个相互独立的子问题:

如此,这个问题就变成了单纯形上的投影。 根据文献[20]中的方法可以将式(14)很好地求解,其求解方法如下。

算法1 单纯形上的投影:s=Proj-Sim(c)

第1 步 按上升顺序排列c形如c(1)≤…≤c(p),令i=p-1;

第4 步 将c的投影s=(c-)+投到Δp上。

3.3 更新F

与S子问题求解方法类似,令D=∇Ff(Sk+1,,(U(v))k)且L2=,于是式(7)可以表示成

消除式(5)中与F无关的项,式(7)可以被重新表示为

最后,式(7)等价于:

式(17)也可以通过算法1 来求解。

3.4 更新U(v)

由于式(8)具有闭形式解,且在每个视角中都是独立的,因此可以将这个问题的每个视角分开处理。先求出关于U(v)式子的梯度,去除目标函数式(5)中与U(v)无关的项,得到:

(i)令f1=‖X(v)-U(v)FT‖2F

=Tr((X(v)-U(v)FT)T(X(v)-U(v)FT))

=Tr((X(v))TX(v)-(X(v))TU(v)FT

F(U(v))TX(v)+F(U(v))TU(v)FT)

=Tr((X(v))TX(v)-2 (X(v))TU(v)FT+

F(U(v))TU(v)FT)

那么可以得到

结合(i)和(ii)得到

令梯度为零,于是得到

得到

因此U(v)的封闭解为

3.5 参数设置

算法共有5 个参数:输入平滑参数λ∊[10-3,103],以及前文提到的更新变量S和F以更新相应的利普希茨(Lipchitz)常数和和权重和。

3.5.1 推导

去除目标函数式(5)中与S无关的项,得到

其中fi是F的第i行。

(iii)令fv=‖S-A(v)‖2F=Tr((S-A(v))T(S-A(v)))

=Tr(STS-2STA(v)+(A(v))TA(v))

(iv)令Hij=‖fi-fj‖22,hi、si分别是H和S的第i行。

则任何和有

因此,Lipschitz 常数为

定义

3.5.2 推导

去除目标函数式(5)中与F无关的项,得到:

(v)令:f1=‖X(v)-U(v)FT‖2F

=Tr((X(v)-U(v)FT)T(X(v)-U(v)FT))

=Tr((X(v))TX(v)-(X(v))TU(v)FT

F(U(v))TX(v)+F(U(v))TU(v)FT)

=Tr((X(v))TX(v)-2 (X(v))TU(v)FT+

F(U(v))TU(v)FT)

那么可以得到

结合(v)和(vi)得到

则任何和有

因此,Lipschitz 常数为

定义

3.5.3 推导权重及

根据文献[12]提到的办法,定义插值权重如下:

这里δw<1,= (τt-1-1)/τt且

结合3.1 ～3.5,整体求解模型式(5)的算法如下:

算法2 多视角自适应图非负矩阵分解(MAGNMF)

输入:亲和矩阵A={A(1),A(2),…,A(m)}∊Rn×n,多视角非负矩阵

X={X(1),X(2),…,X(m)}∊Rd×n,参数λ

输出:共识相似矩阵S∊Rn×n、每个视角的基矩阵

U(v)={U(1),U(2),…,U(m)}∊Rd×c以及共识系数矩阵F∊Rn×c;

步骤1 通过式(17) ～(20)计算、、和;

步骤2 令=Sk+(Sk-Sk-1);

步骤3 令=Fk+(Fk-Fk-1);

步骤4 利用算法1 求解式(11)更新Sk+1;

步骤5 利用算法1 求解式(13)更新Fk+1;

步骤6 通过式(16)更新(U(v))k+1;

步骤7 如果f(Sk+1,Fk+1,(U(v))k+1)≤f(Sk,Fk,(U(v))k),令=Sk,=Fk回到步骤(4);

步骤8 令k←k+1;

步骤9 重复步骤(1) ～(8)直至收敛。

3.6 收敛性分析

定理1算法2 的迭代更新策略可使式(5)中的目标函数值单调递减,并收敛到最小值点。

为简单起见,假设=0、=0,即不进行外推。=0、=0 的情况较复杂,但可以按文献[12]类似地处理。

根据式(5),令

s.t.S≥0,si1n=1,F≥0,fi1n=1,U≥0 于是φ(S,F,U(v))≥0,因此函数目标值下界为0。 根据算法2 的更新策略,由文献[15]可得:

同理可得:

于是

目标值的单调递减。 又由于目标函数存在下界,于是算法2 的更新策略收敛到一个极小值点。

通过算法2 的更新规则,可使目标函数单调递减并收敛到一个极小值点,完成证明。

图1 展示了MAGNMF 算法在ORL 数据集上,不同迭代次数下的目标函数值。 由图1 可知,随着迭代次数的增加,目标函数值呈单调递减趋势,并最终达到收敛。

图1 收敛曲线

4 实验

将MAGNMF 算法与目前先进的算法在聚类效果上进行比较。 为保证算法比较的公平性,对于需要k近邻构建亲和矩阵的算法,统一将近邻数k设置为5,运行算法得到的低维表达之后,再使用K-means 算法进行聚类得到聚类结果,其中K-means 算法直接得到结果。 全部的算法都在MATLAB R2018b 上进行。

4.1 数据集

实验用到4 个数据集,其中包含1 个文本数据集和3 个图像数据集。

BBC:该数据来源于BBC 新闻网页,由685 个文件构成,每个文档被分成4 个部分(4 个视角),包含5个类别的主题标签。

COIL20:该数据集的图片含有20 个类别,共有1440 张,这些图片为32×32 的灰度照片并从3 个不同的角度描述了样本。

Digit:该数据集由2000 张手写数字图片(0 ～9)组成,视角1 是76 个傅里叶系数,视角2 是240 像素的像素特征。

ORL:该数据集共400 张人脸图片,由40 个不同人的人脸图片构成,每个人有10 张图片,每张图片由4 个不同的特征描述。

4 个数据集的主要信息如表2 所示,其中di表示第i个视角数据的维度。

表2 数据集的主要信息统计

4.2 对比方法

选取8 种聚类算法来对比本文所提出的多视角聚类算法,各聚类算法如下。

K 均值聚类(K-means):通过迭代更新,将数据点分给相应的聚类中心。

共正则谱聚类(coregSC)[21]:在谱聚类框架下,通过共同规范聚类假设,使所有视角一致,最终得到聚类结果。

非负矩阵分解(NMF):通过基矩阵和系数矩阵近似表达原数据,得到低维空间的表达。

基于非负矩阵分解的多视角聚类(multiview nonnegative matrix factorization, MultiNMF)[21]:跨多个视角的NMF。

基于图正则项的多视角聚类(graph nonnegative matrix factorization, GMNMF)[22]:通过有局部图正则项的多视角NMF 进行特征提取,考虑了数据之间内部视图的相关性。

自加权多视图学习(auto-weighted multiple graph learning,AMGL)[23]:模型没有额外的参数,能够自动学习每个视图的最优权值。

多图自加权多视角聚类(self-weighted multiview clustering,SwMC)[24]:通过融合不同的权重图来构造相似图,然后利用相似图构造一个具有明确块对角结构的拉普拉斯图。

基于一致相似度矩阵的图非负矩阵分解(similarity graph nonnegative matrix factorization, SGNMF)[25]:通过多图自加权多视角聚类学习相似度矩阵,来构造拉普拉斯图正则项,最后将该正则项加入原始的非负矩阵分解模型中。

4.3 评价指标

采用精确度(ACC)[26]和归一化互信息(NMI)[26]两种指标来度量聚类性能。 指标数值越大,聚类性能越好,4 个真实数据集和ORL 数据集的不同视角组合的ACC 和NMI 如表3 ～5 所示,其中加粗的数值为最高数值,加下划线的数值为次高数值。

表3 4 个数据集的ACC 实验结果

4.4 多视角聚类实验

将本文所提出的MAGNMF 算法和其他8 种对比算法在4 个真实数据集下的聚类效果(ACC、NMI)总结在表3 和表4。 通过观察和对比实验结果,得到如下结论:

表4 4 个数据集的NMI 实验结果

K-means 和NMF 表现的效果不是很好,SwMC、MultiNMF、GMNMF、coregSC、AMGL 以及SCGNMF 等算法的效果不相上下,本文的MAGNMF 算法效果在大多数情况下优于所比较的其他算法。

在BBC、COIL20 和ORL 等数据集上,MAGNMF 算法对比其他算法效果有较大提升。 特别是在BBC 数据集上,对比排第二的算法,MAGNMF 在ACC 度量下提高了16.04%,在NMI 度量下提高了31.73%。 在ORL 数据集中,对比排第二的算法,MAGNMF 在ACC度量下提高了8.37%,在NMI 度量下提高了2.93%。

在Digit 数据集的实验中,MAGNMF 方法在ACC度量下取得了第二好的聚类结果,仅与最好的方法差1.45%,在NMI 度量下取得了最高的聚类结果,优于第二好的结果1.32%。

从实验结果来看,本文的算法效果相对于其他的算法在聚类上有一定的优越性,说明拉普拉斯秩约束的共识相似度矩阵学习和图正则化的非负矩阵的结合,使MAGNMF 方法可以让原始空间的数据在低维空间中更好地保持原始数据的全局重构信息与局部结构信息,使低维表达更具有判别性,从而提升样本的聚类精度。

4.5 多视角聚类有效性验证

为验证本文所提出的MAGNMF 算法在多视角聚类问题的有效性,在ORL 数据集的不同视角组合上进行实验,表5 展示了不同视角组合下,采用MAGNMF算法在ACC 和NMI 度量下的聚类结果。 实验结果表明,完整的多视角数据集比单视角或者不完整视角数据集的聚类性能更好。

表5 ORL 数据集各视角在本方法的实验结果

4.6 参数敏感性分析

算法中的λ是拉普拉斯秩算法和图正则项的参数,它是促进所有视角一致性和权衡这两部分的平滑度。 为使实验具有公平性,将对比算法中所有实验计算亲和矩阵的近邻值设置为K=5。 参数λ在集合{0.001,0.05,0.01,0.5,1,5,10,50,100,500,1000}中变动。 图2 和图3 中的4 条折线分别表示了4 个数据集在不同λ数值时对应ACC 和NMI 度量下的聚类结果。 由此可知,在4 个数据集上,聚类结果对于参数λ的变化并不敏感。

5 结束语

提出了一种新的基于多视角图自适应非负矩阵分解(MAGNMF)方法来处理多视角数据的聚类问题。该方法的优点包括3 个方面:(1)利用CLR 和图嵌入的结合,同时考虑了所有数据的一致性和每个视角之间的互补性,达到数据表达和聚类的效果;(2)该方法有且仅有一个参数需要调优;(3)一个有效的BCU 迭代更新算法被提出。 通过4 个现实数据集的实验,结果表明,本文所提出的MAGNMF 方法在大部分情况下都优于目前的方法。