基于差異性和準確性的加權(quán)調(diào)和平均度量的基因表達數(shù)據(jù)選擇性集成算法

高慧云，陸慧娟，嚴 珂，葉敏超

(中國計量大學(xué)信息工程學(xué)院，杭州310018)

(*通信作者電子郵箱hjlu@cjlu．edu．cn)

0 引言

癌癥是威脅人類公共健康的主要疾病之一，且死亡率較高，如果能及早發(fā)現(xiàn)癌癥疾病并及時治療將有利于患者的康復(fù)［1］。目前，基因表達數(shù)據(jù)已普遍應(yīng)用于癌癥分類，通過利用機器學(xué)習(xí)的方法對基因表達數(shù)據(jù)進行處理分析，這種新方法有望通過對癌癥的精確診斷為癌癥患者提供更好的治療?；虮磉_數(shù)據(jù)是通過DNA微陣列雜交實驗得到的，其數(shù)據(jù)具有高維、小樣本、高噪聲等特點，使通過機器學(xué)習(xí)算法對癌癥基因的診斷變得困難。

目前，機器學(xué)習(xí)的主要發(fā)展之一就是集成學(xué)習(xí)，集成學(xué)習(xí)是一種通過結(jié)合多個基分類器以提高整體泛化性能的算法［2］。常 見 的 集 成 學(xué) 習(xí) 算 法 有 Bagging［3］、Boosting［4］等。Tumer等［5］指出基分類器之間的差異性和基分類器自身的準確性是決定集成系統(tǒng)泛化性能的兩個重要因素;周志華［6］也提出基分類器的差異性越大、準確性越高，則集成的效果越好;張春霞等［7］指出基分類器的差異性難以衡量，現(xiàn)有的選擇性集成算法大多只考慮到基分類器之間的差異性而忽略基分類器自身的準確性;陸慧娟等［8］提出了一種輸出不一致測度的選擇性集成算法，通過刪除相似度較高的基分類器來保證基分類器之間的差異性;Margineantu等［9］指出，基分類器的差異性和準確性這兩個因素彼此相互制約;為克服平衡基分類器的差異性和準確性的困難，Mao等［10］提出一種通過最大化三個不同二次形式來對基分類器中的進行加權(quán)的新方法，通過最小化集合誤差得到個體分類器的最佳權(quán)重。

超限學(xué)習(xí)機(Extreme Learning Machine，ELM)是2006年Huang等［11］提出的一種單隱層的前饋神經(jīng)網(wǎng)絡(luò)，該算法以極快的學(xué)習(xí)速度和較好的泛化性能得到人們的廣泛關(guān)注。但單個ELM仍存在分類精度較差、訓(xùn)練結(jié)果不穩(wěn)定等缺點。本文采用核超限學(xué)習(xí)機(Kernel Extreme Learning Machine，KELM)作為集成學(xué)習(xí)算法的基分類器，同時考慮基分類器之間的差異性和準確性，提出一種基于差異性和準確性的加權(quán)調(diào)和平均(Diversity-Accuracy-Weighted Harmonic Average，D-AWHA)度量的選擇性集成算法，從UCI標準分類數(shù)據(jù)集中選擇了乳腺癌Breast、肺癌Lung、卵巢癌Ovarian三種基因數(shù)據(jù)進行實驗仿真，實驗結(jié)果表明該算法為癌癥基因表達數(shù)據(jù)的分析提供了一種有效的方法。

1 核超限學(xué)習(xí)機

ELM是單隱層的前饋神經(jīng)網(wǎng)絡(luò)訓(xùn)練算法，根據(jù)Huang等［12］提出的ELM理論，ELM的主要目的是同時減少訓(xùn)練誤差和輸出權(quán)重的范數(shù)。在傳統(tǒng)的ELM框架和最小二乘損失函數(shù)中，最小化訓(xùn)練誤差ζi和輸出權(quán)重的范數(shù)可表示為:

其中:β是輸出權(quán)重，C是懲罰參數(shù)，ζ是訓(xùn)練集的訓(xùn)練誤差矩陣，h(x)表示的是隱藏核映射，t是已標記樣本，n為樣本數(shù)。根據(jù)KKT理論，訓(xùn)練ELM等價于解決如下對偶問題:

其中:拉格朗日乘子αi對應(yīng)第i個訓(xùn)練樣本，因此，本文可以得到KKT(Karush-Kuhn-Tucker)最優(yōu)條件:

其中:α = ［α1，α2，…，αn］T，H 為隱層輸出矩陣，因此式(3)可等價為:

其中:I是單位矩陣。T可表示為:

因此，式(1)中最優(yōu)β可以通過分析獲得:

根據(jù)Mercer定理，任何半正定函數(shù)都可作為核函數(shù)，因此KELM的核矩陣可表示為:

其中:i，j∈ (1，2，…，N)，K(xi，xj) 是核函數(shù)。

常見的核函數(shù)有:

1)RBF核函數(shù)(Radical Basis Function Kernel):

2)線性核函數(shù)(Linear Kernel):

3)多項式核函數(shù)(Polynomial Kernel):

本文采用RBF核函數(shù)，核函數(shù)參數(shù)δ為默認值類別數(shù)的倒數(shù)。

因此，KELM的實際輸出可表示為:

2 選擇性集成

一般來說，一個集成算法分為兩個步驟:首先生成多個基分類器，然后通過某種結(jié)合策略將它們結(jié)合起來。根據(jù)文獻［6］，集成學(xué)習(xí)算法按照基分類器的生成方式大致可分為Bagging和 Boosting兩類。2002年，Zhou等［13］首次提出了選擇性集成的概念，并指出選擇集成系統(tǒng)中部分基分類器進行集成不僅能提高算法的速度，而且能提高集成系統(tǒng)整體的泛化性能。因此選擇性集成是一種特殊的集成學(xué)習(xí)方式，它旨在使用更少的基分類器達到更好的泛化能力，被認為比單一的分類算法和傳統(tǒng)的集成算法更有效。目前，許多選擇性集成方法被提出，如徐曉楊等［14］提出一種基于ELM的選擇性集成分類算法，Guo等［15］提出基于動態(tài)粗糙子空間的選擇性集成，Zhu等［16］提出基于改進的人工魚塘算法的ELM選擇性集成，都證明部分集成的效果優(yōu)于全部集成。根據(jù)文獻［5］的內(nèi)容，基分類器之間的差異性和基分類器自身的準確性是決定一個集成系統(tǒng)泛化性能的兩個重要因素，因此，如何選擇一組差異性高并且分類精度高的基分類器是本文的重點。

2．1 差異性度量

基分類器之間的差異性是決定一個集成系統(tǒng)泛化性能的關(guān)鍵因素，但測量基分類器之間的差異性不簡單，目前還沒有統(tǒng)一的定義形式。Kuncheva等［17］提出了10種度量基分類器之間差異性的方法，包括4種基于對(pair-wise)的方法:Q統(tǒng)計量(Q statistic)、相關(guān)系數(shù)(correlation coefficient)、不一致性度量(disagreement)和雙誤性(double fault)以及6種非基于對(non-pair-wise)的方法:投票熵(entropy of votes)、困難索引值(difficulty index)、Kohavi-Wolpert方差、評論一致性(interrater agreement)、泛化差異性(generalized diversity)和同步失敗差異性(coincident failure diversity)。考慮到基于對的差異性度量的計算復(fù)雜度較小，本文將采用基于對的差異性度量。

假設(shè)標簽數(shù)據(jù)集 D={d1，d2，…，dN}，對于二分類任務(wù)zj∈{0，1}，基分類器hi、hj的分類結(jié)果關(guān)系表如表1所示。

表1中N=N11+N10+N01+N00，N11表示基分類器hi和hj都分類正確，因此對于基分類器hi和hj，上述4種基于對的差異性度量方法Q統(tǒng)計量、相關(guān)系數(shù)ρ、不一致性度量D和雙誤性度量DF可分別表示為:

從式(12)～(13)可以看出，當(dāng)基分類器hi和hj共同分對或者分錯的越多時，Q統(tǒng)計量和相關(guān)系數(shù)ρ越接近1;反之如果兩個基分類器對同一樣本分出的不一致的結(jié)果越多則越接近－1。不一致性度量D是直接測量兩個基分類器對同一樣本分類結(jié)果不同的測度，當(dāng)基分類器同時分對或分錯時就越接近0，反之越接近1。雙誤性度量DF表示兩個基分類器同時將樣本分錯與總樣本數(shù)的占比。

因本文對基分類器之間的差異性的度量主要是考慮單個基分類器與其他基分類器分類結(jié)果之間的差異，并不只是考慮分錯的情況，因此將不采用雙誤性度量這一評價標準。因上述其他3種差異性度量方式的側(cè)重點不同，本文將綜合這3種測量方式對各個基分類器進行度量，考慮到Q統(tǒng)計量和相關(guān)系數(shù)ρ的值域是［－1，1］，且值越小，基分類器之間的差異性越大，因此本文將采用sigmoid函數(shù)對其結(jié)果進行處理:

在實驗中，本文將對每個基分類器的分類結(jié)果與其他所有的基分類器分類結(jié)果比較進行差異度計算，使用DIVi，j作為最后基分類器之間差異性度量，計算公式為:

2．2 D-A-WHA 度量

差異性一直被公認為是提高一個集成系統(tǒng)泛化性能的重要因素，因為如果基分類器之間是高度相關(guān)的，將它們結(jié)合以后也很難得到更好的分類結(jié)果;而如果基分類器的分類精度非常準確，這就意味著基分類器的相似度將很高，因此差異性也就較差［18］。吳建鑫等［19］提出集成泛化誤差公式:

為找出集成系統(tǒng)中差異性較大并且精度較高的基分類器，本文提出一種基于D-A-WHA度量的選擇性集成算法，通過對集成系統(tǒng)中所有的基分類器的差異性和準確性的量化，利用加權(quán)調(diào)和公式將多樣性和準確性有效結(jié)合，保證挑選出來的基分類器在保證準確性的同時差異性也大。為均衡基分類器之間的差異性(Diversity)和單個基分類器的準確率(Accuracy)對差異性和準確性進行歸一化:

因此第i個基分類器的差異性和準確率的調(diào)和平均數(shù)(Harmonic Average，HA)可定義為:

因為在不同的數(shù)據(jù)集和生成的不同基分類器的情況下，基分類器之間的差異性和基分類器本身的準確率對一個集成系統(tǒng)泛化性能的影響不一定相同，且基分類器之間的差異性很難被準確量化，需要對差異性和準確率設(shè)置權(quán)重進行調(diào)節(jié)，因此D-A-WHA度量可定義為:

當(dāng)ε=1時，公式退化為式(22)，當(dāng)ε越大時差異性影響越大，ε越小時準確率影響越大。

3 算法描述

通過以上分析，D-A-WHA選擇性集成算法的目的是選擇出一組差異性較大并且分類精度較高的基分類器進行集成，D-A-WHA的算法描述如下:

1)設(shè)置訓(xùn)練的分類器個數(shù)n和挑選的基分類器個數(shù)m;

2)將原始數(shù)據(jù)分為訓(xùn)練樣本和測試樣本，并使用n個KELM對訓(xùn)練樣本進行訓(xùn)練;

3)計算出每一個分類器的分類精度A和每一個分類器i對每個樣本的分類結(jié)果;

4)計算分類器的差異性D;

5)將分類器的準確性A和差異性D歸一化，按照式(23)計算每個基分類器的D-A-WHA度量;

6)取D-A-WHA度量前m的基分類器進行集成。

7)使用選擇的部分基分類器對測試樣本進行測試;

8)多次實驗求平均值。

算法流程如圖1所示。

圖1 基于D-A-WHA選擇性集成的流程Fig．1 Flow chart of selective ensemble based on D-A-WHA

4 實驗

4．1 實驗數(shù)據(jù)

為評估基于D-A-WHA測度的選擇性集成算法的性能，本文對該算法進行了實驗分析與仿真。本文在公開的UCI數(shù)據(jù)集中選擇了乳腺癌Breast、肺癌Lung和卵巢癌Ovarian三種基因數(shù)據(jù)集進行實驗和對比。因基因數(shù)據(jù)集樣本數(shù)小，但維度較高，在不進行處理的情況下能到達上萬維，因此在對數(shù)據(jù)進行分析之前要先對數(shù)據(jù)集進行ReliefF［20］降維，降維后的數(shù)據(jù)集基本信息如表2所示。

表2 數(shù)據(jù)集信息Tab．2 Data set information

4．2 實驗結(jié)果

本文將實驗中的KELM的隱藏節(jié)點數(shù)統(tǒng)一設(shè)為10，正則化系數(shù)為2，激活函數(shù)采用是的sigmoid函數(shù)。為避免算法的不穩(wěn)定性，所有實驗結(jié)果將取迭代30次的平均值。為了尋找在不同數(shù)據(jù)集中D-A-WHA的最優(yōu)權(quán)重ε，實驗在相同的基分類器個數(shù)下(基分類個數(shù)設(shè)為10)，多次取值找到最優(yōu)權(quán)重ε。圖2展示Breast數(shù)據(jù)集在ε不同取值時的精度，從圖中可以看出在ε為1時分類精度最高;按上述方法得到在Ovarian和Lung數(shù)據(jù)集中，權(quán)重ε分為1．7和1．5時集成效果較好。

圖2 Breast數(shù)據(jù)集下不同ε值分類精度的關(guān)系Fig．2 Relationship between classification accuracy and ε value on Breast dataset

為驗證基于D-A-WHA測度的選擇性集成算法的性能，將本文算法與傳統(tǒng)的Bagging、Adaboost以及將KELM作為基分類器的Bagging_KELM［21］作對比，基于D-A-WHA測度的選擇性集成算法的權(quán)重ε在Breast、Lung和Ovarian數(shù)據(jù)集中分別取1、1．7和1．5。實驗結(jié)果如圖3所示，可以看出D-A-WHA選擇性集成的分類精度明顯比其他算法高。

圖3 不同數(shù)據(jù)集下各算法分類精度Fig．3 Accuracy of each algorithm on different datasets

4．3 實驗分析

表3是不同集成學(xué)習(xí)算法取10個基分類器集成時精度、均方差和運行時間的實驗結(jié)果對比，可以看出相對于其他幾種算法，D-A-WHA算法不僅分類器精度最高，而且均方差更小，也就是更穩(wěn)定。同時比傳統(tǒng)的的Bagging和Adaboost運行更快，與Bagging_KELM相比運行速度相對較慢，但在精度和算法的穩(wěn)定性方面，D-A-WHA算法要優(yōu)于Bagging_KELM。

表3 不同算法的精度、均方差和運行時間對比Tab．3 Comparison of different algorithms in accuracy，mean square error and running time

5 結(jié)語

機器學(xué)習(xí)在生物信息學(xué)的研究中已經(jīng)越來越受到重視，但基于基因表達數(shù)據(jù)的癌癥分類仍是一個具有挑戰(zhàn)性的任務(wù)［22］。本文提出一種基于D-A-WHA選擇性度量的基因表數(shù)據(jù)選擇性集成算法，針對傳統(tǒng)的選擇性集成學(xué)習(xí)算法難以平衡基分類器之間的差異性和準確性的問題，同時考慮基分類器之間的差異性和準確性選擇部分基分類器進行集成。通過在癌癥基因表達數(shù)據(jù)集上的分析，該算法在精度、穩(wěn)定性和運行速度方面都優(yōu)于傳統(tǒng)的集成學(xué)習(xí)算法。但是對于如何更好地自動尋找D-A-WHA的最優(yōu)權(quán)重ε還無法確定，因此如何在不同數(shù)據(jù)集下自動選擇D-A-WHA的最優(yōu)權(quán)重ε將是我們下一步的研究方向。