Formal Concept Analysis offers a simple formalization for representing knowledge structures extracted from various data. Lately, the triadic case has become increasingly popular, given that data can often be interpreted in a triadic setting for further processing and analysis. However, visualization and navigation in triadic conceptual landscapes is not trivial and, so far, there are no tools implementing navigation in triconcept sets. This paper extends a navigation paradigm based on a reachability relation of triconcepts and on appropriately de ned dyadic projections, and it offers a detailed description of different implementation methods. Moreover, we propose a visualization of the reachability clusters that gives an overview of the triconcepts' structure and can assist the local navigation.
Nowadays, understanding big collections of data can have a great impact on
advancing different scienti c elds. Formal Concept Analysis (FCA) provides a
powerful mathematical tool that addresses knowledge processing and knowledge
representation [
Previously, we have proposed two methods of navigating in triadic data. The
rst approach is based on narrowing down the space of formal concepts according
to constraints added by the user. This membership-constraint-based approach
was formally described and the theoretical aspects were studied in detail [
The second approach has a local character and is based on appropriately
de ned dyadic projections. For this purpose, we de ned the reachability relation
and studied some of its properties, as well as the properties of other resulting
structures, such as reachability clusters [
This section introduces the basic notions of triadic formal concept analysis as
well as some of the theoretical aspects of the reachability-based navigation. For
a deeper understanding of formal concept analysis we refer the reader to the
standard literature [
The fundamental structures of triadic formal concept analysis are those of a triadic formal context and a triconcept.
De nition 1. A triadic formal context, also referred to as a tricontext, is a quadruple K = (K1; K2; K3; Y ) consisting of three sets K1; K2; K3 and a ternary relation Y K1 K2 K3. The elements of K1; K2; K3 are called (formal) object, attributes and conditions. An element (g; m; b) 2 Y of the incidence relation is read object g has attribute m under condition b.
De nition 2. The triadic concepts, also called triconcepts, of a tricontext K = (K1; K2; K3; Y ) are exactly the triples (A1; A2; A3) that satisfy A1 A2 A3 Y and which are maximal w.r.t. component-wise set inclusion.
The following de nition shows how dyadic projections can be obtained from a triadic context.
De nition 3. Every triadic context (K1; K2; K3; Y ) gives rise to the following dyadic contexts:
K(1) := (K1; K2 K(2) := (K2; K1 K(3) := (K3; K1
K3; Y (1)) with gY (1)(m; b) :, (g; m; b) 2 Y , K3; Y (2)) with mY (2)(g; b) :, (g; m; b) 2 Y , and
K2; Y (3)) with bY (3)(g; m) :, (g; m; b) 2 Y .
For fi; j; kg = f1; 2; 3g and Ak (ai; aj ) 2 YA(ikj) if and only if (ai; aj ; ak) 2 Y for all ak 2 Ak.
Kk, we de ne K(Aijk) := (Ki; Kj ; YA(ikj)), where
Intuitively, the contexts K(i) represent \ attened" versions of the triadic context, obtained by putting the \slices" of (K1; K2; K3; Y ) side by side. Moreover, K(Aijk) corresponds to the intersection of all those slices that correspond to elements of Ak.
Next we introduce the notion of reachability relation and reachability cluster. De nition 4. For (A1; A2; A3) and (B1; B2; B3) triadic concepts, we say that (B1; B2; B3) is directly reachable from (A1; A2; A3) using perspective (1) and we write (A1; A2; A3) ≺1 (B1; B2; B3) if and only if (B2; B3) 2 B(K(A213)). Analogously, we can de ne direct reachability using perspectives (2) and (3).
We say that (B1; B2; B3) is directly reachable from (A1; A2; A3) if it is directly reachable using at least one of the three perspectives, that is, formally (A1; A2; A3) ≺ (B1; B2; B3) :, [(A1; A2; A3) ≺1 (B1; B2; B3)] _ [(A1; A2; A3) ≺2 (B1; B2; B3)] _ [(A1; A2; A3) ≺3 (B1; B2; B3)].
De nition 5. We de ne the reachability relation between two triconcepts as being the transitive closure of the direct reachability relation ≺. We denote this relation by ▹.
For checking whether triconcept (B1; B2; B3) is directly reachable from triconcept (A1; A2; A3), we have proposed the following algorithm.
Algorithm 1: Procedure directlyReachable((A1; A2; A3), (B1; B2; B3)) I f A1 = B1 or A2 = B2 or A3 = B3 then
I f A1
Pe = K(A213) I f A2
Pi = K(A123)
I f (B2)′Pe = B3 and (B3)′Pe = B2 then
I f (B1)′Pe = B3 and (B3)′Pe = B1 then
Pm = K(A132) I f (B1)′Pe = B2 and (B2)′Pe = B1 then
The derivations used in the description of the algorithm are the simple dyadic derivations and the index was added just to highlight that each dyadic derivation corresponds to a different dyadic context. For example, (B2)′Pe = B3 uses the dyadic derivation operator of the context Pe.
When studying the properties of the reachability relation, the notion of reachability cluster arises. Intuitively, a reachability cluster is a maximal set of mutually reachable triconcepts. Formally, a reachability cluster is de ned as follows. De nition 6. The equivalence class of a triconcept (A1; A2; A3) with respect to the preorder ▹ on T(K) will be called a reachability cluster and denoted by [(A1; A2; A3)].
Next, we consider the dyadic context of reachable triconcepts K▹.
Let K = (K1; K2; K3; Y ) be a triadic context. Then we denote with K▹ = (T(K); T(K); ▹) the formal context of triconcepts with the reachability relation.
While analyzing the correlation between reachability clusters and the dyadic concepts (M; N ) 2 B(K▹) of the reachability context, we have shown that there is a one-to-one relation between the clusters and the non-empty intersections of the extent and intent from the dyadic concepts M \ N . These results give rise to a display method of all reachability clusters that can support the navigation among triconcepts, as detailed in the next sections. 3
Considering the theoretical aspects highlighted in Section 2 and described in
more detail in our previous paper ([
One problem that has not been solved yet in an efficient manner is how to
choose a starting point. Currently, for this purpose, we use a preprocessing step
that computes all triconcepts, for example using Trias [
(jk) { generate the concept lattice of KAi { attach as labels to the dyadic concepts in the lattice the corresponding triconcepts by adding the third component { choose one of the triconcepts that are represented by the nodes in the dyadic lattice as a next step
(jk), one must select from the triadic relation
For computing the derived context KAi
the pairs of elements (aj; ak) 2 Aj Ak which are in relation with all elements
from Ai, i.e. (ai; aj; ak) 2 Y; 8ai 2 Ai, assuming, without loss of generality, that
i < j < k. Afterwards, the third step consists of generating the concept lattice
of the derived context. This can be done using one of the existing FCA tools [
The previously described navigation and visualization paradigm has a local
character which is an advantage when considering large contexts. However, one
disadvantage of the navigation is that not every triconcept can be reached from
every other triconcept, although this seems to be the case in most practical
scenarios [
For implementing the rst step, we can use Algorithm 1 that outputs whether
a triconcept is directly reachable from another triconcept. For the second step,
the transitive closure of the direct reachability relation ≺ must be computed in
order to obtain the reachability relation ▹. This can be done by using one of
the existing algorithms that compute the transitive closure of a relation, such as
Warshall algorithm ([
After obtaining that, the reachability context K▹ can be formed and we can compute the clusters and the partial order on the cluster set, using the concept lattice of K▹. We have shown that each reachability cluster is uniquely identi ed by the intersection of extent and intent of exactly one dyadic concept of K▹. Hence, we can compute the concept lattice of K▹ and label each node with the intersection of extent and intent, i.e. the corresponding cluster, and no label when the intersection is empty. In the obtained lattice one can visualize the partial order between the clusters. An example illustrating the described procedure for obtaining the cluster structure is presented in Section 4.
Alternatively, we can make use of the directed graph having the triconcepts as vertices and the edges given by the direct reachability relation. Here, we can identify the reachability clusters, as well as deduce the transitive closure of the direct reachability relation as described in Proposition 1.
Proposition 1. Let K be a tricontext and G the graph with T(K) as vertices and the edges given by the direct reachability relation. Then, the reachability clusters of K are identi ed by the strongly connected components of G. Furthermore, for triconcepts T1; T2 2 T(K), we have that T1 ▹ T2 if, in graph G, there is a directed path from T1 to T2.
Furthermore, the same graph G can be used to deduce the partial order relation between the clusters as described in Proposition 2.
Proposition 2. Let K be a tricontext and G the graph with T(K) as vertices and the edges given by the direct reachability relation. If T1 2 C1 and T2 2 C2 are two triconcepts from different clusters s.t. in G there is a path from T1 to T2, then we have that C1 C2. Observe that, considering T1 and T2 belong to different clusters, in the case that there is a path from T1 to T2, we cannot have a path from T2 to T1.
However, a disadvantage of the graph-based approach is that it does not output the lattice representation of the clusters, hence an FCA tool has to be used if we want to obtain a visualization of the cluster structure.
An important aspect to keep in mind during the navigation is that not every triconcept is reachable from any other triconcept. In fact, when navigating from a triconcept to another belonging to a different cluster, one cannot navigate back by using the standard navigation method described. For this purpose, we propose the use of a navigation history, allowing the user to go back to a certain triconcept in the previous navigation path.
In conclusion, to support exploration through the dataset, we suggest using both the local visualization method for triconcepts and the visualization of the cluster structure as follows. We compute the lattice showing the cluster structure at the beginning of the navigation and make it available to the user throughout the whole exploration process. Then, at each step of the navigation, when visualizing the concept lattice of the possible next steps, i.e. the directly reachable triconcepts, we highlight all the triconcepts belonging to the same cluster as the current triconcept. In that way, the user can easily choose to navigate within the same cluster or to a different one. Furthermore, looking at the cluster structure in parallel, the user can navigate more easily towards a potential goal of the navigation. 4
In practice, experiments that we ran on real datasets showed that tricontexts had one single reachability cluster comprising all triconcepts. This leads us to believe, that, in general, real datasets have a high correlation in the data and therefore, all triconcepts are contained in the same reachability cluster. However, theoretically it is possible that a tricontext comprises several reachability cluster. In this section, we present a small example of an arti cial context containing more than two reachability clusters and exemplify how the structure of the reachability clusters can be obtained.
Let us consider the following triadic context K = (G; M; B; Y ), with the object set G = fg1; g2; g3g, the attribute set M = fm1; m2; m3g and the condition set B = fb1; b2; b3g.
Moreover, when computing the concept lattice of K▹, we obtain a representation of the reachability clusters as depicted in Figure 2. In this lattice, the bottom node corresponds to cluster C1, the node in the middle corresponds to cluster C2 and the upper node corresponds to cluster C3. The partial order between the clusters can be read from the lattice the following way: if one can navigate from cluster C1 to cluster C2 going upwards, then C1 C2, so we have that C1 C2 C3.
During the navigation, taking this cluster structure into consideration, one can deduce, for example, that starting from triconcept T4 you can never reach any of the triconcepts T1, T2 or T3. Hence, the structure of the clusters can be of use also when choosing a starting point for the navigation.
K▹ T1 T2 T3 T4 T5 T6
T1
T2
T3
T4
T5
T6
In this paper, we have extended a navigation paradigm for triadic datasets that
helps the user to get an overview of the data and to understand its underlying
structure. To this end we described the steps of the navigation among triconcepts
based on local dyadic projections and we have shown how the structure of the
reachability clusters can be obtained using different methods. Furthermore, we
have highlighted the fact that the local navigation paradigm can bene t from the
lattice representation of the clusters' structure by offering the user an overview
of the underlying data structure. The described navigation paradigm was
implemented in a tool suite called FCA Tools Bundle that is described in more detail
in an additional paper [
In our future work, we plan to combine the reachability-based navigation with the membership-constraint-based navigation into a new improved paradigm in order to solve the problem of choosing a starting point. The reachability-based navigation can offer the visualization support, while the constraints added by the user can be taken into consideration by highlighting the concepts in the local visualization that satisfy the constraints.