Bicluster Analysis for Coherent Pattern Discovery

Background

The goal of biclustering is to find sub-matrices in the dataset, i.e. subsets of objects and subsets of attributes, where the subset of objects exhibits significant homogeneity within the subset of attributes. Figure 1 shows the fundamental difference between clustering and biclustering. Unlike clusters in row-wise or column-wise clustering, biclusters can overlap. In principle, the subsets of attributes for various biclusters can be different. Two biclusters can share some common objects and attributes, and some objects may not belong to any bicluster at all. Due to this flexibility, biclustering has attracted intense interests in the scientific community as a data exploration tool in many fields, ranging from bioinformatics to text mining and marketing.

Figure 1.

Conceptual difference between cluster analysis (left) and bicluster analysis (right). Different shade of grey denotes different clusters/biclusters, except for the right where it can denote overlapping region of two biclusters.

Model Of Bicluster Patterns

Let a dataset of M objects and N attributes be represented by a rectangular matrix D of M rows and N columns. A bicluster is a subset of rows that exhibit similar behaviors across a subset of columns and vice versa. The bicluster B=(X, Y), therefore, appears as a sub-matrix of D, where the set of row indices X and column indices Y are subsets of M and N, respectively. Biclustering aims to discover a set of biclusters B_k = (X_k, Y_k) such that each bicluster satisfies some notion of homogeneity.