Using fringes for minimal conceptual decomposition of binary contexts

Abstract

Extracting knowledge from huge data in a reasonable time is still a challenging problem. Most real data (structured or not) can be mapped to an equivalent binary context, with or without using a scaling method, as for extracting associations between words in a text, or in machine learning systems. In this paper, our objective is to find a minimal coverage of a relation R with formal concepts. The problem is known to be NP-complete. 1 In this paper, we exploit a particular difunctional relation embedded in any binary relation R, the fringe of R, to find an approximate conceptual coverage of R. We use formal properties of fringes to find better algorithms calculating the minimal rectangular coverage of binary relation. Here, a formal context is considered as a binary relation. By exploiting some background on relational algebra in the present work, we merge some results of Belohlavek and Vichodyl, 2 using formal concept analysis with previous results obtained by Kcherif et al. 3 using relational algebra. We finally propose decomposition algorithms based on the relational formalization and fringe relations.