Abstract The clustering result is determined by the quality of the eigenvectors (spectral) of the related graph Laplacian in spectral clustering, and therefore eigenvector selection is crucial. To solve this problem, spectral discrimination(SD), spectral discrimination availability(SDA) and spectral discrimination degree(SDD) are defined based on generalized information entropy. SD is exploited to measure the clustering information of each eigenvector. SDA is utilized to remove the ineffective eigenvectors for clustering. SDD is employed to construct a selective clustering ensemble scheme based on contribution for clustering. Thus, a spectral clustering algorithm based on eigenvector selection is proposed. The experimental results on varied natural images show that the proposed algorithm is simple and effective.
Fund:Supported by National Natural Science Foundation of China(No. 61471003), Program in the Youth Elite Support Plan in Universities of Anhui Province(No.Higher Education in Anhui 2014(11)), Natural Science Foundation of Anhui Provincial Education Department(No.KJ2014A041, KJ2016A151, KJ2018A05
Corresponding Authors:
ZHANG Daming, Ph.D., associate professor. His research interests include pattern recognition and image processing.
About author:: (ZHANG Xueyong, Ph.D., professor. His research interests include optical metrology and 3D computer vision.) (LI Lu, master, associate professor. Her research interests include digital image proce-ssing.) (LIU Huayong, master, professor. His research interests include computer graphics.)
[1] JAIN A K. Data Clustering: 50 Years Beyond K-means. Pattern Recognition Letters, 2010, 31(8): 651-666. [2] SHI J B, MALIK J. Normalized Cuts and Image Segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2000, 22(8): 888-905. [3] FILIPPONE M, CAMASTRA F, MASULLI F, et al. A Survey of Kernel and Spectral Methods for Clustering. Pattern Recognition, 2008, 41(1): 176-190. [4] VON LUXBURG U. A Tutorial on Spectral Clustering. Statistics and Computing, 2007, 17(4): 395-416. [5] VERMA D, MEILA M. A Comparison of Spectral Clustering Algorithms[J/OL]. [2018-02-25]. http://120.52.51.17/pdfs.semanticscholar.org/7c19/6faadb4cfb4d388f0a97df676a799aafd03a.pdf. [6] CHEN X L, CAI D. Large Scale Spectral Clustering with Landmark-Based Representation // Proc of the 25th AAAI Conference on Artificial Intelligence. Palo Alto, USA: AAAI Press, 2011: 313-318. [7] ZHU X T, LOY C C, GONG S G. Constructing Robust Affinity Graphs for Spectral Clustering // Proc of the IEEE Conference on Computer Vision and Pattern Recognition. Washington, USA: IEEE, 2014: 1450-1457. [8] ZELNIK-MANOR L, PERONA P. Self-tuning Spectral Clustering[C/OL]. [2018-02-25]. http://papers.nips.cc/paper/2619-self-tuning-spectral-clustering.pdf. [9] ZHANG Z Z, XING F Y, WANG H Z, et al. Revisiting Graph Construction for Fast Image Segmentation. Pattern Recognition, 2018, 78: 344-357. [10] 刘仲民,李战明,李博皓,等.基于稀疏矩阵的谱聚类图像分割算法.吉林大学学报(工学版), 2017, 47(4): 1308-1313. (LIU Z M, LI Z M, LI B H, et al. Spectral Clustering Image Segmentation Based on Sparse Matrix. Journal of Jilin University(Engineering and Technology Edition), 2017, 47(4): 1308-1313.) [11] HOUTHUYS L, LANGONE R, SUYKENS J A K, et al. Multi-view Kernel Spectral Clustering. Information Fusion, 2018, 44: 46-56. [12] GOYAL S, KUMAR S, ZAVERI M A, et al. Fuzzy Similarity Measure Based Spectral Clustering Framework for Noisy Image Segmentation. International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, 2017, 25(4): 649-673. [13] CHEN W Y, SONG Y Q, BAI H J, et al. Parallel Spectral Clus-tering in Distributed Systems. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2011, 33(3): 568-586. [14] JIA J H, XIAO X, LIU B X, et al. Bagging-Based Spectral Clustering Ensemble Selection. Pattern Recognition Letters, 2011, 32(10): 1456-1467. [15] WANG S T, CHUNG F L, XIONG F S. A Novel Image Thresholding Method Based on Parzen Window Estimate. Pattern Recognition, 2008, 41(1): 117-129. [16] SHIH F Y, CHENG S X. Automatic Seeded Region Growing for Color Image Segmentation. Image and Vision Computing, 2005, 23(10): 877-886. [17] PENG B, ZHANG L, ZHANG D. A Survey of Graph Theoretical Approaches to Image Segmentation. Pattern Recognition, 2013, 46(3): 1020-1038. [18] CAI Q, LIU H Y, ZHOU S P, et al. An Adaptive-Scale Active Contour Model for Inhomogeneous Image Segmentation and Bias Field Estimation. Pattern Recognition, 2018, 82: 79-93. [19] LI H Y, HE H Z, WEN Y G, et al. Dynamic Particle Swarm Optimization and K-means Clustering Algorithm for Image Segmentation. Optik, 2015, 126(24): 4817-4822. [20] CHOY S K, LAM S Y, YU K W, et al. Fuzzy Model-Based Clustering and Its Application in Image Segmentation. Pattern Recognition, 2017, 68: 141-157. [21] NG A Y, JORDAN M I, WEISS Y. On Spectral Clustering: Analysis and an Algorithm[C/OL]. [2018-02-25]. http://papers.nips.cc/paper/2092-on-spectral-clustering-analysis-and-an-algorithm.pdf. [22] XIANG T, GONG S G. Spectral Clustering with Eigenvector Selection. Pattern Recognition, 2008, 41(3): 1012-1029. [23] MELNYKOV V, MAITRA R. Finite Mixture Models and Model-Based Clustering. Statistics Surveys, 2010, 4: 80-116. [24] MCLACHIAN G, KRISHNAN T. The EM Algorithm and Extensions. New York, USA: John Wiley & Sons, 2007. [25] 张大明,符茂胜,罗 斌.基于广义积分平方误差谱选择的图像分割.模式识别与人工智能, 2011, 24(2): 277-283. (ZHANG D M, FU M S, LUO B. Image Segmentation Using Generalized Integrated Squared Error-Based Eigenvector Selection. Pattern Recognition and Artificial Intelligence, 2011, 24(2): 277-283.) [26] 赵 凤,焦李成,刘汉强,等.半监督谱聚类特征向量选择算法.模式识别与人工智能, 2011, 24(1): 48-56. (ZHAO F, JIAO L C, LIU H Q, et al. Semi-supervised Eigenvector Selection for Spectral Clustering. Pattern Recognition and Artificial Intelligence, 2011, 24(1): 48-56.) [27] JIANG Y, REN J T. Eigenvector Sensitive Feature Selection for Spectral Clustering // Proc of the European Conference on Machine Learning and Knowledge Discovery in Databases. Berlin, Germany: Springer-Verlag, 2011: 114-129. [28] REBAGLIATI N, VERRID A. Spectral Clustering with More Than K Eigenvectors. Neurocomputing, 2011, 74(9): 1391-1401. [29] 王兴良,王立宏,武栓虎.谱聚类中选取特征向量的动态选择性集成方法.模式识别与人工智能, 2014, 27(5): 452-462. (WANG X L, WANG L H, WU S H, Eigenvector Selection Algorithm for Spectral Clustering Based on Dynamic Selective Ensemble. Pattern Recognition and Artificial Intelligence, 2014, 27(5): 452-462.) [30] ZHAO F, JIAO L J, LIU H Q, et al. Spectral Clustering with Eigenvector Selection Based on Entropy Ranking. Neurocomputing, 2010, 73(10/11/12): 1704-1717. [31] GHASSABEH Y A. On the Convergence of the Mean Shift Algorithm in the One-Dimensional Space. Pattern Recognition Letters, 2013, 34(12): 1423-1427. [32] PONT-TUSET J, ARBELAEZ P, BARRON J T, et al. Multiscale Combinatorial Grouping for Image Segmentation and Object Propo-sal Generation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2017, 39(1): 128-140. [33] MALIK J, BELONGIE S, LEUNG T, et al. Contour and Texture Analysis for Image Segmentation. International Journal of Computer Vision, 2001, 43(1): 7-27. [34] MATLAB Normalized Cuts Segmentation Code[DB/OL].[2018-02-13]. http://www.cis.upenn.edu/~jshi/software. [35] MARTIN D, FOWLKES C, TAL D, et al. A Database of Human Segmented Natural Images and Its Application to Evaluating Segmentation Algorithms and Measuring Ecological Statistics // Proc of the 8th IEEE International Conference on Computer Vision. Wa-shington, USA: IEEE, 2001: 416-423.
2019, Vol. 32 
