2.4. 雙聚類 · sklearn中文文檔

# 2.4. 雙聚類校驗者: [@udy](https://github.com/apachecn/scikit-learn-doc-zh) 翻譯者: [@程威](https://github.com/apachecn/scikit-learn-doc-zh) Biclustering 可以使用 [`sklearn.cluster.bicluster`](classes.html#module-sklearn.cluster.bicluster "sklearn.cluster.bicluster") 模塊。 Biclustering 算法對數據矩陣的行列同時進行聚類。同時對行列進行聚類稱之為 biclusters。每一次聚類都會通過原始數據矩陣的一些屬性確定一個子矩陣。例如, 一個矩陣 `(10, 10)` , 一個 bicluster 聚類，有三列二行，就是一個子矩陣 `(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]]) ``` 為了可視化，給定一個 bicluster 聚類，數據矩陣的行列可以重新分配，使得 bi-cluster 是連續的。算法在如何定義 bicluster 方面有一些不同，常見類型包括： - 不變的 values , 不變的 rows, 或者不變的 columns。 - 異常高的或者低的值。 - 低方差的子矩陣。 - 相關的 rows 或者 columns。算法在分配給 bicluster 行列的方式不同, 會導致不同的 bicluster 結構。當行和列分成分區時，會發生對角線或者棋盤結構。如果每一行和每一列同屬于一種 bicluster ,就重新排列數據矩陣的行和列,會使得 bicluster 呈現對角線。下面是一個例子，此結構的biclusters 具有比其他行列更高的平均值: [![http://sklearn.apachecn.org/cn/0.19.0/_images/sphx_glr_plot_spectral_coclustering_0031.png](https://box.kancloud.cn/f4ead1b809dedbd970168effd3f437e6_480x480.jpg)](../auto_examples/bicluster/images/sphx_glr_plot_spectral_coclustering_003.png) 在棋盤結構的例子中, 每一行屬于所有的列類別, 每一列屬于所有的行類別。下面是一個例子，每個 bicluster 中的值差異較小: [![http://sklearn.apachecn.org/cn/0.19.0/_images/sphx_glr_plot_spectral_biclustering_0031.png](https://box.kancloud.cn/bad9a5145d38edb640b94c96343887fe_480x480.jpg)](../auto_examples/bicluster/images/sphx_glr_plot_spectral_biclustering_003.png) 在擬合模型之后，可以在 `rows_` 和 `columns_` 屬性中找到行列 cluster membership 。 `rows_[i]` 是一個二進制的向量，就是屬于 bicluster `i` 的一行。同樣的, `columns_[i]` 就表示屬于 bicluster `i` 的列。一些模塊也有 `row_labels_` 何 `column_labels_` 屬性。這些模塊對行列進行分區, 例如對角線或者棋盤 bicluster 結構。 Note Biclustering 在不同的領域有很多其他名稱，包括 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`](generated/sklearn.cluster.bicluster.SpectralCoclustering.html#sklearn.cluster.bicluster.SpectralCoclustering "sklearn.cluster.bicluster.SpectralCoclustering") 算法找到的 bicluster 的值比相應的其他行和列更高。每一個行和列都只屬于一個 bicluster, 所以重新分配行和列，使得分區連續顯示對角線上的 high value: Note 算法將輸入的數據矩陣看做成二分圖：該矩陣的行和列對應于兩組頂點，每個條目對應于行和列之間的邊，該算法近似的進行歸一化，對圖進行切割，找到更重的子圖。 ### 2.4.1.1. 數學公式找到最優歸一化剪切的近似解，可以通過圖形的 Laplacian 的廣義特征值分解。通常這意味著直接使用 Laplacian 矩陣. 如果原始數據矩陣 ![A](https://box.kancloud.cn/3bbe3fcb07275cb8959a845aebfa63fa_13x12.jpg) 有形狀 ![m \times n](https://box.kancloud.cn/0c80155baa7aea744f143dbf151c93db_49x9.jpg), 則對應的 bipartite 圖的 Laplacian 矩陣具有形狀 ![(m + n) \times (m + n)](https://box.kancloud.cn/c2d3d37bb6a88795d1720b129f6fc585_145x18.jpg)。但是, 在這種情況直接使用 ![A](https://box.kancloud.cn/3bbe3fcb07275cb8959a845aebfa63fa_13x12.jpg) , 因為它更小，更有作用。輸入矩陣 ![A](https://box.kancloud.cn/3bbe3fcb07275cb8959a845aebfa63fa_13x12.jpg) 被預處理如下: ![A_n = R^{-1/2} A C^{-1/2}](https://box.kancloud.cn/01f2ac428f754f7794be392bc5cd1612_146x22.jpg) ![R](https://box.kancloud.cn/e852b8eff445e0cd8df4a9fc694e49f5_14x12.jpg) 是 ![i](https://box.kancloud.cn/9f004454a20e19932b2a071a380ff8ff_6x13.jpg) 對角線矩陣，和 ![\sum_{j} A_{ij}](https://box.kancloud.cn/544e2c236ab2e42a492fbac89e641960_51x22.jpg) 相同， ![C](https://box.kancloud.cn/95378f1036b3ba9a15a5f33f8521b6f2_14x12.jpg) 是 ![j](https://box.kancloud.cn/7c1f52c4cc615183dbd16304bc8c1e94_9x16.jpg) 的對角吸納矩陣，等同于 ![\sum_{i} A_{ij}](https://box.kancloud.cn/7170bdb6d38166827ea11dab298ab5d5_50x19.jpg)。奇異值分解, ![A_n = U \Sigma V^\top](https://box.kancloud.cn/60f776dbd292c36db0471ab654c886b4_98x18.jpg) , 提供了 ![A](https://box.kancloud.cn/3bbe3fcb07275cb8959a845aebfa63fa_13x12.jpg) 行列的分區. 左邊的奇異值向量給予行分區，右邊的奇異值向量給予列分區。 ![\ell = \lceil \log_2 k \rceil](https://box.kancloud.cn/ba11c1a5cd5514f43cfa0a4e4c4ecc93_88x19.jpg) 奇異值向量從第二個開始, 提供所需的分區信息。這些用于形成矩陣 :Z: ![Z = \begin{bmatrix} R^{-1/2} U \\\\ C^{-1/2} V \end{bmatrix}](https://box.kancloud.cn/fe2b9859362e924315f89f845eb5e868_114x69.jpg) ![U](https://box.kancloud.cn/be9c9d987358e2b606c5f29749b66b55_13x12.jpg) 的列是 ![u_2, \dots, u_{\ell +1}](https://box.kancloud.cn/22ddd58a64a30a4353a6c85995db3430_89x13.jpg), 和 ![V](https://box.kancloud.cn/e7065953228a039d8bbaf097ff72097a_14x12.jpg) 相似。然后 ![Z](https://box.kancloud.cn/15dbc83465b1b0e0ca48c121420925ce_12x12.jpg) 的 rows 通過使用 [k-means](clustering.html#k-means) 進行聚類. `n_rows` 標簽提供行分區, 剩下的 `n_columns` 標簽提供列分區。例子: - [A demo of the Spectral Co-Clustering algorithm](../auto_examples/bicluster/plot_spectral_coclustering.html#sphx-glr-auto-examples-bicluster-plot-spectral-coclustering-py): 如何用 bicluster 數據矩陣并應用。 - [Biclustering documents with the Spectral Co-clustering algorithm](../auto_examples/bicluster/plot_bicluster_newsgroups.html#sphx-glr-auto-examples-bicluster-plot-bicluster-newsgroups-py):一個在 20 個新聞組數據集中發現 biclusters 的例子參考文獻: - Dhillon, Inderjit S, 2001. [Co-clustering documents and words using bipartite spectral graph partitioning](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.140.3011). ## 2.4.2. Spectral Biclustering > [`SpectralBiclustering`](generated/sklearn.cluster.bicluster.SpectralBiclustering.html#sklearn.cluster.bicluster.SpectralBiclustering "sklearn.cluster.bicluster.SpectralBiclustering") 算法假設輸入的數據矩陣具有隱藏的棋盤結構。具有這種結構的矩陣的行列可能被分區，使得在笛卡爾積中的大部分 biclusters 的 row clusters 和 column cluster 是近似恒定的。例如，如果有兩個row 分區和三個列分區，每一行屬于三個 bicluster ，每一列屬于兩個 bicluster。這個算法劃分矩陣的行和列，以至于提供一個相應的塊狀不變的棋盤矩陣，近似于原始矩陣。 ### 2.4.2.1. 數學表示輸入矩陣 ![A](https://box.kancloud.cn/3bbe3fcb07275cb8959a845aebfa63fa_13x12.jpg) 先歸一化，使得棋盤模式更明顯。有三種方法: 1. *獨立的行和列歸一化*, as in Spectral Co-Clustering. 這個方法使得行和一個常數相加，列和變量相加。 2. **Bistochastization**: 重復行和列歸一化直到收斂。該方法使得行和列都相加相同的常數。 1. **Log 歸一化**: 計算數據矩陣的對數 ![L = \log A](https://box.kancloud.cn/715c85e0b22b154868a92d443254f969_76x16.jpg). 列就是 ![\overline{L_{i \cdot}}](https://box.kancloud.cn/928a32cfc1b1299fdd612b1bf1740bfb_21x18.jpg), 行就是 ![\overline{L_{\cdot j}}](https://box.kancloud.cn/b71752efa0e010e1d1c94b8da131f3eb_23x21.jpg), 總體上來看 ![\overline{L_{\cdot \cdot}}](https://box.kancloud.cn/e1f57362a29b1f5c3ddd84b4143db34c_21x16.jpg) of ![L](https://box.kancloud.cn/932e52dfeb15d15287c07f0b899113b1_12x12.jpg) 被計算的. 最后矩陣通過下面的公式計算 ![K_{ij} = L_{ij} - \overline{L_{i \cdot}} - \overline{L_{\cdot j}} + \overline{L_{\cdot \cdot}}](https://box.kancloud.cn/ea687b8f2059bfd350217af2af1fcf47_205x21.jpg) 歸一化后，首先少量的奇異值向量被計算，只是在 Spectral Co-Clustering 算法中。如果使用 log 歸一化，則所有的奇異向量都是有意義的。但是, 如果是獨立的歸一化或雙曲線化被使用，第一個奇異矢量, ![u_1](https://box.kancloud.cn/e6da4ee74dc266afe477fc690a96b724_16x12.jpg) 和 ![v_1](https://box.kancloud.cn/64ad3965540e4ee2a1763454da48562c_15x12.jpg)。會被丟棄。從現在開始, “first” 奇異值向量與 ![u_2 \dots u_{p+1}](https://box.kancloud.cn/c8282f140c51129a30274543dfbfef4e_78x14.jpg) 和 ![v_2 \dots v_{p+1}](https://box.kancloud.cn/1492df1344e329f91113b37d20167360_75x14.jpg) 相關，除了日志歸一化的情況。給定這些奇異值向量，將他們排序，通過分段常數向量保證最佳近似。使用一維 k-means 找到每個向量的近似值并使用歐幾里得距離得分。 Some subset of 最好的左右奇異值向量的子集被選擇。下一步, 數據預計到這個最佳子集的奇異向量和聚類。例如，如果 ![p](https://box.kancloud.cn/251fcba434769c07a22131f9d8b84b32_10x12.jpg) 奇異值向量被計算，最好按照描述找到 ![q](https://box.kancloud.cn/ea1b9c81670ab99b7f8d866ad163a2af_9x12.jpg) ，其中 ![q<p](https://box.kancloud.cn/19300021877f872b33397f5042e2fd7e_42x14.jpg)。 ![U](https://box.kancloud.cn/be9c9d987358e2b606c5f29749b66b55_13x12.jpg) 列為，the ![q](https://box.kancloud.cn/ea1b9c81670ab99b7f8d866ad163a2af_9x12.jpg) 最佳左奇異向量的矩陣, 并且 ![V](https://box.kancloud.cn/e7065953228a039d8bbaf097ff72097a_14x12.jpg) 對于右邊是類似的. 要劃分行, 將 ![A](https://box.kancloud.cn/3bbe3fcb07275cb8959a845aebfa63fa_13x12.jpg) 的投影到 ![q](https://box.kancloud.cn/ea1b9c81670ab99b7f8d866ad163a2af_9x12.jpg) 維空間: ![A * V](https://box.kancloud.cn/c69cae49b12b28bbf3687b17ed915f1e_45x12.jpg)。 ![m](https://box.kancloud.cn/4d74e1a3833de6bf63d34767d6dbbc91_16x8.jpg) 行 ![m \times q](https://box.kancloud.cn/ecfe5fd6a10e76f8f91952d03a7bbbea_47x13.jpg)矩陣的行作為采樣和使用 k-means 的聚類處理產生行標簽。類似地，將列投影到 ![A^{\top} * U](https://box.kancloud.cn/32fa0b7d30ace1f29c6ce35ca58760f0_56x15.jpg) ，并且對 ![n \times q](https://box.kancloud.cn/610639f3c273117f834e8bf2f64ff3b3_42x13.jpg) 矩陣進行聚類得到列標簽。示例: - [A demo of the Spectral Biclustering algorithm](../auto_examples/bicluster/plot_spectral_biclustering.html#sphx-glr-auto-examples-bicluster-plot-spectral-biclustering-py): 一個簡單的例子顯示如何生成棋盤矩陣和 bicluster . 參考文獻: - Kluger, Yuval, et. al., 2003. [Spectral biclustering of microarray data: coclustering genes and conditions](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.135.1608). ## 2.4.3. Biclustering 評測有兩種評估雙組分結果的方法：內部和外部。諸如群集穩定性等內部措施只依賴于數據和結果本身。目前在scikit-learn中沒有內部的二集群措施。外部措施是指外部信息來源，例如真正的解決方案。當使用真實數據時，真正的解決方案通常是未知的，但是，由于真正的解決方案是已知的，因此人造數據的雙重分析可能對于評估算法非常有用。為了將一組已發現的雙組分與一組真正的雙組分進行比較，需要兩個相似性度量：單個雙色團體的相似性度量，以及將這些個體相似度結合到總分中的方法。為了比較單個雙核，已經采用了幾種措施。現在，只有Jaccard索引被實現： ![J(A, B) = \frac{|A \cap B|}{|A| + |B| - |A \cap B|}](https://box.kancloud.cn/4ac883782604f102f15f3c155b58bb34_237x44.jpg) ![A](https://box.kancloud.cn/3bbe3fcb07275cb8959a845aebfa63fa_13x12.jpg) 和 ![B](https://box.kancloud.cn/577b9cc5fd0224be358cf847a88d6c06_14x12.jpg) 是 biclusters, ![|A \cap B|](https://box.kancloud.cn/cd51a8c5030bbb7cd9b69c492ede8a1b_54x19.jpg) 是交叉點的元素的數量。Jaccard 索引達到最小值0，當 biclusters 不重疊的時候，并且當他們相同干的時候，最大值為1。有些方法已經開發出來，用來比較兩個 biclusters 的數據集。從現在開始之后 [`consensus_score`](generated/sklearn.metrics.consensus_score.html#sklearn.metrics.consensus_score "sklearn.metrics.consensus_score") (Hochreiter et. al., 2010) 是可以用: 1. 使用 Jaccard 索引或類似措施，計算 biclusters 的 bicluster 相似性。 2. 以一對一的方式將 bicluster 分從一組分配給另一組，以最大化其相似性的總和。該步驟使用匈牙利算法執行。 3. 相似性的最終總和除以較大集合的大小。最小共識得分為0，發生在所有 biclusters 完全不相似時。當兩組 biclusters 相同時，最大分數為1。參考文獻: - Hochreiter, Bodenhofer, et. al., 2010. [FABIA: factor analysis for bicluster acquisition](https://www.ncbi.nlm.nih.gov/pmc/articles/PMC2881408/).