Orthogonal nonnegative matrix t-factorizations for clustering

C. DingTao LiWei PengHaesun Park

article2006KDD1,386 citations

Establishes a rigorous mathematical foundation and convergent update algorithms for orthogonal three-factor nonnegative matrix factorization, enabling simultaneous, interpretable co-clustering of rows and columns in complex data matrices.

Listen

Modern data mining and information retrieval applications face severe challenges when categorizing large, complex collections of unstructured text and operational system logs. Standard clustering techniques typically partition either data items or their constituent features in isolation, missing valuable cross-dimensional relationships. While standard two-factor nonnegative matrix factorization decomposes data into lower-rank representations, enforcing strict structural conditions often degrades matrix approximation quality or leads to non-unique solutions.

The article evaluates a three-factor nonnegative matrix factorization model that incorporates an orthogonality constraint on both factors. It demonstrates how adding an intermediate scaling factor preserves accurate matrix approximations while establishing an exact mathematical equivalence to simultaneous row and column clustering.

To achieve this, the authors develop new iterative multiplicative update algorithms for one-sided and bi-orthogonal factorizations, mathematically proving their correctness and monotonic convergence. Across empirical tests, the model was evaluated on five standard document datasets—spanning from 476 technical reports to 20,000 Usenet newsgroup posts—and a real-world enterprise system log dataset. The evaluation assessed clustering quality using purity, entropy, and Adjusted Rand Index metrics, while introducing class conditional and multi-peak distributions to evaluate hard and soft word clustering.

Across the benchmark document datasets, the bi-orthogonal three-factor approach consistently matched or exceeded standard K-means clustering performance, achieving notable purity gains such as an improvement from 0.330 to 0.507 on the 20 Newsgroups corpus. In the system log management case study, the proposed model significantly outperformed K-means across all evaluation criteria, increasing purity from 0.684 to 0.806 and the Adjusted Rand Index from 0.572 to 0.856. Furthermore, multi-peak distribution analysis confirmed the model's ability to effectively separate domain-specific vocabulary from terms shared across multiple categories, enabling concurrent semantic profiling.

These findings indicate that organizations can improve automated document indexing, IT infrastructure log monitoring, and incident triage by adopting three-factor matrix decomposition. Simultaneous co-clustering reduces manual analysis overhead by concurrently categorizing operational records and identifying the primary descriptive keywords that characterize system faults or functional states.

Organizations seeking automated classification of unstructured text and operational logs should implement bi-orthogonal three-factor factorization over traditional one-sided clustering routines. For optimal results, implementations should leverage K-means clustering for model initialization and utilize multi-peak distribution profiles to interpret the semantic focus of extracted keywords.

Practical deployment must account for standard matrix decomposition trade-offs. The algorithms converge to local rather than global optima and approximate orthogonality conditions to prevent multiplicative updates from locking zero-valued entries permanently. Confidence in the reported performance remains high for high-dimensional, sparse text and log data, though performance in denser or continuous numeric domains requires further empirical validation.

Florida International University Georgia Institute of Technology Lawrence Berkeley National Laboratory classification clustering quality enterprise system nonnegative matrix factorization cluster indicator matrix spectral clustering

Ding et al (2006).pdf

Paper: Algorithms for Non-negative Matrix Factorization, Daniel D. Lee et al. (2000). Introduces the foundational multiplicative update algorithms and convergence proofs for standard nonnegative matrix factorization upon which the three-factor orthogonal extensions directly build.
Paper: Document clustering based on non-negative matrix factorization, Wei Xu et al. (2003). Pioneers the application of nonnegative matrix factorization to document clustering, establishing the baseline framework that orthogonal tri-factorization seeks to refine.
Paper: Co-clustering documents and words using bipartite spectral graph partitioning, Inderjit S. Dhillon (2001). Formalizes simultaneous co-clustering of documents and words via spectral graph partitioning, framing the exact problem that orthogonal nonnegative tri-factorization solves through matrix decomposition.
Paper: K-means clustering via principal component analysis, C. Ding et al. (2004). Derives the theoretical equivalence between continuous principal component relaxations and discrete K-means clustering, motivating the algebraic connections between matrix factor orthogonality and clustering indicators.
Paper: Non-negative Matrix Factorization with Sparseness Constraints, Patrik O. Hoyer (2004). Examines structural constraints in nonnegative matrix factorization to control feature representations and avoid non-unique, degraded approximations.
Paper: Kernel k-means: spectral clustering and normalized cuts, Inderjit S. Dhillon et al. (2004). Establishes the mathematical link between trace-maximization objectives in graph partitioning and iterative clustering relaxations.
Paper: Concept Decompositions for Large Sparse Text Data Using Clustering, I. Dhillon et al. (2004). Analyzes matrix approximations and concept decompositions for high-dimensional, sparse text datasets using geometric centroid projections.

Paper: Convex and Semi-Nonnegative Matrix Factorizations, C. Ding et al. (2010). Extends orthogonal and standard NMF to Semi-NMF and Convex-NMF, relaxing the nonnegativity constraint on input data matrices while preserving clustering interpretability.
Paper: Graph Regularized Nonnegative Matrix Factorization for Data Representation, Deng Cai et al. (2011). Incorporates local geometric manifold regularizations into nonnegative matrix factorization to preserve neighborhood structures alongside parts-based representations.
Paper: Relational learning via collective matrix factorization, Ajit P. Singh et al. (2008). Generalizes matrix factorization to multi-relational database schemes by collectively decomposing interconnected entity matrices.
Paper: V-Measure: A Conditional Entropy-Based External Cluster Evaluation Measure, Andrew Rosenberg et al. (2007). Develops the entropy-based V-Measure to provide a comprehensive, unbiased external evaluation metric for document and data clustering.
Paper: Information Theoretic Measures for Clusterings Comparison: Variants, Properties, Normalization and Correction for Chance, X. Nguyen et al. (2010). Systematically analyzes information-theoretic clustering comparison metrics and adjusts for chance agreement when evaluating partitioned datasets.
Paper: Tensor Decomposition for Signal Processing and Machine Learning, Nicholas D. Sidiropoulos et al. (2016). Extends low-rank decomposition techniques from two-dimensional matrix co-clustering to multi-way tensor representations with unique component identifiability.

Cover for Orthogonal nonnegative matrix t-factorizations for clustering

Abstract

Currently, most research on nonnegative matrix factorization (NMF) focus on 2-factor X = FG^T factorization. We provide a systematic analysis of 3-factor X = FSG^T NMF. While unconstrained 3-factor NMF is equivalent to unconstrained 2-factor NMF, constrained 3-factor NMF brings new features to constrained 2-factor NMF. We study the orthogonality constraint because it leads to rigorous clustering interpretation. We provide new rules for updating F,S,G and prove the convergence of these algorithms. Experiments on 5 datasets and a real world case study are performed to show the capability of bi-orthogonal 3-factor NMF on simultaneously clustering rows and columns of the input data matrix. We provide a new approach of evaluating the quality of clustering on words using class aggregate distribution and multi-peak distribution. We also provide an overview of various NMF extensions and examine their relationships.

Topics

classification clustering quality enterprise system it infrastructures k-means algorithm matrix factorizations multiplicative updates non-negative matrix factorization orthogonality trade

Keywords

nonnegative matrix factorization cluster indicator matrix spectral clustering document clustering word clustering orthogonality condition cluster purity Rand Index sparseness constraints

1. INTRODUCTION
2. UNIQUENESS OF ORTHOGONAL NMF
3. ORTHOGONAL NMF AND CLUSTERING
4. COMPUTING UNI-ORTHOGONAL NMF
5. COMPUTING BI-ORTHOGONAL NMF
6. SYMMETRIC 3-FACTOR NMF: W = HSHT
7. UNI-ORTHOGONAL NMF: CORRECTNESS AND CONVERGENCE
Correctness.
Convergence.
Proof of Theorem 5
Alternative Update Algorithm
8. 3-FACTOR NMF: CORRECTNESS AND CONVERGENCE
Alternative Update Algorithm
9. EXPERIMENTS
9.1 Datasets
9.2 Evaluation Measures
9.3 Document Clustering Result Analysis
9.4 Word Clustering Result Analysis
9.4.1 Hard Clustering Evaluation
9.4.2 Soft Clustering Evaluation
10. A CASE STUDY ON SYSTEM LOG DATA
11. NMF-RELATED FACTORIZATIONS
11.1 NMF and PLSI
12. SUMMARY
Acknowledgments
13. REFERENCES

Knowls

Knowl 1 — Bi-Orthogonal Nonnegative Matrix Tri-Factorization Formulation
model/method
Bi-orthogonal Nonnegative Matrix Tri-Factorization (BiOR-NM3F) decomposes a nonnegative data matrix $X \in \mathbb{R}^{p \times n}_+$ into three nonnegative matrix factors:

$X \approx F S G^T$

where $F \in \mathbb{R}^{p \times k}_+$ is the row cluster indicator matrix, $G \in \mathbb{R}^{n \times \ell}_+$ is the column cluster indicator matrix, and $S \in \mathbb{R}^{k \times \ell}_+$ is a factor matrix providing degrees of freedom to absorb the differing scales of $X, F,$ and $G$ . The parameters $k$ and $\ell$ represent the number of row clusters and column clusters, respectively (often set such that $k = \ell$ ).

The objective function optimization problem is defined as:

$\min_{F \ge 0, \, G \ge 0, \, S \ge 0} \|X - F S G^T\|^2 \quad \text{s.t.} \quad F^T F = I, \; G^T G = I$

where $\|\cdot\|$ denotes the Frobenius norm. Imposing orthogonality on both $F$ and $G$ eliminates transformation indeterminacy while enabling simultaneous co-clustering of rows and columns. Without the middle factor $S$ , a double-orthogonal two-factor factorization $X \approx F G^T$ is overly restrictive and yields poor low-rank matrix approximations.
Knowl 2 — Multiplicative Update Algorithm for Bi-Orthogonal 3-Factor NMF
algorithm
The Bi-orthogonal 3-Factor Nonnegative Matrix Factorization (BiOR-NM3F) algorithm iteratively solves $\min_{F \ge 0, G \ge 0, S \ge 0} \|X - F S G^T\|^2$ subject to $F^T F = I$ and $G^T G = I$ for a nonnegative data matrix $X \in \mathbb{R}^{p \times n}_+$ .
Input: Nonnegative data matrix $X \in \mathbb{R}^{p \times n}_+$ , row cluster count $k$ , column cluster count $\ell$ , max iterations $T$
Output: Row cluster indicator $F \in \mathbb{R}^{p \times k}_+$ , column cluster indicator $G \in \mathbb{R}^{n \times \ell}_+$ , cluster relation matrix $S \in \mathbb{R}^{k \times \ell}_+
Initialize $G \in \mathbb{R}^{n \times \ell}_+$ via column K-means clustering on $X$ , setting $G \leftarrow G + 0.2$
Initialize $F \in \mathbb{R}^{p \times k}_+$ via row K-means clustering on $X$ , setting $F \leftarrow F + 0.2$
Initialize $S \in \mathbb{R}^{k \times \ell}_+$ via $S \leftarrow F^T X G$
for $t = 1$ to $T$ do
     $G_{jk} \leftarrow G_{jk} \frac{(X^T F S)_{jk}}{(G G^T X^T F S)_{jk}}$ for all $j, k$
     $F_{ik} \leftarrow F_{ik} \frac{(X G S^T)_{ik}}{(F F^T X G S^T)_{ik}}$ for all $i, k$
     $S_{ik} \leftarrow S_{ik} \frac{(F^T X G)_{ik}}{(F^T F S G^T G)_{ik}}$ for all $i, k$
    if converged then
        break
    end if
end for
return $F, S, G$
The multiplicative update rules guarantee monotonic non-increase of the objective function $\|X - F S G^T\|^2$ . An alternative monotonic update rule for $S$ based on an auxiliary function with logarithmic terms is:

$S_{ik} \leftarrow S_{ik} \sqrt{\frac{(F^T X G)_{ik}}{(F^T F S G^T G)_{ik}}}$
Knowl 3 — Equivalence of Bi-Orthogonal 3-Factor NMF to Simultaneous Kernel K-Means
theoretical result
For a nonnegative data matrix $X \in \mathbb{R}^{p \times n}_+$ , the bi-orthogonal 3-factor NMF optimization problem

$\min_{F \ge 0, \, G \ge 0, \, S \ge 0} \|X - F S G^T\|^2 \quad \text{s.t.} \quad F^T F = I, \; G^T G = I$

is equivalent to performing kernel K-means clustering simultaneously on the rows and columns of $X$ .

For any fixed orthogonal matrices $F$ and $G$ , the optimal factor $S$ satisfies $S = F^T X G$ , with individual elements given by:

$S_{\ell k} = f_\ell^T X g_k = \frac{1}{|R_\ell|^{1/2} |C_k|^{1/2}} \sum_{i \in R_\ell} \sum_{j \in C_k} X_{ij}$

where $|R_\ell|$ is the number of elements in the $\ell$ -th row cluster $R_\ell$ and $|C_k|$ is the number of elements in the $k$ -th column cluster $C_k$ . The diagonal elements of $S$ represent within-cluster weights, while the off-diagonal elements represent between-cluster weights.

Substituting $S = F^T X G$ reduces the objective to alternating trace maximizations:
1. Column clustering: For a fixed $F$ , finding $G$ is equivalent to maximizing $\mathrm{Tr}[G^T (X^T F F^T X) G]$ subject to $G^T G = I, G \ge 0$ , which corresponds to kernel K-means on the columns of $X$ with kernel matrix $W = X^T F F^T X$ (the inner product of the projection of $X$ onto the subspace spanned by $F$ ).
2. Row clustering: For a fixed $G$ , finding $F$ is equivalent to maximizing $\mathrm{Tr}[F^T (X G G^T X^T) F]$ subject to $F^T F = I, F \ge 0$ , which corresponds to kernel K-means on the rows of $X$ with kernel matrix $W = X G G^T X^T$ (the inner product of the projection of $X$ onto the subspace spanned by $G$ ).
Knowl 4 — Uniqueness of Solution in Orthogonal Nonnegative Matrix Factorization
theoretical result
In standard two-factor Nonnegative Matrix Factorization $X \approx F G^T$ with $X \in \mathbb{R}^{p \times n}_+$ , $F \in \mathbb{R}^{p \times k}_+$ , and $G \in \mathbb{R}^{n \times k}_+$ , there exists continuous transformation indeterminacy: any non-singular matrices $A, B$ satisfying $A B^T = I$ , $F A \ge 0$ , and $G B \ge 0$ yield an identical reconstruction error $\|X - (F A)(G B)^T\| = \|X - F G^T\|$ .

Under the orthogonality condition $F^T F = I$ , this continuous degree of freedom is eliminated: There exist no matrices $A$ and $B$ that simultaneously satisfy $A B^T = I$ , $F A \ge 0$ , $G B \ge 0$ , and $(F A)^T (F A) = I$ , except when $A$ and $B$ are permutation matrices $P$ satisfying $A = P$ , $B = P^T$ , $P^T P = I$ , and $P_{ij} \in \{0, 1\}$ .
Knowl 5 — Equivalence of One-Sided Orthogonal NMF to K-Means Clustering
theoretical result
One-sided orthogonal Nonnegative Matrix Factorization

$\min_{F \ge 0, \, G \ge 0} \|X - F G^T\|^2 \quad \text{s.t.} \quad G^T G = I$

for a data matrix $X \in \mathbb{R}^{p \times n}_+$ is mathematically equivalent to standard K-means clustering on the columns of $X$ .

Setting the derivative with respect to $F$ to zero yields the stationary condition $F = X G$ . Substituting $F = X G$ into the objective reformulates the problem as:

$\max_{G \ge 0, \, G^T G = I} \mathrm{Tr}(G^T X^T X G)$

which is identical to the trace-maximization formulation of K-means clustering, where $G$ acts as the normalized cluster indicator matrix and $X^T X$ represents the pairwise inner-product kernel matrix $W_{ij} = x_i^T x_j$ . This equivalence holds even when $X$ and $F$ contain mixed-sign entries.
Knowl 6 — Matrix Trace Inequality for Monotonicity Proofs in Orthogonal NMF
theoretical result
Let $A \in \mathbb{R}^{n \times n}_+$ and $B \in \mathbb{R}^{k \times k}_+$ be symmetric nonnegative matrices, and let $S \in \mathbb{R}^{n \times k}_+$ and $S' \in \mathbb{R}^{n \times k}_+$ be nonnegative matrices. The following matrix trace inequality holds:

$\sum_{i=1}^n \sum_{p=1}^k \frac{(A S' B)_{ip} S_{ip}^2}{S'_{ip}} \ge \mathrm{Tr}(S^T A S B)$

Equality holds when $S = S'$ .

This inequality serves as the foundation for constructing auxiliary functions $Z(S, S') \ge J(S)$ that majorize the Lagrangian objective functions in orthogonal NMF formulations, thereby establishing the monotonic convergence of multiplicative update algorithms.
Knowl 7 — Multiplicative Update Rules for Uni-Orthogonal Nonnegative Matrix Factorization
algorithm
Uni-orthogonal Nonnegative Matrix Factorization minimizes $\|X - F G^T\|^2$ for a nonnegative data matrix $X \in \mathbb{R}^{p \times n}_+$ subject to nonnegativity and orthogonality on either $F$ or $G$ .
Input: Nonnegative data matrix $X \in \mathbb{R}^{p \times n}_+$ , cluster count $k$ , constraint mode $\in \{F\text{-orthogonal}, G\text{-orthogonal}\}$ , max iterations $T$
Output: Nonnegative factor matrices $F \in \mathbb{R}^{p \times k}_+$ , $G \in \mathbb{R}^{n \times k}_+
Initialize $F$ with cluster centroids from K-means on the columns of $X$
Initialize $G$ with column cluster indicator matrix plus $0.2$
for $t = 1$ to $T$ do
    if constraint mode is $F\text{-orthogonal}$ ( $F^T F = I$ ) then
         $G_{jk} \leftarrow G_{jk} \frac{(X^T F)_{jk}}{(G F^T F)_{jk}}$ for all $j, k$
         $F_{ik} \leftarrow F_{ik} \frac{(X G)_{ik}}{(F F^T X G)_{ik}}$ for all $i, k$
    else if constraint mode is $G\text{-orthogonal}$ ( $G^T G = I$ ) then
         $G_{jk} \leftarrow G_{jk} \frac{(X^T F)_{jk}}{(G G^T X^T F)_{jk}}$ for all $j, k$
         $F_{ik} \leftarrow F_{ik} \frac{(X G)_{ik}}{(F G^T G)_{ik}}$ for all $i, k$
    end if
    if converged then
        break
    end if
end for
return $F, G$
The update for $F$ under the $F^T F = I$ constraint derives from the Lagrangian multiplier $\lambda = F^T X G - G^T G$ . An alternative monotonic update rule for $F$ in the $F$ -orthogonal case is:

$F_{ik} \leftarrow F_{ik} \sqrt{\frac{(X G)_{ik}}{(F F^T X G)_{ik}}}$
Knowl 8 — Symmetric 3-Factor NMF for Pairwise Similarity Matrices
algorithm
When the input matrix is a symmetric pairwise similarity matrix $W = X = X^T \in \mathbb{R}^{n \times n}_+$ , bi-orthogonal 3-factor NMF reduces to symmetric 3-factor NMF where $F = G = H \in \mathbb{R}^{n \times k}_+$ :

$\min_{H \ge 0, \, S \ge 0} \|W - H S H^T\|^2 \quad \text{s.t.} \quad H^T H = I$

where $H$ is the object cluster indicator matrix and $S \in \mathbb{R}^{k \times k}_+$ represents inter-cluster and intra-cluster similarity relationships.
Input: Symmetric similarity matrix $W \in \mathbb{R}^{n \times n}_+$ , cluster count $k$ , max iterations $T$
Output: Nonnegative cluster indicator $H \in \mathbb{R}^{n \times k}_+$ , cluster relation matrix $S \in \mathbb{R}^{k \times k}_+
Initialize $H \ge 0$ and $S \ge 0$
for $t = 1$ to $T$ do
     $H_{jk} \leftarrow H_{jk} \frac{(W^T H S)_{jk}}{(H H^T W^T H S)_{jk}}$ for all $j, k$
     $S_{ik} \leftarrow S_{ik} \frac{(H^T W H)_{ik}}{(H^T H S H^T H)_{ik}}$ for all $i, k$
    if converged then
        break
    end if
end for
return $H, S$
These multiplicative updates guarantee nonnegativity of $H$ and $S$ while monotonically non-increasing the objective value $\|W - H S H^T\|^2$ .
Knowl 9 — Multi-Peak Distribution Framework for Soft Word Clustering Evaluation
model/method
In bi-orthogonal 3-factor NMF ( $X \approx F S G^T$ ), the $i$ -th row of factor matrix $F \in \mathbb{R}^{p \times K}_+$ represents the posterior distribution $(p_1, \dots, p_K)$ of word $i$ over $K$ clusters, normalized such that $\sum_{k=1}^K p_k = 1$ . Because exact orthogonality is slightly relaxed during multiplicative updates, words can belong to multiple clusters (soft clustering).

To categorize word specificity, the multi-peak distribution method defines $K$ prototype distributions representing levels of peakiness:

$P_1 = (1, 0, \dots, 0), \quad P_2 = \left(\frac{1}{2}, \frac{1}{2}, 0, \dots, 0\right), \quad \dots, \quad P_K = \left(\frac{1}{K}, \dots, \frac{1}{K}\right)$

For each word $i$ , its normalized posterior distribution is sorted in descending order, $(p_{(1)}, p_{(2)}, \dots, p_{(K)})$ , and assigned to the prototype $P_m$ that minimizes Euclidean distance:

$m^* = \arg\min_{m \in \{1, \dots, K\}} \left\| (p_{(1)}, \dots, p_{(K)}) - P_m \right\|_2$

Words assigned to $P_1$ (1-peak words) contain domain-specific semantic content tied to a single cluster, whereas words with higher peak counts ( $m \ge 2$ ) represent shared vocabulary spanning multiple topical domains.
Knowl 10 — Hard Clustering Evaluation of Words via Class Aggregate Distributions
model/method
Because text corpora lack ground-truth class labels for words (the rows of data matrix $X$ ), hard word clustering derived from the row indicator matrix $F \in \mathbb{R}^{p \times K}_+$ in BiOR-NM3F is evaluated against class-conditional aggregate distributions:
1. Word Cluster Assignment: Each word $i$ is assigned to the cluster with the highest posterior weight: $k^* = \arg\max_k F_{ik}$ .
2. Ground-Truth Proxy Construction: For each labeled document class $c \in \{1, \dots, K\}$ , the aggregate word distribution (the occurrence frequency of each word across all documents in class $c$ ) is computed. Each word is assigned an objective pseudo-label matching the document class where its aggregate frequency is highest.
3. Metric Computation: Predicted word clusters are compared against the pseudo-labels using Purity, Entropy, and Adjusted Rand Index (ARI).
Hard clustering performance of BiOR-NM3F on words across five benchmark corpora:
- CSTR: Purity = 0.718, Entropy = 0.490, ARI = 0.478
- WebKB4: Purity = 0.666, Entropy = 0.668, ARI = 0.379
- Reuters: Purity = 0.479, Entropy = 0.983, ARI = 0.272
- WebAce: Purity = 0.599, Entropy = 0.857, ARI = 0.479
- Newsgroups: Purity = 0.602, Entropy = 0.886, ARI = 0.275
Knowl 11 — Document Clustering Performance of BiOR-NM3F vs K-Means across Benchmark Corpora
empirical result
Bi-orthogonal 3-factor NMF (BiOR-NM3F) was evaluated against standard K-means clustering on five standard text categorization corpora. Documents were represented as binary vectors over the top 1,000 words selected by mutual information with class labels. Clustering quality was evaluated using Purity, Entropy, and Adjusted Rand Index (ARI).
Could not parse LaTeX table
BiOR-NM3F consistently outperformed K-means on CSTR, WebKB4, Reuters, and Newsgroups in Purity and ARI, with a substantial purity gain on Newsgroups (0.507 vs. 0.330) and an ARI gain on CSTR (0.436 vs. 0.189). On WebAce, K-means achieved a slightly higher purity (by 0.005). BiOR-NM3F achieved these results while simultaneously performing co-clustering of words and documents.
Knowl 12 — Semantic Situation Clustering of System Log Data Using BiOR-NM3F
empirical result
BiOR-NM3F was applied to cluster free-format ASCII system log messages collected across multiple operating systems into semantic situations (including start, stop, dependency, create, connection, report, request, configuration, other) labeled by domain experts.
Could not parse LaTeX table
BiOR-NM3F outperformed K-means across all evaluation metrics on system log data. Additionally, multi-peak word posterior analysis accurately identified characteristic vocabulary for each semantic situation: 1-peak keywords such as "started", "starting", and "service" aligned with the start situation; "configuration" aligned with configure; and "contact" aligned with dependency.

Coverage note — Section 11 (Overview of NMF Related Factorizations: Semi-NMF, PCA connections, and PLSI-NMF equivalence) was omitted as it reviews prior literature rather than presenting new contributions.

References

1.M.W. Berry, S.T. Dumais, and Gavin W. O'Brien. Using linear algebra for intelligent information retrieval. SIAM Review, 37:573–595, 1995.
2.D. Boley. Principal direction divisive partitioning. Data mining and knowledge discovery, 2:325–344, 1998.
3.J.-P. Brunet, P. Tamayo, T.R. Golub, and J.P. Mesirov. Metagenes and molecular pattern discovery using matrix factorization. Proc. Natl Academy of Sciences USA, 102(12):4164–4169, 2004.
4.M. Chessell. Specification: Common base event, 2003. http://www-128.ibm.com /developerworks/webservices/library/ws-cbe/.
5.M. Cooper and J. Foote. Summarizing video using non-negative similarity matrix factorization. In Proc. IEEE Workshop on Multimedia Signal Processing, pages 25–28, 2002.
6.I. Dhillon and D. Modha. Concept decomposition for large sparse text data using clustering. Machine Learning, 42:143–175, 2001.
7.I. S. Dhillon. Co-clustering documents and words using bipartite spectral graph partitioning. Proc. ACM Int’l Conf Knowledge Disc. Data Mining (KDD 2001), 2001.
8.C. Ding and X. He. K-means clustering and principal component analysis. Int’l Conf. Machine Learning (ICML), 2004.
9.C. Ding, X. He, and H.D. Simon. On the equivalence of nonnegative matrix factorization and spectral clustering. Proc. SIAM Data Mining Conf, 2005.
10.C. Ding, X. He, H. Zha, and H. Simon. Unsupervised learning: self-aggregation in scaled principal component space. Proc. 6th European Conf. Principles of Data Mining and Knowledge Discovery (PKDD), pages 112–124, 2002.
11.C. Ding, T. Li, and M. Jordan. Convex and semi-nonnegative matrix factorizations for clustering and low-dimension representation. Technical Report LBNL-60428, Lawrence Berkeley National Laboratory, University of California, Berkeley, 2006.
12.C. Ding, T. Li, and W. Peng. Nonnegative matrix factorization and probabilistic latent semantic indexing: Equivalence, chi-square statistic, and a hybrid method. In Proc. of National Conf. on Artificial Intelligence (AAAI-06), 2006.
13.E. Han, D. Boley, M. Gini, R. Gross, K. Hastings, G. Karypis, V. Kumar, B. Mobasher, and J. Moore. WebACE: A web agent for document categorization and exploration. In Proceedings of the 2nd International Conference on Autonomous Agents (Agents’98). ACM Press, 1998.
14.T. Hofmann. Probabilistic latent semantic analysis. In Proceedings of the 15th Annual Conference on Uncertainty in Artificial Intelligence (UAI-99), pages 289–296, 1999.
15.P. O. Hoyer. Non-negative matrix factorization with sparseness constraints. J. Machine Learning Research, 5:1457–1469, 2004.
16.P. O. Hoyer. Non-negative matrix factorization with sparseness constraints. J. Machine Learning Research, 5:1457–1469, 2004.
17.G. Karypis and E.-H. Han. Concept indexing: A fast dimensionality reduction algorithm with applications to document retrieval and categorization. Proc. 9th Int’l Conf. Information and Knowledge Management (CIKM 2000), 2000.
18.D.D. Lee and H. S. Seung. Learning the parts of objects by non-negative matrix factorization. Nature, 401:788–791, 1999.
19.D.D. Lee and H. S. Seung. Algorithms for non-negatvie matrix factorization. In T. G. Dietterich and V. Tresp, editors, Advances in Neural Information Processing Systems, volume 13. 2001.
20.S.Z. Li, X. Hou, H. Zhang, and Q. Cheng. Learning spatially localized, parts-based representation. In Proceedings of IEEE Computer Vision and Pattern Recognition, pages 207–212, 2001.
21.T. Li. A general model for clustering binary data. In KDD, pages 188–197, 2005.
22.T. Li, F. Liang, S. Ma, and W. Peng. An integrated framework on mining log files for computing system management. In KDD, 2005.
23.T. Li, S. Ma, and M. Ogihara. Document clustering via adaptive subspace iteration. In SIGIR, pages 218–225, 2004.
24.B. Long, Z. Zhang, and P.S. Yu. Co-clustering by block value decomposition. In Proc. SIGKDD Int’l Conf. on Knowledge Discovery in Data Mining (KDD’05), pp.635–640.
25.A.K. McCallum. Bow: A toolkit for statistical language modeling, text retrieval, classification and clustering. http://www.cs.cmu.edu/ mccallum/bow, 1996.
26.G.W. Milligan and M.C. Cooper. A study of the comparability of external criteria for hierarchical cluster analysis. Multivar Behav Res, 21:846–850, 1986.
27.P. Paatero and U. Tapper. Positive matrix factorization: A non-negative factor model with optimal utilization of error estimates of data values. Environmetrics, 5:111–126, 1994.
28.H. Park and P. Howland. Generalizing discriminant analysis using the generalized singular value decomposition. IEEE. Trans. on Pattern Analysis and Machine Intelligence, 26:995 – 1006, 2004.
29.W.M. Rand. Objective criteria for the evaluation of clustering methods. J Am Stat Assoc, 66:846–850, 1971.
30.F. Sha, L.K. Saul, and D.D. Lee. Multiplicative updates for nonnegative quadratic programming in support vector machines. In Advances in Neural Information Processing Systems 15, pages 1041–1048. 2003.
31.J. Stearley. Toward informatic analysis of syslogs. In Proceedings of IEEE International Conference on Cluster Computing, 2004.
32.W. Xu, X. Liu, and Y. Gong. Document clustering based on non-negative matrix factorization. In Proc. ACM conf. Research and development in IR(SIRGIR), pages 267–273, Toronto, Canada, 2003.
33.D. Zeimpekis and E. Gallopoulos. Clsi: A flexible approximation scheme from clustered term-document matrices. Proc. SIAM Data Mining Conf, pages 631–635, 2005.
34.H. Zha, C. Ding, M. Gu, X. He, and H.D. Simon. Spectral relaxation for K-means clustering. Advances in Neural Information Processing Systems 14 (NIPS’01), pages 1057–1064, 2002.
35.H. Zha, X. He, C. Ding, M. Gu, and H.D. Simon. Bipartite graph partitioning and data clustering. Proc. Int’l Conf. Information and Knowledge Management (CIKM 2001), 2001.
36.Y. Zhao and G. Karypis. Empirical and theoretical comparisons of selected criterion functions for document clustering. Machine Learning, 55(3):311–331, 2004.

Citation

MLA

Ding, C., et al. “Orthogonal Nonnegative Matrix T-factorizations for Clustering”. Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2006, pp. 126–35, https://doi.org/10.1145/1150402.1150420.

APA

Ding, C., Li, T., Peng, W., & Park, H. (2006). Orthogonal nonnegative matrix t-factorizations for clustering. Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 126–135. https://doi.org/10.1145/1150402.1150420

Chicago

Ding, C., T. Li, W. Peng, and H. Park. 2006. “Orthogonal Nonnegative Matrix T-factorizations for Clustering”. Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 126–35. https://doi.org/10.1145/1150402.1150420.

Harvard

Ding, C. et al. (2006) “Orthogonal nonnegative matrix t-factorizations for clustering”, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, pp. 126–135. Available at: https://doi.org/10.1145/1150402.1150420.

Vancouver

1. Ding C, Li T, Peng W, Park H (2006) Orthogonal nonnegative matrix t-factorizations for clustering. In: Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, pp 126–135

BibTeX

@inproceedings{Ding_2006, series={KDD06}, title={Orthogonal nonnegative matrix t-factorizations for clustering}, url={http://dx.doi.org/10.1145/1150402.1150420}, DOI={10.1145/1150402.1150420}, booktitle={Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining}, publisher={ACM}, author={Ding, Chris and Li, Tao and Peng, Wei and Park, Haesun}, year={2006}, month=Aug, pages={126–135}, collection={KDD06} }

Metadata:Crossref

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

Orthogonal nonnegative matrix t-factorizations for clustering

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Bi-Orthogonal Nonnegative Matrix Tri-Factorization Formulation

Knowl 2 — Multiplicative Update Algorithm for Bi-Orthogonal 3-Factor NMF

Knowl 3 — Equivalence of Bi-Orthogonal 3-Factor NMF to Simultaneous Kernel K-Means

Knowl 4 — Uniqueness of Solution in Orthogonal Nonnegative Matrix Factorization

Knowl 5 — Equivalence of One-Sided Orthogonal NMF to K-Means Clustering

Knowl 6 — Matrix Trace Inequality for Monotonicity Proofs in Orthogonal NMF

Knowl 7 — Multiplicative Update Rules for Uni-Orthogonal Nonnegative Matrix Factorization

Knowl 8 — Symmetric 3-Factor NMF for Pairwise Similarity Matrices

Knowl 9 — Multi-Peak Distribution Framework for Soft Word Clustering Evaluation

Knowl 10 — Hard Clustering Evaluation of Words via Class Aggregate Distributions

Knowl 11 — Document Clustering Performance of BiOR-NM3F vs K-Means across Benchmark Corpora

Knowl 12 — Semantic Situation Clustering of System Log Data Using BiOR-NM3F

References

Citation

BibTeX

Access the Paper