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。

參考文獻