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. 以一对一的方式将一组中的双聚类分配给另一组，以最大化其相似度之和。此步骤使用scipy.optimize.linear_sum_assignment执行，该函数使用改进的 Jonker-Volgenant 算法。

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

当所有双聚类对完全不同时，最小一致性得分是 0。当两组完全相同时，最大得分为 1。

参考文献