×

Unsupervised 2D dimensionality reduction with adaptive structure learning. (English) Zbl 1474.68294

Summary: In recent years, unsupervised two-dimensional (2D) dimensionality reduction methods for unlabeled large-scale data have made progress. However, performance of these degrades when the learning of similarity matrix is at the beginning of the dimensionality reduction process. A similarity matrix is used to reveal the underlying geometry structure of data in unsupervised dimensionality reduction methods. Because of noise data, it is difficult to learn the optimal similarity matrix. In this letter, we propose a new dimensionality reduction model for 2D image matrices: unsupervised 2D dimensionality reduction with adaptive structure learning (DRASL). Instead of using a predetermined similarity matrix to characterize the underlying geometry structure of the original 2D image space, our proposed approach involves the learning of a similarity matrix in the procedure of dimensionality reduction. To realize a desirable neighbors assignment after dimensionality reduction, we add a constraint to our model such that there are exact \(c\) connected components in the final subspace. To accomplish these goals, we propose a unified objective function to integrate dimensionality reduction, the learning of the similarity matrix, and the adaptive learning of neighbors assignment into it. An iterative optimization algorithm is proposed to solve the objective function. We compare the proposed method with several 2D unsupervised dimensionality methods. K-means is used to evaluate the clustering performance. We conduct extensive experiments on Coil20, AT&T, FERET, USPS, and Yale data sets to verify the effectiveness of our proposed method.

MSC:

68T05 Learning and adaptive systems in artificial intelligence
68T09 Computational aspects of data analysis and big data

Software:

FERET; COIL-20
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Belhumeur, P., Hespanha, J. P., & Kriegman, D. J. (1997). Eigenfaces vs. Fisherfaces: Recognition using class specific linear projection. IEEE Trans. Pattern Anal. Mach. Intelligence, 9(7), 711-720. ,
[2] Belkin, M., & Niyogi, P. (2001). Laplacian eigenmaps and spectral techniques for embedding and clustering. In T. G. Dietlerich, S. Becker, & Z. Ghahramani (Eds.), Advances in neural information processing systems, 14 (pp. 585-591). Cambridge, MA: MIT Press.
[3] Belkin, M., & Niyogi, P. (2003). Laplacian eigenmaps for dimensionality reduction and data representation. Neural Computation, 15(6), 1373-1396. , · Zbl 1085.68119
[4] Bennamoun, M., Guo, Y., & Sohel, F. (2015). Feature selection for 2d and 3d face recognition. In Wiley encyclopedia of electrical and electronics engineering (pp. 1-54). Hoboken, NJ: Wiley. ,
[5] Boyd, S., Vandenberghe, L., & Faybusovich (2013). Convex optimization. IEEE Transactions on Automatic Control, 51(11), 1859-1859.
[6] Cai, D., He, X., & Han, J. (2005). Document clustering using locality preserving indexing. IEEE Transactions on Knowledge and Data Engineering, 17(12), 1624-1637. ,
[7] Cai, D., Zhang, C. Y., & He, X. F. (2010). Unsupervised feature selection for multi-cluster data. In Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (pp. 333-342). New York: ACM. ,
[8] Chang, X., Nie, F., Ma, Z., Yang, Y., & Zhou, X. (2014). A convex formulation for spectral shrunk clustering. arXiv:1411.6308
[9] Chang, X., Nie, F., Wang, S., Yang, Y., Zhou, X., & Zhang, C. (2015). Compound rank-k projections for bilinear analysis. IEEE Transactions on Neural Networks and Learning Systems, 27(7), 1.
[10] Chang, X., Yang, Y., Long, G., Zhang, C., & Hauptmann, A. G. (2016). Dynamic concept composition for zero-example event detection. arXiv:1601.03679
[11] Chung, F. R. (1997). Spectral graph theory. Providence, RI: American Mathematical Society. · Zbl 0867.05046
[12] Dash, M., & Liu, H. (2000). Feature selection for clustering. Encyclopedia of Database Systems, 21(3), 110-121.
[13] Dong, X., Huang, H., & Wen, H. (2010). A comparative study of several face recognition algorithms based on PCA. In Proceedings of the Third International Symposium on Computer Science and Computational Technology (p. 443). N.p.
[14] Du, L., & Shen, Y.-D. (2015). Unsupervised feature selection with adaptive structure learning. In Proceedings of the ACM-SIGKDD International Conference on Knowledge Discovery and Data Mining (pp. 209-218). New York: ACM. ,
[15] Dy, J. G., & Brodley, C. E. (2004). Feature selection for unsupervised learning. Journal of Machine Learning Research, 5(4), 845-889. · Zbl 1222.68187
[16] Fan, K. (1950). On a theorem of Weyl concerning eigenvalues of linear transformations I. PNAS, 35(11), 652. , · Zbl 0041.00602
[17] Gao, L., Song, J., Liu, X., Shao, J., Liu, J., & Shao, J. (2015). Learning in high-dimensional multimedia data: The state of the art. Multimedia Systems, 21, 1-11. ,
[18] Gao, L., Song, J., Nie, F., Yan, Y., Sebe, N., & Heng, T. S. (2015). Optimal graph learning with partial tags and multiple features for image and video annotation. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition.Piscataway, NJ: IEEE. , · Zbl 1408.94607
[19] Gao, L., Song, J., Nie, F., Zou, F., Sebe, N., & Shen, H. T. (2016). Graph-without-cut: An ideal graph learning for image segmentation. In Proceedings of the 30th AAAI Conference on Artificial Intelligence.Cambridge, MA: AAAI Press.
[20] He, X., Ji, M., Zhang, C., & Bao, H. (2011). A variance minimization criterion to feature selection using Laplacian regularization. IEEE Trans. Pattern Anal. Mach. Intelligence, 33(10), 2013-2025. ,
[21] He, X., Yan, S., Hu, Y., Niyogi, P., & Zhang, H.-J. (2005). Face recognition using Laplacianfaces. IEEE Trans. Pattern Anal. Mach. Intelligence, 27(3), 328-340. ,
[22] Hosoya, H., & Hyvärinen, A. (2016). Learning visual spatial pooling by strong PCA dimension reduction. Neural Computation, 28(7), 1-16. , · Zbl 1414.92099
[23] Hou, C., Nie, F., Li, X., Yi, D., & Wu, Y. (2014). Joint embedding learning and sparse regression: A framework for unsupervised feature selection. IEEE Trans. Cybern., 44(6), 793-804. ,
[24] Hu, D., Feng, G., & Zhou, Z. (2007). Two-dimensional locality preserving projections (2DLPP) with its application to palmprint recognition. Pattern Recognition, 40(1), 339-342. , · Zbl 1103.68758
[25] Kadir, S. N., Goodman, D. F., & Harris, K. D. (2014). High-dimensional cluster analysis with the masked EM algorithm. Neural Computation, 26(11), 2379-2394. ,
[26] Kambhatla, N., & Leen, T. K. (1997). Dimension reduction by local PCA. Neural Computation, 9, 1493-1516. ,
[27] Koch, I., & Naito, K. (2007). Dimension selection for feature selection and dimension reduction with principal and independent component analysis. Neural Computation, 19(2), 513-545. , · Zbl 1125.68099
[28] Kodirov, E., Xiang, T., Fu, Z., & Gong, S. (2016). Learning robust graph regularisation for subspace clustering. In Proceedings of the British Machine Conference.N.p.
[29] Kokiopoulou, E., & Saad, Y. (2007). Orthogonal neighborhood preserving projections: A projection-based dimensionality reduction technique. IEEE Trans. Pattern Anal. Mach. Intelligence, 29(12), 2143-2156. ,
[30] Lakshmanan, K. C., Sadtler, P. T., Tyler-Kabara, E. C., Batista, A. P., & Yu, B. M. (2015). Extracting low-dimensional latent structure from time series in the presence of delays. Neural Computation, 27(9), 1-32. , · Zbl 1418.62335
[31] Luo, M., Nie, F., Chang, X., Yang, Y., Hauptmann, A., & Zheng, Q. (2016). Avoiding optimal mean robust PCA/2DPCA with non-greedy l1-norm maximization. In Proceedings of the 25th International Joint Conference on Artificial Intelligence. N.p.
[32] Mohar, B. (1991). The laplacian spectrum of graphs. In Y. Alavi, G. Chartrand, O. Oellermann, & A. J. Schenk, Graph theory, Combinatorics, and Applications (pp. 871-898). New York: Wiley. · Zbl 0840.05059
[33] Nene, S. A., Nayar, S. K., & Murase, H. (1996). Columbia object image library (Coil-20) (Technical Report CUCS-005-96). New York: Columbia University.
[34] Nie, F., Wang, X., & Huang, H. (2014). Clustering and projected clustering with adaptive neighbors. In Proceedings of the ACM SIGKDD Conference on Knowledge Discovery and Data Mining (pp. 977-986). New York: ACM. ,
[35] Niyogi, X. (2004). Locality preserving projections. In S. Thrun, L. K. Saul, & B. Schölkopf (Eds.), Advances in neural information processing systems, 16. Cambridge, MA: MIT Press.
[36] Phillips, P. J., Wechsler, H., Huang, J., & Rauss, P. J. (1998). The FERET database and evaluation procedure for face-recognition algorithms. Image and Vision Computing, 16, 295-306. ,
[37] Roweis, S. T., & Saul, L. K. (2000). Nonlinear dimensionality reduction by locally linear embedding. Science, 290(5500), 2323-2326. ,
[38] Samaria, F. S., & Harter, A. C. (1994). Parameterisation of a stochastic model for human face identification. In Proceedings of the Second IEEE Workshop on Applications of Computer Vision (pp. 138-142). Washington, DC: IEEE Computer Society. ,
[39] Song, J., Gao, L., Puscas, M. M., Nie, F., Shen, F., & Sebe, N. (2016). Joint graph learning and video segmentation via multiple cues and topology calibration. In Proceedings of the 2016 ACM on Multimedia Conference (pp. 831-840). New York: ACM. ,
[40] Turk, M. A., & Pentland, A. P. (1991). Face recognition using eigenfaces. In Proceedings of the Conference on Computer Vision and Pattern Recogintion (pp. 586-591). Washington, DC: IEEE Computer Society. ,
[41] Wang, J., Zhang, T., Song, J., Sebe, N., & Shen, H. (2016). A survey on learning to hash. arXiv:1606.00185.
[42] Welling, M. (2005). Fisher linear discriminant analysis. Toronto: Department of Computer Science, University of Toronto.
[43] Woraratpanya, K., Sornnoi, M., Leelaburanapong, S., Titijaroonroj, T., Varakulsiripunt, R., Kuroki, Y., & Kato, Y. (2015). An improved 2DPCA for face recognition under illumination effects. In Proceedings of the International Conference on Information Technology and Electrical Engineering (pp. 448-452). Piscatway, NJ: IEEE. ,
[44] Yamada, M., Jitkrittum, W., Sigal, L., Xing, E. P., & Sugiyama, M. (2014). High-dimensional feature selection by feature-wise kernelized lasso. Neural Computation, 26(1), 185-207. , · Zbl 1410.68328
[45] Yang, J., Zhang, D., Frangi, A. F., & Yu Yang, J. (2004). Two-dimensional PCA: A new approach to appearance-based face representation and recognition. IEEE Trans. Pattern Anal. Mach. Intelligence, 26(1), 131-137. ,
[46] Zelnik-Manor, L., & Perona, P. (2005). Self-tuning spectral clustering. In L. K. Saul, Y. Weiss, & L. Bottou (Eds.), Advances in neural information processing systems (pp. 1601-1608). Cambridge, MA: MIT Press.
[47] Zhang, D., and Zhou, Z.-H. (2005). (2d)##img##PCA: Two-directional two-dimensional PCA for efficient face representation and recognition. Neurocomputing, 69(1-3), 224-231. ,
[48] Zhao, Z., Wang, L., Liu, H., & Ye, J. (2013). On similarity preserving feature selection. IEEE Transactions on Knowledge and Data Engineering, 25(3), 619-632. ,
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.