Relational Concept Analysis (RCA) has been introduced in order to allow concept analysis on multi-relational data. It significantly widens the field of application of Formal Concept Analysis (FCA), and it produces richer concept intents that are similar to concept definitions in Description Logics (DL). However, reading and interpreting RCA concept lattices is notoriously difficult. Nica et al have proposed to represent RCA intents by cpo-patterns in the special case of sequence structures. We propose an equivalent representation of a family of RCA concept lattices in the form of a hierarchy of concept graphs. Each concept belongs to one concept graph, and each concept graph exhibits the relationships between several concepts. A concept graph is generally transversal to several lattices, and therefore highlights the relationships between different types of objects. We show the benefits of our approach on several use cases from the RCA litterature.
Many domains produce multi-relational data. For example, in the health domain,
one can have patients taking drugs, drugs giving some symptoms and
interacting with other drugs, doctors taking care of patients and prescribing drugs to
patients, etc. In order to extract knowledge from that kind of data, many data
mining techniques, such as Formal Concept Analysis (FCA) [
An important issue for the effective use of RCA is the interpretation of its
outputs. Indeed, RCA produces not one but several concept lattices, and the
intent of each concept may depend on the intent of other relationally-related
concepts, recursively. To the best of our knowledge, there has been only one
proposal to automatically extract and graphically represent the relational patterns
that are buried into concept intents: Nica’s cpo-patterns [
In this paper, we propose a novel and generic graphical representation of RCA outputs that emphasizes the relational patterns. We call it hierarchy of concept graphs. It has the following good properties. First, it makes no assumption on the context family, and can therefore handle all kinds of graph structures, not only sequences. Second, it is at the same time a complete and non-redundant representation of the family of concept lattices, and does not require to choose one concept lattice as starting point. Third, it offers a better balance in the display between generalization ordering (lattice edges), and relationships (relational attributes). Fourth, it clusters concepts into concept graphs, and hence produce a coarser-grained representation. Fifth, it can be efficiently computed from the concept lattices, in linear time.
Section 2 discusses related work. Section 3 shortly recalls the main definitions of RCA. Section 4 introduces our representation of RCA outputs as a hierarchy of concept graphs, illustrates it on a reference example of RCA, and discusses its properties. Section 5 evaluates our approach on a few use cases, and discusses the impact of representation choices. Section 6 concludes and draws perspectives. 2
Several generalizations of FCA have been proposed to handle relational data.
Power Context Families [
The above shows that there are two kinds of representations of the results:
concept lattices and concept graphs. They complement each other: concept
lattices emphasizes the generalization ordering between concepts, while concept
graphs emphasize the relationship patterns between objects in data. In RCA,
the native representation is made of concept lattices, and the relationship
patterns are only indirectly accessible through relational attributes. Recently, Nica
et al [
Relational Concept Analysis (RCA)
We here recall the definitions of context family and lattice family in RCA. We
therefore focus on the input and output of RCA, and we ignore the methodology
and algorithms that are used to compute the concept lattices from the context
family. Indeed we are here concerned with the graphical representation of RCA
lattices rather than on their computation. A detailed presentation of RCA is
available in previous papers, in particular [
As a running example, we reuse the RCF defined in [
Given an RCF, the output of RCA is a collection of concept lattices, one
for each context of the RCF. The relations of the RCF are taken into account
by repeatedly applying a mechanism of relational scaling on each context and
its concept lattice, until convergence is reached. This leads to the introduction
of relational attributes that express relational constraints, and contribute to the
formation of concepts (see [
p4 takes:d12 p2
takes:d9 p3 takes:d13
takes:d10 p6 takes:d14
p7 Fatigue takes:d3 takes:d6
takes:d16 p8 takes:d18
p0 Senior p11
p1 takes:d2 p14 takes:d21
takes:d0 p10 takes:d15
p9 Nausea Definition 2. Let (K , R) be a RCF. The Relational Concept Lattice Family (RCLF) is a set of concept lattices L = {Li}i=1..n, one for each context Ki. Each concept ci in Li is a pair (X, Y ) where: – X ⊆ Oi is the extent of the concept, and – Y is the intent of the concept, and contains attributes in Ai and relational attributes in the form ρ r : cj where ρ ∈ {∃, ∀∃, ...} is a scaling operator, r ∈ R, dom(r) = Oi, ran(r) = Oj , and cj ∈ Lj .
In this paper, we only consider existential scaling (ρ = ∃) even though our approach is applicable to other scaling operators. Figure 1 shows the concept lattice Lp of patients, and Figure 2 the concept lattice Ld of drugs. Both are represented with reduced labelling, i.e. each object/attribute appears only once. Object labels are placed below the concept, while attribute labels are placed above and on the right of the concept. Each relational attribute ∃r : cj is displayed as r : cj .
The reading and interpretation of RCA lattices is notoriously difficult. The main reason is probably that reading the intent of a concept requires not only to traverse the lattice upward, as in FCA, but also to follow relationships to other concepts through the relational attributes. For example, concept p7 groups the adult patients who have fatigue, and take a drug in concept d10 and a drug in concept d14. Concept d10 groups the drugs for which diarrhea is expected, and d14 Fatigue
d19 itb:p8 itb:p10 d20
itb:p3 d17 iw:d3
d18
d15 HairLoss
d3 iw:d9
d0
d13 iw:d6
d9 Maraviroc
d1 which are taken by patients in concept p7. Loops in the exploration of the intent, like in that example, lead to circular definitions of concepts, and contribute to the difficulty of interpretation. 4
Hierarchies of Concept Graphs
Our objective is to facilitate the reading of the intent of RCA concepts, in order
to facilitate their interpretation. The first idea is to display the different lattices
side-by-side, and to materialize each relational attribute r : c2 on a concept c1 as
r
a relational edge, i.e. a labeled and directed edge c1 −→ c2. However, the
graphical representation becomes denser and even less readable; and its structure is
dominated by the lattice structures at the cost of elongated relational edges. A
better balance between lattice edges and relational edges is desirable. The second
idea is to identify relational structures as subsets of interrelated concepts from
different lattices, and to use them as building blocks in the graphical
representation. We propose to define those relational structures as the Strongly Connected
Components (SCC) [
Definition 4. Let L be a RCLF. The dependency graph of L is the directed graph GL = (V, E) where: – V is the set of all concepts of all lattices in L except bottom concepts, – and E = {(c1, c2) | c1, c2 ∈ V and c1 → c2}.
SCCs as Concept Graphs. From there, a SCC of GL is a maximal set of concepts (possibly from several lattices) where each concept has a dependency path to all other concepts in the SCC for the definition of its intent. SCCs are used to define concept graphs, which are the building blocks of our graphical representation. Definition 5. A concept graph is the subgraph of the lattice family (enriched with relational edges) that is induced by a SCC of GL . It therefore mixes concepts from several lattices, and both lattice edges and relational edges.
In Figure 3, each rounded box contains a concept graph (G1-G6). Nodes are concepts from the two RCA lattices in Figures 1 and 2 (same id, same labels). Relational edges (arrows) replace the relational attributes to graphically represent the relational dependencies. Lattice edges that cross concept graph boundaries are displayed as dotted lines to keep the graph light, and to emphasize the concept graphs over the global lattice structures. It is notable in this example that no relational edge crosses concept graph boundaries. This is because in the context family each relation either has an inverse relation (e.g., takes and itb) or is a symmetric relation (e.g., iw ).
Furthermore, it is known that the SCCs of a graph form a directed acyclic graph, where SCC1 → SCC2 if any concept in SCC1 depends on any concept in SCC2. The concept graphs of a RCLF can therefore be organized into a hierarchy of concept graphs. For example, concept graph G2 is a child of concept graph G1 in Figure 3 because several concepts in G2 have lattice edges (dotted lines) to concepts in G1: e.g., from p4 to p6, or from d12 to d14. Those hierarchical relationships can be seen as a complex version of the lattice edges, combining several lattice edges across different lattices.
Interpretation. We here give a short interpretation of the hierarchy of concept graphs in Figure 3. G1 represents the most general pattern between patients and drugs. It shows that all patients take drugs expected to give fatigue and diarrhea, and that all drugs are taken by an adult with fatigue. G2-4 are specializations of G1. For example, G4 specializes G1 to patients with bleeding. G2 specializes G1 to patients with hairloss and oedema, which all take drugs giving vomiting and rash, which are taken by a patient with hives, and by a female patient. G5 and G6 represent patterns that are specific to individual patients and drugs, 6 p 8 1 d 4 1 p R 8
d h s a g n i t i m 1 o 1 V d s s a o m irL ed a e H O 4 p 2
5 G
G le H N e l a m e f 5 p s e v 2 i p H
r 6 e s d n so r i G o c L 0 2 e t d r c d is y ir m D ma o h o H in ta in 5 t 1 c
a B A n i c y
D r i s v s a e r 0 r g d t e n lt e re a Is d R r o s i g thD iitn
y a e m 0 d r o 1 u B V p r
T 7 1 lu c d i o a r e r tF iv r a 9 iw ea ra d
H M e g a D r e v i L am iw 5 d 3 1 p
e 3 n p a
L z n e r i v a f E a v 3 i
t 1 s d u
S y r t n e z l e S a r t e l a
K ir iw iw v a n o f i 3 R d r i v o d a fo d6 r
e n i e V T
a 1 n 1 a p h
S y e 0 l e p r h a
F acd iro a n e e H S and are therefore less interesting from a data-mining perspective. G5 shows that some patients (p13) take drugs (d6 and d3) that cause liver dammage (d5) and are in interaction with drug Sustiva (d13) which is taken by patient Lane (p3). Discussion. The hierarchy of concept graphs has a number of good theoretical properties. First, it is a complete representation because it keeps all concepts and edges from the concept lattices. It is also parcimonious in that it does not duplicate any concept, edge, or label. Second, it is more readable because it displays relation attributes as relation edges, and because its layout offers a better balance between lattice edges and relational edges. Moreover, when the many concepts are clustered in a small number of concept graphs, the RCLF can be read at a higher level of granularity. Third, it is efficient to compute because the SCCs can be extracted in time linear with the size of GL , and hence in the cumulated size of lattices in L. 5
In this section we present two use cases in order to compare graph concepts with
results of Graph-FCA and cpo-patterns from [
Royal Family: Genealogical Data
G1 p0 G2 male p1
G3 female p3 G4 p10 child
parent p6 p8 p9
p4
G5
The first use case is the one used for Graph-FCA [
Comparing those results to Graph-FCA, it is interesting to note that the graph patterns of Graph-FCA are equivalent to the RCA concept graphs, up to a few representation changes. Graph-FCA patterns only represent relational edges, not lattice edges. The generalization ordering between concepts and patterns is therefore not explicitly represented. In Graph-FCA the use of inverse relations is implicit so that the child relation is redundant with the parent relation. Note that Graph-FCA also defines n-ary concepts such as “couple” or “sibling”. The equivalence with Graph-FCA on this example must not be generalized. In fact, it does not hold on the running example about patients and drugs. 5.2
Medical Histories and Comparison to cpo-Patterns
The second use case is the one used for cpo-Patterns [
Figure 5 shows the hierarchy of concept graphs obtained from those lattices with our approach. We note that it is a special case, indeed each concept is a COUGHhigh 4
FEVERhigh
6 14 10 24 23
?moderate COUGHmoderate 2
15 17 16 9 8 13 19
29 21 5 12 concept graph by its own. It is due to the fact that the relation ”is-precededby” has no inverse relation, and forms no cycle because of its sequential nature. It is thus impossible to find more than one concept in a strongly connected component. The greyed concepts are the concepts from the viral test lattice, other concepts come from the medical examination lattice. In the graph only concepts with support greater than one are shown. We can read in the hierarchy that all viral tests (top concept 0) are preceded by a medical examination (top concept 1). That relational pattern has two specialisations. The first one where the symptom during the examination is moderate cough (concepts 2 and 8). The second one where there is a high symptom (concepts 7 and 14). We can also note that parts of sequential patterns are shared by several concepts. For instance, concept 24 and 10 are preceded by a medical examination with high cough (concept 4). In fact, concept 9 specializes concept 10 by inserting between the viral test and the high cough (concept 4) two additional medical examinations (concepts 21 and 23), which are themselves specialisations of concept 24. It highlights the overlaps between sequential patterns.
We have also conducted experiments when considering the inverse relation of ”is-preceded-by” (ipb), i.e. ”is-followed-by” (ifb). The power context family is thus extended with two relations: RME-ifb-ME and RME-ifb-VT. RCA still produces two lattices but the hierarchy of concept graphs is different. Indeed, eleven concept graphs are extracted. Each of them contains several concepts and only one viral test concept. Figure 6 shows an excerpt of the hierarchy of concept graphs with those inverse relations. For the sake of readability and compactness, we modified the representation of concept graphs in two ways: (a) only the most ipb ifb G4 specific concepts of a concept graph are kept, and (b) the full intent of those concepts is shown, instead of the reduced intent, so that each concept graph can be read in isolation. Eight concept graphs among the eleven are shown and only two of them (G4 and G5) are detailled in the figure. Concept graph G4 can be read as ”a viral test (concept 13) preceded by a medical examination with moderate cough (concept 15) and a medical examination with high fever (concept 16) and both of them are preceded by a medical examination with a high symptom (concept 31)”.
The interesting result is that the eleven concept graphs match exactly the
eleven cpo-patterns extracted by [
Conclusion and Perspectives We have proposed a novel and general representation of RCA concept lattices, called hierarchy of concept graphs, in order to facilitate their interpretation. The key idea is to exhibit relational patterns by having a better balance in the display between lattice edges and relational edges. Each concept graph clusters a set of concepts (from different lattices) whose intents are mutually dependent, and exhibits a relational pattern. Concept graphs are organized into a hierarchy so that generalization ordering between concepts is lifted to concept graphs. As future work, we plan to study the impact of relation properties (e.g., inverse, transitivity) on the trade-off between the number of concept graphs and the size of each concept graph. It will also be necessary to develop tools for the dynamic visualization of large hierarchies of concept graphs, `a la Conexp1. 1 http://conexp.sourceforge.net/