2.4. 双聚类

校验者: @udy @barrycg 翻译者: @程威

Biclustering(双向聚类) 的实现模块是 sklearn.cluster.bicluster。双向聚类算法对数据矩阵的行列同时进行聚类。而这些行列的聚类称之为双向簇(biclusters)。每一次聚类都会基于原始数据矩阵确定一个子矩阵, 并且这些子矩阵具有一些需要的属性。

例如, 给定一个矩阵 (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]])

为了可视化，给定一个双向簇，数据矩阵的行列可以重新分配，使得该双向簇是连续的。

不同的双向聚类算法在如何定义双向簇方面有所不同，但其中通用类型包括： * 常量, 常量行或常量列。 * 异常高的或者低的值。 * 低方差的子矩阵。 * 相互关联的行列。

算法在给双向簇分配行列的方式不同, 会导致不同的双向聚类结构。当行和列分成区块时，会出现块对角或者棋盘结构。

如果每一行和每一列仅属于一个双向簇,重新排列数据矩阵的行和列,会使得双向簇出现在对角线上。下面是一个示例，此结构的双向簇具有比其他行列更高的平均值:

在棋盘结构的示例中, 每一行属于所有的列簇, 每一列属于所有的行簇。下面是一个示例，每个双向簇内的值差异较小:

在拟合模型之后，可以在 rows_ 和 columns_ 属性中找到行簇和列簇的归属信息(membership)。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. Spectral Co-Clustering

SpectralCoclustering(联合谱聚类) 算法找到的双向簇的值比其它的行和列更高。每一个行和列都只属于一个双向簇, 所以重新分配行和列，使得分区连续显示对角线上的高值:

注意算法将输入的数据矩阵看做成二分图：该矩阵的行和列对应于两组顶点，每个条目对应于行和列之间的边，该算法近似的进行归一化，对图进行切割，找到更重的子图。

2.4.1.1. 数学公式

找到最优归一化剪切的近似解，可以通过图形的 Laplacian 的广义特征值分解。通常这意味着直接使用 Laplacian 矩阵. 如果原始数据矩阵的形状 $m \times n$ , 则对应的二分图(bipartite graph)的 Laplacian 矩阵具有形状 $(m + n) \times (m + n)$ 。但是, 在这种情况下, 直接使用 , 因为它更小，更有效率。

输入矩阵被预处理如下:

$A_n = R^{-1/2} A C^{-1/2}$

是对角线矩阵，其中元素等于 $\sum_{j} A_{ij}$ ，是对角矩阵，其中元素等于 $\sum_{i} A_{ij}$ 。

奇异值分解, $A_n = U \Sigma V^\top$ , 产生了行列的分区. 左边奇异向量的子集给予行分区，右边的奇异向量的子集给予列分区。

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

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

的列是 $u_2, \dots, u_{\ell +1}$ , 和的列也具有相似特性。

然后的所有行通过使用 k-means 进行聚类. 第一个n_rows 标签提供行分区信息, 剩下的 n_columns 标签提供列分区信息。

示例:

A demo of the Spectral Co-Clustering algorithm: 如何用双向簇产生一个数据矩阵并应用。
Biclustering documents with the Spectral Co-clustering algorithm:一个在 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. 数学表示

输入矩阵先归一化，使得矩阵的棋盘模式更明显。这里有三种方法:

独立的行列归一化, 如联合谱聚类中所示. 这个方法使得所有行进行行内相加得到一个相同常量，所有列相加得到另一个相同常量。
Bistochastization: 重复行和列归一化直到收敛。该方法使得行和列相加得到一个相同的常数。
对数归一化: 数据矩阵的对数是 $L = \log A$ . 列对数就是 $\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}}$

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

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

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

例如，如果已计算得到个奇异向量, 个最佳得奇异向量可以被找出, 因为 q<p 。让为列是个最佳左奇异向量的矩阵, 并且是用右奇异向量组成的矩阵. 为了划分行, 将投影到维空间: A * V 。把 $m \times q$ 矩阵的行作为样本, 然后使用 k-means 的聚类处理产生行标签。类似地，将列投影到 $A^{\top} * U$ ，并且对 $n \times q$ 矩阵进行聚类得到列标签。