非负拉格朗日松弛优化的子空间聚类算法

朱东霞; 贾洪杰; 黄龙霞

doi:10.19665/j.issn1001-2400.20230204

您当前的位置：

首页 >

文章列表页 >

非负拉格朗日松弛优化的子空间聚类算法

计算机科学与技术 | 更新时间：2024-04-03

- 非负拉格朗日松弛优化的子空间聚类算法
- Subspace clustering algorithm optimized by non-negative Lagrangian relaxation
- 西安电子科技大学学报 2024年51卷第1期页码：100-113
- 作者机构：
  
  江苏大学计算机科学与通信工程学院,江苏镇江 212013
- 作者简介：
  
  [ "朱东霞(1998—),女,江苏大学硕士研究生,E-mail:[email protected];" ]
  贾洪杰(1988—),男,副教授,E-mail:[email protected]
  [ "黄龙霞(1991—),女,副教授,E-mail:[email protected]" ]
- 基金信息：
  
  国家自然科学青年基金(61906077);国家自然科学青年基金(62102168);江苏省自然科学青年基金(BK20190838);江苏省自然科学青年基金(BK20200888);中国博士后科学基金(2020T130257);中国博士后科学基金(2020M671376);江苏省博士后科学基金(2021K596C)
- DOI：10.19665/j.issn1001-2400.20230204
  中图分类号： TN96
- 收稿日期：2022-10-17，
  
  网络出版日期：2023-09-14，
  
  纸质出版日期：2024-01-20
- 稿件说明：
移动端阅览
朱东霞, 贾洪杰, 黄龙霞. 非负拉格朗日松弛优化的子空间聚类算法[J]. 西安电子科技大学学报, 2024,51(1):100-113.

Dongxia ZHU, Hongjie JIA, Longxia HUANG. Subspace clustering algorithm optimized by non-negative Lagrangian relaxation[J]. Journal of xidian university, 2024, 51(1): 100-113.
朱东霞, 贾洪杰, 黄龙霞. 非负拉格朗日松弛优化的子空间聚类算法[J]. 西安电子科技大学学报, 2024,51(1):100-113. DOI： 10.19665/j.issn1001-2400.20230204.

Dongxia ZHU, Hongjie JIA, Longxia HUANG. Subspace clustering algorithm optimized by non-negative Lagrangian relaxation[J]. Journal of xidian university, 2024, 51(1): 100-113. DOI： 10.19665/j.issn1001-2400.20230204.

摘要

传统的子空间聚类和谱聚类中普遍使用谱松弛方法聚类

需要先计算拉普拉斯矩阵的特征向量。特征向量中包含负数

根据元素的正负可以直接得到二类聚类的结果。对于多类聚类问题

需要递归地进行二划分

或在特征向量空间中使用

-means算法聚类

分配类簇标签是间接的

这种后处理的聚类方式会增加聚类结果的不稳定性。针对谱松弛的问题

提出了一种非负拉格朗日松弛优化的子空间聚类算法

在目标函数中集成了自表示学习和秩约束。通过非负拉格朗日松弛来求解相似性矩阵和隶属矩阵

并保持隶属矩阵的非负性。在这种情况下

原来的隶属矩阵就变成了类簇的后验概率

当算法收敛时

只需将数据点分配给具有最大后验概率的类簇

即可得到聚类结果。与已有的子空间聚类和谱聚类方法相比

所提出的算法设计了新的优化规则

可以实现类簇标签的直接分配

不需要额外的聚类步骤。最后

给出了算法的收敛性证明。在5个基准聚类数据集上的大量实验表明

所提算法的聚类性能优于近几年来的子空间聚类方法。

Abstract

Spectral relaxation is widely used in traditional subspace clustering and spectral clustering.First

the eigenvector of the Laplacian matrix is calculated.The eigenvector contains negative numbers

and the result of the 2-way clustering can be obtained directly according to the positive and negative of the elements.For multi-way clustering problems

2-way graph partition is applied recursively or the

-means is used in eigenvector space.The assignment of the cluster label is indirect.The instability of clustering results will increase by this post-processing clustering method.For the limitation of spectral relaxation

a subspace clustering algorithm optimized by non-negative Lagrangian relaxation is proposed

which integrates self-representation learning and rank constraints in the objective function.The similarity matrix and membership matrix are solved by non-negative Lagrangian relaxation and the nonnegativity of the membership matrix is maintained.In this way

the membership matrix becomes the cluster posterior probability.When the algorithm converges

the clustering results can be obtained directly by assigning the data object to the cluster with the largest posterior probability.Compared with the existing subspace clustering and spectral clustering methods

the proposed algorithm designs a new optimization rule

which can realize the direct allocation of cluster labels without additional clustering steps.Finally

the convergence of the proposed algorithm is analyzed theoretically.Generous experiments on five benchmark clustering datasets show that the clustering performance of the proposed method is better than that of the recent subspace clustering methods.

关键词

Keywords

references

ANAND S K , KUMAR S . Experimental Comparisons of Clustering Approaches for Data Representation [J]. ACM Computing Surveys(CSUR) , 2022 , 55 ( 3 ): 1 - 33 .

张春祥 , 周雪松 , 高雪瑶 , 等 . 融合 k 均值聚类与LSTM网络的半监督词义消歧 [J]. 西安电子科技大学学报 , 2021 , 48 ( 6 ): 161 - 171 .

ZHANG Chunxiang , ZHOU Xuesong , GAO Xueyao , et al. Semi-Supervised Word Sense Disambiguation by Combining k -Means Clustering and the LSTM Network [J]. Journal of Xidian University , 2021 , 48 ( 6 ): 161 - 171 .

SHI S , NIE F , WANG R , et al. Self-Weighting Multi-View Spectral Clustering Based on Nuclear Norm [J]. Pattern Recognition , 2022 , 124 : 108429 .

WU C , PENG Q , LEE J , et al. Effective Hierarchical Clustering Based on Structural Similarities in Nearest Neighbor Graphs [J]. Knowledge-Based Systems , 2021 , 228 : 107295 .

冯少荣 , 肖文俊 . 一种提高DBSCAN聚类算法质量的新方法 [J]. 西安电子科技大学学报 , 2008 , 35 ( 3 ): 523 - 529 .

FENG Shaorong , XIAO Wenjun . New Method to Improve DBSCAN Clustering Algorithm Quality [J]. Journal of Xidian University , 2008 , 35 ( 3 ): 523 - 529 .

任佳兴 , 曹玉东 , 曹睿 , 等 . 一种采用动态子空间的小样本图像分类算法 [J]. 西安电子科技大学学报 , 2022 , 49 ( 5 ): 166 - 174 .

REN Jiaxing , CAO Yudong , CAO Rui , et al. Algorithm for Classification of Few-Shot Images by Dynamic Subspace [J]. Journal of Xidian University , 2022 , 49 ( 5 ): 166 - 174 .

AGRAWAL R , GEHRKE J , GUNOPULOS D , et al. Automatic Subspace Clustering of High Dimensional Data for Data Mining Applications[C]// Proceedings of the 1998 ACM SIGMOD International Conference on Management of Data . New York : ACM , 1998 : 94 - 105 .

PENG X , FENG J , XIAO S , et al. Structured Autoencoders for Subspace Clustering [J]. IEEE Transactions on Image Processing , 2018 , 27 ( 10 ): 5076 - 5086 .

GAO H , NIE F , LI X , et al. Multi-View Subspace Clustering[C]//Proceedings of the IEEE International Conference on Computer Vision . Piscataway:IEEE , 2015 : 4238 - 4246 .

PENG C , ZHANG Q , KANG Z , et al. Kernel Two-Dimensional Ridge Regression for Subspace Clustering [J]. Pattern Recognition , 2021 , 113 : 107749 .

VIDAL R . Subspace Clustering [J]. IEEE Signal Processing Magazine , 2011 , 28 ( 2 ): 52 - 68 .

LIU G , LIN Z , YAN S , et al. Robust Recovery of Subspace Structures by Low-Rank Representation [J]. IEEETransactions on Pattern Analysis and Machine Intelligence , 2012 , 35 ( 1 ): 171 - 184 .

ELHAMIFAR E , VIDAL R . Sparse Subspace Clustering:Algorithm, Theory, and Applications [J]. IEEETransactions on Pattern Analysis and Machine Intelligence , 2013 , 35 ( 11 ): 2765 - 2781 .

CAI B , LU G F . Tensor Subspace Clustering Using Consensus Tensor Low-Rank Representation [J]. Information Sciences , 2022 , 609 : 46 - 59 .

ABHADIOMHEN S E , WANG Z Y , SHEN X J . Coupled Low Rank Representation and Subspace Clustering [J]. Applied Intelligence , 2022 , 52 ( 1 ): 530 - 546 .

DING C , HE X , SIMON H D . NonnegativeLagrangian Relaxation of K-Means and Spectral Clustering[C]//European Conference on Machine Learning . Heidelberg:Springer , 2005 : 530 - 538 .

LU C Y , MIN H , ZHAO Z Q , et al. Robust and Efficient Subspace Segmentation via Least Squares Regression[C]//European Conference on Computer Vision . Heidelberg:Springer , 2012 : 347 - 360 .

HUANG J , NIE F , HUANG H . A New Simplex Sparse Learning Model to Measure Data Similarity for Clustering[C]// Twenty-Fourth International Joint Conference on Artificial Intelligence . New York : ACM , 2015 : 3569 - 3575 .

YOU C Z , SHU Z Q , FAN H H . Low-Rank Sparse Subspace Clustering with a Clean Dictionary [J]. Journal of Algorithms & Computational Technology , 2021 , 15 : 1748302620983690.

LIU G , ZHANG Z , LIU Q , et al. Robust Subspace Clustering with Compressed Data [J]. IEEE Transactions on Image Processing , 2019 , 28 ( 10 ): 5161 - 5170 .

NG A , JORDAN M , WEISS Y . On Spectral Clustering:Analysis and an Algorithm[C]//Advances in Neural Information Processing Systems 14 . San Diego:NIPS , 2001 : 849 - 856 .

续拓 , 李洁 , 王颖 . 叠加信息熵游走数据聚类算法 [J]. 西安电子科技大学学报 , 2018 , 45 ( 4 ): 75 - 79 .

XU Tuo , LI Jie , WANG Ying . Clustering by Samples Movement in the Superposition Information Entropy Field [J]. Journal of Xidian University , 2018 , 45 ( 4 ): 75 - 79 .

XIA R , PAN Y , DU L , et al. Robust Multi-View Spectral Clustering via Low-Rank and Sparse Decomposition[C]//Proceedings of the AAAI Conference on Artificial Intelligence . Palo Alto : AAAI , 2014 : 2149 - 2155 .

LI Y , NIE F , HUANG H , et al. Large-Scale Multi-View Spectral Clustering via Bipartite Graph[C]//Twenty-Ninth AAAI Conference on Artificial Intelligence . Palo Alto : AAAI , 2015 : 2750 - 2756 .

XUE X , NIE F , WANG S , et al. Multi-View Correlated Feature Learning by Uncovering Shared Component[C]//Proceedings of the AAAI Conference on Artificial Intelligence . Palo Alto : AAAI , 2017 : 2810 - 2816 .

CHEN J , MAO H , WANG Z , et al. Low-Rank Representation with Adaptive Dictionary Learning for Subspace Clustering [J]. Knowledge-Based Systems , 2021 , 223 : 107053 .

NIE F , WANG X , JORDAN M , et al. The Constrained Laplacian Rank Algorithm for Graph-Based Clustering[C]// Proceedings of the AAAI Conference on Artificial Intelligence . Palo Alto : AAAI , 2016 : 1969 - 1976 .

LUO D , NIE F , DING C , et al. Multi-Subspace Representation and Discovery[C]//Joint European Conference on Machine Learning and Knowledge Discovery in Databases . Heidelberg : Springer , 2011 : 405 - 420 .

KANG Z , PENG C , CHENG Q . Robust Subspace Clustering via Tighter Rank Approximation[C]//Proceedings of the 24th ACM International on Conference on Information and Knowledge Management . New York : ACM , 2015 : 393 - 401 .

KANG Z , PENG C , CHENG Q . Twin Learning for Similarity and Clustering:a Unified Kernel Approach [C]// Proceedings of the AAAI Conference on Artificial Intelligence . Palo Alto : AAAI , 2017 : 2080 - 2086 .

ZHU X , ZHANG S , LI Y , et al. Low-Rank Sparse Subspace for Spectral Clustering [J]. IEEE Transactions on Knowledge and Data Engineering , 2018 , 31 ( 8 ): 1532 - 1543 .

CHEN Y , LI C G , YOU C . Stochastic Sparse Subspace Clustering [C]//Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. Piscataway:IEEE , 2020 : 4155 - 4164 .

ZHAO Y , DENG F , PEI J , et al. Progressive Deep Non-Negative Matrix Factorization Architecture with Graph Convolution-Based Basis Image Reorganization [J]. Pattern Recognition , 2022 , 132 : 108984 .

DING C , LI T , PENG W , et al. Orthogonal Nonnegative Matrix T-Factorizations for Clustering [C]// Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining . New York : ACM , 2006 : 126 - 135 .

LI D , ZHONG X , DOU Z , et al. Detecting Dynamic Community by Fusing Network Embedding and Nonnegative Matrix Factorization [J]. Knowledge-Based Systems , 2021 , 221 : 106961 .

KUANG D , DING C , PARK H . Symmetric Nonnegative Matrix Factorization for Graph Clustering [C]//Proceedings of the 2012 SIAM International Conference on Data Mining. Philadelphia:SIAMS , 2012 : 106 - 117 .

ZHANG S , YOU C , VIDAL R , et al. Learning a Self-Expressive Network for Subspace Clustering [C]//Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. Piscataway:IEEE , 2021 : 12393 - 12403 .

TANG C , LIU X , ZHU X , et al. Feature Selective Projection with Low-Rank Embedding and Dual Laplacian Regularization [J]. IEEE Transactions on Knowledge and Data Engineering , 2019 , 32 ( 9 ): 1747 - 1760 .

MOHAR B . The Laplacian Spectrum of Graphs. Graph Theory,Combinatorics and Applications,Vol.2 [M]. New York : Wiley , 1991 : 871 - 898 .

FAN K . On a Theorem of Weyl Concerning Eigenvalues of Linear Transformations I [J]. Proceedings of the National Academy of Sciences , 1949 , 35 ( 11 ): 652 - 655 .

LEE D , SEUNG H S . Algorithms for Non-Negative Matrix Factorization[C]//Advances in Neural Information Processing Systems , San Diego : NIPS , 2000 : 556 - 562 .

GAO W , DAI S , ABHADIOMHEN S E , et al. Low Rank Correlation Representation and Clustering [J]. Scientific Programming , 2021 , 1 : 1 - 12 .

YANG Y , XU D , NIE F , et al. Image Clustering Using Local Discriminant Models and Global Integration [J]. IEEE Transactions on Image Processing , 2010 , 19 ( 10 ): 2761 - 2773 .

LV J , KANG Z , LU X , et al. Pseudo-Supervised Deep Subspace Clustering [J]. IEEE Transactions on Image Processing , 2021 , 30 : 5252 - 5263 .

陈昌川 , 王海宁 , 黄炼 , 等 . 一种基于局部表征的面部表情识别算法 [J]. 西安电子科技大学学报 , 2021 , 48 ( 5 ): 100 - 109 .

CHEN Changchuan , WANG Haining , HUANG Lian , et al. Facial Expression Recognition Based on Local Representation [J]. Journal of Xidian University , 2021 , 48 ( 5 ): 100 - 109 .

REN Z , SUN Q . Simultaneous Global and Local Graph Structure Preserving for Multiple Kernel Clustering [J]. IEEE Transactions on Neural Networks and Learning Systems , 2020 , 32 ( 5 ): 1839 - 1851 .

DU L , ZHOU P , SHI L , et al. Robust Multiple Kernel K-Means Using L21-Norm[C]//Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence . Palo Alto : AAAI , 2015 : 3476 - 3482 .

KANG Z , LIN Z , ZHU X , et al. Structured Graph Learning for Scalable Subspace Clustering:From Single View to Multiview [J]. IEEE Transactions on Cybernetics , 2022 , 52 ( 9 ): 8976 - 8986 .

浏览量

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

类Raptor多速率QC-LDPC码的一种优化方法

B样条曲面三维扩展目标跟踪算法

带通滤波器的优化设计和可制造性分析

一种低复杂度的雷达信号分选方法

对地侦察卫星星座优化设计及仿真分析