The Fixed-Point Semantics of Relational Concept Analysis

Abstract

Background: Relational concept analysis (RCA) is an extension of formal concept analysis dealing with several related formal contexts simultaneously. It can learn description logic theories from data and has been used within various applications. However, RCA returns a single family of concept lattices, though, when the data feature circular dependencies, other solutions may be considered acceptable. The semantics of RCA, provided in an operational way, does not shed light on this issue. Objectives: This paper aims at defining precisely the semantics of RCA and identifying alternative solutions. Methods: We first characterise the acceptable solutions as those families of concept lattices which belong to the space determined by the initial contexts (well-formed), which cannot scale new attributes (saturated), and which refer only to concepts of the family (self-supported). We adopt a functional view on the RCA process by defining the space of well-formed solutions and two functions on that space: one expansive and the other contractive. In this context, the acceptable solutions are the common fixed points of both functions. Results: We show that RCA returns the least element of the set of acceptable solutions. In addition, it is possible to build dually an operation that generates its greatest element. The set of acceptable solutions is a complete sublattice of the interval between these two elements. Its structure, and how the defined functions traverse it, are studied in detail.