Deep spectral clustering algorithm with L1 regularization

doi:10.11772/j.issn.1001-9081.2022121822

Journal of Computer Applications ›› 2023, Vol. 43 ›› Issue (12): 3662-3667.DOI: 10.11772/j.issn.1001-9081.2022121822

Special Issue: 人工智能

• Artificial intelligence • Previous Articles Next Articles

Deep spectral clustering algorithm with L1 regularization

Wenbo LI¹^,², Bo LIU¹^,²(), Lingling TAO¹^,², Fen LUO¹^,², Hang ZHANG¹^,²

^1.School of Artificial Intelligence，Chongqing Technology and Business University，Chongqing 400067，China
^2.Chongqing Key Laboratory of Intelligent Perception and Block Chain Technology （Chongqing Technology and Business University），Chongqing 400067，China

Received:2022-12-06 Revised:2023-02-20 Accepted:2023-02-27 Online:2023-03-03 Published:2023-12-10
Contact: Bo LIU
About author:LI Wenbo， born in 1998， M. S. candidate. His research interests include deep clustering， unsupervised learning， computer vision.
TAO Lingling， born in 1998， M. S. candidate. Her research interests include computer vision， image processing， generative adversarial network.
LUO Fen， born in 1975， M. S.，lecturer. His research interests include computer vision， medical image processing.
ZHANG Hang， born in 1998， M. S. candidate. His research interests include machine learning， computer vision， deep clustering.
Supported by:
Science and Technology Research Program of Chongqing Municipal Education Commission(KJZD-K202200803);Chongqing Natural Science Foundation(cstc2018jcyjAX0057);Graduate Innovative Scientific Research Project of Chongqing Technology and Business University(yjscxx2022-112-68)

L1正则化的深度谱聚类算法

李文博¹^,², 刘波¹^,²(), 陶玲玲¹^,², 罗棻¹^,², 张航¹^,²

^1.重庆工商大学人工智能学院，重庆 400067
^2.智能感知与区块链技术重庆市重点实验室（重庆工商大学），重庆 400067

通讯作者: 刘波
作者简介:李文博（1998—），男，重庆人，硕士研究生，主要研究方向：深度聚类、无监督学习、计算机视觉
陶玲玲（1998—），女，重庆人，硕士研究生，主要研究方向：计算机视觉、图像处理、生成对抗网络
罗棻（1975—），男，重庆人，讲师，硕士，主要研究方向：计算机视觉、医学图像处理
张航（1998—），男，重庆人，硕士研究生，主要研究方向：机器学习、计算机视觉、深度聚类。
基金资助:
重庆市教委科学技术研究项目(KJZD?K202200803);重庆市自然科学基金资助项目(cstc2018jcyjAX0057);重庆工商大学研究生“创新型科研项目”(yjscxx2022?112?68)

Abstract

Abstract:

Aiming at the problems that the deep spectral clustering models perform poorly in training stability and generalization capability， a Deep Spectral Clustering algorithm with L1 Regularization （DSCLR） was proposed. Firstly， L1 regularization was introduced into the objective function of deep spectral clustering to sparsify the eigen vectors of the Laplacian matrix generated by the deep neural network model. And the generalization capability of the model was enhanced. Secondly， the network structure of the spectral clustering algorithm based on deep neural network was improved by using the Parametric Rectified Linear Unit activation function （PReLU） to solve the problems of model training instability and underfitting. Experimental results on MNIST dataset show that the proposed algorithm improves Clustering Accuracy （CA）， Normalized Mutual Information （NMI） index， and Adjusted Rand Index （ARI） by 11.85， 7.75， and 17.19 percentage points compared to the deep spectral clustering algorithm， respectively. Furthermore， the proposed algorithm also significantly improves the three evaluation metrics， CA， NMI and ARI， compared to algorithms such as Deep Embedded Clustering （DEC） and Deep Spectral Clustering using Dual Autoencoder Network （DSCDAN）.

Key words: deep clustering, spectral clustering, L1 regularization, deep learning, unsupervised learning

摘要：

针对深度谱聚类模型训练不稳定和泛化能力弱等问题，提出L1正则化的深度谱聚类算法（DSCLR）。首先，在深度谱聚类的目标函数中引入L1正则化，使深度神经网络模型生成的拉普拉斯矩阵的特征向量稀疏化，并提升模型的泛化能力；其次，通过利用参数化修正线性单元激活函数（PReLU）改进基于深度神经网络的谱聚类算法的网络结构，解决模型训练不稳定和欠拟合问题。在MNIST数据集上的实验结果表明，所提算法在聚类精度（CA）、归一化互信息（NMI）指数和调整兰德系数（ARI）这3个评价指标上，相较于深度谱聚类算法分别提升了11.85、7.75和17.19个百分点。此外，所提算法相较于深度嵌入聚类（DEC）和基于对偶自编码器网络的深度谱聚类（DSCDAN）等算法，在CA、NMI和ARI这3个评价指标上也有大幅提升。

关键词: 深度聚类, 谱聚类, L1正则化, 深度学习, 无监督学习

CLC Number:

TP311.5

Wenbo LI, Bo LIU, Lingling TAO, Fen LUO, Hang ZHANG. Deep spectral clustering algorithm with L1 regularization[J]. Journal of Computer Applications, 2023, 43(12): 3662-3667.

李文博, 刘波, 陶玲玲, 罗棻, 张航. L1正则化的深度谱聚类算法[J]. 《计算机应用》唯一官方网站, 2023, 43(12): 3662-3667.

Figures/Tables 8

Fig.1 Overall framework of DSCLR model

Tab.1 Network architecture of DSCLR

模块	网络结构
模块	全连接层维度	激活函数
自编码器模块	$[d, 1 024]$	ReLU
	$[1 024,512]$	ReLU
	$[512, k]$	—
特征映射模块	$[k, 1 024]$	ReLU
	$[1 024,2 048]$	ReLU
	$[2 048,1 024]$	ReLU
	$[2 048,1 024]$	ReLU
	$[512, k]$	PReLU

Tab.1 Network architecture of DSCLR

模块	网络结构
模块	全连接层维度	激活函数
自编码器模块	$[d, 1 024]$	ReLU
	$[1 024,512]$	ReLU
	$[512, k]$	—
特征映射模块	$[k, 1 024]$	ReLU
	$[1 024,2 048]$	ReLU
	$[2 048,1 024]$	ReLU
	$[2 048,1 024]$	ReLU
	$[512, k]$	PReLU

Fig. 2 Some images in COIL20 dataset

Tab.2 Dataset details

数据集	样本数	类别数	数据维度
MNIST	70 000	10	28×28×1
USPS	9 298	10	28×28×1
FASHION	70 000	10	28×28×1
DIGITS	28 000	10	28×28×1
COIL20	1 440	20	128×128×1

Tab.3 CA，NMI and ARI values of different algorithms on different datasets

算法	MNIST			DIGITS			USPS			COIL20			FASHION
算法	CA	NMI	ARI	CA	NMI	ARI	CA	NMI	ARI	CA	NMI	ARI	CA	NMI	ARI
k-means	50.14	54.67	38.10	49.44	58.67	38.83	56.61	61.39	46.33	76.16	62.85	50.91	51.46	48.3	34.98
AC	71.14	69.48	60.63	66.44	63.65	52.37	61.69	57.30	44.74	80.95	68.06	57.46	52.59	51.31	34.78
DBSCAN	23.56	20.55	4.22	24.34	19.70	4.34	8.53	20.58	1.78	3.17	8.33	0.13	25.11	20.95	2.47
SC	66.71	60.23	49.32	72.45	72.09	58.57	67.79	58.94	51.89	79.11	62.15	56.92	57.85	51.73	38.51
DEC	84.40	81.60	79.50	78.40	80.05	76.33	61.90	58.60	55.40	61.00	62.10	55.32	57.81	62.83	45.71
SpectralNet	73.75	72.17	63.63	84.11	87.91	82.47	63.53	60.65	53.03	50.47	46.95	49.20	58.41	66.06	46.30
SCDE	83.31	79.02	81.31	86.79	85.91	84.19	64.67	67.04	56.97	64.56	67.86	54.56	49.29	66.45	49.29
DSCDAN	77.60	74.50	78.34	85.40	80.10	86.25	69.80	65.20	57.56	47.60	64.20	53.64	54.60	55.60	40.82
DSCLR	85.60	79.92	80.82	90.97	88.50	87.13	65.97	61.39	53.16	69.44	70.26	61.25	65.88	66.82	46.72

Fig.3 t-SNE visualization results on MNIST dataset

Fig.4 Influence of β value on evaluation indexes on MNIST dataset

Fig.5 Influence of different training strategies on algorithm performance

References 38

1	GUO X， LIU X， ZHU E， et al. Adaptive self-paced deep clustering with data augmentation［J］. IEEE Transactions on Knowledge and Data Engineering， 2019， 32（9）： 1680-1693. 10.1109/TKDE.2019.2911833
2	JAIN A K， MURTY M N， FLYNN P J. Data clustering： a review［J］. ACM Computing Surveys （CSUR）， 1999， 31（3）： 264-323. 10.1145/331499.331504
3	刘海杨，孟令航，林仲航，等.基于轨迹点聚类的航路发现方法［J］. 计算机应用， 2022， 42（3）： 890-894.
	LIU H Y， MENG L H， LIN Z H， et al. GU. Route discovery method based on trajectory point clustering［J］. Journal of Computer Applications， 2022， 42（3）： 890-894.
4	祝承，赵晓琦，赵丽萍，等. 基于谱聚类半监督特征选择的功能磁共振成像数据分类［J］. 计算机应用， 2021， 41（8）： 2288-2293. 10.11772/j.issn.1001-9081.2020101553
	ZHU C， ZHAO X Q， ZHAO L P， et al. Classification of functional magnetic resonance imaging data based on semi-supervised feature selection by spectral clustering［J］. Journal of Computer Applications， 2021， 41（8）： 2288-2293. 10.11772/j.issn.1001-9081.2020101553
5	袁野，谭晓阳. 复杂环境下的冰箱金属表面缺陷检测［J］. 计算机应用， 2021， 41（1）： 270-274.
	YUAN Y， TAN X Y. Defect detection of refrigerator metal surface in complex environment［J］. Journal of Computer Applications， 2021， 41（1）： 270-274.
6	曾祥银，郑伯川，刘丹. 基于深度卷积神经网络和聚类的左右轨道线检测［J］. 计算机应用， 2021， 41（8）： 2324-2329. 10.11772/j.issn.1001-9081.2021030385
	ZENG X Y， ZHENG B C， LIU D. Detection of left and right railway tracks based on deep convolutional neural network and clustering［J］. Journal of Computer Applications， 2021， 41（8）： 2324-2329. 10.11772/j.issn.1001-9081.2021030385
7	KANUNGO T， MOUNT D M， NETANYAHU N S， et al. An efficient k-means clustering algorithm： analysis and implementation［J］. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2002， 24（7）： 881-892. 10.1109/tpami.2002.1017616
8	VON L U. A tutorial on spectral clustering［J］. Statistics and Computing， 2007， 17（4）： 395-416. 10.1007/s11222-007-9033-z
9	ACKERMANN M R， BLÖMER J， KUNTZE D， et al. Analysis of agglomerative clustering［J］. Algorithmica， 2014， 69（1）： 184-215. 10.1007/s00453-012-9717-4
10	ESTER M， KRIEGEL H P， SANDER J， et al. A density-based algorithm for discovering clusters in large spatial databases with noise ［EB/OL］. ［2022-10-20］. . 10.1007/3-540-48238-5_5
11	XIE J， GIRSHICK R， FARHADI A. Unsupervised deep embedding for clustering analysis［C］// Proceedings of the 33th International Conference on Machine Learning. ［S.l.］： PMLR， 2016： 478-487.
12	YANG B， FU X， SIDIROPOULOS N D， et al. Towards K-means-friendly spaces： simultaneous deep learning and clustering［C］// Proceedings of the 34th International Conference on Machine Learning. ［S.l.］： PMLR， 2017： 3861-3870.
13	SHAHAM U， STANTON K， LI H， et al. SpectralNet： spectral clustering using deep neural networks ［C］// Proceedings of the 6th International Conference on Learning Representations. Vancouver： OpenReview.net， 2018， 1050： 10.
14	YANG X， DENG C， ZHENG F， et al. Deep spectral clustering using dual autoencoder network［C］// Proceedings of the 2019 IEEE/CVF Conference on Computer Vision and Pattern Recognition. Piscataway： IEEE， 2019： 4066-4075. 10.1109/cvpr.2019.00419
15	HE K， ZHANG X， REN S， et al. Delving deep into rectifiers： surpassing human-level performance on ImageNet classification ［C］// Proceedings of the 2015 IEEE/CVF International Conference on Computer Vision. Washington， DC： IEEE Computer Society， 2015： 1026-1034. 10.1109/iccv.2015.123
16	苏常保，龚世才.一种基于卷积神经网络的谱聚类算法［J］.安徽大学学报（自然科学版），2022，46（5）：20-26.
	SU C B， GONG S C. A spectral clustering algorithm based on convolutional neural network［J］. Journal of Anhui University（Natural Sciences）， 2022，46（5）：20-26.
17	YE X， ZHAO J， CHEN Y， et al. Bayesian adversarial spectral clustering with unknown cluster number ［J］. IEEE Transactions on Image Processing， 2020， 29： 8506-8518. 10.1109/tip.2020.3016491
18	JI P， ZHANG T， LI H，et al.Deep subspace clustering networks［C］// Proceedings of the 30th Advances in Neural Information Processing Systems. Long Beach： Curran Associates Inc.， 2017：24-33.
19	ZHOU L， WANG S， BAI X，et al.Iterative deep subspace clustering［C］// Proceedings of the 2018 Joint IAPR International Workshop Structural，Syntactic，and Statistical Pattern Recognition. Cham： Springer， 2018：42-51. 10.1007/978-3-319-97785-0_5
20	HUANG S， OTA K， DONG M， et al. MultiSpectralNet： spectral clustering using deep neural network for multi-view data［J］. IEEE Transactions on Computational Social Systems， 2019， 6（4）： 749-760. 10.1109/tcss.2019.2926450
21	BIANCHIF M， GRATTAROLA D， ALIPPI C. Spectral clustering with graph neural networks for graph pooling ［C］// Proceedings of the 37th International Conference on Machine Learning. ［S.l.］： PMLR， 2020： 874-883.
22	TIBSHIRANI R. Regression shrinkage and selection via the lasso： a retrospective［J］. Journal of the Royal Statistical Society： Series B （Statistical Methodology）， 2011， 73（3）： 273-282. 10.1111/j.1467-9868.2011.00771.x
23	TIBSHIRANI R. Regression shrinkage and selection via the lasso［J］. Journal of the Royal Statistical Society： Series B （Methodological）， 1996， 58（1）： 267-288. 10.1111/j.2517-6161.1996.tb02080.x
24	刘建伟，李双成，付捷，等.L1范数正则化SVM聚类算法［J］.计算机工程，2012，38（12）：185-187. 10.3969/j.issn.1000-3428.2012.12.055
	LIU J W， LI S C， FU J， et al. L1-norm regularized SVM clustering algorithm［J］. Computer Engineering， 2012，38（12）：185-187. 10.3969/j.issn.1000-3428.2012.12.055
25	KAWALE J， BOLEY D. Constrained spectral clustering using L1 regularization［C］// Proceedings of the 2013 SIAM International Conference on Data Mining. Philadelphia，PA： SIAM， 2013： 103-111. 10.1137/1.9781611972832.12
26	LEMHADRI I， RUAN F， TIBSHIRANI R. LassoNet： neural networks with feature sparsity［C］// Proceedings of the 24th International Conference on Artificial Intelligence and Statistics. ［S.l.］： PMLR， 2021： 10-18.
27	LIU K， WANG H. High-order co-clustering via strictly orthogonal and symmetric L1-norm nonnegative matrix tri-factorization［C］//Proceedings of the 27th International Joint Conference on Artificial Intelligence. Menlo Park， CA： AAAI Press， 2018： 2454-2460. 10.24963/ijcai.2018/340
28	ZHAO M， LIU J. Robust clustering with sparse corruption via ℓ2， 1， ℓ1 norm constraint and Laplacian regularization［J］. Expert Systems with Applications， 2021， 186： 115704. 10.1016/j.eswa.2021.115704
29	BAGIROV A M， MOHEBI E. An algorithm for clustering using L1-norm based on hyperbolic smoothing technique［J］. Computational Intelligence， 2016， 32（3）： 439-457. 10.1111/coin.12062
30	DENG L. The MNIST database of handwritten digit images for machine learning research ［J］. IEEE Signal Processing Magazine， 2012， 29（6）：141-142.. 10.1109/msp.2012.2211477
31	HULL J J. A database for handwritten text recognition research［J］. IEEE Transactions on Pattern Analysis and Machine Intelligence， 1994， 16（5）： 550-554. 10.1109/34.291440
32	COHEN G， AFSHAR S， TAPSON J， et al. EMNIST： extending MNIST to handwritten letters［C］// Proceedings of the 13th International Joint Conference on Neural Networks. Piscataway： IEEE， 2017： 2921-2926. 10.1109/ijcnn.2017.7966217
33	XIAO H， RASUL K， VOLLGRAF R. Fashion-MNIST： a novel image dataset for benchmarking machine learning algorithms ［EB/OL］. ［2022-10-20］. .
34	NENE S A. Columbia object image library ［DB/OL］. ［2022-10-20］. .
35	DUAN L， MA S， AGGARWAL C， et al. Improving spectral clustering with deep embedding， cluster estimation and metric learning［J］. Knowledge and Information Systems， 2021， 63（3）： 675-694. 10.1007/s10115-020-01530-8
36	CAI D， HE X， HAN J. Locally consistent concept factorization for document clustering［J］. IEEE Transactions on Knowledge and Data Engineering， 2010， 23（6）： 902-913. 10.1109/tkde.2010.165
37	VINH N， EPPS J， BAILEY J. Information theoretic measures for clusterings comparison： is a correction for chance necessary？［C］//Proceedings of the 26th Annual International Conference on Machine Learning. New York： ACM， 2009： 1073-1080. 10.1145/1553374.1553511
38	VAN DER MAATEN L， HINTON G. Visualizing data using t-SNE［J］. Journal of Machine Learning Research， 2008， 9（11）： 2579-2605.

[1]	Shunyong LI, Shiyi LI, Rui XU, Xingwang ZHAO. Incomplete multi-view clustering algorithm based on self-attention fusion [J]. Journal of Computer Applications, 2024, 44(9): 2696-2703.
[2]	Yexin PAN, Zhe YANG. Optimization model for small object detection based on multi-level feature bidirectional fusion [J]. Journal of Computer Applications, 2024, 44(9): 2871-2877.
[3]	Yunchuan HUANG, Yongquan JIANG, Juntao HUANG, Yan YANG. Molecular toxicity prediction based on meta graph isomorphism network [J]. Journal of Computer Applications, 2024, 44(9): 2964-2969.
[4]	Jieru JIA, Jianchao YANG, Shuorui ZHANG, Tao YAN, Bin CHEN. Unsupervised person re-identification based on self-distilled vision Transformer [J]. Journal of Computer Applications, 2024, 44(9): 2893-2902.
[5]	Jing QIN, Zhiguang QIN, Fali LI, Yueheng PENG. Diagnosis of major depressive disorder based on probabilistic sparse self-attention neural network [J]. Journal of Computer Applications, 2024, 44(9): 2970-2974.
[6]	Xiyuan WANG, Zhancheng ZHANG, Shaokang XU, Baocheng ZHANG, Xiaoqing LUO, Fuyuan HU. Unsupervised cross-domain transfer network for 3D/2D registration in surgical navigation [J]. Journal of Computer Applications, 2024, 44(9): 2911-2918.
[7]	Yuhan LIU, Genlin JI, Hongping ZHANG. Video pedestrian anomaly detection method based on skeleton graph and mixed attention [J]. Journal of Computer Applications, 2024, 44(8): 2551-2557.
[8]	Yanjie GU, Yingjun ZHANG, Xiaoqian LIU, Wei ZHOU, Wei SUN. Traffic flow forecasting via spatial-temporal multi-graph fusion [J]. Journal of Computer Applications, 2024, 44(8): 2618-2625.
[9]	Qianhong SHI, Yan YANG, Yongquan JIANG, Xiaocao OUYANG, Wubo FAN, Qiang CHEN, Tao JIANG, Yuan LI. Multi-granularity abrupt change fitting network for air quality prediction [J]. Journal of Computer Applications, 2024, 44(8): 2643-2650.
[10]	Yiqun ZHAO, Zhiyu ZHANG, Xue DONG. Anisotropic travel time computation method based on dense residual connection physical information neural networks [J]. Journal of Computer Applications, 2024, 44(7): 2310-2318.
[11]	Song XU, Wenbo ZHANG, Yifan WANG. Lightweight video salient object detection network based on spatiotemporal information [J]. Journal of Computer Applications, 2024, 44(7): 2192-2199.
[12]	Xun SUN, Ruifeng FENG, Yanru CHEN. Monocular 3D object detection method integrating depth and instance segmentation [J]. Journal of Computer Applications, 2024, 44(7): 2208-2215.
[13]	Zheng WU, Zhiyou CHENG, Zhentian WANG, Chuanjian WANG, Sheng WANG, Hui XU. Deep learning-based classification of head movement amplitude during patient anaesthesia resuscitation [J]. Journal of Computer Applications, 2024, 44(7): 2258-2263.
[14]	Huanhuan LI, Tianqiang HUANG, Xuemei DING, Haifeng LUO, Liqing HUANG. Public traffic demand prediction based on multi-scale spatial-temporal graph convolutional network [J]. Journal of Computer Applications, 2024, 44(7): 2065-2072.
[15]	Zhi ZHANG, Xin LI, Naifu YE, Kaixi HU. DKP： defending against model stealing attacks based on dark knowledge protection [J]. Journal of Computer Applications, 2024, 44(7): 2080-2086.

Deep spectral clustering algorithm with L1 regularization

L1正则化的深度谱聚类算法

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 8

References 38

Related Articles 15

Recommended Articles

Metrics