Non-negative matrix factorization

Non-negative matrix factorization (NMF) is a group of algorithms in multivariate analysis and linear algebra where a matrix, $\mathbf{X}$ , is factorized into (usually) two matrices, $\mathbf{W}$ and $\mathbf{H}$ : $\operatorname{nmf}(\mathbf{X}) \rightarrow \mathbf{WH}$

Factorization of matrices is generally non-unique, and a number of different methods of doing so have been developed (e.g. principal component analysis and singular value decomposition) by incorporating different constraints; non-negative matrix factorization differs from these methods in that it enforces the constraint that the factors W and H must be non-negative, i.e., all elements must be equal to or greater than zero.

History

Early work on non-negative matrix factorizations was performed by a Finnish group of researchers in the middle of the 1990s under the name positive matrix factorization.¹² It became more widely known as non-negative matrix factorization after Lee and Seung investigated the properties of the algorithm and published some simple and useful algorithms for two types of factorizations.³⁴

Types

Approximative non-negative matrix factorization

Usually the number of columns of W and the number of rows of H in NMF are selected so the product WH will become an approximation to X (it has been suggested that the NMF model should be called nonnegative matrix approximation instead). The full decomposition of X then amounts to the two non-negative matrices W and H as well as a residual U, such that: X = WH + U. The elements of the residual matrix can either be negative or positive.

Different cost functions and regularizations

There are different types of non-negative matrix factorizations. The different types arise from using different cost functions for measuring the divergence between X and WH and possibly by regularization of the W and/or H matrices.⁵

Two simple divergence functions studied by Lee and Seung are the squared error (or Frobenius norm) and an extension of the Kullback-Leibler divergence to positive matrices (the original Kullback-Leibler divergence is defined on probability distributions). Each divergence leads to a different NMF algorithm, usually minimizing the divergence using iterative update rules.

The factorization problem in the squared error version of NMF may be stated as: Given a nonnegative matrix $\mathbf{X}$ find nonnegative matrices W and H that minimize the function

Algorithms

There are several ways in which the W and H may be found: Lee and Seung's updates are usually referred to as the multiplicative update method, while others have suggested gradient descent algorithms and so-called alternating non-negative least squares and "projected gradient".⁷⁸

The algorithms may be less than ideal, however, as they typically can only be guaranteed to find local minima, rather than a global minimum of the cost function but in many data mining applications a local minimum may still be enough to be useful.

Relation to other Techniques

The initial paper by Lee & Seung proposed NMF mainly for parts-based decomposition of images. It compares NMF to vector quantization and principal component analysis, and shows that although the three techniques may be written as factorizations, they implement different constraints and therefore produce different results.

It was later shown that some types of NMF are an instance of a more general probabilistic model called "multinomial PCA".⁹ When NMF is obtained by minimizing the Kullback–Leibler divergence, it is in fact equivalent to another instance of multinomial PCA, probabilistic latent semantic analysis,¹⁰ trained by maximum likelihood estimation. That method is commonly used for analyzing and clustering textual data and is also related to the latent class model.

It was also shown¹¹ that when the Frobenius norm is used as a divergence, NMF is equivalent to a relaxed form of K-means clustering: matrix factor W contains cluster centroids and H contains cluster membership indicators. This also justifies the use of NMF for data clustering.

Uniqueness

The factorization is not unique: A matrix and its inverse can be used to transform the two factorization matrices by, e.g.,¹⁴

If the two new matrices $\mathbf{\tilde{W} = WB}$ and $\mathbf{\tilde{H}}=\mathbf{B}^{-1}\mathbf{H}$ are non-negative they form another parametrization of the factorization.

The non-negativity of $\mathbf{\tilde{W}}$ and $\mathbf{\tilde{H}}$ applies at least if B is a non-negative monomial matrix. In this simple case it will just correspond to a scaling and a permutation.

More control over the non-uniqueness of NMF is obtained with sparsity constraints.¹⁵

Applications

Text mining

NMF can be used for text mining applications. In this process, a document-term matrix is constructed with the weights of various terms (typically weighted word frequency information) from a set of documents. This matrix is factored into a term-feature and a feature-document matrix. The features are inferred by the contents of the documents, and the feature-document matrix describes data clusters of related documents.

One specific application clustered parts of the Enron email dataset¹⁶ with 65,033 messages and 91,133 terms into 50 clusters.¹⁷

Spectral data analysis

NMF is also used to analyze spectral data; one such use is in the classification of space objects and debris.¹⁸

Current research

Current research in approximate nonnegative matrix factorization includes searching for techniques to initialize the factor matrices for various algorithms, algorithms to find global minima for the factors, and efficient ways to update the factors when new data is added to the matrix.

Sources and external links

Notes

^ P. Paatero, U. Tapper (1994). "Positive matrix factorization: A non-negative factor model with optimal utilization of error estimates of data values". Environmetrics 5: 111–126. doi:10.1002/env.3170050203.
^ Pia Anttila, Pentti Paatero, Unto Tapper, Olli Järvinen (1995). "Source identification of bulk wet deposition in Finland by positive matrix factorization". Atmospheric Environment 29 (14): 1705–1718. doi:10.1016/1352-2310(94)00367-T.
^ Daniel D. Lee and H. Sebastian Seung (1999). "Learning the parts of objects by non-negative matrix factorization". Nature 401 (6755): 788–791.
^ Daniel D. Lee and H. Sebastian Seung (2001). "Algorithms for Non-negative Matrix Factorization". Advances in Neural Information Processing Systems 13: Proceedings of the 2000 Conference: 556–562, MIT Press.
^ Inderjit S. Dhillon, Suvrit Sra (2005). "Generalized Nonnegative Matrix Approximations with Bregman Divergences" (PDF). NIPS.
^ Taiping Zhanga, Bin Fang, Weining Liu, Yuan Yan Tang, Guanghui He and Jing Wen (June 2008). "Total variation norm-based nonnegative matrix factorization for identifying discriminant representation of image patterns". Neurocomputing 71 (10–12): 1824–1831. doi:10.1016/j.neucom.2008.01.022.
^ Chih-Jen Lin (October 2007). "Projected Gradient Methods for Non-negative Matrix Factorization" (PDF). Neural Computation 19 (10), http://www.csie.ntu.edu.tw/~cjlin/papers/pgradnmf.pdf.
^ Chih-Jen Lin (November 2007). "On the Convergence of Multiplicative Update Algorithms for Nonnegative Matrix Factorization". IEEE Transactions on Neural Networks 18 (6): 1589–1596. doi:10.1109/TNN.2007.895831.
^ Wray Buntine (2002). "Extensions to EM and Multinomial PCA" (PDF). Proc. European Conference on Machine Learning (ECML-02) 2430: 23-34.
^ Eric Gaussier and Cyril Goutte (2005). "Relation between PLSA and NMF and Implications" (PDF). Proc. 28th international ACM SIGIR conference on Research and development in information retrieval (SIGIR-05): 601-602.
^ Chris Ding, Xiaofeng He, and Horst D. Simon (2005). "On the Equivalence of Nonnegative Matrix Factorization and Spectral Clustering". Proc. SIAM Int'l Conf. Data Mining, pp. 606-610.
^ Pentti Paatero (1999). "The Multilinear Engine: A Table-Driven, Least Squares Program for Solving Multilinear Problems, including the n-Way Parallel Factor Analysis Model". Journal of Computational and Graphical Statistics 8 (4): 854–888.
^ Max Welling and Markus Weber (2001). "Positive Tensor Factorization". Pattern Recognition Letters 22 (12): 1255–1261. doi:10.1016/S0167-8655(01)00070-8.
^ Wei Xu, Xin Liu & Yihong Gong (2003). "Document clustering based on non-negative matrix factorization". Proceedings of the 26th annual international ACM SIGIR conference on Research and development in informaion retrieval: 267–273, New York: Association for Computing Machinery.
^ Julian Eggert, Edgar Körner, "Sparse coding and NMF", Proceedings. 2004 IEEE International Joint Conference on Neural Networks, 2004., pp. 2529-2533, 2004.
^ William W. Cohen (2005-04-04). "Enron Email Dataset". Retrieved on 2008-08-26.
^ Michael W. Berry & Murray Browne (October 2005). "Email Surveillance Using Non-negative Matrix Factorization". Computational & Mathematical Organization Theory 11 (3): 249–264. doi:10.1007/s10588-005-5380-5.
^ Michael W. Berry, et al. (June 2006). Algorithms and Applications for Approximate Nonnegative Matrix Factorization.

Others

J. Shen, G. W. Israël (1989). "A receptor model using a specific non-negative transformation technique for ambient aerosol". Atmospheric Environment 23 (10): 2289–2298.
Pentti Paatero (May 1997). "Least squares formulation of robust non-negative factor analysis". Chemometrics and Intelligent Laboratory Systems 37 (1): 23–35. doi:10.1016/S0169-7439(96)00044-5.
Raul Kompass (March 2007). "A Generalized Divergence Measure for Nonnegative Matrix Factorization". Neural Computation 19 (3): 780–791. doi:10.1162/neco.2007.19.3.780. PMID 17298233, http://neco.mitpress.org/cgi/content/abstract/19/3/780.
Amy N. Langville, Michael W. Berry, Murray Browne, V. Paul Pauca, and Robert J. Plemmons. A Survey of Algorithms and Applications for the Nonnegative Matrix Factorization. Computational Statistics and Data Analysis. Elsevier. Submitted Jan. 2006.
Liu, W.X. and Zheng, N.N. and You, Q.B. (2006). "Nonnegative Matrix Factorization and its applications in pattern recognition" (PDF). Chinese Science Bulletin 51 (17–18): 7–18. doi:10.1007/s11434-005-1109-6, http://www.springerlink.com/index/7285V70531634264.pdf.
Ngoc-Diep Ho, Paul Van Dooren and Vincent Blondel (2007). Descent Methods for Nonnegative Matrix Factorization, http://arxiv.org/abs/0801.3199.
Andrzej Cichocki, Rafal Zdunek and Shun-ichi Amari (January 2008). "Nonnegative Matrix and Tensor Factorization". IEEE Signal Processing Magazine 25 (1): 142–145. doi:10.1109/MSP.2008.4408452.
H. Kim and H. Park (2008). "Nonnegative matrix factorization based on alternating nonnegativity constrained least squares and active set method". SIAM Journal on Matrix Analysis and Applications 30 (2): 713–730.
H. Kim and H. Park (2007). "Sparse non-negative matrix factorizations via alternating non-negativity-constrained least squares for microarray data analysis". Bioinformatics 23 (12): 1495–1502. doi:10.1093/bioinformatics/btm134, http://bioinformatics.oxfordjournals.org/cgi/content/abstract/23/12/1495.

Contents