[1]何玉林,杨振宇,肖又旗,等.一种新的稀疏表示驱动的大规模数据集成聚类算法[J].智能系统学报,2026,21(4):888-907.[doi:10.11992/tis.202509003]
HE Yulin,YANG Zhenyu,XIAO Youqi,et al.A new sparse representation-driven ensemble clustering algorithm for large-scale data[J].CAAI Transactions on Intelligent Systems,2026,21(4):888-907.[doi:10.11992/tis.202509003]
点击复制
HE Yulin,YANG Zhenyu,XIAO Youqi,et al.A new sparse representation-driven ensemble clustering algorithm for large-scale data[J].CAAI Transactions on Intelligent Systems,2026,21(4):888-907.[doi:10.11992/tis.202509003]
一种新的稀疏表示驱动的大规模数据集成聚类算法
《智能系统学报》[ISSN 1673-4785/CN 23-1538/TP] 卷:
21
期数:
2026年第4期
页码:
888-907
栏目:
学术论文—机器学习
出版日期:
2026-07-05
- Title:
- A new sparse representation-driven ensemble clustering algorithm for large-scale data
- Keywords:
- large-scale clustering; sparse representation; ensemble clustering; representative point selection; distributed computing; Spark; large-scale data; consensus function
- 分类号:
- TP391.4
- 摘要:
- 针对大规模高维数据聚类中存在的采样代表性不足与计算开销过高的问题，本文提出了一种稀疏表示驱动的集成聚类（sparse representation-driven ensemble clustering，SREC）算法。在基聚类生成阶段，SREC算法引入了随机样本划分与K-means的混合代表点采样策略，结合FAISS（facebook AI similarity search）索引构建高效稀疏图，有效克服了局部采样难以覆盖全局分布的缺陷；在共识函数构建阶段，SREC算法采用了一种非迭代的加权谱共识函数，利用Tcut（transfer cut）策略在稀疏图中实现高精度的簇划分。在分布式环境下基于Spark计算框架实现了SREC算法，通过百万级数据集对其表现进行了系统性地验证。实验结果表明：SREC算法在评价指标NMI（normalized mutual information）、ARI（adjusted Rand index）和ACC（clustering accuracy）上优于选用的10种主流聚类算法，较之次优算法获得了4.15%、3.33%以及0.98%的性能提升；同时，SREC算法具备良好的稳定性，对基聚类算法个数的变化不敏感，NMI指标标准差仅为0.21%；另外，在处理五百万级样本数据的聚类问题时，相比次优算法，SREC算法的计算效率提升了51.8%，证实了其在处理大规模数据聚类问题时的优势。本文研究结果可为大规模数据的高效聚类分析、分布式数据挖掘及相关智能应用系统设计提供参考。
- Abstract:
- To address the challenges of inadequate sampling representativeness and high computational cost in large-scale high-dimensional data clustering, this paper proposes a sparse representation-driven ensemble clustering(SREC) algorithm. In the base clustering generation stage, SREC algorithm incorporates a hybrid sampling strategy that combines random sample partitioning with K-means, along with facebook AI similarity search(FAISS) indexing to build an efficient sparse graph. This approach effectively mitigates the limitation of local sampling in capturing the global data distribution. For the consensus function construction, a non-iterative weighted spectral consensus function is introduced, which employs the Tcut strategy to achieve high-precision cluster partitioning within the sparse graph. The SREC algorithm is implemented in a distributed environment using the Spark computing framework, and its performance is systematically evaluated on datasets containing over one million samples. Experimental results show that SREC outperforms ten selected mainstream clustering algorithms on the NMI, ARI, and ACC evaluation metrics, with improvements of 4.15%, 3.33% and 0.98%, respectively, over the second-best algorithm. Moreover, SREC algorithm exhibits strong stability, demonstrating low sensitivity to changes in the number of base clusters, as reflected by an NMI standard deviation of only 0.21%. Furthermore, when applied to clustering tasks with five million samples, SREC algorithm achieves a 51.8% increase in computational efficiency compared to the next-best algorithm, confirming its advantages for large-scale data clustering. The findings of this study can provide a reference for efficient clustering analysis of large-scale data, distributed data mining, and the design of related intelligent application systems.
- 参考文献/References:
-
[1] SASAKI Y. A survey on IoT big data analytic systems: current and future[J]. IEEE internet of things journal, 2022, 9(2): 1024-1036
[2] 孙吉贵, 刘杰, 赵连宇. 聚类算法研究[J]. 软件学报, 2008, 19(1): 48-61 SUN Jigui, LIU Jie, ZHAO Lianyu. Clustering algorithms research[J]. Journal of software, 2008, 19(1): 48-61
[3] SINGH J, SINGH D. A comprehensive review of clustering techniques in artificial intelligence for knowledge discovery: taxonomy, challenges, applications and future prospects[J]. Advanced engineering informatics, 2024, 62: 102799
[4] 段意强. 多视图子空间聚类算法研究[D]. 广州: 广东工业大学, 2022: 6-7. DUAN Yiqiang. Research on multi-view subspace clustering algorithms[D]. Guangzhou: Guangdong University of Technology, 2022: 6-7.
[5] HE Wei, ZHANG Shangzhi, LI Chunguang, et al. Neural normalized cut: a differential and generalizable approach for spectral clustering[J]. Pattern recognition, 2025, 164: 111545
[6] 林毓秀, 刘慧, 于晓, 等. 面向子空间聚类的多视图统一表示学习网络[J]. 计算机研究与发展, 2025, 62(5): 1248-1261 LIN Yuxiu, LIU Hui, YU Xiao, et al. A multi-view unified representation learning network for subspace clustering[J]. Journal of computer research and development, 2025, 62(5): 1248-1261
[7] YANG Yiyang, DENG Sucheng, LU Juan, et al. GraphLSHC: towards large scale spectral hypergraph clustering[J]. Information sciences, 2021, 544: 117-134
[8] STREJL A, GHOSH J. Cluster ensembles—a knowledge reuse framework for combining multiple partitions[J]. Journal of machine learning research, 2002, 3(12): 583-617.
[9] ZHOU Peng, LI Rongwen, LING Zhaolong, et al. Fair clustering ensemble with equal cluster capacity[J]. IEEE transactions on pattern analysis and machine intelligence, 2025, 47(3): 1729-1746
[10] 闫晨, 杨有龙, 刘原园. 基于聚类质量的两阶段集成算法[J]. 吉林大学学报(理学版), 2023, 61(4): 899-908 YAN Chen, YANG Youlong, LIU Yuanyuan. Two stage ensemble algorithm based on clustering quality[J]. Journal of Jilin University(science edition), 2023, 61(4): 899-908
[11] SALLOUM S, HUANG J Z, HE Yulin. Random sample partition: a distributed data model for big data analysis[J]. IEEE transactions on industrial informatics, 2019, 15(11): 5846-5854
[12] WEI Chenghao, SALLOUM S, EMARA T Z, et al. A two-stage data processing algorithm to generate random sample partitions for big data analysis[C]//Cloud Computing. Seattle: IEEE, 2018.
[13] IKOTUN A M, EZUGWU A E, ABUALIGAH L, et al. K-means clustering algorithms: a comprehensive review, variants analysis, and advances in the era of big data[J]. Information sciences, 2023, 622: 178-210
[14] FOWLKES C, BELONGIE S, CHUNG F, et al. Spectral grouping using the nystrom method[J]. IEEE transactions on pattern analysis and machine intelligence, 2004, 26(2): 214-225
[15] HUANG Dong, WANG Changdong, WU Jiansheng, et al. Ultra-scalable spectral clustering and ensemble clustering[J]. IEEE transactions on knowledge and data engineering, 2020, 32(6): 1212-1226
[16] WANG Jingyu, MA Zhenyu, NIE Feiping, et al. Fast self-supervised clustering with anchor graph[J]. IEEE transactions on neural networks and learning systems, 2022, 33(9): 4199-4212
[17] YANG Geping, DENG Sucheng, YANG Yiyang, et al. LiteWSC: a lightweight framework for web-scale spectral clustering[C]//Database Systems for Advanced Applications. Online: Springer, 2022.
[18] FRED A L N, JAIN A K. Combining multiple clusterings using evidence accumulation[J]. IEEE transactions on pattern analysis and machine intelligence, 2005, 27(6): 835-850
[19] LIU Hongfu, WU Junjie, LIU Tongliang, et al. Spectral ensemble clustering via weighted K-means: theoretical and practical evidence[J]. IEEE transactions on knowledge and data engineering, 2017, 29(5): 1129-1143
[20] HUANG Dong, WANG Changdong, PENG Hongxing, et al. Enhanced ensemble clustering via fast propagation of cluster-wise similarities[J]. IEEE transactions on systems, man, and cybernetics: systems, 2021, 51(1): 508-520
[21] YANG Geping, DENG Sucheng, CHEN Can, et al. LiteWSEC: a lightweight framework for web-scale spectral ensemble clustering[J]. IEEE transactions on knowledge and data engineering, 2023, 35(10): 10035-10047
[22] ZHU Xueying, SUN Jie, HE Zhenhao, et al. Stale-ness-reduction mini-batch K-means[J]. IEEE transactions on neural networks and learning systems, 2024, 35(10): 14424-14436
[23] 李大瑞, 杨林军, 华先胜, 等. 视觉特征空间中大规模聚类问题的一种鲁棒近似算法[J]. 中国科学技术大学学报, 2014, 44(10): 844-852 LI Darui, YANG Linjun, HUA Xiansheng, et al. A robust approximate algorithm for large-scale clustering of visual features[J]. Journal of University of Science and Technology of China, 2014, 44(10): 844-852
[24] CHEN Xinlei, CAI Deng. Large scale spectral clustering with landmark-based representation[J]. Proceedings of the AAAI conference on artificial intelligence, 2011, 25(1): 313-318
[25] 贾洪杰, 丁世飞, 史忠植. 求解大规模谱聚类的近似加权核K-means算法[J]. 软件学报, 2015, 26(11): 2836-2846 JIA Hongjie, DING Shifei, SHI Zhongzhi. Approximate weighted kernel K-means for large-scale spectral cluster-ing[J]. Journal of software, 2015, 26(11): 2836-2846
[26] YAN Donghui, HUANG Ling, JORDAN M I. Fast ap-proximate spectral clustering[C]//Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Paris: ACM, 2009.
[27] WU Junjie, LIU Hongfu, XIONG Hui, et al. K-means-based consensus clustering: a unified view[J]. IEEE transactions on knowledge and data engineering, 2015, 27(1): 155-169
[28] LIU Hongfu, ZHAO Rui, FANG Hongsheng, et al. Entropy-based consensus clustering for patient stratification[J]. Bioinformatics, 2017, 33(17): 2691-2698
[29] LI Tao, DING C. Weighted consensus clustering[C]//Proceedings of the 2008 SIAM International Conference on Data Mining. Atlanta: SIAM, 2008.
[30] DOUZE M, GUZHVA A, DENG C, et al. The faiss library[EB/OL]. (2024-01-16)[2025-08-20]. https://arxiv.org/abs/2401.08281.
[31] 郭嘉铭. 基于大语言模型的领域问答技术研发[D]. 成都: 电子科技大学, 2025. GUO Jiaming. Research and development of domain question answering technology based on large language models[D]. Chengdu: School of Computer Science and Engineering, 2025.
[32] LI Zhenguo, WU Xiaoming, CHANG S F. Segmentation using superpixels: a bipartite graph partitioning approach[C]//2012 IEEE Conference on Computer Vision and Pattern Recognition. Providence: IEEE, 2012.
[33] SLATE D. Letter recognition[DB/OL]. UCI machine learning repository. (1990-12-30) [2025-06-25]. https://doi.org/10.24432/C5ZP40.
[34] LECUN Y, CORTES C, BURGES C J C. The MNIST database of handwritten digits[DB/OL]. (2021-10-16)[2025-06-25]. https://doi.org/10.24432/C53K8Q.
[35] BLACKARD J. Covertype[DB/OL]. UCI Machine Learning Repository. (1998-07-31) [2025-06-25]. https://doi.org/10.24432/C50K5N.
[36] HUBERT L, ARABIE P. Comparing partitions[J]. Journal of classification, 1985, 2(1): 193-218
[37] NGUYEN N, CARUANA R. Consensus clusterings[C]//Seventh IEEE International Conference on Data Mining. Omaha: IEEE, 2007.
[38] 李婕, 张智雄, 王字飞. 增加类簇级对比的SCCL文本深度聚类方法研究[J]. 数据分析与知识发现, 2024, 8(3): 98-109 LI Jie, ZHANG Zhixiong, WANG Yufei. SCCL text deep clustering with increased cluster-level comparison[J]. Data analysis and knowledge discovery, 2024, 8(3): 98-109
- 相似文献/References:
-
[1]张佳骕,蒋亦樟,王士同.基于特征选择聚类方法的稀疏TSK模糊系统[J].智能系统学报,2015,10(4):583.[doi:10.3969/j.issn.1673-4785.201412001]
ZHANG Jiasu,JIANG Yizhang,WANG Shitong.Sparse TSK fuzzy system based on feature selection clustering method[J].CAAI Transactions on Intelligent Systems,2015,10():583.[doi:10.3969/j.issn.1673-4785.201412001]
[2]马晓,张番栋,封举富.基于深度学习特征的稀疏表示的人脸识别方法[J].智能系统学报,2016,11(3):279.[doi:10.11992/tis.201603026]
MA Xiao,ZHANG Fandong,FENG Jufu.Sparse representation via deep learning features based face recognition method[J].CAAI Transactions on Intelligent Systems,2016,11():279.[doi:10.11992/tis.201603026]
[3]赵志辉,赵瑞珍,岑翼刚,等.基于稀疏表示与线性回归的图像快速超分辨率重建[J].智能系统学报,2017,12(1):8.[doi:10.11992/tis.201603039]
ZHAO Zhihui,ZHAO Ruizhen,CEN Yigang,et al.Rapid super-resolution image reconstruction based on sparse representation and linear regression[J].CAAI Transactions on Intelligent Systems,2017,12():8.[doi:10.11992/tis.201603039]
[4]马忠丽,刘权勇,武凌羽,等.一种基于联合表示的图像分类方法[J].智能系统学报,2018,13(2):220.[doi:10.11992/tis.201611036]
MA Zhongli,LIU Quanyong,WU Lingyu,et al.Syncretic representation method for image classification[J].CAAI Transactions on Intelligent Systems,2018,13():220.[doi:10.11992/tis.201611036]
[5]赵晓晓,周治平.结合稀疏表示与约束传递的半监督谱聚类算法[J].智能系统学报,2018,13(5):855.[doi:10.11992/tis.201703013]
ZHAO Xiaoxiao,ZHOU Zhiping.A semi-supervised spectral clustering algorithm combined with sparse representation and constraint propagation[J].CAAI Transactions on Intelligent Systems,2018,13():855.[doi:10.11992/tis.201703013]
[6]孙必慎,石武祯,姜峰.计算视觉核心问题：自然图像先验建模研究综述[J].智能系统学报,2019,14(1):71.[doi:10.11992/tis.201804019]
SUN Bishen,SHI Wuzhen,JIANG Feng.Core problem in computer vision: survey of natural image prior models[J].CAAI Transactions on Intelligent Systems,2019,14():71.[doi:10.11992/tis.201804019]
[7]徐久成,王楠,王煜尧,等.基于非凸加权Lp范数稀疏误差约束的图像去噪算法[J].智能系统学报,2019,14(3):500.[doi:10.11992/tis.201804057]
XU Jiucheng,WANG Nan,WANG Yuyao,et al.Non-convex weighted-Lp-norm sparse-error constraint for image denoising[J].CAAI Transactions on Intelligent Systems,2019,14():500.[doi:10.11992/tis.201804057]
[8]王建,吴锡生.基于改进的稀疏表示和PCNN的图像融合算法研究[J].智能系统学报,2019,14(5):922.[doi:10.11992/tis.201805045]
WANG Jian,WU Xisheng.Image fusion based on the improved sparse representation and PCNN[J].CAAI Transactions on Intelligent Systems,2019,14():922.[doi:10.11992/tis.201805045]
[9]张敏,周治平.结合度量融合和地标表示的自编码谱聚类算法[J].智能系统学报,2020,15(4):687.[doi:10.11992/tis.201911039]
ZHANG Min,ZHOU Zhiping.An autoencoder-based spectral clustering algorithm combined with metric fusion and landmark representation[J].CAAI Transactions on Intelligent Systems,2020,15():687.[doi:10.11992/tis.201911039]
[10]钱剑滨,陈秀宏.自适应多阶段线性重构表示分类的人脸识别[J].智能系统学报,2020,15(5):964.[doi:10.11992/tis.201904002]
QIAN Jianbin,CHEN Xiuhong.Self-adaptive multi-phase linear reconstruction representation based classification for face recognition[J].CAAI Transactions on Intelligent Systems,2020,15():964.[doi:10.11992/tis.201904002]
备注/Memo
收稿日期:2025-9-1。
基金项目:深圳市科技重大专项项目 (KJZD20230923114809020)；深圳市基础研究面上项目(JCYJ20250604175602004).
作者简介:何玉林，研究员，博士，深圳市特支人才，主要研究方向为新型大数据理论模型、大数据高性能/并行计算平台、面向大数据的机器学习算法、复杂型大数据应用系统。主持国家级、省部级科研项目10余项，发表学术论文100余篇。E-mail：yulinhe@gml.ac.cn。;杨振宇，硕士研究生，主要研究方向为大规模数据聚类、集成聚类、机器学习。E-mail：yangzhenyu@gml.ac.cn。;肖又旗，硕士研究生，主要研究方向为大数据分布式计算、Spark能耗优化、高性能数据挖掘。E-mail：xiaoyouqi@gml.ac.cn。
通讯作者:杨振宇. E-mail：yangzhenyu@gml.ac.cn
更新日期/Last Update:
1900-01-01