淺述雙聚類算法

摘要：雙聚類（Biclustering）算法在數(shù)據(jù)挖掘中是一個新興的算法，對于矩陣類型的數(shù)據(jù)，其聚類效果很好。本文淺述了雙聚類算法的基本特點，并提出了用迭代的雙聚類算法對未知的數(shù)據(jù)進(jìn)行分類，并對一組數(shù)據(jù)進(jìn)行了測試，其分類表現(xiàn)不錯。

關(guān)鍵詞：雙聚類；數(shù)據(jù)挖掘；迭代；分類

雙聚類基礎(chǔ)的可以定義為：給定矩陣M，尋找到矩陣M的多個子矩陣A，對于每一個A滿足其指定條件進(jìn)行聚類，最后得到需要的子矩陣B。雙聚類方法可在以下一個或者多個問題下使用：1.僅僅是一小部分基因參與的有趣的細(xì)胞作用過程的聚類。2.對于一部分特定條件下的細(xì)胞作用過程體現(xiàn)為活躍的。3.單個基因可以在多重維度路徑下并且全局限制條件對其沒限制，可以是活躍的也可以是不活躍的。因此，對于雙聚類也得遵循下面約束：1.基因簇按給定特定的部分條件能夠被聚類出來。2.聚簇的條件按基因子集能夠被清晰定義。3.聚簇不是被獨占的和/或全體占有的：一個基因/條件可以屬于一個簇或者都不屬于在一個子集的條件/基因下。

一.基本分類

雙聚類是應(yīng)用各種算法得到在條件子集下具有共同表達(dá)模式的基因子集。得到的雙聚簇一般具有以下幾種樣式：

1.常值型：即得到的雙聚簇中基因的表達(dá)水平為一個常數(shù)，如表1.a

2.行或者列為一個常數(shù)：即在一個雙聚簇中，每個基因的表達(dá)水平為一個常量，或者再一個條件下的所有基因的表達(dá)水平為一個常量。如表1.b和表1.c。

3.一致性變化：在一個雙聚簇中，基因間得表達(dá)水平相差一個常量，雙聚簇表1.e中的基因之間的表達(dá)水平成倍數(shù)關(guān)系。

計算刪除每行和每列后的矩陣的H值，選擇使H值減少幅度最大的行或者列，刪除該行或者該列，返回AIJ，直到找不到這樣的行或者列為止。

雙聚類也可用于基因表達(dá)的進(jìn)化演算上面去，在基因的進(jìn)化演算中使用到雙聚類的一個算法叫做SEBI算法，它可以發(fā)現(xiàn)雙聚簇通過表達(dá)數(shù)據(jù)。而且SEBI算法在進(jìn)行數(shù)據(jù)集觀察和實驗時不需要設(shè)置參數(shù)，他可以在一個實驗條件集中清晰的找出基因集合的上相似約束和下相似約束?？偟膩碚fSEBI算法可以在基因表達(dá)數(shù)據(jù)中找出狡猾難尋的和擴(kuò)大縮小后的模式。

雙聚類運用的領(lǐng)域也是很廣的，他不單單是用在我上面提到的基因表達(dá)上，因為他主要解決了基因表達(dá)問題，所以上面都是以這個為例子來說。雙聚類可以應(yīng)用在生物上也可以應(yīng)用在非生物學(xué)上，在生物學(xué)上很多學(xué)者都已經(jīng)用大量的實驗證實是相當(dāng)有用的。比如用微陣列技術(shù)收集酵母菌細(xì)胞和人類細(xì)胞，研究他們在特定條件下的基因表達(dá)等級。在非生物學(xué)上的應(yīng)用也很多，比如信息恢復(fù)，文本挖掘，協(xié)同過濾，數(shù)據(jù)庫搜索，知識挖掘等方面都有廣泛的應(yīng)用。Gaul and Schader在此中介紹了雙聚類于市場調(diào)查的關(guān)聯(lián)性，他們用數(shù)據(jù)基準(zhǔn)陣列去封裝營銷中收集到的數(shù)據(jù)，然后通過雙聚類算法來得出給定條件下的子矩陣，如此實現(xiàn)調(diào)查。

但是雙聚類在對于邊界噪聲點比較多，實驗效果差，或者是圖形圖像比較模糊的數(shù)據(jù)還是很難進(jìn)行聚類的，這個同時也約束了他的使用范圍。我想這個可以通過結(jié)合模糊聚類的話可能可以解決一些問題。而且微陣列通常不滿足正態(tài)分布，因此在數(shù)據(jù)分析上面也有一定的局限性。我認(rèn)為微陣列的不足可以嘗試使用貝葉斯算法統(tǒng)計來試試。

二.相關(guān)工作

可以嘗試用雙聚類算法對未知的數(shù)據(jù)進(jìn)行分類。如在生物信息中有矩陣類型的數(shù)據(jù)，行表示樣本，列代表基因，那么這類數(shù)據(jù)是可以用雙聚類算法對其進(jìn)行歸類和劃分的。算法會用到迭代對類別進(jìn)行區(qū)分。使用威斯康辛乳腺癌數(shù)據(jù)集，有569個樣本，30個基因，分為兩類http：//archive.ics.uci.edu/ml/machine-learning-databases/breast-cancer-wisconsin/wdbc.data，以上是數(shù)據(jù)地址。算法步驟如下：

輸入：數(shù)據(jù)矩陣M，殘基選擇的閾值H，基因占總樣本的比為T。

輸出：多個子矩陣。

1.計算矩陣M的殘基，如果小于H，直接輸出，否則進(jìn)入2.（直接輸出就是分為一類了）

2.找出行或者列中殘基最大的，進(jìn)行刪除，直到子矩陣M1的殘基小于H為止。

3.對M1進(jìn)行行或者列的增加，計算與當(dāng)前矩陣行或者列對應(yīng)的行或者列的殘基，把最小的進(jìn)行增加，直到預(yù)判增加后子矩陣M2的殘基大于H，則最后這一行或者列不添加。

4.對找出的子矩陣M2進(jìn)行基因占比計算，小于T則終止（第一個就小于T則說明應(yīng)全部歸為一類或者T的選擇不合適或者算法不適用這數(shù)據(jù)），大于T則在原始矩陣M中刪除M2所包含的列（樣本）得到M3。

5.迭代地對M3進(jìn)行2-4.

6.直到出現(xiàn)小于T，則判定無其他分類，剩余的歸為一類。

用了準(zhǔn)確率，召回率，支持?jǐn)?shù)，這三個指標(biāo)來衡量分類準(zhǔn)確性。

三.總結(jié)

雙聚類在生物上的發(fā)展是有很大很大的空間的，當(dāng)然在其他領(lǐng)域上也是一樣，這是一個很廣很實用的方法，而且現(xiàn)在也只是雙聚類發(fā)展的起步，他將會在以后的研究中迅速發(fā)展起來，更加全面更加實用。

參考文獻(xiàn)

[1]Y.Cheng and G.M.Church.“Biclustering of expression data”.In Proc.ISMB’00，pages 93–103.AAAI Press，2000.

作者簡介：肖志軍（1975-），男，江西崇義人，高級工程師，碩士，主要研究方向：數(shù)據(jù)挖掘，人工智能。