最大生成樹聚類算法研究

摘 要：在生物學(xué)研究中，需要對基因進(jìn)行分類，以獲得對種群固有結(jié)構(gòu)的認(rèn)識，有效鑒別基因表示數(shù)據(jù)的模式是研究DNA序列的重要基礎(chǔ)。在已有最大樹聚類理論基礎(chǔ)上，引入模糊聚類思想，提出了最大樹基因聚類算法，同時將該方法用于基因的聚類分析，實驗結(jié)果表明它們是有效可行的。

關(guān)鍵詞：最大生成樹；模糊聚類；簇；相關(guān)系數(shù)；基因

中圖分類號：TP311

文獻(xiàn)標(biāo)識碼：A 文章編號：1672-7800（2015）005-0068-02

作者簡介：劉芳（1979-），女，遼寧沈陽人，碩士，沈陽理工大學(xué)理學(xué)院講師，研究方向為應(yīng)用數(shù)學(xué)與計算機(jī)輔助幾何設(shè)計。

0 引言

近年來，隨著人們對生命科學(xué)的深入研究，開發(fā)出許多用于基因分析的工具[2]。利用這些工具，在不同的試驗條件下，人們能夠?qū)Τ汕先f個基因進(jìn)行實時監(jiān)控，以研究由于環(huán)境變化引起的基因變化。因此，首先對大量的基因表示數(shù)據(jù)進(jìn)行分類，有效地鑒別基因表示數(shù)據(jù)的模式是研究DNA序列的重要基礎(chǔ)。

聚類分析是統(tǒng)計學(xué)的一個分支，聚類算法能從空間數(shù)據(jù)庫中直接發(fā)現(xiàn)一些有意義的聚類結(jié)構(gòu)。聚類分析以相似性為基礎(chǔ)，在一個聚類中的模式比不在同一聚類中的模式之間具有更多相似性。聚類分析算法有劃分法、層次法、基于密度的方法、基于網(wǎng)格的方法和基于模型的方法等。但傳統(tǒng)的聚類分析把每個待辨識的對象嚴(yán)格地劃分到某個類中，這種硬劃分的界線是分明的。而客觀世界中存在大量界限不分明的聚類問題，它們的類屬和性態(tài)存在著中介性，適合軟劃分。Zadeh提出的模糊集理論[3]為這種軟劃分提供了有力的分析工具，人們開始用模糊方法處理聚類問題，并稱之為模糊聚類分析。常用的模糊聚類方法有傳遞閉包法、動態(tài)直接聚類法、最大樹法[2]、基于攝動的模糊聚類方法FCMBP、系統(tǒng)聚類法、模糊C-均值法和模糊ISODATA算法。

本文把最大生成樹法用于模糊聚類分析，最大生成樹可以將數(shù)據(jù)聚類轉(zhuǎn)換成樹分割問題，通過刪除最大生成樹中某些具有最短距離的邊，將最大生成樹分為若干子樹。本文討論數(shù)據(jù)集的最大生成樹表示，以及相應(yīng)的聚類分析方法，并將其用于基因分類。

1 用生成樹表示數(shù)據(jù)

2 最大生成樹聚類算法

楊國惠[4]等人提出改進(jìn)的中心聚類算法，本文在此基礎(chǔ)上又提出最大生成樹的基因聚類算法，同時通過實例驗證了此算法可以得到較好結(jié)果。算法描述如下：具有較長邊的兩個點應(yīng)屬于同一個簇，具有較短邊的兩個點應(yīng)屬于不同的簇，并將被分割。由推論1，通過清除最大生成樹中具有最小距離的k-1條邊可得到k個簇，只要不同簇之間點的邊距離小于簇內(nèi)點的邊距離，這k個簇則是全局最優(yōu)解。但是，當(dāng)不同簇沒有用短距離邊而是一系列長距離邊連接，或者當(dāng)存在“噪聲”和孤立點數(shù)據(jù)時，該方法可能得不到最好的聚類結(jié)果。為了自動決定應(yīng)該進(jìn)行多少次有效分割，可在分割算法中檢測新產(chǎn)生的子樹是否為孤立點，通過消除孤立點并增加有效分割次數(shù)，最終獲得正確的k個簇。

2.1 算法程序?qū)崿F(xiàn)

開始

輸入：數(shù)據(jù)集data和聚類數(shù)目K

begin

weight←compute_weight（data）；{計算距離矩陣}

t←{1，2，3，…，data_number}；

m=0；

查找weight中的最大值所在的行列值（x，y）；

while（m～= data_number-cluster_number）

begin

if（t（x）～=t（y））

begin

m=m+1；

tree（1，m）=x（1）；

tree（2，m）=y（1）；

tmin=min（t（x（1）），t（y（1）））；

tmax=max（t（x（1）），t（y（1）））；

for j=1：datanumber

if（t（j）==tmax）

t（j）=tmin；

end

weight（x，y） ←∞；

查找weight中的最大值所在的行列值（x，y）；

end

由tree得到聚類結(jié)果cluster；

計算聚類誤差平方和cluster_err；

計算q值；

end

輸出：聚類cluster、誤差平方和cluster_err，q值；

結(jié)束

3 實驗結(jié)果與評價

現(xiàn)選擇酵母數(shù)據(jù)集[5]，此數(shù)據(jù)集中每個基因有79個屬性（或79維），選擇4個聚類共68個基因，這4個聚類分別為protein degradation（聚類C）、glycolysis（聚類E）、protein synthesis（聚類F）、 protein chromatin（聚類H）。

這個實驗的目的是將最大生成樹基因聚類算法應(yīng)用到基因聚類中，同時說明該算法是可行、有效的。為了評價計算結(jié)果，使用以下定義。

誤差平方和J（k）的定義如下：

J（k）=∑ki=1∑d∈Tid-center（Ti）2（5）

對于用戶選擇的目標(biāo)函數(shù)和一個整數(shù)值K，計算最優(yōu)k聚類k∈[1，K]，然后比較這些值。設(shè)J（k）代表選擇的目標(biāo)函數(shù)最佳k聚類的值，里面的k∈[2，K-1]，q（k）的最大值作為最自然的聚類數(shù)：

q（k）=J（k-1）-J（k）J（k）-J（k+1）（6）

距離測度采用公式（2）。

從圖像中可以看到最大生成樹基因聚類算法的最佳聚類數(shù)是4，分類的結(jié)果完全一致（見圖1）[1]。

4 結(jié)語

本文在已有最大樹聚類理論基礎(chǔ)上，引入模糊聚類思想，提出了最大樹基因聚類算法，對基因數(shù)據(jù)的聚類分析有重要的實踐價值。特別對于生物學(xué)DNA序列信息、蛋白質(zhì)結(jié)構(gòu)信息的分類更具有意義。

參考文獻(xiàn)：

[1] YING XU， VICTOR OLMAN， DONG XU.Clustering gene expression data using a graph-theoretic approach： an application of minimum spanning trees[J]. Bioinformatics， 2002， 18（4）：526-545.

[2] HATHAWAY R J，BEZDEK J C.Optimization of clustering criteria by reformulation[J].IEEE Transactions Fuzzy Systems，1995，3（2）：241-245.

[3] ZADEH L A. Fuzzy sets [J].Information and contral，1965（8）：338-353.

[4] 楊國惠，周春光，等. 最小生成樹用于基因表示數(shù)據(jù)的聚類算法[J].計算機(jī)研究與發(fā)展，2003，40（10）：1431-1435.

[5] M B EISEN，P T SPELLMAN，P O BROWN，et al.Cluster analysis and display of gene-wide expression patterns[J]. The National Academic of Science，N W，1998.

（責(zé)任編輯：黃 ?。?