Core-points based spectral clustering for big data analysis

doi:10.3969/j.issn.0253-2778.2016.09.007

Abstract

Abstract: With regard to failures in applying spectral clustering to big data due to its computation complexity, a new spectral clustering algorithm for big data was proposed. Firstly, core-points based on random sampling and data similarity were selected, with which, the big data were grouped. Secondly, spectral clustering was applied to the core-points. Finally, the clustering of whole data was completed by combining the clustering result of the core-points and the grouped big data information. The algorithm both promotes the spectral clustering to big data and reduces the influence of noise or abnormal data by the core-points. A large number of experiments fully verify the effectiveness of the method proposed in this paper.

Key words: big data, spectral clustering, core-points, data group

CLC Number:

TP181

YANG Yi, MA Runing. Core-points based spectral clustering for big data analysis[J]. Journal of University of Science and Technology of China, 2016, 46(9): 757-763.

References

［1］
刘冰．Web数据挖掘[M]．北京：清华大学出版社，2011.
[2] KAUFMAN L, ROUSSEEUW P J. Finding Groups in Data: An Introduction to Cluster Analysis[M]. New York: Wiley, 1990.
[3] XU R, WUNSCH D. Survey of clustering algorithms [J]. IEEE Transactions on Neural Networks, 2005, 16(3): 645-678.
[4] SHI J B, MALIK J. Normalized cuts and image segmentation [J]. IEEE Transactions on Pattern Analysis & Machine Intelligence, 2000, 22(8): 888-905.
[5] MACQUEEN J. Some methods for classification and analysis of multivariate observations[C]// Proceedings of the 5th Berkeley Symposium Mathematical Statistics Probability. Berkeley: 1967: 281-297.
[6] WILLIAMS P K, SOARES C V, GILBERT J E. A clustering rule based approach for classification problems [J]. International Journal of Data Warehousing and Mining, 2010, 8(1): 1-23.
[7] FOWLKES C, BELONGIE S, FAN C, et al. Spectral grouping using the Nystrm method [J]. IEEE Transactions on Pattern Analysis & Machine Intelligence, 2004, 26(2): 214-225.
[8] ZHANG K, KWOK J T. Clustered Nystrm method for large scale manifold learning and dimension reduction [J]. IEEE Transactions on Neural Networks, 2010, 21(10):1576-1587.
[9] DING S F, JIA H J, SHI Z Z. Spectral clustering algorithm based on adaptive Nystrm sampling for big data analysis [J]. Journal of Software, 2014, 25(9): 2037-2049.
[10] CHEN X L, DENG C. Large scale spectral clustering with landmark-based representation[C]// Proceedings of the 25th AAAI Conference on Artificial Intelligence. San Francisco: AAAI Press, 2011: 313-318.
[11] YAN D H, HUANG L, JORDAN M I. Fast approximate spectral clustering[C]// Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Paris,France: ACM Press, 2009: 907-916.
[12] SHINNOU H, SASAKI M. Spectral clustering for a large data set by reducing the similarity matrix size[C]// Proceedings of the 6th International Language Resources and Evaluation. 2008.
[13] VISWANATH P, BABU V S. Rough-DBSCAN: A fast hybrid density based clustering method for large data sets [J]. Pattern Recognition Letters, 2009, 30(16): 1477-1488.
[14] ZHANG T, RAMAKRISHNAN R, LIVNY M. BIRCH: An efficient data clustering method for very large databases [J]. ACM SIGMOD Record, 1999, 25(2): 103-114.
[15] 马儒宁，王秀丽，丁军娣．多层核心集凝聚算法[J]．软件学报，2013，24(3)：490-506.
MA R N，WANG X L，DING J D．Multilevel core-sets based aggregation clustering algorithm [J]. Journal of Software，2013，24(3)：490-506.

()
()

[1]	QIU Zhen, WANG Qiyuan, LIU Di, MENG Hongmin. A novel method for mining latent events based on scalable patterns [J]. Journal of University of Science and Technology of China, 2019, 49(7): 524-532.
[2]	CHEN Feng, ZHANG Zhi, LI Qinjian, CHEN Yuqiang, CHEN Guoliang. Dynamic task scheduling algorithm of parallel computing for FCD big data [J]. Journal of University of Science and Technology of China, 2018, 48(9): 718-722.
[3]	CHEN Zhizhu, WANG Hongzhi, XIONG Feng, ZHANG Yice, GAO Hong, LI Jianzhong. Research on the auction strategies and pricing of big data [J]. Journal of University of Science and Technology of China, 2018, 48(6): 486-494.
[4]	TANG Fengqin,2， DING Wenwen. Community detection based on spectral clustering with node attributes [J]. Journal of University of Science and Technology of China, 2018, 48(2): 162-173.
[5]	WANG Jiayu, ZHANG Zhenyu, CHU Zheng, WU Xiaohong. A trajectory data density partition based distributed parallel clustering method [J]. Journal of University of Science and Technology of China, 2018, 48(1): 47-56.
[6]	XU Ziwei, WANG Peng, CHEN Zonghai. A two-stage feature selection method based on Fisher’s ratio and prediction risk for telecom customer churn prediction [J]. Journal of University of Science and Technology of China, 2017, 47(8): 686-694.
[7]	CHEN Zhenguo, TIAN Liqin, LIN Chuang. Data reliable assurance model of Internet of Things based on the trust evaluation of perceived source [J]. Journal of University of Science and Technology of China, 2017, 47(4): 297-303.
[8]	XU Xueli, ZHAO Xuejing. Application of sparse spectral clustering algorithm in high-dimensional data [J]. Journal of University of Science and Technology of China, 2017, 47(4): 311-319.
[9]	BU Yao, WU Bin, CHEN Yufeng, BAI Demeng. BDAP: A data mining platform based on Spark [J]. Journal of University of Science and Technology of China, 2017, 47(4): 358-368.
[10]	ZHANG Hui, ZHAO Jing. An unsupervised boundary detection algorithm based on orientation contrast model [J]. Journal of University of Science and Technology of China, 2017, 47(1): 26-31.
[11]	SHI Lukui, YUAN Bin, LIU Wenhao. Parallel ISOMAP algorithm based on Spark [J]. Journal of University of Science and Technology of China, 2016, 46(9): 711-718.
[12]	ZHANG Jingjing,YANG Yan*,WANG Hongjun, HAN Xiaotao,DENG Qiang. A novel voting method and parallel implementation for soft clustering [J]. Journal of University of Science and Technology of China, 2016, 46(3): 173-179.
[13]	YIN Chao, WANG Jianzong, LV Haitao, CUI Zongmin, CHENG Lianglun, LI Tongfang, LIU Yan. BDCode: An erasure code algorithm for big data storage systems [J]. Journal of University of Science and Technology of China, 2016, 46(3): 188-199.
[14]	WANG Yaling, LIU Yue, HONG Jianguang, CUI Wei LI Yanhu, SU Yipeng, HUANG Gaopan, ZHANG Mingming, LIU Wantao. Spark/Shark-based OLAP system for smart grid applications [J]. Journal of University of Science and Technology of China, 2016, 46(1): 66-75.
[15]	ZHENG Xiumeng, CHEN Fucai, HUANG Ruiyang. Research on collaborative recommendation algorithms based on parallel spectral clustering [J]. Journal of University of Science and Technology of China, 2016, 46(1): 82-86.