Relational Concept Analysis [4] is an extension to FCA considering several contexts with relations between them. Often used to extend the knowledge that can be learned with FCA, RCA also meets the issue of combinatorial explosion. The initial specification of RCA implies a monotonic growth of the number of concepts and an exhaustiveness of all the concepts that can be obtained when a fixed point is reached. In this position paper we propose a different specification of RCA that permits an interactive exploration of the data by letting the choice of the user for each step. This change will permit to handle richer relational data in a more flexible way by restraining the relations explored at each step hence reducing the number of created concepts.
Relational Concept Analysis (RCA) [
The context of this research is the FRESQUEAU project4 which aims at developing new methods for studying, comparing and exploiting all the parameters available concerning streams and water areas. In this project, different ? This work was partly funded by french contract ANR11_MONU14. 4 http://engees-fresqueau.unistra.fr/ approaches of knowledge discovery (including FCA) are tested and combined in order to better assess the ecological functioning of such hydrosystems.
In this paper we first outline the RCA process to highlight potential variation points that would promote exploration. Then we conclude with a short discussion. 2
Algorithm 1 outlines the main steps followed by RCA to build groups of objects
by considering attributes and object-object relations [
Algorithm 1: The RCA process
For Rj Oi Oj , we call Oi the domain and Oj the range. The initialization step (Lines 4-5) consists in building, for all i in 1::n, the lattice L0[i] associated with the context Ki.
At step p: – Extend-Rel appends to Ki the relations obtained by scaling object-object relations for which Ki is the domain. The scaling consists in including the object-object relations as relational attributes. They are obtained using the concepts of the lattices of step p 1 and a scaling operator (i.e. 9, 8). For example, if the scaling operator 9 is chosen for scaling a given relation Rj , Rj columns are replaced by attributes of the form 9Rj : C, where C is a concept in the lattice built upon objects of the range of Rj at step p 1. An object o of the domain of Rj owns 9Rj : C if Rj (o) \ Extent(C) 6= ;. – Update–Lattice updates the lattices of step p 1 in order to produce, for i in 1::n, the lattice Lp[i], associated with Ki concatenated to all scaled object-object contexts with Ki domain.
The algorithm stops when a fix-point is obtained: a lattice family isomorphic to the lattice family obtained at the previous step is obtained and leaves unchanged concept extents.
The advantage of such a process is that the obtained concepts have in their
intent relations to other concepts in addition to classical attributes. Those
relations permit the extraction of patterns built from several interconnected concepts
as shown in [
However, one problem of such a process is the potential difficulty to apprehend the result. In past work in the domain of Model Driven Engineering, data extracted from models of medium size have been easily handled by RCA. Nevertheless in a context of data mining the data are of a different scale. Especially when only small patterns are needed while many relations connect the objects and these relations form a cyclic entity-relationship diagram, the result will appear hard to understand by a human due to the number of concepts to consider simultaneously and the computation time will be considered as a handicap. In such cases, we think it will be more practical to have a kind-of exploratory approach.
Table 1 shows main possible variations on the algorithm to go towards an exploratory approach. We have enumerated the variation points of the algorithm that could affect the result by changing the contexts considered at each step. We have proposed for each variation point an alternative scenario from the process previously described that involves the user by asking him or her to perform selections. All those variations or only a subset of them can be applied depending on the granularity needed.
In this position paper, we have outlined an exploratory approach for assisting the
use of Relational Concept Analysis in a way that would better fit a data mining
process. We have several motivations for disturbing the original RCA process:
to go faster to a relevant result by calculating less lattices (preferably lattices of
interest), to cope with the inherent complexity of mining relational data, or to
let the expert guiding the discovery process based on his/her intuition and the
knowledge patterns that appear on-the-fly. In our current approach, the data are
given by experts, so we don’t use exploration in the sense of [
Many questions are raised by this way of extracting concepts from relational data. Initialization of the process has an impact for the later discovered structures. It can accelerate the process, if the selected object-object relations contain the main information for the expert, or reversely, it can discard the expert from the relevant information. Nevertheless, the most serious problem comes from the fact that going step-by-step leads to a non-monotonic concept construction and one could build several cases where the process diverges (iterates between recurrent configurations). In the original RCA process, when the fix-point is attained, lattices of the two last steps are isomorphic, thus when a concept references another through a relational attribute, the latter can be found in the same step appropriate lattice. But in the exploratory process we propose, when a concept references another through a relational attribute, the latter is in a lattice of a previous step and may itself reference a concept in a previous step, etc. We should find solutions for presenting the expert information easy to interpret these situations. Nevertheless, we think that such an exploratory approach should be more practical than the "brute force" that iterates until the fix-point and gives results that an expert will hardly understand.