2.4. 双聚类(Biclustering)

可以使用该模块 sklearn.cluster.bicluster实现双聚类(Biclustering)算法。双聚类算法同时对数据矩阵的行和列进行聚类。这些行和列的聚类称为双聚类。每一次聚类都会基于原始数据矩阵确定一个子矩阵，并且这些子矩阵具有一些需要的属性。

例如，给定一个形状为(10, 10)的矩阵，如果对三行两列进行双聚类的话，会产生出一个形状为(3, 2)的子矩阵：

>>> 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]])

出于可视化目的，给定一个双聚类，可以重新排列数据矩阵的行和列以使该双聚类是连续的。

不同的双聚类算法在如何定义双聚类方面有所不同，但其中通用类型包括：

• 常量, 常量行或常量列
  • 异常高或低的值
  • 低方差的子矩阵
  • 相关的行或列

算法的不同之处还在于如何给行和列分配双聚类，这导致了不同的双聚类结构。当行和列分成区块时，将出现块对角线(block diagonal)或棋盘(checkerboard)结构。

如果每一行和每一列恰好属于同一个双聚类的话，则重新排列数据矩阵的行和列将会显示在对角线上。这是此结构的案例，其中双聚类比其他行和列具有更高的平均值：

通过划分行和列而形成的双聚类的案例。

在棋盘(checkerboard)结构的情况下，每一行都属于所有列聚类，并且每一列都属于所有行聚类。这是此结构的案例，其中每个双象限内值的方差很小：

棋盘双聚类的案例。

在拟合完模型之后，可以在rows_和columns_属性中找到行和列的归属信息。rows_[i] 是一个二元向量，其中非零元素表示属于双聚类的i行。同样的，columns_[i] 就表示属于双聚类的 i列。

一些模型也具有row_labels_和column_labels_属性。这些模型会对行和列进行分区，例如在块对角线和棋盘双聚类结构中。

注意：双聚类(biclustering)在不同领域中还有许多其他名称，包括协同聚类(co-clustering)，双模式聚类(two-mode clustering)，双向聚类(two-way clustering)，块聚类(block clustering)，耦合双向聚类(coupled two-way clustering)等。某些算法（例如频谱协同聚类）反映了这些名称。

2.4.1. 光谱协同聚类(Spectral Co-Clustering)

SpectralCoclustering算法会找到比其他行和列中的值更高的双聚类。每一行和每一列恰好属于同一个双聚类，因此重新分配行和列，使得分区连续显示对角线上的高值：

注意：该算法将输入数据矩阵视为二部图(bipartite graph)：矩阵的行和列对应于两组顶点，每个元素对应于行和列之间的边。该算法会标准化分割此图并进行近似，以找到较重(heavy)的子图。

2.4.1.1. 数学公式

可以通过图的拉普拉斯算子的广义特征值分解找到最优归一化割的近似解。通常，这意味着直接使用拉普拉斯矩阵。如果原始数据矩阵A的形状为m×n，则相应二部图(bipartite graph)的拉普拉斯矩阵的形状为(m+n)×(m+n)。但是，在这种情况下，可以直接使用A矩阵，因为它的数据量更小，更有效。

输入矩阵A预处理如下：

A_n = R^{-1/2} A C^{-1/2}
R是对角矩阵，其中元素i等于\sum_{j} A_{ij}，C是对角矩阵，其中元素j等于\sum_{i} A_{ij}。

奇异值分解，A_n = U \Sigma V^\top，提供矩阵A的行和列的分区。左边奇异向量的子集给予行分区，右边的奇异向量的子集给予列分区。

奇异向量\ell = \lceil \log_2 k \rceil从第二个开始，提供所需的分区信息。这些用于形成矩阵Z：

Z = \begin{bmatrix} R^{-1/2} U \\\\ C^{-1/2} V \end{bmatrix}
U的列是u_2, \dots, u_{\ell +1}，V的列也具有相似特性。

然后Z的所有行通过使用k-means进行聚类。第一个n_rows标签提供行分区信息，其余n_columns标签提供列分区信息。

案例：

• 光谱协同聚类算法演示：如何用双聚类产生一个数据矩阵并应用。

• 使用光谱协同聚类算法对文档进行分类：一个在20个新闻组数据集中发现双聚类的案例。

参考文献：

• Dhillon, Inderjit S, 2001. Co-clustering documents and words using bipartite spectral graph partitioning.

2.4.2. 双向谱聚类(Spectral Biclustering)

SpectralBiclustering算法假设输入的数据矩阵具有隐藏的棋盘结构。具有这种结构的矩阵的行列可能被分区，使得在笛卡尔积中的大部分双聚类的列聚类和行聚类是近似恒定的。

这个算法对矩阵的行和列进行分区，以至于提供一个相应的块状不变的棋盘矩阵，近似于原始矩阵。

2.4.2.1. 数学公式

输入矩阵A首先进行标准化，以使棋盘图案更加明显。有三种可能的方法：

1. 独立行和列归一化，如同“光谱协同聚类”中所描述的。此方法使所有行进行行内相加得到一个相同常量，所有列相加得到另一个相同常量。
2. 双歧化(Bistochastization)：重复行和列归一化直到收敛。此方法使行和列的总和为相同的常量。
3. 对数归一化：计算数据矩阵的对数：L =\log A。然后列均值\overline{L_{i \cdot}}，行均值\overline{L_{\cdot j}}和\overline{L_{\cdot\cdot}}是L的总体均值。最终矩阵根据下面公式进行计算

K_{ij} = L_{ij} – \overline{L_{i \cdot}} – \overline{L_{\cdot j}} + \overline{L_{\cdot \cdot}}

归一化后，第一个的奇异向量被计算，就如同光谱协同聚类算法一样。

如果使用对数归一化，则所有奇异向量都是有意义的。但是，如果使用独立行和列归一化或双歧化，则第一个奇异矢量u_1和v_1将会被丢弃。从现在开始，“第一个”奇异向量指的是u_2 \dots u_{p+1}和v_2 \dots v_{p+1}，除了对数归一化的情况。

给定这些奇异向量，按照分段常数向量的最佳近似程度,将他们排序。使用一维 k-means 找到每个向量的近似值并使用欧氏距离进行评分。最好的左右奇异向量的某个子集被选择。下一步，数据将被投影到奇异向量的最佳子集并进行聚类。

例如，如果已经计算得到p个奇异向量，则可以找出q个最佳得奇异向量，其中q。让U的列具有q个最佳左奇异向量的矩阵，并且V是由q个右奇异向量组成的矩阵。要对行进行分区，将A投影到q维空间：A∗V。把m×q矩阵的m行作为样本，并使用k均值聚类处理产生行标签。同样，将列投影到A^{\top} * U，并对n×q矩阵j进行聚类产生列标签。

案例：

• 双向谱聚类算法演示：一个简单的案例，说明如何生成棋盘矩阵并对其进行双聚类。

参考文献：

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

2.4.3. 双聚类(Biclustering)评估

有两种评估双聚类结果的方法：内部和外部。内部评估，如聚类稳定性，依赖于数据和结果本身。目前在scikit-learn中没有内部的双聚类评估。外部评估是指外部信息来源，例如真实解。当处理真实数据时，真实解通常是未知的，但是，由于人造数据的真实解是已知的，因此人造数据的双向聚类可能对于评估算法非常有用。

为了将一组已发现的双聚类与一组真实的双聚类的行进行比较，需要两个相似性度量：单个双聚类的相似性度量以及将这些个体相似度结合到总分中的度量。

为了比较单个双聚类，已使用了几种方法。现在，仅实现了Jaccard索引：

J(A, B) = \frac{|A \cap B|}{|A| + |B| – |A \cap B|}
其中A和B是双聚类，|A∩B|是交叉点的元素的数量。当双聚类完全不重叠时，Jaccard索引的最小值为0，而当它们完全重叠时时，最大值为1。

已经开发了几种方法来比较两个双聚类的集合(set)。目前，只有 consensus_score (Hochreiter et. al., 2010)是可用的：

1. 使用Jaccard索引或类似措施，为每个集合中的一对双聚类对计算之间的相似性。
2. 以一对一的方式将双聚类从一个集合分配给另一个集合，以最大化其相似性的总和。该步骤使用匈牙利算法(Hungarian algorithm)执行。
3. 相似性的最终总和除以较大集合的大小。

当所有双聚类对都完全不相似时，最小共识得分为0。当两个双聚类集合相同时，最大得分为1。

参考文献：

• Hochreiter, Bodenhofer, et. al., 2010. FABIA: factor analysis for bicluster acquisition.

©2007-2019，scikit-learn开发人员（BSD许可证）。 显示此页面源码

未经允许不得转载：PythonOK » 2.4. 双聚类(Biclustering)