PSO和Cholesky分解的KELM的基因表達(dá)數(shù)據(jù)分類

杜幫俊，陸慧娟，嚴(yán)　珂，鄭文斌

(中國(guó)計(jì)量大學(xué) 信息工程學(xué)院,浙江 杭州 310018)

?

PSO和Cholesky分解的KELM的基因表達(dá)數(shù)據(jù)分類

杜幫俊，陸慧娟，嚴(yán)珂，鄭文斌

(中國(guó)計(jì)量大學(xué) 信息工程學(xué)院,浙江 杭州 310018)

【摘要】核極限學(xué)習(xí)機(jī)(KELM)可使低維空間中線性不可分的數(shù)據(jù)變得線性可分，增加了ELM算法的魯棒性，但KELM算法的輸入權(quán)值參數(shù)采用隨機(jī)初始化，容易導(dǎo)致算法不穩(wěn)定.為此,本研究提出用粒子群優(yōu)化算法對(duì)KELM中的權(quán)值初始參數(shù)進(jìn)行優(yōu)化、設(shè)定，以得到優(yōu)化的分類器PSO-KELM.由于該算法輸出權(quán)值求解采用傳統(tǒng)的矩陣求逆運(yùn)算，導(dǎo)致計(jì)算復(fù)雜，因此再對(duì)KELM的輸出權(quán)值采用Cholesky分解進(jìn)行優(yōu)化.經(jīng)一些標(biāo)準(zhǔn)基因數(shù)據(jù)集的實(shí)驗(yàn)表明，提出的PSO-KELM算法與已有的ELM、KELM、PSO-ELM相比分類精度更高，適用于基因表達(dá)數(shù)據(jù)分類.

【關(guān)鍵詞】核極限學(xué)習(xí)機(jī)；粒子群優(yōu)化算法；Cholesky分解；基因表達(dá)數(shù)據(jù)分類

傳統(tǒng)的基于梯度下降的神經(jīng)網(wǎng)絡(luò)算法(如BP神經(jīng)網(wǎng)絡(luò))已經(jīng)被廣泛應(yīng)用于多層前饋神經(jīng)網(wǎng)絡(luò)的訓(xùn)練中，但是該網(wǎng)絡(luò)存在學(xué)習(xí)速度慢、容易陷入局部極小，存在過(guò)訓(xùn)練現(xiàn)象[1].針對(duì)這些問(wèn)題，Huang等[2]在2004年提出了一種新型前饋神經(jīng)網(wǎng)絡(luò)，即極限學(xué)習(xí)機(jī)(extreme learning machine, ELM)，它具有結(jié)構(gòu)簡(jiǎn)單、訓(xùn)練速度快、參數(shù)調(diào)整少等特點(diǎn).

2012年，Huang等人[3]在ELM基礎(chǔ)上加入核函數(shù)，提出了一種核極限學(xué)習(xí)機(jī)(kernel extreme learning machine，KELM)，通過(guò)一個(gè)核函數(shù)將數(shù)據(jù)從低維空間映射到高維空間中，使得在低維空間中線性不可分的數(shù)據(jù)變得線性可分，在提高學(xué)習(xí)精度的同時(shí)增加算法的魯棒性.與ELM相比，KELM具有更好的魯棒性，在樣本線性不可分時(shí)性能更佳，并且解決回歸預(yù)測(cè)問(wèn)題的能力更強(qiáng).文獻(xiàn)[4-6]分別采用KLEM研究液壓泵特性參數(shù)的在線預(yù)測(cè)、行為識(shí)別、航空航天的損傷定位檢測(cè).

HAN等[7]提出了用粒子群算法(particle swam optimization，PSO)對(duì)ELM進(jìn)行優(yōu)化，通過(guò)優(yōu)化ELM的輸入層權(quán)值及隱層偏差，得到一個(gè)最優(yōu)的網(wǎng)絡(luò).

本文針對(duì)ELM、KELM算法的不穩(wěn)定性，采用粒子群優(yōu)化算法分別對(duì)ELM、KELM的輸入權(quán)值進(jìn)行優(yōu)化，但輸入層權(quán)值優(yōu)化更新后的KELM在輸出權(quán)值求解的過(guò)程中，由于引入核函數(shù)和PSO算法計(jì)算量復(fù)雜，當(dāng)樣本數(shù)量較大時(shí)，而且在求解輸出權(quán)值時(shí)采用矩陣求逆等復(fù)雜運(yùn)算，訓(xùn)練時(shí)間會(huì)增加，故再采用矩陣Cholesky分解對(duì)輸出矩陣求解進(jìn)行優(yōu)化，進(jìn)而減少訓(xùn)練時(shí)間.

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

ELM[8-9]輸入權(quán)值隨機(jī)設(shè)定，參數(shù)無(wú)需像傳統(tǒng)神經(jīng)網(wǎng)絡(luò)反復(fù)調(diào)整，其將參數(shù)訓(xùn)練問(wèn)題直接轉(zhuǎn)化為求解線性代數(shù)問(wèn)題，然后求解網(wǎng)絡(luò)輸出權(quán)值，網(wǎng)絡(luò)只需訓(xùn)練一次即可，速度得到明顯的提高.

ELM的訓(xùn)練可等價(jià)于利用如下對(duì)偶優(yōu)化的問(wèn)題:

β-ti+ξi).

(1)

式(1)中，αi代表拉格朗日算子，i代表樣本.可得KKT的優(yōu)化條件:

(2)

式(2)中，

針對(duì)訓(xùn)練樣本，上述公式可等價(jià)地寫(xiě)為

(3)

其中，I為單位矩陣，C為懲罰參數(shù)，計(jì)算得ELM的輸出權(quán)值為

(4)

應(yīng)用Mercer’s條件定義KELM的核矩陣為

其中，i,j∈(1,2,…,N)，K(xi,xj)為核函數(shù).

本文KELM預(yù)測(cè)模型的選擇是RBF核函數(shù)，其表達(dá)式為

K(x,y)=exp(-γ‖x-y‖2),γ>0.

(5)

其中，γ為核參數(shù).

故可得KLEM模型的實(shí)際輸出為：

(6)

(7)

其中，式(7)中aN為KELM網(wǎng)絡(luò)的輸出權(quán)值.

2粒子群優(yōu)化算法

PSO算法是由James Kennedy和Russel Eberhart在1995年提出的一種群體智能優(yōu)化算法，其思想源于鳥(niǎo)或魚(yú)群群體合作捕食行為的研究[10]，稱這些鳥(niǎo)或魚(yú)為“粒子”.粒子群被隨機(jī)初始化，根據(jù)粒子的速度和位置的更新公式，不斷進(jìn)行迭代尋找個(gè)體最優(yōu)解和歷史最優(yōu)解，進(jìn)而對(duì)粒子狀態(tài)進(jìn)行更新，直到達(dá)到合適的全局最優(yōu)解.PSO算法簡(jiǎn)單，易于實(shí)現(xiàn)，收斂速度快，不論是在連續(xù)優(yōu)化問(wèn)題還是離散優(yōu)化問(wèn)題效果都良好.在神經(jīng)網(wǎng)絡(luò)訓(xùn)練、函數(shù)優(yōu)化和工業(yè)系統(tǒng)優(yōu)化等領(lǐng)域都表現(xiàn)出良好的應(yīng)用前景.但是,在處理多峰函數(shù)優(yōu)化過(guò)程中容易發(fā)生早熟收斂，收斂速度慢，陷入局部最優(yōu)等問(wèn)題.

PSO算法具體如下[11]：群體每個(gè)粒子(m個(gè)粒子組成)以一定速度飛行在d維搜索空間中，在飛行搜索時(shí)，同時(shí)尋找粒子搜索到的歷史最好點(diǎn)和其他粒子的歷史最好點(diǎn)，然后再進(jìn)行位置的變化.第i個(gè)粒子的位置表示為xi=(xi1,xi2,…xid),速度表示為vi=(vi1,vi2,…vid).第i個(gè)粒子搜索到的歷史最優(yōu)位置為pbestid，種群搜索到的全局最優(yōu)位置為gbestid，第i個(gè)粒子的位置和速度根據(jù)如下：

(8)

(9)

3基于PSO的KELM權(quán)值優(yōu)化

3.1算法分析

PSO-KELM算法[12]的目的是得到分類精度更高、更穩(wěn)定、泛化能力更好的模型.PSO-KELM結(jié)合了PSO算法的智能參數(shù)優(yōu)化的穩(wěn)定和KELM的分類精度高、泛化性能好等特點(diǎn)，各個(gè)算法的優(yōu)缺點(diǎn)如表1.

表1　各種算法的優(yōu)缺點(diǎn)介紹

3.2算法描述

根據(jù)以上分析，PSO-KELM具體算法流程[13]可描述如下：

1)給定訓(xùn)練與測(cè)試數(shù)據(jù)集，在訓(xùn)練前，對(duì)數(shù)據(jù)集進(jìn)行歸一化處理；

2)建立PSO-KELM神經(jīng)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)(如圖1)，選擇激活函數(shù)、設(shè)置神經(jīng)元數(shù)目；

3)根據(jù)PSO算法，設(shè)定粒子數(shù)z，產(chǎn)生種群，每個(gè)粒子的個(gè)體范圍選取在[-1,1]的隨機(jī)數(shù)；

4)初始化PSO的學(xué)習(xí)因子、初始速度、慣性權(quán)重系數(shù)以及最大迭代次數(shù)等；

5)計(jì)算每個(gè)粒子適應(yīng)度值.先計(jì)算網(wǎng)絡(luò)實(shí)際輸出值，再求期望輸出值與實(shí)際輸出值的MSE(均方誤差)，從而可得到粒子的適應(yīng)度值和粒子個(gè)體極值和種群的群體極值；

6)更新粒子的位置和速度值；

7)判定粒子是否到最小誤差或最大迭代次數(shù)，若達(dá)到，停止進(jìn)行迭代，否則，轉(zhuǎn)到5),繼續(xù)迭代.

圖1　PSO-KELM神經(jīng)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖　　Figure 1　Neural network topology graph of PSO-KELM

4Cholesky分解的KELM優(yōu)化

經(jīng)過(guò)輸入權(quán)值優(yōu)化后的KELM的訓(xùn)練過(guò)程就是求解輸出權(quán)值αN，傳統(tǒng)求解輸出權(quán)值采用矩陣復(fù)雜的求逆等運(yùn)算，會(huì)增加運(yùn)行時(shí)間.本文采用一種基于矩陣Cholesky分解的方法求解.

由式(7)可得

(10)

AaN=b.

(11)

對(duì)上式進(jìn)行線性方程組求解之前先要證明A為對(duì)稱正定矩陣.

證明：

(HNx)THNx>0，故xTAx>0，故A為正定矩陣，則A可以分解為一個(gè)上三角和下三角矩陣的乘積.即

A=SST.

(12)

其中，S是一個(gè)具有正對(duì)角線元素的下三角矩陣，即

(13)

式(12)帶人式(11)并乘以S-1得

STaN=S-1b.

(14)

令F=S-1b，則F的元素fi為

(15)

其中bi為b相應(yīng)位置上元素.最終可得

(16)

綜上可得，使用Cholesky分解方法不需要通過(guò)矩陣求逆復(fù)雜運(yùn)算直接利用矩陣簡(jiǎn)單運(yùn)算就可求解aN,運(yùn)算速度更快，更簡(jiǎn)便.

使用Cholesky分解方法的PSO-KELM神經(jīng)網(wǎng)絡(luò)拓?fù)鋱D如圖2.

圖2　Cholesky分解的PSO-KELM神經(jīng)網(wǎng)絡(luò)拓?fù)鋱DFigure 2　Cholesky decomposition of the PSO-KELM neural network topology graph

5實(shí)驗(yàn)與結(jié)果分析

為了驗(yàn)證PSO-KELM算法性能和采用Cholesky分解的有效性，本文對(duì)該算法進(jìn)行實(shí)驗(yàn)仿真，從UCI標(biāo)準(zhǔn)分類中數(shù)據(jù)集選擇Breast、Brain、Colon三個(gè)基因數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)訓(xùn)練與測(cè)試，分別為腫瘤數(shù)據(jù)中的乳腺癌數(shù)據(jù)集、腦癌數(shù)據(jù)集、結(jié)腸癌數(shù)據(jù)集，其中選用的每個(gè)數(shù)據(jù)集的情況如表2.

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

本實(shí)驗(yàn)是在Core i7-4790 CPU 3.6GHz，16G內(nèi)存的硬件環(huán)境下，在操作系統(tǒng)為Windows7環(huán)境下，通過(guò)Matlab編程實(shí)現(xiàn).

為了驗(yàn)證PSO-KELM算法高效性，分別用ELM、KELM、PSO-ELM在3個(gè)數(shù)據(jù)集上分別采用10次5折交叉驗(yàn)證，即將每個(gè)基因數(shù)據(jù)集分成5份，然后取其中4份作為訓(xùn)練數(shù)據(jù)集，取1份作為測(cè)試數(shù)據(jù)集，進(jìn)行實(shí)驗(yàn)，取10次結(jié)果精度的平均值作為算法的精度，對(duì)應(yīng)的精度圖分別見(jiàn)圖3、圖4、圖5.

圖3　Breast數(shù)據(jù)集上算法的測(cè)試精度對(duì)比圖Figure 3　Comparison of test accuracy of each algorithms on the Breast dataset

各種算法運(yùn)行所消耗時(shí)間、采用Cholesky分解所消耗時(shí)間、均方差比較、PSO-KELM與其他算法精度比較，分別見(jiàn)表3、表4、表5、表6，迭代次數(shù)為50.

圖4　Brain數(shù)據(jù)集上算法的測(cè)試精度對(duì)比圖Figure 4　Comparison of test accuracy of each algorithms on the Brain dataset

圖5　Colon數(shù)據(jù)集上算法的測(cè)試精度對(duì)比圖Figure 5　Comparison of test accuracy of each algorithms on the Colon dataset

Table 3Time comparison of each algorithms

s

表4各種算法采用Cholesky分解后的時(shí)間比較

Table 4Time comparison of each algorithm after usingCholesky decomposition

s

表5PSO-KELM與其他算法的均方差比較

Table 5Comparison of MSE between PSO-KELM and other algorithms

數(shù)據(jù)集ELMKELMPSO-ELMPSO-KELMBreast0.01330.01420.01090.0087Brain0.03470.04200.01690.0134Colon0.02080.01890.00650.0049

表6PSO-KELM與SVM、KNN算法分類精度對(duì)比

Table 6Comparison of classification accuracy between PSO-KELM, SVM and KNN

%

由圖3、圖4、圖5所示，ELM、KELM算法隨著迭代次數(shù)增加一直處于上下波動(dòng)，不易收斂，但是KELM算法的精度比ELM高，說(shuō)明了引入核函數(shù)的必要性，用PSO算法對(duì)ELM、KELM算法進(jìn)行參數(shù)優(yōu)化，精度不再上下波動(dòng)，隨著迭代次數(shù)增加逐漸進(jìn)入收斂，說(shuō)明采用參數(shù)優(yōu)化的必要性.

由表3、表4、表5、表6，在不同算法運(yùn)行時(shí)間比較可知，PSO-KELM算法運(yùn)行的時(shí)間最長(zhǎng)，這是因?yàn)镻SO-KELM算法分別在PSO和ELM算法上引入活躍算子和核函數(shù)，計(jì)算復(fù)雜性增加，輸出權(quán)值計(jì)算采用矩陣求逆的復(fù)雜運(yùn)算.對(duì)輸出權(quán)值提出采用Cholesky分解方法之后運(yùn)行時(shí)間明顯縮短.在各種算法的均方誤差對(duì)比可知，ELM、KELM算法均方誤差最高，最不穩(wěn)定，經(jīng)過(guò)PSO進(jìn)行參數(shù)優(yōu)化后,均方誤差明顯下降，穩(wěn)定性提高，PSO-KELM算法也相對(duì)穩(wěn)定.在PSO-KELM算法與目前流行的支持向量機(jī)(support vector machine，SVM)和K最近鄰(K-nearest neighbor，KNN)[14]算法的精度對(duì)比可知，PSO-KLEM算法在Breast、Brain、Colon數(shù)據(jù)集的精度都比較高.

綜上所述，PSO-KELM算法分別針對(duì)ELM的不穩(wěn)定、精度低和加入PSO優(yōu)化后運(yùn)行速度慢，并在此基礎(chǔ)上分別加以改進(jìn)，無(wú)論在分類精度還是在穩(wěn)定性、收斂性都優(yōu)于其他算法，說(shuō)明PSO-KELM是一種十分可靠有效的分類算法.

6結(jié)語(yǔ)

本文提出一種改進(jìn)的ELM算法PSO-KELM，針對(duì)KELM內(nèi)權(quán)隨機(jī)賦值問(wèn)題，用PSO算法對(duì)內(nèi)權(quán)參數(shù)進(jìn)行優(yōu)化和用Cholesky分解對(duì)輸出權(quán)值進(jìn)行優(yōu)化.經(jīng)與已有類似算法在不同數(shù)據(jù)集上進(jìn)行分類對(duì)比實(shí)驗(yàn)，表明提出的方法具有更好的分類性能，在基因數(shù)據(jù)分類等領(lǐng)域有較好的應(yīng)用前景，值得進(jìn)一步深入研究.同時(shí)，由于PSO-KELM算法容易早熟收斂，接下來(lái)的主要工作是希望能夠繼續(xù)優(yōu)化算法.

【參考文獻(xiàn)】

[1]HE Zhibin, WEN Xiaohu, LIU Hu, et al. A comparative study of artificial neural network, adaptive neuro fuzzy inference system and support vector machine for forecasting river flow in the semiarid mountain region[J]. Journal of Hydrology,2014,509:379-386.

[2]HUANG Guangbing, ZHU Qinyu, SIEW C K. Extreme learning machine: theory and applications[J]. Neurocomputing,2006,70(1-3):489-501.

[3]HUANG Guangbing, ZHOU Hongming, DING Xiajian, et al. Extreme learning machine for regression and multiclass classification.[J]. IEEE Transactions on Systems Man & Cybernetics Part B Cybernetics,2012,42(2):513-29.

[4]MA Chao, ZHANG Yingtang, LI Zhining, et al. Hydraulic pump characteristic parameters online prediction based on kernel extreme learning machine[J]. Computer Simulation,2014,31(5):351-354,397.

[5]DENG Wanyu, ZHENG Qinghua, WANG Zhongmin. Cross-person activity recognition using reduced kernel extreme learning machine[J]. Neural Networks,2014,53(5):1-7.

[6]FU Heming, VONG Chiman, WONG P K, et al. Fast detection of impact location using kernel extreme learning machine[J]. Neural Computing & Applications,2016,27:121-130.

[7]HAN Fei, YAO Haifei, LING Qinghua. An improved evolutionary extreme learning machine based on particle swarm optimization[J]. Neurocomputing,2013,116:87-93.

[8]陸慧娟.基于基因表達(dá)數(shù)據(jù)的腫瘤分類算法研究[D].徐州：中國(guó)礦業(yè)大學(xué),2012.

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

[9]LU Huijuan, AN Chunlin, ZHENG Enhui, et al. Dissimilarity based ensemble of extreme learning machine for tumor data classification[J]. Neurocomputing,2014,128(27):22-30.

[10]EBERHART R, KENNEDY J. A new optimizer using particle swarm theory[C]//International Symposium on MICRO Machine and Human Science. Piscataway:IEEE Press,1995:39-43.

[11]KENNEDY J, EBERHART R. Particle swarm optimization[C]// Proceeding of IEEE International Conference on Neural Networks. Piscataway: IEEE Press,1995:1942-1948.

[12]LU Huijuan, DU Bangjun, LIU Jinyong, et al. A kernel extreme learning machine algorithm based on improved particle swam optimization[J]. Memetic Computing, 2016,8:1-8.

[13]周東凱,李剛,王學(xué)琨.基于PSO-ELM的雙目視覺(jué)攝像機(jī)標(biāo)定[J].廣西大學(xué)學(xué)報(bào)(自然科學(xué)版),2014,39(6):1285-1290.

ZHOU Dongkai, LI Gang, WANG Xuekun. Camera calibration for binocular vision based on PSO-ELM[J]. Journal of Guangxi University(Natural Science Edition),2014,39(6):1285-1290.

[14]盧新國(guó),林亞平,駱嘉偉,等.癌癥識(shí)別中一種基于組合GCM和CCM的分類算法[J].軟件學(xué)報(bào),2010,21(11):2838-2851.

LU Xinguo, LIN Yaping, LUO Jiawei, et al. Classification algorithm combined GCM with CCM in cancer recognition[J]. Institute of Software,2010,21(11):2838-2851.

【文章編號(hào)】1004-1540(2016)02-0204-06

DOI:10.3969/j.issn.1004-1540.2016.02.014

【收稿日期】2015-12-30《中國(guó)計(jì)量學(xué)院學(xué)報(bào)》網(wǎng)址：zgjl.cbpt.cnki.net

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

【作者簡(jiǎn)介】杜幫俊(1991-)，男，安徽省六安人，碩士研究生，主要研究方向?yàn)闄C(jī)器學(xué)習(xí).E-mail:1172169188@qq.com 通信聯(lián)系人：陸慧娟，女，教授.E-mail: hjlu@cjlu.edu.cn

【中圖分類號(hào)】TP391

【文獻(xiàn)標(biāo)志碼】A

An improved KELM on PSO algorithm and Cholesky decomposition for gene expression data classification

DU Bangjun, LU Huijuan, YAN Ke, ZHENG Wenbin

(College of Information Engineering， China Jiliang University, Hangzhou 310018， China)

Abstract:Kernel extreme learning machines (KELM) increase the robustness of extreme learning machines (ELM) by turning linearly non-separable data in low dimensional space into a linearly separable one. However, the internal weighted parameters of KELM are initialized randomly, which causes the algorithm to be unstable. In this paper, we used the particle swam optimization (PSO) algorithm to obtain an optimal set of initial parameters for KELM and thus created an optimal KELM classifier referred to as PSO-KELM. Since a calculation of the output weights adopting the traditional matrix inversion could result in a more complicated algorithm when calculating the output weights, we used the Cholesky decomposition to optimize the output weights of KELM. Experiments on some standard genetic datasets demonstrate that the PSO-KELM has the highest classification accuracy compared to the existing ELM, KELM, PSO-ELM and other similar algorithms.

Key words:kernel extreme learning machine; particle swam optimization algorithm; Cholesky decomposition; gene expression data