×

Low-rank representation with adaptive graph regularization. (English) Zbl 1434.68472

Summary: Low-rank representation (LRR) has aroused much attention in the community of data mining. However, it has the following two problems which greatly limit its applications: (1) it cannot discover the intrinsic structure of data owing to the neglect of the local structure of data; (2) the obtained graph is not the optimal graph for clustering. To solve the above problems and improve the clustering performance, we propose a novel graph learning method named low-rank representation with adaptive graph regularization (LRR\(_-\)AGR) in this paper. Firstly, a distance regularization term and a non-negative constraint are jointly integrated into the framework of LRR, which enables the method to simultaneously exploit the global and local information of data for graph learning. Secondly, a novel rank constraint is further introduced to the model, which encourages the learned graph to have very clear clustering structures, i.e., exactly \(c\) connected components for the data with \(c\) clusters. These two approaches are meaningful and beneficial to learn the optimal graph that discovers the intrinsic structure of data. Finally, an efficient iterative algorithm is provided to optimize the model. Experimental results on synthetic and real datasets show that the proposed method can significantly improve the clustering performance.

MSC:

68T05 Learning and adaptive systems in artificial intelligence
62H30 Classification and discrimination; cluster analysis (statistical aspects)

Software:

LFW
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Belkin, M.; Niyogi, P., Laplacian eigenmaps and spectral techniques for embedding and clustering, (Advances in neural information processing systems (2002)), 585-591
[2] Cai, J. F.; Osher, S., Fast singular value thresholding without singular value decomposition, Methods and Applications of Analysis, 20, 4, 335-352 (2013) · Zbl 1401.65042
[3] Du, S.; Ma, Y.; Ma, Y., Graph regularized compact low rank representation for subspace clustering, Knowledge-Based Systems, 118, 56-69 (2017)
[4] Elhamifar, E.; Vidal, R., Sparse subspace clustering: algorithm, theory, and applications, IEEE Transactions on Pattern Analysis and Machine Intelligence, 35, 11, 2765-2781 (2013)
[5] Fan, K., On a theorem of weyl concerning eigenvalues of linear transformations i, Proceedings of the National Academy of Sciences, 35, 11, 652-655 (1949) · Zbl 0041.00602
[6] Feng, J., Lin, Z., Xu, H., & Yan, S. (2014). Robust subspace segmentation with block-diagonal prior. In IEEE conference on computer vision and pattern recognition; Feng, J., Lin, Z., Xu, H., & Yan, S. (2014). Robust subspace segmentation with block-diagonal prior. In IEEE conference on computer vision and pattern recognition
[7] Georghiades, A. S.; Belhumeur, P. N.; Kriegman, D. J., From few to many: Illumination cone models for face recognition under variable lighting and pose, IEEE Transactions on Pattern Analysis and Machine Intelligence, 23, 6, 643-660 (2001)
[8] Hagen, L.; Kahng, A. B., New spectral methods for ratio cut partitioning and clustering, IEEE Transactions on Computer-aided Design of Integrated Circuits and Systems, 11, 9, 1074-1085 (1992)
[9] He, X.; Cai, D.; Yan, S.; Zhang, H. J., Neighborhood preserving embedding, (IEEE international conference on computer vision, vol. 2 (2005), IEEE), 1208-1213
[10] He, X.; Niyogi, P., Locality preserving projections, (Advances in neural information processing systems (2004)), 153-160
[11] He, R.; Zheng, W. S.; Hu, B. G.; Kong, X. W., Nonnegative sparse coding for discriminative semi-supervised learning, (IEEE conference on computer vision and pattern recognition (2011), IEEE), 2849-2856
[12] Huang, J., Nie, F., & Huang, H. (2015). A new simplex sparse learning model to measure data similarity for clustering. In International joint conference on artificial intelligence; Huang, J., Nie, F., & Huang, H. (2015). A new simplex sparse learning model to measure data similarity for clustering. In International joint conference on artificial intelligence
[13] Jain, A. K., Data clustering: 50 years beyond \(K\)-means, Pattern Recognition Letters, 31, 8, 651-666 (2010)
[14] Jia, H.; Cheung, Y. M., Subspace clustering of categorical and numerical data with an unknown number of clusters, IEEE Transactions on Neural Networks and Learning Systems (2017)
[15] Jin, B.; Vai, M. I., An adaptive ultrasonic backscattered signal processing technique for instantaneous characteristic frequency detection, Bio-medical Materials and Engineering, 24, 6, 2761-2770 (2014)
[16] Kanungo, T.; Mount, D. M.; Netanyahu, N. S.; Piatko, C. D.; Silverman, R.; Wu, A. Y., An efficient \(k\)-means clustering algorithm: Analysis and implementation, IEEE Transactions on Pattern Analysis and Machine Intelligence, 24, 7, 881-892 (2002)
[17] Larsen, R. M. (2004). PROPACK-software for large and sparse SVD calculations (pp. 2008-2009). Available online. URL http://sun.stanford.edu/rmunk/PROPACK; Larsen, R. M. (2004). PROPACK-software for large and sparse SVD calculations (pp. 2008-2009). Available online. URL http://sun.stanford.edu/rmunk/PROPACK
[18] Learned-Miller, E.; Huang, G. B.; RoyChowdhury, A.; Li, H.; Hua, G., Labeled faces in the wild: A survey, (Advances in face detection and facial image analysis (2016), Springer), 189-248
[19] Li, S.; Fu, Y., Learning robust and discriminative subspace with low-rank constraints, IEEE Transactions on Neural Networks and Learning Systems, 27, 11, 2160-2173 (2016)
[20] Lichman, M. (2013). UCI machine learning repository http://archive.ics.uci.edu/ml; Lichman, M. (2013). UCI machine learning repository http://archive.ics.uci.edu/ml
[21] Lin, Z., Chen, M., & Ma, Y. (2010). The augmented lagrange multiplier method for exact recovery of corrupted low-rank matrices. arXiv preprint arXiv:1009.5055; Lin, Z., Chen, M., & Ma, Y. (2010). The augmented lagrange multiplier method for exact recovery of corrupted low-rank matrices. arXiv preprint arXiv:1009.5055
[22] Liu, J.; Chen, Y.; Zhang, J.; Xu, Z., Enhancing low-rank subspace clustering by manifold regularization, IEEE Transactions on Image Processing, 23, 9, 4022-4030 (2014) · Zbl 1374.68472
[23] Liu, G.; Lin, Z.; Yan, S.; Sun, J.; Yu, Y.; Ma, Y., Robust recovery of subspace structures by low-rank representation, IEEE Transactions on Pattern Analysis and Machine Intelligence, 35, 1, 171-184 (2013)
[24] Liu, Q.; Lu, X.; He, Z.; Zhang, C.; Chen, W. S., Deep convolutional neural networks for thermal infrared object tracking, Knowledge-Based Systems, 134, 189-198 (2017)
[25] Liu, G.; Yan, S., Latent low-rank representation for subspace segmentation and feature extraction, (IEEE international conference on computer vision (2011), IEEE), 1615-1622
[26] Lu, Y.; Lai, Z.; Li, X.; Wong, W. K.; Yuan, C.; Zhang, D., Low-Rank 2-D Neighborhood Preserving Projection for Enhanced Robust Image Representation, IEEE Transactions on Cybernetics (2018)
[27] Lu, G. F.; Wang, Y.; Zou, J., Low-rank matrix factorization with adaptive graph regularizer, IEEE Transactions on Image Processing, 25, 5, 2196-2205 (2016) · Zbl 1408.94443
[28] Lu, Y.; Yuan, C.; Lai, Z.; Li, X.; Zhang, D.; Wong, W. K., Horizontal and vertical nuclear norm-based 2DLDA for image representation, IEEE Transactions on Circuits and Systems for Video Technology (2018)
[29] Lu, Y.; Yuan, C.; Li, X.; Lai, Z.; Zhang, D.; Shen, L., Structurally incoherent low-rank 2DLPP for image classification, IEEE Transactions on Circuits and Systems for Video Technology (2018)
[30] Luo, G.; Dong, S.; Wang, K.; Zuo, W.; Cao, S.; Zhang, H., Multi-views fusion CNN for left ventricular volumes estimation on cardiac MR images, IEEE Transactions on Biomedical Engineering (2017)
[31] Ma, X.; Liu, Q.; Ou, W.; Zhou, Q., Visual object tracking via coefficients constrained exclusive group LASSO, Machine Vision and Applications, 1-15 (2018)
[32] Martinez, A. M. (1998). The AR face database. CVC technical report.; Martinez, A. M. (1998). The AR face database. CVC technical report.
[33] Murtagh, F., A survey of recent advances in hierarchical clustering algorithms, The Computer Journal, 26, 4, 354-359 (1983) · Zbl 0523.68030
[34] Nene, S. A., Nayar, S. K., & Murase, H., et al. (1996). Columbia object image library (coil-20).; Nene, S. A., Nayar, S. K., & Murase, H., et al. (1996). Columbia object image library (coil-20).
[35] Ng, A. Y.; Jordan, M. I.; Weiss, Y., On spectral clustering: Analysis and an algorithm, (Advances in neural information processing systems (2002)), 849-856
[36] Nie, F.; Wang, X.; Huang, H., Clustering and projected clustering with adaptive neighbors, (ACM SIGKDD international conference on knowledge discovery and data mining (2014), ACM), 977-986
[37] Nie, F., Wang, X., Jordan, M. I., & Huang, H. (2016). The constrained Laplacian rank algorithm for graph-based clustering. In AAAI conference on artificial intelligence; Nie, F., Wang, X., Jordan, M. I., & Huang, H. (2016). The constrained Laplacian rank algorithm for graph-based clustering. In AAAI conference on artificial intelligence
[38] Parimala, M.; Lopez, D.; Senthilkumar, N., A survey on density based clustering algorithms for mining large spatial databases, International Journal of Advanced Science and Technology, 31, 1, 59-66 (2011)
[39] Phillips, J.; Bruce, V.; Soulie, F. F., Face recognition: From theory to applications (1999), Springer-Verlag New York, Inc
[40] Ren, Y.; Zhang, G.; Yu, G.; Li, X., Local and global structure preserving based feature selection, Neurocomputing, 89, 147-157 (2012)
[41] Roweis, S. T.; Saul, L. K., Nonlinear dimensionality reduction by locally linear embedding, Science, 290, 5500, 2323-2326 (2000)
[42] Shi, J.; Malik, J., Normalized cuts and image segmentation, IEEE Transactions on Pattern Analysis and Machine Intelligence, 22, 8, 888-905 (2000)
[43] Sun, F.; Yao, Y.; Chen, M.; Li, X.; Zhao, L.; Meng, Y.; …; Feng, D., Performance analysis of superheated steam injection for heavy oil recovery and modeling of wellbore heat efficiency, Energy, 125, 795-804 (2017)
[44] Sun, F.; Yao, Y.; Li, X., The heat and mass transfer characteristics of superheated steam coupled with non-condensing gases in horizontal wells with multi-point injection technique, Energy, 143, 995-1005 (2018)
[45] Sun, F.; Yao, Y.; Li, X.; Yu, P.; Ding, G.; Zou, M., The flow and heat transfer characteristics of superheated steam in offshore wells and analysis of superheated steam performance, Computers & Chemical Engineering, 100, 80-93 (2017)
[46] Toh, K. C.; Yun, S., An accelerated proximal gradient algorithm for nuclear norm regularized linear least squares problems, Pacific Journal of Optimization, 6, 615-640, 15 (2010) · Zbl 1205.90218
[47] Von Luxburg, U., A tutorial on spectral clustering, Statistics and Computing, 17, 4, 395-416 (2007)
[48] Wang, S. J.; Yang, J.; Sun, M. F.; Peng, X. J.; Sun, M. M.; Zhou, C. G., Sparse tensor discriminant color space for face verification, IEEE Transactions on Neural Networks and Learning Systems, 23, 6, 876-888 (2012)
[49] Wang, J.; Yang, J.; Yu, K.; Lv, F.; Huang, T.; Gong, Y., Locality-constrained linear coding for image classification, (IEEE conference on computer vision and pattern recognition (2010), IEEE), 3360-3367
[50] Wen, J.; Han, N.; Fang, X.; Fei, L.; Yan, K.; Zhan, S., Low-rank preserving projection via graph regularized reconstruction, IEEE Transactions on Cybernetics (2018)
[51] Wen, J.; Xu, Y.; Li, Z.; Ma, Z.; Xu, Y., Inter-class sparsity based discriminative least square regression, Neural Networks, 102, 36-47 (2018) · Zbl 1439.62163
[52] Wen, J.; Zhang, B.; Xu, Y.; Yang, J.; Han, N., Adaptive weighted nonnegative low-rank representation, Pattern Recognition, 81, 326-340 (2018)
[53] Xu, R.; Wunsch, D., Survey of clustering algorithms, IEEE Transactions on Neural Networks, 16, 3, 645-678 (2005)
[54] Yi, S.; He, Z.; Cheung, Y.m.; Chen, W. S., Unified sparse subspace learning via self-contained regression, IEEE Transactions on Circuits and Systems for Video Technology (2017)
[55] Yi, S.; Lai, Z.; He, Z.; Cheung, Y.m.; Liu, Y., Joint sparse principal component analysis, Pattern Recognition, 61, 524-536 (2017) · Zbl 1428.68266
[56] Yin, M.; Gao, J.; Lin, Z., Laplacian regularized low-rank representation and its applications, IEEE Transactions on Pattern Analysis and Machine Intelligence, 38, 3, 504-517 (2016)
[57] Yu, K.; Zhang, T.; Gong, Y., Nonlinear learning using local coordinate coding, (Advances in neural information processing systems (2009)), 2223-2231
[58] Zhang, Z.; Lai, Z.; Xu, Y.; Shao, L.; Wu, J.; Xie, G. S., Discriminative elastic-net regularized linear regression, IEEE Transactions on Image Processing, 26, 3, 1466-1481 (2017) · Zbl 1409.94783
[59] Zhang, Z.; Liu, L.; Shen, F.; Shen, H. T.; Shao, L., Binary multi-view clustering, IEEE Transactions on Pattern Analysis and Machine Intelligence (2018)
[60] Zhang, Z.; Xu, Y.; Shao, L.; Yang, J., Discriminative block-diagonal representation learning for image recognition, IEEE Transactions on Neural Networks and Learning Systems, 29, 7, 3111-3125 (2018)
[61] Zhuang, L.; Gao, H.; Lin, Z.; Ma, Y.; Zhang, X.; Yu, N., Non-negative low rank and sparse graph for semi-supervised learning, (IEEE conference on computer vision and pattern recognition (2012), IEEE), 2328-2335
[62] Zou, H.; Hastie, T.; Tibshirani, R., Sparse principal component analysis, Journal of Computational and Graphical Statistics, 15, 2, 265-286 (2006)
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.