Biclustering

• Simulaneously cluster the rows & columns of a matrix into "biclusters". Each defines a submatrix with some desired properties.
• Common bicluster definitions include:
  • constant values
  • unusually high/low values
  • low-variance submatrices
  • correlated rows/columns

# given matrix (10,10)
# example bicluster w/ 3 rows, 2 cols
import numpy as np
data = np.arange(100).reshape(10, 10)
rows = np.array([0, 2, 3])[:, np.newaxis]
columns = np.array([1, 2])
data[rows, columns]

array([[ 1,  2],
       [21, 22],
       [31, 32]])

Spectral Co-Clustering

• Finds biclusters with values higher than those in corresponding other rows & columns.
• Each row & column belongs to only one bicluster.
• Arranging the rows & columns create contiguous partitions reveals the high values along the diagonal.
• Algorithm treats input data as a bipartite graph (rows & cols represent two sets of vertices; each entry is an edge between a row & column. It approximates a normalized cut of the graph to find subgraphs.

Example

• uses make_biclusters to build a matrix of small values, then implant large-valued biclusters.
• The rows & columns are shuffled & passed to Spectral CoClustering algorithm.
• Rearranging the shuffled matrix should reveal the contiguous biclusters.

import numpy as np
from matplotlib import pyplot as plt
from sklearn.datasets import make_biclusters
from sklearn.cluster import SpectralCoclustering as SC
from sklearn.metrics import consensus_score as CS

data, rows, columns = make_biclusters(
    shape=(300, 300), n_clusters=5, noise=5,
    shuffle=False, random_state=0)

plt.matshow(data, cmap=plt.cm.Blues)
plt.title("Original dataset")

Text(0.5, 1.0, 'Original dataset')

rng = np.random.RandomState(0)
row_idx = rng.permutation(data.shape[0])
col_idx = rng.permutation(data.shape[1])
data = data[row_idx][:, col_idx]

plt.matshow(data, cmap=plt.cm.Blues)
plt.title("Shuffled dataset")

Text(0.5, 1.0, 'Shuffled dataset')

model = SC(n_clusters=5, random_state=0)
model.fit(data)
score = CS(model.biclusters_,
           (rows[:,    row_idx], 
            columns[:, col_idx]))

print("consensus score: {:.3f}".format(score))

fit_data =     data[   np.argsort(model.row_labels_   )]
fit_data = fit_data[:, np.argsort(model.column_labels_)]

plt.matshow(fit_data, cmap=plt.cm.Blues)
plt.title("After biclustering; rearranged to show biclusters")

consensus score: 1.000

Text(0.5, 1.0, 'After biclustering; rearranged to show biclusters')

Spectral BiClustering

• Assumes input data has a hidden checkerboard structure.
• Partitions the rows & columns so that a corresponding blockwise-constant checkerboard matrix is a good approximation of the original.

Example Spectral Biclustering

• Data is generated using make_checkerboard, then shuffled and passed to the Biclustering algorithm. The rows & columns are then rearranged to show the discovered biclusters.

import numpy as np
from matplotlib import pyplot as plt
from sklearn.datasets import make_checkerboard 
from sklearn.cluster import SpectralBiclustering as SB
from sklearn.metrics import consensus_score as CS

n_clusters = (4, 3)
data, rows, columns = make_checkerboard(
    shape=(300, 300), n_clusters=n_clusters, noise=10,
    shuffle=False, random_state=0)

plt.matshow(data, cmap=plt.cm.Blues)
plt.title("Original")

Text(0.5, 1.0, 'Original')

rng = np.random.RandomState(0)
row_idx = rng.permutation(data.shape[0])
col_idx = rng.permutation(data.shape[1])
data = data[row_idx][:, col_idx]

plt.matshow(data, cmap=plt.cm.Blues)
plt.title("Shuffled")

Text(0.5, 1.0, 'Shuffled')

model = SB(n_clusters=n_clusters, method='log', random_state=0)
model.fit(data)
score = CS(model.biclusters_,
           (rows[   :, row_idx], 
            columns[:, col_idx]))

print("consensus score: {:.1f}".format(score))

fit_data =     data[   np.argsort(model.row_labels_)]
fit_data = fit_data[:, np.argsort(model.column_labels_)]

plt.matshow(fit_data, cmap=plt.cm.Blues)
plt.title("After biclustering; rearranged")

consensus score: 1.0

Text(0.5, 1.0, 'After biclustering; rearranged')

plt.matshow(np.outer(np.sort(model.row_labels_) + 1,
                     np.sort(model.column_labels_) + 1),
            cmap=plt.cm.Blues)
plt.title("Checkerboard of rearranged data")

Text(0.5, 1.0, 'Checkerboard of rearranged data')

Metrics / Evaluation

• Currently in Scikit-Learn: no way to use self-guided measures such as cluster stability. Must rely on external measures using true data.
• True is usually unavailable. Biclustering with artificial data may be useful given the true data is known.
• Use the Jaccard index to compare individual biclusters: $J(A, B) = \frac{|A \cap B|}{|A| + |B| - |A \cap B|}$ where $A$ & $B$ are biclusters and $|A \cap B|$ is the #elements in the intersection.
  • Jaccard index = 0: no overlap
  • Jaccard index = 1: identical biclusters
• Use the consensus score to compare two sets of biclusters.
  • Consensus score = 0: all bicluster pairs are totally dissimilar.
  • Consensus score = 1: both sets are identical.