Even if not explicitly stated, data can be often interpreted in a triadic setting in numerous scenarios of data analysis and processing. Formal Concept Analysis, as the underlying mathematical theory of Conceptual Knowledge Processing gives the possibility to explore the structure of data and to understand its structure. Representing knowledge as conceptual hierarchies becomes increasingly popular as a basis for further communication of knowledge. While in the dyadic setting there are well-known methods to reduce the complexity of data without a ecting its underlying structure, these methods are missing in the triadic case. Driven by practical requirements, we discuss an extension of the classical reduction methods to the triadic case and apply them to a medium-sized oncological data set.
Introduction Formal Concept Analysis has constantly developed in the last 30 years, one important point in its evolution being, the extension to Triadic Formal Concept Analysis (3FCA) proposed by Lehmann and Wille in [7]. Wille introduces Conceptual Knowledge Processing as an approach to knowledge management which is based on Formal Concept Analysis as its underlying mathematical theory [12, 14]. Dealing with three-dimensional data-sets, 3FCA is used to build triadic landscapes of knowledge [13]. The present paper is part of a broader discussion on a navigation paradigm in triadic conceptual landscapes.
Triadic FCA has been successfully used in inherently triadic scenarios such as collaborative tagging [6], triadic factor analysis [4], or investigation of oncological databases [10]. Despite the fact that 3FCA is just an extension of FCA, the graphical representation for the dyadic case does not have an intuitive extension to the triadic case. An initial investigation based on locally displaying smaller parts of the space of triconcepts, using perspectives for navigation has been done in [9].
For dyadic contexts, reducible objects and attributes can be deleted, without a ecting the underlying conceptual structure. Clarifying and reducing is thus a preprocessing stage, in order to simplify the structure of the context for further analysis. For triadic data sets, these notions have not been de ned until now. This paper is devoted to reduction procedures in triadic contexts and an analysis of the e ects of reducing in a medical data set is provided in the applications section. The paper concludes with a discussion about how an e cient navigation environment for di erent types of conceptual structures could combine existing tools (see Applications section) with newly developed navigation paradigms for triadic concept sets, starting from the same underlying data set (which does not have to be necessarily a typical triadic set). 2
Preliminaries This section is devoted to some basic notions of triadic formal concept analysis as they have been introduced in [7, 11]. For further information about the dyadic case or more speci c results about 3FCA we refer the interested reader to the standard literature [3].
De nition 1. A triadic context (also: tricontext) is a quadruple (K1; K2; K3; Y ), where K1; K2 and K3 are sets and Y K1 K2 K3 is a ternary relation between them. The elements of K1; K2; K3 are called (formal) objects, attributes and conditions, respectively. An element (g; m; b) 2 Y is read object g has attribute m under condition b.
The following de nition shows how dyadic contexts can be obtained from a triadic one in a natural way.
De nition 2 (Derived contexts). Every triadic context (K1; K2; K3; Y ) gives rise to the following projected dyadic contexts:
K(
K(
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.
The derivation operators in the triadic case are de ned using the dyadic derivation operators in the projected formal dyadic contexts.
De nition 3 ((i)-derivation operators). For fi; j; kg = f1; 2; 3g with j < k and for X Ki and Z Kj Kk the (i)-derivation operators are de ned by: X 7! X(i) := f(aj ; ak) 2 Kj Kk j (ai; aj ; ak) 2 Y for all ai 2 Xg.
Z 7! Z(i) := fai 2 Ki j (ai; aj ; ak) 2 Y for all (aj ; ak) 2 Zg.
Obviously, these derivation operators correspond to the derivation operators of the dyadic contexts K(i); i 2 f1; 2; 3g.
De nition 4 ((i; j; Xk)-derivation operators). For fi; j; kg = f1; 2; 3g and Xi Ki; Xj Kj ; Xk Kk, the (i; j; Xk)-derivation operators are de ned by Xi 7! X(i;j;Xk) := faj 2 Kj j (ai; aj ; ak) 2 Y for all (ai; ak) 2 Xi
i Xj 7! X(i;j;Xk) := fai 2 Ki j (ai; aj ; ak) 2 Y for all (aj ; ak) 2 Xi j Xkg Xkg.
The (i; j; Xk)-derivation operators correspond to those of the dyadic contexts (Ki; Kj ; Y (ij)).
Xk
Triadic concepts are de ned using the above derivation operators and are maximal cuboids of incidences.
De nition 5. A triadic concept (short: triconcept) of K := (K1; K2; K3; Y ) is a triple (A1; A2; A3) with Ai Ki for i 2 f1; 2; 3g and Ai = (Aj Ak)(i) for every fi; j; kg = f1; 2; 3g with j < k. The sets A1; A2, and A3 are called extent, intent, and modus of the triadic concept, respectively. We let T(K) denote the set of all triadic concepts of K.
A complete trilattice is a triordered set (L; .1; .2; .3) in which the ik-joins exist for all i 6= k in f1; 2; 3g and all pairs of subsets of L. We denote the set of all order lters of the complete trilattice L with respect to the preorder .i by Fi(L). A principal lter is denoted by [x) := fy 2 L j x .i yg. A subset X of L is said to be i dense with respect to L if each principal lter of (L; .i) is the intersection of some order lters from X .
Theorem 1 (The basic theorem of triadic concept analysis). Let K := (K1; K2; K3; Y ) be a triadic context. Then T(K) is a complete trilattice of K for which the ik-joins can be described as follows rik(Xi; Xk) := bik
[fAi j (A1; A2; A3) 2 Xig; [fAk j (A1; A2; A3) 2 Xkg : In general, a complete trilattice (L .1; .2; .3) is isomorphic to T(K) if and only if there exist mappings ~i: Ki ! Fi(L)(i = 1; 2; 3) such that ~i(Ki) is i-dense with respect to L and A1 A2 A3 Y , \i3=1 \ai2Ai ~i(ai) 6= ; for all A1 K1, A2 A2, A3 K3. In particular, L = T(L; L; L; YL) with YL := f(x1; x2; x3) 2 L3 j (x1; x2; x3) is joinedg. 3
Reduced tricontexts In the dyadic case, a context is called clari ed if there are no identical rows and columns, more precisely, De nition 6. A dyadic context (G; M; I) is clari ed if for any objects g; h 2 G, from g0 = h0 follows g = h, and for all attributes m; n 2 M , m0 = n0 implies m = n.
In the triadic case, we can make use of the same idea applied on the " attened" projection of the tricontext. Since a triconcept (A1; A2; A3) is a maximal triple of triadic incidences, removing identical "rows" in the tricontext does not alter the structure of triconcepts.
De nition 7. A triadic context (K1; K2; K3; Y ) is clari ed if for every i 2 f1; 2; 3g and every u; v 2 Ki, from u(i) = v(i) follows u = v.
Context reduction is one of the most important operations performed in the dyadic case, with no e ect on the conceptual structure. This consists in the removal of reducible objects and attributes. Reducible objects and attributes are precisely those objects and attributes which can be written as combinations of other objects and attributes, respectively. Formally, De nition 8. A clari ed context (G; M; I) is called row reduced if every object concept is _-irreducible and column reduced if every attribute concept is ^irreducible.
Remark 1. Due to the symmetry of the context, if we switch the role of the objects with that of the attributes and look at the context (M; G; I 1), then the context is row reduced if every object concept (attribute concept in the former context) is _-irreducible. So we can consider only _-irreducible concepts by "switching the perspective".
Similar to the dyadic case, objects, attributes, and conditions which can be written as combinations of others have no in uence on the structure of the trilattice of K, hence they can be reduced.
De nition 9. A clari ed tricontext (K1; K2; K3; Y ) is called object reduced if
every object concept from the context (K1; K2 K3; Y (
Proposition 1. Let g 2 K1 be an object and X K1 with g 62 X but g(
K3)): Proof. By Theorem 1, it su ces to de ne a map ~1: K1 ! F1(T(K1 n fgg; K2; K3; Y \ (K1 n fgg K2 K3)) such that ~1(K1) is 1-dense in F1(T(K1 n fgg; K2; K3; Y \ (K1 n fgg K2 K3)). This can be done by ~1(h) := (h) if h 6= g and ~1(g) := \x2X 1(x) elsewhere.
Let (A1; A2; A3) 2 T(K) with g 2 A1. Since A1 = (A2 A3)(
This proves that ~1(K1) is 1-dense, i.e., the two trilattices are isomorphic. 2 Example 1. The following example shows how reduction works:
m1 m2 m3 m1 m2 m3 m1 m2 m3 The non-trivial triconcepts of this context are: (fg1g; fm1g; fb1; b2; b3g), (fg2g; fm3g; fb1g), (fg1; g2; g3g; fm1g; fb2; b3g), (fg1g; fm1; m3g; fb2g), (fg2g; fm1; m2g; fb3g). We can observe that by reducing g3, the number of triconcepts remains unchanged and the trilattice will be the same.
We obtain the following characterization for reducible elements.
Proposition 2. Let K = (K1; K2; K3; Y ) be a tricontext and ai 2 Ki, i = 1; 2; 3. Then the element ai is reducible if and only if there exist a subset X Ki with YX(jk) = Ya(ijk), where YX(jk) := f(bj ; bk) 2 Kj Kk j 8bi 2 X: (bi; bj ; bk) 2 Y g, for fi; j; kg = f1; 2; 3g.
Proof. The element ai 2 Ki is reducible if and only if there exists a subset X Ki, such that they have the same derivative, i.e., ai(i) = X(i) in K(i). Now (bj ; bk) 2 Ya(ijk) if and only if (a;bj ; bk) 2 Y which is equivalent to (bj ; bk) 2 a(i) = X(i).
i 2 Remark 2. Remember that nite tricontexts can be represented as slices consisting of dyadic contexts. Moreover, this representation has a sixfold symmetry. In order to represent the triadic context in a plane, we just put these slices one next to the other (see previous example). This proposition states that ai is reducible if and only if the slice of ai is the intersection of some slices corresponding to the elements of a certain subset X Ki. This has a striking similarity to the dyadic case, where, for example, an object is reducible, if its row is the intersection of the rows from a certain subset X of objects. This also gives us an algorithmic approach to the problem of nding all reducible elements in a tricontext.
Similar to the dyadic case, where double arrow have been introduced in order to identify those rows and columns which are not reducible (remember that a row or a column is not reducible, if it contains a double arrow), we can de ne a similar notion for tricontexts, where the role of the double arrow will be played by the symbol A.
De nition 10. Let K := (K1; K2; K3; Y ) be a tricontext. For g 2 K1; m 2 K2; b 2 K3 we de ne the following relations, where . is the arrow relation from dyadic FCA: { (g; m; b) 2 / , g . (m; b) { (g; m; b) 2 4 , m . (g; b) { (g; m; b) 2 . , b . (g; m) { (g; m; b) 2 A , (g; m; b) 2 / and (g; m; b) 2 4, and (g; m; b) 2 . Remark 3. An element ai 2 Ki will be reducible if and only if its corresponding slice, i.e., (Kj ; Kk; Ya(ijk)) does not contain the triadic arrow A.
In the dyadic case, object and attribute concepts are playing an important role, see for instance the Basic Theorem on Concept Lattices. We might ask if there is a similar notion in the triadic case. Due to the structure of triconcepts, it proves that an object concept, for instance, should be de ned as a set of triconcepts.
De nition 11. Let K := (K1; K2; K3; Y ) be a tricontext, g 2 K1, m 2 K2, and
b 2 K3 be objects, attributes, and conditions, respectively. The object concept of
g is de ned as (g) := f(A1; A2; A3) 2 T(K) j A1 = g(
Proof. Following the construction used in the proof of Theorem 1, the principal lter of the triadic concept (A1; A2; A3) in (T(K); .i) is Tai2Ai f(B1; B2; B3) 2 T(K) j ai 2 Big 2 Fi(T(K)). Combining this with the fact that for (B1; B2; B3) 2 T(K), ai 2 Bi i ai(i)(i) Bi, we obtain an i-dense set of order lters i(Ki) and i(ai) = f(B1; B2; B3) 2 T(K) j ai 2 Big for ai 2 Ki and i = 1; 2; 3. 2 4
Applications In this section we discuss some applications of the previous results on a cancer registry database comprising information about several thousand patients. Even if the original data set does not have an inherently triadic format, one can select triadic subsets herefrom which are then suitable for further analysis. This proves that even many-valued dyadic contexts can be interpreted and studied from a triadic point of view. For more about this interpretation mechanism we refer to [10]). In order to prepare the data for a triadic interpretation, the knowledge management suite ToscanaJ ([1]) and Toscana2Trias, a triadic extension developed at Babes-Bolyai University Cluj-Napoca have been used. Toscana2Trias uses the TRIAS algorithm developed by R. Jaeschke et al. [5]. It connects to a database and displays the table names (or attribute names). The user may de ne, according to his own view, which are the objects, the attributes and the conditions. The ternary incidence relation is then read from the database. Moreover, if a conceptual schema has been built upon the data set, i.e., the data has been preprocessed for ToscanaJ, then the user has even more control over the selection of objects, attributes and conditions. From the conceptual schema, a part of the scaled attributes can be considered as conditions, the rest being considered as attributes in the tricontext. Triadic concepts are then computed, using the Trias algorithm and displayed in a variety of formats. If the data set is larger, the visualization becomes easily obscure because of the number of triconcepts. In this case, one can make use of the navigation paradigm discussed in [9].
The cancer registry database, in its original form, contains 25 attributes for each patient, including an identi cation number, for example Tumor sequence, Topography, Morphology, Behavior, Basis of diagnosis, Di erentiation degree, Surgery, Radiotherapy, Hormonal Therapy, Curative Surgery, Curative Chemotherapy etc. These attributes are all interpreted as conceptual scales and represented as conceptual landscapes for an enhanced knowledge retrieval.
The triadic approach makes possible to investigate these data from a totally di erent point of view. While a typical usage of ToscanaJ implies the combination of several scales into a so-called browsing scenario, 3FCA gives a certain depth to the scale-based navigation of the conceptual landscapes.
For the rst example, we have selected a number of 4686 objects, 11 attributes (all 8 degrees of certainty in the oncological decision process, in-situs carcinoma and tumor sequence 1, i.e., just one tumor) and three conditions (Gender = Male, age < 59, and survival > 30 months). This selection generated a relation with 44545 tuples (crosses in the tricontext) and 63 triconcepts and a clari ed tricontext with 61 objects. Herefrom, 38 objects could be reduced as well as 7 attributes (all of them being certainty-related, due to the speci c selection we have made), resulting in a relation with 77 tuples.
For the next example, the selection was restricted to types of tumors (as attributes) versus stage (as conditions). A clari ed tricontext resulted, with 13 objects, 5 attributes and 8 conditions, and 23 triconcepts. Three more objects, one attribute and one condition could be further reduced. 5
Conclusions and Future Work In this paper we have de ned the notion of reduction for triadic FCA and the notion of triadic object, attribute, and condition concept, showing that these triconcepts are playing for the basic theorem of 3FCA the same role to that played by object and attribute concepts in the dyadic case.
In the applications section, we have shown how reducing a tricontext eliminates redundant information, hence increasing the e ciency in determining its underlying conceptual structure. Moreover, due to the selection procedure speci c to the Toscana2Trias extension, reducible objects (or attributes, conditions) may give important clues about the structure of the data subset.
This contribution is a natural development of the navigation paradigm discussed in [9], which will include reduction as a preprocessing stage. The ToscanaJ knowledge management suite and its triadic extension Toscana2Trias makes possible to generate triadic data sets in a natural way, even if the underlying data does not have a natural triadic structure (as, for instance, folksonomies have). A navigation tool for triadic conceptual landscapes is imperatively necessary, and the local navigation approach described in [9] makes use of a similar approach to that of combining scales in ToscanaJ, hence restricting only to a local view. A selection of the starting points for navigation could be performed by user de ned constraints. More speci cally, the user de nes two lists: one containing required and one forbidden objects, attributes and conditions. This selection will focus on a subset of triconcepts, wherefrom navigation can start. For a detailed discussion of user de ned constraints for FCA, including complexity results, we refer to [8].