基于黎曼流形的多视角谱聚类算法

doi:10.19678/j.issn.1000-3428.0062723

摘要/Abstract

摘要： 现有的多视角谱聚类算法大多只线性结合了各视角的基拉普拉斯矩阵，未考虑不同视角数据的差异性对最优拉普拉斯矩阵的影响，存在聚类性能受限的问题。提出一种基于黎曼几何均值与高阶拉普拉斯矩阵的谱聚类算法（RMMSC），挖掘多视角数据中的高阶连接信息与流形信息，提高最优拉普拉斯矩阵对各视角的信息利用率。按一定的权重线性结合数据单一视角的各阶拉普拉斯矩阵，得到每个视角的基拉普拉斯矩阵，通过低阶与高阶连接信息的结合使用，充分体现多视角数据集的全局结构。在此基础上，计算各视角基拉普拉斯矩阵的黎曼几何均值，将其作为最优拉普拉斯矩阵输入谱聚类算法，得到聚类结果。相比于传统矩阵算数均值的计算，基于黎曼流形的黎曼几何均值能够更好地恢复互补层数据的流形信息。实验结果表明，RMMSC在多组标准数据集上聚类效果优于ONMSC、MLAN、AMGL等算法。其中，在Flower17数据集上，精确度较基准算法ONMSC提高了2.14%，纯度提高了1.7%，且收敛性较好。

关键词: 多视角谱聚类, 黎曼几何均值, 高阶拉普拉斯矩阵, 对称正定矩阵, 流形学习

Abstract: Most multi-view spectral clustering algorithms only linearly aggregate the base Laplacian matrices of different views, neglecting the discrepancy of data from each view;this limits the clustering performance.A novel Riemannian Manifold based Multi-view Spectral Clustering algorithm(RMMSC) is proposed to address this problem. The manifold information and high-order connection information of different views are exploited effectively, and the information utilization of each view is improved.For each view, the Laplacian matrices of different orders are merged with certain weights to obtain the base Laplacian matrix.The integration of the connection information of different orders sufficiently represents the global structure of the multi-view datasets.On this basis, the Riemannian geometric mean of the base Laplacian matrices of different views is calculated, which is considered as the optimal Laplacian matrix for spectral clustering and obtains the clustering result.A Riemannian manifold based geometric mean recovers the manifold information of complementary layers more comprehensively compared with the arithmetic mean.Experiments on several benchmark datasets show that in contrast with ONMSC, MLAN, AMGL and other algorithms, the proposed algorithm produces superior clustering results and faster convergence.For example, compared with the baseline model ONMSC, the accuracy and purity of RMMSC are improved by 2.14% and 1.7%, respectively, on the Flower17 dataset.

Key words: multi-view spectral clustering, Riemannian geometric mean, high-order Laplacian matrix, Symmetric Positive Definite(SPD) martix, manifold learning

中图分类号:

TP18

李林珂, 康昭, 龙波. 基于黎曼流形的多视角谱聚类算法[J]. 计算机工程, 2023, 49(1): 113-120,129.

LI Linke, KANG Zhao, LONG Bo. Riemannian Manifold Based Multi-View Spectral Clustering Algorithm[J]. Computer Engineering, 2023, 49(1): 113-120,129.

http://www.ecice06.com/CN/Y2023/V49/I1/113

图/表 6

20230701175535

20230701175538

20230701175541

20230701175544

20230701175547

20230701175550

参考文献

[1] 王省, 康昭.基于光滑表示的半监督分类算法[J].计算机科学, 2021, 48(3):124-129. WANG X, KANG Z.Smooth representation-based semi-supervised classification[J].Computer Science, 2021, 48(3):124-129.(in Chinese)
[2] 葛君伟, 杨广欣.基于共享最近邻的密度自适应邻域谱聚类算法[J].计算机工程, 2021, 47(8):116-123. GE J W, YANG G X.Spectral clustering algorithm for density adaptive neighborhood based on shared nearest neighbors[J].Computer Engineering, 2021, 47(8):116-123.(in Chinese)
[3] 章蓉, 陈谊, 张梦录, 等.高维数据聚类可视分析方法综述[J].图学学报, 2020, 41(1):44-56. ZHANG R, CHEN Y, ZHANG M L, et al.Overviewing of visual analysis approaches for clustering high-dimensional data[J].Journal of Graphics, 2020, 41(1):44-56.(in Chinese)
[4] KANG Z, ZHAO X J, PENG C, et al.Partition level multiview subspace clustering[J].Neural Networks:the Official Journal of the International Neural Network Society, 2020, 122:279-288.
[5] KUMAR A, DAUMÉ H.A co-training approach for multi-view spectral clustering[C]//Proceedings of the 28th International Conference on Machine Learning.New York, USA:ACM Press, 2011:393-400.
[6] CHAO G Q, SUN S L, BI J B.A survey on multi-view clustering[EB/OL].[2021-08-12].https://arxiv.org/abs/1712.06246.
[7] LIU J L, WANG C, GAO J, et al.Multi-view clustering via joint nonnegative matrix factorization[C]//Proceedings of 2013 SIAM International Conference on Data Mining.Philadelphia, USA:Society for Industrial and Applied Mathematics, 2013:252-260.
[8] KHAN G A, HU J, LI T R, et al.Multi-view data clustering via non-negative matrix factorization with manifold regularization[J].International Journal of Machine Learning and Cybernetics, 2022, 13(3):677-689.
[9] HUANG S D, KANG Z, XU Z L.Self-weighted multi-view clustering with soft capped norm[J].Knowledge-Based Systems, 2018, 158:1-8.
[10] ZHANG C, WANG S, LIU J, et al.Multi-view clustering via deep matrix factorization and partition alignment[C]//Proceedings of the 29th ACM International Conference on Multimedia.New York, USA:ACM Press, 2021:4156-4164.
[11] LIU X W, ZHOU S H, WANG Y Q, et al.Optimal neighborhood kernel clustering with multiple kernels[C]//Proceedings of the 31st AAAI Conference on Artificial Intelligence.Palo Alto, USA:AAAI Press, 2017:2266-2272.
[12] LÜ J C, KANG Z, LU X, et al.Pseudo-supervised deep subspace clustering[J].IEEE Transactions on Image Processing, 2021, 30:5252-5263.
[13] KANG Z, LIN Z P, ZHU X F, et al.Structured graph learning for scalable subspace clustering:from single view to multiview[J].IEEE Transactions on Cybernetics, 2022, 52(9):8976-8986.
[14] CHEN X J, YE Y M, XU X F, et al.A feature group weighting method for subspace clustering of high-dimensional data[J].Pattern Recognition, 2012, 45(1):434-446.
[15] ELHAMIFAR E, VIDAL R.Sparse subspace clustering:algorithm, theory, and applications[J].IEEE Transactions on Pattern Analysis and Machine Intelligence, 2013, 35(11):2765-2781.
[16] WANG B Y, HU Y L, GAO J B, et al.Learning adaptive neighborhood graph on Grassmann manifolds for video/image-set subspace clustering[J].IEEE Transactions on Multimedia, 2021, 23:216-227.
[17] KANG Z, SHI G X, HUANG S D, et al.Multi-graph fusion for multi-view spectral clustering[J].Knowledge-Based Systems, 2020, 189:105102.
[18] 周林, 平西建, 徐森, 等.基于谱聚类的聚类集成算法[J].自动化学报, 2012, 38(8):1335-1342. ZHOU L, PING X J, XU S, et al.Cluster ensemble based on spectral clustering[J].Acta Automatica Sinica, 2012, 38(8):1335-1342.(in Chinese)
[19] HUANG S D, WANG H J, LI D C, et al.Spectral co-clustering ensemble[J].Knowledge-Based Systems, 2015, 84:46-55.
[20] NIE F, LI J, LI X.Self-weighted multiview clustering with multiple graphs[C]//Proceedings of the 26th International Joint Conference on Artificial Intelligence.New York, USA:ACM Press, 2017:2564-2570.
[21] ZHOU S, LIU X, LIU J, et al.Multi-view spectral clustering with optimal neighborhood Laplacian matrix[C]//Proceedings of the 34th AAAI Conference on Artificial Intelligence.Palo Alto, USA:AAAI Press, 2020:6965-6972.
[22] ZHOU P, SHEN Y D, DU L, et al.Incremental multi-view spectral clustering[J].Knowledge-Based Systems, 2019, 174:73-86.
[23] XIA T, TAO D C, MEI T, et al.Multiview spectral embedding[J].IEEE Transactions on Systems, Man, and Cybernetics, Part B(Cybernetics), 2010, 40(6):1438-1446.
[24] NIE F, LI J, LI X.Parameter-free auto-weighted multiple graph learning:a framework for multiview clustering and semi-supervised classification[C]//Proceedings of the 25th International Joint Conference on Artificial Intelligence.Washington D.C., USA:IEEE Press, 2016:1881-1887.
[25] ZONG L, ZHANG X, LIU X, et al.Weighted multi-view spectral clustering based on spectral perturbation[C]//Proceedings of the 32nd AAAI Conference on Artificial Intelligence.Palo Alto, USA:AAAI Press, 2018:1-10.
[26] TANG J, QU M, WANG M Z, et al.LINE:large-scale information network embedding[C]//Proceedings of the 24th International Conference on World Wide Web.New York, USA:ACM Press, 2015:1067-1077.
[27] EL GHECHE M, CHIERCHIA G, FROSSARD P.OrthoNet:multilayer network data clustering[J].IEEE Transactions on Signal and Information Processing over Networks, 2020, 6:13-23.
[28] MERCADO P, TUDISCO F, HEIN M.Clustering signed networks with the geometric mean of Laplacians[C]//Proceedings of the 30th International Conference on Neural Information Processing Systems.Washington D.C., USA:IEEE Press, 2016:4428-4436.
[29] HAN Q, XU K, AIROLDI E.Consistent estimation of dynamic and multi-layer block models[C]//Proceedings of International Conference on Machine Learning.[S.l.]:PMLR, 2015:1511-1520.
[30] HEIMLICHER S, LELARGE M, MASSOULIÉ L.Community detection in the labelled stochastic block model[EB/OL].[2021-08-12].https://arxiv.org/pdf/1209.2910.pdf.
[31] QIN F P, ZHANG A W, WANG S M, et al.Hyperspectral band selection based on spectral clustering and inter-class separability factor[J].Spectroscopy and Spectral Analysis, 2015, 35(5):1357-1364.
[32] CORTES C, MOHRI M, ROSTAMIZADEH A.Algorithms for learning kernels based on centered alignment[J].The Journal of Machine Learning Research, 2012, 13(1):795-828.
[33] BAEK M, KIM C.A review on spectral clustering and stochastic block models[J].Journal of the Korean Statistical Society, 2021, 50(3):818-831.
[34] 柴变芳, 于剑, 贾彩燕, 等.一种基于随机块模型的快速广义社区发现算法[J].软件学报, 2013, 24(11):2699-2709. CHAI B F, YU J, JIA C Y, et al.Fast algorithm on stochastic block model for exploring general communities[J].Journal of Software, 2013, 24(11):2699-2709.(in Chinese)
[35] LIM Y, PÁLFIA M.Matrix power means and the Karcher mean[J].Journal of Functional Analysis, 2012, 262(4):1498-1514.
[36] ZHANG H, SRA S.First-order methods for geodesically convex optimization[C]//Proceedings of Conference on Learning Theory.[S.l.]:PMLR, 2016:1617-1638.
[37] BINI D A, IANNAZZO B.Computing the Karcher mean of symmetric positive definite matrices[J].Linear Algebra and Its Applications, 2013, 438(4):1700-1710.
[38] CHEN S S, DONOHO D L, SAUNDERS M A.Atomic decomposition by basis pursuit[J].SIAM Review, 2001, 43(1):129-159.
[39] ZHAO Y, KARYPIS G.Criterion functions for document clustering:experiments and analysis[EB/OL].[2021-08-12].https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.17.3151&rep=rep1&type=pdf.
[40] NIE F P, CAI G H, LI X L.Multi-view clustering and semi-supervised classification with adaptive neighbours[C]//Proceedings of the 31st AAAI Conference on Artificial Intelligence.Palo Alto, USA:AAAI Press, 2017:2408-2414.

选择文件类型/文献管理软件名称

选择包含的内容