基于雙重?cái)_動(dòng)與改進(jìn)教與學(xué)優(yōu)化算法的DNA微陣列集成分類

陳 濤

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

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

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

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

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

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

1 鄰域互信息模型

鄰域互信息(NMI)是在互信息概念的基礎(chǔ)上，將鄰域引入Shannon熵理論，實(shí)現(xiàn)對(duì)變量之間的線性或非線性關(guān)系進(jìn)行度量.鄰域互信息可以直接處理連續(xù)型數(shù)據(jù)，有效地避免了互信息使用過程中進(jìn)行離散化而帶來的信息損失問題，因而對(duì)微陣列數(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 改進(jìn)的教與學(xué)優(yōu)化算法

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

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

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

2.2 改進(jìn)的教與學(xué)優(yōu)化算法MyTLBO

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

(1)“教”階段改進(jìn)

forj=1:NP

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

end

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

forj=1:2:NP

ifrand

隨機(jī)選擇一個(gè)交叉點(diǎn)位k∈{2,…，D-1}；

end

end

(2)“自學(xué)”階段改進(jìn)

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

forj=1:NP

ifrand

隨機(jī)選擇一個(gè)變異點(diǎn)位k∈{1,…，D}；

end

end

(3)精英策略

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

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

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

(1)個(gè)體向量表示

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

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

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

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

3 本文算法

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

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

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

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

4 仿真實(shí)驗(yàn)

4.1 實(shí)驗(yàn)數(shù)據(jù)

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

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

4.2 實(shí)驗(yàn)方法與參數(shù)設(shè)置

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

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

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

4.3 實(shí)驗(yàn)結(jié)果及分析

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

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

1)本文算法在所有數(shù)據(jù)集上的分類精度明顯優(yōu)于其他算法，至少分別被提高1%、2.79%、3.22%和2.7%，說明基于雙重?cái)_動(dòng)和改進(jìn)教與學(xué)優(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的雙重?cái)_動(dòng)方法，既增強(qiáng)分類器之間的差異性，又提升分類器的個(gè)體精度，有效地提升集成分類器的泛化性能.另外，本文算法、Ensemble 2、Ensemble 3與Bagging，AdaBoost、Ensemble 1對(duì)比發(fā)現(xiàn)，選擇性集成是提高集成分類器精度的有效方法.

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

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

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

表3對(duì)比了TLBO、MTLBO和MyTLBO算法構(gòu)建的選擇性集成器的分類精度，表中avg表示各算法在4個(gè)數(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è)計(jì)的集成方法.特別從avg值來看，MyTLBO算法的最優(yōu)、平均和最差分類精度相比其他算法至少提高1.39%、2.43%和3.4%，說明MyTLBO算法具有更強(qiáng)的收斂性和全局搜索能力，明顯優(yōu)于MTLBO和TLBO算法.

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

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

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

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

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

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

圖3顯示了三種算法20次實(shí)驗(yàn)結(jié)果的統(tǒng)計(jì)盒圖.可以發(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)計(jì)學(xué)理論比較算法性能

從表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)計(jì)量看，本文算法在所有數(shù)據(jù)集上結(jié)果均優(yōu)于其他算法；從“平均”值看，本文算法的平均精度為97.11%，遠(yuǎn)優(yōu)于其他算法.

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

5 結(jié)語

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