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_ 属性。这些模型对行和列进行分区，例如在块对角线和棋盘式双聚类结构中。

注意

双聚类在不同的领域有许多其他名称，包括共聚类、双模聚类、双向聚类、块聚类、耦合双向聚类等。一些算法的名称，例如谱共聚类算法，反映了这些替代名称。

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 个标签提供列分区。

示例

参考文献

2.4.2. 谱双聚类#

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

该算法对矩阵的行和列进行分区，使得相应的块状常数棋盘式矩阵对原始矩阵提供了良好的近似。

2.4.2.1. 数学公式#

输入矩阵 \(A\) 首先被归一化，以使棋盘式模式更加明显。有三种可能的方法

  1. 独立的行和列归一化，如谱共聚类中。此方法使行之和为常数，列之和为不同的常数。

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

  3. 对数归一化：计算数据矩阵的对数：\(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\) 矩阵进行聚类，即可得到列标签。

示例

参考文献

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. 以一对一的方式将一组双聚类分配到另一组，以最大化它们的相似度之和。此步骤使用匈牙利算法执行。

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

最小一致性分数为 0，发生在所有双聚类对完全不同时。最大分数为 1，发生在两组完全相同时。

参考文献

本页内容
显示源代码