Query-based Biclustering using Formal Concept Analysis

Biclustering methods have proven to be critical tools in the ex-ploratory analysis of high-dimensional data including information networks, microarray experiments, and bag of words data. How-ever, most biclustering methods fail to answer specific questions of interest and do not incorporate prior knowledge and expertise from the user. To this end, query-based biclustering algorithms that are recently developed in the context of microarray data utilize a set of seed genes provided by the user which are assumed to be tightly co-expressed or functionally related to prune the search space and guide the biclustering algorithm. In this paper, a novel Query-Based Bi-Clustering algorithm, QBBC, is proposed by a new for-mulation that combines the advantages of low-variance biclustering techniques and Formal Concept Analysis. We prove that statistical dispersion measures that are order-preserving induce an ordering on the set of biclusters in the data. In turn, this ordering is exploited to form query-based biclusters in an efficient manner. Our novel ap-proach provides a mechanism to generalize query-based bicluster-ing to sparse high-dimensional data such as information networks and bag of words. Moreover, the proposed framework performs a local approach to query-based biclustering as opposed to the global approaches that previous algorithms have employed. Experimental results indicate that this local approach often produces higher qual-ity and precise biclusters compared to the state-of-the-art query-based methods. In addition, our results on the performance eval-uation illustrate the efficiency and scalability of QBBC compared to full biclustering approaches and other existing query-based ap-proaches