SMARTech Collection: Computational Science and Engineering Technical Reports

Sparse Nonnegative Matrix Factorization for Clustering

Mon, 29 Oct 2007 22:58:59 GMT

Title: Sparse Nonnegative Matrix Factorization for Clustering

Authors: Kim, Jingu; Park, Haesun

Abstract: Properties of Nonnegative Matrix Factorization (NMF) as a clustering method are studied by relating its formulation to other methods such as K-means clustering. We show how interpreting the objective function of K-means as that of a lower rank approximation with special constraints allows comparisons between the constraints of NMF and K-means and provides the insight that some constraints can be relaxed from K-means to achieve NMF formulation. By introducing sparsity constraints on the coefficient matrix factor in NMF objective function, we in term can view NMF as a clustering method. We tested sparse NMF as a clustering method, and our experimental results with synthetic and text data shows that sparse NMF does not simply provide an alternative to K-means, but rather gives much better and consistent solutions to the clustering problem. In addition, the consistency of solutions further explains how NMF can be used to determine the unknown number of clusters from data. We also tested with a recently proposed clustering algorithm, Affinity Propagation, and achieved comparable results. A fast alternating nonnegative least squares algorithm was used to obtain NMF and sparse NMF.

Non-Negative Matrix Factorization Based on Alternating Non-Negativity Constrained Least Squares and Active Set Method

Sun, 29 Oct 2006 22:58:59 GMT

Title: Non-Negative Matrix Factorization Based on Alternating Non-Negativity Constrained Least Squares and Active Set Method

Authors: Kim, Hyunsoo; Park, Haesun

Fast Linear Discriminant Analysis using QR Decomposition and Regularization

Thu, 22 Mar 2007 22:58:59 GMT

Title: Fast Linear Discriminant Analysis using QR Decomposition and Regularization

Authors: Park, Haesun; Drake, Barry L.; Lee, Sangmin; Park, Cheong Hee

Abstract: Linear Discriminant Analysis (LDA) is among the most optimal dimension reduction methods for classification, which provides a high degree of class separability for numerous applications from science and engineering. However, problems arise with this classical method when one or both of the scatter matrices is singular. Singular scatter matrices are not unusual in many applications, especially for high-dimensional data. For high-dimensional undersampled and oversampled problems, the classical LDA requires modification in order to solve a wider range of problems. In recent work the generalized singular value decomposition (GSVD) has been shown to mitigate the issue of singular scatter matrices, and a new algorithm, LDA/GSVD, has been shown to be very robust for many applications in machine learning. However, the GSVD inherently has a considerable computational overhead. In this paper, we propose fast algorithms based on the QR decomposition and regularization that solve the LDA/GSVD computational bottleneck. In addition, we present fast algorithms for classical LDA and regularized LDA utilizing the framework based on LDA/GSVD and preprocessing by the Cholesky decomposition. Experimental results are presented that demonstrate substantial speedup in all of classical LDA, regularized LDA, and LDA/GSVD algorithms without any sacrifice in classification performance for a wide range of machine learning applications.

Sparse Non-negative Matrix Factorizations via Alternating Non-negativity-constrained Least Squares

Sat, 29 Oct 2005 22:58:59 GMT

Title: Sparse Non-negative Matrix Factorizations via Alternating Non-negativity-constrained Least Squares

Authors: Kim, Hyunsoo; Park, Haesun

Abstract: Many practical pattern recognition problems require non-negativity constraints. For example, pixels in digital images and chemical concentrations in bioinformatics are non-negative. Non-negative matrix factorization (NMF) is a useful technique in approximating these high dimensional data. Sparse NMFs are also useful when we need to control the degree of sparseness in non-negative basis vectors or non-negative lower-dimensional representations. In this paper, we introduce novel sparse NMFs via alternating non-negativity-constrained least squares. We applied one of the proposed sparse NMFs to cancer class discovery and gene expression data analysis. Our experimental results illustrate that our proposed method achieves better clustering performance than NMF based on multiplicative update rules and sparse NMFs based on the gradient descent method.