基于图形正则化低秩表示张量与亲和矩阵的多视图聚类

2022-07-07程学军王建平

吉林大学学报（理学版） 2022年3期

程学军, 王建平

(1. 河南工业大学漯河工学院, 河南漯河 462000; 2. 河南科技学院信息工程学院, 河南新乡 453003)

子空间聚类由于其高效性在模式识别和机器学习领域得到广泛关注[1]. 由于每个视图通常都描述原始对象或数据的部分知识, 因此多视图聚类方法比单视图聚类方法更能挖掘数据的潜在信息, 从而聚类效果更好[2]. 多视图聚类算法(multiple view clustering, MVC)目前已有许多研究成果, 如多视图k-means聚类、共正则化MVC、基于规范化相关分析的聚类以及基于低秩表示MVC[3-6]等. 上述方法首先都使用不同的子空间学习方法学习表示矩阵或张量; 然后通过对所有表示矩阵求平均构造属性矩阵, 其中亲和矩阵旨在测量两个数据点之间的相似性；最后使用具有亲和矩阵的谱聚类算法获得聚类结果. 聚类的核心是构造一个信息亲和矩阵, 但该矩阵的构造依赖于先验知识. 因此, 很多研究都集中在如何直接学习一个设计良好的表示矩阵或张量构造亲和力矩阵. 如夏菁等[7]提出了学习低秩稀疏表示矩阵; 李杏峰等[8]使用完整的空间学习技术学习信息完整性感知表示矩阵; 于茜茜[9]提出了一种结构化的多视点子空间聚类方法学习表示矩阵. 尽管上述基于低秩矩阵或张量表示的MVC方法已取得了较好的性能, 但其仍存在以下局限性： 1) 这些方法常忽略局部结构, 即仅考虑表示矩阵或张量的全局低秩性, 在学习过程中忽略了样本的局部性和相似性信息; 2) 分别学习低秩表示和亲和矩阵, 忽略了两者之间的高度依赖性.

为解决上述问题, 本文提出一种基于图形正则化低秩表示张量与亲和矩阵的多视图聚类算法(multi view clustering algorithm based on graph regularized low rank representation tensor and affinity matrix, GRLRTAM-MVC), 该算法不仅可以同时学习低秩表示张量和亲和矩阵, 而且可以将局部结构统一集成, 有效增强信息挖掘的深度, 提升聚类性能. 在7个数据集上的实验结果证明了该方法的有效性.

1 预备知识

参考文献[8], 设χ,X,x分别表示张量、矩阵和向量.在N1×N2×N3中,χ和y的内积定义为〈χ,y〉=vec(χ)Tvec(y)T,χ的Frobenius范数定义为表示将矩阵X的所有列堆叠为一个向量.χ的L1范数表示为‖χ‖1=‖vec(χ)‖1,χ的无穷范数表示为张量χ的第k个切片表示为χ(k).沿χ的方向进行快速Fouier变换(FFT), 表示为同理, 可通过逆FFT由得到χ, 即对于张量χ∈N1×N2×N3, 其分块循环矩阵bcirc(χ)和块对角矩阵bdiag(χ)定义为

(1)

(2)

块矢量化定义为bvec(χ)=(χ(1),…,χ(N3)), bvec和bdiag的逆运算分别定义为bvfold(bvec(χ))=χ, bdfold(bdiag(χ))=χ.令y∈N2×N4×N3,t-productχ×y是N1×N4×N3张量,χ×y=bvfold(bcirc(χ)×bvec(y)).χ的转置为χT∈N2×N1×N3, 是通过将每个切片进行转置, 然后将转置后的切片通过N3将顺序颠倒.单位张量L∈N1×N1×N3是一个第一个切片为N1×N1的单位矩阵张量, 其余切片为零.如果满足条件χTχ=χχT=L, 则张量χ∈N1×N1×N3是正交的.

定义1(t-SVD) 对于χ∈N1×N2×N3, 其t-SVD为χ=u×s×vT, 其中u∈N1×N1×N3,v∈N2×N2×N3, 二者是正交向量,s∈N1×N2×N3是f的对角张量, 其每个切片都是对角矩阵.三阶张量的t-SVD如图1所示.t-SVD可通过Fourier域中的矩阵SVD进行计算.

图1 三阶张量的t-SVDFig.1 t-SVD of third-order tensor

定义2(张量多秩) 张量χ∈N1×N2×N3的张量多秩是向量r∈N3×1, 其第i个元素是的第i个切片的秩.

定义3(t-SVD-TNN) 张量χ∈N1×N2×N3的t-SVD-TNN表示为‖χ‖⊗, 定义为所有切片的奇异值之和, 即

(3)

2 算法设计

2.1 聚类算法

根据自表示特性, 其他点的线性组合可用第v个视图中的每个数据点表示, 即

X(v)=X(v)Z(v)+E(v),

其中E(v)表示噪声.显然, 由X(v)得到表示矩阵Z(v)和噪声E(v), 适用性较差.因此引入低秩张量, 近似研究多视图之间的高阶关联性.

(4)

(5)

其中‖·‖2,1是l2,1范数, 用于去除特定样本的损失；E=(E(1),E(2),…,E(V)); 利用Φ(·)将所有表示矩阵Z(V)合并, 构造一个3阶表示张量Z(V)∈n×n×V; 正则化ψ(Z)描述了Z的低秩性质;S为最终要学习的相似矩阵;λ1,λ2,λ3和γ为非负参数；ω=(ω1,ω2,…,ωV)为权重向量,ωv是第v个视图的相对权重.由式(5)可知, 可以在同一个框架内同时训练学习低秩表示张量Z和相似矩阵S, 从而得到一个相似矩阵作为谱聚类算法的输入, 进而得到聚类结果.式(5)中的第一项描述了表示张量Z的低秩性; 第二项可以模拟特定样本的损失；使用流形正则化, 即式(5)中的第三项, 可保持多视图数据的局部结构, 使在原始空间中距离近的数据点仍具有相似的表示；式(5)中的最后一项对不同的视图施加不同的权重, 以获得信息丰富的相似矩阵.为克服权重分配的困难, 式(5)可通过约束二次规划方法, 对不同特征进行自适应权重分配.

文献[10]研究表明,t-SVD-TNN在计算机视觉中的性能优于其他张量分解形式, 包括CANDECOMP/PARAFAC分解和Tucker分解. 受此启发, 本文利用t-SVD-TNN对Z的低秩张量性质进行编码.

2.2 GRLRTAM的优化

利用式(3)中t-SVD-TNN的定义, 即ψ(Z)=‖Z‖⊗, 式(5)中的模型可表示为

(6)

由于在Z上同时施加了全局低秩性和局部结构优先性, 所以式(6)与Z相耦合, 为使Z可分解, 引入变量分裂技术, 并引入一个辅助张量变量y, 则式(6)可转化为以下优化问题：

(7)

式(7)对应的增广Lagrange函数为

其中Θ(v)∈dv×π和Π∈π×π×V分别是关于两个等式约束的Lagrange乘子;ρ>0是惩罚参数.式(8)可分为下列6个子问题.

1) 更新y.给定上述迭代中的其他变量, 可通过解决以下问题更新y：

式(9)可分为V个独立的极小化问题, 第v个极小化问题为

(10)

式中

将式(10)对Y(v)求导, 并令导数为零, 可得Sylvester方程

MY(v)+Y(v)N=C,

其中

2) 更新Z.修正其他变量,Z可更新为

(11)

式(11)的闭合形式解为

Zt+1=Cv/ρ(Ft)=uCv/ρ(S)VT,

(12)

算法1基于t-SVD更新Z.

输入：张量Ft∈n×V×v；参数

Ft=fft(χ,[ ],3)；

fork=1到k=ndo

Σ(k)=S(k)J(k)；

end for

输出：张量Zt+1.

3) 更新E.最小化式(8)中E的增广Lagrange函数, 可得

(13)

其中

Et+1的第j列可表示为

(14)

4) 更新S.为得到St+1的最优解, 将式(8)中关于S的增广Lagrange函数最小化为

(15)

关于式(15)对S的导数, 其闭式解St+1为

(16)

5) 更新ω.将ω的优化问题转化为

(17)

(18)

6) 更新Θ(v),Π,ρ.Lagrange乘子Θ(v),Π和惩罚参数ρ可更新表示为

(19)

其中β>1是为加快收敛速度,ρmax是惩罚参数ρ的最大值.下列算法给出了求解式(7)的过程, 其中停止循环条件定义为

(20)

算法2GRLRTAM多视图子空间聚类算法.

输入：多视图特征X(v)；参数λ1,λ2,λ3,γ=10；最近邻域个数为5；图像Laplace矩阵L(v)；簇的个数为K；

While不收敛do

forv=1到Vdo

end for

根据算法1更新Zt+1;

根据式(14)更新Et+1;

根据式(16)更新St+1;

根据式(18)更新ωt+1;

检查式(20)的收敛条件;

end while.

输出：相似矩阵St+1.

2.3 计算复杂度

算法2的计算量主要通过更新y,Z,E决定, 求解Sylvester方程的计算量为O(n3), 更新Z的计算量为O(2Vn2log(n)), 通过更新Z计算三维Fourier变换和逆Fourier变换, 并用计算量为O(V2n2)对V个n×V矩阵执行SVD, 其他更新的计算量为O(Vn2).其余计算步骤的计算成本可忽略不计, 因为其只包含基本运算, 如矩阵加法、减法和乘法.因此, 算法2的计算复杂度为

O(T(Vn3+2Vn2log(n)+V2n2)),

其中T是迭代次数.

3 实验

下面实验评估GRLRTMA在7个具有代表性的多视图数据集上的性能.

3.1 数据集

BBC4view数据集和BBCSport数据集: BBC4view和BBCSport数据集主要包括新闻报道数据, 其包含了来自英国广播公司(BBC)体育网站的685份和544份关于体育新闻的5个主题文件, 对于每个文件, 提取BBC4view中4种不同类型的特征, 提取BBCSport中2种不同类型的特征.

3个新闻数据集：该数据集的内容是新闻故事, 来自3个在线新闻, 其包含6类416个不同的新闻故事, 这3个数据集共包含了169篇新闻, 每个数据集都有各自的观点.

MSRC-V1数据集：包含树、建筑、飞机、奶牛、人脸、汽车、自行车等7类210张图像, 本文提取了5个视图特征, 包括24维颜色矩、 576维定向梯度直方图(HOG)、 512维 GIST、 254维中心特征和256维局部二值模式(LBP). Scene-15数据集：包含15类4 485张室外和室内场景图像, 本文提取了1 800维光照、 1 180维PRI-CoLBP和1 240维中心点3种图像特征表示Scene-15. MITIndoor-67数据集：包含1.5万张室内图片, 涵盖67个不同类别, 本文选取一个包含5 360张图像的子集进行训练聚类. COIL-20数据集：有20个类别和1 440张像素大小为32×32的通用对象图像, 此外还提取了1 024维强度、 3 304维LBP和6 750维Gabor三种视图特征. 表1列出了这些数据集的统计特征.

表1 7个代表性多视图数据集的统计特征

3.2 不同方法的对比分析

将GRLRTMA与目前最新的方法进行比较, 包括SSCbest[3]：通过L1范数正则化表示矩阵构造的单视图聚类； LRRbest[4]：通过核范数正则化表示矩阵构造的单视图聚类； RSSbest[5]: 通过同时学习数据表示和相似性矩阵实现单视图聚类; MLAP[8]: 通过连接不同视图的子空间表示并施加低秩约束探索具有互补性的MVC； DiMSC[9]：具有Hilbert-Schmidt独立性的MVC； LT-MSC[11]：具有低秩张量约束的MVC； MVCC[12]：基于局部流形正则化分散式概念的MVC； ECMSC[13]：具有一致排外性的正则化MVC； MLAN[14]：具有自适应邻域的MVC；t-SVD MSC[15]：张量多秩极小化的MVC； MLRSSC[16]：基于低秩稀疏子空间聚类的MVC； MSC_IAS[17]：具有完整感知相似性的MVC. 其中前3种方法属于单视图聚类方法, 其他方法属于多视图聚类方法. 上述方法均按其实验参数值进行设置, 以便进行公平的比较. 此外, 在MITIndoor-67数据集上加入了深度特征, 并将GRLRTMA与GSNMF-CNN[18]进行比较. 对于SSCbest,LRRbest和RSSbest, 每个特征独立使用, 并展示最佳聚类结果. 为进行全面比较, 使用由所有特征联合在一起的联合视图进行了SSC,LRR和RSS, 其分别表示为SSCCon,LRRCon和RSSCon. 由于MLAN中存在一个随机参数, 将MLAN执行10次, 并展现其最佳的聚类结果. 对于DiMSC,LT-MSC,t-SVD-MSC,MLRSSC和MSC-IAS, 它们都首先学习表示矩阵或张量, 然后构造相似性矩阵. 文献[17]使用Tucker分解对低秩性进行编码, 用GLTA_Tucker表示. 对于除MLAN外的所有方法, 均使用谱聚类算法计算聚类结果.

根据文献[15], 本文利用6种常用的聚类指标, 即准确度(ACC)、归一化互信息(NMI)、调整后的秩指数(AR)、F-score、精确度和召回率评估聚类性能. 通常这6个指标值越高, 聚类效果越好. 由于所有方法的谱聚类都是基于k均值的, 不同的初始化设置可能会产生不同结果, 因此本文对每个实验均进行10次试验, 并计算其平均性能和标准差.

3.3 聚类效果比较

表2～表8分别列出了7个数据集的所有聚类结果. 由表2～表8可见, 多数情况下, GRLRTMA的性能优于其他方法, 尤其是在BBC4view,Scene-15,MITIndoor-67和COIL-20数据集上.t-SVD-NN的GRLRTMA在所有情况下都优于GLTA-Tucker, 表明基于奇异值分解的张量核范数可能比Tucker分解更适合于表示张量的低秩性. 在Scene-15数据集上, 相对于次优方法t-SVD-MSC, 对于6个指标, 本文GRLRTMA的精度分别提高16.7%,11.6%,19.6%,18.1%,22.7%和12.9%, 而在MITIndoor-67数据集上, GRLRTMA的精度分别提高23.8%,22.3%,36.1%,35.6%,34.9%和36.3%. 这主要是因为DiMSC,LT-MSC,t-SVD-MSC-MLRSSC和MSC_IAS分两步构造表示矩阵或张量相似性矩阵, 并未考虑不同特征的不同贡献度. 但GRLRTMA同时学习表示张量和相似性矩阵, 很好地利用了它们之间的高度依赖性, 且其良好性能还得益于局部几何结构的保留.

表2 数据集BBC4view的聚类结果(平均值±标准差)

表3 基于BBCSport数据集的聚类结果(平均值±标准差)

表4 基于3Sources数据集的聚类结果(平均值±标准差)

表5 基于MSRC-V1数据集的聚类结果(平均值±标准差)

表6 基于COIL-20数据集的聚类结果(平均值±标准差)

续表6

表7 基于Scene-15数据集的聚类结果(平均值±标准差)

表8 基于MITIndoor-67数据集的聚类结果(平均值±标准差)

通常多视图聚类方法比单视图聚类方法SSCbest,LRRbest和RSSbest具有更好的聚类性能. 这主要是因为单视图聚类方法关注特定的视图特征, 而多视图聚类方法能很好地捕捉到多视图之间的高阶交叉信息； LT-MSC在前两个数据集上的结果不理想, 可能是因为基于展开的张量核范数是Tucker阶数的稀疏替代. 此外,t-SVD-MSC的性能比LT-MSC更好, 主要是因为t-SVD-TNN比基于展开的张量核范数能更好地揭示表示张量的整体结构； MLAN在BBCSport和Scene-15数据集上的性能比3种单视图聚类方法差, 主要是因为可能由MLAN得到的相似性矩阵是直接从含有噪声和离群值的原始数据中学习得到的；基于低秩矩阵的多视图子空间聚类方法MLRSSC和MSC_IAS性能不稳定, 例如, 在BBC4view,BBCSport和COIL-20数据集上, 其性能优于其他方法, 但在MITIndoor-67数据集上的性能却比SSC和LRR差. 实验结果表明, 同步学习表示张量和相似性矩阵有助于提高聚类性能.

3.4 性能分析

3.4.1 参数选择

本文将所有实验的最近邻域个数设为5,γ=10. 将GRLRTMA中的3个自由参数λ1,λ2,λ3进行微调, 即分别从集合{0.001,0.005,0.01,0.05,0.1,0.2,0.4,0.5}, {0.001,0.005,0.01,0.05,0.1,0.2,0.4,0.5,1,2,5,10,50,100,500}, {0.01,0.1,0.5,1,3,5,7,10,50 100}中取值.本文仅给出BBCSport和MSRC-V1数据集中不同组合λ1,λ2,λ3的GRLRTMA的ACC值. 由于误差项对目标函数的影响可能较小, 因此首先将λ1固定为相对较小的常数, 然后将λ2和λ3设为不同值, 结果如图2所示. 由图2可见, GRLRTMA和参数λ2,λ3的关联度较小.最后, 确定λ2和λ3参数值, 并考察λ1对模型性能的影响.当λ1较小时, GRLRTMA得到的结果较好. 因此, 与GRLRTMA的相关参数λ1,λ2,λ3可分别从区间[0.005,0.2],[0.05,0.2],[0.01,1]中取值.

图2 不同参数值的ACC值Fig.2 ACC values of different parameter values

3.4.2 收敛性分析

推导GRLRTMA的收敛性有一定困难. 因此本文分析了如图2(A)所示的2个数据集的经验收敛性, 其中纵轴表示

的误差. 经过15次迭代后, 产生一个稳定的误差值, 表明GRLRTMA可以在有限次数迭代后收敛. 如图2(B)所示, 给出了每次迭代的ACC和NMI值, 因为这两个指标在一定程度上反映了聚类性能. 由图2(B)可见, 当迭代次数增加时, ACC和NMI值也增加, 直到逼近最优值. 从而证明了GRLRTMA在以上真实数据上的收敛性.

3.4.3 特征权重

表9列出了SSC和LRR对每个视图特征的聚类结果. 由表9可见, 对于同一个数据集, 不同特征可能会产生不同的聚类结果. 如SSC在BBC4view上的ACC和NMI值分别为0.414～0.660和0.236～0.494. 对于3Sources数据集, SSC在3种视图的ACC和NMI的差异分别为0.101和0.126. 此外, 在3Sources和MSRC-V1数据集上, SSCCon和LRRCon的性能比SSC和LRR差. 因此, 不同特征对聚类结果有不同的影响度. 在多视图聚类过程中, 充分考虑不同特征对聚类结果的不同影响程度至关重要.

表9 不同视图特征的对比

3.5 分块研究

由上述实验结果可见, 仅考虑低阶张量表示(如LT-MSC和t-SVD-MSC)或局部结构(如MLAN)都不能获得满意的性能结果. 现有的方法, 包括DiMSC,LT-MSC和t-SVD-MSC, 都是学习表示张量, 然后构造相似性矩阵, 未考虑不同特征的不同贡献度和特征之间的依赖性. 为解决这些问题, 本文提出的GRLRTMA分两个阶段改进现有的方法： 1) 同时学习表示张量和相似性矩阵； 2) 将局部几何结构整合到一个统一的框架中. 为分别统计上述两个因素的贡献程度, 进行了两种测试. 测试1令λ2,λ3=0, 并调整其他参数, 而测试2仅令λ3=0.

测试1表示为GRLRTMA-p1, 令λ2,λ3=0, 验证λ1的贡献.在GRLRTMA-p1中, 当局部结构丢失时, 同时学习Z和S.测试2表示为GRLRTMA-p2, 令λ1,λ3=0, 验证λ2的贡献. 这两个测试均使用BBC4view,BBCSport,3Sources,MSRC-V1,Scene15和COIL-20数据集. 表10列出了GRLRTMA,GRLRTMA-p1和GRLRTMA-p2的聚类结果. 由表10可见, GRLRTMA-p1和GRLRTMA在所有情况下表现都较出色. 对于ACC的平均值, GRLRTMA比GRLRTMA-p1和GRLRTMA-p2分别提高了21.85%,6.25%, NMI提高了23.57%,7.27%. 实验结果证明了GRLRTMA的优越性, 并说明同步构造表示张量和相似性矩阵并维持局部几何结构可明显提高聚类性能. 不同多视图聚类方法的平均运行时间列于表11.

表10 不同方法的ACC,NMI比较

表11 所有数据集上的平均运行时间

所有实验均采用MATLAB2016a编译器, 硬件配置为3.50 GHz的CPU和16 GB的RAM. 在所有方法中, MLAN和MSC_IAS的运行时间最短, 尤其是在处理大规模数据集时. MLAP和DiMSC的运行时间与GRLRTMA相当. 基于低秩张量的多视图聚类方法(LT-MSC,t-SVD-MSC,GRLRTMA)的计算量较大, 但其性能优于其他同类方法. 其根本原因是LT-MSC,t-SVD-MSC和GRLRTMA通过低秩张量在全局视图中尽力找到表示矩阵的相关性. 为进一步研究该算法的计算复杂度, 基于BBC4view数据集, 进行不同组合(λ1,λ2,λ3)的实验, 结果列于表12.由表12可见, 不同参数(λ1,λ2,λ3)的设置对GRLRTMA的运行时间影响较小.