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

(中國計量學院 信息工程學院,浙江 杭州 310018)

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

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

(中國計量學院 信息工程學院,浙江 杭州 310018)

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

主成分分析;旋轉(zhuǎn)森林;集成學習;ReliefF算法;決策樹

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

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

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

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

1 主成分分析理論

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

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

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

(1)

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

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

(2)

并對A進行標準化處理,生成X.

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

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

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

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

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

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

其算法描述如下:

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

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

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

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

(3)

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

(4)

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

(5)

3 實驗與分析

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

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

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

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

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

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

圖3是對每組的數(shù)據(jù)施以三種不同的算法進行分類測試.可以得出,隨著集成數(shù)目的增加,旋轉(zhuǎn)森林算法明顯優(yōu)于另外兩種算法,隨機森林其次,而Bagging決策樹接近隨機森林算法;同時也可以得出,隨著集成度的上升,旋轉(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

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

相比其他集成算法,旋轉(zhuǎn)森林算法的核心在于運用主成分分析的特征子空間進行變換,再重組成完整的特征空間.依靠稀疏矩陣,在沒有降低基分類器精度的同時,盡可能的差異化.旋轉(zhuǎn)森林方法之所以在基因表達數(shù)據(jù)方面取得較好的表現(xiàn),是因為本算法在基分類器的精度和差異性兩方面做了很好的折衷.

4 結(jié) 語

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

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

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

[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] 李凱,崔麗娟.集成學習算法的差異性及性能比較[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].自動化學報,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é)同訓練算法[J].計算機工程與應用,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] 韓敏,劉賁.一種改進的旋轉(zhuǎn)森林算法[J].電子與信息學報,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 《中國計量學院學報》網(wǎng)址：zgjl.cbpt.cnki.net

國家自然科學基金資助項目(No.61272315),浙江省自然科學基金資助項目(No.Y1110342)．

TP391

A