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-均值 对 \(Z\) 的行进行聚类。前 n_rows 个标签提供行分区，其余 n_columns 个标签提供列分区。

示例

参考文献

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-均值找到，并使用欧几里得距离进行评分。选择最佳左奇异向量和右奇异向量的某个子集。接下来，数据被投影到这个最佳奇异向量子集并进行聚类。

例如，如果计算了 \(p\) 个奇异向量，则按照上述描述找到 \(q\) 个最佳奇异向量，其中 \(q<p\)。令 \(U\) 为以 \(q\) 个最佳左奇异向量为列的矩阵，\(V\) 类似。为了对行进行分区，矩阵 \(A\) 的行被投影到一个 \(q\) 维空间：\(A * V\)。将这个 \(m \times q\) 矩阵的 \(m\) 行视为样本，并使用 k-均值进行聚类，得到行标签。类似地，将列投影到 \(A^{\top} * U\) 并对这个 \(n \times q\) 矩阵进行聚类，得到列标签。

示例

参考文献

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 等., 2010) 可用

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

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

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

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

参考文献