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

doi:10.19665/j.issn1001-2400.20230204

摘要/Abstract

摘要：

传统的子空间聚类和谱聚类中普遍使用谱松弛方法聚类,需要先计算拉普拉斯矩阵的特征向量。特征向量中包含负数,根据元素的正负可以直接得到二类聚类的结果。对于多类聚类问题,需要递归地进行二划分,或在特征向量空间中使用k-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 k-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.

Key words: clustering algorithms, self-expression, optimization, non-negative Lagrangian relaxation, subspace clustering

中图分类号:

TN96

朱东霞, 贾洪杰, 黄龙霞. 非负拉格朗日松弛优化的子空间聚类算法[J]. 西安电子科技大学学报, 2024, 51(1): 100-113.

ZHU Dongxia, JIA Hongjie, HUANG Longxia. Subspace clustering algorithm optimized by non-negative Lagrangian relaxation[J]. Journal of Xidian University, 2024, 51(1): 100-113.

图/表 7

图1

表1

表2

表3

表4

表5

图2

参考文献 48

[1]	ANAND S K, KUMAR S. Experimental Comparisons of Clustering Approaches for Data Representation[J]. ACM Computing Surveys(CSUR), 2022, 55(3):1-33.
[2]	张春祥, 周雪松, 高雪瑶, 等. 融合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.
[3]	SHI S, NIE F, WANG R, et al. Self-Weighting Multi-View Spectral Clustering Based on Nuclear Norm[J]. Pattern Recognition, 2022, 124:108429. doi: 10.1016/j.patcog.2021.108429
[4]	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. doi: 10.1016/j.knosys.2021.107295
[5]	冯少荣, 肖文俊. 一种提高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.
[6]	任佳兴, 曹玉东, 曹睿, 等. 一种采用动态子空间的小样本图像分类算法[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.
[7]	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.
[8]	PENG X, FENG J, XIAO S, et al. Structured Autoencoders for Subspace Clustering[J]. IEEE Transactions on Image Processing, 2018, 27(10):5076-5086. doi: 10.1109/TIP.2018.2848470
[9]	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.
[10]	PENG C, ZHANG Q, KANG Z, et al. Kernel Two-Dimensional Ridge Regression for Subspace Clustering[J]. Pattern Recognition, 2021, 113:107749. doi: 10.1016/j.patcog.2020.107749
[11]	VIDAL R. Subspace Clustering[J]. IEEE Signal Processing Magazine, 2011, 28(2):52-68. doi: 10.1109/MSP.2010.939739
[12]	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.
[13]	ELHAMIFAR E, VIDAL R. Sparse Subspace Clustering:Algorithm, Theory, and Applications[J]. IEEETransactions on Pattern Analysis and Machine Intelligence, 2013, 35(11):2765-2781.
[14]	CAI B, LU G F. Tensor Subspace Clustering Using Consensus Tensor Low-Rank Representation[J]. Information Sciences, 2022, 609:46-59. doi: 10.1016/j.ins.2022.07.049
[15]	ABHADIOMHEN S E, WANG Z Y, SHEN X J. Coupled Low Rank Representation and Subspace Clustering[J]. Applied Intelligence, 2022, 52(1):530-546. doi: 10.1007/s10489-021-02409-z
[16]	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.
[17]	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.
[18]	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.
[19]	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.
[20]	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. doi: 10.1109/TIP.83
[21]	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.
[22]	续拓, 李洁, 王颖. 叠加信息熵游走数据聚类算法[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.
[23]	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.
[24]	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.
[25]	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.
[26]	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. doi: 10.1016/j.knosys.2021.107053
[27]	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.
[28]	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.
[29]	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.
[30]	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.
[31]	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. doi: 10.1109/TKDE.69
[32]	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.
[33]	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. doi: 10.1016/j.patcog.2022.108984
[34]	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.
[35]	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. doi: 10.1016/j.knosys.2021.106961
[36]	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.
[37]	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.
[38]	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.
[39]	MOHAR B. The Laplacian Spectrum of Graphs. Graph Theory,Combinatorics and Applications,Vol.2[M]. New York: Wiley, 1991:871-898.
[40]	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. doi: 10.1073/pnas.35.11.652
[41]	LEE D, SEUNG H S. Algorithms for Non-Negative Matrix Factorization[C]//Advances in Neural Information Processing Systems, San Diego: NIPS, 2000:556-562.
[42]	GAO W, DAI S, ABHADIOMHEN S E, et al. Low Rank Correlation Representation and Clustering[J]. Scientific Programming, 2021, 1:1-12. doi: 10.1155/1992/125016
[43]	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. doi: 10.1109/TIP.2010.2049235 pmid: 20423802
[44]	LV J, KANG Z, LU X, et al. Pseudo-Supervised Deep Subspace Clustering[J]. IEEE Transactions on Image Processing, 2021, 30:5252-5263. doi: 10.1109/TIP.2021.3079800
[45]	陈昌川, 王海宁, 黄炼, 等. 一种基于局部表征的面部表情识别算法[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.
[46]	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. doi: 10.1109/TNNLS.2020.2991366
[47]	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.
[48]	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. doi: 10.1109/TCYB.2021.3061660

符号	解释
X∈R^d^×ⁿ	数据矩阵
S∈Rⁿ^×ⁿ	相似性矩阵
H∈Rⁿ^×^c	隶属矩阵
1	单位向量
I	单位矩阵
tr(·)	矩阵的迹
diag(·)	对角矩阵
rank(·)	矩阵的秩
‖·‖_F	F范数

数据集	类型	类别	样本	特征
YALE	人脸	15	165	1 024
AR	人脸	120	840	768
ORL	人脸	40	400	1 024
JAFFE	人脸	10	213	676
TR45	文本	10	690	8 261

数据集	谱聚类	鲁棒核k-均值	低秩表示	单纯形稀疏表示	全局结构学习方法	结构化图学习	文中方法
YALE	49.42	48.09	53.94	54.55	55.85	61.21	62.42
AR	28.83	33.43	32.02	65.00	56.79	65.13	66.79
ORL	57.96	54.96	71.50	69.00	62.35	68.83	73.00
JAFFE	74.88	75.61	70.89	87.32	99.83	98.12	99.06
TR45	57.39	58.13		71.45	74.02	73.04	77.25
平均ACC	53.70	54.04	57.09	69.46	69.77	73.27	75.70

数据集	谱聚类	鲁棒核k-均值	低秩表示	单纯形稀疏表示	全局结构学习方法	结构化图学习	文中方法
YALE	52.92	52.29	59.39	57.26	56.50	59.85	63.83
AR	58.37	65.44	67.23	84.16	76.02	82.61	84.05
ORL	75.16	74.23	84.40	84.23	78.96	80.44	84.71
JAFFE	82.08	83.47	75.73	92.93	99.35	97.32	98.59
TR45	48.03	57.86		67.82	74.24	69.96	70.27
平均NMI	63.31	66.66	71.74	77.28	76.94	78.04	80.29

数据集	谱聚类	鲁棒核k-均值	低秩表示	单纯形稀疏表示	全局结构学习方法	结构化图学习	文中方法
YALE	51.61	49.79	55.15	58.18	57.27	65.45	66.64
AR	33.24	35.87	33.33	69.52	63.45	69.16	70.95
ORL	61.45	59.60	75.25	76.50	74.00	67.50	77.75
JAFFE	76.83	79.58	74.18	96.24	99.85	98.12	99.06
TR45	61.25	68.18		83.62	78.26	83.76	86.52
平均Purity	56.88	58.60	59.48	76.81	74.57	76.80	80.18