Triadic formal concept analysis has become a popular research direction, since triadic relations give natural models of many data collections. In this paper we address the problem of selecting most interesting concepts by proposing triadic stability indices. Triadic formal concept analysis (3FCA) was introduced by Rudolf Wille and Fritz Lehmann [1] to model hierarchies of classes and dependencies arising from ternary relations. Recently, several algorithms for computing frequent triconcepts were proposed [2, 3]. It is noticed that some infrequent concepts are still interesting, since they represent extraordinary or uncommon data. In this paper we propose triadic stability for selecting interesting triadic concepts. Together with exact stability indices we suggest their e cient approximations analogous to -stability introduced in [4].
2.1
Formal Concept Analysis First, we brie y recall some basic de nitions of the Formal Concept Analysis (FCA) [5]. A formal context is a triple (G; M; I). G and M are sets of objects and attributes respectively, and I is an incidence relation. It is de ned as the Cartesian product G M , i.e. (g; m) 2 I if the object g 2 G has the attribute m 2 M . The derivation operators ( )0 are de ned for A G and B M as follows:
A0 = fm 2 M j 8g 2 A : gImg
B0 = fg 2 G j 8m 2 B : gImg A0 is the set of attributes common to all objects of A, and B0 is the set of objects sharing all attributes of B. The double application of ( )0 is a closure operator, i.e. ( )00 is extensive, idempotent and monotone. Subsets A G, B M such that A = A00 and B = B00 are called closed.
A (formal) concept is a pair (A; B), where A G, B M and A0 = B, B0 = A. A is called the (formal) extent, and B is called the (formal) intent of the concept (A; B).
A concept lattice (or Galois lattice) is a partial ordered set of concepts, the order 6 on the set of concepts is de ned as follows: (A; B) (C; D) i A C (D B), a pair (A; B) is a subconcept of (C; D), while (C; D) is a superconcept of (A; B). Each nite lattice has the highest element with A = G, called the top element, and the lowest element with B = M , called the bottom element. 2.2
Triadic Concept Analysis In the case of a triadic relation one deals with a quadruple (G; M; B; Y ), called a triadic context. G, M , B are sets and Y is a ternary relation between G, M and B, i.e. Y G M B; the elements of G, M and B are called objects, attributes and conditions respectively, and (g; m; b) 2 Y is read: object g has attribute m under condition b.
The dyadic derivation operators can be used to construct triadic concepts. A triadic context can be represented as follows: K := (K1; K2; K3; Y ), where K1 is a set of objects G, K2 is a set of attributes and K3 is a set of conditions, and each element of Ki may be seen as an instance of Peirce's i-th category [1]. For every triadic context one de nes the following dyadic contexts:
K1 := K1; K2 K3; Y (
Kk, one de nes K(Ai;kj) :=
Ki; Kj ; YA(ik;j) , where (ai; aj ) 2 YA(ik;j) if and only if (ai; aj ; ak) 2 Y for all ak 2 Ak.
Put di erently, the context K(i) is a attened representation of the original triadic context, while K(Ai;kj) corresponds to the relation between elements of Ki and Kj that belong to Ak. (i)-derivation operator For fi; j; kg = f1; 2; 3g with j < k and for X Z Kj Kk the (i)-derivation operators are de ned by Ki and 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 (i; j; Xk)-derivation operators For fi; j; kg = f1; 2; 3g and for Xi and Ak Kk the (i; j; Xk)-derivation operators are de ned by Ki, Xj
Kj Xi 7 ! X(i;j;Ak) := faj 2 Kj j (ai; aj ; ak) 2 Y for all (ai; ak) 2 Xi i Xj 7 ! X(i;j;Ak) := fai 2 Ki j (ai; aj ; ak) 2 Y for all (aj ; ak) 2 Xj j Akg Akg
A triadic concept (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 triadic concept lattice has three maximal elements, namely ((K2 K3)(
Stability indices for formal concepts were introduced in [6, 7] and modi ed in [8]. We de ne stability indices for the triadic case in a similar way. We describe two types of stability that correspond to the derivation operators de ned above. (i)-stability For a triadic concept (A1; A2; A3) the (i)-stability is de ned by: Stab(i) (A1; A2; A3) := j X
AijX(i) = (Aj
Ak) j
This index shows how much the binary relation on sets Xj and Xk is dependent on particular elements of a subset Ai. (i; j; Xk)-stability For a triadic concept (A1; A2; A3) the (i; j; Xk)-stability is de ned by:
Stab(i;j;Xk) (A1; A2; A3) := j X (Ai
Aj ) jX(k) = Ak j
The (i; j; Xk)-stability allows us to estimate the dependence of a subset Ak on elements of the (Xi; Xj )-relation.
Example Below we consider a small examples of computing stability indices for
a concept. The formal context is given in the table 1.
and f2; 3g(
f ; g).
Let us consider a triconcept C = (f2; 3g ; fb; cg ; f ; g) with (
Stab(
C corresponding to all possible subsets of the extent f2; 3g f;g a b c d f2g a b c d f3g a b c d f2; 3g a b c d
Stab(1;3;X2) (C) = 38 . To compute this value one needs to check 16 subsets of X1 X3 and corresponding subsets of X2. The following sets occur in the numerator: f;; 2; 3; 23g f;; ; ; g.
fb; cg = (f2; 3g ; f ; g)(1;3;A2) = (f2; 3g ; f g)(1;3;A2) = (f3g ; f g)(1;3;A2) (f3g ; f ; g)(1;3;A2) = (f2g ; f g)(1;3;A2) = (f2g ; f ; g)(1;3;A2) 4
The problem of computing stability is #P -complete [6, 7], therefore, in practice, when one deals with a big context and with the huge amount of generated concepts, it is very di cult to apply these indices. That's why, estimates of the stability for dyadic concepts have been proposed [9, 4].
We have expanded the -stability [4] for the case of triadic stability indices. In this regard, it is important to note that the estimates derived from the direct descendants of a triconcept can be useless owing to the de ned quasiorders, because the number of direct neighbors is usually small. In gure 1 the distributions of the descendants number with respect to di erent inclusion/exclusion relations are represented.
Instead of considering the set di erence between (i)-th components of a triconcept and each direct descendant, we consider the set di erence between (i)-th components of a triconcept c = (A1; A2; A3) and other, possibly, unclosed concepts derived by adding new elements from Kj n Aj , j 6= i or Kj Kk n Aj Ak, j; k 6= i. Put di erently, the lower and upper bounds estimates of stability index look as follows: log2
X d2Enl(c) 2 (c;d)
LStab (c) min (c) ; where min (c) = mind2Enl(c) (c; d), Enl (c) = nX j X = fAk [ xg ; x 2 Kk n Ak; X(k) (Ai
Aj ) o and (c; d) is the di erence between jAj j jAkj and the number of elements in X(k) for estimates of (i; j; Xk)-stability.
Enl (c) = nX j X = fAj
Ak [ xg ; x 2 Kj and (c; d) is the di erence between jAij and the number of elements in X(i) for estimates of (i)-stability.
Example. Consider upper and lower bounds of stability estimates for C =
(f2; 3g ; fb; cg ; f ; g) from the running example (Table 1). To get an estimate of
the (
In this section we explore some empirical properties of the introduced indices using synthetic data. We generated four groups of 100 random 10 10 10 contexts with densities 0.1, 0.2, 0.4, 0.6. The features of the data are given in Figure 2.
The choice of a subset of indices for data exploration can be motivated by the following properties: the indices should be pairwise uncorrelated (to avoid biased results when combining indices) and e ciently computable (if possible). The density function of an index may be a multimodal mixture of two or more distributions. In this case one needs a special justi cation for the choice of a threshold value separating two distributions.
We consider Pearson's correlation between all pairs of stability indices and cardinalities of sets that comprise a triadic concept (extent, intent, modus). In Figure 3 the values of the coe cient are represented. The sizes of the extent, intent and modus are denoted by jA1j, jA2j, jA3j, respectively. The sizes of dyadic subcontexts are denoted in a similar way. The corresponding stability estimates are referred to by the log pre x.
As can be seen from Figure 3, there is a correlation between (i)-stability and jAj j jAkj. The index of (i)-stability correlates less strongly with the estimates of (j; k; Xi)-stability and the size of the set Ai. These types of correlation become stronger as the density of a context increases. In fact, these indices can be replaced by the size of a particular set in the case of a dense context. A correlation is observed between (i; j; Xk)-stability and its estimates, a less strong correlation is observed between (i; j; Xk)-stability and jAij jAj j. It is important to note that the strong correlation between (i; j; Xk)-stability and its estimates, as well as very small correlation between (i; j; Xk)-stability and estimates of (k)-stability remains the same with di erent context densities. The pairwise correlation between stability indices is weak, hence it is preferable to use these indices together.
For selecting interesting concepts based on values of an index it is important
to choose a correct threshold. This choice can be based on the distribution of
index values. Figure 4 shows that the distribution of values (
The lower bound of (i)-stability is also strongly correlated with the size of set i. This is due to the fact that a big size of the set i leads to larger di erence between the sizes of Ai and (Xj Xk)(i), where Xj Xk is a superset of Aj Ak, and the sum under logarithm. The estimate of (i; j; Xk)-stability are correlated with the corresponding indices. There is roughly the same correlation between the estimate and the value jAij jAj j, which results from the bigger di erence between jAij jAj j and jXij jXj j, which correspond to a superset of Ak. The upper and lower estimates of (i; j; Xk)-stability also correlate, in this case, the correlation could be related to set-di erence between the set Ai Aj and the volume of the rectangular subarea of Xi Xk for the corresponding superset of Ak.
It is noteworthy that the calculation of stability estimates in practice could take more time then the stability calculation itself. It is typical for (i)-stability, where the number 2jAij is lower then the number of all possible subsets obtained by adding elements from Kj Ak. 6
In this paper we have introduced two stability indices for triadic concepts, based on two derivation operators, and studied their empirical behavior. We have proposed to compute stability using two derivation operators. We have studied correlation of stability indices and their distributions, which is important in practical data analysis. As it was shown, the introduced stability indices are not pairwise correlated and therefore can be used in some combinations for selecting interesting concepts. Moreover, (i)-stability correlates with jAij(for dense contexts) and jAj jjAkj, and hence these indices should not be combined together.
The values of (i)-stability for all concepts are characterized by the presence of groups of values with high frequency, which facilitates selection of interesting concepts based on threshold values, while the distribution of (i; j; Xk)-stability does not give clearly de ned groups of interesting concepts.
We have also introduced the estimates of stability indices, which correlate both with the corresponding stability indices and some of stability estimates. This is due to the fact that the estimates of (i)-stability (or (i; j; Xk)-stability) are based on the elements from Kj Kk n Aj Ak (or Kk n Ak). Hence, the choice between stability and its estimates must be guided by the comparison of the sizes of sets involved in calculation, e.g. in the case of (i)-stability the number of subsets 2jAij, most probably, will be less then the number of elements in Kj Kk n Aj Ak.
The proposed indices characterize triconcepts di erently, in general they do not agree in the top-n selected concepts, which allow us to use either their combination to set up the strictest selection criteria, or to take some of them depending on the meaning behind a stability index.