Top

Hint

Swipe to navigate through the articles of this issue

19-11-2020 | Original Article

A robust spectral clustering algorithm based on grid-partition and decision-graph

Journal:: International Journal of Machine Learning and Cybernetics

Authors:: Lijuan Wang, Shifei Ding, Yanru Wang, Ling Ding

» Get access to the full-text

Important notes

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Abstract

Spectral clustering (SC) transforms the dataset into a graph structure, and then finds the optimal subgraph by the way of graph-partition to complete the clustering. However, SC algorithm constructs the similarity matrix and feature decomposition for overall datasets, which needs high consumption. Secondly, k-means is taken at the clustering stage and it selects the initial cluster centers randomly, which leads to the unstable performance. Thirdly, SC needs prior knowledge to determine the number of clusters. To deal with these issues, we propose a robust spectral clustering algorithm based on grid-partition and decision-graph (PRSC) to reduce the amount of calculation and improve the clustering efficiency. In addition, a decision-graph method is added to identify the cluster centers quickly to improve the algorithm stability without any prior knowledge. A numerical experiments validate that PRSC algorithm can effectively improve the efficiency of SC. It can quickly obtain the stable performance without any prior knowledge.

Please log in to get access to this content

To get access to this content you need the following product:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 69.000 Bücher
über 500 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Umwelt
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Testen Sie jetzt 30 Tage kostenlos.

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 50.000 Bücher
über 380 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Umwelt
Maschinenbau + Werkstoffe

Testen Sie jetzt 30 Tage kostenlos.

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 58.000 Bücher
über 300 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Testen Sie jetzt 30 Tage kostenlos.

inform now

Deng T, Ye D, Ma R et al (2020) Low-rank local tangent space embedding for subspace clustering. Inf Sci 508:1–21 MathSciNetCrossRef

Zhang Q, Zhu C, Yang L et al (2017) An incremental CFS algorithm for clustering large data in industrial internet of things. IEEE Trans Ind Inf 13(3):1193–1201 CrossRef

Pang Y, Ye L, Li X et al (2016) Incremental learning with saliency map for moving object detection. IEEE Trans Circuits Syst Video Technol 28(3):640–651 CrossRef

Zhu Y, Ting K, Carman M (2016) Density-ratio based clustering for discovering clusters with varying densities. Pattern Recognit 60:983–997 CrossRef

MacQueen J Some methods for classification and analysis of multivariate observations. In: Proceedings of 5th Berkeley symposium on mathematical statistics and probability, vol 1, pp 281–297

Frey B, Dueck D (2007) Clustering by passing messages between data points. Science 315(5814):972–976 MathSciNetCrossRef

Ester M, Kriegel H, Sander J et al (1996) A density-based algorithm for discovering clusters in large spatial databases with noise. In: Proceedings of the 2nd international conference on knowledge discovery and data mining, vol 226, p 231

Cour T, Benezit F, Shi J (2005) Spectral segmentation with multiscale graph decomposition. In: Proceedings of the IEEE computer society conference on computer vision and pattern recognition (CVPR'05), vol 2, pp 1124–1131

Chung F, Graham F (1997) Spectral graph theory. American Mathematical Soc., Providence

10.

Huang J, Nie F, Huang H (2013) Spectral rotation versus k-means in spectral clustering. In: Proceedings of the twenty-seventh AAAI conference on artificial intelligence

11.

Li Z, Nie F, Chang X et al (2018) Rank-constrained spectral clustering with flexible embedding. IEEE Trans Neural Netw Learn Syst 29(12):6073–6082 MathSciNetCrossRef

12.

Mehrkanoon S, Alzate C, Mall R et al (2014) Multiclass semisupervised learning based upon kernel spectral clustering. IEEE Trans Neural Netw Learn Syst 26(4):720–733 MathSciNetCrossRef

13.

Yang Y, Ma Z, Yang Y et al (2014) Multitask spectral clustering by exploring intertask correlation. IEEE Trans Cybern 45(5):1083–1094 CrossRef

14.

Panda R, Kuanar S, Chowdhury AS (2017) Nyström approximated temporally constrained multisimilarity spectral clustering approach for movie scene detection. IEEE Trans Cybern 48(3):836–847 CrossRef

15.

Pang Y, Wang S, Yuan Y (2014) Learning regularized LDA by clustering. IEEE Trans Neural Netw Learn Syst 25(12):2191–2201 CrossRef

16.

Chen G, Hu J, Peng H et al (2018) A spectral clustering algorithm improved by P systems. Int J Comput Commun Control 13(5):759–771 CrossRef

17.

Zelnik-Manor, L, Perona, P, Self-Tuning Spectral Clustering. In: Advances in Neural Information Processing Systems 17 (NIPS, (2004) The MITPress, December 13-18, Vancouver, British Columbia, Canada, pp 1601–1608

18.

Wang L, Ding S, Jia H (2019) An improvement of spectral clustering via message passing and density sensitive similarity. IEEE Access 7:101054–101062 CrossRef

19.

Wen G, Zhu Y, Cai Z et al (2018) Self-tuning clustering for high-dimensional data. World Wide Web 21(6):1563–1573 CrossRef

20.

Zhang H, Cao L (2014) A spectral clustering based ensemble pruning approach. Neurocomputing 139:289–297 CrossRef

21.

Cheng D, Nie F, Sun J et al (2017) A weight-adaptive Laplacian embedding for graph-based clustering. Neural Comput 29(7):1902–1918 MathSciNetCrossRef

22.

Hu Z, Nie F, Wang R et al (2020) Multi-view spectral clustering via integrating nonnegative embedding and spectral embedding. Inf Fusion 55:251–259 CrossRef

23.

Pang Y, Xie J, Nie F et al (2018) Spectral clustering by joint spectral embedding and spectral rotation. IEEE Trans Cybern 50(1):247–258 CrossRef

24.

Tautenhain C, Nascimento M (2020) An ensemble based on a bi-objective evolutionary spectral algorithm for graph clustering. Expert Syst Appl 141:112911 CrossRef

25.

Liu J, Guo X, Liu Y (2020) Hyperspectral remote sensing image feature extraction based on spectral clustering and subclass discriminant analysis. Remote Sens Lett 11(2):166–175 CrossRef

26.

Allab K, Labiod L, Nadif M (2018) Simultaneous spectral data embedding and clustering. IEEE Trans Neural Netw Learn Syst 29(12):6396–6401 MathSciNetCrossRef

27.

Wang Y, Duan X, Liu X et al (2018) A spectral clustering method with semantic interpretation based on axiomatic fuzzy set theory. Appl Soft Comput 64:59–74 CrossRef

28.

Nataliani Y, Yang M (2019) Powered Gaussian kernel spectral clustering. Neural Comput Appl 31(1):557–572 CrossRef

29.

Zhang H, Zhang R, Nie F et al (2019) An efficient framework for unsupervised feature selection. Neurocomputing 366:194–207 CrossRef

30.

Ding S, Jia H, Du M et al (2018) A semi-supervised approximate spectral clustering algorithm based on HMRF model. Inf Sci 429:215–228 MathSciNetCrossRef

31.

Rodriguez A, Laio A (2014) Clustering by fast search and find of density peaks. Science 344(6191):1492–1496 CrossRef

32.

Xu X, Ding S, Du M et al (2018) DPCG: an efficient density peaks clustering algorithm based on grid. Int J Mach Learn Cybern 9(5):743–754 CrossRef

33.

Bai L, Cheng X, Liang J et al (2017) Fast density clustering strategies based on the k-means algorithm. Pattern Recognit 71:375–386 CrossRef

34.

Du M, Ding S, Jia H (2016) Study on density peaks clustering based on k-nearest neighbors and principal component analysis. Knowl Based Syst 99:135–145 CrossRef

35.

Ding S, Du M, Sun T et al (2017) An entropy-based density peaks clustering algorithm for mixed type data employing fuzzy neighborhood. Knowl Based Syst 133:294–313 CrossRef

36.

Xie J, Gao H, Xie W et al (2016) Robust clustering by detecting density peaks and assigning points based on fuzzy weighted K-nearest neighbors. Inf Sci 354:19–40 CrossRef

37.

Liu R, Wang H, Yu X (2018) Shared-nearest-neighbor-based clustering by fast search and find of density peaks. Inf Sci 450:200–226 MathSciNetCrossRef

38.

Xu X, Ding S, Wang L et al (2020) A robust density peaks clustering algorithm with density-sensitive similarity. Knowl Based Syst 200:1–11 CrossRef

39.

Xu X, Ding S, Shi Z (2018) An improved density peaks clustering algorithm with fast finding cluster centers. Knowl Based Syst 158:65–74 CrossRef

40.

Wang M, Zuo W, Wang Y (2016) An improved density peaks-based clustering method for social circle discovery in social networks. Neurocomputing 179:219–227 CrossRef

41.

Meng H, Yuan F, Yan T et al (2019) Indoor positioning of rbf neural network based on improved fast clustering algorithm combined with LM algorithm. IEEE Access 7:5932–5945 CrossRef

42.

Li X, Wong K (2019) Evolutionary multiobjective clustering and its applications to patient stratification. IEEE Trans Cybern 49(5):1680–1693 CrossRef

43.

Jiang J, Yan X, Yu Z et al (2015) A Chinese expert disambiguation method based on semi-supervised graph clustering. Int J Mach Learn Cybern 6(2):197–204 CrossRef

Title: A robust spectral clustering algorithm based on grid-partition and decision-graph
Authors:: Lijuan Wang
Shifei Ding
Yanru Wang
Ling Ding
Publication date: 19-11-2020
DOI: https://doi.org/10.1007/s13042-020-01231-2
Publisher: Springer Berlin Heidelberg
Journal: International Journal of Machine Learning and Cybernetics
Print ISSN: 1868-8071
Electronic ISSN: 1868-808X