一種加權(quán)K—均值基因聚類算法

姚登舉+詹曉娟+張曉晶

摘要：針對微陣列表達(dá)數(shù)據(jù)集中基因-基因之間存在復(fù)雜相關(guān)關(guān)系的問題，基于隨機(jī)森林變量重要性分?jǐn)?shù)，提出了一種新的加權(quán)K-均值基因聚類算法。首先，以微陣列表達(dá)數(shù)據(jù)中的樣本為對象、基因?yàn)樘卣鳎?xùn)練隨機(jī)森林分類器，計(jì)算每個(gè)基因的變量重要性分?jǐn)?shù)；然后，以基因?yàn)閷ο?、樣本為特征、基因的變量重要性分?jǐn)?shù)為權(quán)重進(jìn)行K-均值聚類。在Leukemia、Breast、DLBCL等3個(gè)微陣列表數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn)，結(jié)果表明：所提出的加權(quán)K-均值聚類算法與原始的K-均值聚類算法相比，類間距離與總距離的比值平均高出177個(gè)百分點(diǎn)，具有更好的同質(zhì)性和差異性。

關(guān)鍵詞：微陣列表達(dá)數(shù)據(jù)；聚類分析；隨機(jī)森林；K-均值

DOI：1015938/jjhust201702021

中圖分類號： TP391

文獻(xiàn)標(biāo)志碼： A

文章編號： 1007-2683（2017）02-0112-05

Abstract：In view of the complex correlation between gene and gene in the microarray data set， a weighted K mean gene clustering algorithm based on random forest variable importance score was proposed First， the proposed algorithm begins with training random forest classifier on the microarray data， using the samples as objects and the genes as features， variable importance scores were calculated for each gene； then， a weighted Kmeans clustering were performed with genes as objects， samples as features， and variable importance score as weighted value Experiments were carried out on Leukemia， Breast and DLBCL three datasets The experimental results show that the proposed weighted K mean clustering algorithm has an average of 177 percentage points higher than the original K mean clustering algorithm with respective to the ratio of the distance between the class and the total distance and has better homogeneity and difference

Keywords：microarray expression data； clustering analysis； random forest； Kmeans

0引言

聚類是將物理或抽象對象的集合分組為由類似的對象組成的多個(gè)集合的過程，其中屬于同一個(gè)集合的對象之間彼此相似，屬于不同集合的對象之間彼此相異[1]。聚類是機(jī)器學(xué)習(xí)和數(shù)據(jù)挖據(jù)中的重要研究內(nèi)容，被廣泛應(yīng)用于經(jīng)濟(jì)、管理、地質(zhì)勘探、圖像識別、生物醫(yī)學(xué)、生物信息學(xué)等領(lǐng)域中[2-6]。隨著高通量測序技術(shù)（Highthroughput Sequencing）的迅速發(fā)展，各物種的基因表達(dá)數(shù)據(jù)（Gene expression data）出現(xiàn)了爆炸式增長，同時(shí)大量的基因表達(dá)數(shù)據(jù)能夠在公共數(shù)據(jù)庫（如由美國NCBI管理和維護(hù)的GEO數(shù)據(jù)庫、由美國斯坦福大學(xué)管理和維護(hù)的SMD數(shù)據(jù)庫、由歐洲EBI管理和維護(hù)的ArraryExpress數(shù)據(jù)庫和由日本多所大學(xué)合作提供的CGED數(shù)據(jù)庫等）中得到[7-11]。在基因表達(dá)數(shù)據(jù)分析任務(wù)中，基因聚類分析有著非常廣泛的應(yīng)用。當(dāng)前，基因聚類分析方法主要有三類：基于基因的聚類（Genebased clustering）、基于樣本的聚類（Samplebased clustering）和兩路聚類（Biclustering）[12，13]。基于基因的聚類將基因看成聚類的對象，將樣本看成描述基因的特征，表達(dá)模式類似的基因（即共表達(dá)的基因，Coexpression gene）通常被劃分為同一類，一般具有相同的功能，因此可以根據(jù)聚類中已知基因的功能推斷某些未知基因的功能；基于樣本的聚類則以基因?yàn)樘卣鳎詷颖緸閷ο?，通過樣本聚類，可以發(fā)現(xiàn)樣本的顯性結(jié)構(gòu)（Phenotype structure），自動對病理特征或?qū)嶒?yàn)條件進(jìn)行分類；兩路聚類是指同時(shí)對基因和樣本進(jìn)行的聚類，目的是找出在某些條件下參與調(diào)控的基因聚類以及與某些基因相關(guān)聯(lián)的條件，從而更精確、更細(xì)致地探索基因和樣本間的相互關(guān)系。

基因聚類的主要對象是基因表達(dá)微陣列數(shù)據(jù)。原始的基因表達(dá)微陣列數(shù)據(jù)中存在著大量的冗余基因、噪聲基因和不相關(guān)基因，并且研究表明，對于某類疾病的發(fā)生發(fā)展，通常是多個(gè)基因共同作用的結(jié)果，亦即基因表達(dá)微陣列中多個(gè)基因之間存在著復(fù)雜的相互作用，所以一般的基于統(tǒng)計(jì)的度量標(biāo)準(zhǔn)，如皮爾森相關(guān)系數(shù)、信息熵等，難以準(zhǔn)確地表達(dá)基因的相對重要性[14]。隨機(jī)森林作為一種流行的機(jī)器學(xué)習(xí)算法，由于在訓(xùn)練決策樹的過程中，既考慮了單個(gè)變量對于目標(biāo)變量的影響，又考慮了多個(gè)變量之間的相互作用，其變量重要性分?jǐn)?shù)被廣泛應(yīng)用于評價(jià)數(shù)據(jù)集中特征變量的相對重要性，尤其是應(yīng)用在生物醫(yī)學(xué)與生物信息學(xué)研究中[15-17]。當(dāng)前，基于隨機(jī)森林和K-均值聚類相結(jié)合的方法已經(jīng)被應(yīng)用在網(wǎng)絡(luò)入侵檢測[18]等研究中，然而在基因聚類任務(wù)中，基于隨機(jī)森林變量重要性分?jǐn)?shù)對基因進(jìn)行加權(quán)聚類研究較少，仍然是一個(gè)值得探索的領(lǐng)域。本文主要針對基于基因的聚類分析任務(wù)，將隨機(jī)森林的變量重要性分?jǐn)?shù)引入到K-均值聚類的過程中，提出了一種基于隨機(jī)森林變量重要性分?jǐn)?shù)的加權(quán)K-均值聚類算法，能夠提高基因聚類結(jié)果的質(zhì)量。

1算法設(shè)計(jì)

12隨機(jī)森林

隨機(jī)森林（Random Forest，RF）[19]是一個(gè)由一組決策樹分類器{h（X，θk），k=1，2，，K}組成的集成分類器，其中θk是服從獨(dú)立同分布的隨機(jī)向量，K表示隨機(jī)森林中決策樹的個(gè)數(shù)，在給定自變量X下，每個(gè)決策樹分類器通過投票來決定最優(yōu)的分類結(jié)果[5]。隨機(jī)森林是許多決策樹集成在一起的分類器，如果把決策樹看成分類任務(wù)中的一個(gè)專家，隨機(jī)森林就是許多專家在一起對某種任務(wù)進(jìn)行分類。生成隨機(jī)森林的步驟如下[20]：

1）從原始訓(xùn)練數(shù)據(jù)集中，應(yīng)用Bootstrap方法有放回地隨機(jī)抽取K個(gè)新的自助樣本集，并由此構(gòu)建K棵分類回歸樹，每次未被抽到的樣本組成了K個(gè)袋外數(shù)據(jù)（outofbag， OOB）。

2）設(shè)有n個(gè)特征，則在每一棵樹的每個(gè)節(jié)點(diǎn)處隨機(jī)抽取mtry個(gè)特征（mtry<=n），通過計(jì)算每個(gè)特征蘊(yùn)含的信息量，在mtry個(gè)特征中選擇一個(gè)最具有分類能力的特征進(jìn)行節(jié)點(diǎn)分裂。

3）每棵樹最大限度生長，不做任何剪裁。

4）將生成的多棵樹組成隨機(jī)森林，用隨機(jī)森林對新的數(shù)據(jù)進(jìn)行分類，分類結(jié)果按樹分類器的投票多少而定。

由于決策樹算法在節(jié)點(diǎn)分裂過程中考慮了特征之間的相互影響，隨機(jī)森林算法能夠有效地揭示多個(gè)特征之間的相互作用，對于單個(gè)特征具有小的邊際效應(yīng)但多個(gè)特征的組合對目標(biāo)變量有較大影響的數(shù)據(jù)集合，表現(xiàn)出優(yōu)異的分類和預(yù)測性能，而且隨機(jī)森林算法不需要先驗(yàn)假設(shè)[7]。目前，RF已經(jīng)被廣泛應(yīng)用于各種分類、預(yù)測、變量重要性研究、特征選擇以及異常點(diǎn)檢測問題中，尤其在生物醫(yī)學(xué)和生物信息學(xué)領(lǐng)域，隨機(jī)森林由于能識別多個(gè)特征變量之間的相互作用而受到青睞[21-22]。

隨機(jī)森林算法的一個(gè)重要產(chǎn)物是變量重要性分?jǐn)?shù)，它可以很好地反映訓(xùn)練數(shù)據(jù)集中分類變量對于目標(biāo)變量的影響程度，目前，隨機(jī)森林變量重要性分?jǐn)?shù)已經(jīng)被廣泛應(yīng)用于各種數(shù)據(jù)挖掘任務(wù)中。隨機(jī)森林提供了4種變量重要性分?jǐn)?shù)供選擇，本文采用基于置換的變量重要性分?jǐn)?shù)[16]?；谥脫Q的變量重要性分?jǐn)?shù)定義為在袋外數(shù)據(jù)（OOB）上當(dāng)變量發(fā)生輕微擾動前后分類模型的分類正確率的平均減少量，它采用了直覺排列策略，既考慮到每一個(gè)變量單獨(dú)的影響，又考慮了多個(gè)變量之間的相關(guān)作用。

給定訓(xùn)練樣本集合D，集合中的特征標(biāo)記為Xj，j=1，2，，N，Xj的基于置換的變量重要性分?jǐn)?shù)表示為IMj，則IMj的計(jì)算過程如下[20]：

1）對訓(xùn)練集D進(jìn)行Bootstrap隨機(jī)重采樣B次，得到B個(gè)樣本子集Db，b=1，2，，B；

2）設(shè)置b=1；

3）在樣本集合Db上訓(xùn)練決策樹Tb，袋外數(shù)據(jù)標(biāo)記為Loobb；

4）在袋外數(shù)據(jù)Loobb上，應(yīng)用決策樹分類器Tb對測試數(shù)據(jù)進(jìn)行分類，正確分類的樣本個(gè)數(shù)標(biāo)記為Roobb；

5）對特征Xj，j=1，2，，N，隨機(jī)地?cái)_動Loobb中每一個(gè)樣本直到它與目標(biāo)變量的原始關(guān)系被打斷，擾動后的數(shù)據(jù)集標(biāo)記為Loobbj；

6）在擾動后的數(shù)據(jù)集Loobbj上，應(yīng)用決策樹分類器Tb對數(shù)據(jù)進(jìn)行分類，正確分類的樣本個(gè)數(shù)標(biāo)記為Roobbj；如果特征Xj與目標(biāo)變量相關(guān)，那么分類器的分類性能將明顯降低；

7）對于b=2，，B，重復(fù)第3）-6）步；

8）按照下式計(jì)算特征Xj的變量重要性分?jǐn)?shù)：

IMj=1B∑Bi=1Roobb-Roobbj；

9）輸出所有特征的重要性分?jǐn)?shù)：

IM={IM1，IM2，，IMN}。

13基于隨機(jī)森林變量重要性分?jǐn)?shù)的加權(quán)K-均值基因聚類算法

基因數(shù)據(jù)通常以DNA微陣列表達(dá)數(shù)據(jù)形式存儲。一般而言，微陣列表達(dá)數(shù)據(jù)集是一個(gè)N×（M+1） 的矩陣，矩陣中的每一行表示一個(gè)樣本，除最后列以外的每一列表示該樣本的一個(gè)基因，每一個(gè)元素gi，j是一個(gè)數(shù)值，表示第i個(gè)樣本第j個(gè)基因的基因表達(dá)水平，最后一列表示第i個(gè)樣本的類標(biāo)簽，如圖1所示。

g1，1g1，2…g1，MC1

g2，1g2，2…g2，MC2

……………

gN，1gN，2…gN，MCN

2實(shí)驗(yàn)與結(jié)果分析

21數(shù)據(jù)集

為了驗(yàn)證本文提出的算法的有效性，在Leukemia（白血?。reast（乳腺癌）、DLBCL（彌漫性大B細(xì)胞淋巴瘤）等3個(gè)微陣列表數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn)。這些數(shù)據(jù)集的基本信息如表1所示。

原始的微陣列表達(dá)數(shù)據(jù)集中通常包含大量的噪聲基因，為了降低計(jì)算時(shí)間和存儲空間需求，在執(zhí)行基因聚類分析之前首先采用四分位距方法和單因素方差分析法來過濾掉明顯不相關(guān)的基因和噪聲基因，所有表達(dá)水平低于總體IQR 1/5的基因在這一步被過濾掉?；蜻^濾后的數(shù)據(jù)信息如表2所示。

23實(shí)驗(yàn)結(jié)果及分析

在3個(gè)實(shí)驗(yàn)數(shù)據(jù)集上對原始的K-均值算法和本文提出的基于隨機(jī)森林變量重要性分?jǐn)?shù)的加權(quán)K-均值算法進(jìn)行了實(shí)驗(yàn)，指定聚類數(shù)目k=100，最大迭代次數(shù)T=60。采用類內(nèi)離散度和J和類間加權(quán)距離和D指標(biāo)來衡量算法的性能，10次實(shí)驗(yàn)結(jié)果的平均值如表3所示。

從表3可以看出，本文提出的基于隨機(jī)森林變量重要性分?jǐn)?shù)的加權(quán)K-均值聚類算法的J值明顯低于原始的K-均值算法，說明類內(nèi)基因表達(dá)模式高度相關(guān)；所提出的算法的R值比原始的K-均值算法平均高177個(gè)百分點(diǎn)，表明基于隨機(jī)森林變量重要性分?jǐn)?shù)的加權(quán)K-均值聚類算法得到的聚類劃分中，類間差異比原始的K-均值聚類算法顯著。

3結(jié)語

提出了一種基于隨機(jī)森林變量重要性分?jǐn)?shù)的加權(quán)K-均值基因聚類算法，相對于原始的K-均值聚類算法，該算法能夠有效地提高類內(nèi)相似度和類間差異度，即提高聚類結(jié)果的質(zhì)量。如何針對基因表達(dá)數(shù)據(jù)的特點(diǎn)，選擇或設(shè)計(jì)合適的聚類準(zhǔn)則函數(shù)，利用本文提出的算法探索生物醫(yī)學(xué)信息，有待于進(jìn)一步研究。

參 考 文 獻(xiàn)：

[1]周志華.機(jī)器學(xué)習(xí)[M].北京：清華大學(xué)出版社，2016：211-213

[2]劉帥，林克正，孫旭東，等.基于聚類的SIFT人臉檢測算法[J].哈爾濱理工大學(xué)學(xué)報(bào)，2014，19（1）：31-35

[3]吳娛，鐘誠，尹夢曉.基因表達(dá)數(shù)據(jù)的分層近鄰傳播聚類算法[J].計(jì)算機(jī)工程與設(shè)計(jì)，2016，37（11）：2961-2966

[4]陳偉，程詠梅，張紹武，潘泉.鄰域種子的啟發(fā)式454序列聚類方法[J].軟件學(xué)報(bào)，2014，25（5）：929-938

[5]黃偉華，馬中，戴新發(fā)，徐明迪，高毅，劉利民.一種特征加權(quán)模糊聚類的負(fù)載均衡算法[J].西安電子科技大學(xué)學(xué)報(bào)（自然科學(xué)報(bào)），2017，44（2）：138-143

[6]余曉東，雷英杰，岳韶華，王睿.基于粒子群優(yōu)化的直覺模糊核聚類算法研究[J].通信學(xué)報(bào)，2015，36（5）：1-7

[7]李霞，雷健波，李亦學(xué)，李勁松.生物信息學(xué)[M].北京：人民衛(wèi)生出版社，2015：286-287

[8]李雨童，姚登舉，李哲，侯金利.基于R的醫(yī)學(xué)大數(shù)據(jù)挖掘系統(tǒng)研究[J].哈爾濱理工大學(xué)學(xué)報(bào)，2016，21（2）：38-43

[9]高敬陽，齊飛，管瑞.基于高通量測序技術(shù)的基因組結(jié)構(gòu)變異檢測算法[J].生物信息學(xué)，2014，12（1）：5-9

[10]李晟，程福東，孫嘯.高通量DNA測序技術(shù)與疾病診斷及預(yù)防[J].生物醫(yī)學(xué)工程與臨床，2016，20（2）：210-215

[11]吳林寰，陸震鳴，龔勁松，史勁松，許正宏.高通量測序技術(shù)在食品微生物研究中的應(yīng)用[J].生物工程學(xué)報(bào)，2016，32（9）：1164-1174

[12]岳峰，孫亮，王寬全，王永吉，左旺孟.基因表達(dá)數(shù)據(jù)的聚類分析研究進(jìn)展[J].自動化學(xué)報(bào)，2008，34（2）：113-120

[13]張國印，程慧杰，劉詠梅，姚愛紅.一種新算法在基因表達(dá)譜聚類中的應(yīng)用[J].計(jì)算機(jī)工程與應(yīng)用，2009，45（36）：216-218

[14]王愛國.微陣列基因表達(dá)數(shù)據(jù)的特征分析方法研究[D].安徽：合肥工業(yè)大學(xué)，2015：1-5

[15]ALI Anaissi， PAUL J KENNEDY， Madhu Goyal1 Daniel R Catchpoole A Balanced Iterative Random Forest for Gene Selection from Microarray Data[J] BMC Bioinformatics， 2013， 14： 261P

[16]QI， Y Random Forest for Bioinformatics [J]. Ensemble Machine Learning， 2012： 307-323

[17]孫磊，許馳，胡學(xué)龍.一種基于隨機(jī)森林的長非編碼RNA預(yù)測方法[J].揚(yáng)州大學(xué)學(xué)報(bào)：自然科學(xué)版，2016，19（4）：50-53

[18]ELBASIONY R M， SALLAM E A， ELTOBELY T E， et al A Hybrid Network Intrusion Detection Framework Based on Random Forests and Weighted kmeans [J]. Ain Shams Engineering Journal， 2013， 4（4）：753-762

[19]BREINMAN L Random Forests [J]. Machine Learning， 2001， 45： 5–32

[20]姚登舉，楊靜，詹曉娟.基于隨機(jī)森林的特征選擇算法[J].吉林大學(xué)學(xué)報(bào)工學(xué)版，2014，44（1）：137-141

[21]VERIKAS A，GELZINIS A，BACAUSKIENE M Mining Data with Random Forests： A Survey and Results of New Tests [J]. Pattern Recognition， 2011， 44： 330–349

[22]劉勘，袁蘊(yùn)英，劉萍.基于隨機(jī)森林分類的微博機(jī)器用戶識別研究[J].北京大學(xué)學(xué)報(bào)（自然科學(xué)版），2015，51（2）：289-300

（編輯：王萍）