Graph dual regularization non-negative matrix factorization for co-clustering.

*(English)*Zbl 1234.68356Summary: Low-rank matrix factorization is one of the most useful tools in scientific computing, data mining and computer vision. Among of its techniques, non-negative matrix factorization (NMF) has received considerable attention due to producing a parts-based representation of the data. Recent research has shown that not only the observed data are found to lie on a nonlinear low dimensional manifold, namely data manifold, but also the features lie on a manifold, namely feature manifold. In this paper, we propose a novel algorithm, called graph dual regularization non-negative matrix factorization (DNMF), which simultaneously considers the geometric structures of both the data manifold and the feature manifold. We also present a graph dual regularization non-negative matrix tri-factorization algorithm (DNMTF) as an extension of DNMF. Moreover, we develop two iterative updating optimization schemes for DNMF and DNMTF, respectively, and provide the convergence proofs of our two optimization schemes. Experimental results on UCI benchmark data sets, several image data sets and a radar HRRP data set demonstrate the effectiveness of both DNMF and DNMTF.

##### MSC:

68T10 | Pattern recognition, speech recognition |

65F30 | Other matrix algorithms (MSC2010) |

68T05 | Learning and adaptive systems in artificial intelligence |

68R10 | Graph theory (including graph drawing) in computer science |

##### Keywords:

low-rank matrix factorization; non-negative matrix factorization (NMF); graph Laplacian; graph dual regularization; co-clustering
PDF
BibTeX
XML
Cite

\textit{F. Shang} et al., Pattern Recognition 45, No. 6, 2237--2250 (2012; Zbl 1234.68356)

Full Text:
DOI

##### References:

[1] | Jain, A.; Murty, M.; Flynn, P., Data clustering: a review, ACM computing surveys, 31, 3, 264-323, (1999) |

[2] | Shi, J.; Malik, J., Normalized cuts and image segmentation, IEEE transactions on pattern analysis and machine intelligence, 22, 8, 888-905, (2000) |

[3] | Hagen, L.; Kahng, A., 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) |

[4] | C. H. Q. Ding, X. He, H. Zha, M. Gu, H. D. Simon, A min – max cut algorithm for graph partitioning and data clustering, in: Proceedings of the IEEE International Conference on Data Mining (ICDM), 2001, pp. 107-114. |

[5] | Shang, F.; Jiao, L.C.; Shi, J.; Gong, M.; Shang, R., Fast density-weighted low-rank approximation spectral clustering, Data mining and knowledge discovery, 23, 2, 345-378, (2011) · Zbl 1235.68187 |

[6] | Shang, F.; Jiao, L.C.; Shi, J.; Wang, F.; Gong, M., Fast affinity propagation clustering: a multilevel approach, Pattern recognition, 45, 1, 474-486, (2012) |

[7] | Paatero, P.; Tapper, U., Positive matrix factorization: a non-negative factor model with optimal utilization of error estimates of data values, Environmetrics, 5, 2, 111-126, (1994) |

[8] | Lee, D.D.; Seung, H.S., Learning the parts of objects by non-negative matrix factorization, Nature, 401, 788-791, (1999) · Zbl 1369.68285 |

[9] | Biederman, I., Recognition-by-components: a theory of human image understanding, Psychological review, 94, 2, 115-147, (1987) |

[10] | Ross, D.A.; Zemel, R.S., Learning parts-based representation of data, Journal of machine learning research, 7, 2369-2397, (2006) · Zbl 1222.68289 |

[11] | H. Zha, X. He, C. H. Q. Ding, M. Gu, H. D. Simon, Spectral relaxation for K-means clustering, in: Advances in Neural Information Processing Systems (NIPS) 14, 2001, pp. 1057-1064. |

[12] | Dhillon, I.; Guan, Y.; Kulis, B., Weighted graph cuts without eigenvectors: a multilevel approach, IEEE transactions on pattern analysis and machine intelligence, 29, 11, 1944-1957, (2007) |

[13] | C. H. Q. Ding, X. He, On the equivalence of non-negative matrix factorization and spectral clustering, in: Proceedings of the 5th SIAM Conference on Data Mining (SDM), 2005, pp. 606-610. |

[14] | Shang, F.; Jiao, L.C.; Shi, J.; Chai, J., Robust positive semidefinite {\scl}-isomap ensemble, Pattern recognition letters, 32, 4, 640-649, (2011) |

[15] | Tenenbaum, J.B.; de Silva, V.; Langford, J.C., A global geometric framework for nonlinear dimensionality reduction, Science, 290, 5500, 2319-2323, (2000) |

[16] | Roweis, S.T.; Saul, L.K., Nonlinear dimensionality reduction by locally linear embedding, Science, 290, 5500, 2323-2326, (2000) |

[17] | M. Belkin, P. Niyogi, Laplacian Eigenmaps and spectral techniques for embedding and clustering, in: Advances in Neural Information Processing Systems (NIPS) 14, 2002, pp. 585-591. |

[18] | Belkin, M.; Niyogi, P.; Sindhwani, V., Manifold regularization: a geometric framework for learning from examples, Journal of machine learning research, 7, 2399-2434, (2006) · Zbl 1222.68144 |

[19] | Cai, D.; He, X.; Han, J.; Huang, T.S., Graph regularization non-negative matrix factorization for data representation, IEEE transactions on pattern analysis and machine intelligence, 33, 8, 1548-1560, (2011) |

[20] | I. S. Dhillon, Co-clustering documents and words using bipartite spectral graph partitioning, in: Proceedings of the 7th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), 2001, pp. 269-274. |

[21] | I. S. Dhillon, S. Mallela, D. S. Modha, Information-theoretic co-clustering, in: Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), 2003, pp. 89-98. |

[22] | C. H. Q. Ding, T. Li, W. Peng, H. Park, Orthogonal nonnegative matrix tri-factorization for clustering, in: Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), 2006, pp. 126-135. |

[23] | V. Sindhwani, J. Hu, A. Mojsilovic, Regularized co-clustering with dual supervision, in: Advances in Neural Information Processing Systems (NIPS) 21, 2009, pp. 1505-1512. |

[24] | Q. Gu, J. Zhou, Co-clustering on manifolds, in: Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), 2009, pp. 359-368. |

[25] | F. Wang, T. Li, C. Zhang, Semi-supervised clustering via matrix factorization, in: Proceedings of the 8th SIAM Conference on Data Mining (SDM), 2008, pp. 1-12. |

[26] | F. Wang, P. Li, Efficient nonnegative matrix factorization with random projections, in: Proceedings of the 10th SIAM Conference on Data Mining (SDM), 2010, pp. 281-292. |

[27] | S. Z. Li, X. Hou, H. Zhang, Q. Cheng, Learning spatially localized parts-based representation, in: Proceedings of IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR), 2001, pp. 207-212. |

[28] | W. Xu, X. Liu, Y. Gong, Document clustering based on nonnegative matrix factorization, in: Proceedings of International Conference on Research and Development in Information Retrieval (SIGIR), 2003, pp. 267-273. |

[29] | Brunet, J.-P.; Tamayo, P.; Golub, T.R.; Mesirov, J.P., Metagenes and molecular pattern discovery using matrix factorization, Proceedings of the national Academy of sciences (PNAS), 101, 12, 4164-4169, (2004) |

[30] | Pauca, P.; Piper, J.; Plemmons, R., Nonnegative matrix factorization for spectral data analysis, Linear algebra and its applications, 406, 1, 29-47, (2006) · Zbl 1096.65033 |

[31] | Gillis, N.; Glineur, F., Using underapproximations for sparse nonnegative matrix factorization, Pattern recognition, 43, 4, 1676-1687, (2010) · Zbl 1191.68783 |

[32] | Kim, H.; Park, K., Non-negative matrix factorization based on alternating non-negativity constrained least squares and active set method, SIAM journal on matrix analysis and applications, 30, 2, 713-730, (2008) · Zbl 1162.65354 |

[33] | Berry, M.W.; Browne, M.; Langville, A.N.; Pauca, P.V.; Plemmons, R.J., Algorithms and applications for approximate nonnegative matrix factorization, Computational statistics and data analysis, 52, 1, 155-173, (2007) · Zbl 1452.90298 |

[34] | D. D. Lee, H. S. Seung, Algorithms for non-negative matrix factorization, in: Advances in Neural Information Processing Systems (NIPS) 13, 2001, pp. 556-562. |

[35] | Catral, M.; Han, L.; Neumann, M.; Plemmons, R., On reduced rank nonnegative matrix factorization for symmetric nonnegative matrices, Linear algebra and its applications, 393, 107-126, (2004) · Zbl 1085.15012 |

[36] | Lin, C.-J., On the convergence of multiplicative update algorithms for non-negative matrix factorization, IEEE transactions on neural networks, 18, 6, 1589-1596, (2007) |

[37] | Ding, C.H.Q.; Li, T.; Jordan, M.I., Convex and semi-nonnegative matrix factorization, IEEE transactions on pattern analysis and machine intelligence, 32, 1, 45-55, (2010) |

[38] | S. A. Nene, S. K. Nayar, J. Murase, Columbia Object Image Library (COIL-20), Technical Report, CUCS-005-96, Columbia Univ., Feb. 1996. |

[39] | Lyons, M.J.; Budynek, J.; Akamatsu, S., Automatic classification of single facial images, IEEE transactions on pattern analysis and machine intelligence, 21, 12, 1357-1362, (1999) |

[40] | Pei, B.; Bao, Z., Bispectrum based approach to high radar range profile for automatic target recognition, Pattern recognition, 35, 11, 2643-2651, (2002) · Zbl 1006.68915 |

[41] | Du, L.; Liu, H.; Bao, Z.; Xing, M., Radar HRRP target recognition based on higher order spectra, IEEE transactions on signal processing, 53, 7, 2359-2368, (2005) · Zbl 1370.94319 |

[42] | Chai, J.; Liu, H.; Bao, Z., Generalized re-weighting local sampling Mean discriminant analysis, Pattern recognition, 43, 10, 3422-3432, (2010) · Zbl 1213.68518 |

[43] | Xing, M.; Bao, Z.; Pei, B., Properties of high-resolution range profiles, Optical engineering, 41, 2, 493-504, (2002) |

[44] | Dempster, A.P.; Laird, N.M.; Rubin, D.B., Maximum likelihood from incomplete data via the EM algorithm, Journal of the royal statistical society series B (methodological), 39, 1, 1-38, (1977) · Zbl 0364.62022 |

[45] | Q. Gu, J. Zhou, C. Ding, Collaborative filtering: weighted nonnegative matrix factorization incorporating user and item graphs, in: Proceedings of the 10th SIAM Conference on Data Mining (SDM), 2010, pp. 199-210. |

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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.