Boolean matrix factorization (BMF), a popular methodology of preprocessing and analyzing 1/0 tabular data, generally handles Os and Is differently. It aims to explain Is in the data by factors, while Os are just left unexplained. This difference is mainly given by the usual data character, where 1s carry much more important information (and are much scarcer) than Os. However, in some datasets, the Is and Os are equally important. Such datasets require symmetrical handling of Is and Os. We propose a novel factorization of such data and its algorithm. Unlike usual BMF methods, factors are linearly ordered by priority in our factorization, and factors can contradict each other – meaning that one factor can put 1 where the other puts 0. In such a case, the factor with higher priority is right. We show that the proposed factorization provides a more compact data description than a straightforward application of the usual BMF methods.

We provide a detailed analysis and a first complete description of 8M—an old but virtually unknown algorithm for Boolean matrix factorization. Even though the algorithm uses a rather limited insight into the factorization problem from today’s perspective, we demonstrate that its performance is reasonably good compared to the currently available algorithms. Our analysis reveals that this is due to certain concepts employed by 8M that are not exploited by the current algorithms. We discuss the prospect of these concepts, utilize them to improve two well-known current factorization algorithms, and, furthermore, propose an improvement of 8M itself, which significantly enhances the performance of the original 8M. Our findings are illustrated by experimental evaluation.

Finding interesting patterns is a classical problem in data mining. Boolean matrix decomposition is nowadays a standard tool that can find a set of patterns-also called factors-in Boolean data that explain the data well. We describe and experimentally evaluate a probabilistic algorithm for Boolean matrix decomposition problem. The algorithm is derived from GreCon algorithm which uses formal concepts-maximal rectangles or tiles-as factors in order to find a decomposition. We change the core of GreCon by substituting a sampling procedure for a deterministic computation of suitable formal concepts. This allows us to alleviate the greedy nature of GreCon, creates a possibility to bypass some of the its pitfalls and to preserve its features, e.g. an ability to explain the entire data.