=Paper=
{{Paper
|id=Vol-1703/paper5
|storemode=property
|title=A Reachability-based Navigation Paradigm for Triadic Concepts
|pdfUrl=https://ceur-ws.org/Vol-1703/paper5.pdf
|volume=Vol-1703
|authors=Diana Troanca
|dblpUrl=https://dblp.org/rec/conf/ecai/Troanca16
}}
==A Reachability-based Navigation Paradigm for Triadic Concepts ==
https://ceur-ws.org/Vol-1703/paper5.pdf
A Reachability-based Navigation Paradigm for
Triadic Concepts
Diana Troancă
Babeş-Bolyai University Cluj Napoca
dianat@cs.ubbcluj.ro
Abstract. 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 of-
ten 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 defined dyadic
projections, and it offers a detailed description of different implementa-
tion methods. Moreover, we propose a visualization of the reachability
clusters that gives an overview of the triconcepts’ structure and can assist
the local navigation.
1 Introduction
Nowadays, understanding big collections of data can have a great impact on
advancing different scientific fields. Formal Concept Analysis (FCA) provides a
powerful mathematical tool that addresses knowledge processing and knowledge
representation [3]. The main advantage of FCA is the intuitive visualization and
navigation methods offered by concept lattices. FCA was extended to the triadic
case by Lehman and Wille in 1995 [6]. Since then, different theoretical aspects
were studied and extended from the dyadic to the triadic case, and trilattices
were proposed as a visualization method. However, this type of representation
does not support an intuitive navigation method. Moreover, for slightly larger
triadic data sets, the complexity of the representation makes any navigation
attempt useless. Therefore, the problem of visualization and navigation in triadic
conceptual spaces needs to be further analyzed and new approaches have to be
found.
Previously, we have proposed two methods of navigating in triadic data. The
first 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 [7].
Moreover, the navigation paradigm was implemented, tested and evaluated [1,
9]. This approach, however, generates lists of elements, hence the users cannot
visualize the underlying structure of the triconcept set.
The second approach has a local character and is based on appropriately
defined dyadic projections. For this purpose, we defined the reachability relation
and studied some of its properties, as well as the properties of other resulting
structures, such as reachability clusters [8]. In our previous paper, we analyzed
the theoretical aspects of the described paradigm and shortly sketched a navi-
gation strategy without going into details about the implementation methods.
This paper aims to extend the navigation paradigm and to offer a comprehen-
sive description of strategy behind. Moreover, we show how the structure of the
reachability clusters can be used for supporting the local navigation paradigm.
2 Preliminaries
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 [3, 6], while a more detailed discussion on the properties of
the reachability relation can be found in our previous paper [8].
The fundamental structures of triadic formal concept analysis are those of a
triadic formal context and a triconcept.
Definition 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) ∈ Y of the incidence
relation is read object g has attribute m under condition b.
Definition 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 definition shows how dyadic projections can be obtained from
a triadic context.
Definition 3. Every triadic context (K1 , K2 , K3 , Y ) gives rise to the following
dyadic contexts:
K(1) := (K1 , K2 × K3 , Y (1) ) with gY (1) (m, b) :⇔ (g, m, b) ∈ Y ,
K(2) := (K2 , K1 × K3 , Y (2) ) with mY (2) (g, b) :⇔ (g, m, b) ∈ Y , and
K(3) := (K3 , K1 × K2 , Y (3) ) with bY (3) (g, m) :⇔ (g, m, b) ∈ Y .
(ij) (ij)
For {i, j, k} = {1, 2, 3} and Ak ⊆ Kk , we define KAk := (Ki , Kj , YAk ), where
(ij)
(ai , aj ) ∈ YAk if and only if (ai , aj , ak ) ∈ Y for all ak ∈ Ak .
Intuitively, the contexts K(i) represent “flattened” versions of the triadic con-
text, obtained by putting the “slices” of (K1 , K2 , K3 , Y ) side by side. Moreover,
(ij)
KAk corresponds to the intersection of all those slices that correspond to ele-
ments of Ak .
Next we introduce the notion of reachability relation and reachability cluster.
Definition 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
(23)
we write (A1 , A2 , A3 ) ≺1 (B1 , B2 , B3 ) if and only if (B2 , B3 ) ∈ B(KA1 ). Anal-
ogously, we can define direct reachability using perspectives (2) and (3).
We say that (B1 , B2 , B3 ) is directly reachable from (A1 , A2 , A3 ) if it is di-
rectly 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 )].
Definition 5. We define 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 tri-
concept (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
Return true
I f A1 ⊂ B1 then
(23)
Pe = KA1
I f (B2 )′Pe = B3 and (B3 )′Pe = B2 then
Return true
I f A2 ⊂ B2 then
(13)
Pi = KA2
I f (B1 )′Pe = B3 and (B3 )′Pe = B1 then
Return true
I f A3 ⊂ B3 then
(12)
Pm = KA3
I f (B1 )′Pe = B2 and (B2 )′Pe = B1 then
Return true
Return f a l s e
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 reach-
ability cluster arises. Intuitively, a reachability cluster is a maximal set of mutu-
ally reachable triconcepts. Formally, a reachability cluster is defined as follows.
Definition 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▹ .
Definition 7.
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 ) ∈ 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 Navigation Strategy
Considering the theoretical aspects highlighted in Section 2 and described in
more detail in our previous paper ([8]), we propose a strategy for navigating
among triconcepts inside a reachability cluster as well as between clusters. In
addition, as guidance during the navigation, we suggest the use of the cluster
structure that shows an overview of the reachable triconcepts. Intuitively, a step
of the navigation paradigm consists of moving from one triconcept to another
directly reachable triconcept. Hence, by following a navigation path of several
steps one can explore the triadic conceptual knowledge landscape.
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 [4]. Once we have the
triconcept set, one can choose a triconcept as a starting point and navigate by
choosing one perspective, i.e. one of the three dimensions. However, we high-
light the fact that this preprocessing step is not necessary for the rest of the
navigation and, if a starting point is chosen using a different method, this time
consuming step can be eliminated. The local navigation paradigm is described
by the following steps:
– choose a triconcept T = (A1 , A2 , A3 ) and a perspective (i) with i ∈ {1, 2, 3}
(jk)
– compute the derived context KAi of the triadic relation with j, k ∈ {1, 2, 3}\
{i} s.t. j < k
(jk)
– generate the concept lattice of KAi
– attach as labels to the dyadic concepts in the lattice the corresponding tri-
concepts 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)
For computing the derived context KAi , one must select from the triadic relation
the pairs of elements (aj , ak ) ∈ Aj × Ak which are in relation with all elements
from Ai , i.e. (ai , aj , ak ) ∈ Y, ∀ai ∈ 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 [2].
(jk)
In the next step, for a dyadic concept (Bj , Bk ) of the derived context KAi we
must identify the corresponding triconcept (Bi , Bj , Bk ) ∈ T(K). Theoretically,
this can be done by using the corresponding derivation operator to compute
the third component of a triconcept. However, considering that we have already
computed all triconcepts, it is more efficient to select the triconcept having
the two components Bj and Bk (which will be unique given the maximality
condition) from the triconcept set.
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 [8]. Therefore, we believe that it is useful to have an overall view of the
navigation clusters’ structure in order to understand whereto one can navigate.
With that purpose, we obtain the lattice structure of the reachability context
K▹ = (T(K), T(K), ▹) as follows:
– compute the direct reachability relation between triconcepts
– compute the transitive closure of the direct reachability relation
– represent the concept lattice of clusters
For implementing the first 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 ([11]), Warren algorithm ([10]), etc.
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 identified
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 identified by the strongly connected components of G. Furthermore, for
triconcepts T1 , T2 ∈ 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 ∈ C1 and T2 ∈ 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 visu-
alizing 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 Example
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 artificial 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 ob-
ject set G = {g1 , g2 , g3 }, the attribute set M = {m1 , m2 , m3 } and the condition
set B = {b1 , b2 , b3 }.
b1 m1 m2 m3 b2 m1 m2 m3 b3 m1 m2 m3
g1 × g1 g1 × ×
g2 g2 g2
g3 g3 × g3
The triconcepts of this context are the following:
T1 = ({g3 }, {m2 }, {b2 })
T2 = ({g1 }, {m1 }, {b1 .b3 })
T3 = ({g1 }, {m1 .m2 }, {b3 })
T4 = ({g1 , g2 , g3 }, {m1 , m2 , m3 }, ∅)
T5 = ({g1 , g2 , g3 }, ∅, {b1 , b2 , b3 })
T6 = (∅, {m1 , m2 , m3 }, {b1 , b2 , b3 })
The triconcepts are partitioned in clusters the following way:
C1 = {({g3 }, {m2 }, {b2 })}
C2 = {({g1 }, {m1 }, {b1 .b3 }), ({g1 }, {m1 .m2 }, {b3 })}
C3 = {({g1 , g2 , g3 }, {m1 , m2 , m3 }, ∅), ({g1 , g2 , g3 }, ∅, {b1 , b2 , b3 }),
(∅, {m1 , m2 , m3 }, {b1 , b2 , b3 })}
Then, we obtain the dyadic context of reachability K▹ as depicted in Figure 1.
K▹ T1 T2 T3 T4 T5 T6
T1 × × × × × ×
T2 × × × × ×
T3 × × × × ×
T4 × × ×
T5 × × ×
T6 × × ×
Fig. 1: Dyadic context of
reachability K▹ Fig. 2: Concept lattice of K▹
Moreover, when computing the concept lattice of K▹ , we obtain a represen-
tation 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 be-
tween 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.
5 Conclusions and Future Work
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 benefit from the
lattice representation of the clusters’ structure by offering the user an overview
of the underlying data structure. The described navigation paradigm was imple-
mented in a tool suite called FCA Tools Bundle that is described in more detail
in an additional paper [5].
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.
References
1. Dragoş, S., Haliţă, D., Troancă, D.: Investigating trend-setters in e-learning systems
using polyadic formal concept analysis and answer set programming. In: Proc. of
AI4KM 2016, co-located with IJCAI. pp. 42–48 (2016)
2. Ganter, B., Stumme, G., Wille, R. (eds.): Formal Concept Analysis, Foundations
and Applications, LNCS, vol. 3626. Springer (2005)
3. Ganter, B., Wille, R.: Formal Concept Analysis - Mathematical Foundations.
Springer (1999)
4. Jäschke, R., Hotho, A., Schmitz, C., Ganter, B., Stumme, G.: TRIAS - An Algo-
rithm for Mining Iceberg Tri-Lattices. In: Clifton, C.W., Zhong, N., Liu, J., Wah,
B.W., Wu, X. (eds.) Proc. of ICDM 2006. pp. 907–911. IEEE (2006)
5. Kis, L.L., Săcărea, C., Troancă, D.: FCA Tools Bundle - a Tool that Enables
Dyadic and Triadic Conceptual Navigation. In: Proc. of FCA4AI 2015, co-located
with IJCAI 2015 (2015)
6. Lehmann, F., Wille, R.: A Triadic Approach to Formal Concept Analysis. In: Ellis,
G., Levinson, R., Rich, W., Sowa, J.F. (eds.) Proc. of ICCS 1995. Lecture Notes
in Computer Science, vol. 954, pp. 32–43. Springer (1995)
7. Rudolph, S., Săcărea, C., Troancă, D.: Membership constraints in formal concept
analysis. In: Yang, Q., Wooldridge, M. (eds.) Proc. of IJCAI 2015. pp. 3186–3192.
AAAI Press (2015)
8. Rudolph, S., Săcărea, C., Troancă, D.: Towards a navigation paradigm for triadic
concepts. In: Baixeries, J., Săcărea, C., Ojeda-Aciego, M. (eds.) Proc. of ICFCA
2015. LNCS, vol. 9113, pp. 232–248. Springer (2015)
9. Rudolph, S., Săcărea, C., Troancă, D.: Conceptual navigation for polyadic formal
concept analysis. In: Proc. of AI4KM 2016, co-located with IJCAI. pp. 35–41 (2016)
10. Warren, H.S.: A modification of Warshall’s algorithm for the transitive closure of
binary relations. Commun. ACM 18(4), 218–220 (1975)
11. Warshall, S.: A Theorem on Boolean Matrices. J. ACM 9(1), 11–12 (1962)