Conceptual Visualization and Navigation Methods for Polyadic Formal Concept Analysis

1 Motivation and ProblemDescription

Conceptual knowledge is closely related to a deeper understanding of existing facts and relationships, but also to the argumentation and communication of why something happens in a particular way. Formal Concept Analysis (FCA) is the core of Conceptual Knowledge Processing. It emerged from applied mathematics and quickly developed into a powerful framework for knowledge representation. It is based on a settheoretical semantics and provides a rich amount of mathematical instruments for representation, acquiring, retrieval, discovery and further processing of knowledge.

FCA was introduced in the dyadic setting [Ganter and Wille, 1999] and extended to a triadic [Lehmann and Wille, 1995] and eventually n-adic setting [Voutsadakis, 2002]. Intuitively, dyadic datasets can be understood as objects related to attributes and, in addition, to conditions for the triadic case. FCA defines concepts as maximal clusters of data in which all elements are mutually interrelated. A common problem for n-adic FCA is concept visualization and navigation.

The goal of my thesis is to find visualization and navigation paradigms that can be applied to higher-dimensional datasets. Therefore, we study the triadic case and propose several visualization and navigational approaches. Furthermore, we evaluate these approaches, study their generalizations and extend them, where possible, to n-ary formal contexts.

2 Preliminaries

A short introduction to the FCA notions is necessary in order to fully understand the presented topic.

Definition 1. Let n ≥ 2 be a natural number. An ncontext is an (n + 1)-tuple K := (K1↪K2↪ ▷ ▷ ▷ ↪Kn↪ Y ), where K1↪K2↪ ▷ ▷ ▷ ↪Kn are sets and Y is an n-ary relation Y ✓ K1 ⇥K2 ⇥ · · · ⇥Kn.

Definition 2. The n-concepts of an n-context (K1↪ ▷ ▷ ▷ ↪Kn↪ Y ) are exactly the n-tuples that satisfy A1 ⇥ · · · ⇥ An ✓ Y and which are maximal with respect to component-wise set inclusion. (A1↪ ▷ ▷ ▷ ↪An) is called a proper n-concept if A1↪ ▷ ▷ ▷ ↪ An are all non-empty.

Example 1. Finite triadic contexts can be represented as multiple cross-tables labeled with condition names, while rows are being labeled with object names and columns with attribute names. In the following example we consider a triadic context where the object set consists of authors of scientific papers, the attribute set contains conference names/journal names while the conditions are the publication years (the data has been selected from dblp database).

⇤My research was supported by a scholarship from DAAD.

Alouni ⇥ ⇥

Figure 1: DBLP data: author, conference/journal, year

There are exactly six triconcepts of this context, i.e., maximal 3D cuboids full of incidences:

• ÷ (¶Rumpe↪Alouni♦↪ ¶Corr♦↪ ¶2014↪ 2015♦),
• ÷ (¶Alouni♦↪ ¶Corr↪ ICC↪ PIMRC♦↪ ¶2014♦),
• ÷ (¶Alouni♦↪ ¶Corr↪ ICC♦↪ ¶2014↪ 2015♦),
• ÷ (¶Rumpe♦↪ ¶Corr↪HICSS♦↪ ¶2015♦),
• ÷ (;↪ ¶Corr↪ ICC ↪ PIMRC ↪HICSS♦↪ ¶2014↪ 2015♦) and
• ÷ (¶Rumpe↪Alouni♦↪¶Corr↪ICC↪PIMRC↪HICSS♦↪ ;)

The first four of these triconcepts are proper.

3 Progress to Date

3.1 Visualization of Triadic Contexts

In our previous work we applied triadic FCA to study the navigational patterns of students in an e-learning environment [Dragos¸ et al., 2014a; 2014b]. The purpose is to find methods to enhance e-learning systems and to make predictions of user patterns. The problem that arised during this study is that the triconcepts contain a large amount of data, so displaying the components is not helpful. The approach used in these works is to define some dyadic projections and visualize the dyadic data obtained with a tool called Circos that uses a circular layout.

3.2 ANavigation Paradigm based on Reachability Clusters

Next, we address the problem of navigation and consider a paradigm based on a neighborhood notion arising from appropriately defined projections [Rudolph et al., 2015b]. The navigation starts locally, from a chosen triconcept and the first step is to fix one perspective, i.e. one of the three dimensions. The next step of the navigation must be chosen from the socalled directly reachable concepts, which can be computed with a dyadic projection once a perspective is chosen. After selecting one of the directly reachable triconcepts, one may change the perspective and move towards a different group of reachable triconcepts. Because of the local character, this navigation allows to explore large datasets. The corresponding reachability relation defined as a transitive closure of the direct reachability, gives rise to equivalence classes called clusters. These clusters are structured by a partial order. As a consequence, we present in the paper a first exploration strategy based on the previously introduced notions.

One of the useful techniques used to optimize visualization and navigation in dyadic contexts are the clarification and reduction processes. In order to support our proposed navigation paradigm, we extend these notions to triadic formal contexts [Rudolph et al., 2015c]. The intuition behind is to eliminate elements from the context without loss of information. In the clarification phase one looks for elements of a set having the same behavior, i.e. that are in relation with the same elements of the other two sets. Those elements can be clarified (unified as one element), hence reducing the size of the context. The reduction process consists of the removal of elements which can be written as combinations of other elements of the same set. Both techniques help reducing the size of the context while keeping its structure for further analysis.

3.3 Interactive Concept Navigation using Membership Constraints

The second navigational approach [Rudolph et al., 2015a] is more user-oriented and has an interactive character. We give the user the freedom to choose what elements to include and exclude from the components of the formal concept. We formalize the user's restrictions as membership constraints.

Definition 3. An n-adic membership constraint on an n-context K = (K1↪ ▷ ▷ ▷ ↪Kn↪R) is a 2n-tuple C = (K+ 1 ↪K1 ↪ ▷ ▷ ▷ ↪K+ n ↪Kn ) with K+ i ✓Ki called required sets and Ki ✓Ki called forbidden sets.

An n-concept (A1↪ ▷ ▷ ▷ ↪An) of K is said to satisfy such a membership constraint if K+ i ✓ Ai and Ki \ Ai = ; hold for all i 2 ¶1↪ ▷ ▷ ▷ ↪ n♦.

After each step, i.e. when the user adds a new restriction, there is a propagation phase, during which we compute all additional restrictions required for ensuring that the user will always get to a proper n-concept at the end of the navigation.

We consider this approach to be more intuitive and userfriendly than the previous one, especially for users who are not very familiar with FCA. Hence, we intesively analyzed implementation methods for this navigation framework. We came up with two different strategies for the implementation of the navigation tool. The first strategy 1 relies on Answer Set Programming [Gebser et al., 2012] and extends the ASP encoding of the membership constraint satisfiability problem [Rudolph et al., 2015a]. The advantage of this navigation tool is that it can be easily extended to n-ary contexts, for any n, by the model of the already implemented cases n 2 ¶2↪ 3↪ 4♦. The second strategy 2 is a brute force implementation and uses an exhaustive search in the whole formal concept space. In order to use this tool one must precompute the formal concepts with an existing tool, like Trias 3 for the triadic case. Both implementations were described in more detail, as well as evaluated and compared, in a paper currently under review.

4 Future Plan

For future work, we plan to implement the navigation paradigm based on clusters as well as the brute-force approach for the n-adic case and run usability studies on all the proposed navigation paradigms.