抽样子空间约束改进大数据谱聚类算法

doi:10.11959/j.issn.1000-0801.2018277

电信科学 ›› 2018, Vol. 34 ›› Issue (11): 41-47.doi: 10.11959/j.issn.1000-0801.2018277

抽样子空间约束改进大数据谱聚类算法

聂茹

华南理工大学广州学院电子信息工程学院，广东广州 510800

修回日期:2018-10-31 出版日期:2018-11-01 发布日期:2018-12-06
作者简介:聂茹（1982-），女，华南理工大学广州学院电子信息工程学院讲师、教学研究室副主任，主要研究方向为智能信息处理、智能控制、电力电子与自动控制等。
基金资助:
广东省教育厅青年创新人才基金资助项目(2016KQNCX227)

Improved large data spectral clustering algorithm based on sampling subspace constraint

Ru NIE

Electronic Information Engineering Institute,Guangzhou College of South China University of Technology,Guangzhou 510800,China

Revised:2018-10-31 Online:2018-11-01 Published:2018-12-06
Supported by:
Youth Innovation Talent Project of Guangdong Provincial Department of Education(2016KQNCX227)

摘要/Abstract

摘要：

在分析经典谱聚目标函数与加权核k-means目标函数等价基础上，设计了一种基于抽样子空间约束的改进大规模数据谱聚类算法，算法通过加权核k-means迭代优化避免矩阵特征分解的大量资源被占用，通过数据抽样及聚类中心的子空间约束，避免全部核矩阵都被使用，从而降低经典算法的时间空间复杂度。理论分析和实验结果表明，改进算法保持与经典算法相近聚类精度，提高了聚类效率，验证了改进算法的有效性。

关键词: 大规模数据谱聚类, 加权核k-means算法, 数据抽样, 矩阵特征分解, 核矩阵

Abstract:

On the basis of analyzing the equivalent function of the objective function of classical spectral clustering algorithm and the weighted kernel k-means objective function,an improved large-scale data spectrum clustring algorithm based on sampling subspace constraint was designed,the weighted kernel k-means iterative optimization was used to avoid the large resource consumption of Laplacian matrix feature decomposition,and by using data sampling and constraining the cluster center to the subspace generated by the sampling points,the use of all kernel matrices was avoided,thereby reducing the time-space complexity of classical algorithms.Theoretical analysis and experimental results show that the improved algorithm can greatly improve the clustering efficiency on the basis of maintaining similar clustering accuracy with the classic algorithm and verify the effectiveness of the proposed algorithm.

Key words: large scale data spectral clustering, weighted kernel k-means algorithm, data sampling, matrix feature decomposition, kernel matrix

中图分类号:

TP181

聂茹. 抽样子空间约束改进大数据谱聚类算法[J]. 电信科学, 2018, 34(11): 41-47.

Ru NIE. Improved large data spectral clustering algorithm based on sampling subspace constraint[J]. Telecommunications Science, 2018, 34(11): 41-47.

图/表 5

表1

图1

表2

表3

图2

参考文献 16

[1]	成宝芝, 赵春晖, 张丽丽 ,等. 联合空间预处理与谱聚类的协同稀疏高光谱异常检测[J]. 光学学报, 2017,37(4): 296-306.
	CHENG B Z , ZHAO C H , ZHANG L L ,et al. Cooperative sparse hyperspectral anomaly detection based on joint spatial preprocessing and spectral clustering[J]. Acta Optica Sinica, 2017,37(4): 296-306.
[2]	林顺富, 田二伟, 符杨 ,等. 基于信息熵分段聚合近似和谱聚类的负荷分类方法[J]. 中国电机工程学报, 2017,37(8): 2242-2252.
	LIN S F , TIAN E W , FU Y ,et al. Load classification method based on information entropy segmentation aggregation approximation and spectral clustering[J]. Proceedings of the CSEE, 2017,37(8): 2242-2252.
[3]	刘春, 邹海锋, 向勇 . 大数据环境下电信数据服务能力开放研究[J]. 电信科学, 2014,30(3): 156-161.
	LIU C , ZOU H F , XIANG Y . Research on telecom data service open ability under the environment of big data[J]. Telecommunications Science, 2014,30(3): 156-161.
[4]	YAN D H , HUANG L , JORDAN M I . Fast approximate spectral clustering[C]// The 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,June 28-July 1,2009,Paris,France. New York:ACM Press, 2009: 907-916.
[5]	钱鹏江, 王士同, 邓赵红 ,等. 基于最小包含球的大数据集快速谱聚类算法[J]. 电子学报, 2010,38(9): 2035-2041.
	QIAN P J , WANG S T , DENG Z H ,et al. Fast spectral clustering for large data sets using minimal enclosing ball[J]. Acta Electronica Sinica, 2010,38(9): 2035-2041.
[6]	杨艺, 马儒宁 . 基于核心点的大数据谱聚类算法[J]. 中国科学技术大学学报, 2016,46(9): 757-763.
	YANG Y , MA R N . Big data spectrum clustering algorithm based on core points[J]. Journal of University of Science and Technology of China, 2016,46(9): 757-763.
[7]	KUMAR S , MOHRI M , TALWALKAR A . Sampling methods for the Nystr?m method[J]. Journal of Machine Learning Research, 2012,13(1): 981-1006.
[8]	SONG Y Q , CHEN W Y , BAI H J ,et al. Parallel spectral clustering[C]// European Conferecne on Machine Learning and Knowledge Discovery in Databases,September 15-19,2008,Antwerp,Belgium. New York:ACM Press, 2008: 374-389.
[9]	SONG Y Q , CHEN W Y , BAI H J ,et al. Parallel spectral clustering in distributed systems[J]. IEEE Transactions on Pattern Analysis ＆ Mach, 2011,33(3): 568-586.
[10]	DHILLON I S , GUAN Y , KULIS B . Weighted graph cuts without eigenvectors:a multilevel approach[J]. IEEE Transactions on Pattern Analysis ＆ Mach, 2007,29(11): 1944-1957.
[11]	HE L , ZHANG H . Kernel K-means sampling for Nystr?m approximation[J]. IEEE Trans Image Process, 2018,27(5): 2108-2120.
[12]	朱光辉, 黄圣彬, 袁春风 ,等. SCoS:基于Spark的并行谱聚类算法设计与实现[J]. 计算机学报, 2018,41(4): 868-884.
	ZHU G H , HUANG S B , YUAN C F ,et al. SCoS:design and implementation of parallel spectrum clustering algorithm based on Spark[J]. Chinese Journal of Computers, 2018,41(4): 868-884.
[13]	BüHLER T , HEIN M . Spectral clustering based on the graph p-Laplacian[C]// The 26th Annual International Conference on Machine Learning,June 14-18,2009,Montreal,Quebec,Canada. New York:ACM Press, 2009: 81-88.
[14]	夏景明, 唐玲玲, 谈玲 ,等. 基于K-means和MTLS-SVM算法的生理参数监测系统[J]. 电信科学, 2017,33(10): 43-49.
	XIA J , TANG L , TAN L ,et al. Biometric monitoring system based on K-means ＆ MTLS-SVM algorithm[J]. Telecommunications Science, 2017,33(10): 43-49.
[15]	CAI D , HE X F , HAN J W ,et al. Graph regularized nonnegative matrix factorization for data representation[J]. IEEE Trans Pattern Anal Mach Intell, 2011,33(8): 1548-1560.
[16]	HAVENS T C , BEZDEK J C , LECKIE C ,et al. Fuzzy c-means algorithms for very large data[J]. IEEE Transactions on Fuzzy Systems, 2012,20(6): 1130-1146.

数据集	数据点个数	维数	类数
Waveform	5 000	40	3
Ringnorm	7 400	20	2
USPS	9 298	256	10
MNIST	70 000	784	10

算法		数据集
算法	Waveform	Ringnorm	USPS	MNIST
Clas-SC	0.375 8	0.787 4	0.669 5	-
Swk-SC	0.389 5	0.793 2	0.685 5	-

算法		数据集
算法	Waveform	Ringnorm	USPS	MNIST
Clas-SC	247.484 2	707.356 8	1 835.890 9	-
Swk-SC	157.670 1	428.077 7	1 164.494 3	-

抽样子空间约束改进大数据谱聚类算法

Improved large data spectral clustering algorithm based on sampling subspace constraint

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 5

参考文献 16

相关文章 11

Metrics

推荐阅读 0

[1]	陈一波, 赵知劲. 基于ET-PPO的双变跳频图案智能决策[J]. 电信科学, 2022, 38(11): 86-95.
[2]	乔稳, 王晓征, 孙震强, 任赣, 刘云新, 杨爱东, 王鹏, 王达, 叶晓舟, 欧阳晔. 下一代电信IT架构演进初探：业务功能虚拟化（BFV）[J]. 电信科学, 2022, 38(6): 143-155.
[3]	祝文军, 王思宁, 高晓欣, 郑倩. 基于知识流和迁移学习的负荷预测[J]. 电信科学, 2022, 38(5): 114-123.
[4]	朱明伟. 网络智能化中的AI工程化技术方案[J]. 电信科学, 2022, 38(2): 157-165.
[5]	刘姿杉,程强,吕博. 面向机器学习的隐私保护关键技术研究综述[J]. 电信科学, 2020, 36(11): 18-27.
[6]	卢子萌,陈佳怡,李璟,谢岳,蒋欣利,韩蕾,郭倩. 基于加权随机森林算法的空巢电力用户识别方法[J]. 电信科学, 2020, 36(8): 112-121.
[7]	欧阳晔,杨爱东,孟凡语. 一种博弈论辅助的机器学习算法检测用户流失行为[J]. 电信科学, 2020, 36(6): 79-89.
[8]	朱应钊. 异构迁移学习研究综述[J]. 电信科学, 2020, 36(3): 100-110.
[9]	周峰,王兵. 基于人工智能的基站巡检应用实践[J]. 电信科学, 2018, 34(12): 102-109.
[10]	赵宇翔,卢光跃,王航龙,李四维. 基于缺失数据BN参数学习的电信流失客户预测算法[J]. 电信科学, 2018, 34(1): 52-60.
[11]	李创创,卢光跃,王航龙. 基于边界样本欠取样支持向量机的电信用户欠费分类算法[J]. 电信科学, 2017, 33(9): 85-91.