第17卷第2期 智能系统学报 Vol.17 No.2 2022年3月 CAAI Transactions on Intelligent Systems Mar.2022 D0:10.11992tis.202101011 网络出版地址：https:/kns.cnki.net/kcms/detail/23.1538.TP.20211015.0634.004.html 结合地标点与自编码的快速多视图聚类网络 马睿，周治平 (江南大学物联网技术应用教育部工程研究中心，江苏无锡214122) 摘要：针对目前存在的多视图聚类方法大多是对聚类准确性进行研究而未着重于提升算法效率，从而难以应 用于大规模数据的现象，本文提出一种结合地标点和自编码的快速多视图聚类算法。利用加权PageRank排序 算法选出每个视图中最具代表性的地标点。使用凸二次规划函数从数据中直接生成多个视图的相似度矩阵， 求得多个视图的共识相似度矩阵以有效利用多个视图包含的具有一致性和互补性的聚类有效信息，将获得的 具有低存储开销性能的共识相似度矩阵输入自编码器替代拉普拉斯矩阵特征分解，在联合学习框架下同时更 新自编码器参数和聚类中心从而在降低计算复杂度的同时保证聚类精度。在5个多视图数据集上的实验证明 了本文算法相对于其他多视图算法在运行时间上的优越性。 关键词：多视图聚类；地标点聚类：加权PageRank:自编码器：特征分解：联合学习：聚类分析：数据挖掘 中图分类号：TP181文献标志码：A文章编号：1673-4785(2022)02-0333-08 中文引用格式：马睿，周治平.结合地标点与自编码的快速多视图聚类网络J.智能系统学报，2022,17(2)：333-340. 英文引用格式：MA Rui,,ZHOU Zhiping.Fast multiview clustering network combining landmark points and autoencoder.CAAl transactions on intelligent systems,2022,17(2):333-340. Fast multiview clustering network combining landmark points and autoencoder MA Rui,ZHOU Zhiping (Engineering Research Center of Internet of Things Technology Applications Ministry of Education,Jiangnan University,Wuxi 214122,China) Abstract:Currently,most existing multiview clustering methods only focus on the accuracy of clustering and pay little attention to the improvement of the efficiency of the algorithm,which makes it difficult to apply them to large-scale datasets.This paper proposes a fast multiview clustering algorithm combining landmarks and autoencoder.The weighted PageRank algorithm is adopted to select the most representative landmark points in each view.The similarity matrix of multiple views is directly generated through the convex quadratic programming function.To effectively use the consistent and complementary clustering effective information contained in multiple views,the consensus similarity matrix of multiple views is obtained.The obtained consensus similarity matrix with low storage overhead performance is inputted to the autoencoder to replace the Laplacian matrix eigendecomposition.The proposed algorithm updates the autoencoder parameters and clustering centers under the framework of joint learning to ensure clustering accuracy while reducing computational complexity.Experiments in five multiview datasets show that the proposed algorithm is better than other multiview algorithms in terms of running time. Keywords:multiview clustering:landmark point clustering;weighted PageRank;autoencoder:eigendecomposition; joint learning;cluster analysis;data mining 聚类作为一种无监督的学习方法可将给定的 由于现实世界中多视图数据的普遍存在，例如， 数据集根据数据的内在联系划分成多个集内相似文档可以由不同语言来编写，基因可由不同技术 度高而集间相似度低的子集，获得了数据挖掘、 来测量2。充分利用多视图数据以探索到更丰 模式识别、图像分割等诸多领域的关注山。并且 富、全面的数据特征从而获得更好的性能也成为 收稿日期：2021-01-08.网络出版日期：2021-10-15. 聚类发展的方向。 通信作者：周治平.E-mail:zp@jiangnan.edu..cn 多视图子空间聚类由于其优越的性能和丰富
DOI: 10.11992/tis.202101011 网络出版地址: https://kns.cnki.net/kcms/detail/23.1538.TP.20211015.0634.004.html 结合地标点与自编码的快速多视图聚类网络 马睿，周治平 （江南大学 物联网技术应用教育部工程研究中心，江苏 无锡 214122） PageRank 摘 要：针对目前存在的多视图聚类方法大多是对聚类准确性进行研究而未着重于提升算法效率，从而难以应 用于大规模数据的现象，本文提出一种结合地标点和自编码的快速多视图聚类算法。利用加权 排序 算法选出每个视图中最具代表性的地标点。使用凸二次规划函数从数据中直接生成多个视图的相似度矩阵， 求得多个视图的共识相似度矩阵以有效利用多个视图包含的具有一致性和互补性的聚类有效信息，将获得的 具有低存储开销性能的共识相似度矩阵输入自编码器替代拉普拉斯矩阵特征分解，在联合学习框架下同时更 新自编码器参数和聚类中心从而在降低计算复杂度的同时保证聚类精度。在 5 个多视图数据集上的实验证明 了本文算法相对于其他多视图算法在运行时间上的优越性。 关键词：多视图聚类；地标点聚类；加权 PageRank；自编码器；特征分解；联合学习；聚类分析；数据挖掘 中图分类号：TP181 文献标志码：A 文章编号：1673−4785(2022)02−0333−08 中文引用格式：马睿, 周治平. 结合地标点与自编码的快速多视图聚类网络 [J]. 智能系统学报, 2022, 17(2): 333–340. 英文引用格式：MA Rui, ZHOU Zhiping. Fast multiview clustering network combining landmark points and autoencoder[J]. CAAI transactions on intelligent systems, 2022, 17(2): 333–340. Fast multiview clustering network combining landmark points and autoencoder MA Rui，ZHOU Zhiping (Engineering Research Center of Internet of Things Technology Applications Ministry of Education, Jiangnan University, Wuxi 214122, China) Abstract: Currently, most existing multiview clustering methods only focus on the accuracy of clustering and pay little attention to the improvement of the efficiency of the algorithm, which makes it difficult to apply them to large-scale datasets. This paper proposes a fast multiview clustering algorithm combining landmarks and autoencoder. The weighted PageRank algorithm is adopted to select the most representative landmark points in each view. The similarity matrix of multiple views is directly generated through the convex quadratic programming function. To effectively use the consistent and complementary clustering effective information contained in multiple views, the consensus similarity matrix of multiple views is obtained. The obtained consensus similarity matrix with low storage overhead performance is inputted to the autoencoder to replace the Laplacian matrix eigendecomposition. The proposed algorithm updates the autoencoder parameters and clustering centers under the framework of joint learning to ensure clustering accuracy while reducing computational complexity. Experiments in five multiview datasets show that the proposed algorithm is better than other multiview algorithms in terms of running time. Keywords: multiview clustering; landmark point clustering; weighted PageRank; autoencoder; eigendecomposition; joint learning; cluster analysis; data mining 聚类作为一种无监督的学习方法可将给定的 数据集根据数据的内在联系划分成多个集内相似 度高而集间相似度低的子集，获得了数据挖掘、 模式识别、图像分割等诸多领域的关注[1]。并且 由于现实世界中多视图数据的普遍存在，例如， 文档可以由不同语言来编写，基因可由不同技术 来测量[2]。充分利用多视图数据以探索到更丰 富、全面的数据特征从而获得更好的性能也成为 聚类发展的方向。 多视图子空间聚类由于其优越的性能和丰富 收稿日期：2021−01−08. 网络出版日期：2021−10−15. 通信作者：周治平. E-mail: zzp@jiangnan.edu.cn. 第 17 卷第 2 期 智 能 系 统 学 报 Vol.17 No.2 2022 年 3 月 CAAI Transactions on Intelligent Systems Mar. 2022
·334· 智能系统学报 第17卷 的可扩展性得到了飞速发展。例如，Cao等在 多视图学习场景显然无能为力。 各个视图之间利用希尔伯特施密特独立性准则 综上所述，本文提出一种结合地标点和自编 (HSIC)进行视图间相互约束，从而捕获到更丰富 码的快速多视图聚类方法。为了提取大规模数据 的数据关系。Wang等通过新颖的位置感知准 集中的强代表性点以降低存储开销，首先利用加 则来利用多个视图的互补信息，同时通过一致性 权PageRank排序算法在每个视图中选取原始数 约束来获得多个视图的通用聚类指示矩阵。Brbic 据中权重较高的数据点作为每个视图的地标点， 等向在生成多个视图的联合亲和度矩阵时利用低 为了避免传统的手工生成相似度矩阵中指数函数 秩稀疏进行约束，并将方法扩展到核空间以适用 与近邻点个数的选择，本文利用凸二次规划函数 于非线性数据。Nie等m通过避免引入超参数的 直接从数据中获得每个视图的相似度矩阵，融合 完全自动加权方案来为每个视图分配不同的权重 多视图信息，将生成的多视图共识相似度矩阵作 以区分不同视图的重要性。Wang等图试图通过 为自编码器的输人，利用自编码器替代拉普拉斯 整合编码的补充信息，利用具有最大依赖性的空 矩阵特征分解获得多视图数据的联合嵌入表示， 间学习技术来形成多视图的信息丰富的完整感知 最后利用K-means算法进行最后的聚类划分。为 相似性。L等通过将潜在表示强制构造为最大 了避免微调环节覆盖之前所得最优参数从而获得 程度接近多个视图的形式从而能够灵活地编码来 更精确的聚类结果，本文将自编码器的重建损失 自不同视图的互补信息。随着科技迅速发展，网 和聚类损失放在同一学习框架下从而能够对自编 络数据量也随之剧烈膨胀并越发呈现纷繁复杂状 码器的参数和聚类中心进行联合更新。 态。例如，Facebook每月约报告60亿张新照片， YouTube每分钟约上传72小时的视频。而聚类 1相关算法理论 分析的主要任务之一就是对大规模数据集进行无 1.1多视图子空间聚类 监督分类。虽然上述多视图聚类方法相较于单 鉴于融合多视图数据以捕获到更全面的聚类 视图聚类方法在聚类精度方面有了质的提升，但 有效信息是十分有必要的，多视图子空间聚类最 是它们都呈现出较高的计算复杂度，从而在大规 近获得了大量关注。给出多视图数据 模数据集上的使用具有局限性。 为了提升面向大规模数据集的可扩展性，亟 X=[KX2…K]eRa4w 需找到一种优质的能降低计算复杂度的聚类算 根据自表示思想通过一个稀疏系数矩阵重构 法，为了解决这一问题，He等☑利用随机傅里叶 原始数据，则多视图子空间聚类网络的目标函数为 特征来显式表示内核空间中的数据，显式特征映 min∑x-xs2+afs) 射可显著加快特征向量近似，从而提高谱聚类预 1 (1) 测速度。Tian等u1发现自编码器和谱聚类本质 s.t.S≥0，S1=1 上都是在保留原始数据最重要数据特征的同时实 式中：S为第个视图的相似度矩阵，不同形式的 现降维处理，因此运用自编码器来替代谱聚类中 f)可以给出不同性质的解。例如，文献[4]利用 的拉普拉斯矩阵特征分解，对于大规模数据集来 HSIC鼓励图对之间的差异性，文献[6]利用低秩 说，这一处理极大地减少了内存消耗，但此方法 稀疏对相似度矩阵S进行约束，文献[9]生成了一 仍需要直接处理规模庞大的数据。因此Yin等 个潜在的表示空间以灵活编码多视图信息。但是 提出了一种具有局部相似性表示的基于地标的光 所有这些多视图子空间聚类方法每个视图的相似 谱聚类方法，该方法首先通过使用给定的相似度 度矩阵S的大小都为n×n,从而都至少需要O(nk) 函数对原始数据点的“最相似”地标进行编码，然 的时间，且都涉及拉普拉斯矩阵特征分解，因此 后对编码数据点进行奇异值分解以得到频谱嵌入 具有计算效率以及存储空间上的劣势，使其很难 数据点，再利用传统聚类方法例如K-means对嵌 扩展到样本点数量庞大的大规模数据集上。 入数据点进行划分。Banijamali等将地标表示 1.2锚图构造 与非线性低维映射相结合，同时避免了直接处理 相似度矩阵的构造对于谱聚类来说非常重 大规模数据集与拉普拉斯矩阵特征分解步骤，实 要，对于构造大规模数据集的相似度矩阵，锚图 现了更精确的快速聚类方法。虽然上述基于谱聚 是一种十分有效的方法。 类的扩展算法十分有效地降低了谱聚类的计算 利用K-means或随机选择等方法从含有n个 量，但它们都是针对单视图谱聚类进行的，对于 样本点的数据集中提取出具有m(m<)个样本点
的可扩展性得到了飞速发展[3]。例如，Cao 等 [4] 在 各个视图之间利用希尔伯特施密特独立性准则 (HSIC) 进行视图间相互约束，从而捕获到更丰富 的数据关系。Wang 等 [5] 通过新颖的位置感知准 则来利用多个视图的互补信息，同时通过一致性 约束来获得多个视图的通用聚类指示矩阵。Brbic 等 [6] 在生成多个视图的联合亲和度矩阵时利用低 秩稀疏进行约束，并将方法扩展到核空间以适用 于非线性数据。Nie 等 [7] 通过避免引入超参数的 完全自动加权方案来为每个视图分配不同的权重 以区分不同视图的重要性。Wang 等 [8] 试图通过 整合编码的补充信息，利用具有最大依赖性的空 间学习技术来形成多视图的信息丰富的完整感知 相似性。Li 等 [9] 通过将潜在表示强制构造为最大 程度接近多个视图的形式从而能够灵活地编码来 自不同视图的互补信息。随着科技迅速发展，网 络数据量也随之剧烈膨胀并越发呈现纷繁复杂状 态。例如，Facebook 每月约报告 60 亿张新照片， YouTube 每分钟约上传 72 小时的视频。而聚类 分析的主要任务之一就是对大规模数据集进行无 监督分类[10]。虽然上述多视图聚类方法相较于单 视图聚类方法在聚类精度方面有了质的提升，但 是它们都呈现出较高的计算复杂度，从而在大规 模数据集上的使用具有局限性[11]。 为了提升面向大规模数据集的可扩展性，亟 需找到一种优质的能降低计算复杂度的聚类算 法，为了解决这一问题，He 等 [12] 利用随机傅里叶 特征来显式表示内核空间中的数据，显式特征映 射可显著加快特征向量近似，从而提高谱聚类预 测速度。Tian 等 [13] 发现自编码器和谱聚类本质 上都是在保留原始数据最重要数据特征的同时实 现降维处理，因此运用自编码器来替代谱聚类中 的拉普拉斯矩阵特征分解，对于大规模数据集来 说，这一处理极大地减少了内存消耗，但此方法 仍需要直接处理规模庞大的数据。因此 Yin 等 [14] 提出了一种具有局部相似性表示的基于地标的光 谱聚类方法，该方法首先通过使用给定的相似度 函数对原始数据点的“最相似”地标进行编码，然 后对编码数据点进行奇异值分解以得到频谱嵌入 数据点，再利用传统聚类方法例如 K-means 对嵌 入数据点进行划分。Banijamali 等 [15] 将地标表示 与非线性低维映射相结合，同时避免了直接处理 大规模数据集与拉普拉斯矩阵特征分解步骤，实 现了更精确的快速聚类方法。虽然上述基于谱聚 类的扩展算法十分有效地降低了谱聚类的计算 量，但它们都是针对单视图谱聚类进行的，对于 多视图学习场景显然无能为力。 综上所述，本文提出一种结合地标点和自编 码的快速多视图聚类方法。为了提取大规模数据 集中的强代表性点以降低存储开销，首先利用加 权 PageRank 排序算法在每个视图中选取原始数 据中权重较高的数据点作为每个视图的地标点， 为了避免传统的手工生成相似度矩阵中指数函数 与近邻点个数的选择，本文利用凸二次规划函数 直接从数据中获得每个视图的相似度矩阵，融合 多视图信息，将生成的多视图共识相似度矩阵作 为自编码器的输入，利用自编码器替代拉普拉斯 矩阵特征分解获得多视图数据的联合嵌入表示， 最后利用 K-means 算法进行最后的聚类划分。为 了避免微调环节覆盖之前所得最优参数从而获得 更精确的聚类结果，本文将自编码器的重建损失 和聚类损失放在同一学习框架下从而能够对自编 码器的参数和聚类中心进行联合更新。 1 相关算法理论 1.1 多视图子空间聚类 鉴于融合多视图数据以捕获到更全面的聚类 有效信息是十分有必要的，多视图子空间聚类最 近获得了大量关注。给出多视图数据 X = [X 1 X 2 ··· X v ] ∈ R ∑v i=1 di×n 根据自表示思想通过一个稀疏系数矩阵重构 原始数据，则多视图子空间聚类网络的目标函数为 min S i ∑v i=1 X i − X iS i 2 F +α f ( S i ) s.t. S i ⩾ 0,S i 1 = 1 (1) S i i f(·) S i S i n×n O ( n 2 k ) n 式中： 为第 个视图的相似度矩阵，不同形式的 可以给出不同性质的解。例如，文献 [4] 利用 HSIC 鼓励图对之间的差异性，文献 [6] 利用低秩 稀疏对相似度矩阵 进行约束，文献 [9] 生成了一 个潜在的表示空间以灵活编码多视图信息。但是 所有这些多视图子空间聚类方法每个视图的相似 度矩阵 的大小都为 ，从而都至少需要 的时间，且都涉及拉普拉斯矩阵特征分解，因此 具有计算效率以及存储空间上的劣势，使其很难 扩展到样本点 数量庞大的大规模数据集上。 1.2 锚图构造 相似度矩阵的构造对于谱聚类来说非常重 要，对于构造大规模数据集的相似度矩阵，锚图 是一种十分有效的方法[16]。 n m(m ≪ n) 利用 K-means 或随机选择等方法从含有 个 样本点的数据集中提取出具有 个样本点 ·334· 智 能 系 统 学 报 第 17 卷
第2期 马容，等：结合地标点与自编码的快速多视图聚类网络 ·335· 的子集，每个子集中的点作为地标点来逼近原数 子空间聚类中的2个数据点。对于大规模数据集 据集，引入k近邻点来度量点对之间的局部亲和 来说，此举可在利用多视图一致性与互补性确保 力。利用地标点与原数据来构造一个稀疏相似度 聚类精度的同时使复杂度显著降低。 矩阵Z∈Rmm: 由于现实世界中数据的固有结构呈现出普遍 K(xi,aj) 非线性状态9，将式(3)扩展到核空间中进行。定 Zy= yK(x,ay） je(i) (2) 义p:RD→H为从原始输入空间到核希尔伯特空 间H的映射，对于每个包含n个样本点的视图 0,其他 X=x号…x],其变换后形式为 式中：)表示x:的(r<m)个最近邻地标点；K()= (X)=[(xi)o(x2)...(x")] exp(-p(x,a)/262)是带宽参数为6的常用高斯核函 由m个地标点构成的强代表性数据矩阵 数；6控制每个数据点的局部邻域大小。 A"=[aa…aJ的变换后形式为 然而此启发式策略存在一个总是被忽略的固 (A)=(a)a)...oa")] 有缺点，即所构建的图形质量很大程度依赖于指 核函数定义为 数函数和近邻点个数的选择，因此，下游任务可 K(ss)=<pc),p(c）> 能会受到负面影响。 则式(3)可转变为 2结合地标点与自编码的快速多视 mintr(K-2K'Z'+ZK'Z+aZ" (4) 图聚类算法 s.t.ZT1=1.0≤Z"≤1 通过求解式(4)可以捕获到p(x)与p(a)间的线 2.1图形构造 性稀疏关系，即样本点x与地标点a间的非线性关 大规模数据集中存在很多冗余数据，少量样 系。将式(4)按列重新写出： 本完全满足重建子空间的需求。传统的地标点选 minK:-2KZ+ZK'Z:+aZTZ Z 择方法有文献[15]中的随机抽样和使用K均值中 (5) 心点作为地标点的方法。但是随机抽样可能导致 st.ZT1=1,0≤Z≤1 地标点彼此过于靠近，这可能导致邻域重叠。而 进而式(5)可转变成为二次型形式(6)，从而 采用K均值中心作为地标点的方法运行时间过长 能直接通过凸二次规划函数求解得到各个视图的 且当数据规模极大，超出系统的内存时，K均值聚 由数据直接生成的相似度矩阵Z: 类算法需要不断地执行读取操作”。因此，本文 minZ:(al+K)Z:-2KZ (6) 采用文献[I8]中的加权PageRank算法来为每个视 s.tZr1=1,0≤z≤1 图选择wpr值最高的m个样本点作为地标点。 因为所获得的Z的大小不为n×n,不能直接 为了避免式(2)形式生成相似度矩阵的不足 对Z进行后续谱聚类操作，在每个视图上求取双 之处，本文在多视图聚类框架下采取直接从数据 随机相似度矩阵S=22r,该形式比Z能更多地 生成相似度矩阵的方法，该方法不仅能揭示数据 保留数据局部结构，然而利用传统方法计算度矩 低维结构，还对噪声和数据规模有着极强的鲁棒 阵D需消耗O(n2m)时间，很难负担大规模数据集 性。在多视图思想下利用重构误差和约束项建立 的运行。为此采用文献20]中方法进行快速度矩 采用地标点的多视图聚类模型目标函数： 阵计算D"=diag(亿r2),其中2是第k个元素为 2第k行元素之和的m×1向量，该计算度矩阵的 min∑K-A'(Z2+az (3) 时间复杂度为O(nm),相比O(nm)有了巨大提升。 拉普拉斯矩阵表示为 st.0≤Z",(Z)T1=1. L"=D-122r2D-1n 式中：V为从不同来源或者利用不同收集方式获 (7) 得到S"=2D-,再联合各个视图以获得具 取到的视图总个数；、A"、Z分别为第v个视图 的原始数据矩阵、地标点矩阵、相似度矩阵。因 有互补性与一致性的多视图蕴涵的丰富信息： 为无需设置近邻点，该形式生成的相似度矩阵不 再受困于只能捕获到数据的局部分布这一桎梏， (8) 并能完整感知数据从而保留数据的全局结构。可 2.2联合优化框架 以看出，与式(2)相比，对于每个视图，本方法只 由于对S进行特征向量分解而获得类指示矩 需在mm个数据点之间计算相似度矩阵而非传统 阵需要花费至少O(k)的时间，当面临样本数n极
k Z ∈ R n×m 的子集，每个子集中的点作为地标点来逼近原数 据集，引入 近邻点来度量点对之间的局部亲和 力。利用地标点与原数据来构造一个稀疏相似度 矩阵 : Zi j = Kδ ( xi , aj ) ∑ j ′∈⟨i⟩ Kδ ( xi , aj ′ ) , j ∈ ⟨i⟩ 0, 其他 (2) ⟨i⟩ xi r(r < m) Kδ (·) = exp( −ρ 2 (xi , aj)/2δ 2 ) δ δ 式中： 表示 的 个最近邻地标点； 是带宽参数为 的常用高斯核函 数； 控制每个数据点的局部邻域大小。 r 然而此启发式策略存在一个总是被忽略的固 有缺点，即所构建的图形质量很大程度依赖于指 数函数和近邻点个数 的选择，因此，下游任务可 能会受到负面影响。 2 结合地标点与自编码的快速多视 图聚类算法 2.1 图形构造 K K K PageRank wpr m 大规模数据集中存在很多冗余数据，少量样 本完全满足重建子空间的需求。传统的地标点选 择方法有文献 [15] 中的随机抽样和使用 均值中 心点作为地标点的方法。但是随机抽样可能导致 地标点彼此过于靠近，这可能导致邻域重叠。而 采用 均值中心作为地标点的方法运行时间过长 且当数据规模极大，超出系统的内存时， 均值聚 类算法需要不断地执行读取操作[17]。因此，本文 采用文献 [18] 中的加权 算法来为每个视 图选择 值最高的 个样本点作为地标点。 为了避免式 (2) 形式生成相似度矩阵的不足 之处，本文在多视图聚类框架下采取直接从数据 生成相似度矩阵的方法，该方法不仅能揭示数据 低维结构，还对噪声和数据规模有着极强的鲁棒 性。在多视图思想下利用重构误差和约束项建立 采用地标点的多视图聚类模型目标函数： min Z v ∑V v=1 X v − A v (Z v ) T2 F +αZ v2 F s.t. 0 ⩽ Z v ,(Z v ) T 1 = 1. (3) V X v A v Z v v mn 式中： 为从不同来源或者利用不同收集方式获 取到的视图总个数； 、 、 分别为第 个视图 的原始数据矩阵、地标点矩阵、相似度矩阵。因 为无需设置近邻点，该形式生成的相似度矩阵不 再受困于只能捕获到数据的局部分布这一桎梏， 并能完整感知数据从而保留数据的全局结构。可 以看出，与式 (2) 相比，对于每个视图，本方法只 需在 个数据点之间计算相似度矩阵而非传统 n 子空间聚类中的 2个数据点。对于大规模数据集 来说，此举可在利用多视图一致性与互补性确保 聚类精度的同时使复杂度显著降低。 φ : R D → H H n X v = [x v 1 x v 2 ··· x v n ] 由于现实世界中数据的固有结构呈现出普遍 非线性状态[19] ，将式 (3) 扩展到核空间中进行。定 义 为从原始输入空间到核希尔伯特空 间 的映射，对于每个包含 个样本点的视图 ，其变换后形式为 φ(X v ) = [φ ( x v 1 ) φ ( x v 2 ) ··· φ ( x v n ) ] m A v = [a v 1 a v 2 ··· a v m ] 由 个地标点构成的强代表性数据矩阵 的变换后形式为 φ(A v ) = [ φ( a v 1 ) φ(a v 2 ) ··· φ(a v m )] 核函数定义为 K(xi,xj) =< φ(xi),φ( xj ) > 则式 (3) 可转变为 min Z v tr( K v −2K vZ v + Z vTK vZ v ) +αZ v2 F s.t. Z vT 1 = 1,0 ⩽ Z v ⩽ 1 (4) φ(x) φ(a) x a 通过求解式 (4) 可以捕获到 与 间的线 性稀疏关系，即样本点 与地标点 间的非线性关 系。将式 (4) 按列重新写出： min Z v i K v ii −2K v i,:Z v i + Z v i TK vZ v i +αZ v i T Z v i s.t. Z v i T 1 = 1,0 ⩽ Z v i ⩽ 1 (5) Z v 进而式 (5) 可转变成为二次型形式 (6)，从而 能直接通过凸二次规划函数求解得到各个视图的 由数据直接生成的相似度矩阵 ： min Z v i Z v i T (αI+ K v ) Z v i −2K v i,:Z v i s.t. Z v i T 1 = 1,0 ⩽ zi j ⩽ 1 (6) Z v n×n Z v S v = Zˆ vZˆ vT Z v D v O ( n 2m ) D v = diag( Zˆ vT Zˆ vs) Zˆ vs Zˆ v m×1 O(nm) O ( n 2m ) 因为所获得的 的大小不为 ，不能直接 对 进行后续谱聚类操作，在每个视图上求取双 随机相似度矩阵 ，该形式比 能更多地 保留数据局部结构，然而利用传统方法计算度矩 阵 需消耗 时间，很难负担大规模数据集 的运行。为此采用文献 [20] 中方法进行快速度矩 阵计算 ，其中 是第 k 个元素为 第 k 行元素之和的 向量，该计算度矩阵的 时间复杂度为 ，相比 有了巨大提升。 拉普拉斯矩阵表示为 L v = D v−1/2 Zˆ vT Zˆ v D v−1/2 (7) S v = bZ v D 得到 v−1/2 ，再联合各个视图以获得具 有互补性与一致性的多视图蕴涵的丰富信息： S = ∑ v S v v (8) 2.2 联合优化框架 S O ( n 2 k ) n 由于对 进行特征向量分解而获得类指示矩 阵需要花费至少 的时间，当面临样本数 极 第 2 期 马睿，等：结合地标点与自编码的快速多视图聚类网络 ·335·
·336· 智能系统学报 第17卷 为庞大的大规模数据集时，特征分解步骤将耗时 示h;和聚类中心c,的梯度计算公式为 巨大从而降低算法可用性。由文献[2]可知谱聚 类的本质是寻求样本空间标准相似度矩阵的最小 =2∑1+k-cp,-9wa-c (14) =1 重构误差的过程，这与自编码器的核心思想高度 一致，且利用自编码器替代拉普拉斯矩阵特征分 =221+h,-c'a-pa,-c） (15) =1 解只需消耗样本数n的线性次方时间。因此将 给定m为小批量样本数，为学习速率，编码 S作为自编码器的输入来替代特征分解，通过编 器权重M1、译码器权重M2、聚类中心c,的更新公 码和解码重构学习低维嵌入形式数据。 式分别为 自编码器是一种利用非线性变换函数将原 始输入x:映射到低维嵌入空间，获得嵌入表示， (16) 再通过另一映射函数gw对h进行解码重构，通过 最小化原始输入x,与嵌入表示h,的重构输出y:之 M=M,-1/aL, 间的重构损失L,来迭代更新的人工神经网络， maM, (17) 其均值误差测量形式目标函数为 :-%m 62 (18) (9) 当连续两次更新的类标签分配之间的变化率 文献[15]同样利用自编码器来配合聚类，然 小于给定的阈值6时迭代停止。 而其仅在聚类步骤前简单叠加无监督深度学习框 23算法流程图 架，这样形成的低维嵌入空间可能反而会损坏聚 结合地标点与自编码的快速多视图聚类网络 类分配效果。为此本文将聚类步骤和表示学习统 算法流程如图1所示。 到一个基于KL散度的利用损失函数迭代更新 开始 自编码器参数{M1、M2:0、}和聚类中心c,的联 合学习框架中，从而能联合优化聚类标签的分配 从文件中读取多视图数据 和特征的学习，也使位于自编码器隐藏层的低维 特征能够最大限度的保留原始数据的固有局部结 根据加权PageRank选择出 构。将聚类损失目标函数定义为 每个视图的m个地标点 4.=KL(nIQ)=∑∑p,log (10) qii 根据式（⑥）利用凸二次规划函数 式中：Q为由t-SNE测量的软标签的分布；P为由 直接生成多个视图的相似度矩阵 Q导出的目标分布。KL散度衡量了两种不同分 根据式(8)生成多个视图的 布之间的差异性，若对其进行最小化则能使得目 共识相似度矩阵 标分布P能够尽可能接近聚类输出分布Q。9表 示根据t-SNE测量得到的嵌入表示h,与聚类中心 使用共识相似度矩阵作为堆叠 c,的相似程度，其表达式如下： 自编码器的输入 (1+h:-c) qi (11) ∑1+h-c7 在隐藏层初始化聚类中心 P则是由q确定的目标分布： 根据式(16)~(18)更新自 编码器参数和聚类中心 /∑u Py= ∑所∑ (12) 类标签分配变化率 是否小于给定阈值 因此，总体的优化目标函数为 Y L=L+λL (13) 其中，A(0<A<1)为控制嵌入空间失真程度的平衡 结束 参数。则根据mini-batch随机梯度算法反向传播 图1所提算法流程图 逐层训练网络后计算出的聚类损失L关于嵌入表 Fig.1 Flow chart of the proposed algorithm
n S 为庞大的大规模数据集时，特征分解步骤将耗时 巨大从而降低算法可用性。由文献 [21] 可知谱聚 类的本质是寻求样本空间标准相似度矩阵的最小 重构误差的过程，这与自编码器的核心思想高度 一致，且利用自编码器替代拉普拉斯矩阵特征分 解只需消耗样本数 的线性次方时间。因此将 作为自编码器的输入来替代特征分解，通过编 码和解码重构学习低维嵌入形式数据。 fi xi hi gw’ hi xi hi yi Lr 自编码器是一种利用非线性变换函数 将原 始输入 映射到低维嵌入空间，获得嵌入表示 ， 再通过另一映射函数 对 进行解码重构，通过 最小化原始输入 与嵌入表示 的重构输出 之 间的重构损失 来迭代更新的人工神经网络[14] ， 其均值误差测量形式目标函数为 Lr = ∑n i=1 xi −gw’ (fi) 2 2 (9) {M1、M2；θ1、θ2} cj 文献 [15] 同样利用自编码器来配合聚类，然 而其仅在聚类步骤前简单叠加无监督深度学习框 架，这样形成的低维嵌入空间可能反而会损坏聚 类分配效果。为此本文将聚类步骤和表示学习统 一到一个基于 KL 散度的利用损失函数迭代更新 自编码器参数 和聚类中心 的联 合学习框架中，从而能联合优化聚类标签的分配 和特征的学习，也使位于自编码器隐藏层的低维 特征能够最大限度的保留原始数据的固有局部结 构。将聚类损失目标函数定义为 Lc = KL(P| |Q) = ∑ i ∑ j pi jlog pi j qi j (10) Q P Q P Q qi j hi cj 式中： 为由 t-SNE 测量的软标签的分布； 为由 导出的目标分布。KL 散度衡量了两种不同分 布之间的差异性，若对其进行最小化则能使得目 标分布 能够尽可能接近聚类输出分布 。 表 示根据 t-SNE 测量得到的嵌入表示 与聚类中心 的相似程度[14] ，其表达式如下： qi j = (1+ hi − cj) −1 ∑ j (1+ hi − cj 2 ) −1 (11) pi j 则是由 qi j 确定的目标分布： pi j = q 2 i j/ ∑ i qi j ∑ j (q 2 i j/ ∑ i qi j) (12) 因此，总体的优化目标函数为 L = Lc +λLr (13) λ(0 < λ < 1) Lc 其中， 为控制嵌入空间失真程度的平衡 参数。则根据 mini-batch 随机梯度算法反向传播 逐层训练网络后计算出的聚类损失 关于嵌入表 示 hi和聚类中心 cj 的梯度计算公式为 ∂Lc ∂hi = 2 ∑k j=1 ( 1+ hi − cj 2 )−1 ( pi j −qi j) (hi − cj ) (14) ∂Lc ∂cj = 2 ∑k j=1 ( 1+ hi − cj 2 )−1 ( qi j − pi j) (hi − cj ) (15) m η M1 M2 cj 给定 为小批量样本数， 为学习速率，编码 器权重 、译码器权重 、聚类中心 的更新公 式分别为 M1 = M1 − η m ∑m i=1 ( ∂Lc ∂M1 +λ ∂Lr ∂M1 ) (16) M2 = M2 − η m ∑m i=1 ( ∂Lr ∂M2 ) (17) cj = cj − η m ∑m i=1 ( ∂Lc ∂cj ) (18) δ 当连续两次更新的类标签分配之间的变化率 小于给定的阈值 时迭代停止。 2.3 算法流程图 结合地标点与自编码的快速多视图聚类网络 算法流程如图 1 所示。 开始 从文件中读取多视图数据 根据式 (6) 利用凸二次规划函数 直接生成多个视图的相似度矩阵 根据式 (8) 生成多个视图的 共识相似度矩阵 使用共识相似度矩阵作为堆叠 自编码器的输入 在隐藏层初始化聚类中心 根据式 (16) ~ (18) 更新自 编码器参数和聚类中心 类标签分配变化率 是否小于给定阈值 结束 根据加权 PageRank 选择出 每个视图的 m 个地标点 N Y 图 1 所提算法流程图 Fig. 1 Flow chart of the proposed algorithm ·336· 智 能 系 统 学 报 第 17 卷
第2期 马容，等：结合地标点与自编码的快速多视图聚类网络 ·337· 2.4算法复杂度分析 techl01-7/20、NUS-WIDE-Object (NUS)五个大规 当有v个视图，每个视图有n个样本点，每个视 模的多视图数据集进行实验，每个数据集样本点 图的地标点个数为m时：1)利用加权PageRank算法 数都在1000以上，表2为5个大规模多视图数据 为每个视图进行地标点选择，因此本文地标点选 集的详细介绍，其中V为多视图数据集的视图编 择步骤的时间复杂度为O(vmm),t为生成每个样本 号。本文算法实验是在python3..7运行，计算机配 点的wpr的迭代次数；2)构造多个视图的相似度 置为Intel Core i5CPU1.6GHz、4GB内存，操作系 矩阵，DiMSC和FMR等多视图子空间聚类方法 统为macOS Catalina. 由于未进行1)地标点选择，在2)中DiMSC和 表2数据集介绍 FMR算法构造的每个视图的自表示矩阵图形大 Table 2 Description of the datasets 小均为n×m,二者的计算复杂度分别为O(Tvm3+vdm2)、 100leaves Handwritten Caltech101-7/20 NUS O(T(L+1)(m3+k2),其中L表示FMR算法中涉及 64 216 48 65 的梯度下降法的迭代次数，T为DiMSC、FMR算 64 76 40 226 法总迭代次数。当数据规模n很大时，L、T<m,因 64 64 254 145 此DiMSC和FMR算法步骤2)的计算复杂度均 4 6 1984 74 可视为O(n),这远远高于本文算法的m×n(m《n) 5 240 512 129 图形的计算复杂度O(mm)。3)聚类步骤，DiM- 6 47 928 SC和FMR算法的步骤3)采用常规谱聚类，涉及 1600 2000 1474/2386 30000 到2图的拉普拉斯矩阵特征分解，需要消耗 100 10 7/20 31 O()的时间复杂度，且存储开销极大。而所提算 法采用自编码器替代拉普拉斯矩阵特征分解步 将本文方法所得聚类结果与样本真实标签进 骤，自编码器参数和聚类中心联合更新，仅需 行比较，利用聚类准确率(ACC)、标准化互信息 O(nD2+ndk)的时间，其中D为自编码器隐藏层的 (NM)和运行时间(Time)来作为性能评估指标， 最大单元数，d为自编码器中间层的维数，k为簇 ACC和NMI取值均在O~1,值越大说明聚类性能 数，与此同时存储开销也被大大降低。因为通常 越佳，运行时间越短说明算法越具有普遍适用 k《d《D,所以本文所提算法的总体时间复杂度 性，即越适用于大规模数据集。 为O(vtpm+vmm3+nD)。可以看出，本文提出的采 3.2数据集及对比算法 用地标点的快速多视图聚类网络的总体时间复杂 为证明本文提出的算法的有效性，将其分别 度为样本点数n的线性次方，而DiMSC和FMR聚 与单视图聚类算法和多视图聚类算法进行对比， 类算法的总体时间复杂度为样本点数n的三次 对比单视图聚类算法分别为文献[21]中的传统单 方。表1给出了所提算法与多视图聚类算法DMSC、 视图谱聚类算法SC和文献[15]中的使用K均值 FMR的时间复杂度对比结果。与通常的多视图 进行地标点选择后利用嵌入表示替代拉普拉斯矩 聚类算法相比本文算法的效率大大提升，且所需 阵分解步骤的SCAL-K,同时与4个近期出现的 的存储开销显著降低，从而可更适用于大规模数 性能优异的多视图聚类算法DiMSCH、MLRSSC 据集。 MSC IAS!⑧、FMRO进行对比。 表1不同方法时间复杂度对比 为保证算法对比的公平性，所有对比算法都 Table 1 Complexity analysis of different methods 遵从算法原论文的实验设置，并调试参数获得其 算法步骤1 步骤2 步骤3 总体 最优值。文献[I5]中的SCAL-K算法及本文算法 DiMSC O(Tvn+vdn2) O(n3) O(n) 的自编码器部分的编码器维度设置为p-500-500- FMR O(T(L+1)(n3+km2) O(n) O(n) 2000-10,解码器部分为编码器的镜像，最小批量 本文O(vtn) O(vnm) O(nD2+ndk)O(n) 样本数设置为256，初始学习速率n设为0.1，停止 阈值设置为h=103,并把控制嵌入空间失真程度 3实验与结果分析 的平衡参数A设置为0.1。对于两个单视图聚类算 法，在数据集的每个视图上运行实验后取多个视 3.1实验环境及评价指标 图里的最佳结果展示。 为了证明本文所提方法对大规模多视图数据 3.3实验结果分析 的适用性，选取100leaves、Handwritten(HW)、Cal- 各个算法在5个数据集上的实验结果如表3~7
2.4 算法复杂度分析 v n m PageRank O(vtmn) t n×n O(T vn3 +vdn2 ) O(T(L+1))( n 3 +kn2 ) L T n L T ≪ n O ( n 3 ) m×n m ≪ n O ( vnm3 ) n 2 O ( n 3 ) O ( nD2 +ndk) D d k k ≪ d ≪ D O ( vtpn+vnm3 +nD2 ) n n 当有 个视图，每个视图有 个样本点，每个视 图的地标点个数为 时：1) 利用加权 算法 为每个视图进行地标点选择，因此本文地标点选 择步骤的时间复杂度为 ， 为生成每个样本 点的 wpr 的迭代次数；2) 构造多个视图的相似度 矩阵，DiMSC 和 FMR 等多视图子空间聚类方法 由于未进行 1) 地标点选择，在 2) 中 DiMSC 和 FMR 算法构造的每个视图的自表示矩阵图形大 小均为 ，二者的计算复杂度分别为 、 ，其中 表示 FMR 算法中涉及 的梯度下降法的迭代次数， 为 DiMSC、FMR 算 法总迭代次数。当数据规模 很大时， 、 ，因 此 DiMSC 和 FMR 算法步骤 2) 的计算复杂度均 可视为 ，这远远高于本文算法的 ( ) 图形的计算复杂度 。3) 聚类步骤，DiMSC 和 FMR 算法的步骤 3) 采用常规谱聚类，涉及 到 图的拉普拉斯矩阵特征分解，需要消耗 的时间复杂度，且存储开销极大。而所提算 法采用自编码器替代拉普拉斯矩阵特征分解步 骤，自编码器参数和聚类中心联合更新，仅需 的时间，其中 为自编码器隐藏层的 最大单元数， 为自编码器中间层的维数， 为簇 数，与此同时存储开销也被大大降低。因为通常 ，所以本文所提算法的总体时间复杂度 为 。可以看出，本文提出的采 用地标点的快速多视图聚类网络的总体时间复杂 度为样本点数 的线性次方，而 DiMSC 和 FMR 聚 类算法的总体时间复杂度为样本点数 的三次 方。表 1 给出了所提算法与多视图聚类算法 DiMSC、 FMR 的时间复杂度对比结果。与通常的多视图 聚类算法相比本文算法的效率大大提升，且所需 的存储开销显著降低，从而可更适用于大规模数 据集。 表 1 不同方法时间复杂度对比 Table 1 Complexity analysis of different methods 算法 步骤1 步骤2 步骤3 总体 DiMSC — O(T vn3 +vdn2 ) O ( n 3 ) O ( n 3 ) FMR — O(T(L+1))( n 3 +kn2 ) O ( n 3 ) O ( n 3 ) 本文 O(vtmn) O ( vnm3 ) O ( nD2 +ndk) O(n) 3 实验与结果分析 3.1 实验环境及评价指标 为了证明本文所提方法对大规模多视图数据 的适用性，选取 100leaves、Handwritten（HW）、CalV tech101-7/20、NUS-WIDE-Object (NUS) 五个大规 模的多视图数据集进行实验，每个数据集样本点 数都在 1 000 以上，表 2 为 5 个大规模多视图数据 集的详细介绍，其中 为多视图数据集的视图编 号。本文算法实验是在 python3.7 运行，计算机配 置为 Intel Core i5CPU 1.6 GHz、4 GB 内存，操作系 统为 macOS Catalina。 表 2 数据集介绍 Table 2 Description of the datasets V 100leaves Handwritten Caltech101-7/20 NUS 1 64 216 48 65 2 64 76 40 226 3 64 64 254 145 4 — 6 1984 74 5 — 240 512 129 6 — 47 928 — n 1600 2000 1474/2386 30 000 k 100 10 7/20 31 将本文方法所得聚类结果与样本真实标签进 行比较，利用聚类准确率 (ACC)、标准化互信息 (NMI) 和运行时间 (Time) 来作为性能评估指标， ACC 和 NMI 取值均在 0~1，值越大说明聚类性能 越佳，运行时间越短说明算法越具有普遍适用 性，即越适用于大规模数据集。 3.2 数据集及对比算法 为证明本文提出的算法的有效性，将其分别 与单视图聚类算法和多视图聚类算法进行对比， 对比单视图聚类算法分别为文献 [21] 中的传统单 视图谱聚类算法 SC 和文献 [15] 中的使用 K 均值 进行地标点选择后利用嵌入表示替代拉普拉斯矩 阵分解步骤的 SCAL-K，同时与 4 个近期出现的 性能优异的多视图聚类算法 DiMSC[4] 、MLRSSC[6] 、 MSC_IAS[8] 、FMR[10] 进行对比。 η 0.1 h = 10−3 λ 0.1 为保证算法对比的公平性，所有对比算法都 遵从算法原论文的实验设置，并调试参数获得其 最优值。文献 [15] 中的 SCAL-K 算法及本文算法 的自编码器部分的编码器维度设置为 p-500-500- 2000-10，解码器部分为编码器的镜像，最小批量 样本数设置为 256，初始学习速率 设为 ，停止 阈值设置为 ，并把控制嵌入空间失真程度 的平衡参数 设置为 。对于两个单视图聚类算 法，在数据集的每个视图上运行实验后取多个视 图里的最佳结果展示。 3.3 实验结果分析 各个算法在 5 个数据集上的实验结果如表 3~7 第 2 期 马睿，等：结合地标点与自编码的快速多视图聚类网络 ·337·