Formal Concepts as Optimal Factors in Boolean Factor Analysis: Implications and Experiments.
Radim Bělohlávek, Vilém Vychodil · 2007
Abstract. Boolean factor analysis aims at decomposing an objects × attributes Boolean matrix I into a Boolean product of an objects × factors Boolean matrix A and a factors × attributes Boolean matrix B, with the number of factors as small as possible. This paper is a continuation of our previous paper where we proved that formal concepts of I are optimal factors for Boolean factor analysis. In particular, we concentrate on the implications of the proof. Namely, on the fact that finding factors can be reduced to the set covering problem for which there exist efficient approximation algorithms. In this paper, we present the algorithm for finding factors which results this way and present several experiments on factorizing Boolean matrices. 1 Introduction and problem setting The present paper concerns factor analysis of Boolean data and is a continuation of [4]. In [4], we proved that formal concepts are optimal factors in Boolean factor analysis and outlined some implications of the insight provided by the proof. The