劉亞卿,陸慧娟，杜幫俊，余 翠

(中國(guó)計(jì)量學(xué)院 信息工程學(xué)院,浙江 杭州 310018)

面向基因數(shù)據(jù)分類的旋轉(zhuǎn)森林算法研究

劉亞卿,陸慧娟，杜幫俊，余 翠

(中國(guó)計(jì)量學(xué)院 信息工程學(xué)院,浙江 杭州 310018)

針對(duì)基因表達(dá)數(shù)據(jù)高維和小樣本的特點(diǎn),介紹一種基于主成分分析的決策樹(shù)集成分類算法——旋轉(zhuǎn)森林.首先通過(guò)對(duì)數(shù)據(jù)屬性集的隨機(jī)分割,再對(duì)子集進(jìn)行主成分分析變換,保留全部的主成分系數(shù),重新組成一個(gè)稀疏矩陣.然后對(duì)變換后的數(shù)據(jù)利用非剪枝決策樹(shù)集成算法進(jìn)行分類.再結(jié)合ReliefF算法,選用3組基因表達(dá)數(shù)據(jù)驗(yàn)證算法,對(duì)比Bagging決策樹(shù)和隨機(jī)森林兩種集成方法.結(jié)果表明旋轉(zhuǎn)森林算法對(duì)基因數(shù)據(jù)具有更好的分類精度,同時(shí)驗(yàn)證旋轉(zhuǎn)森林在較低的集成數(shù)的情況下,可以取得良好的效果.

主成分分析;旋轉(zhuǎn)森林;集成學(xué)習(xí);ReliefF算法;決策樹(shù)

在生物醫(yī)學(xué)領(lǐng)域,基因芯片技術(shù)可以檢測(cè)大規(guī)模的基因表達(dá)數(shù)據(jù),可以實(shí)現(xiàn)基因檢測(cè)的快速、高通量、敏感和高效率檢測(cè),將可能為臨床疾病診斷和健康監(jiān)測(cè)等領(lǐng)域,提供一種高通量和系統(tǒng)性的研究手段.因表達(dá)數(shù)據(jù)具有分布不平衡、樣本小、維數(shù)高的特點(diǎn),應(yīng)該如何對(duì)基因表達(dá)數(shù)據(jù)進(jìn)行分析,是當(dāng)前機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘領(lǐng)域內(nèi)的一個(gè)研究熱點(diǎn).目前已經(jīng)有很多比較成熟的單分類器,比如貝葉斯、決策樹(shù)、神經(jīng)網(wǎng)絡(luò)、支持向量機(jī)以及極限學(xué)習(xí)機(jī)等,但是有些單分類器由于存在隨機(jī)賦值而具有分類不穩(wěn)定的缺點(diǎn),例如神經(jīng)網(wǎng)絡(luò)和極限學(xué)習(xí)機(jī).同時(shí)集成學(xué)習(xí)在應(yīng)對(duì)非平衡數(shù)據(jù)方面也表現(xiàn)良好.隨著機(jī)器學(xué)習(xí)的發(fā)展,集成學(xué)習(xí)算法因?yàn)榫哂休^高的穩(wěn)定性和較強(qiáng)的泛化性能已經(jīng)成為機(jī)器學(xué)習(xí)領(lǐng)域一個(gè)非常重要的研究方向.

Kearns和Valiant提出關(guān)于“弱可學(xué)習(xí)和強(qiáng)可學(xué)習(xí)等價(jià)性”的問(wèn)題[1].意味著只要性能略好于“隨機(jī)猜測(cè)”的弱分類器經(jīng)過(guò)一定的手段可以實(shí)現(xiàn)強(qiáng)分類器.實(shí)現(xiàn)弱分類器代替強(qiáng)分類器的途徑是集成學(xué)習(xí)[2],集成學(xué)習(xí)可以顯著提高學(xué)習(xí)器的精度和泛化能力.集成分類器的預(yù)測(cè)誤差是由兩方面決定的,一方面是基分類器的強(qiáng)度(正相關(guān)),另一方面是分類器之間的相關(guān)度(反相關(guān)).分類器的差異性[3]是影響集成學(xué)習(xí)的重要因素,當(dāng)基分類器的誤差不關(guān)聯(lián)時(shí),集成學(xué)習(xí)器才可以達(dá)到更良好的效果.

Bagging和Boosting是兩種知名的集成方法[4],由于其具有良好的理論支持和實(shí)驗(yàn)表現(xiàn)而受到關(guān)注.對(duì)于Bagging方法,訓(xùn)練集被隨機(jī)混合,按照一定的比例有放回地抽樣T次,產(chǎn)生T個(gè)樣本集.最終的分類器是由這些樣本訓(xùn)練出來(lái)的分類器的線性組合.Bagging方法的誤分類概率與單獨(dú)的自助法(Boostrap)重復(fù)實(shí)驗(yàn)相當(dāng),但是比Booststrap更穩(wěn)定.Bootstrap方法可以提高小樣本情況下的總體均值區(qū)間估計(jì)的精度.另一方面,boosting(提升)方法根據(jù)基分類器的精度自適應(yīng)地改變訓(xùn)練集的分布權(quán)重,在迭代時(shí)更關(guān)注于被分錯(cuò)的樣本,Boosting方法存在著多種優(yōu)良的變體,其中的AdaBoost(Adaptive Boosting)算法[5]是最著名的一種,可以解決從二分類到多分類的問(wèn)題.

本文介紹的旋轉(zhuǎn)森林算法[6](Rotation Forest,RoF)是一種利用決策樹(shù)作為基分類器的集成分類算法,對(duì)樣本的屬性集進(jìn)行隨機(jī)分割,利用某種變換手段,例如主成分分析(principal components analysis,PCA),對(duì)屬性子集進(jìn)行變換,以增加各子集之間的差異性.再利用變換后的屬性子集來(lái)選擇樣本訓(xùn)練不同的分類器.通過(guò)與Bagging決策樹(shù)以及隨機(jī)森林RF方法相比較,驗(yàn)證了此方法良好的分類性能.

1 主成分分析理論

主成分分析[7]PCA是一種展現(xiàn)事物主要矛盾的統(tǒng)計(jì)分析方法,可以從多元事物中解析出主要影響因素,揭示事物的本質(zhì),簡(jiǎn)化復(fù)雜的問(wèn)題.PCA理論用幾個(gè)較少的綜合指標(biāo)來(lái)代替原來(lái)較多的指標(biāo),而這些較少的綜合指標(biāo)既能盡多地反映原來(lái)較多指標(biāo)的有用信息,且相互之間又是無(wú)關(guān)的,也可以實(shí)現(xiàn)經(jīng)過(guò)降維去除噪聲.

PCA的思想是將原始的n維特征空間映射到k維上,k的大小按實(shí)際需求選定,通常k≤n.這k維特征是經(jīng)過(guò)變換后的正交特征,被稱為主元.主成分分析運(yùn)算是一種確定一個(gè)坐標(biāo)系統(tǒng)的正交變換,在新的坐標(biāo)系統(tǒng)下,變換數(shù)據(jù)樣本的方差在沿新的坐標(biāo)軸方向上取得最大化,使得數(shù)據(jù)投影的方差依次按照從大到小排列.這種變換在無(wú)損或很少損失了數(shù)據(jù)集的信息的情況下降低數(shù)據(jù)集的維數(shù).

PCA的基本原理如下:對(duì)于輸入數(shù)據(jù)矩陣Xm×n(通常滿足m>n),由一系列中心化的樣本數(shù)據(jù)構(gòu)成,其中xi∈Rn且滿足

(1)

令U是一個(gè)n階的正交矩陣,第i列Ui是樣本的協(xié)方差矩陣的第i個(gè)特征向量.對(duì)輸入數(shù)據(jù)樣本xi通過(guò)變換成為一個(gè)新的向量:si=UTxi.主成分分析的主要步驟如下:

1)將所獲得的n個(gè)指標(biāo)(每一指標(biāo)有m個(gè)樣品)的一批數(shù)據(jù)寫成一個(gè)(m×n)維數(shù)據(jù)矩陣A

(2)

并對(duì)A進(jìn)行標(biāo)準(zhǔn)化處理,生成X.

2)計(jì)算X的協(xié)方差矩陣,得出一個(gè)n階的矩陣S,計(jì)算出S的特征向量e1,e2,…,en,以及對(duì)應(yīng)的特征值λi,I=1,2,…,N,并把特征值按大到小排序.

3)根據(jù)需要保留前k個(gè)較大的特征值,在本算法中,為了分類精度,保留全部的特征值.

4)計(jì)算已標(biāo)準(zhǔn)化的樣本數(shù)據(jù)X在提取出的特征向量上的投影Y=X·Z.所得的Y即為進(jìn)行特征變換后的數(shù)據(jù).

5)對(duì)于n維的數(shù)據(jù)矩陣,經(jīng)過(guò)主成分分析后會(huì)產(chǎn)生n個(gè)主成分.主成分是原變量的線性組合,既不會(huì)增加總信息量,也不減少總信息量.對(duì)于旋轉(zhuǎn)森林算法,主成分分析本身并不是目的,而是一種手段[8].通過(guò)變換,可以使得訓(xùn)練得到的各基分類器的差異性增強(qiáng).

2 旋轉(zhuǎn)森林算法

旋轉(zhuǎn)森林是一種運(yùn)用線性分析理論和決策樹(shù)分類算法,既可以用于分類也可以用于回歸[9].旋轉(zhuǎn)森林通過(guò)對(duì)坐標(biāo)軸變換建立同種集成分類器.因此,基分類器必須對(duì)特征軸旋轉(zhuǎn)敏感[10],決策樹(shù)是一個(gè)通常的選擇.旋轉(zhuǎn)森林旨在建立一個(gè)精確的并且差異性強(qiáng)的集成分類器.旋轉(zhuǎn)森林借助特征提取得到特征子空間,通過(guò)主成分分析變換后再重組為一個(gè)完整的屬性集.

其算法描述如下:

令x=[x1,x2,…,xn]T為一個(gè)具有n個(gè)屬性的樣本點(diǎn),X為一個(gè)包含N個(gè)訓(xùn)練樣本的訓(xùn)練集,構(gòu)成N×n的矩陣,同時(shí)令向量Y=[y1,y2,…,yN]是訓(xùn)練集X對(duì)應(yīng)的類標(biāo),并且yi屬于類標(biāo)集合{w1,w2,…,wc}.D1,D2,…,DL為所選擇的L個(gè)基分類器,F為完整的屬性集.

為了訓(xùn)練各分類器,需要先選擇好L的值,即存在D1,D2,…,DL為基分類器.與Bagging決策樹(shù)、隨機(jī)森林類似,各分類器也可以并行訓(xùn)練.具體的構(gòu)建步驟如下:

1)隨機(jī)將屬性集F劃分成K個(gè)不相交的子集,每個(gè)子集將包含M=n/K個(gè)屬性.子集之間相互獨(dú)立,以增加屬性子集的差異性.對(duì)同一數(shù)據(jù)集,K的取值與分類器的精度并不存在單調(diào)對(duì)應(yīng)關(guān)系,其精度也會(huì)隨著訓(xùn)練數(shù)據(jù)集的不同而有所變化.但是實(shí)驗(yàn)發(fā)現(xiàn),當(dāng)K=1或者n,所得到的效果最差,其他取值時(shí)差別不大[10].主要原因是,構(gòu)造稀疏矩陣是增強(qiáng)各分類器準(zhǔn)確性的先決條件,K=1時(shí)沒(méi)有對(duì)屬性集進(jìn)行分割,也無(wú)法形成稀疏矩陣;當(dāng)K=n(n是特征數(shù))時(shí),經(jīng)過(guò)變換和重組后,所有的基分類器都是一樣的,因此相當(dāng)于只得到了一個(gè)分類器,而非集成分類器.

3)對(duì)每一個(gè)特征子集都進(jìn)行步驟(2)的操作,將得到的所有的主成分系數(shù)存入一個(gè)系數(shù)矩陣Ri

(3)

Ri形成一個(gè)稀疏矩陣,其行數(shù)為n,列數(shù)為各子屬性集變換后的列數(shù)之和∑jMj.

(4)

x=argmax(uw(x)),w∈C.

(5)

3 實(shí)驗(yàn)與分析

本實(shí)驗(yàn)所用的數(shù)據(jù)集有三個(gè),分別為L(zhǎng)eukemia(白血病)、Diabetes(糖尿病)和Heart Disease(心臟病)數(shù)據(jù)集.因?yàn)榛虮磉_(dá)數(shù)據(jù)具有維度特別高的特點(diǎn),直接用于分類存在著運(yùn)算量大的問(wèn)題,故首先運(yùn)用ReliefF算法[11]先對(duì)實(shí)驗(yàn)數(shù)據(jù)進(jìn)行處理,以降低復(fù)雜度.ReliefF算法是一種特征權(quán)重算法.根據(jù)各個(gè)特征和類別的相關(guān)性賦予特征不同的權(quán)重,權(quán)重小于某個(gè)閾值的特征將被移除.ReliefF算法中特征和類別的相關(guān)性是基于特征對(duì)近距離樣本的區(qū)分能力.見(jiàn)表1.

表1 試驗(yàn)用數(shù)據(jù)集

其中Diabetes和Heart是二分類數(shù)據(jù)集,Leukemia是多分類數(shù)據(jù)集,各數(shù)據(jù)集均無(wú)缺失.參照用的分類算法為Bagging決策樹(shù)(Bagging Tree)和隨機(jī)森林算法[12](Random Forest).為了對(duì)比突出,基分類器均采用C4.5決策樹(shù)算法,并且各實(shí)驗(yàn)結(jié)果均做了10次十折交叉驗(yàn)證,以保證實(shí)驗(yàn)結(jié)果的穩(wěn)定性和準(zhǔn)確性.

本實(shí)驗(yàn)將從精度和集成度兩個(gè)方面體現(xiàn)旋轉(zhuǎn)森林算法的優(yōu)點(diǎn).首先固定一個(gè)集成度,對(duì)每一組數(shù)據(jù)集,均采用三種不同的算法進(jìn)行測(cè)試,得出結(jié)果進(jìn)行對(duì)比;其次,再對(duì)每一組數(shù)據(jù),均施以3種不同的算法,變動(dòng)集成度,顯示在不同集成度下,各算法的表現(xiàn).

表2 不同分類器的分類精度和方差

表2是三組數(shù)據(jù)在不同的算法下所得到的分類精度以及方差.每種算法均在基分類器個(gè)數(shù)為10下進(jìn)行試驗(yàn).可以得到,每組數(shù)據(jù)的分類精度均在旋轉(zhuǎn)森林時(shí)取得最佳.除第二組數(shù)據(jù)外,RF算法也是較好的結(jié)果.但是從方差分析,Bagging決策樹(shù)的方差總是最小的,這也體現(xiàn)Bagging決策樹(shù)是一種相對(duì)較穩(wěn)定的算法.

圖3是對(duì)每組的數(shù)據(jù)施以三種不同的算法進(jìn)行分類測(cè)試.可以得出,隨著集成數(shù)目的增加,旋轉(zhuǎn)森林算法明顯優(yōu)于另外兩種算法,隨機(jī)森林其次,而B(niǎo)agging決策樹(shù)接近隨機(jī)森林算法;同時(shí)也可以得出,隨著集成度的上升,旋轉(zhuǎn)森林算法很快

圖1 Leukemia數(shù)據(jù)集在不同算法下的分類結(jié)果Figure 1 Classification result of Leukemia based on bifferent algorithms

圖2 Heart數(shù)據(jù)集在不同算法下的分類結(jié)果Figure 2 Classification result of Heart based on different algorithms

圖3 Diabetes數(shù)據(jù)集在不同算法下的分類結(jié)果Figure 3 Classification result of Diabetes based on different algorithms

就可以達(dá)到不錯(cuò)的結(jié)果,在基分類器個(gè)數(shù)為10時(shí),就相當(dāng)于另外兩種算法基分類器個(gè)數(shù)為30的效果.從圖中可得出,Bagging決策樹(shù)平穩(wěn)的上升,之后幾乎不變.

相比其他集成算法,旋轉(zhuǎn)森林算法的核心在于運(yùn)用主成分分析的特征子空間進(jìn)行變換,再重組成完整的特征空間.依靠稀疏矩陣,在沒(méi)有降低基分類器精度的同時(shí),盡可能的差異化.旋轉(zhuǎn)森林方法之所以在基因表達(dá)數(shù)據(jù)方面取得較好的表現(xiàn),是因?yàn)楸舅惴ㄔ诨诸惼鞯木群筒町愋詢煞矫孀隽撕芎玫恼壑?

4 結(jié) 語(yǔ)

旋轉(zhuǎn)森林的基本思想是實(shí)現(xiàn)從輸入空間到屬性空間的映射,在變換過(guò)程中保持原有的維度而不降維,但是產(chǎn)生一個(gè)坐標(biāo)軸旋轉(zhuǎn)(axes rotation).本試驗(yàn)運(yùn)用主成分分析對(duì)特征子空間進(jìn)行變換,以決策樹(shù)為基分類器,今后將從兩個(gè)方面繼續(xù)開(kāi)展相關(guān)研究:

1)研究其它變換手段對(duì)旋轉(zhuǎn)森林分類的影響.例如獨(dú)立分量分析(independent component analysis,ICA)算法,線性判別式分析(linear discriminant analysis,LDA)算法等;以及運(yùn)用非線性變化方法,例如將核主成分分析方法(kernel based principal component analysis,KPCA)[13]引入旋轉(zhuǎn)森林算法,并且研究KPCA方法的適應(yīng)性問(wèn)題.

2)將研究對(duì)其它分類器[14]的集成效果,例如極限學(xué)習(xí)機(jī)(extreme learning machine,ELM),支持向量機(jī)(support vector machine,SVM)等,試圖提高原算法的分類精度,以及增強(qiáng)其泛化能力.

[1] SCHAPIRE R E. The strength of weak learnability[J].Machine Learning,1990,5(2):197-227.

[2] ROBI P.Ensemble machine learning[M].USA: Springer,2012:1-34.

[3] 李凱,崔麗娟.集成學(xué)習(xí)算法的差異性及性能比較[J].計(jì)算機(jī)工程,2008,34(6):35-37.

LI Kai, CUI Lijuan. Diversity and performance comparison for ensemble learning algorithms[J].Computer Enginee-ring,2008,34(6):35-37.

[4] SOTIRIS B K. Bagging and boosting variants for handing classifications probelms:a survey[J].The Knowledge Engineering Review,2013,29(1):78-100.

[5] 曹瑩,苗啟廣,劉家辰,等.AdaBoost算法研究進(jìn)展與展望[J].自動(dòng)化學(xué)報(bào),2013,39(6):745-753. CAO Ying, MIAO Qiguang, LIU Jiachen, et al. Advance and prospects of adaBoost algorithm[J].Acta Automatica Sinica,2013,39(6):745-753.

[6] RODRIGUEZ J J, KUNCHEVA L I, ALONSO C J.Rotation forest: A new classifier ensemble method[J].IEEE Tranactions on Pattern Analysis and Machine Intelligence,2006,28(10):1619-1630.

[7] AKAMA Y. Realizability interpretation of PA by iterated limiting PCA[J].Mathematical Structures in Computer Science,2014,24(6):35-48.

[8] 劉敏,謝秋生.一種基于旋轉(zhuǎn)森林的集成協(xié)同訓(xùn)練算法[J].計(jì)算機(jī)工程與應(yīng)用,2011,47(30):172-175. LIU Min, XIE Qiusheng. Ensemble co-training algorithm based on ration forest[J].Computer Engineering and Applications,2011,47(30):172-175.

[9] CARLOS P. Rotation forests for regression[J].Applied Mathematics and Computation,2013,219(19):9914-9924.

[10] KUNCHEVA L I, RODRIGUEZ J J. An experimental study on rotation forest ensembles[G].Lecture Notes in Computer Science,2007:459-468.

[11] ROBNIK-SIKONJA M, KONONENKO I. Theoretical and empirical analysis of reliefF and rreliefF[J].Machine Learning,2003,53(1):23-69.

[12] ZHANG L, SUGANTHAN P N. Random forest with ensemble of feature spaces[J].Pattern Recognition,2014,47(10):3429-3437.

[13] SHAH J H, SHARIF M. A survey: linear and nonlinear pca based face recognition techniques[J].International Arab Journal of Information Technology,2013,10(6):536-545.

[14] 韓敏,劉賁.一種改進(jìn)的旋轉(zhuǎn)森林算法[J].電子與信息學(xué)報(bào),2013,35(12):2896-2900. HAN Min, LIU Ben. An improved rotation forest classification algorithm[J].Journal of Electronisc & Information Technology,2013,35(12):2896-2900.

Study on classifier algorithm of genetic data based on rotation forest

LIU Yaqing, LU Huijuan, DU Bangjun, YU Cui

(College of Information Engineering, China Jiliang University, Hangzhou 310018, China)

Aiming at the character of high dimensions and small samples of gene expression data, an ensemble classification algorithm by the name of rotation forest based on decision tree was introduced. By splitting the feature set of data, applying the principal component analysis (PCA) on them and then reserving all the coefficients of the principal components, a sparse matrix was rebuilt up.Finally the unpruned decision tree ensemble algorithm was used to classify the transformed data set. Here, combined with the ReliefF algorithm,three groups of gene expression data were choosen to test the rotation forest algorithm, compared with two other ensemble methods: Bagging tree and random forest. The result indicates that the rotation forest has a higher classification accuracy and can get an excellent performance with a low ensemble size all the same.

principal components analysis; rotation forest; ensemble learning; reliefF; decision tree

1004-1540(2015)02-0227-05

10.3969/j.issn.1004-1540.2015.02.019

2015-02-06 《中國(guó)計(jì)量學(xué)院學(xué)報(bào)》網(wǎng)址：zgjl.cbpt.cnki.net

國(guó)家自然科學(xué)基金資助項(xiàng)目(No.61272315),浙江省自然科學(xué)基金資助項(xiàng)目(No.Y1110342)．

TP391

A