Abstract
Spectral clustering is a useful tool for clustering data. It separates data points into different clusters using eigenvectors corresponding to eigenvalues of the similarity matrix from a data set. There are various types of similarity functions to be used for spectral clustering. In this paper, we propose a powered Gaussian kernel function for spectral clustering. We first consider a Gaussian kernel similarity function with a power parameter, and then use a modified correlation comparison algorithm to estimate the power parameter. This parameter can be used for separating points that actually lie on different clusters, but with small distance. We then use the maximum value among all minimum distances between data points to get better clustering results. Using the estimated power parameter and the maximum value among minimum distances is able to improve spectral clustering. Some numerical data, real data sets, and images are used for making comparisons between the powered Gaussian kernel spectral clustering algorithm and some existing methods. The comparison results show the superiority and effectiveness of the proposed method.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Kaufman L, Rousseeuw PJ (1990) Finding groups in data: an introduction to cluster analysis. Wiley, New York
Dubois D, Prade H (1980) Fuzzy Sets and systems: theory and applications. Academic Press, New York
Jain AK, Dubes RC (1988) Algorithms for clustering data. Prentice-Hall, New Jersey
MacQueen J (1967) Some methods for classification and analysis of multivariate observations. In: Proceedings of 5th Berkeley symposium on mathematical statistics and probability, vol 1. University of California Press, pp 281–297
Pollard D (1982) Quantization and the method of k-means. IEEE Trans Inf Theory 28:199–205
Bezdek JC (1981) Pattern recognition with fuzzy objective function algorithms. Plenum, New York
Yang MS (1993) A survey of fuzzy clustering. Math Comput Model 18:1–16
Krishnapuram R, Keller JM (1993) A possibilistic approach to clustering. IEEE Trans Fuzzy Syst 1:98–110
Yang MS, Lai CY (2011) A robust automatic merging possibilistic clustering method. IEEE Trans Fuzzy Syst 19:26–41
Cheng Y (1995) Mean shift, mode seeking, and clustering. IEEE Trans Pattern Anal Mach Intell 17:790–799
Wu KL, Yang MS (2007) Mean shift-based clustering. Pattern Recogn 40:3035–3052
von Luxburg U (2007) A tutorial on spectral clustering. Stat Comput 17:395–416
Nascimento MCV, de Carvalho ACPLF (2011) Spectral methods for graph clustering—a survey. Eur J Oper Res 211:221–231
Jia H, Ding S, Xu X, Nie R (2014) The latest research progress on spectral clustering. Neural Comput Appl 24:1477–1486
Shi J, Malik J (2000) Normalized cuts and image segmentation. IEEE Trans Pattern Anal Mach Intell 22:888–905
Kong W, Hu S, Zhang J, Dai G (2013) Robust and smart spectral clustering from normalized cut. Neural Comput Appl 23:1503–1512
Newman M (2006) Finding community structure in networks using the eigenvectors of matrices. Phys Rev E 74:36–104
Oliveira S, Ribeiro JFF, Seok SC (2009) A spectral clustering algorithm for manufacturing cell formation. Comput Ind Eng 57:1008–1014
Ding S, Jia H, Zhang L, Jin F (2014) Research of semi-supervised spectral clustering algorithm based on pairwise constraints. Neural Comput Appl 24:211–219
Ng AY, Jordan MI, Weiss Y (2001) On spectral clustering: analysis and an algorithm. Adv Neural Inf Process Syst 14:849–856
Zelnik-Manor L, Perona P (2004) Self-tuning spectral clustering. In: Advances in neural information processing systems
Li XY, Guo LJ (2012) Constructing affinity matrix in spectral clustering based on neighbor propagation. Neurocomputing 97:125–130
Zhang X, Li J, Yu H (2011) Local density adaptive similarity measurement for spectral clustering. Pattern Recogn Lett 32:352–358
Jia H, Ding S, Du M (2015) Self-tuning p-spectral clustering based on shared nearest neighbors. Cogn Comput 7:622–632
Jia H, Ding S, Du M, Xue Y (2016) Approximate normalized cuts without Eigen-decomposition. Inf Sci 374:135–150
Tasdemir K, Yalcin B, Yildirim I (2015) Approximate spectral clustering with utilized similarity information using geodesic based hybrid distance measures. Pattern Recogn 48:1465–1477
Donath W, Hoffman A (1973) Lower bounds for the partitioning of graphs. IBM J Res Dev 17:420–425
Fiedler M (1973) Algebraic connectivity of graphs. Czechoslov Math J 23:298–305
Chang H, Yeung DY (2008) Robust path-based spectral clustering. Pattern Recogn 41:191–203
Yang MS, Wu KL (2004) A similarity-based robust clustering method. IEEE Trans Pattern Anal Mach Intell 26:434–448
Blake CL, Merz CJ (1998) UCI Repository of machine learning databases. http://www.ics.uci.edu/~mlearn/MLRepository.html. University of California, Department of Information and Computer Science, Irvine, CA
Rebagliati N, Verri A (2011) Spectral clustering with more than K eigenvectors. Neurocomputing 74:1391–1401
Huang L, Li R, Chen H, Gu X, Wen K, Li Y (2014) Detecting network communities using regularized spectral clustering algorithm. Artif Intell Rev 41:579–594
Lei J, Rinaldo A (2015) Consistency of spectral clustering in stochastic block models. Ann Stat 43:215–237
Acknowledgements
The authors are grateful to the anonymous referees for their constructive comments and suggestions to improve the presentation of the paper. This work was supported in part by the Ministry of Science and Technology, Taiwan, under Grant MOST 105-2118-M-033-004-MY2.
Author information
Authors and Affiliations
Corresponding author
Ethics declarations
Conflict of interest
The authors declare that they have no conflict of interest.
Rights and permissions
About this article
Cite this article
Nataliani, Y., Yang, MS. Powered Gaussian kernel spectral clustering. Neural Comput & Applic 31 (Suppl 1), 557–572 (2019). https://doi.org/10.1007/s00521-017-3036-2
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00521-017-3036-2