scikit-learn 雙聚類(lèi)
可以使用sklearn.cluster.bicluster模塊進(jìn)行Biclustering(雙聚類(lèi)) 。 雙聚類(lèi)算法同時(shí)對(duì)數(shù)據(jù)矩陣的行和列進(jìn)行聚類(lèi)。而這些行列的聚類(lèi)稱(chēng)之為雙向簇(biclusters)。每一次聚類(lèi)都會(huì)基于原始數(shù)據(jù)矩陣確定一個(gè)子矩陣, 并且這些子矩陣具有一些需要的屬性。
例如, 給定一個(gè)矩陣 (10, 10) 的矩陣 , 如果對(duì)其中 3 行 2 列進(jìn)行雙向聚類(lèi)，就可以誘導(dǎo)出一個(gè)子矩陣 (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]])
出于可視化目的，給定一個(gè)雙向簇，可以重新排列數(shù)據(jù)矩陣的行和列以使雙向簇是連續(xù)的。
不同的雙向聚類(lèi)算法在如何定義雙向簇方面有所不同，一些常見(jiàn)的類(lèi)型包括：
常量, 常量行或常量列 異常高或低的值 低方差的子矩陣 相關(guān)聯(lián)的行或列
算法采用不同的方式給雙向簇分配行列，這導(dǎo)致了不同的雙向聚類(lèi)結(jié)構(gòu)。當(dāng)將行和列劃分為區(qū)塊時(shí)，將出現(xiàn)塊對(duì)角或棋盤(pán)結(jié)構(gòu)。
如果每一行和每一列恰好屬于一個(gè)二元組，則重新排列數(shù)據(jù)矩陣的行和列將顯示對(duì)角線上的二元組。這是此結(jié)構(gòu)的示例，此結(jié)構(gòu)的雙向簇具有比其他行列更高的平均值:
? 通過(guò)分隔行和列形成的雙向簇的示例
在棋盤(pán)結(jié)構(gòu)的例子中，每一行屬于所有的列簇, 每一列屬于所有的行簇。下面是這種結(jié)構(gòu)的一個(gè)例子，每個(gè)雙向簇內(nèi)的值差異較小:
? 棋盤(pán)格狀雙簇的示例
在對(duì)模型進(jìn)行擬合之后，可以在 rows_ 和 columns_ 屬性中找到行簇和列簇的歸屬信息。rows_[i] 是一個(gè)二元向量，其中非零項(xiàng)對(duì)應(yīng)于屬于雙向簇i 的行。 columns_[i] 就表示屬于雙向簇 i 的列。
一些模型還具有 row_labels_ 和 column_labels_ 屬性。這些模型劃分行和列，例如在塊對(duì)角或者棋盤(pán)雙向簇結(jié)構(gòu)。
注意 雙向聚類(lèi)在不同的領(lǐng)域有很多其他名稱(chēng)，包括 co-clustering, two-mode clustering, two-way clustering, block clustering, coupled two-way clustering 等等。一些算法的名稱(chēng)，比如 Spectral Co-Clustering algorithm, 反映了這些替代名稱(chēng)。
2.4.1. 聯(lián)合譜聚類(lèi)
SpectralCoclustering(聯(lián)合譜聚類(lèi))算法可以找到比對(duì)應(yīng)的其他行和列的值更高的雙向簇（biclusters）。每一行和每一列都只對(duì)應(yīng)一個(gè)雙向簇, 因此重新分配行和列以使分區(qū)相鄰，顯示對(duì)角線上的高值:
注意：該算法將輸入數(shù)據(jù)矩陣看做成二分圖：矩陣的行和列對(duì)應(yīng)于兩組頂點(diǎn)，每個(gè)條目對(duì)應(yīng)于行和列之間的一條邊，該算法近似于此圖的歸一化割，以找到重子圖。
2.4.1.1. 數(shù)學(xué)公式
可以 通常這意味著直接使用拉普拉斯矩陣。 如果原始數(shù)據(jù)矩陣 的形狀為 , 則對(duì)應(yīng)的二分圖的拉普拉斯矩陣具有形狀 (m+n)×(m+n)。 但是, 在這種情況下, 直接使用 , 因?yàn)樗?，更有效?/p>
輸入矩陣 預(yù)處理如下：
為對(duì)角線矩陣，其中元素 等于 ， 是對(duì)角矩陣，其中 等于 ，
奇異值分解, 產(chǎn)生了 行列的分區(qū)，左邊奇異向量的子集給予行分區(qū)，右邊的奇異向量的子集給予列分區(qū)。
奇異向量 從第二個(gè)開(kāi)始，奇異向量提供了所需的分區(qū)信息，它們用于形成矩陣 ：
的列是 類(lèi)似于 。
然后 的所有行通過(guò)k-means進(jìn)行聚類(lèi). 第一個(gè)n_rows 標(biāo)簽提供行分區(qū)信息, 剩下的 n_columns 標(biāo)簽提供列分區(qū)信息。
示例:
光譜共聚類(lèi)算法演示: 一個(gè)簡(jiǎn)單的示例，展示了如何使用雙向簇生成數(shù)據(jù)矩陣并將其應(yīng)用。 用譜協(xié)聚類(lèi)算法對(duì)文檔進(jìn)行集群化:一個(gè)在 20 個(gè)新聞組數(shù)據(jù)集中找雙向簇的示例 參考文獻(xiàn):
Dhillon, Inderjit S, 2001. Co-clustering documents and words using bipartite spectral graph partitioning.
2.4.2. 光譜雙聚類(lèi)
該SpectralBiclustering算法假定輸入數(shù)據(jù)矩陣具有隱藏的棋盤(pán)結(jié)構(gòu)?？梢詫?duì)具有這種結(jié)構(gòu)的矩陣的行和列進(jìn)行分區(qū)，例如，如果有兩個(gè)行分區(qū)和三個(gè)列分區(qū)，則每行將屬于三個(gè)bicluster，而每列將屬于兩個(gè)bicluster。
該算法對(duì)矩陣的行和列進(jìn)行劃分，以使相應(yīng)的塊狀不變的棋盤(pán)矩陣可以很好地逼近原始矩陣。
2.4.2.1. 數(shù)學(xué)表示
先歸一化輸入矩陣 ，使得矩陣的棋盤(pán)模式更明顯。有三種可能的方法:
獨(dú)立的行列歸一化，如聯(lián)合譜聚類(lèi)中所示。此方法使行總和為常量，而列總和為另一個(gè)的常量。 Bistochastization: 重復(fù)行和列歸一化直到收斂。此方法使行和列的總和為相同的常數(shù)。 對(duì)數(shù)歸一化: 計(jì)算數(shù)據(jù)矩陣的對(duì)數(shù) 。列均值是 ，行均值是 ，是 的整體平均。根據(jù)公式計(jì)算出最終矩陣：
歸一化之后，就像在聯(lián)合譜聚類(lèi)算法中一樣，計(jì)算前幾個(gè)奇異矢量。
如果使用對(duì)數(shù)歸一化，則所有奇異向量都是有意義的。但是, 如果使用獨(dú)立的歸一化或雙歧化, 則第一個(gè)奇異矢量 和 被丟棄。從現(xiàn)在開(kāi)始，“第一個(gè)“奇異向量指的是 和 對(duì)數(shù)歸一化的情況除外。
給定這些奇異向量，按照分段常數(shù)向量的最佳近似程度進(jìn)行排序。使用一維 k-means 找到每個(gè)向量的近似值，并使用歐氏距離進(jìn)行評(píng)分。選擇最佳左右奇異向量的一些子集。接下來(lái), 將數(shù)據(jù)投影到奇異向量的最佳子集并進(jìn)行聚類(lèi)。
例如，如果計(jì)算 個(gè)奇異向量，因?yàn)?$q
示例:
譜協(xié)聚類(lèi)算法的一個(gè)示例: 一個(gè)簡(jiǎn)單的示例，展示如何生成棋盤(pán)矩陣并對(duì)它進(jìn)行雙向聚類(lèi)。 參考資料:
Kluger, Yuval, et. al., 2003. Spectral biclustering of microarray data: coclustering genes and conditions.
2.4.3. Biclustering 評(píng)價(jià)
評(píng)估雙聚類(lèi)結(jié)果有兩種方法：內(nèi)部和外部。內(nèi)部度量,如聚類(lèi)穩(wěn)定性, 只依賴(lài)于數(shù)據(jù)和結(jié)果本身。目前scikit-learn還沒(méi)有內(nèi)部的雙向簇度量。外部度量是指外部信息來(lái)源，例如真實(shí)解。當(dāng)處理真實(shí)數(shù)據(jù)時(shí)，真實(shí)解通常是未知的，但是，雙聚類(lèi)人工數(shù)據(jù)可能有助于精確地評(píng)估算法，因?yàn)檎鎸?shí)解是已知的。
為了將一組已發(fā)現(xiàn)的雙向簇與一組真實(shí)的雙向簇行比較，需要兩種相似性度量：一種是單個(gè)雙向簇的相似性度量，另一種是將這些個(gè)體相似度整合到整體得分中的方法。
為了比較單個(gè)雙向簇，采用了幾種方法。現(xiàn)在，目前只執(zhí)行 Jaccard 索引：
其中Ａ和Ｂ是雙向簇, ｜Ａ∩Ｂ｜ 是交叉點(diǎn)的元素?cái)?shù)量。
Jaccard 索引達(dá)到最小值0，當(dāng)biclusters完全不同時(shí)，Jaccard指數(shù)最小值為0;當(dāng)biclusters完全相同時(shí)，Jaccard指數(shù)最大值為1。
已經(jīng)開(kāi)發(fā)了幾種方法來(lái)比較兩個(gè)雙向簇的集合。目前，只有consensus_score（Hochreiter等人，2010）可用：
使用Jaccard索引或類(lèi)似度量， 為每個(gè)集合中的雙向簇對(duì)計(jì)算簇之間的相似性。 以一對(duì)一的方式將雙向簇從一個(gè)集合分配給另一個(gè)集合，以最大化他們的相似性之和。使用匈牙利算法(Hungarian algorithm)執(zhí)行此步驟。 最終的相似度之和除以較大集合的大小。
當(dāng)所有雙向簇對(duì)都完全不相似時(shí)，將出現(xiàn)最低共識(shí)分?jǐn)?shù)0。當(dāng)兩個(gè)雙向簇集合相同時(shí)，出現(xiàn)最高分?jǐn)?shù)為1。
參考文獻(xiàn):
Hochreiter, Bodenhofer, et. al., 2010. FABIA: factor analysis for bicluster acquisition.
更多建議：