=Paper=
{{Paper
|id=Vol-1430/paper6
|storemode=property
|title=Reduction in Triadic Data Sets
|pdfUrl=https://ceur-ws.org/Vol-1430/paper6.pdf
|volume=Vol-1430
|dblpUrl=https://dblp.org/rec/conf/ijcai/RudolphST15a
}}
==Reduction in Triadic Data Sets==
https://ceur-ws.org/Vol-1430/paper6.pdf
Reduction in Triadic Data Sets
Sebastian Rudolph1 , Christian Săcărea2 , and Diana Troancă2
1
Technische Universität Dresden
2
Babeş-Bolyai University Cluj Napoca
sebastian.rudolph@tu.dresden.de, csacarea@cs.ubbcluj.ro,
dianat@cs.ubbcluj.ro
Abstract. Even if not explicitly stated, data can be often interpreted
in a triadic setting in numerous scenarios of data analysis and process-
ing. 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 knowl-
edge 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
affecting its underlying structure, these methods are missing in the tri-
adic 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.
1 Introduction
Formal Concept Analysis has constantly developed in the last 30 years, one im-
portant point in its evolution being, the extension to Triadic Formal Concept
Analysis (3FCA) proposed by Lehmann and Wille in [7]. Wille introduces Con-
ceptual 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
affecting 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 defined until now.
This paper is devoted to reduction procedures in triadic contexts and an analysis
of the effects of reducing in a medical data set is provided in the applications
section. The paper concludes with a discussion about how an efficient navigation
environment for different 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 specific results about 3FCA we refer the interested reader to the
standard literature [3].
Definition 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 be-
tween them. The elements of K1 , K2 , K3 are called (formal) objects, attributes
and conditions, respectively. An element (g, m, b) ∈ Y is read object g has at-
tribute m under condition b.
The following definition shows how dyadic contexts can be obtained from a
triadic one in a natural way.
Definition 2 (Derived contexts). Every triadic context (K1 , K2 , K3 , Y ) gives
rise to the following projected 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 ,
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 .
The derivation operators in the triadic case are defined using the dyadic
derivation operators in the projected formal dyadic contexts.
Definition 3 ((i)-derivation operators). For {i, j, k} = {1, 2, 3} with j < k
and for X ⊆ Ki and Z ⊆ Kj × Kk the (i)-derivation operators are defined by:
X 7→ X (i) := {(aj , ak ) ∈ Kj × Kk | (ai , aj , ak ) ∈ Y for all ai ∈ X}.
Z 7→ Z (i) := {ai ∈ Ki | (ai , aj , ak ) ∈ Y for all (aj , ak ) ∈ Z}.
Obviously, these derivation operators correspond to the derivation operators of
the dyadic contexts K(i) , i ∈ {1, 2, 3}.
Definition 4 ((i, j, Xk )-derivation operators). For {i, j, k} = {1, 2, 3} and
Xi ⊆ Ki , Xj ⊆ Kj , Xk ⊆ Kk , the (i, j, Xk )-derivation operators are defined by
(i,j,Xk )
Xi 7→ Xi := {aj ∈ Kj | (ai , aj , ak ) ∈ Y for all (ai , ak ) ∈ Xi × Xk }
(i,j,Xk )
Xj 7→ Xj := {ai ∈ Ki | (ai , aj , ak ) ∈ Y for all (aj , ak ) ∈ Xi × Xk }.
The (i, j, Xk )-derivation operators correspond to those of the dyadic contexts
(ij)
(Ki , Kj , YXk ).
Triadic concepts are defined using the above derivation operators and are
maximal cuboids of incidences.
Definition 5. A triadic concept (short: triconcept) of K := (K1 , K2 , K3 , Y ) is
a triple (A1 , A2 , A3 ) with Ai ⊆ Ki for i ∈ {1, 2, 3} and Ai = (Aj × Ak )(i) for
every {i, j, k} = {1, 2, 3} 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 {1, 2, 3} and all pairs of subsets of L. We denote the set of
all order filters of the complete trilattice L with respect to the preorder .i by
Fi (L). A principal filter is denoted by [x) := {y ∈ L | x .i y}. A subset X of L
is said to be i − dense with respect to L if each principal filter of (L, .i ) is the
intersection of some order filters 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
[ [
∇ik (Xi , Xk ) := bik {Ai | (A1 , A2 , A3 ) ∈ Xi }, {Ak | (A1 , A2 , A3 ) ∈ Xk } .
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 ⇔ ∩3i=1 ∩ai ∈Ai κ̃i (ai ) 6= ∅
for all A1 ⊆ K1 , A2 ⊆ A2 , A3 ⊆ K3 . In particular, L ∼ = T(L, L, L, YL ) with
YL := {(x1 , x2 , x3 ) ∈ L3 | (x1 , x2 , x3 ) is joined}.
3 Reduced tricontexts
In the dyadic case, a context is called clarified if there are no identical rows and
columns, more precisely,
Definition 6. A dyadic context (G, M, I) is clarified if for any objects g, h ∈ G,
from g 0 = h0 follows g = h, and for all attributes m, n ∈ M , m0 = n0 implies
m = n.
In the triadic case, we can make use of the same idea applied on the ”flat-
tened” 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.
Definition 7. A triadic context (K1 , K2 , K3 , Y ) is clarified if for every i ∈
{1, 2, 3} and every u, v ∈ 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 effect 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,
Definition 8. A clarified 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 influence on the structure of the
trilattice of K, hence they can be reduced.
Definition 9. A clarified tricontext (K1 , K2 , K3 , Y ) is called object reduced if
every object concept from the context (K1 , K2 × K3 , Y (1) ) is ∨-irreducible, at-
tribute reduced if every object concept from the context (K2 , K3 × K1 , Y (2) ) is
∨-irreducible, and condition reduced if every object concept from the context
(K3 , K1 × K2 , Y (3) ) is ∨-irreducible.
Proposition 1. Let g ∈ K1 be an object and X ⊆ K1 with g 6∈ X but g (1) =
X (1) in K(1) = (K1 , K2 × K3 , Y (1) ), i.e. g is ∨-reducible in K(1) . Then
T(K1 , K2 , K3 , Y ) ∼
= T(K1 \ {g}, K2 , K3 , Y ∩ ((K1 \ {g}) × K2 × K3 )).
Proof. By Theorem 1, it suffices to define a map κ̃1 : K1 → F1 (T(K1 \
{g}, K2 , K3 , Y ∩ (K1 \ {g} × K2 × K3 )) such that κ̃1 (K1 ) is 1-dense in F1 (T(K1 \
{g}, K2 , K3 , Y ∩ (K1 \ {g} × K2 × K3 )). This can be done by κ̃1 (h) := κ(h) if
h 6= g and κ̃1 (g) := ∩x∈X κ1 (x) elsewhere.
Let (A1 , A2 , A3 ) ∈ T(K) with g ∈ A1 . Since A1 = (A2 × A3 )(1) , we have
g ∈ (A2 × A3 )(1) , wherefrom follows that (A2 × A3 )(3)(3) ⊆ g (1) = X (1) . Then
X (1)(1) ⊆ (A2 × A3 )(1) = A1 , hence X ⊆ A1 . We have that κ1 (g) ⊆ ∩x∈X κ1 (x).
By a similar argument, we can prove the converse inclusion, hence the equality.
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:
b1 m1 m2 m3 b2 m1 m2 m3 b3 m1 m2 m3
g1 × g1 × × g1 ×
g2 × g2 × g2 × ×
g3 g3 × g3 ×
The non-trivial triconcepts of this context are: ({g1 }, {m1 }, {b1 , b2 , b3 }), ({g2 },
{m3 }, {b1 }), ({g1 , g2 , g3 }, {m1 }, {b2 , b3 }), ({g1 }, {m1 , m3 }, {b2 }), ({g2 },
{m1 , m2 }, {b3 }). 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 ∈ Ki , i =
1, 2, 3. Then the element ai is reducible if and only if there exist a subset X ⊆ Ki
(jk) (jk) (jk)
with YX = Yai , where YX := {(bj , bk ) ∈ Kj × Kk | ∀bi ∈ X. (bi , bj , bk ) ∈
Y }, for {i, j, k} = {1, 2, 3}.
Proof. The element ai ∈ Ki is reducible if and only if there exists a subset
(i)
X ⊆ Ki , such that they have the same derivative, i.e., ai = X (i) in K(i) . Now
(jk)
(bj , bk ) ∈ Yai if and only if (a, bj , bk ) ∈ Y which is equivalent to (bj , bk ) ∈
(i)
ai = X (i) . 2
Remark 2. Remember that finite tricontexts can be represented as slices consist-
ing 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 finding 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 define a
similar notion for tricontexts, where the role of the double arrow will be played
by the symbol A.
Definition 10. Let K := (K1 , K2 , K3 , Y ) be a tricontext. For g ∈ K1 , m ∈
K2 , b ∈ K3 we define the following relations, where . is the arrow relation from
dyadic FCA:
– (g, m, b) ∈ / ⇔ g . (m, b)
– (g, m, b) ∈ 4 ⇔ m . (g, b)
– (g, m, b) ∈ . ⇔ b . (g, m)
– (g, m, b) ∈ A ⇔ (g, m, b) ∈ / and (g, m, b) ∈ 4, and (g, m, b) ∈ .
Remark 3. An element ai ∈ Ki will be reducible if and only if its corresponding
(jk)
slice, i.e., (Kj , Kk , Yai ) 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 defined as a set of
triconcepts.
Definition 11. Let K := (K1 , K2 , K3 , Y ) be a tricontext, g ∈ K1 , m ∈ K2 , and
b ∈ K3 be objects, attributes, and conditions, respectively. The object concept of
g is defined as γ ∆ (g) := {(A1 , A2 , A3 ) ∈ T(K) | A1 = g (1)(1) }, where (·)(i) is the
derivation operator g in K(i) , i ∈ {1, 2, 3}. Similar, the attribute concept of m is
defined as µ∆ (m) := {(A1 , A2 , A3 ) ∈ T(K) | A2 = m(2)(2) }, while the condition
concept of b is defined as β ∆ (b) := {(A1 , A2 , A3 ) ∈ T(K) | A2 = b(3)(3) }.
Lemma 1. Let (K1 , K2 , K3 , Y ) be a tricontext, ai ∈ Ki , i ∈ {1, 2, 3}. Let
Γ1 (a1 ) := [γ1∆ (a1 )) be the filter generated by the triadic object concept γ1∆ (a1 ) in
(T(K), .1 ) (and similar Γ2 (a2 ), and Γ3 (a3 ) for attribute and conditions tricon-
cepts, respectively). Then Γi (Ki ) := {Γi (ai ) | ai ∈ Ki } is i-dense in (T(K), .1
, .2 , .3 ).
Proof. Following the construction used in the proof of Theorem
T 1, the princi-
pal filter of the triadic concept (A1 , A2 , A3 ) in (T(K), .i ) is ai ∈Ai {(B1 , B2 , B3 ) ∈
T(K) | ai ∈ Bi } ∈ Fi (T(K)). Combining this with the fact that for (B1 , B2 , B3 ) ∈
(i)(i)
T(K), ai ∈ Bi iff ai ⊆ Bi , we obtain an i-dense set of order filters Γi (Ki ) and
Γi (ai ) = {(B1 , B2 , B3 ) ∈ T(K) | ai ∈ Bi } for ai ∈ 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 devel-
oped 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
define, according to his own view, which are the objects, the attributes and the
conditions. The ternary incidence relation is then read from the database. More-
over, 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 tri-
concepts. 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 identification number, for example Tumor se-
quence, Topography, Morphology, Behavior, Basis of diagnosis, Differentiation
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
different 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 first 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 clarified
tricontext with 61 objects. Herefrom, 38 objects could be reduced as well as 7
attributes (all of them being certainty-related, due to the specific 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 clarified 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 defined 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 elimi-
nates redundant information, hence increasing the efficiency in determining its
underlying conceptual structure. Moreover, due to the selection procedure spe-
cific 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 dis-
cussed in [9], which will include reduction as a preprocessing stage. The ToscanaJ
knowledge management suite and its triadic extension Toscana2Trias makes pos-
sible 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 defined
constraints. More specifically, the user defines 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 defined constraints for FCA, including complexity results, we refer to [8].
References
1. Becker, P., Correia, J.H.: The toscanaj suite for implementing conceptual informa-
tion systems. In: Ganter et al. [2], pp. 324–348
2. Ganter, B., Stumme, G., Wille, R. (eds.): Formal Concept Analysis, Foundations
and Applications, Lecture Notes in Computer Science, vol. 3626. Springer (2005)
3. Ganter, B., Wille, R.: Formal concept analysis - mathematical foundations.
Springer (1999)
4. Glodeanu, C.: Triadic factor analysis. In: Kryszkiewicz, M., Obiedkov, S.A. (eds.)
Proceedings of the 7th International Conference on Concept Lattices and Their Ap-
plications, Sevilla, Spain, October 19-21, 2010. CEUR Workshop Proceedings, vol.
672, pp. 127–138. CEUR-WS.org (2010), http://ceur-ws.org/Vol-672/paper12.pdf
5. Jäschke, R., Hotho, A., Schmitz, C., Ganter, B., Stumme, G.: TRIAS -
an algorithm for mining iceberg tri-lattices. In: Proceedings of the 6th
IEEE International Conference on Data Mining (ICDM 2006), 18-22 Decem-
ber 2006, Hong Kong, China. pp. 907–911. IEEE Computer Society (2006),
http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=4053012
6. Jäschke, R., Hotho, A., Schmitz, C., Ganter, B., Stumme, G.: Discovering shared
conceptualizations in folksonomies. Journal of Web Semantics 6(1), 38–53 (2008)
7. Lehmann, F., Wille, R.: A triadic approach to formal concept analysis. In: Ellis,
G., Levinson, R., Rich, W., Sowa, J.F. (eds.) Proceedings of the Third Interna-
tional Conference on Conceptual Structures, ICCS ’95. LNCS, vol. 954, pp. 32–43.
Springer (1995)
8. Rudolph, S., Săcărea, C., Troancă, D.: Membership constraints in formal concept
analysis. In: Proceedings of the 24th International Joint Conference on Artificial
Intelligence (IJCAI) (2015), to appear
9. Rudolph, S., Săcărea, C., Troancă, D.: Towards a navigation paradigm for triadic
concepts. In: Baixeries, J., Sacarea, C., Ojeda-Aciego, M. (eds.) Proceedings of the
13th International Conference on Formal Concept Analysis (ICFCA 2015). LNCS,
vol. 9113, pp. 232–248. Springer (2015)
10. Săcărea, C.: Investigating oncological databases using conceptual landscapes. In:
Hernandez, N., Jäschke, R., Croitoru, M. (eds.) Graph-Based Representation and
Reasoning - 21st International Conference on Conceptual Structures, ICCS 2014,
Iaşi, Romania, July 27-30, 2014, Proceedings. Lecture Notes in Computer Science,
vol. 8577, pp. 299–304. Springer (2014)
11. Wille, R.: The basic theorem of triadic concept analysis. Order 12(2), 149–158
(1995)
12. Wille, R.: Begriffliche Wissensverarbeitung: Theorie und Praxis. Informatik Spek-
trum (23), 357–369 (2000)
13. Wille, R.: Formal concept analysis as mathematical theory of concepts and concept
hierarchies. In: Ganter et al. [2], pp. 1–33
14. Wille, R.: Methods of conceptual knowledge processing. In: Missaoui, R., Schmid,
J. (eds.) Formal Concept Analysis, 4th International Conference, ICFCA 2006,
Dresden, Germany, February 13-17, 2006, Proceedings. Lecture Notes in Computer
Science, vol. 3874, pp. 1–29. Springer (2006)