Mining Biclusters of Similar Values with Triadic Concept Analysis Mehdi Kaytoue1 , Sergei O. Kuznetsov2 , Juraj Macko3 , Wagner Meira Jr.1 and Amedeo Napoli4 1 Universidade Fereral de Minas Gerais – Belo Horizonte – Brazil 2 HSE – Pokrovskiy Bd. 11 – 109028 Moscow – Russia 3 Palacky University – 17. listopadu – 77146 Olomouc – Czech Republic 4 INRIA/LORIA – Campus Scientifique, B.P. 239 – Vandœuvre-lès-Nancy – France kaytoue@dcc.ufmg.br, kuznetsovs@yandex.ru, juraj.macko@upol.cz, meira@dcc.ufmg.br, napoli@loria.fr Abstract. Biclustering numerical data became a popular data-mining task in the beginning of 2000’s, especially for analysing gene expression data. A bicluster reflects a strong association between a subset of objects and a subset of attributes in a numerical object/attribute data-table. So called biclusters of similar values can be thought as maximal sub-tables with close values. Only few methods address a complete, correct and non redundant enumeration of such patterns, which is a well-known in- tractable problem, while no formal framework exists. In this paper, we introduce important links between biclustering and formal concept anal- ysis. More specifically, we originally show that Triadic Concept Analysis (TCA), provides a nice mathematical framework for biclustering. Inter- estingly, existing algorithms of TCA, that usually apply on binary data, can be used (directly or with slight modifications) after a preprocessing step for extracting maximal biclusters of similar values. Keywords: Triadic concept analysis, numerical biclustering, scaling 1 Introduction Numerical data biclustering mainly appeared in the beginning of 2000’s as a first answer to new challenges raised by biological data analysis, and especially gene expression data analysis [13]. Starting from an object/attribute numerical data-table (e.g. Table 1), the goal is to group together some objects with some attributes according to the values taken by these attributes for these objects [13]. Accordingly, a bicluster is formally defined as a pair composed of a set of ob- jects and a set of attributes. Such pair can be represented as a rectangle in the numerical table, modulo lines and columns permutations. Table 1 is a numerical dataset with objects in lines and attributes in columns, while each table entry corresponds to the value taken by the attribute in column for the object in line. Table 2 illustrates bicluster ({g1 , g2 , g3 }, {m1 , m2 , m3 }) as a grey rectangle. There are several types of biclusters in the literature (see [13] for a survey), depending on the relation between the values taken by their attributes for their objects. The most simple case can be understood as rectangles of equal val- ues: a bicluster corresponds to a set of objects whose values taken by a same set of attributes are exactly the same, e.g. ({g1 , g2 , g3 }, {m5 }). Constant bi- clusters only appear in idyllic situations: generally numerical data are noisy. Accordingly, a straightforward generalization of such biclusters lies in so called biclusters of similar values: they are represented by rectangles with almost iden- tical, say similar, values [13, 1, 7]. Table 2 illustrates a bicluster of similar values ({g1 , g2 , g3 }, {m1 , m2 , m3 }) where two values are said to be similar if their dif- ference is no more than 1. Moreover, this bicluster is maximal: neither an object nor an attribute can be added without violating the similarity condition. Only few methods address a complete, correct and non redundant enumer- ation of such patterns [1, 7], which is a well-known intractable problem [13], while no formal framework exists. In this paper, we show that Formal Concept Analysis (FCA) [3], and especially Triadic Concept Analysis (TCA) [12] pro- vides a suitable and well defined framework for this task: Basically, an object has an attribute under a condition (a value). After a simple scaling procedure (turning original data into binary), a bicluster is represented as a triadic con- cept, composed of a set of objects, a set of attributes (both characterizing the corresponding “rectangle”) and a set of values. All sets are maximal thanks to existing concept forming derivation operators of TCA. This comes with several advantages: – Two values w1 , w2 of the original data are said to be similar iff their difference does not exceed a given parameter θ. In this case, we write w1 'θ w2 ⇐⇒ |w1 − w2 | ≤ θ. Otherwise, we write w1 6'θ w2 . The trilattice produced with TCA after scaling gives all maximal biclusters of similar values for any θ ordered w.r.t. similarity of their values. – The well known notion of frequency takes a semantics w.r.t. similarity of values. For example, let (A, B, C) be a triconcept, where A is a set of objects, B a set of attributes, and C a set of similar values. Assume (A, B) to be the corresponding bicluster. The higher |C|, the more similar are the values of the bicluster. If all |A|, |B|, and |C| are high we obtain a bicluster represented as a large rectangle of close values. – Existing algorithms from TCA [4] and n-ary closed set mining [2] can be used directly after scaling. We also provide a new algorithm to compute biclusters maximal only for a given θ (see algorithm TriMax later on). – Both scaling procedure and algorithm TriMax computations can be directly distributed to several computing cores. – The method can be adapted to n-ary numerical datasets. For example, with n = 3, a n-cluster would be a maximal 3D-box of similar values. It can be applied to 3D gene expression data, monitoring the behaviour of genes in different samples over time. It follows that mining n-dimensional clusters can be achieved with n + 1-adic concept analysis. The paper is organized as follows. Firstly, preliminaries regarding TCA are presented in Section 2. Then Section 3 formally states the problem. It is followed by the description of our two methods, respectively in Section 4 and 5. The first shows how TCA can help characterizing all maximal biclusters for any θ, while the second restricts the problem to a user-given θ. This is followed by experiments on the proposed approaches. Finally, the paper ends with a discussion and perspectives of further research. Table 1: A numerical dataset Table 2: A bicluster of similar values m1 m2 m3 m4 m5 m1 m2 m3 m4 m5 g1 1 2 2 1 6 g1 1 2 2 1 6 g2 2 1 1 0 6 g2 2 1 1 0 6 g3 2 2 1 7 6 g3 2 2 1 7 6 g4 8 9 2 6 7 g4 8 9 2 6 7 2 Triadic Concept Analysis We assume that the reader is familiar with basic notions of Formal Concept Anal- ysis [3]. Lehmann and Wille introduced Triadic Concept Analysis (TCA [12]). Data are represented by a triadic context, given by (G, M, B, Y ). G, M , and B are respectively called sets of objects, attributes and conditions, and Y ⊆ G × M × B. The fact (g, m, b) ∈ Y is interpreted as the statement “Object g has the attribute m under condition b”. A (triadic) concept of (G, M, B, Y ) is a triple (A1 , A2 , A3 ) with A1 ⊆ G, A2 ⊆ M and A3 ⊆ B satisfying the two following statements: (i) A1 × A2 × A3 ⊆ Y , X1 × X2 × X3 ⊆ Y and (ii) A1 ⊆ X1 , A2 ⊆ X2 and A3 ⊆ X3 implies A1 = X1 , A2 = X2 and A3 = X3 . If (G, M, B, Y ) is represented by a three dimensional table, (i) means that a concept stands for a 3-dimensional rectangle full of crosses while (ii) characterises component-wise maximality of concepts. For a triadic concept (A1 , A2 , A3 ), A1 is called the extent, A2 the intent and A3 the modus. To describe the derivation operators, it is convenient to alternatively repre- sent a triadic context as (K1 , K2 , K3 , Y ). Then, for {i, j, k} = {1, 2, 3}, j < k, X ⊆ Ki and Z ⊆ Kj × Kk , (i)-derivation operators are defined by: Φ : X → X (i) : {(aj , ak ) ∈ Kj × Kk | (ai , aj , ak ) ∈ Y for all ai ∈ X} 0 Φ : Z → Z (i) : {ai ∈ Ki | (ai , aj , ak ) ∈ Y for all (aj , ak ) ∈ Z} This definition leads to derivation operator K(3) and dyadic context K(3) = hK3 , K1 × K2 , Y (3) i. Further derivation operators are defined as follows: for {i, j, k} = {1, 2, 3}, Xi ⊆ Ki , Xj ⊆ Kj and Ak ⊆ Kk , the (i, j, Ak )-derivation operators are defined by: (i,j,Ak ) Ψ : Xi → Xi : {aj ∈ Kj | (ai , aj , ak ) ∈ Y for all (ai , ak ) ∈ Xi × Ak } 0 (i,j,Ak ) Ψ : Xj → Xj : {ai ∈ Ki | (ai , aj , ak ) ∈ Y for all (aj , ak ) ∈ Xj × Ak } 0 Operators Φ and Φ will be called outer operators, pair of both operators outer 0 closure and dyadic operators Ψ and Ψ inner operators or inner closure when pair of both is used. Derivation operators of dyadic context are defined by Kij Ak = hKi , Kj , YAijk i, where (ai , aj ) ∈ YAijk iff ai , aj , ak are related by Y for all ak ∈ Ak . From a computational point of view, [4] developed the algorithm Trias for extracting frequent triadic concepts, i.e. whose extent, intent and modus cardi- nalities are higher than user-defined thresholds (see also [5]). Cerf et al. presented a more efficient algorithm called Data-peeler able to handle n-ary relations [2] while formal definitions lie in so called Polyadic Concept Analysis [14]. 3 Notations and problem settings A numerical dataset is realized by a many-valued context [3] and we define accordingly (maximal) biclusters of similar values. Definition 1 (Many-valued context). Let G be a set of objects, M be a set of attributes, W be the set of attribute values and I be a ternary relation defined on the Cartesian product G × M × W . The fact (g, m, w) ∈ I, also written m(g) = w, means that “Attribute m takes the value w for the object g”. The tuple (G, M, W, I) is called many-valued context, or simply numerical dataset in this paper. Example 1. Table 1 is a numerical dataset, or many-valued context, with objects G = {g1 , g2 , g3 , g4 }, attributes M = {m1 , m2 , m3 , m4 , m5 }, W = {0, 1, 2, 6, 7, 8, 9} and for example m5 (g2 ) = 6. Definition 2 (Bicluster). In a numerical dataset (G, M, W, I), a bicluster is a tuple (A, B) with A ⊆ G and B ⊆ M . Definition 3 (Similarity relation and bicluster of similar values). Let w1 , w2 ∈ W be two attribute values and θ ∈ N be a user-defined parameter, called similarity parameter. w1 and w2 are said to be similar iff |w1 − w2 | ≤ θ and we note w1 'θ w2 . (A, B) is bicluster of similar values if m(g) 'θ n(h) for all g, h ∈ A and for all m, n ∈ B. Definition 4 (Maximal bicluster of similar values). A bicluster of similar values (A, B) is maximal if adding either an object in A or an attribute in B does not result in a bicluster of similar values. Example 2 (From Table 1). ({g1 , g4 }, {m2 , m4 }) is a bicluster. ({g1 , g2 }, {m2 }) is a bicluster of similar values with θ ≥ 1. However, it is not maximal. With 1 ≤ θ < 5, ({g1 , g2 , g3 }, {m1 , m2 , m3 }) is maximal. Finally, with θ = 7 the biclus- ter ({g1 , g2 , g3 }, {m1 , m2 , m3 , m4 , m5 }) is maximal. Note that a constant (max- imal) bicluster is a (maximal) bicluster of similar values with θ = 0. Thus the problem that we address in this paper is the extraction of all max- imal biclusters of similar values from a numerical dataset. We desire the extrac- tion to be complete, correct and non-redundant compared to several existing methods of the literature based on heuristics [13]. For that matter, we pro- pose in the next section a first method aiming at extracting biclusters for any similarity parameter θ. This method establishes new links between biclustering and FCA in general, and TCA in particular. Then, the present methodology is adapted to characterize and extract biclusters that are maximal for a given θ only as usually done in the literature [1, 7, 13]. 4 Biclusters of similar values in Triadic Concept Analysis Firstly, we consider the problem of generating maximal biclusters for any θ. Starting from a numerical dataset (G, M, W, I), the basic idea lies in building a triadic context (G, M, T, Y ) where the two first dimensions remain formal objects and formal attributes, while W is scaled into a third dimension denoted by T . This new dimension T is called the scale dimension: intuitively, it gives different “spaces of values” that each object-attribute pair (g, m) ∈ G×M can take. Once the scale is given, a triadic context is derived from which triadic concepts are characterized. We use the interordinal scaling [3] to build the scale dimension. It allows to encode in 2T all possible intervals of values in W . This scale allows to derive a triadic context from which any bicluster of similar values can be characterized as a triadic concept. We made more precise these statements and illustrate the whole procedure with examples. Definition 5 (Interordinal Scaling). A scale is a binary relation J ⊆ W × T associating original elements from the set of values W to their derived ele- ments in T . In the case of interordinal scaling, T = {[min(W ), w], ∀w ∈ W } ∪ {[w, max(W )], ∀w ∈ W }. Then (w, t) ∈ J iff w ∈ t. Example 3. Table 3 gives the tabular representation of the interordinal scale for Table 1. Intuitively, each line describes a single value, while dyadic concepts represent all possible intervals over W . An example of dyadic concept in this table is given by ({6, 7, 8}, {t6 , t7 , t8 , t9 , t10 }), rewritten as ({6, 7, 8}, {[6, 8]}) since {t6 , t7 , t8 , t9 , t10 } represents the interval [0, 8] ∩ [0, 9] ∩ [1, 9] ∩ [2, 9] ∩ [6, 9] = [6, 8]. t10 = [6, 9] t11 = [7, 9] t12 = [8, 9] t13 = [9, 9] t1 = [0, 0] t2 = [0, 1] t3 = [0, 2] t4 = [0, 6] t5 = [0, 7] t6 = [0, 8] t7 = [0, 9] t8 = [1, 9] t9 = [2, 9] J 0 × × × × × × × 1 × × × × × × × 2 × × × × × × × 6 × × × × × × × 7 × × × × × × × 8 × × × × × × × 9 × × × × × × × Table 3: Interordinal scale of the set of attribute values W . Once the scale is defined, we can derive the triadic context w.r.t. this scale. Definition 6 (Triadic scaled context). Let Y be ternary relation Y ⊆ G × M ×T . Then (g, m, t) ∈ Y iff (m(g), t) ∈ J, or simply m(g) ∈ t. We call the tuple (G, M, T, Y ) the triadic scaled context of the numerical dataset (G, M, W, I). Example 4. The object-attribute pair (g1 , m1 ) taking value m1 (g1 ) = 1 is scaled into triples (g1 , m1 , t) ∈ Y where t takes any interval in {[0, 1], [0, 2], [0, 6], [0, 7], [0, 8], [0, 9], [1, 9]}. The intersection of intervals in this set is the original value itself, i.e. m1 (g1 ) = 1, a basic property of interordinal scaling. As a result, Table 4 illustrates the whole scaled triadic context derived from the numerical dataset given in Table 1 using interordinal scale. The very first cross (×) in this table (upper left) represents the tuple (g2 , m4 , t1 ), meaning that m4 (g2 ) ∈ [0, 0]. We present now our first main result: there is a one-to-one correspondence between (i) the set of maximal biclusters of similar values in a given numerical dataset for any similarity parameter θ and (ii) the set of all triadic concepts in the triadic context derived with interordinal scaling. Proposition 1. Tuple hA, B, U i, where A ⊆ G, B ⊆ G and U ⊆ T is triadic concept iff (A, B) is a maximal bicluster of similar values for some θ ≥ 0. Proof. We leave the proof in the Appendix of the paper since we need to intro- duce notations and propositions not necessary in the rest of the paper. Example 5. For example, ({g1 , g2 , g3 }, {m1 , m2 , m3 }, {t3 , t4 , t5 , t6 , t7 , t8 }) is a tri- adic concept from the context depicted in Table 4. It corresponds to the maximal bicluster ({g1 , g2 , g3 }, {m1 , m2 , m3 }) with θ = 1. θ = 1 since {t3 , t4 , t5 , t6 , t7 , t8 } is maximal (it is a modus), it corresponds to interval [1, 2] and naturally 2−1 = 1 is the length of this interval. t1 = [0, 0] t2 = [0, 1] t3 = [0, 2] t4 = [0, 6] t5 = [0, 7] m1 m2 m3 m4 m5 m1 m2 m3 m4 m5 m1 m2 m3 m4 m5 m1 m2 m3 m4 m5 m1 m2 m3 m4 m5 g1 × × × × × × × × × × × × × × × × g2 × × × × × × × × × × × × × × × × × × g3 × × × × × × × × × × × × × g4 × × × × × × t6 = [0, 8] t7 = [0, 9] t8 = [1, 9] t9 = [2, 9] t10 = [6, 9] m1 m2 m3 m4 m5 m1 m2 m3 m4 m5 m1 m2 m3 m4 m5 m1 m2 m3 m4 m5 m1 m2 m3 m4 m5 g1 × × × × × × × × × × × × × × × × × × × g2 × × × × × × × × × × × × × × × × × g3 × × × × × × × × × × × × × × × × × × × × × × g4 × × × × × × × × × × × × × × × × × × × × × × × t11 = [7, 9] t12 = [8, 9] t13 = [9, 9] m1 m2 m3 m4 m5 m1 m2 m3 m4 m5 m1 m2 m3 m4 m5 g1 g2 g3 × g4 × × × × × × Table 4: Triadic scaled context for Table 1 with interordinal scaling. Hence we showed that extracting biclusters of similar values for any θ in a numerical dataset can be achieved by (i) scaling the attribute value dimension and (ii) extracting the triadic concepts in the resulting derived triadic context. Interestingly, triadic concepts (A, B, U ) with the largest sets A, B or C rep- resent large biclusters of close values. Indeed, the larger |A| and |B| the larger the data covering of the corresponding bicluster. Furthermore, the larger |U |, the more similar values for bicluster (A, B). Indeed, by the properties of interordinal scaling, the more intervals in U , the smaller their interval intersection. Mining so called top-k frequent triadic concepts can accordingly be achieved with the existing algorithm Data-Peeler [2]. On another hand, extracting maximal biclusters for all θ may be neither efficient nor effective with large numerical data: their number tends to be very large and all biclusters are not relevant for a given analysis. Furthermore, both size and density of contexts derived with interordinal scaling are known to be problematic w.r.t algorithmic scalability, see e.g. [9]. In existing methods of the literature, θ is set a priori. We show now how to handle this case with slight modifications, our second main result. 5 Extracting biclusters of similar values for a given θ In this section we consider the problem of extracting maximal biclusters of sim- ilar values in TCA for a given θ only. It comes with slight modifications of the methodology presented in last section. Intuitively, consider the previous scaling applied on a numerical dataset (G, M, W, I). It scales W into dimension T and subsets of T characterize all intervals of values over W . To get maximal biclusters for a given θ only, we should not consider all possible intervals in W , but rather all intervals (i) having a range size that is less or equal than θ to avoid biclusters with non similar values, and (ii) having a range size the closest as possible to θ to avoid non-maximal biclusters. For example, if we set θ = 2, it is probably not interesting to consider interval [0, 8] in the scale dimension since 8 − 0 > θ. Similarly, considering the interval [6, 6] may not be interesting as well, since a bicluster with all its values equal to 6 may not be maximal. As introduced in [6], those maximal intervals of similar values used for the scale are called blocks of tolerance over the set of numbers W with respect to the tolerance relation 'θ . Therefore we firstly recall basics on tolerance relations over a set of numbers. It allows us to define a simpler scaling procedure. The resulting triadic context is then mined with a new TCA algorithm called TriMax to extract maximal biclusters of similar values for a given θ. Blocks of tolerance over W are defined as maximal sets of pairwise similar values from W : Definition 7 (Tolerance blocks from a set of numbers). The similarity relation 'θ is called a tolerance relation, i.e. reflexive, symmetric but not tran- sitive. Given a set W of values, a subset V ⊆ W , and a tolerance relation 'θ over W , V is a block of tolerance if: (i) ∀w1 , w2 ∈ V, w1 'θ w2 (pairwise similarity) (ii) ∀w1 6∈ V, ∃w2 ∈ V, w1 6'θ w2 (maximality). From Table 1 we have W = {0, 1, 2, 6, 7, 8, 9}. With θ = 2, one has 0 '2 2 but 2 6'2 6. Accordingly, one obtains 3 blocks of tolerance, namely the sets {0, 1, 2}, {6, 7, 8} and {7, 8, 9}. These three sets can be renamed as the convex hull of their elements on N: respectively, [0, 2], [6, 8] and [7, 9]: any number lying between the minimal and the maximal elements (w.r.t. natural number ordering) of a block of tolerance is naturally similar to any other element of the block. To derive a triadic context from a numerical dataset, we simply use tolerance blocks over W to define the scale dimension. Definition 8 (Trimax scale relation). The scale relation is a binary relation J ⊆ W × C, where C is the set of blocks of tolerance over W renamed as their convex hulls. Then, (w, c) ∈ J iff w ∈ c. Example 6. From Table 1 we have: C = {[0, 1], [1, 2], [6, 7], [7, 8], [8, 9]} with θ = 1, and C = {[0, 2], [6, 8], [7, 9]} with θ = 2. Then, we can apply the same context derivation as in previous section: scaling is still based on intervals, but this time it uses tolerance blocks. Definition 9 (TriMax triadic scaled context). Let Y ⊆ G × M × C be a ternary relation. Then (g, m, c) ∈ Y iff (m(g), c) ∈ J, or simply m(g) ∈ c, where J is the scale relation. (G, M, C, Y ) is called the TriMax triadic scaled context. Example 7. Table 5 is the Trimax triadic scaled concept derived from the nu- merical dataset lying in Table 1 with θ = 1. label 1 label 2 label 3 label 4 label 5 [0, 1] [1, 2] [6, 7] [7, 8] [8, 9] m1 m2 m3 m4 m5 m1 m2 m3 m4 m5 m1 m2 m3 m4 m5 m1 m2 m3 m4 m5 m1 m2 m3 m4 m5 g1 × × × × × × × g2 × × × × × × × g3 × × × × × × × g4 × × × × × × × Table 5: Triadic scaled context using tolerance blocks over W and θ = 1. Definition 10 (Dyadic context associated with a block of tolerance). Consider a block of tolerance c ∈ C. The dyadic context associated with this block is given by (G, M, Z) where z ∈ Z denotes all (g, m) ∈ G × M such as m(g) ∈ c. Example 8. In Table 5, each such dyadic context is labelled by its corresponding block of tolerance. Now, remark that blocks of tolerance over W are totally ordered: let [v1 , v2 ] and [w1 , w2 ] be two blocks of tolerance, one has [v1 , v2 ] < [w1 , w2 ] iff v1 < w1 . Hence, associated dyadic contexts are also totally ordered and we use a corre- sponding indexing set to label them. In Table 5, contexts for blocks h[0, 1], [1, 2], [6, 7], [7, 8], [8, 9]i are respectively labelled h1, 2, 3, 4, 5i. We now present our second main results: The scaled triadic context supports the extraction of maximal biclusters of similar values for a given θ. In this case however, existing algorithms of TCA cannot be applied directly. For example, in Table 5, the triconcept ({g3 }, {m4 }, {3, 4}) corresponds to a bicluster of similar values which is not maximal. Hence we present hereafter a new TCA algorithm for this task, called TriMax. The basic idea of TriMax relies on the following facts. Firstly, since each dyadic context corresponds to a block of tolerance, we do not need to compute intersections of contexts, such as classically done in TCA. Hence each dyadic context is processed separately. Secondly, a dyadic concept of a dyadic context necessarily represents a bicluster of similar values, but we cannot be sure it is maximal (see previous example). Hence, we need to check if a concept is still a concept in other dyadic contexts, corresponding to other classes of tolerance. This is made precise with the following proposition. Proposition 2. Let (A, B, U ) be a triadic concept from Trimax triadic scaled context (G, M, C, Y ), such that U is the outer closure of a singleton {c} ⊆ C. If |U | = 1, (A, B) is a maximal bicluster of similar values. Otherwise, (A, B) is a maximal bicluster of similar values iff @y ∈ [min(U ); max(U )], y < c s.t. 0 0 (A, B) 6= Ψy (Ψy ((A, B))), where Ψy (.) and Ψy (.) correspond to inner derivation operators associated with y th dyadic context. Proof. When |U | = 1, (A, B) is a dyadic concept only in one dyadic context corresponding to a block of tolerance. By properties of tolerance blocks, (A, B) is a maximal bicluster. If |U | 6= 1, (A, B) is a dyadic concept in |U | dyadic contexts. Since the tolerance block set is totally ordered, it directly implies that modus U is an interval [min(U ); max(U )]. Hence, if ∃y ∈ [min(U ); max(U )] s.t. 0 (A, B) = Ψy (Ψy ((A, B))) this means that (A, B) is not a maximal bicluster of similar values. Description of the TriMax algorithm. TriMax starts with scaling ini- tial numerical data into several dyadic contexts, each one standing for a block of tolerance over W with given θ. The set of all dyadic contexts forms accordingly a triadic context. Then, each dyadic context is mined with any FCA algorithm (or closed itemset mining algorithm), and all formal concepts are extracted. For 0 a given concept (A, B), we compute outer derivation Φ ((A, B)), i.e. to obtain the set of dyadic contexts labels in which the current dyadic concept holds. If it results in a singleton, this means that (A, B) is a concept for the current block of tolerance only, i.e. it is a maximal bicluster of similar values, and it has been, or will never be, generated twice. Otherwise, (A, B) is a concept in other con- texts, and can be generated accordingly several times (as much as the number of contexts in which it holds). Then, we only consider (A, B) if we are sure it is the last time it is computed. Finally, we need to check if current concept represents a maximal bicluster, i.e. there should not exist a context from the modus where (A, B) is not a dyadic concept. Proposition 3. TriMax outputs a (i) complete, (ii) correct and (iii) non re- dundant collection of all maximal biclusters of similar values for a given numer- ical dataset and similarity parameter θ. Proof. (i) and (ii) follow directly from Proposition 2. Statement (iii) is ensured by the second if condition of the algorithm: a dyadic concept (or equivalently bicluster) is considered iff it has been extracted in the last dyadic context in which it holds. Algorithm 1: TriMax input : Numerical dataset (G, M, W, I), tolerance parameter θ output: Maximal biclusters of similar values Let C = {[ai , bi ]} be the totally ordered set of all blocks over W for given θ. Indices i form an indexing set. forall the [ai , bi ] ∈ C do Build context (G, M, Zi ) such that (g, m) ∈ Zi ⇔ m(g) ∈ [ai , bi ] forall the (G, M, Zi ) do Use any FCA algorithm to extract all its concepts (A, B) forall the dyadic concepts (A, B) in the current context (G, M, Zi ) do 0 if |Φ ((A, B))| = 1 then print (A, B) 0 else if max(Φ ((A, B)) = i then 0 x ← min(Φ ((A, B)) 0 if @y ∈ [x, i[ s.t. (A, B) 6= Ψy (Ψy ((A, B))) then print (A, B) 6 Computer experiments In this section, we experiment with the algorithm TriMax and highlight various aspects of its practical complexity. Data. We explore a gene expression dataset of the species Laccaria bicolor avail- able at NCBI5 . More details on this dataset can be found in [9]. This gene expres- sion dataset monitors the behaviour of 11, 930 genes in 12 biological situations, reflecting various stages of Laccaria bicolor biological cycle. Attribute values in W vary between 0 and 60, 000. TriMax implementation. TriMax is written in C++. It uses the boost library 1.42 for data structures and the implementation of InClose from its authors6 for dyadic concepts extraction. At each iteration of the main loop, i.e. each tolerance block, the current scaled dyadic context is produced: We do not generated the whole triadic context which cannot fit into memory for large databases. It turns out that the modus computation for a given dyadic concept requires to compute scaling “on the fly”, i.e. when computing the set of dyadic contexts in which a current concept holds. The experiments were carried out on an Intel CPU 2.54 Ghz machine with 8 GB RAM running under Ubuntu 11.04. Experiment settings. The goal of the present experiments is not to give a qualitative evaluation of the present approach (say biological interpretation), but rather a quantitative evaluation. Indeed, the present work aims at showing 5 http://www.ncbi.nlm.nih.gov/geo/ as series GSE9784 6 http://sourceforge.net/projects/inclose/ (i) Numbers of patterns (Y-axis) (ii) Execution times in seconds (Y-axis) w.r.t. θ (X-axis) and |G| (Z-axis) w.r.t. θ (X-axis) and |G| (Z-axis) (iii) Numbers of blocks of tolerance (Y-axis) (iv) Density of triadic contexts (Y-axis) w.r.t. θ (X-axis) and |G| (Z-axis) w.r.t. θ (X-axis) and |G| (Z-axis) (v) Comparing the number of generated dyadic (vi) Repartition of execution time concepts w.r.t. the actual number of maximal w.r.t main steps of TriMax biclusters varying θ with |G| = 500 with θ = 33, 000 and |G| = 500 Fig. 1: Monitoring with different settings (i) the number of maximal biclusters, (ii) the execution times of TriMax, (iii) the number of tolerance blocks, (iv) the derived triadic context density, (v) the number of non-maximal biclusters generated as dyadic-concepts w.r.t. the number of maximal biclusters, and (vi) repartition of execution time in the TriMax algorithm. how an existing type of biclusters can be mined with Triadic Concept Analysis. For a qualitative evaluation, the reader may refer for example to [1, 9]. Accordingly, we designed the following experiments to monitor various as- pects of the TriMax algorithm. For most of the experiments, the dataset used is composed of an increasing number of objects and all attributes. The objects are chosen randomly once and for all so that the different experiment results can be compared. We also vary the parameter θ in the same way across all experiments. Then, we monitor the following aspects, as presented in Figure 1: i. Number of maximal biclusters of similar values ii. Execution time (in seconds) iii. Number of tolerance blocks iv. Density of the triadic context, where density is defined as d(G, M, C, Y ) = |Y |/(|G| × |M | × |C|). This information is important, since contexts with high density are known to be hard to process with FCA algorithms [11], and we use the InClose algorithm for dyadic contexts processing. v. Comparison between the number of non-maximal biclusters produced by TriMax (i.e. dyadic concepts that do not corresponds to maximal biclus- ters) with the number of maximal biclusters. vi. Execution time profiling of the main procedures of TriMax. This is achieved with the tool GNU GProf and gives us what parts of the algorithm are the most time consuming. Experiment results. Figure 1 presents the results of our experiments with different settings. In these settings, we vary the number of objects |G| and the parameter θ. A first observation arises from graph (i): the number of biclusters is the highest when θ ' 30, 000. A first explanation is that 30, 000 is the half of the maximal value of W and almost all multiples of 100 in [0; 60, 000] belongs to W . In graph (ii), execution time has the same behaviour as graph (i). These results can be understood by paying attention to the next graphs (iii) and (iv). In (iii) is monitored the number of tolerance blocks. The maximal number is reached when θ = 0, i.e. |C| = |W |. When θ = max(W ), we have |C| = 1. Now we observe in (iv) that the density follows a reverse behaviour: When θ = 0, the density tends towards 0%; when θ = max(W ), then density exactly equal 1%. Combining both graph (iii) and (iv), the worst cases happen when both density and tolerance bloc count are high. Another observation, which explains also the execution times, arises from graph (v). Here are compared the number of maximal biclusters and the number of non-maximal biclusters generated as dyadic concepts. Here again, worst case is reached when θ ' 30, 000. Looking at graph (vi), we learn that this is however not the major problem. The mostly consuming procedure of TriMax is the computation of the modus of a dyadic concept. The explanation is that we compute modus with “on the fly scaling”. Therefore, the bottleneck of our algorithm reveals itself to be the modus computation. In practical applications however, the analyst is not interested in all biclusters of similar values. Some constraints are generally defined, such as a minimal (resp. maximal) number of objects (resp. attributes) in a bicluster (A, B), or a minimal area |A| × |B|, etc. Interestingly, most of those constraints can be evaluated on a generated dyadic concept. Therefore, before computing the modus of such concept, we can check such properties and discard the concept if not respecting the constraints. Although not reflected in this paper, we tested how adding minimal (resp. maximal) size constraints on a bicluster affects both number of biclusters and execution times. The results are very interesting: for example with θ = 33, 000, |G| = 500, and minimal (resp. maximal) size for |A| set to 10 (resp. 40), TriMax produces only 5, 332 maximal biclusters in 2.1 seconds compared to 104, 226 maximal biclusters extracted in 16.130 seconds without any constraint. Finally, the most interesting aspect of TriMax is its direct distributed com- putation capacity. Indeed, each iteration, i.e. for each block of tolerance, can be achieved independently from the others. Furthermore, the core of TriMax consisting in extracting dyadic contexts can also be distributed, see e.g. [10]. A deeper investigation remains to be done in this case. Note that although the method description involves W as a set of natural numbers, TriMax can directly handle numerical data real numbers, and has been implemented as such. Comparison with existing methods. Two existing methods in the literature also consider the problem of extracting all maximal biclusters of similar values from a numerical dataset. The first method is called Numerical Biset Miner (NBS-Miner [1]). The second method is based on interval pattern structures (IPS [7, 8]). Limited by space, we do not detail these methods. Both NBS-Miner and IPS algorithms have been implemented in C++. First experiments show that NBS-Miner is not scalable compared to IPS and TriMax. On another hand, it seems that TriMax outperforms IPS, but a deeper investigation is required. The main problem in IPS is to find an efficient algorithm able to compute tolerance blocks over a set of intervals. 7 Conclusion We addressed the problem of biclustering numerical data with Formal Concept Analysis. So called (maximal) biclusters of similar values can be characterized and extracted with Triadic Concept Analysis, which turns out to be a novel mathematical framework for this task. We properly defined a scaling procedure turning original numerical data into triadic contexts from which biclusters can be extracted as triadic concepts with existing algorithms. This approach allows a correct, complete and non-redundant extraction of all maximal biclusters, for any similarity parameter θ and can be extended to n-ary numerical datasets while their computation can be directly distributed. The interpretation of triadic con- cepts is very rich: both extent and intent allow to characterize a bicluster (i.e. the rectangle), while the modus gives the range of values of the biclusters, and for which θ is the bicluster maximal. Moreover, the larger the modus, the more simi- lar the values within current bicluster. It follows a perspective of research, aiming at extracting the top-k frequent tri-concepts with Data-Peeler [2], which can help to handle the problem of top-k biclusters extraction. We also adapted the TCA machinery with algorithm TriMax to extract maximal biclusters for a user-defined θ, which is classical in the existing literature. It appears that Tri- Max is a fully customizable algorithm: any concept extraction algorithm can be used inside its core (along with several constraints on produced dyadic concepts), while its distributed computation is direct. Among several other experiments, it remains now to determine which are the best core algorithms for a given θ parameter, the very last directly influencing derived contexts density. Acknowledgements. Authors would like to thank Dmitry Andreevich Morozov for implementing the algorithms NBS-Miner and IPS. The second author was supported by the project of the Russian Foundation for Basic Research, grant no. 08-07-92497-NTsNIL a. Juraj Macko acknowledges support by Grant No. 202/10/0262 of the Czech Science Foundation. A Proof of the Proposition 1. Before proving this proposition, we need to introduce the following. For sake of simplicity, we now consider W as the set of all natural numbers from a numerical dataset that are greater or equal than the minimal value and lower or equal than the maximal value, i.e. W = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} with the example of Table 1. Definition 11 (Scale value and scale relation). We call scale value s = q − r where r = min(W ) and q = max(W ). The scale relation is a binary relation J ⊆ W × T , where T = {t1 , . . . , t2s+1 } r ≤ w ≤ q and hw, ti i ∈ J iff i ∈ [w − r + 1, w − r + 1 + s]. Note that J is equivalent to interordinal scale of W previously given, but this notations are used for the proof. Definition 12 (Eθw - cluster base). We introduce Eθw ⊆ T defined as Eθw = [tw+θ−r+1 ; tw−r+1+s ] for given θ and w ∈ W . Example 9 (Eθw - cluster base). E12 = [t2+1−0+1 ; t2−0+1+9 ] = [t4 ; t12 ]. Proposition 4. (wb = m(g)) 'θ (n(h) = wc ) iff (hg, mi ∈ YE12θb and hh, ni ∈ YE12θb ). Proof. Let Eb , Ec ⊆ T and wc ≥ wb . According to the definition (g, m) ∈ YE12θb iff m, g, t are related by Y for all t ∈ Eθb . Using scaling and definition we have [twb −r+1 ; twb −r+1+s ] = Eb ⊇ Eθb = [twb +θ−r+1 ; twb −r+1+s ] which is straight- forward. We just need to show that (h, n) ∈ YE12θb holds as well. With scaling definition and previous definition we get [twc −r+1 ; twc −r+1+s ] = Ec ⊇ Eθb = [twb +θ−r+1 ; twb −r+1+s ] holding iff wc − wb ≤ θ, which is equal to the definition of 'θ . Moreover we can easily see as a corollary that wc −wb ≤ θ holds iff Eb ∩Ec ⊇ Eθb and wc − wb = θ holds iff Eb ∩ Ec = Eθb . Now we can prove the Proposition 1 from the main text. Proposition 1. Tuple hA1 , A2 , U i, where A1 ⊆ G, A2 ⊆ M and U ⊆ T is triadic concept iff (A1 , A2 ) is a maximal bicluster of similar values for some θ ≥ 0. Furthermore the value of θ is defined as θ = s − |U | + 1. Proof. Let U = Eθb and consider dyadic context YU12 = YE12θb for some wb . Using 0 dyadic closure operator Ψ (Ψ ((A1 )) we get (A1 , A2 ). From definition of triconcept we know that A1 ⊆ B1 implies A1 = B1 (the same for A2 ). From definition of maximal bicluster of similar values we know that hA1 , A2 i is maximal when it does not exists hB1 , B2 i s.t. B1 ⊇ A1 (the same applies for A2 ). It is obvious that both sets are maximal from definition and when we have the same dyadic context YU12 = YE12θb . Now we need to look at dyadic context YU12 = YE12θb . In |U | = |Eθb | = |[twb +θ−r+1 ; twb −r+1+s ]| we can easily see that |U | = s − θ + 1, which gives θ = s − |U | + 1. Finally, U is maximal (as being modus of a triconcept) and Eθb is maximal as well because wc − wb ≤ θ holds iff Eb ∩ Ec ⊇ Eθb . All facts mentioned in this proof leads to equality of the triconcept and maximal bicluster of similar values. References 1. Besson, J., Robardet, C., Raedt, L.D., Boulicaut, J.F.: Mining bi-sets in numerical data. In: Dzeroski, S., Struyf, J. (eds.) KDID. Lecture Notes in Computer Science, vol. 4747, pp. 11–23. Springer (2007) 2. Cerf, L., Besson, J., Robardet, C., Boulicaut, J.F.: Closed patterns meet n-ary relations. TKDD 3(1) (2009) 3. Ganter, B., Wille, R.: Formal Concept Analysis. Springer (1999) 4. Jäschke, R., Hotho, A., Schmitz, C., Ganter, B., Stumme, G.: Trias - an algorithm for mining iceberg tri-lattices. In: ICDM. pp. 907–911 (2006) 5. Ji, L., Tan, K.L., Tung, A.K.H.: Mining frequent closed cubes in 3d datasets. In: Proceedings of the 32nd International Conference on Very Large Data Bases (VLDB). pp. 811–822. ACM (2006) 6. Kaytoue, M., Assaghir, Z., Napoli, A., Kuznetsov, S.O.: Embedding tolerance re- lations in formal concept analysis: an application in information fusion. In: CIKM. pp. 1689–1692. ACM (2010) 7. Kaytoue, M., Kuznetsov, S.O., Napoli, A.: Biclustering numerical data in formal concept analysis. In: Valtchev, P., Jäschke, R. (eds.) ICFCA. LNCS, vol. 6628, pp. 135–150. Springer (2011) 8. Kaytoue, M., Kuznetsov, S.O., Napoli, A.: Revisiting numerical pattern mining with formal concept analysis. In: Proceedings of the 22nd International Joint Con- ference on Artificial Intelligence (IJCAI). IJCAI/AAAI (2011) 9. Kaytoue, M., Kuznetsov, S.O., Napoli, A., Duplessis, S.: Mining gene expression data with pattern structures in formal concept analysis. Inf. Sci. 181(10), 1989– 2001 (2011) 10. Krajca, P., Vychodil, V.: Distributed algorithm for computing formal concepts using map-reduce framework. In: IDA. pp. 333–344. Springer (2009) 11. Kuznetsov, S.O., Obiedkov, S.A.: Comparing performance of algorithms for gen- erating concept lattices. J. Exp. Theor. Artif. Intell. 14(2-3), 189–216 (2002) 12. Lehmann, F., Wille, R.: A triadic approach to formal concept analysis. In: ICCS. LNCS, vol. 954, pp. 32–43. Springer (1995) 13. Madeira, S., Oliveira, A.: Biclustering algorithms for biological data analysis: a survey. IEEE/ACM Transactions on Computational Biology and Bioinformatics 1(1), 24–45 (2004) 14. Voutsadakis, G.: Polyadic concept analysis. Order 19(3), 295–304 (2002)