面向基因數(shù)據(jù)分類的AGA-ELM算法研究

孟亞瓊,陸慧娟,嚴(yán) 珂,關(guān) 偉

(1.中國計(jì)量大學(xué) 信息工程學(xué)院,浙江 杭州 310018;2.中國計(jì)量大學(xué) 現(xiàn)代科技學(xué)院,浙江 杭州 310018)

面向基因數(shù)據(jù)分類的AGA-ELM算法研究

孟亞瓊1,陸慧娟1,嚴(yán) 珂1,關(guān) 偉2

(1.中國計(jì)量大學(xué) 信息工程學(xué)院,浙江 杭州 310018;2.中國計(jì)量大學(xué) 現(xiàn)代科技學(xué)院,浙江 杭州 310018)

對基因表達(dá)數(shù)據(jù)進(jìn)行分類時,超限學(xué)習(xí)機(jī)(ELM)算法具有學(xué)習(xí)效率高、泛化能力強(qiáng)、分類精度高的優(yōu)點(diǎn).為了解決超限學(xué)習(xí)機(jī)算法受輸入權(quán)值矩陣和隱含層偏差隨機(jī)初始化的影響,本文利用自適應(yīng)遺傳算法(AGA)具有良好的全局搜索效果對超限學(xué)習(xí)機(jī)的輸入權(quán)值矩陣和隱含層偏差進(jìn)行優(yōu)化,提出了基于自適應(yīng)遺傳算法優(yōu)化超限學(xué)習(xí)機(jī)(AGA-ELM)的分類算法.通過實(shí)驗(yàn)表明,該算法與已有的ELM、GA-ELM以及SVM算法相比，分類精度更高,可用于基因數(shù)據(jù)分類.

超限學(xué)習(xí)機(jī);自適應(yīng)遺傳算法;基因表達(dá)數(shù)據(jù)分類

基因數(shù)據(jù)存在著樣本小、維數(shù)高以及非線性等特點(diǎn),使得基因表達(dá)數(shù)據(jù)的分析存在著一定的困難.目前比較新的適用于基因表達(dá)數(shù)據(jù)分類的方法主要有:二維主成分分析法、二維線性判別分析法、支持向量機(jī)方法、K最近鄰法、支持向量機(jī)算法以及超限學(xué)習(xí)機(jī)(extreme learning machine, ELM)算法[1-2].本文主要研究的是ELM.

超限學(xué)習(xí)機(jī),是由黃廣斌提出來的求解單隱層神經(jīng)網(wǎng)絡(luò)的算法.后來又有許多專家學(xué)者對ELM進(jìn)行了研究.羅庚合[3]提出一種基于可拓聚類的ELM神經(jīng)網(wǎng)絡(luò).該神經(jīng)網(wǎng)絡(luò)是以隱含層神經(jīng)元的徑向基中心向量作為輸入層權(quán)值,采用可拓聚類算法動態(tài)調(diào)整隱含層節(jié)點(diǎn)數(shù)目和徑向基中心,并根據(jù)所確定的輸入層權(quán)值,利用Moore-Penrose廣義逆快速完成輸出層權(quán)值求解.王杰[4]等人提出粒子群超限學(xué)習(xí)機(jī)算法,利用粒子群優(yōu)化算法優(yōu)化選擇超限學(xué)習(xí)機(jī)的輸入層權(quán)值和隱含層偏差,從而計(jì)算出輸出權(quán)值矩陣.LU H J[5]等人提出用帶活躍算子的PSO算法對KELM中的內(nèi)權(quán)初始參數(shù)進(jìn)行優(yōu)化、設(shè)定,以得到最優(yōu)KELM分類器.朱志杰[6]等人提出了將遺傳算法與超限學(xué)習(xí)機(jī)相結(jié)合的沖擊地壓預(yù)測的新方法,采用遺傳算法對超限學(xué)習(xí)機(jī)的輸入權(quán)值矩陣和隱含層偏差進(jìn)行優(yōu)化.解決了ELM受隨機(jī)初始化權(quán)值矩陣帶來的不利影響,但是,遺傳算法容易早熟收斂,陷入局部最優(yōu).

為了解決上述問題,本文提出了基于自適應(yīng)遺傳算法(adaptive genetic algorithm, AGA)的超限學(xué)習(xí)機(jī)分類算法.ELM最大的特點(diǎn)是對于傳統(tǒng)的神經(jīng)網(wǎng)絡(luò),尤其是單隱層前饋神經(jīng)網(wǎng)絡(luò)(SLFNs),在保證學(xué)習(xí)精度的前提下比傳統(tǒng)的學(xué)習(xí)算法速度更快.但是ELM的輸入權(quán)值矩陣和隱含層偏差是隨機(jī)初始化的,而這些權(quán)值并沒有包含任何訓(xùn)練樣本的先驗(yàn)知識,因此可能會導(dǎo)致ELM的擬合精度降低.而自適應(yīng)遺傳算法作為一種基于自然選擇與進(jìn)化機(jī)制的功能強(qiáng)大的搜索算法,AGA的操作不需要規(guī)劃對象的先驗(yàn)性知識,只需要計(jì)算個體的適應(yīng)度值并篩選,具有良好的全局搜索效果.這里就利用自適應(yīng)遺傳算法優(yōu)化ELM的輸入權(quán)值矩陣和隱含層偏差,該算法能根據(jù)最后的分類精度相應(yīng)地調(diào)整權(quán)值,從而達(dá)到提高分類精度的效果.實(shí)驗(yàn)表明優(yōu)化后的算法分類精度明顯提升,且穩(wěn)定性更好.

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

ELM是一種快速學(xué)習(xí)算法,與傳統(tǒng)的單隱層前饋神經(jīng)網(wǎng)絡(luò)相比,具有分類準(zhǔn)確率高、泛化能力好、調(diào)節(jié)參數(shù)少等優(yōu)點(diǎn)[7].ELM可以隨機(jī)初始化輸入權(quán)重和偏置并得到相應(yīng)的輸出權(quán)重.

ELM實(shí)現(xiàn)的過程描述如下:對一個單隱層前饋神經(jīng)網(wǎng)絡(luò),假設(shè)給出N個任意樣本(Xi,ti),其中Xi=[xi1,xi2,…,xin]T∈Rn,ti=[ti1,ti2,…,tin]T∈Rm.對于一個有L個隱層節(jié)點(diǎn)的單隱層神經(jīng)網(wǎng)絡(luò)可以表示為

(1)

其中:定義g(x)為激活函數(shù),Wi=[wi1,wi2,…,win]T為輸入權(quán)重,βi為輸出權(quán)重,bi是第i個隱層單元的偏置.Wi·Xj表示W(wǎng)i和Xj的內(nèi)積.

式(1)可用矩陣表示為Hβ=T.其中

H(W1,…,WL,b1,…,bL,X1,…,XL)=

其中:H是隱層節(jié)點(diǎn)的輸出,β為輸出權(quán)重,T為期望輸出.

2 利用自適應(yīng)遺傳算法優(yōu)化超限學(xué)習(xí)機(jī)的分類算法

2.1 遺傳算法

遺傳算法(genetic algorithm, GA)最初是由美國Michigan大學(xué)的J.Holland教授提出來的.遺傳算法是模仿自然界生物進(jìn)化機(jī)制發(fā)展起來的隨機(jī)全局搜索和優(yōu)化方法,它借鑒了達(dá)爾文的進(jìn)化論和孟德爾的遺傳學(xué)說[8].其本質(zhì)是一種高效、并行、全局搜索的方法,它能在搜索過程中自動獲取和積累有關(guān)搜索空間的知識,并自適應(yīng)地控制搜索過程以求得最優(yōu)解[9].

遺傳算法的基本步驟[10]如下:

1)設(shè)置初始種群大小M、終止代數(shù)T、交叉概率Pc、變異概率Pm,進(jìn)化代數(shù)t=0,隨機(jī)生成M(應(yīng)為偶數(shù))個個體,得到初始化種群;

2)計(jì)算各個個體的適應(yīng)度;

3)以交叉概率Pc進(jìn)行交叉操作;

4)以變異概率Pm進(jìn)行變異操作;

6)如果t

2.2 自適應(yīng)遺傳算法

遺傳算法在運(yùn)算過程中往往會出現(xiàn)個別適應(yīng)度很高的個體,導(dǎo)致這個個體被選擇的概率遠(yuǎn)遠(yuǎn)大于其他個體,可能一再被選擇,從而充斥下一代種群,使進(jìn)化難以進(jìn)行,出現(xiàn)早熟現(xiàn)象.

為解決上述問題,提出了自適應(yīng)遺傳算法[11-12].自適應(yīng)遺傳算法是一種交叉率和變異率可根據(jù)適應(yīng)度自調(diào)整的改進(jìn)遺傳算法,具有更快的收斂速度和全局搜索能力.本算法用適應(yīng)度差值來衡量適應(yīng)度的差異大小,先定義調(diào)節(jié)因子γ:

(2)

Δf=fmax-fmin,ΔF=Fmax-Fmin.

(3)

其中,Δf為當(dāng)前群體中適應(yīng)度的差值,ΔF為適應(yīng)度的差值的理論最大值,fmin為當(dāng)前群體中適應(yīng)度的最小值,fmax為當(dāng)前群體中適應(yīng)度的最大值,Fmin為適應(yīng)度的理論最小值,Fmax為適應(yīng)度的理論最大值,易知γ的取值范圍為[0,1].

對適應(yīng)度函數(shù)進(jìn)行變換

f′(x)=f(x)+k(γ-0.5).

(4)

其中,f(x)為原適應(yīng)度函數(shù),f′(x)為變換后的適應(yīng)度函數(shù),k為正常數(shù),根據(jù)具體情況進(jìn)行設(shè)置,越大則變換力度越大,但應(yīng)盡量保證適應(yīng)度值非負(fù),這里取k=5.

利用SPSS 16.0軟件對49個樣點(diǎn)土壤的8項(xiàng)養(yǎng)分指標(biāo)進(jìn)行主成分分析，并對各土壤樣品的綜合得分以歐式距離為衡量土壤間差異大小的指標(biāo)，采用類平均法進(jìn)行系統(tǒng)聚類。主成分分析的主要運(yùn)算步驟包括[7]：

當(dāng)群體中適應(yīng)度差值較大時(γ>0.5),個體適應(yīng)度都增加k(γ-0.5),則適應(yīng)度小的個體增加的比例大,被選擇的概率將增大,有利于維持群體的多樣性;反之,亦然.

交叉概率Pc和變異概率Pm分別定義為:

Pc=γ,

(5)

Pm=0.1(1-γ).

(6)

在進(jìn)化初期,個體差異較大,交叉產(chǎn)生更好個體的可能性也較大,如果增大交叉概率,減小變異概率,將加快進(jìn)化進(jìn)程;在進(jìn)化后期,由于個體差異較小,導(dǎo)致交叉產(chǎn)生更好的個體的可能性減少,如果減小交叉概率可減小計(jì)算量,增大變異概率可保持群體的多樣性.

2.3 AGA-ELM

為解決ELM隨機(jī)初始化輸入權(quán)值矩陣和隱含層偏差而帶來的一系列問題[13].本文利用AGA優(yōu)化ELM的輸入權(quán)值矩陣和隱含層偏差.

算法的具體步驟如下:

1)產(chǎn)生初始種群,粒子數(shù)N,取N=10.種群個體即粒子數(shù)是由隱層節(jié)點(diǎn)K和粒子數(shù)N組成的,粒子長度D=N·K.

2)確立適應(yīng)度函數(shù),利用ELM算法計(jì)算出輸出權(quán)值矩陣,其中隱含層激活函數(shù)為sigmoid函數(shù).再利用訓(xùn)練樣本計(jì)算初始化種群的每個個體的分類準(zhǔn)確率f(nint),由f(x)=1-f(nint)計(jì)算出誤分類率f(x).根據(jù)公式(4)計(jì)算出該自適應(yīng)遺傳算法的適應(yīng)度函數(shù).

3)判斷是否滿足終止條件,若滿足則停止;否則,繼續(xù)下一步.

4)以交叉概率,即公式(5)進(jìn)行交叉操作.

5)以變異概率,即公式(6)進(jìn)行變異操作.

6)采用輪盤賭注法進(jìn)行選擇,產(chǎn)生新群體.

7)解碼,得到輸入權(quán)重Wi,和隱含層偏差bi.

8)利用ELM算法計(jì)算出分類精度并輸出分類精度.先計(jì)算隱含層矩陣H,計(jì)算出連接權(quán)值,求出分類精度.返回3).

9)結(jié)束.

算法流程圖如圖1.

3 實(shí) 驗(yàn)

為了評估AGA-ELM算法的性能,本文對該算法進(jìn)行了實(shí)驗(yàn)分析與仿真,從UCI標(biāo)準(zhǔn)測試數(shù)據(jù)集中選擇Breast、Brain、Colon以及Leukemia四個基因數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)訓(xùn)練與測試,這4個數(shù)據(jù)集分別為腫瘤數(shù)據(jù)中的乳腺癌數(shù)據(jù)集、腦癌數(shù)據(jù)集、結(jié)腸癌數(shù)據(jù)集以及白血病數(shù)據(jù)集。選用的每個數(shù)據(jù)集經(jīng)過ReliefF[14]降維后的基本信息的如表1.

表1 數(shù)據(jù)集信息表

圖1 算法流程圖Figure 1 Description of AGA-ELM

本實(shí)驗(yàn)是在Core i5-4790 CPU 3.6 GHz,6 G內(nèi)存,操作系統(tǒng)為Windows8.1的環(huán)境下,通過Matlab編程實(shí)現(xiàn)仿真的.

為了驗(yàn)證AGA-ELM算法高效性,分別用ELM、GA-ELM、以及SVM算法分別在4個數(shù)據(jù)集上分別采用10次5折交叉驗(yàn)證,將數(shù)據(jù)集分成五份,輪流將其中4份作為訓(xùn)練數(shù)據(jù)集,1份作為測試數(shù)據(jù)集,進(jìn)行實(shí)驗(yàn)[15].取10次結(jié)果精度的平均值作為算法的精度,各數(shù)據(jù)集在不同迭代次數(shù)下的分類精度如表2.為了更直觀地表示出隨著迭代次數(shù)的變化分類精度也相應(yīng)地變化,各數(shù)據(jù)集下的分類精度圖如圖2～5.

圖2 Breast數(shù)據(jù)集下各算法分類精度Figure 2 Classification accuracy of Breast dataset

圖3 Brain數(shù)據(jù)集下各算法分類精度Figure 3 Classification accuracy of Brain dataset

表2 基因數(shù)據(jù)集下各算法的分類精度

圖4 Colon數(shù)據(jù)集下各算法分類精度Figure 4 Classification accuracy of Colon dataset

圖5 Leukemia數(shù)據(jù)集下各算法分類精度Figure 5 Classification accuracy of Leukemia dataset

由上述實(shí)驗(yàn)結(jié)果可知:在基因數(shù)據(jù)集上,ELM算法隨著迭代次數(shù)增加,分類精度一直處于上下波動的狀態(tài),極不穩(wěn)定.分別用GA、AGA算法對ELM算法進(jìn)行參數(shù)優(yōu)化后,算法的分類精度不再上下波動.隨著迭代次數(shù)增加,算法的分類精度穩(wěn)步上升,這說明了采用參數(shù)優(yōu)化的必要性.但是,由于GA算法容易導(dǎo)致早熟收斂,而AGA算法克服了早熟收斂這一缺點(diǎn),所以AGA-ELM算法的優(yōu)化的效果是最好的.

本文將AGA-ELM算法在迭代次數(shù)為55次時與目前流行的支持向量機(jī)(SVM)[16]的精度對比可知,AGA-ELM算法在Breast、Brain以及Colon數(shù)據(jù)集的精度都比SVM高.見表3.

表3 AGA-ELM與SVM算法分類精度對比

綜上所述,AGA-ELM算法通過利用AGA算法優(yōu)化ELM的輸入權(quán)值矩陣和隱含層偏差,取得良好效果,在分類精度以及穩(wěn)定性上均優(yōu)于其他算法,說明AGA-ELM是一種十分可靠有效的分類算法.

4 結(jié) 論

采用AGA對ELM輸入權(quán)值矩陣和隱含層偏差進(jìn)行優(yōu)化,避免了輸入權(quán)值矩陣和隱含層偏差隨機(jī)性對ELM預(yù)測精度的影響,提高了預(yù)測準(zhǔn)確率.與已有類似算法在不同數(shù)據(jù)集上進(jìn)行分類對比實(shí)驗(yàn),證明提出的方法具有更好的分類性能;并且在基因數(shù)據(jù)分類等領(lǐng)域有較好的應(yīng)用前景,值得進(jìn)一步深入研究.

[1] 李珉.基于基因表達(dá)譜的腫瘤數(shù)據(jù)分類[D].長沙:湖南大學(xué),2012. LI M. The Research on Gene Expression Profiles Data for Tumor Classification[D].Changsha: Hunan University,2012.

[2] 陸慧娟,安春霖,馬小平,等.基于輸出不一致測度的極限學(xué)習(xí)機(jī)集成的基因表達(dá)數(shù)據(jù)分類[J].計(jì)算機(jī)學(xué)報(bào),2013,36(2):341-348. LU H J, AN C L, MA X P, et al. Disagreement measure based ensemble of extreme learning machine for gene expression data classification[J].Chinese Journal of Computers,2013,36(2):341-348.

[3] 羅庚合.基于可拓聚類的極限學(xué)習(xí)機(jī)神經(jīng)網(wǎng)絡(luò)[J].計(jì)算機(jī)應(yīng)用,2013,33(7):1942-1945. LUO G H. Extension clustering-based extreme learning machine neural network[J].Journal of Computer Applications,2013,33(7):1942-1945.

[4] 王杰,畢浩洋.一種基于粒子群優(yōu)化的極限學(xué)習(xí)機(jī)[J].鄭州大學(xué)學(xué)報(bào),2013,45(1):100-104. WANG J, BI H Y. A extreme learning machine algorithm based on particle swam optimization[J].Journal of Zhengzhou University,2013,45(1):100-104.

[5] LU H J, DU B J, LIU J Y, et al. A kernel extreme learning machine algorithm based on improved particle swam optimization[EB/OL].(2016-04-02)[2016-10-18].http://link.springer.com/article/10.1007%2Fs12293-016-0182-5.

[6] 朱志潔,張宏偉.基于GA-ELM的沖擊地壓危險(xiǎn)性預(yù)測研究[J].中國安全生產(chǎn)科學(xué)技術(shù),2014,10(8):46-51. ZHU Z J, ZHANG H W. Study on hazard prediction of rock burst based on GA-ELM[J].Journal of Safety and Technology,2014,10(8):46-51.

[7] 趙志勇,李元香,喻飛,等.基于極限學(xué)習(xí)的深度學(xué)習(xí)算法[J].計(jì)算機(jī)工程與設(shè)計(jì),2015,36(4):1022-1026. ZHAO Z Y, LI Y X, YU F, et al. Improved deep learning algorithm based on extreme learning machine[J].Computer Engineering and Design,2015,36(4):1022-1026.

[8] 梁亞瀾,聶長海.覆蓋表生成的遺傳算法配置參數(shù)優(yōu)化[J].計(jì)算機(jī)學(xué)報(bào),2012,35(7):1522-1538. LIANG Y L, NIE C H. The optimization of configurable algorithm for covering arrays generation[J].Chinese Journal of Computers,2012,35(7):1522-1538.

[9] 雷英杰,張善文,李續(xù)武,等.MATLAB遺傳算法工具箱及應(yīng)用[M].西安:西安電子科技大學(xué)出版社,2014:2.

[10] 苑士義,撒力.基本遺傳算法設(shè)計(jì)及改進(jìn)[J].微計(jì)算機(jī)信息,2011(12):133-135. YUAN S Y, SA L. The basic design and improvement of genetic algorithm[J].Microcomputer Information,2011(12):133-135.

[11] DREZNER Z, MISEVICIUS A. Enhancing the performance of hybrid genetic algorithms by differential improvement[J].Computers & Operations Research,2013,40(4):1038-1046.

[12] 徐繼偉,張文博,王燾,等.一種基于遺傳算法的虛擬機(jī)鏡像自適應(yīng)備份策略[J].計(jì)算機(jī)學(xué)報(bào),2016,39(2):351-363. XU J W, ZHANG W B, WANG T, et al. A genetic algorithm based adaptive strategy for image backup of virtual machines[J].Chinese Journal of Computers,2016,39(2):351-363.

[13] YU W C, ZHUANG F Z, HE Q, et al. Learning deep representations via extreme learning machines[J].Neurocomputing,2015,149:308-305.

[14] LORENZO B, ALESSANDRO S. Implementing ReliefF filters to extract meaningful features from genetic lifetime datasets[J].Journal of Biomedical Informatics,2011,44(2):361-369.

[15] 胡強(qiáng),郝曉燕,雷蕾.基于遺傳算法和BP神經(jīng)網(wǎng)絡(luò)的孤立性肺結(jié)節(jié)分類算法[J].計(jì)算機(jī)科學(xué),2016,43(6A):37-39,54. HU Q, HAO X Y, LEI L. Solitary pulmonary nodules classification based on genetic algorithm and back propagation neural networks[J].Computer Science,2016,43(6A):37-39,54.

[16] 黃剛,李正杰.基于Hadoop平臺的SVM_WNB分類算法的研究[J].計(jì)算機(jī)應(yīng)用研究,2016,33(11):1-6. HUANG G, LI Z J. Research of SVM_WNB classification algorithm based on Hadoop platform[J].Application Research of Computers,2016,33(11):1-6.

AGA-ELM algorithm for genetic data classification

MENG Yaqiong1, LU Huijuan1, YAN Ke1, GUAN Wei2
(1.College of Information Engineering, China Jiliang University, Hangzhou 310018, China;2.College of Modern Science and Technology, China Jiliang University, Hangzhou 310018, China)

Extreme learning machine algorithm(ELM) has high learning efficiency, high generalization capability and high classification accuracy for gene expression data classification. In order to avoid the side-effect of the random input layer weights and the hidden layer bias, an adaptive genetic algorithm(AGA) was integrated into the ELM algorithm to optimize the input layer weight matrix and the hidden layer bias. The new algorithm is called AGA-ELM. The experiment shows that the gene expression data classification results of AGA-ELM are higher than the algorithms such as ELM, GA-ELM and SVM.

extreme learning machine; adaptive genetic algorithm; gene expression data classification

2096-2835(2017)01-0097-06

10.3969/j.issn.2096-2835.2017.01.017

2016-10-28 《中國計(jì)量大學(xué)學(xué)報(bào)》網(wǎng)址：zgjl.cbpt.cnki.net

國家自然科學(xué)基金資助項(xiàng)目(No.61272315,61602431),浙江省自然科學(xué)基金資助項(xiàng)目(No.Y1110342,LY14F020041).

孟亞瓊(1992- ),女,安徽省蕪湖人,碩士研究生,主要研究方向?yàn)闄C(jī)器學(xué)習(xí).E-mail:825726214@qq.com 通信聯(lián)系人：陸慧娟,女,教授.E-mail:hjlu@cjlu.edu.cn

TP391

A