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

doi:10.11959/j.issn.1000-0801.2018277

Abstract

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

CLC Number:

TP181

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

Figures/Tables 5

References 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.

Metrics

Recommended 0

No Suggested Reading articles found!

数据集	数据点个数	维数	类数
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

RichHTML

PDF下载

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 5

References 16

Related Articles 11

Metrics

Recommended 0

[1]	Yibo CHEN, Zhijin ZHAO. Intelligent anti-jamming decision algorithm of bivariate frequency hopping pattern based on ET-PPO [J]. Telecommunications Science, 2022, 38(11): 86-95.
[2]	Wen QIAO, Xiaozheng WANG, Zhenqiang SUN, Gan REN, Yunxin LIU, Aidong YANG, Peng WANG, Da WANG, Xiaozhou YE, Ye OUYANG. A pilot study of Telco’s next generation IT architecture evolution: business function virtualization (BFV) [J]. Telecommunications Science, 2022, 38(6): 143-155.
[3]	Wenjun ZHU, Sining WANG, Xiaoxin GAO, Qian ZHENG. Load forecasting based on knowledge flow and transfer learning [J]. Telecommunications Science, 2022, 38(5): 114-123.
[4]	Mingwei ZHU. AI engineering technology solutions in network intelligence [J]. Telecommunications Science, 2022, 38(2): 157-165.
[5]	Zishan LIU,Qiang CHENG,Bo LV. A survey on key technologies of privacy protection for machine learning [J]. Telecommunications Science, 2020, 36(11): 18-27.
[6]	Zimeng LU,Jiayi CHEN,Jing LI,Yue XIE,Xinli JIANG,Lei HAN,Qian GUO. An empty-nest power user identification method based on weighted random forest algorithm [J]. Telecommunications Science, 2020, 36(8): 112-121.
[7]	Ye OUYANG,Aidong YANG,Fanyu MENG. A game theory-assisted machine learning methodology for subscriber churn behaviors detection [J]. Telecommunications Science, 2020, 36(6): 79-89.
[8]	Yingzhao ZHU. Review on heterogeneous transfer learning [J]. Telecommunications Science, 2020, 36(3): 100-110.
[9]	Feng ZHOU,Bing WANG. Application practice of base station inspection based on AI [J]. Telecommunications Science, 2018, 34(12): 102-109.
[10]	Yuxiang ZHAO,Guangyue LU,Hanglong WANG,Siwei LI. A prediction algorithm of telecom customer churn based on Bayesian network parameters learning under incomplete data [J]. Telecommunications Science, 2018, 34(1): 52-60.
[11]	Chuangchuang LI,Guangyue LU,Hanglong WANG. SVM classifier for telecom user arrears based on boundary samples-based under-sampling approaches [J]. Telecommunications Science, 2017, 33(9): 85-91.