Improved large data spectral clustering algorithm based on sampling subspace constraint

Ru NIE

doi:10.11959/j.issn.1000-0801.2018277

您当前的位置：

首页 >

文章列表页 >

Improved large data spectral clustering algorithm based on sampling subspace constraint

research and development | 更新时间：2024-06-05

- Improved large data spectral clustering algorithm based on sampling subspace constraint
- Telecommunications Science Vol. 34, Issue 11, Pages: 41-47(2018)
- 作者机构：
- 作者简介：
- 基金信息：
- DOI：10.11959/j.issn.1000-0801.2018277
  CLC： TP181
- Published Online：2018-11，
  
  Published：20 November 2018
- 稿件说明：
移动端阅览
Ru NIE. Improved large data spectral clustering algorithm based on sampling subspace constraint[J]. Telecommunications science, 2018, 34(11): 41-47.
DOI：

Ru NIE. Improved large data spectral clustering algorithm based on sampling subspace constraint[J]. Telecommunications science, 2018, 34(11): 41-47. DOI： 10.11959/j.issn.1000-0801.2018277.

摘要

在分析经典谱聚目标函数与加权核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.

关键词

Keywords

references

成宝芝 , 赵春晖 , 张丽丽 , 等 . 联合空间预处理与谱聚类的协同稀疏高光谱异常检测 [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 .

林顺富 , 田二伟 , 符杨 , 等 . 基于信息熵分段聚合近似和谱聚类的负荷分类方法 [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 .

刘春 , 邹海锋 , 向勇 . 大数据环境下电信数据服务能力开放研究 [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 .

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 .

钱鹏江 , 王士同 , 邓赵红 , 等 . 基于最小包含球的大数据集快速谱聚类算法 [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 .

杨艺 , 马儒宁 . 基于核心点的大数据谱聚类算法 [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 .

KUMAR S , MOHRI M , TALWALKAR A . Sampling methods for the Nyström method [J ] . Journal of Machine Learning Research , 2012 , 13 ( 1 ): 981 - 1006 .

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 .

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 .

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 .

HE L , ZHANG H . Kernel K-means sampling for Nyström approximation [J ] . IEEE Trans Image Process , 2018 , 27 ( 5 ): 2108 - 2120 .

朱光辉 , 黄圣彬 , 袁春风 , 等 . 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 .

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 .

夏景明 , 唐玲玲 , 谈玲 , 等 . 基于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 .

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 .

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 .

Views

483

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

No data

Related Author

No data

Related Institution

No data

⁰