2.4. 双聚类#

双聚类算法同时对数据矩阵的行和列进行聚类。这些行和列的簇被称为双聚类。每个双聚类都确定了原始数据矩阵的一个子矩阵，该子矩阵具有某些期望的特性。

例如，给定一个形状为 (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]])

为了可视化目的，给定一个双聚类，可以重新排列数据矩阵的行和列，使双聚类在视觉上连续。

算法在如何定义双聚类方面有所不同。一些常见的类型包括：

  • 恒定值、恒定行或恒定列

  • 异常高或异常低的值

  • 低方差的子矩阵

  • 相关的行或列

算法在如何将行和列分配给双聚类方面也有所不同，这导致了不同的双聚类结构。当行和列被划分为分区时，会出现块对角线或棋盘格结构。

如果每行和每列都恰好属于一个双聚类，那么重新排列数据矩阵的行和列会在对角线上显示出这些双聚类。这是一个示例，其中双聚类具有比其他行和列更高的平均值。

../_images/sphx_glr_plot_spectral_coclustering_003.png

由行和列分区形成的双聚类示例。#

在棋盘格的情况下，每行属于所有的列簇，每列属于所有的行簇。这是一个示例，其中每个双聚类内的值方差很小。

../_images/sphx_glr_plot_spectral_biclustering_003.png

棋盘格双聚类示例。#

拟合模型后，行和列簇的成员身份可以在 rows_ 和 columns_ 属性中找到。rows_[i] 是一个二进制向量，其中非零项对应于属于双聚类 i 的行。类似地，columns_[i] 指示哪些列属于双聚类 i。

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

注意

双聚类在不同领域有许多其他名称，包括协同聚类（co-clustering）、双模式聚类（two-mode clustering）、双向聚类（two-way clustering）、块聚类（block clustering）、耦合双向聚类（coupled two-way clustering）等。一些算法的名称，如谱协同聚类算法（Spectral Co-Clustering algorithm），反映了这些替代名称。

2.4.1. 谱协同聚类#

SpectralCoclustering 算法寻找值高于相应其他行和列中值的双聚类。每行和每列都恰好属于一个双聚类，因此重新排列行和列以使分区连续会沿对角线显示这些高值。

注意

该算法将输入数据矩阵视为一个二分图：矩阵的行和列对应于两组顶点，每个条目对应于行和列之间的一条边。该算法近似地计算该图的归一化割，以找到较重的子图。

2.4.1.1. 数学公式#

最优归一化割的近似解可以通过图的拉普拉斯矩阵的广义特征值分解找到。通常这意味着直接使用拉普拉斯矩阵。如果原始数据矩阵 \(A\) 的形状为 \(m \times n\)，则相应二分图的拉普拉斯矩阵的形状为 \((m + n) \times (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\)

\[\begin{split}Z = \begin{bmatrix} R^{-1/2} U \\\\ C^{-1/2} V \end{bmatrix}\end{split}\]

其中 \(U\) 的列是 \(u_2, \dots, u_{\ell + 1}\)，\(V\) 类似。

然后使用 k-means 对 \(Z\) 的行进行聚类。前 n_rows 个标签提供行分区，剩下的 n_columns 个标签提供列分区。

示例

References

2.4.2. 谱双聚类#

SpectralBiclustering 算法假设输入数据矩阵具有隐藏的棋盘格结构。具有这种结构的矩阵的行和列可以被分区，使得行簇和列簇笛卡尔积中任何双聚类的条目近似恒定。例如，如果有两个行分区和三个列分区，每行将属于三个双聚类，每列将属于两个双聚类。

该算法对矩阵的行和列进行分区，以便相应的块状恒定棋盘格矩阵能很好地近似原始矩阵。

2.4.2.1. 数学公式#

首先对输入矩阵 \(A\) 进行归一化，以使棋盘格图案更加明显。有三种可能的方法：

  1. 独立的行和列归一化，如谱协同聚类中所述。此方法使行的总和为常数，列的总和为另一个常数。

  2. 双随机化（Bistochastization）：重复进行行和列归一化直到收敛。此方法使行和列的总和都为相同的常数。

  3. 对数归一化（Log normalization）：计算数据矩阵的对数：\(L = \log A\)。然后计算 \(L\) 的列均值 \(\overline{L_{i \cdot}}\)、行均值 \(\overline{L_{\cdot j}}\) 和整体均值 \(\overline{L_{\cdot \cdot}}\)。最终矩阵根据以下公式计算：

\[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<p\)）。设 \(U\) 是以这 \(q\) 个最佳左奇异向量为列的矩阵，\(V\) 类似。为了对行进行分区，将 \(A\) 的行投影到 \(q\) 维空间：\(A * V\)。将这个 \(m \times q\) 矩阵的 \(m\) 行视为样本，并使用 k-means 进行聚类，得到行标签。类似地，将列投影到 \(A^{\top} * U\) 并对这个 \(n \times q\) 矩阵进行聚类，得到列标签。

示例

References

2.4.3. 双聚类评估#

评估双聚类结果有两种方式：内部评估和外部评估。内部度量（如簇稳定性）仅依赖于数据和结果本身。目前 scikit-learn 中没有内部双聚类度量。外部度量参考外部信息源，例如真实解。在处理真实数据时，真实解通常是未知的，但对人工数据进行双聚类可能有助于精确评估算法，因为真实解是已知的。

为了将找到的双聚类集与真实双聚类集进行比较，需要两个相似性度量：单个双聚类的相似性度量，以及将这些单个相似性组合成总体分数的方​​法。

为了比较单个双聚类，已经使用了几种度量。目前，只实现了 Jaccard 指数：

\[J(A, B) = \frac{|A \cap B|}{|A| + |B| - |A \cap B|}\]

其中 \(A\) 和 \(B\) 是双聚类，\(|A \cap B|\) 是它们的交集中的元素数量。当双聚类完全不重叠时，Jaccard 指数达到最小值 0，当它们相同时，达到最大值 1。

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

  1. 使用 Jaccard 指数或类似度量，计算每组中成对双聚类的相似性。

  2. 以一对一的方式将一组中的双聚类分配给另一组中的双聚类，以使它们的相似性总和最大化。此步骤使用 scipy.optimize.linear_sum_assignment 执行，该函数使用修改后的 Jonker-Volgenant 算法。

  3. 最终的相似性总和除以较大集合的大小。

当所有双聚类对完全不相似时，最小共识分数（consensus score）为 0。当两组完全相同时，最大分数为 1。

References