陳 濤

(陜西理工大學 數(shù)學與計算機科學學院，漢中 723000)

DNA微陣列技術(shù)是分子生物學領(lǐng)域一項高通量測序技術(shù)，在一次實驗中可以同時測試細胞中成千上萬個基因活性，使得對單基因的研究進入到基因組學研究時代.其中，基于DNA微陣列的數(shù)據(jù)挖掘成為生物信息學領(lǐng)域研究熱點之一，對生物醫(yī)學發(fā)展具有重要意義[1,2].然而，微陣列具有高維、小樣本及高冗余等特點，易出現(xiàn)維數(shù)災(zāi)難和過擬合等問題，使得神經(jīng)網(wǎng)絡(luò)、支持向量機及貝葉斯等機器學習方法不能很好地解決微陣列的數(shù)據(jù)挖據(jù)問題.

近年來，“集成學習”被成功地用于微陣列數(shù)據(jù)挖據(jù)，其最大優(yōu)勢是：一個基分類器的錯分可以被其他基分類器的正確分類所抵消而達到一種平衡，從而降低選擇到性能較差分類器的風險，同時提高集成分類器的性能.Krogh 等[3]指出：增加基分類器之間的差異性和基分類器的個體精度是提高集成學習性能的關(guān)鍵所在.此后，Bagging、Boosting、隨機子空間、隨機森林和旋轉(zhuǎn)森林等一系列集成方法被提出，并取得較好的效果.但是，這些方法集成了所有基分類器，導致以下問題：(1)多個分類器的存儲需要消耗大量計算機內(nèi)存；(2)對多個分類器的輸出進行集成需耗費大量計算時間，降低了算法的運行效率；(3)參與集成的基分類器數(shù)量越多，其之間的差異性容易受到影響，從而降低集成系統(tǒng)的泛化性能.

2002年，周志華等[4]提出的選擇性集成學習有效的解決以上問題，主要是從訓練的所有基分類器中選擇部分分類器進行集成而獲得更好的分類效果，從而有效地解決了集成分類中內(nèi)存消耗大、運行效率低及集成性能受限等問題.此后，選擇性集成分類方法受到廣大研究者的關(guān)注，陸續(xù)提出一系列選擇性集成方法，如周志華等[4]采用遺傳算法實現(xiàn)選擇集成；Martinez等[5]采用啟發(fā)式規(guī)則提出基于精確度的選擇性集成方法；Bryll等[6]采用改進的粒子群算法實現(xiàn)基分類器選擇；Castro等[7]采用人工免疫算法進行選擇性集成；Li等[8]使用聚類算法構(gòu)建選擇性集成.其中，基于遺傳算法、粒子群和人工免疫等啟發(fā)式智能優(yōu)化算法構(gòu)建選擇性集成是一種有效方法.

教與學優(yōu)化算法(TLBO)[9]是2011年Rao等提出的一種基于自然的啟發(fā)式群體智能優(yōu)化算法.其主要思想是通過教師的“教”和學生之間的互相“學”，提高學生整體學習水平.與其他智能優(yōu)化算法相比，TLBO最大優(yōu)勢在于不需要設(shè)置過多參數(shù).智能優(yōu)化算法參數(shù)設(shè)置是一件比較困難的事情，且算法參數(shù)往往對于算法性能影響較大，但目前沒有較好的參數(shù)選擇的方法或原則，這給智能優(yōu)化算法的廣泛應(yīng)用帶來一定局限.正因此，TLBO算法以其自身獨特的優(yōu)點被廣泛應(yīng)用于各種優(yōu)化領(lǐng)域，取得較好的優(yōu)化效果.然而，TLBO算法也因為種群多樣性過早喪失而易陷入局部最優(yōu)，導致優(yōu)化精度不高以及算法搜索速度較慢等不足[10].

本文提出了一種新的集成分類方法，首先基于bootstrap和鄰域互信息的雙重擾動機制產(chǎn)生訓練子集并訓練基分類器，這將增加基分類之間的差異性和提高基分類器的個體精度；然后設(shè)計了改進的教與學優(yōu)化算法實現(xiàn)基分類選擇性集成；最后通過微陣列數(shù)據(jù)集上的仿真實驗來驗證算法的有效性.

1 鄰域互信息模型

鄰域互信息(NMI)是在互信息概念的基礎(chǔ)上，將鄰域引入Shannon熵理論，實現(xiàn)對變量之間的線性或非線性關(guān)系進行度量.鄰域互信息可以直接處理連續(xù)型數(shù)據(jù)，有效地避免了互信息使用過程中進行離散化而帶來的信息損失問題，因而對微陣列數(shù)據(jù)的屬性約簡更加有效[11].

定義設(shè)樣本集U={x1,x2,…，xn}，屬性集F={f1,f2,…，fm}，屬性子集R,S?F，則R和S之間的鄰域互信息定義為：

其中，δR(xi)、δS(xi)和δRUS(xi)分別表示在屬性子空間R、S和RUS中樣本的鄰域.

算法1 基于前向貪心搜索策略和鄰域互信息的屬性約簡算法

2 改進的教與學優(yōu)化算法

2.1 教與學優(yōu)化算法TLBO

TLBO算法是一種基于自然的啟發(fā)式智能優(yōu)化算法，其主要思想是通過教師的“教”引導學生學習，同時學生之間進行互相“學”習，最終提高學生整體學習水平.TLBO算法由教師的“教”和學生的“學”兩個過程組成，“教”是讓學生向教師學習，而“學”則是學生之間進行互相學習.其中，“教”使得每個學員都向教師學習，向班級中的最優(yōu)者靠近，搜索速度較快.但正因為過早地向教師靠近，導致種群多樣性的過早丟失，易陷入局部最優(yōu)；“學”使學生互相學習，取長補短，優(yōu)于學員在彼此之間小范圍內(nèi)學習，不會過早地向全局最優(yōu)方向凝聚，一定程度上保持了種群多樣性，保證算法的全局搜索性能.

TLBO算法最大優(yōu)勢是不需要設(shè)置過多參數(shù)，且具有原理簡單、易理解、優(yōu)化效果相對較好等優(yōu)點，被廣泛應(yīng)用于各種優(yōu)化領(lǐng)域.

2.2 改進的教與學優(yōu)化算法MyTLBO

TLBO算法也存在種群多樣性過早喪失而易陷入局部最優(yōu)、優(yōu)化精度不高以及搜索速度較慢等不足[12]，本文從以下三方面對算法進行改進，提出MyTLBO算法.

(1)“教”階段改進

forj=1:NP

TF=round(1+rand(1,D))；

end

2)“教”使得學員全部向教師學習，這樣過早地向班級中最優(yōu)個體聚集，雖能加快搜索速度，但往往導致種群多樣性的過早喪失，易陷入局部最優(yōu).此處，借鑒遺傳算法的“交叉”思想，在“教”之后，加入交叉操作，能把群體保持在合適區(qū)域內(nèi)的同時，搜索新的解空間.

forj=1:2:NP

ifrand

隨機選擇一個交叉點位k∈{2,…，D-1}；

end

end

(2)“自學”階段改進

學員主要通過“教”和“學”兩個過程進行學習，但沒有考慮到個體自身學習，過分依賴他人，缺乏主觀能動性和學習積極性.此處，借鑒遺傳算法中“變異”操作使學員進行“自學”，獲得更優(yōu)解.

forj=1:NP

ifrand

隨機選擇一個變異點位k∈{1,…，D}；

end

end

(3)精英策略

每代優(yōu)化之前，選擇種群中最好個體作為精英解，當種群經(jīng)過一次優(yōu)化后，用精英解替換當前種群中的最差解，保持最優(yōu)解遺傳到下一代，增強算法的收斂性能.

改進的教與學優(yōu)化算法MyTLBO流程圖見圖1所示.

2.3 個體向量表示與適應(yīng)度函數(shù)構(gòu)造

(1)個體向量表示

班級中的學員被表示成一個由“0”和“1”組成的向量，代表從當前基分類器集中選擇部分分類器組成的一個序列，如“010…101” ，其中“1”表示對應(yīng)位置分類器被選，“0”表示對應(yīng)位置分類器未被選中.

(2)適應(yīng)度函數(shù)構(gòu)造

選擇基分類器的目的是使得選擇到的基分類器構(gòu)成的集成分類器具有更高的分類精度，所以，算法中以分類精度作為評價學員水平的標準，即在訓練集上采用交叉驗證方法獲得的平均分類精度作為適應(yīng)度函數(shù)，其適應(yīng)度值越大，則分類精度越大.

圖1 改進的教與學優(yōu)化算法MyTLBO流程圖Fig.1 The flow chart of the improved TLBO algorithm

3 本文算法

本文提出一種新的集成分類方法，整體框架如圖2所示，具體步驟如下：

(1)基于雙重擾動樣本集的方法訓練產(chǎn)生基分類器.一方面，通過bootstrap技術(shù)實現(xiàn)樣本擾動獲得具有差異性的訓練子集；另一方面，利用Kruskalwallis和鄰域互信息方法進行屬性約簡實現(xiàn)特征擾動，既可加大訓練子集之間的差異性，又通過屬性約簡剔除噪聲，有助于提高基分類器的個體精度.

(2)基于改進的教與學優(yōu)化算法(MyTLBO)實現(xiàn)基分類器的選擇性集成.針對教與學優(yōu)化算法容易造成種群多樣性過早丟失而陷入局部最優(yōu)，設(shè)計了一種改進的教與學優(yōu)化算法(MyTLBO)實現(xiàn)基分類器的選擇性集成.

圖2 本文算法的整體框架Fig.2 The overall framework of the algorithm

4 仿真實驗

4.1 實驗數(shù)據(jù)

為驗證本文算法有效性，采用公共微陣列數(shù)據(jù)集進行仿真實驗，具體描述見表1.

表1 DNA微陣列數(shù)據(jù)集

4.2 實驗方法與參數(shù)設(shè)置

為驗證本文算法有效性，Bagging，AdaBoost，Ensemble 1(Bootstrap+Kruskalwallis+NMI)，Ensemble 2(Bootstrap+Kruskalwallis+NMI+TLBO)和Ensemble 3(Bootstrap+Kruskalwallis +NMI+MTLBO) 等5種算法與本文算法進行對比，其中MTLBO[13]是Rao提出的一種優(yōu)化精度和收斂速度較高的TLBO改進算法.

TLBO、MTLBO和MyTLBO參數(shù)設(shè)置：班級規(guī)模為20，最大迭代次數(shù)為400，所有基分類器總數(shù)為40，Kruskalwallis預(yù)選基因數(shù)為300.

每個實驗均重復(fù)20次，取20出實驗結(jié)果的平均值為最終結(jié)果，可以排除試驗結(jié)果的偶然性，其結(jié)果更具有一般性，更具說服力.

4.3 實驗結(jié)果及分析

(1)不同算法分類精度和分類器數(shù)量的比較

表2比較了不同算法的分類精度和基分類器的數(shù)量.很容易發(fā)現(xiàn)：

1)本文算法在所有數(shù)據(jù)集上的分類精度明顯優(yōu)于其他算法，至少分別被提高1%、2.79%、3.22%和2.7%，說明基于雙重擾動和改進教與學優(yōu)化算法構(gòu)建的選擇性集成分類系統(tǒng)具有明顯優(yōu)勢.另外，與Ensemble 2和Ensemble 3比較，說明本文提出的MyTLBO比TLBO和MTLBO更有效，優(yōu)化精度更高.

2)Ensemble 1在所有數(shù)據(jù)集上的分類精度明顯優(yōu)于Bagging和AdaBoost，至少分別被提高3.33%、20.7%、13.34%和3.34%，說明本文采用Bootstrap與Kruskalwallis及NMI的雙重擾動方法，既增強分類器之間的差異性，又提升分類器的個體精度，有效地提升集成分類器的泛化性能.另外，本文算法、Ensemble 2、Ensemble 3與Bagging，AdaBoost、Ensemble 1對比發(fā)現(xiàn)，選擇性集成是提高集成分類器精度的有效方法.

3)本文算法最終用于集成的基分類器數(shù)量在所有數(shù)據(jù)集上分別平均為13、5.85、14.1和6.5，遠遠小于40，表明僅用較少的分類器進行集成就可以獲得更高的分類精度，既減少內(nèi)存占用，又提高集成系統(tǒng)的泛化性能，再次證明選擇性集成的效果明顯.

表2 不同算法分類精度比較(%)Tab.2 Comparison of classification accuracy with the different algorithms(%)

(2)TLBO、MTLBO和MyTLBO算法性能比較

表3對比了TLBO、MTLBO和MyTLBO算法構(gòu)建的選擇性集成器的分類精度，表中avg表示各算法在4個數(shù)據(jù)集上分類精度的平均值.

表3 TLBO、MTLBO和MyTLBO算法性能比較Tab.3 Performance comparison of TLBO、MTLBO and MyTLBO

從表3發(fā)現(xiàn)，無論是最優(yōu)值、平均值和最差值，基于MyTLBO構(gòu)建的本文算法分類精度明顯優(yōu)于MTLBO和TLBO設(shè)計的集成方法.特別從avg值來看，MyTLBO算法的最優(yōu)、平均和最差分類精度相比其他算法至少提高1.39%、2.43%和3.4%，說明MyTLBO算法具有更強的收斂性和全局搜索能力，明顯優(yōu)于MTLBO和TLBO算法.

圖3繪制了TLBO、MTLBO和MyTLBO算法的平均進化曲線圖和多次試驗統(tǒng)計盒圖.

圖3 平均進化曲線圖和統(tǒng)計盒圖Fig.3 The average evolutionary curve and statistical box chart

1)優(yōu)化精度與速度比較

從圖3看出，MyTLBO算法在所有數(shù)據(jù)集上的優(yōu)化精度高于TLBO和MTLBO.TLBO容易陷入局部最優(yōu)點，主要是因為迭代初期，班級成員均向教師聚集，導致種群多樣性過早喪失而陷入局部最優(yōu).MTLBO算法因為增加了種群多樣性，更容易跳出局部最優(yōu)，尋找全局最優(yōu)解.但從圖中發(fā)現(xiàn)，MTLBO算法在迭代次數(shù)達到一定次數(shù)后，也因為種群多樣性的丟失而陷入局部最優(yōu)，所以MTLBO算法也很難搜索到全局最優(yōu)解.MyTLBO算法既增強了種群多樣性，使得迭代初期能保證較大的搜索范圍，而不至于陷入局部最優(yōu)；同時變異操作提升了種群的局部搜索能力，所以進化曲線隨迭代次數(shù)的增加不斷階梯型遞增，保持了更強的全局和局部搜索能力，保證了全局最優(yōu)解的獲得.

還發(fā)現(xiàn)，MyTLBO的搜索速度明顯比MTLBO和TLBO快，即在迭代次數(shù)較小時就能達到與MTLBO、TLBO同樣的優(yōu)化精度，甚至更高.

2)算法穩(wěn)定性比較

圖3顯示了三種算法20次實驗結(jié)果的統(tǒng)計盒圖.可以發(fā)現(xiàn)，除Gliomas，MyTLBO算法在其他數(shù)據(jù)集上的穩(wěn)定性明顯好于TLBO和MTLBO算法.

綜合分析，MyTLBO算法相比MTLBO和TLBO算法，具有優(yōu)化精度高、搜索速度快和穩(wěn)定性好等優(yōu)勢，說明本文提出的MyTLBO算法是有效的、具有一定的優(yōu)越性.

(3)基于統(tǒng)計學理論比較算法性能

從表4看到，Bagging、Adaboost、Ensemble 1、Ensemble 2和 Ensemble 3等算法與本文算法的幾何平均正確率r分別是0.8807、0.8836、0.9521、0.9710和0.9889，表明本文算法明顯優(yōu)于其他5種算法；從s統(tǒng)計量看，本文算法在所有數(shù)據(jù)集上結(jié)果均優(yōu)于其他算法；從“平均”值看，本文算法的平均精度為97.11%，遠優(yōu)于其他算法.

進一步得到這些算法優(yōu)劣排序依次是：本文算法、Ensemble 3、Ensemble 2、Ensemble 1、Adaboost和Bagging.

5 結(jié)語

本文提出了一種新的選擇性集成分類方法，該方法基于Bootstrap技術(shù)和Kruskalwallis與NMI屬性約簡方法實現(xiàn)數(shù)據(jù)集的雙重擾動，增加基分類器之間的差異性和準確性，然后采用改進的教與學優(yōu)化算法構(gòu)造選擇性集成分類器.仿真實驗表明：本文算法在分類精度、穩(wěn)定性等方面具有較強的優(yōu)勢.