research-article

Multiple Kernel Clustering with Dual Noise Minimization

Authors:

En ZhuAuthors Info & Claims

MM '22: Proceedings of the 30th ACM International Conference on Multimedia

Pages 3440 - 3450

https://doi.org/10.1145/3503161.3548334

Published: 10 October 2022 Publication History

Abstract

Clustering is a representative unsupervised method widely applied in multi-modal and multi-view scenarios. Multiple kernel clustering (MKC) aims to group data by integrating complementary information from base kernels. As a representative, late fusion MKC first decomposes the kernels into orthogonal partition matrices, then learns a consensus one from them, achieving promising performance recently. However, these methods fail to consider the noise inside the partition matrix, preventing further improvement of clustering performance. We discover that the noise can be disassembled into separable dual parts, i.e. N-noise and C-noise (Null space noise and Column space noise). In this paper, we rigorously define dual noise and propose a novel parameter-free MKC algorithm by minimizing them. To solve the resultant optimization problem, we design an efficient two-step iterative strategy. To our best knowledge, it is the first time to investigate dual noise within the partition in the kernel space. We observe that dual noise will pollute the block diagonal structures and incur the degeneration of clustering performance, and C-noise exhibits stronger destruction than N-noise. Owing to our efficient mechanism to minimize dual noise, the proposed algorithm surpasses the recent methods by large margins.

Supplementary Material

MP4 File (MM22-fp2623.mp4)

Presentation video of MM22-fp2623.

Download
192.32 MB

References

[1]

Feiping Nie, Xiaoqian Wang, and Heng Huang. Clustering and projected clustering with adaptive neighbors. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 977--986, 2014.

Digital Library

[2]

Yazhou Ren, Shudong Huang, Peng Zhao, Minghao Han, and Zenglin Xu. Self-paced and auto-weighted multi-view clustering. Neurocomputing, 383:248--256, 2020.

Digital Library

[3]

Feiping Nie, Xiaoqian Wang, Michael Jordan, and Heng Huang. The constrained laplacian rank algorithm for graph-based clustering. In Proceedings of the AAAI conference on artificial intelligence, volume 30, 2016.

[4]

Yue Liu, Xihong Yang, Sihang Zhou, and Xinwang Liu. Simple contrastive graph clustering. arXiv preprint arXiv:2205.07865, 2022.

[5]

Yazhou Ren, Ni Wang, Mingxia Li, and Zenglin Xu. Deep density-based image clustering. Knowledge-Based Systems, 197:105841, 2020.

[6]

Changqing Zhang, Qinghua Hu, Huazhu Fu, Pengfei Zhu, and Xiaochun Cao. Latent multi-view subspace clustering. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 4279--4287, 2017.

[7]

Jie Xu, Yazhou Ren, Huayi Tang, Xiaorong Pu, Xiaofeng Zhu, Ming Zeng, and Lifang He. Multi-vae: Learning disentangled view-common and view-peculiar visual representations for multi-view clustering. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 9234--9243, 2021.

[8]

Xiaojun Chang, Feiping Nie, Zhigang Ma, Yi Yang, and Xiaofang Zhou. A convex formulation for spectral shrunk clustering. In Twenty-Ninth AAAI Conference on Artificial Intelligence, 2015.

Digital Library

[9]

Kun Zhan, Changqing Zhang, Junpeng Guan, and Junsheng Wang. Graph learning for multiview clustering. IEEE transactions on cybernetics, 48(10):2887--2895, 2017.

[10]

Jie Wen, Yong Xu, and Hong Liu. Incomplete multiview spectral clustering with adaptive graph learning. IEEE transactions on cybernetics, 50(4):1418--1429, 2018.

[11]

Kun Zhan, Chaoxi Niu, Changlu Chen, Feiping Nie, Changqing Zhang, and Yi Yang. Graph structure fusion for multiview clustering. IEEE Transactions on Knowledge and Data Engineering, 31(10):1984--1993, 2018.

[12]

Zhao Kang, Haiqi Pan, Steven CH Hoi, and Zenglin Xu. Robust graph learning from noisy data. IEEE transactions on cybernetics, 50(5):1833--1843, 2019.

[13]

Shudong Huang, Zhao Kang, and Zenglin Xu. Auto-weighted multi-view clustering via deep matrix decomposition. Pattern Recognition, 97:107015, 2020.

Digital Library

[14]

Shudong Huang, Ivor W Tsang, Zenglin Xu, Jiancheng Lv, and Quanhui Liu. Cdd: Multi-view subspace clustering via cross-view diversity detection. In Proceedings of the 29th ACM International Conference on Multimedia, pages 2308--2316, 2021.

Digital Library

[15]

Siwei Wang, Xinwang Liu, Xinzhong Zhu, Pei Zhang, Yi Zhang, Feng Gao, and En Zhu. Fast parameter-free multi-view subspace clustering with consensus anchor guidance. IEEE Transactions on Image Processing, 31:556--568, 2022.

Digital Library

[16]

Siwei Wang, Xinwang Liu, Suyuan Liu, Jiaqi Jin, Wenxuan Tu, Xinzhong Zhu, and En Zhu. Align then fusion: Generalized large-scale multi-view clustering with anchor matching correspondences. arXiv preprint arXiv:2205.15075, 2022.

[17]

Liping Jing, Michael K Ng, and Tieyong Zeng. Dictionary learning-based subspace structure identification in spectral clustering. IEEE Transactions on Neural Networks and Learning Systems, 24(8):1188--1199, 2013.

[18]

Feiping Nie, Guohao Cai, and Xuelong Li. Multi-view clustering and semi-supervised classification with adaptive neighbours. In Thirty-first AAAI conference on artificial intelligence, 2017.

Digital Library

[19]

Liping Jing, Lixin Zhou, Michael K Ng, and J Zhexue Huang. Ontology-based distance measure for text clustering. In Proc. of SIAM SDM workshop on text mining, Bethesda, Maryland, USA, 2006.

[20]

Suyuan Liu, Siwei Wang, Pei Zhang, Kai Xu, Xinwang Liu, Changwang Zhang, and Feng Gao. Efficient one-pass multi-view subspace clustering with consensus anchors. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 7576--7584, 2022.

[21]

Changqing Zhang, Yajie Cui, Zongbo Han, Joey Tianyi Zhou, Huazhu Fu, and Qinghua Hu. Deep partial multi-view learning. IEEE transactions on pattern analysis and machine intelligence, 2020.

[22]

Yue Liu, Sihang Zhou, Xinwang Liu, Wenxuan Tu, and Xihong Yang. Improved dual correlation reduction network. arXiv preprint arXiv:2202.12533, 2022.

[23]

Jie Wen, Zheng Zhang, Yong Xu, Bob Zhang, Lunke Fei, and Guo-Sen Xie. Cdimcnet: Cognitive deep incomplete multi-view clustering network. In Proceedings of the Twenty-Ninth International Conference on International Joint Conferences on Artificial Intelligence, pages 3230--3236, 2021.

[24]

Siwei Wang, Xinwang Liu, Li Liu, Wenxuan Tu, Xinzhong Zhu, Jiyuan Liu, Sihang Zhou, and En Zhu. Highly-efficient incomplete large-scale multi-view clustering with consensus bipartite graph. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 9776--9785, 2022.

[25]

Bin Zhao, James T Kwok, and Changshui Zhang. Multiple kernel clustering. In Proceedings of the 2009 SIAM International Conference on Data Mining, pages 638--649. SIAM, 2009.

[26]

Changshui Zhang, Feiping Nie, and Shiming Xiang. A general kernelization framework for learning algorithms based on kernel pca. Neurocomputing, 73(4--6):959--967, 2010.

[27]

Zhao Kang, Chong Peng, and Qiang Cheng. Kernel-driven similarity learning. Neurocomputing, 267:210--219, 2017.

Digital Library

[28]

Shudong Huang, Zhao Kang, Ivor W Tsang, and Zenglin Xu. Auto-weighted multi-view clustering via kernelized graph learning. Pattern Recognition, 88:174--184, 2019.

Digital Library

[29]

Zhao Kang, Liangjian Wen, Wenyu Chen, and Zenglin Xu. Low-rank kernel learning for graph-based clustering. Knowledge-Based Systems, 163:510--517, 2019.

[30]

Zhenwen Ren, Quansen Sun, and Dong Wei. Multiple kernel clustering with kernel k-means coupled graph tensor learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 9411--9418, 2021.

[31]

John Shawe-Taylor, Nello Cristianini, et al. Kernel methods for pattern analysis. Cambridge university press, 2004.

[32]

Inderjit S Dhillon, Yuqiang Guan, and Brian Kulis. Kernel k-means: spectral clustering and normalized cuts. In Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, pages 551--556, 2004.

Digital Library

[33]

Hsin-Chien Huang, Yung-Yu Chuang, and Chu-Song Chen. Multiple kernel fuzzy clustering. IEEE Transactions on Fuzzy Systems, 20(1):120--134, 2012.

Digital Library

[34]

Xinwang Liu, Yong Dou, Jianping Yin, Lei Wang, and En Zhu. Multiple kernel k-means clustering with matrix-induced regularization. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 30, 2016.

[35]

Zhao Kang, Chong Peng, and Qiang Cheng. Twin learning for similarity and clustering: a unified kernel approach. In Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence, pages 2080--2086, 2017.

[36]

Xinwang Liu, Sihang Zhou, Yueqing Wang, Miaomiao Li, Yong Dou, En Zhu, and Jianping Yin. Optimal neighborhood kernel clustering with multiple kernels. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 31, 2017.

[37]

Zhao Kang, Yiwei Lu, Yuanzhang Su, Changsheng Li, and Zenglin Xu. Similarity learning via kernel preserving embedding. In proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 4057--4064, 2019.

Digital Library

[38]

Liang Li, Siwei Wang, Xinwang Liu, En Zhu, Li Shen, Kenli Li, and Keqin Li. Local sample-weighted multiple kernel clustering with consensus discriminative graph. arXiv preprint arXiv:2207.02846, 2022.

[39]

Siwei Wang, Xinwang Liu, En Zhu, Chang Tang, Jiyuan Liu, Jingtao Hu, Jingyuan Xia, and Jianping Yin. Multi-view clustering via late fusion alignment maximization. In The Twenty-eighth International Joint Conference on Artificial Intelligence, pages 3778--3784, 2019.

[40]

Xinwang Liu, Xinzhong Zhu, Miaomiao Li, Lei Wang, Chang Tang, Jianping Yin, Dinggang Shen, Huaimin Wang, and Wen Gao. Late fusion incomplete multi-view clustering. IEEE transactions on pattern analysis and machine intelligence, 2018.

[41]

Jiyuan Liu, Xinwang Liu, Yuexiang Yang, Siwei Wang, and Sihang Zhou. Hierarchical multiple kernel clustering. In Thirty-Fifth AAAI Conference on Artificial Intelligence, AAAI, pages 2--9, 2021.

[42]

Xinwang Liu, Li Liu, Qing Liao, Siwei Wang, Yi Zhang, Wenxuan Tu, Chang Tang, Jiyuan Liu, and En Zhu. One pass late fusion multi-view clustering. In International Conference on Machine Learning, pages 6850--6859. PMLR, 2021.

[43]

Siwei Wang, Xinwang Liu, Li Liu, Sihang Zhou, and En Zhu. Late fusion multiple kernel clustering with proxy graph refinement. IEEE Transactions on Neural Networks and Learning Systems, 2021.

[44]

Tiejian Zhang, Xinwang Liu, Lei Gong, Siwei Wang, Xin Niu, and Li Shen. Late fusion multiple kernel clustering with local kernel alignment maximization. IEEE Transactions on Multimedia, pages 1--1, 2021.

[45]

Liping Jing, Michael K Ng, and Joshua Zhexue Huang. An entropy weighting k-means algorithm for subspace clustering of high-dimensional sparse data. IEEE Transactions on knowledge and data engineering, 19(8):1026--1041, 2007.

Digital Library

[46]

Feiping Nie, Zinan Zeng, Ivor W Tsang, Dong Xu, and Changshui Zhang. Spectral embedded clustering: A framework for in-sample and out-of-sample spectral clustering. IEEE Transactions on Neural Networks, 22(11):1796--1808, 2011.

Digital Library

[47]

Jie Wen, Ke Yan, Zheng Zhang, Yong Xu, Junqian Wang, Lunke Fei, and Bob Zhang. Adaptive graph completion based incomplete multi-view clustering. IEEE Transactions on Multimedia, 23:2493--2504, 2020.

Digital Library

[48]

Changqing Zhang, Huazhu Fu, Qinghua Hu, Xiaochun Cao, Yuan Xie, Dacheng Tao, and Dong Xu. Generalized latent multi-view subspace clustering. IEEE transactions on pattern analysis and machine intelligence, 42(1):86--99, 2018.

[49]

Grigorios Tzortzis and Aristidis Likas. The global kernel k-means clustering algorithm. In 2008 IEEE International Joint Conference on Neural Networks (IEEE World Congress on Computational Intelligence), pages 1977--1984. IEEE, 2008.

[50]

Werner H Greub. Linear algebra, volume 23. Springer Science & Business Media, 2012.

[51]

Igor Griva, Stephen G Nash, and Ariela Sofer. Linear and nonlinear optimization, volume 108. Siam, 2009.

[52]

Kazuo Murota. Discrete convex analysis, volume 10 of SIAM monographs on discrete mathematics and applications. SIAM, 2003.

Digital Library

[53]

Shmuel Onn. Convex discrete optimization. In Vasek Chvátal, editor, Combinatorial Optimization - Methods and Applications, volume 31 of NATO Science for Peace and Security Series - D: Information and Communication Security, pages 183--228. IOS Press, 2011.

[54]

Zhao Kang, Wangtao Zhou, Zhitong Zhao, Junming Shao, Meng Han, and Zenglin Xu. Large-scale multi-view subspace clustering in linear time. In Proceedings of the AAAI conference on Artificial Intelligence, volume 34, pages 4412--4419, 2020.

[55]

James C. Bezdek and Richard J. Hathaway. Convergence of alternating optimization. Neural, Parallel Sci. Comput., 11(4):351--368, 2003.

Digital Library

[56]

Feiping Nie, Jing Li, Xuelong Li, et al. Self-weighted multiview clustering with multiple graphs. In The Twenty-sixth International Joint Conference on Artificial Intelligence, pages 2564--2570, 2017.

[57]

Zhenwen Ren and Quansen Sun. Simultaneous global and local graph structure preserving for multiple kernel clustering. IEEE transactions on neural networks and learning systems, 32(5):1839--1851, 2020.

[58]

Zhenwen Ren, Simon X Yang, Quansen Sun, and Tao Wang. Consensus affinity graph learning for multiple kernel clustering. IEEE Transactions on Cybernetics, 2020.

[59]

Shudong Huang, Yazhou Ren, and Zenglin Xu. Robust multi-view data clustering with multi-view capped-norm k-means. Neurocomputing, 311:197--208, 2018.

Digital Library

[60]

Jie Wen, Zheng Zhang, Yong Xu, Bob Zhang, Lunke Fei, and Hong Liu. Unified embedding alignment with missing views inferring for incomplete multi-view clustering. In Proceedings of the AAAI conference on artificial intelligence, volume 33, pages 5393--5400, 2019.

Digital Library

[61]

Yazhou Ren, Uday Kamath, Carlotta Domeniconi, and Zenglin Xu. Parallel boosted clustering. Neurocomputing, 351:87--100, 2019.

Digital Library

[62]

Jie Wen, Zheng Zhang, Zhao Zhang, Lunke Fei, and Meng Wang. Generalized incomplete multiview clustering with flexible locality structure diffusion. IEEE transactions on cybernetics, 51(1):101--114, 2020.

[63]

Changqing Zhang, Huazhu Fu, Si Liu, Guangcan Liu, and Xiaochun Cao. Low-rank tensor constrained multiview subspace clustering. In Proceedings of the IEEE international conference on computer vision, pages 1582--1590, 2015.

Digital Library

Cited By

Liu YYang XZhou SLiu XWang SLiang KTu WLi L(2024)Simple Contrastive Graph ClusteringIEEE Transactions on Neural Networks and Learning Systems10.1109/TNNLS.2023.327187135:10(13789-13800)Online publication date: Oct-2024
https://doi.org/10.1109/TNNLS.2023.3271871
Gong LTu WZhou SZhao LLiu ZLiu X(2024)Deep Fusion Clustering Network With Reliable Structure PreservationIEEE Transactions on Neural Networks and Learning Systems10.1109/TNNLS.2022.322091435:6(7792-7803)Online publication date: Jun-2024
https://doi.org/10.1109/TNNLS.2022.3220914
Wu XRen ZYu F(2024)Parameter-Free Shifted Laplacian Reconstruction for Multiple Kernel ClusteringIEEE/CAA Journal of Automatica Sinica10.1109/JAS.2023.12360011:4(1072-1074)Online publication date: Apr-2024
https://doi.org/10.1109/JAS.2023.123600
Show More Cited By

Index Terms

Multiple Kernel Clustering with Dual Noise Minimization
1. Computing methodologies
  1. Machine learning
    1. Learning paradigms
      1. Unsupervised learning
        Cluster analysis
2. Theory of computation
  1. Theory and algorithms for application domains
    1. Machine learning theory
      1. Unsupervised learning and clustering

Recommendations

Efficient Multiple Kernel Clustering via Spectral Perturbation
MM '22: Proceedings of the 30th ACM International Conference on Multimedia

Clustering is a fundamental task in the machine learning and data mining community. Among existing clustering methods, multiple kernel clustering (MKC) has been widely investigated due to its effectiveness to capture non-linear relationships among ...
Unified and View-Specific Multiple Kernel K-Means Clustering
Database and Expert Systems Applications
Abstract
Multiple kernel clustering (MKC), as an important tool for handling multi-view non-linear data, has attracted notable attention among data mining and machine learning communities. The key issue of MKC is to obtain a more accurate and appropriate ...
Simple multiple kernel k-means with kernel weight regularization
Abstract
Multiple kernel clustering (MKC) aims to determine the optimal kernel from several pre-computed basic kernels. Most of MKC algorithms follow a common assumption that the optimal kernel is linearly combined by basic kernels. Based on a min–max ...
Highlights
- A novel module encourages more kernels participating in the min–max optimization.
- The sparsity of kernel weight helps balance between the adaptive kernel and average one.
- We have designed an efficient and effective algorithm with ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

MM '22: Proceedings of the 30th ACM International Conference on Multimedia

October 2022

7537 pages

ISBN:9781450392037

DOI:10.1145/3503161

General Chairs:
João Magalhães
NOVA University of Lisbon, Portugal
,
Alberto del Bimbo
University of Florence, Italy
,
Shin'ichi Satoh
National Institute of Informatics, Japan
,
Nicu Sebe
University of Trento, Italy
,
Program Chairs:
Xavier Alameda-Pineda
Inria, Grenoble, France
,
Qin Jin
Renmin University of China, China
,
Vincent Oria
New Jersey Institute of Technology, USA
,
Laura Toni
University College London, UK

Copyright © 2022 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGMM: ACM Special Interest Group on Multimedia

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 10 October 2022

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Conference

MM '22

Sponsor:

SIGMM

MM '22: The 30th ACM International Conference on Multimedia

October 10 - 14, 2022

Lisboa, Portugal

Acceptance Rates

Overall Acceptance Rate 995 of 4,171 submissions, 24%

Upcoming Conference

MM '24

Sponsor:
sigmm

The 32nd ACM International Conference on Multimedia

October 28 - November 1, 2024

Melbourne , VIC , Australia

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
175
Total Downloads

Downloads (Last 12 months)63
Downloads (Last 6 weeks)3

Reflects downloads up to 03 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Liu YYang XZhou SLiu XWang SLiang KTu WLi L(2024)Simple Contrastive Graph ClusteringIEEE Transactions on Neural Networks and Learning Systems10.1109/TNNLS.2023.327187135:10(13789-13800)Online publication date: Oct-2024
https://doi.org/10.1109/TNNLS.2023.3271871
Gong LTu WZhou SZhao LLiu ZLiu X(2024)Deep Fusion Clustering Network With Reliable Structure PreservationIEEE Transactions on Neural Networks and Learning Systems10.1109/TNNLS.2022.322091435:6(7792-7803)Online publication date: Jun-2024
https://doi.org/10.1109/TNNLS.2022.3220914
Wu XRen ZYu F(2024)Parameter-Free Shifted Laplacian Reconstruction for Multiple Kernel ClusteringIEEE/CAA Journal of Automatica Sinica10.1109/JAS.2023.12360011:4(1072-1074)Online publication date: Apr-2024
https://doi.org/10.1109/JAS.2023.123600
Li XSun YSun QDai JRen ZEl Saddik AMei TCucchiara RBertini MTobon Vallejo DAtrey PHossain M(2023)Distribution Consistency based Fast Anchor Imputation for Incomplete Multi-view ClusteringProceedings of the 31st ACM International Conference on Multimedia10.1145/3581783.3612483(368-376)Online publication date: 26-Oct-2023
https://dl.acm.org/doi/10.1145/3581783.3612483
Liu YLiang KXia JYang XZhou SLiu MLiu XLi SEl Saddik AMei TCucchiara RBertini MTobon Vallejo DAtrey PHossain M(2023)Reinforcement Graph Clustering with Unknown Cluster NumberProceedings of the 31st ACM International Conference on Multimedia10.1145/3581783.3612155(3528-3537)Online publication date: 26-Oct-2023
https://dl.acm.org/doi/10.1145/3581783.3612155
Liu MLiang KHu DYu HLiu YMeng LTu WZhou SLiu XEl Saddik AMei TCucchiara RBertini MTobon Vallejo DAtrey PHossain M(2023)TMac: Temporal Multi-Modal Graph Learning for Acoustic Event ClassificationProceedings of the 31st ACM International Conference on Multimedia10.1145/3581783.3611853(3365-3374)Online publication date: 26-Oct-2023
https://dl.acm.org/doi/10.1145/3581783.3611853
Li LZhang JWang SLiu XLi KLi K(2023)Multi-View Bipartite Graph Clustering With Coupled Noisy Feature FilterIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2023.326821535:12(12842-12854)Online publication date: 27-Apr-2023
https://dl.acm.org/doi/10.1109/TKDE.2023.3268215
Jin JWang SDong ZLiu XZhu E(2023)Deep Incomplete Multi-View Clustering with Cross-View Partial Sample and Prototype Alignment2023 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)10.1109/CVPR52729.2023.01116(11600-11609)Online publication date: Jun-2023
https://doi.org/10.1109/CVPR52729.2023.01116

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents