面向基因數據分類的核主成分分析旋轉森林算法*

陸慧娟，劉亞卿，孟亞瓊，關 偉，劉硯秋

1.中國計量大學 信息工程學院，杭州 310018

2.中國計量大學 現代科技學院，杭州 310018

面向基因數據分類的核主成分分析旋轉森林算法*

陸慧娟1+，劉亞卿1，孟亞瓊1，關 偉2，劉硯秋1

1.中國計量大學 信息工程學院，杭州 310018

2.中國計量大學 現代科技學院，杭州 310018

Abstract:Rotation forest(RoF)algorithm is an ensemble classification algorithm using linear analysis theory and decision trees.The rotation forest achieves higher classification accuracy and superior performance with less number of classifiers.However,the classification accuracy decreases for gene expression data with linearly inseparable cases.To address this issue,this paper proposes a rotation forest algorithm based on kernel principal component analysis(KPCA-RoF),chooses the Gaussian kernel function and principal component analysis to implement the nonlinear mapping and deal with differences in gene data.The proposed algorithm focuses on the optimization of parameters,and uses decision tree algorithm for ensemble learning.Experiments show that the new algorithm well addresses the linearly inseparabal issue and improves the classification accuracy.

Key words:kernel function;principal component analysis;decision tree;rotation forest;gene data classification

旋轉森林（rotation forest，RoF）是一種運用線性分析理論和決策樹的集成分類算法，在分類器個數較少的情況下仍可以取得良好的結果，同時能保證集成分類的準確性。但對于部分基因數據集，存在線性不可分的情況，原始的算法分類效果不佳。提出了一種運用核主成分分析變換的旋轉森林算法（rotation forest algorithm based on kernel principal component analysis，KPCA-RoF），選擇高斯徑向基核函數和主成分分析的方法對基因數據集進行非線性映射和差異性變化，著重于參數的選擇問題，再利用決策樹算法進行集成學習。實驗證明，改進后的算法能很好地解決數據線性不可分的情形，同時也提高了基因數據集上的分類精度。

核函數；主成分分析；決策樹；旋轉森林；基因數據分類

1 引言

癌癥是嚴重威脅人類健康的一大疾病，已經成為我國主要的公共衛生問題之一。目前癌癥的發病率和死亡率一直呈上升趨勢，因此預防和治療癌癥是全世界關注的焦點問題[1]。然而，人類肌體從癌變的發生，到有明顯癥狀的出現，要經過一個較長的潛伏期，如果在此期間能夠及時發現，并且進行有效的干預，就可以將腫瘤控制或扼殺在萌芽狀態。依靠基因表達數據進行腫瘤診斷分類是目前比較熱門的一種分類方法，對于基因數據的分類問題，目前主要集中在分類精度、泛化能力、算法的復雜性和可理解性上。但是由于基因表達數據維數高、小樣本和非線性等特點，使得基因表達數據的分析遇到一定的困難。且對于部分基因數據集，存在線性不可分的情況，原始的旋轉森林（rotation forest，RoF）算法在對線性不可分的基因數據集進行分類時容易出現分類精度低，耗時長等問題。對樣本數據的篩選、特征選擇、降維、數據分類等都是當前數據挖掘和機器學習中的研究熱點，清楚差異基因的功能和對其進行干預而引起的結果，并最終可以根據獲得的信息進行診斷和治療[2]。

旋轉森林[3]是于2006年提出的一種分類器集成系統，其基本思想建立在隨機森林算法基礎上。旋轉森林把原特征空間分割成若干子集，之后對每個子集分別進行某種線性變換。如主成分分析（principal components analysis，PCA），保留所有主成分的情況下，將得到的變換分量分別按照這些子集原來對應的順序合并，這樣每次隨機分割后得到的數據集都被投影到不同坐標空間中，從而形成差別較大的分量子集，用這些分量自己訓練分類器，能夠得到差異較大且分類性能較高的基分類器，以提高集成分類的性能。

毛莎莎等人[4]利用旋轉森林集成方式，集成了兩種不同的模型，充分利用兩種模型各自的優勢，為形成異構算法集成提供了啟示。Mousavi等人[5]結合了旋轉森林和集成剪枝兩種方法，并提出了EP-RTF（ensemble pruning and rotation forest）算法。首先通過遺傳算法選擇異構的分類器子集，其次運用旋轉森林方法進行訓練，參數由遺傳算法進行優化，并使用加權投票的方式得出最終結果。Wong等人[6]將旋轉森林分類器和LPQ（local phase quantization）算法相結合，驗證了旋轉森林和支持向量機分類器的良好性能，同時也為未來的蛋白質研究提供了理論基礎。不過從目前的文獻來看，對旋轉森林算法的研究和應用依然不多，有很多地方值得進一步深入探討。

本文提出了一種運用核主成分分析變換的旋轉森林算法（rotation forest algorithm based on kernerl principal component analysis，KPCA-RoF）。利用核主成分分析的方法進行數據的非線性映射和差異性變換，并選擇合適的參數，利用決策樹算法進行集成學習，形成核函數旋轉森林算法。實驗表明，核旋轉森林方法在同等集成度的條件下具有更高的分類精度，這在一定程度上可以解決基因數據線性不可分的情形。

2 核函數相關理論

對于任意一數據集T有以下關系：

其中，i=1,2,…,n，Rn表示n維空間。如果存在一個超平面S：

可以將兩類樣本完全分開，則稱數據集T為線性可分數據集。

一個數據集是否線性可分，取決于是否能找到一個超平面來分離兩個相鄰的類別。如果每個類別的分布范圍本身是全連通的單一凸集，且沒有重疊部分，則這兩個類別就是線性可分的。如果存在的多種模式可以用n維歐式空間的點分開，則可以在此空間中形成一個曲面把歸屬于不同模式的樣本點完全隔開，如支持向量機（support vector machine，SVM）[7]就可以很好地分類。線性不可分的現象，簡單來說就是一個數據集不可以通過一個線性分類器（直線、平面）來實現正確的分類。如圖1所示。

Fig.1 Linearly separable and linearly inseparable圖1 線性可分與線性不可分

對于線性不可分的情形，可以采用核函數映射的方式得到其特征空間，之后在此基礎上進一步操作。但是采用直接映射的方法在高維空間進行操作是不可行的，因為直接映射本身就存在著計算復雜等技術問題，且映射函數的形式和參數也不容易把握，借助核函數的方法可以間接地實現此種映射[8]。

以下列舉幾種常用的核函數：

（1）線性核函數

（2）P階多項式核函數

（3）高斯徑向基核函數（radialbasisfunction，RBF）

將樣本集作為輸入，高維的特征空間作為輸入空間，許多的傳統線性分類算法就可以實現非線性分類，這是基于核的機器學習算法應用的基礎。雖然其中的映射函數非常復雜甚至難以求出，但是可以通過核函數繞過此問題，使此方法變得容易應用。高斯徑向基核函數由于更小的數值復雜度和較少的參數，以及較強的代表性而成為核函數的首選方法[9]，通過調整核函數參數的大小控制其過擬合的程度而得到合適的算法。

3 核主成分分析

假設x1,x2,…,xm為訓練樣本，xk∈RN用來表示其輸入空間。選定映射函數為Φ，其定義如下：

核函數通過映射關系Φ先實現輸入樣本點x到特征空間F的映射，F由Φ(x1),Φ(x2),…,Φ(xm)生成，中心化處理映射后的數據，即：

則映射后特征空間的協方差矩陣為：

按照主成分分析的方式求解特征方程：

λ和V是屬于Φ(xi)的生成空間中的特征值和特征向量，因此：

并且存在參數αi，使得V可由Φ(xi)線性表示，即：

合并式（6）、（7），把映射后數據的相互內積定義成一個m階的矩陣K，其元素根據選擇的核函數計算所得：

則可以得到與式（5）等價的公式：

其中，α=(α1,α2,…,αm)T,矩陣K就是以后所要用到的變換矩陣[10]。

求解K的特征值和特征向量。設K的特征值為λ1≤λ2≤ …≤λm，所對應的特征向量為α1,α2,…,αm。

4 算法描述

4.1 基于核主成分分析的旋轉森林算法

核函數方法可以按照模塊化的形式擴展機器學習算法，基于這一原理，選擇利用核主成分分析的方式實現樣本數據的變換，并形成差異性強的訓練集，之后再參照旋轉森林算法以決策樹為基分類器，形成核主成分分析旋轉森林算法。算法描述如圖2所示。

Fig.2 Description of KPCA-RoF圖2 核主成分分析旋轉森林算法描述

（1）對一給定的n維樣本集，取除去類標的特征集部分為H，劃分為不相交的K份。

（2）設D1,D2,…,DL為要用于分類的基分類器。Hij表示Di分類器所使用訓練集中對應的第j個特征子集，其中1≤i≤L,1≤j≤K。對樣本集進行隨機抽樣m次，抽樣形成樣本子集Zi，并且m=n/k，Zij表示Hij所對應的樣本子集。對Zij選擇某核函數進行核主成分分析，排列其特征向量產生一個新的系數矩陣Cij。

（3）重復上述步驟，對每個Zi通過核主成分分析的方式產生一個系數矩陣，共重復了K次。

（4）將上述產生的系數矩陣組合成一個巨大的稀疏矩陣，以此生成基分類器Di的旋轉矩陣Ri：

這樣分類器Di所使用的訓練集則為ZRi。同樣在測試過程中，對于新樣本x，也要與旋轉矩陣相乘得到xRi再送入分類器，判定其類別的置信度為：

4.2 核函數的選擇方法以及參數的選擇方法

因為不同的核函數會對分類效果帶來較大的差異，不適當的函數形式或者參數甚至有可能達不到分類的效果。單獨對核函數進行評價，通過測算映射后數據的類內聚集和類間離散程度來評估可分性的好壞[11]。這種方法獨立于具體的分類算法，也不考慮最后的泛化能力，因而適用性較強。本文采用高斯核函數改進旋轉森林算法，并關注于參數的選擇問題。

這里對參數的優化選用特征類間距作為參考指標[12]。數據映射后在特征空間中的夾角和距離為：

用Di,j來表示兩個向量之間的距離，表示如下：

將具體的核函數代入式（12）和（13）：

其中夾角滿足：

同理可得出：

從上述表達式可得，僅有一個參數影響類間距和夾角，從而影響特征空間的分布情況，進一步影響旋轉森林算法的分類效果。

當參數δ的值趨于0時，可以得出其夾角的余弦值趨于1，也即意味著映射后的兩向量夾角值趨于0；并且通過計算向量距離可知，向量的距離也趨于0，這意味著所有的樣本被映射到一點上了，這樣根本無法對樣本進行分類。當參數δ的值趨于無窮大時，兩向量夾角趨于π/2，樣本的距離趨于一個常數，這說明樣本集被映射到一個n維的特征空間中，且可以發現特征向量是兩兩正交。因此特征空間的維數隨著δ的增大而單調增大，一直增加到n（n是樣本空間樣本的個數）；并且特征空間各向量之間的夾角以及距離也是單調增加的，分別趨于π/2和。

給定一個包含有L個樣本C個類別的訓練集X，即：

計算樣本映射后在特征空間中的平均值：

則在映射后的空間中類間平均距離的表達式為：

在核空間中類間余弦值為：

在核空間中類內余弦值為：

綜合式（19）、（20）、（21）可得：

通過上述表達式可知，類間距可以表述為類間角和類內角的運算結果。當類內角大，類間角小時，類間距較大；反之則類間距較小。而根據式（14）可知，類間角和類內角均隨著δ的增大而增大，因此可能存在一個參數值，使得類間距最大。

5 實驗結果及分析

本實驗主要選擇高斯徑向基核函數對樣本進行變換，對比指標主要有分類精度、集成度等。通過對核函數唯一的參數δ進行優化[13]，使之獲得較好的分類性能。

本實驗選定Breast（乳腺癌）、CNS（神經系統腫瘤組織）、ALL（急性淋巴細胞白血?。?個數據集作為實驗對象，數據來源均可以從公開的站點下載，其下載網址為http://datam.i2r.a-star.edu.sg/datasets/krbd/。因為原始數據集的維數過高，不利于直接進行數據分類，所以先利用ReliefF算法[14]進行一定程度上的降維處理。ReliefF算法是一種帶有特征權重的選擇方法，這里對數據集隨機抽樣30次，特征閾值設為0.95，得出預處理后的數據集。按照上述方法通過實驗的手段取得各數據集的最佳參數。下面是有關的曲線δ-J(δ)，δ的取值范圍為δ={10-5,10-4,…,105}。

圖3表示3組數據各自的參數值與其歸一化的類間距之間的關系，均采用30次實驗的平均值?？梢钥闯觯诳捎^測到的范圍內[10-6,106]，存在著極大值點，分別是0.9、0.9、0.8。則認為對于這3組數據集，最優的參數值分別為δ1=δ2=0.9,δ3=0.8。

Fig.3 Parameter values and class separation distance圖3 參數值與類間距的關系

本文主要通過與Bagging算法[15]、隨機森林算法以及原始的旋轉森林算法進行比較實驗和分析，依次驗證改進后的旋轉森林算法的有效性。所有算法的基分類器都采用C4.5決策樹[16]，主要控制的變量有集成度N和抽取的樣本個數M，每次均做到控制單一量的變化，分別取最好的結果進行對比實驗。實驗統計量為F檢驗，樣本方差為S2，樣本均值為Xˉ。

（1）高斯徑向基核旋轉森林（RBF-RoF）特征集分割數實驗。

表1在基于決策樹的集成數為30的情況下，不斷地改變各特征集的分割數后所得到的分類精度。保證基分類器的數目足夠多，這樣就可以使得每個實驗數據集充分集成。從實驗結果得到，在特征集分割數大于10時，分割數的改變對于提高旋轉森林的分類精度不會帶來很大的改善，這跟原始的旋轉森林實驗的結果類似。因此在后續的實驗中，沒必要再去增加特征集的分割數，保持在5～10之間的任何一個值即可，這里選擇N=9。

Table 1 Classification accuracy and the number of feature set splitting表1 分類精度與特征集分割數之間的關系

表2展示了隨著集成度的上升，各數據集分類精度的變化。從結果可以得到，隨著集成度的上升，各數據集大約在集成度為15時獲得較好的精度，之后就幾乎穩定下來。分別在每一個數據集上選用幾種集成算法，實驗變量為集成度，驗證不同集成算法所帶來的分類效果。

Table 2 Classification accuracy and integration level表2 分類精度與集成度之間的關系

圖4～圖6分別展示了各數據集在不同分類算法下的分類精度，對比結果可以發現，隨著集成度的上升，各分類算法的精度都會有所上升?？傮w來講，Bagging決策樹的分類精度最差，隨機森林稍好，旋轉森林更好一些，經過高斯徑向基核函數改進的核主成分分析旋轉森林（RBF-RoF）效果總是最好的。Bagging決策樹僅僅是對決策樹的集成，不會對算法性能帶來明顯的提升，隨機森林增加了對特征空間的隨機分割，基分類器間存在一定的差異性。從上述實驗結果可以看出，旋轉森林和RBF-RoF都會取得良好的實驗效果，這是由于這兩種算法對特征空間進行分割和變換。對比改進前后的旋轉森林，改進后的分類精度會有所提升；同時，改進后的旋轉森林在比較小的集成度時就可以取得很好的精度，這說明進行非線性變換相比線性變換會帶來更好的可分性，同時非線性變換會增加很多的計算量，但算法的復雜度同屬于O(n3)，復雜度影響并不明顯，相對于精度的提高，可以忽略。

Fig.4 Classification accuracy of Breast dataset圖4 Breast數據集的分類精度

Fig.5 Classification accuracy of CNS dataset圖5 CNS數據集的分類精度

Fig.6 Classification accuracy ofALL dataset圖6 ALL數據集的分類精度

（2）通過對改進后的算法進行統計學分析，以說明比原始算法存在顯著性差別。這里利用F檢驗的方法來驗證改進前后的顯著性。

求解實驗結果樣本的方差S2：

進一步求得F值：

其中一般取參數α=0.05，與F分布表中所查到的值進行比對，如果前者大于后者，則認為本組算法之間是彼此顯著的，否則就認為差別不大。

表3列舉了幾個常用的統計量，樣本均值、方差S2以及顯著性F。從計算結果可以得到，在各個數據集上表現顯著性有效。

Table 3 Statistics analysis of algorithms表3 算法改進前后的統計量分析

6 結束語

通過特征集分割、采樣與變換，最后再重新生成一個變換矩陣，是旋轉森林的重要特點。借助核支持向量機的思想以及旋轉森林算法的流程，實現了基于高斯徑向基核主成分分析的旋轉森林，與利用線性變換的旋轉森林算法相比，分類精度得到提高。并通過對其他統計量的分析可知，改進后的算法方差更小，并且比原始算法更顯著。盡管改進后的算法會帶來更多的資源消耗，例如計算時間和內存，但是在計算成本越來越低的現今社會，這不應該成為一種瓶頸。

[1]Lu Huijuan.A study of tumor classification algorithms using gene expression data[D].Xuzhou:China University of Mining and Technology,2012.

[2]Lu Huijuan,An Chunlin,Zheng Enhui,et al.Dissimilarity based ensemble of extreme learning machine for gene expression data classification[J].Neurocomputing,2014,128(5):22-30.

[3]Liu Min,Xie Huosheng.Ensemble co-training algorithm based on rotation forest[J].Computer Engineering and Applications,2011,47(30):172-175.

[4]Mao Shasha,Xiong Lin,Jiao Licheng,et al.Isomerous multiple classifier ensemble via transformation of the rotation forest[J].Journal of Xidian University,2014,41(5):48-53.

[5]Mousavi R,Eftekhari M,Haghighi M G.A new approach to human microRNA target prediction using ensemble pruning and rotation forest[J].Journal of Bioinformatics and Computational Biology,2015,13(6):1550017.

[6]Wong Leon,You Zhuhong,Ming Zhong,et al.Detection of interactions between proteins through rotation forest and local phase quantization descriptors[J].International Journal of Molecular Sciences,2015,17(1):21.

[7]Adankon M M,Cheriet M.Support vector machine[M]//Encyclopedia of Biometrics.[S.l.]:Springer US,2015:1303-1308.

[8]Lu Huijuan,Du Bangjun,Liu Jinyong,et al.A kernel extreme learning machine algorithm based on improved particle swam optimization[J].Memetic Computing,2017,9(2):121-128.

[9]Jian Ling.Kernel based learning algorithm and application[D].Dalian:Dalian University of Technology,2012.

[10]Li Zhe,Kruger U,Xie Lei,et al.Adaptive KPCA modeling of nonlinear systems[J].IEEE Transactions on Signal Processing,2015,63(9):2364-2376.

[11]Song Xiaoshan,Jiang Xiaoyu,Luo Jianhua,et al.Analysis of the inter-class distance-based kernel parameter evaluating method for RBF-SVM[J].Acta Armamentarii,2012,33(2):203-208.

[12]Wang Tinghua,Chen Junting.Survey of research on kernel function evaluation[J].Application Research of Computers,2011,28(1):25-28.

[13]Qiu Xiaoyu.The selection for the kernel-based method[D].Jinan:Shandong Normal University,2008.

[14]Chen Xiaolin,Ji Bo,Ye Yangdong.A R-NIC algorithm based on ReliefF feature weighting[J].Computer Engineering,2015,41(4):161-165.

[15]Li Yaqin,Yang Huizhong.Ensemble modeling method based on Bagging algorithm and Gaussian process[J].Journal of Southeast University:Natural Science Edition,2011,41(S1):93-96.

[16]Meng Yang,Hou Feifei.Node association mining based on C4.5[J].Telecom World,2016(10):131-132.

附中文參考文獻:

[1]陸慧娟.基于基因表達數據的腫瘤分類算法研究[D].徐州:中國礦業大學,2012.

[3]劉敏,謝伙生.一種基于旋轉森林的集成協同訓練算法[J].計算機工程與應用,2011,47(30):172-175.

[4]毛莎莎,熊霖,焦李成,等.利用旋轉森林變換的異構多分類器集成算法[J].西安電子科技大學學報:自然科學版,2014,41(5):48-53.

[9]漸令.基于核的學習算法與應用[D].大連:大連理工大學,2012.

[11]宋小衫,蔣曉瑜,羅建華,等.基于類間距的徑向基函數——支持向量機核參數評價方法分析[J].兵工學報,2012,33(2):203-208.

[12]汪廷華,陳峻婷.核函數的度量研究進展[J].計算機應用研究,2011,28(1):25-28.

[13]邱瀟鈺.核函數的參數選擇[D].濟南:山東師范大學,2008.

[14]陳曉琳,姬波,葉陽東.一種基于ReliefF特征加權的RNIC算法[J].計算機工程,2015,41(4):161-165.

[15]李雅芹,楊慧中.一種基于Bagging算法的高斯過程集成建模方法[J].東南大學學報,2011,41(S1):93-96.

[16]孟楊,候飛飛.基于C4.5的節點關聯挖掘[J].通訊世界,2016(10):131-132.

Classifier Algorithm of Genetic Data Based on Kernel Principal Component Analysis and Rotation Forest*

LU Huijuan1+,LIU Yaqing1,MENG Yaqiong1,GUAN Wei2,LIU Yanqiu1
1.College of Information Engineering,China Jiliang University,Hangzhou 310018,China
2.College of Modern Science and Technology,China Jiliang University,Hangzhou 310018,China

A

TP181

+Corresponding author:E-mail:hjlu@cjlu.edu.cn

LU Huijuan,LIU Yaqing,MENG Yaqiong,et al.Classifier algorithm of genetic data based on kernel principal component analysis and rotation forest.Journal of Frontiers of Computer Science and Technology,2017,11(10)：1570-1578.

ISSN 1673-9418 CODEN JKYTA8

Journal of Frontiers of Computer Science and Technology

1673-9418/2017/11(10)-1570-09

10.3778/j.issn.1673-9418.1608046

E-mail:fcst@vip.163.com

http://www.ceaj.org

Tel:+86-10-89056056

*The National Natural Science Foundation of China under Grant Nos.61272315,60905034(國家自然科學基金);the Natural Science Foundation of Zhejiang Province under Grant No.Y1110342(浙江省自然科學基金);the National Security Bureau Project under Grant No.zhejiang-00062014AQ(國家安全總局項目).

Received 2016-08,Accepted 2016-10.

CNKI網絡優先出版:2016-10-19,http://www.cnki.net/kcms/detail/11.5602.TP.20161019.1458.008.html

LU Huijuan was born in 1962.She received the Ph.D.degree from China University of Mining and Technology in 2012.Now she is a professor at China Jiliang University,and the outstanding member of CCF.Her research interests include machine learning,pattern recognition and bioinformatics,etc.She has published over 80 papers,conducted 2 National Natural Science Foundation of China projects and 8 Science&Technology projects of Zhejiang Province.

陸慧娟（1962—），女，浙江東陽人，2012年于中國礦業大學獲得博士學位，現為中國計量大學教授，CCF杰出會員、理事，主要研究領域為機器學習，模式識別，生物信息學等。發表學術論文80多篇，主持完成國家自然科學基金項目2項，浙江省級科技項目8項。

LIU Yaqing was born in 1988.His research interests include machine learning,cloud computing and data mining,etc.

劉亞卿（1988—），男，河南周口人，碩士，主要研究領域為機器學習，云計算，數據挖掘等。

MENG Yaqiong was born in 1992.She is an M.S.candidate at China Jiliang University,and the member of CCF.Her research interests include machine learning and data mining,etc.

孟亞瓊（1992—），女，安徽蕪湖人，中國計量大學碩士研究生，CCF會員，主要研究領域為機器學習，數據挖掘等。

GUAN Wei was born in 1976.He is a lecturer at China Jiliang University,and the member of CCF.His research interests include machine learning and pattern recognition,etc.

關偉（1976—），男，湖北仙桃人，碩士，中國計量大學講師，CCF會員，主要研究領域為機器學習，模式識別等。

LIU Yanqiu was born in 1977.She is an associate professor at China Jiliang University,and the member of CCF.Her research interests include machine learning,data mining and image processing,etc.

劉硯秋（1977—），女，河南洛陽人，碩士，中國計量大學副教授，CCF會員，主要研究領域為機器學習，數據挖掘，圖像處理等。