2.4. Biclustering

For instance, given a matrix of shape (10, 10), one possible biclusterwith three rows and two columns induces a submatrix of shape (3, 2):

>>>

For visualization purposes, given a bicluster, the rows and columns ofthe data matrix may be rearranged to make the bicluster contiguous.

Algorithms differ in how they define biclusters. Some of thecommon types include:

• constant values, constant rows, or constant columns

• submatrices with low variance

• correlated rows or columns

Algorithms also differ in how rows and columns may be assigned tobiclusters, which leads to different bicluster structures. Blockdiagonal or checkerboard structures occur when rows and columns aredivided into partitions.

If each row and each column belongs to exactly one bicluster, thenrearranging the rows and columns of the data matrix reveals thebiclusters on the diagonal. Here is an example of this structurewhere biclusters have higher average values than the other rows andcolumns:

An example of biclusters formed by partitioning rows and columns.

In the checkerboard case, each row belongs to all column clusters, andeach column belongs to all row clusters. Here is an example of thisstructure where the variance of the values within each bicluster issmall:

An example of checkerboard biclusters.

After fitting a model, row and column cluster membership can be foundin the rows and columns attributes. is a binary vectorwith nonzero entries corresponding to rows that belong to biclusteri. Similarly, columns[i] indicates which columns belong tobicluster i.

Some models also have and columnlabels attributes.These models partition the rows and columns, such as in the blockdiagonal and checkerboard bicluster structures.

Note

Biclustering has many other names in different fields includingco-clustering, two-mode clustering, two-way clustering, blockclustering, coupled two-way clustering, etc. The names of somealgorithms, such as the Spectral Co-Clustering algorithm, reflectthese alternate names.

The SpectralCoclustering algorithm finds biclusters withvalues higher than those in the corresponding other rows and columns.Each row and each column belongs to exactly one bicluster, sorearranging the rows and columns to make partitions contiguous revealsthese high values along the diagonal:

Note

The algorithm treats the input data matrix as a bipartite graph: therows and columns of the matrix correspond to the two sets of vertices,and each entry corresponds to an edge between a row and a column. Thealgorithm approximates the normalized cut of this graph to find heavysubgraphs.

An approximate solution to the optimal normalized cut may be found viathe generalized eigenvalue decomposition of the Laplacian of thegraph. Usually this would mean working directly with the Laplacianmatrix. If the original data matrix

has shape, the Laplacian matrix for the corresponding bipartite graphhas shape. However, in this case it ispossible to work directly with, which is smaller and moreefficient.

is preprocessed as follows:

Where

is the diagonal matrix with entry equal to and is the diagonal matrix withentry equal to.

The singular value decomposition,

,provides the partitions of the rows and columns of. A subsetof the left singular vectors gives the row partitions, and a subsetof the right singular vectors gives the column partitions.

The

singular vectors, startingfrom the second, provide the desired partitioning information. Theyare used to form the matrix:

where the columns of

are, and similarly for.

Then the rows of

are clustered using k-means. The first n_rows labels provide the row partitioning,and the remaining n_columns labels provide the column partitioning.

Examples:

• : A simple exampleshowing how to generate a data matrix with biclusters and applythis method to it.

• Biclustering documents with the Spectral Co-clustering algorithm: An example of findingbiclusters in the twenty newsgroup dataset.

References:

• Dhillon, Inderjit S, 2001. .

The algorithm assumes that the inputdata matrix has a hidden checkerboard structure. The rows and columnsof a matrix with this structure may be partitioned so that the entriesof any bicluster in the Cartesian product of row clusters and columnclusters are approximately constant. For instance, if there are tworow partitions and three column partitions, each row will belong tothree biclusters, and each column will belong to two biclusters.

The algorithm partitions the rows and columns of a matrix so that acorresponding blockwise-constant checkerboard matrix provides a goodapproximation to the original matrix.

2.4.2.1. Mathematical formulation

The input matrix

is first normalized to make thecheckerboard pattern more obvious. There are three possible methods:

• Independent row and column normalization, as in SpectralCo-Clustering. This method makes the rows sum to a constant and thecolumns sum to a different constant.

• Log normalization: the log of the data matrix is computed:

. Then the column mean, row mean, and overall mean of are computed. The final matrix is computedaccording to the formula

After normalizing, the first few singular vectors are computed, justas in the Spectral Co-Clustering algorithm.

If log normalization was used, all the singular vectors aremeaningful. However, if independent normalization or bistochastizationwere used, the first singular vectors,

and.are discarded. From now on, the “first” singular vectors refers to and except in thecase of log normalization.

Given these singular vectors, they are ranked according to which canbe best approximated by a piecewise-constant vector. Theapproximations for each vector are found using one-dimensional k-meansand scored using the Euclidean distance. Some subset of the best leftand right singular vector are selected. Next, the data is projected tothis best subset of singular vectors and clustered.

For instance, if

singular vectors were calculated, the best are found as described, where. Let be the matrix with columns the best left singularvectors, and similarly for the right. To partition the rows,the rows of are projected to a dimensional space:. Treating the rows of thismatrix as samples and clustering using k-means yields the row labels.Similarly, projecting the columns to andclustering this matrix yields the column labels.

Examples:

• : a simple exampleshowing how to generate a checkerboard matrix and bicluster it.

References:

• Kluger, Yuval, et. al., 2003. Spectral biclustering of microarraydata: coclustering genes and conditions.

There are two ways of evaluating a biclustering result: internal andexternal. Internal measures, such as cluster stability, rely only onthe data and the result themselves. Currently there are no internalbicluster measures in scikit-learn. External measures refer to anexternal source of information, such as the true solution. Whenworking with real data the true solution is usually unknown, butbiclustering artificial data may be useful for evaluating algorithmsprecisely because the true solution is known.

To compare a set of found biclusters to the set of true biclusters,two similarity measures are needed: a similarity measure forindividual biclusters, and a way to combine these individualsimilarities into an overall score.

To compare individual biclusters, several measures have been used. Fornow, only the Jaccard index is implemented:

where

and are biclusters, isthe number of elements in their intersection. The Jaccard indexachieves its minimum of 0 when the biclusters to not overlap at alland its maximum of 1 when they are identical.

Several methods have been developed to compare two sets of biclusters.For now, only (Hochreiter et. al., 2010) isavailable:

• Compute bicluster similarities for pairs of biclusters, one in eachset, using the Jaccard index or a similar measure.

• Assign biclusters from one set to another in a one-to-one fashionto maximize the sum of their similarities. This step is performedusing the Hungarian algorithm.

• The final sum of similarities is divided by the size of the largerset.

The minimum consensus score, 0, occurs when all pairs of biclustersare totally dissimilar. The maximum score, 1, occurs when both setsare identical.