Bicluster enumeration using Formal Concept Analysis

Abstract

In this work we introduce a novel technique to enumerate constant row/column value biclusters using formal concept analysis. To achieve this, a numerical data-table (standard input for biclustering algorithms) is modelled as a many-valued context where rows represent objects and columns represent attributes. Using equivalence relations dened for each single column, we are able to translate the bicluster mining problem in terms of the partition pattern structure framework. We show how biclustering can bene t from the FCA framework through its robust theoretical description and e cient algorithms. Finally, we show how this technique is able to nd high quality biclusters (in terms of the mean squared error) more e ciently than a state-of-the-art bicluster algorithm.

Introduction

Biclustering has become a fundamental tool for bioinformatics and gene expression analysis [ 4 ]. Di erent from standard clustering where objects are compared and grouped together based on their full descriptions, biclustering generates groups of objects based on a subset of their attributes, values or conditions. Thus biclusters are able to represent object relations in a local scale instead of the global representation given by an object cluster [ 12 ]. In this sense, biclustering has many elements in common with Formal Concept Analysis (FCA) [ 6 ]. In FCA objects are grouped together by the attributes they share in what is called a formal concept. Furthermore, formal concepts are arranged in a hierarchical and overlapping structure denominated a concept lattice. Hence a formal concept can be considered as a bicluster of objects and attributes representing relations in a local scale, while the lattice structure gives a description in the global scale. FCA is not only analogous to biclustering, but has much to o er in terms of mining techniques and algorithms [ 10 ]. The concept lattice can also provide biclusters with an overlapping hierarchy which has been reported as an important feature for bicluster analysis [ 15 ]. Recently, some approaches considering the use of FCA algorithms to mine biclusters from a numerical data-table have been introduced showing good potential [ 8, 7 ]. In this work, we present a novel technique for lattice-based biclustering using the pattern structure framework [ 5 ], an extension of FCA to deal with complex data. More speci cally, we propose a technique for mining biclusters with similar row/column values, a specialization of biclustering focused on mining attributes with coherent variations, i.e. the di erence between two attributes is the same for a group of objects [ 12 ]. We show that, by the use of partition pattern structures [ 1 ], we can nd high quality maximal biclusters (w.r.t. the mean squared error). Finally, we compare our approach with a standard constant row value algorithm [ 3 ], showing the capabilities and limitations of our approach.

The remainder of this paper is organized as follows. The basics of biclustering are introduced in Section 2. Section 3 presents our approach and Section 4 presents the experiments and initial ndings of our biclustering technique. Finally, Section 5 concludes our article and presents some new perspectives of research. 2

Biclustering de nitions

A numerical data-table is a matrix M where Mij indicates the value of an object gi 2 G w.r.t. the attribute mj 2 M with i 2 [1::jGj] and j 2 [1::jMj] (j j represents set cardinality). A bicluster of M is a submatrix B where each value Bij satis es a given restriction. According to [ 4, 12 ], there are ve di erent restrictions which we summarize in Table 1.

Constant values

Bij = c Constant row val- Bij=c + i ues Constant column Bij=c + j values Coherent values

Bij= c + i + j Coherent evolution

Within the submatrix, all values are equal to a constant c 2 R (R indicates real values).

Within the submatrix, all the values in a given row i are equal to a constant c and a row adjustment i 2 R.

Within the submatrix, all the values in a given column j are equal to a constant c and a column adjustment j 2 R.

Within the submatrix, all the values in a given column j are equal to a constant c, a row adjustment i and a column adjustment j. Instead of addition, the model can also consider multiplicative factors.

Values in the submatrix induce a linear order.

Similar values instead of constant values When noise is present in a datatable, it is di cult to search for constant values. Several approaches have tackled this issue in di erent ways, e.g. by the use of evaluation functions [ 14 ], equivalence relations [ 2, 13 ] and tolerance relations [ 7 ]. The most common way is establishing a threshold 2 R to enable the similarity comparison of two di erent values w1; w2 2 R. We say that w1 ' w2 (values are similar) i jw1 w2j . Thus, constant values are a special case of similar values when = 0. Using this, we can rede ne the rst three types of biclusters as follows: 1. Similar values: Bij ' Bkl. 2. Similar row/column values: (a) Similar row values: Bij ' Bil. (b) Similar column values: Bij '

Bkj .

Example 1. With = 1, Table 2 shows in its upper left corner a bicluster with similar values (dark grey). The upper right corner represents a similar column bicluster (light grey). Lower left corner considering fg3; g4g and fm1; m2g (not marked in the table) represents a similar row bicluster. The pattern structure framework is an extension of FCA proposed to deal with complex data [ 5 ]. Partition pattern structures are an instance of the pattern structure framework proposed to mine functional dependencies among attributes of a database [ 1 ] dealing with set partitions. In the following, we provide the speci cs of partition pattern structures where the main de nitions are given in [ 5 ].

Let G be a set of objects, M a set of attributes and M a data-table of numerical values where Mij contains the value of attribute (column) mj 2 M in object (row) gi 2 G. A partition d = fpig of the set G can be formalized as a collection of components pi such as: [ pi = G pi2d

pi \ pj = ; ; (pi; pj 2 d; i 6= j)

Two partitions can be ordered by the coarser- ner relation where we say that a partition d1 = fpig is a re nement of d2 = fpj g (or d2 is a coarsening of d1) i 8 pi 2 d1; 9 pj 2 d2; pi pj . We denote this as d1 v d2 where d1; d2 2 D is the space of all partitions of the set G.

Let us de ne the mapping function : M ! D, which assigns to each attribute in M the partition it generates over the set of objects G, as follows: (mj ) = f[gi]mj j gi 2 Gg [gi]mj = fgk 2 G j Mij = Mkj g

Where [gi]mj is the equivalence class of gi w.r.t. attribute mj , i.e. the set of rows in data-table M which have the same value in column mj as row gi. Since the set of equivalence classes for a given attribute generates a partition over G, it comes naturally that (mj ) 2 D for any mj 2 M.

It is easy to show that the order in the space of object partitions D de nes a complete lattice for which the similarity operator u for any two partitions d1; d2 2 D is de ned as follows: (1) (2) (3) (4) (5) (6) d1 u d2 = [ pi \ pj d1 v d2 () d1 u d2 = d1

B = l (m)

m2B d

= fm 2 M j d v (m)g

Then, a partition pattern structure is determined by the triple (M; (D; u); ) in which the following derivation operators for B M and d 2 D are de ned:

Similarly to standard FCA, we have that (B; d) is a partition pattern concept (pp-concept) when B = d and d = B and that for two pp-concepts (B1; d1) and (B2; d2), the order between them is given by (B1; d1) (B2; d2) () (B1 B2) or (d2 v d1). Pp-concepts determines biclusters as pairs (p; B) where p is a component of the partition pattern d . It should be noticed that to keep consistency with previous notation, we write biclusters as pairs (p; B) (p represent rows and B represent columns), while pp-concepts are written inversely (B; d) (B is the extent and d is the intent of (B; d)).

Proposition 1. Let (B; d) be a pp-concept, then for any partition component p 2 d each pair (p; B) corresponds to a constant column value bicluster.

The proof of this proposition is straightforward considering that each pair (p; B) represents a submatrix the columns of which were selected using an equivalence relation, i.e. the values in the columns are the same.

We say that a bicluster (p; B) is maximal i adding an object to p or an attribute to B does not result in a bicluster, i.e. (p [ fgg; B) and (p; B [ f g m ) are not biclusters. While pp-concepts are maximal (closed under ( ) ), biclusters corresponding to pairs (p; B) are not always maximal. This is due to the fact that pp-concepts are maximal w.r.t. the partitions and not w.r.t. the individual components of those partitions. Nevertheless, maximal biclusters are still easy to identify.

Proposition 2. Let (B1; d1); (B2; d2) be two pp-concepts such as (B1; d1) (B2; d2). Let p G be a component of a partition. If p 2 d1 and p 2= d2 then the bicluster corresponding to (p; B1) is maximal.

Proof. Given de nitions in Equations 2, 5 and 6, we have that for (B1; d1) and for any gi 2 p, the following is true: p = \ mj2B1 fgk 2 G j Mij = Mkj g (7) Consequently, for any other object gh 2 G, such as gh 2= p, we have Mij 6= Mhj . Hence, the pair (p + fghg; B) cannot be a bicluster.

Let B2 = B1 + fmj g for any mj 2 M, we show that (p; B2) cannot be a cluster by contradiction. Let (p; B2) be a bicluster. Then, there exists the pp-concept (B2; B2 ) such as p 2 B2 . If it does, then it is necessarily a direct super concept of (B1; d1). However, this contradicts the de nition p 2= B2 .

Supporting similar values: In general, it is not possible to support similar value biclusters as described in Section 2 using the partition pattern structures framework. This is due to the fact that the restriction Bij ' Bkl () jBij Bklj is not transitive and hence, it is not an equivalence but a tolerance relation [ 10 ] which do not necessarily generates partitions over the set of objects. However, the setting to support this scenario is only slightly different from the partition pattern structures framework. We do not provide its description for the sake of simplicity.

Nevertheless, through the use of interval of values we can get a close representation of similar value biclusters considering that two rows (objects) are in the same equivalence class if their values in a given column (attribute) is within a given interval (rather than being equal as described in Equation 2). For example, consider in Table 2 the intervals [0; 1] and [6; 7] for attribute m4. We can see that it generates the partition fg1; g2g; fg3; g4g. We call these intervals \equivalence blocks", similarly as the \tolerance blocks" described in [ 10 ]. Equivalence blocks can be either pre-de ned, allowing the user to include some background knowledge in the biclustering process, or calculated on-the- y if a number of equivalence blocks is speci ed. 4 4.1

Experiments

Partition pattern concept lattice calculation

In order to calculate the partition pattern concept lattice for a given data-table we used the AddIntent algorithm as described in [ 16 ]. We applied AddIntent over a subset of the dataset called MovieLens 100k1 of movie ratings containing 943 users and 50 movies (out of a total of 1682) using the prede ned set of equivalence blocks [1; 2][3; 3][4; 5]. The dataset contains user ratings for movies 1 http://grouplens.org/datasets/movielens/ which range from 1 to 5. When information is not available, the matrix contains 0 which we disregard (we do not mine biclusters with columns equal to 0). The dataset contained 16532 similar column biclusters.

Empirical results showed that less than 20% of the pp-concepts within the pp-lattice actually hold a maximal bicluster. In order to improve the e ciency of AddIntent for biclustering purposes we have included a pruning step between a certain number of AddIntent iterations (each time a new intent is added to the lattice). The pruning step consists of removing from the lattice any concept that do not hold a maximal bicluster. Figure 1 shows experimental results in this regard. The graphic shows the execution time (y axis) taken by AddIntent to calculate the 16532 biclusters when a pruning step was included in a given number of iterations (x axis). The solid horizontal line represents the execution time without pruning (30.5 seconds). While initially, the execution time doubles the non-optimized version (for a lattice prune each AddIntent iteration), later the time quickly stabilizes around half the time the non-optimized version. Best time is found for 40 iterations (15 seconds).

The pruning a ects the number of intent intersections performed by AddIntent. When the lattice is pruned, there are not as many intents to intersect as there were originally. However, pruning the lattice is an expensive task and adds overhead to the algorithm. The correct balance of this trade-o leads to dramatic improvements in the performance (twice in the experiments), however further experimentation in di erent numerical data-tables are needed to draw more conclusions regarding its setting. 4.2

Biclusters quality

A second experiment was performed over an example dataset provided with the system BicAt2 containing 419 objects and 70 attributes. We measure the performance of our approach mining similar row biclusters compared with Cheng and Church's algorithm (CC) [ 3 ]. CC tries to nd a determined number of biclusters 2 http://www.tik.ee.ethz.ch/sop/bicat/ with a maximum threshold for the mean squared error . Results are shown in Table 4. Parameters for pp-lattice are number of equivalence blocks and minimal number of columns in the cluster . CC was executed as provided by BicAt and other parameters were left as system's default.

PPL PPL PPL PPL PPL CC CC CC

Results show a general better performance of our approach which is able to mine more than four million maximal biclusters from the dataset in less time than CC calculates only ten thousands. In terms of minimal squared error (MSE), our approach gets smaller scores which induces better quality biclusters. CC is able to nd larger biclusters compared to our approach given the topdown strategy which implements. While larger biclusters can be found with our approach by decreasing the number of equivalent classes ( ), this is done at the cost of increasing the MSE as shown in Table 4. Compared to CC, our approach is better on nding many high quality and rather small biclusters inducing specialized associations among objects. CC is better at creating a global map of the entire data-table by nding larger biclusters. 5

Conclusions and research perspectives

In this work we have presented a novel technique for exhaustive similar row/column value biclustering based on FCA algorithms using partition pattern structures. We have shown the capabilities of the technique which is able to nd a large number of high quality biclusters. Furthermore, biclusters are provided with an overlapping hierarchy based on a concept lattice structure. How to leverage current biclusters analysis techniques using the concept lattice is still a matter of research.

Partition pattern structures were initially proposed for functional dependencies mining [ 1 ] using association rules from pp-concepts. How these techniques may bene t from the current approach and the opposite, is an interesting subject which should be explored. Using other techniques of formal concept selection and ltering, and their associations with biclusters is another compelling aspect for a future work.

References

1. Jaume Baixeries , Mehdi Kaytoue, and Amedeo Napoli, ` Characterizing functional dependencies in formal concept analysis with pattern structures' , Annals of Mathematics and Arti cial Intelligence , ( 2014 ).

2. Jeremy Besson , Celine Robardet, Luc Raedt, and Jean-Francois Boulicaut , ` Mining bi-sets in numerical data' , in Knowledge Discovery in Inductive Databases , ( 2007 ).

3. Yizong Cheng and George M. Church , ` Biclustering of expression data' , in Proceedings of the Eighth International Conference on Intelligent Systems for Molecular Biology , ( 2000 ).

4. Adelaide Valente Freitas , Wassim Ayadi, Mourad Elloumi, Joseluis Oliveira, Joseluis Oliveira, and Jin-Kao Hao , Survey on Biclustering of Gene Expression Data , 2013 .

5. Bernhard Ganter and Sergei O. Kuznetsov , ` Pattern Structures and their projections', Conceptual Structures: Broadening the Base, ( 2001 ).

6. Bernhard Ganter and Rudolf Wille , Formal Concept Analysis, mathematic edn ., 1999 .

7. Mehdi Kaytoue , Sergei O. Kuznetsov , Juraj Macko, and Amedeo Napoli, ` Biclustering meets triadic concept analysis' , Annals of Mathematics and Arti cial Intelligence , ( 2013 ).

8. Mehdi Kaytoue , Sergei O. Kuznetsov , and Amedeo Napoli, ` Biclustering numerical data in formal concept analysis' , in Formal Concept Analysis , ( 2011 ).

9. Mehdi Kaytoue , Sergei O. Kuznetsov , and Amedeo Napoli, ` Revisiting numerical pattern mining with formal concept analysis' , Proceedings of the Twenty-Second international joint conference on Arti cial Intelligence , ( November 2011 ).

10. Sergei O. Kuznetsov , ` Galois connections in data analysis: Contributions from the soviet era and modern russian research', in Formal Concept Analysis , volume 3626 of Lecture Notes in Computer Science, ( 2005 ).

11. Sergei O Kuznetsov and Sergei Obiedkov , ` Comparing Performance of Algorithms for Generating Concept Lattices' , Journal of Experimental and Theoretical Arti - cial Intelligence , ( 2002 ).

12. Sara C. Madeira and Arlindo L. Oliveira , ` Biclustering algorithms for biological data analysis: A survey' , IEEE/ACM Trans. Comput. Biol. Bioinformatics , ( January 2004 ).

13. Sadaaki Miyamoto , ` Lattice-valued hierarchical clustering for analyzing information systems' , in Rough Sets and Current Trends in Computing , volume 4259 of Lecture Notes in Computer Science, ( 2006 ).

14. Gaurav Pandey , Gowtham Atluri, Michael Steinbach, Chad L. Myers , and Vipin Kumar, ` An association analysis approach to biclustering' , in Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining , ( 2009 ).

15. Gianvito Pio , Michelangelo Ceci, Corrado Loglisci, Domenica D'Elia , and Donato Malerba, ` A novel biclustering algorithm for the discovery of meaningful biological correlations between mirnas and mrnas' , EMBnet.journal, 18(A) , (2012 ).

16. Dean van der Merwe , Sergei Obiedkov, and Derrick Kourie, ` Addintent: A new incremental algorithm for constructing concept lattices' , in Concept Lattices, ( 2004 ).