Constrained Clustering With Nonnegative Matrix Factorization.

Area of Science:

• Machine Learning
• Data Mining
• Computational Biology

Background:

• Nonnegative Matrix Factorization (NMF) and symmetric NMF (SymNMF) are effective for clustering linearly and nonlinearly separable data, respectively.
• Practical clustering often requires incorporating must-link and cannot-link constraints.

Purpose of the Study:

• To propose a novel NMF-based constrained clustering framework.
• To integrate must-link and cannot-link constraints into NMF and SymNMF for enhanced clustering.
• To address clustering challenges in linearly and nonlinearly separable data.

Main Methods:

• Formulated a constrained clustering framework using NMF for linearly separable data.
• Formulated a constrained clustering framework using SymNMF for nonlinearly separable data.
• Developed multiplicative update rules to solve the proposed NMF and SymNMF models, proving correctness and convergence.

Main Results:

• The proposed framework effectively enforces must-link constraints (similarity ≈ 1) and cannot-link constraints (similarity ≈ 0).
• Experimental results on text, UCI, and gene expression datasets demonstrated superior performance compared to existing constrained clustering algorithms.

Conclusions:

• The developed NMF-based constrained clustering framework offers a superior approach for data clustering when prior constraints are available.
• The algorithms are effective for both linearly and nonlinearly separable data, showing broad applicability.