From-below approximations in Boolean matrix factorization: geometry and new algorithm

DOI10.1016/J.JCSS.2015.06.002zbMATH Open1328.68295arXiv1306.4905OpenAlexW1497640967WikidataQ113643210 ScholiaQ113643210MaRDI QIDQ494072FDOQ494072

Radim Belohlavek, Martin Trnecka

Publication date: 31 August 2015

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Abstract: We present new results on Boolean matrix factorization and a new algorithm based on these results. The results emphasize the significance of factorizations that provide from-below approximations of the input matrix. While the previously proposed algorithms do not consider the possibly different significance of different matrix entries, our results help measure such significance and suggest where to focus when computing factors. An experimental evaluation of the new algorithm on both synthetic and real data demonstrates its good performance in terms of good coverage by the first k factors as well as a small number of factors needed for exact decomposition and indicates that the algorithm outperforms the available ones in these terms. We also propose future research topics.

Full work available at URL: https://arxiv.org/abs/1306.4905

Recommendations

• An incremental recomputation of from-below Boolean matrix factorization
• From-below Boolean matrix factorization algorithm based on MDL
• A new algorithm for Boolean matrix factorization which admits overcovering
• Toward quality assessment of Boolean matrix factorizations
• Lower bounds for matrix factorization
• Lower bounds for matrix factorization
• scientific article; zbMATH DE number 1979525
• Parallelization of the GreConD algorithm for Boolean matrix factorization

zbMATH Keywords

approximation algorithmconcept latticematrix decompositionBoolean matrixclosure structures

Mathematics Subject Classification ID

Factor analysis and principal components; correspondence analysis (62H25) Factorization of matrices (15A23) Knowledge representation (68T30) Boolean and Hadamard matrices (15B34) Approximation algorithms (68W25)

Cites Work

• A mathematical analysis of human leukocyte antigen serology
• Discovery of optimal factors in binary data via a novel method of matrix decomposition
• Optimal factorization of three-way binary data using triadic concepts
• Title not available (Why is that?)
• Title not available (Why is that?)
• Comparing performance of algorithms for generating concept lattices
• Discovery Science
• Combinatorial matrix theory
• Title not available (Why is that?)
• Ordinal Factor Analysis
• Title not available (Why is that?)
• Optimal decompositions of matrices with entries from residuated lattices
• Title not available (Why is that?)
• Summarizing transactional databases with overlapped hyperrectangles
• Knowledge Discovery in Inductive Databases

Cited In (15)

• A new algorithm for Boolean matrix factorization which admits overcovering
• From-below Boolean matrix factorization algorithm based on MDL
• An incremental recomputation of from-below Boolean matrix factorization
• Toward quality assessment of Boolean matrix factorizations
• Generalized inverses of Boolean tensors via the Einstein product
• Factorizing Boolean matrices using formal concepts and iterative usage of essential entries
• Semantic explorations in factorizing Boolean data via formal concepts
• A knowledge reduction approach for linguistic concept formal context
• Handling noise in Boolean matrix factorization
• Factorization of matrices with grades via essential entries
• FCA2VEC: Embedding Techniques for Formal Concept Analysis
• Impact of Boolean factorization as preprocessing methods for classification of Boolean data
• On stability of fuzzy formal concepts over randomized one-sided formal context
• Factorizing formal contexts from closures of necessity operators
• \textsc{QualityCover}: efficient binary relation coverage guided by induced knowledge quality

Uses Software

• UCI-ml

This page was built for publication: From-below approximations in Boolean matrix factorization: geometry and new algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q494072)