Global discriminative-based nonnegative spectral clustering. (English) Zbl 1412.62085
Summary: Based on spectral graph theory, spectral clustering is an optimal graph partition problem. It has been proven that the spectral clustering is equivalent to nonnegative matrix factorization (NMF) under certain conditions. Based on the equivalence, some spectral clustering methods are proposed, but the global discriminative information of the dataset is neglected. In this paper, based on the equivalence between spectral clustering and NMF, we simultaneously maximize the between-class scatter matrix and minimize the within-class scatter matrix to enhance the discriminating power. We integrate the geometrical structure and discriminative structure in a joint framework. With a global discriminative regularization term added into the nonnegative matrix factorization framework, we propose two novel spectral clustering methods, named global discriminative-based nonnegative and spectral clustering (GDBNSC-Ncut and GDBNSC-Rcut) These new spectral clustering algorithms can preserve both the global geometrical structure and global discriminative structure. The intrinsic geometrical information of the dataset is detected, and clustering quality is improved with enhanced discriminating power. In addition, the proposed algorithms also have very good abilities of handling out-of-sample data. Experimental results on real word data demonstrate that the proposed algorithms outperform some state-of-the-art methods with good clustering qualities.
MSC:
| 62H30 | Classification and discrimination; cluster analysis (statistical aspects) |
| 05C50 | Graphs and linear algebra (matrices, eigenvalues, etc.) |
Keywords:
spectral clustering; nonnegative matrix factorization (NMF); global discrimination informationReferences:
| [1] | Jain, A. K.; Murty, M. N.; Flynn, P. J., Data clustering: a review, ACM Comput. Surv. ((CSUR)), 31, 264-323 (1999) |
| [2] | Shang, F. H.; Jiao, L. C.; Wang, F., Graph dual regularization non-negative matrix factorization for co-clustering, Pattern Recognit., 45, 2237-2250 (2012) · Zbl 1234.68356 |
| [3] | Jain, A. K.; Dubes, R. C., Algorithms for Clustering Data [M] (1988), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ · Zbl 0665.62061 |
| [4] | Tung, F.; Wong, A.; Clausi, D. A., Enabling scalable spectral clustering for image segmentation, Pattern Recognit., 43, 4069-4076 (2010) · Zbl 1207.68323 |
| [5] | Jiang, D.; Tang, C.; Zhang, A., Cluster analysis for gene expression data: a survey, IEEE Trans. Knowl. Data Eng., 16, 1370-1386 (2004) |
| [6] | Hammouda, K. M.; Kamel, M. S., Efficient phrase-based document indexing for web document clustering, IEEE Trans. Knowl. Data Eng., 16, 1279-1296 (2004) |
| [7] | Gordon, S.; Greenspan, H.; Goldberger, J., Applying the information bottleneck principle to unsupervised clustering of discrete and continuous image representations, IEEE Comput. Soc. Conf. Comput. Vis. Pattern Recognit. ((CVPR)), 370-377 (2003) |
| [8] | Kong, X. W.; Wang, R.; Li, G., Fuzzy clustering algorithms based on resolution and their application in image compression, Pattern Recognit., 2439-2444 (2002) · Zbl 1006.68911 |
| [9] | Filippone, M.; Camastra, F.; Masulli, F.; Rovetta, S., A survey of kernel and spectral methods for clustering, Pattern Recognit., 41, 176-190 (2008) · Zbl 1122.68530 |
| [10] | Luxburg, U. V., A tutorial on spectral clustering, Stat. Comput., 17, 395-416 (2007) |
| [11] | Ng, A.; Jordan, M.; Weiss, Y., On spectral clustering: analysis and an algorithm, Adv. Neural Inform. Process. Syst. ((NIPS)), 849-856 (2001) |
| [13] | Nie, F.; Xu, D.; Tsang, I. W.; Zhang, C., Flexible manifold embedding: a framework for semi-supervised and unsupervised dimension reduction, IEEE Trans. Image Process., 19, 7, 1921-1932 (2010) · Zbl 1371.94276 |
| [15] | Ding, S. F.; Jia, H. J.; Zhang, L. W.; Jin, F. X., Research of semisupervised spectral clustering algorithm based on pairwise constraints, Neural Comput. Appl., 24, 1, 211-219 (2014) |
| [16] | Jia, H. J.; Ding, S. F.; Ma, H.; Xing, W. Q., Spectral clustering with neighborhood attribute reduction based on information entropy, J. Comput., 9, 6, 1316-1324 (2014) |
| [17] | Jia, H. J.; Ding, S. F.; Zhu, H.; Wu, F. L.; Bao, L. N., A feature weighted spectral clustering algorithm based on knowledge entropy, J. Softw., 8, 5, 1101-1108 (2013) |
| [18] | Shi, J.; Malik, J., Normalized cuts and image segmentation, IEEE Trans. Pattern Anal. Mach. Intell., 22, 888-905 (2000) |
| [19] | Chan, P. K.; Schlag, M.; Zien, J. Y., Spectral k-way ratio cut partitioning and clustering, IEEE Trans. CAD-Integrated Circuits Syst., 13, 1088-1096 (1994) |
| [20] | Barnes, E. R., An algorithm for partitioning the nodes of a graph, SIAM J. Algebraic Discret. Methods, 3, 4, 541-550 (1982) · Zbl 0505.05050 |
| [21] | Ding, C. H.Q.; He, X.; Zha, H., A min-max cut algorithm for graph partitioning and data clustering, Proc. IEEE Int. Conf. Data Min., 107-114 (2001), ICDM’ |
| [22] | Jia, H. J.; Ding, S. F.; Xu, X. Z.; Nie, R., The latest research progress on spectral clustering, Neural Comput. Appl., 24, 7−8, 1477-1486 (2014) |
| [23] | Lee, D. D.; Seung, H. S., Learning the parts of objects by non-negative matrix factorization, Nature, 401, 788-791 (1999) · Zbl 1369.68285 |
| [24] | Lee, D. D.; Seung, H. S., Algorithms for non-negative matrix factorization, Adv. Neural Inform. Process. Syst. ((NIPS)), 556-562 (2001) |
| [25] | Biederman, I., Recognition-by-components: a theory of human image understanding, Psychol. Rev., 94, 115-147 (1987) |
| [26] | Ross, D.; Zemel, R. S., Learning parts-based representation of data, J. Mach. Learn. Res. ((JMLR)), 7, 2369-2397 (2006) · Zbl 1222.68289 |
| [27] | Ding, C.; Li, T.; Peng, W., Nonnegative matrix factorization and probabilistic latent semantic indexing: equivalence, chi-square statistic, and a hybrid method, Proc. Natl. Conf. Artif. Intell. (2006), (AAAI-06) |
| [28] | Ding, C.; He, X.; Simon, H. D., On the equivalence of nonnegative matrix factorization and spectral clustering, Proc. SIAM Data Min. Conf. (2005) |
| [29] | Luo, D.; Ding, C.; Huang, H.; Li, T., Non-negative Laplacian embedding, Int. Conf. Data Min. ((ICDM)), 337-346 (2009) |
| [30] | Lu, H.; Fu, Z.; Shu, X., Non-negative and sparse spectral clustering, Pattern Recognit., 47, 418-426 (2014) · Zbl 1326.68231 |
| [32] | Ye, J.; Zhao, Z.; Wu, M., Discriminative k-means for clustering, Adv. Neural Inform. Process. Syst., 1649-1656 (2007) |
| [33] | Li, P.; Bu, J.; Yang, Y.; Ji, R.; Chen, C.; Cai, D., Discriminative orthogonal nonnegative matrix factorization with flexibility for data representation, Expert Syst. Appl., 41, 1283-1293 (2014) |
| [34] | Yang, Y.; Xu, D.; Nie, F.; Yan, S.; Zhuang, Y., Image clustering using local discriminative models and global integration, IEEE Trans. Image Process., 19, 2761-2773 (2010) · Zbl 1371.94434 |
| [36] | Nie, F.; Zeng, Z.; Tsang, I. W.; Xu, D.; Zhang, C., Spectral embedded clustering: a framework for in-sample and out-of-sample spectral clustering, IEEE Trans. Neural Netw., 22, 1796-1808 (2011) |
| [37] | Yang, Y.; Shen, H.; Zhang, Y.; Du, X., Discriminative nonnegative spectral clustering with out-of-sample extension, IEEE Trans. Knowl. Data Eng., 26, 1760-1770 (2013) |
| [38] | Nie, F.; Xiang, S.; Liu, Y.; Hou, C.; Zhang, C., Orthogonal vs. uncorrelated least squares discriminant analysis for feature extraction, Pattern Recognit. Lett., 33, 5, 485-491 (2012) |
| [39] | Schölkopf, B.; Smola, A.; Müller, K. R., Kernel principal component analysis, Artif. Neural Netw., 1327, 583-588 (1997) |
| [40] | Müller, K. R.; Mika, S.; Rätsch, G.; Tsuda, K.; Schölkopf, B., An introduction to kernel-based learning algorithms, IEEE Trans. Neural Netw., 12, 02, 181-201 (2001) |
| [42] | Baudat, G.; Anouar, F., Generalized discriminant analysis using a kernel approach, Neural Comput., 12, 10, 2385-2404 (2000) |
| [43] | Liang, Z.; Shi, P., An efficient and effective method to solve kernel Fisher discriminant analysis, Neurocomputing, 61, 485-493 (2004) |
| [44] | Yang, J.; Jin, Z.; Yang, J., Essence of kernel Fisher discriminant: KPCA plus LDA, Pattern Recognit., 37, 10, 2097-2100 (2004) |
| [46] | Wang, J.; Bensmail, H.; Gao, X., Feature selection and multi-kernel learning for sparse representation on a manifold, Neural Netw., 51, 9-16 (2014) · Zbl 1298.68232 |
| [48] | Lin, C. J., On the convergence of multiplicative updating algorithms for non-negative matrix factorization, IEEE Trans. Neural Netw., 18, 1589-1596 (2007) |
| [49] | Cai, D.; He, X. F.; Han, J. W.; Huang, T. S., Graph regularized nonnegative matrix factorization for data representation, IEEE Trans. Pattern Anal. Mach. Intell., 33, 1548-1560 (2011) |
| [51] | Liu, H.; Wu, Z.; Li, X.; Cai, D.; Huang, T. S., Constrained nonnegative matrix factorization for imagine representation, IEEE Trans. Pattern Anal. Mach. Intell., 34, 1299-1311 (2012) |
| [52] | Papadimitriou, C. H.; Steiglitz, K., Combinatorial Optimization: Algorithms and Complexity (1998), Dover: Dover New York · Zbl 0944.90066 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
