Computing Formal Concepts by Attribute Sorting

Issue title: Concept Lattices and Their Applications

Article type: Research Article

Authors: Krajca, Petr | Outrata, Jan | Vychodil, Vilem

Affiliations: DAMOL: Data Analysis and Modeling Laboratory, Department of Computer Science, Palacky University, Olomouc, Czech Republic, [email protected]; [email protected]; [email protected]

Note: [] Jan Outrata was supported by grant no. P202/10/P360 of the Czech Science Foundation.

Note: [] Petr Krajca and Vilem Vychodil were supported by grant no. P103/10/1056 of the Czech Science Foundation. Address for correspondence: Department of Computer Science, Palacky University, 17. listopadu 12, CZ–77146 Olomouc, Czech Republic

Abstract: We present a novel approach to compute formal concepts of formal context. In terms of operations with Boolean matrices, the presented algorithm computes all maximal rectangles of the input Boolean matrix which are full of 1s. The algorithm combines basic ideas of previous approaches with our recent observations on the influence of attribute permutations and attribute sorting on the number of formal concepts which are computed multiple times. As a result, we present algorithm which computes formal concepts by successive context reduction and attribute sorting. We prove its soundness, discuss its complexity and efficiency, and show that it outperforms other algorithms from the CbO family in terms of substantially lower numbers of formal concepts which are computed multiple times.

DOI: 10.3233/FI-2012-661

Journal: Fundamenta Informaticae, vol. 115, no. 4, pp. 395-417, 2012