面向基因数据分类的AGA-ELM算法研究

孟亚琼,陆慧娟,严 珂,关 伟

(1.中国计量大学 信息工程学院,浙江 杭州 310018;2.中国计量大学 现代科技学院,浙江 杭州 310018)

面向基因数据分类的AGA-ELM算法研究

孟亚琼1,陆慧娟1,严 珂1,关 伟2

(1.中国计量大学 信息工程学院,浙江 杭州 310018;2.中国计量大学 现代科技学院,浙江 杭州 310018)

对基因表达数据进行分类时,超限学习机(ELM)算法具有学习效率高、泛化能力强、分类精度高的优点.为了解决超限学习机算法受输入权值矩阵和隐含层偏差随机初始化的影响,本文利用自适应遗传算法(AGA)具有良好的全局搜索效果对超限学习机的输入权值矩阵和隐含层偏差进行优化,提出了基于自适应遗传算法优化超限学习机(AGA-ELM)的分类算法.通过实验表明,该算法与已有的ELM、GA-ELM以及SVM算法相比，分类精度更高,可用于基因数据分类.

超限学习机;自适应遗传算法;基因表达数据分类

基因数据存在着样本小、维数高以及非线性等特点,使得基因表达数据的分析存在着一定的困难.目前比较新的适用于基因表达数据分类的方法主要有:二维主成分分析法、二维线性判别分析法、支持向量机方法、K最近邻法、支持向量机算法以及超限学习机(extreme learning machine, ELM)算法[1-2].本文主要研究的是ELM.

超限学习机,是由黄广斌提出来的求解单隐层神经网络的算法.后来又有许多专家学者对ELM进行了研究.罗庚合[3]提出一种基于可拓聚类的ELM神经网络.该神经网络是以隐含层神经元的径向基中心向量作为输入层权值,采用可拓聚类算法动态调整隐含层节点数目和径向基中心,并根据所确定的输入层权值,利用Moore-Penrose广义逆快速完成输出层权值求解.王杰[4]等人提出粒子群超限学习机算法,利用粒子群优化算法优化选择超限学习机的输入层权值和隐含层偏差,从而计算出输出权值矩阵.LU H J[5]等人提出用带活跃算子的PSO算法对KELM中的内权初始参数进行优化、设定,以得到最优KELM分类器.朱志杰[6]等人提出了将遗传算法与超限学习机相结合的冲击地压预测的新方法,采用遗传算法对超限学习机的输入权值矩阵和隐含层偏差进行优化.解决了ELM受随机初始化权值矩阵带来的不利影响,但是,遗传算法容易早熟收敛,陷入局部最优.

为了解决上述问题,本文提出了基于自适应遗传算法(adaptive genetic algorithm, AGA)的超限学习机分类算法.ELM最大的特点是对于传统的神经网络,尤其是单隐层前馈神经网络(SLFNs),在保证学习精度的前提下比传统的学习算法速度更快.但是ELM的输入权值矩阵和隐含层偏差是随机初始化的,而这些权值并没有包含任何训练样本的先验知识,因此可能会导致ELM的拟合精度降低.而自适应遗传算法作为一种基于自然选择与进化机制的功能强大的搜索算法,AGA的操作不需要规划对象的先验性知识,只需要计算个体的适应度值并筛选,具有良好的全局搜索效果.这里就利用自适应遗传算法优化ELM的输入权值矩阵和隐含层偏差,该算法能根据最后的分类精度相应地调整权值,从而达到提高分类精度的效果.实验表明优化后的算法分类精度明显提升,且稳定性更好.

1 超限学习机

ELM是一种快速学习算法,与传统的单隐层前馈神经网络相比,具有分类准确率高、泛化能力好、调节参数少等优点[7].ELM可以随机初始化输入权重和偏置并得到相应的输出权重.

ELM实现的过程描述如下:对一个单隐层前馈神经网络,假设给出N个任意样本(Xi,ti),其中Xi=[xi1,xi2,…,xin]T∈Rn,ti=[ti1,ti2,…,tin]T∈Rm.对于一个有L个隐层节点的单隐层神经网络可以表示为

(1)

其中:定义g(x)为激活函数,Wi=[wi1,wi2,…,win]T为输入权重,βi为输出权重,bi是第i个隐层单元的偏置.Wi·Xj表示Wi和Xj的内积.

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

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

其中:H是隐层节点的输出,β为输出权重,T为期望输出.

2 利用自适应遗传算法优化超限学习机的分类算法

2.1 遗传算法

遗传算法(genetic algorithm, GA)最初是由美国Michigan大学的J.Holland教授提出来的.遗传算法是模仿自然界生物进化机制发展起来的随机全局搜索和优化方法,它借鉴了达尔文的进化论和孟德尔的遗传学说[8].其本质是一种高效、并行、全局搜索的方法,它能在搜索过程中自动获取和积累有关搜索空间的知识,并自适应地控制搜索过程以求得最优解[9].

遗传算法的基本步骤[10]如下:

1)设置初始种群大小M、终止代数T、交叉概率Pc、变异概率Pm,进化代数t=0,随机生成M(应为偶数)个个体,得到初始化种群;

2)计算各个个体的适应度;

3)以交叉概率Pc进行交叉操作;

4)以变异概率Pm进行变异操作;

6)如果t

2.2 自适应遗传算法

遗传算法在运算过程中往往会出现个别适应度很高的个体,导致这个个体被选择的概率远远大于其他个体,可能一再被选择,从而充斥下一代种群,使进化难以进行,出现早熟现象.

为解决上述问题,提出了自适应遗传算法[11-12].自适应遗传算法是一种交叉率和变异率可根据适应度自调整的改进遗传算法,具有更快的收敛速度和全局搜索能力.本算法用适应度差值来衡量适应度的差异大小,先定义调节因子γ:

(2)

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

(3)

其中,Δf为当前群体中适应度的差值,ΔF为适应度的差值的理论最大值,fmin为当前群体中适应度的最小值,fmax为当前群体中适应度的最大值,Fmin为适应度的理论最小值,Fmax为适应度的理论最大值,易知γ的取值范围为[0,1].

对适应度函数进行变换

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

(4)

其中,f(x)为原适应度函数,f′(x)为变换后的适应度函数,k为正常数,根据具体情况进行设置,越大则变换力度越大,但应尽量保证适应度值非负,这里取k=5.

利用SPSS 16.0软件对49个样点土壤的8项养分指标进行主成分分析，并对各土壤样品的综合得分以欧式距离为衡量土壤间差异大小的指标，采用类平均法进行系统聚类。主成分分析的主要运算步骤包括[7]：

当群体中适应度差值较大时(γ>0.5),个体适应度都增加k(γ-0.5),则适应度小的个体增加的比例大,被选择的概率将增大,有利于维持群体的多样性;反之,亦然.

交叉概率Pc和变异概率Pm分别定义为:

Pc=γ,

(5)

Pm=0.1(1-γ).

(6)

在进化初期,个体差异较大,交叉产生更好个体的可能性也较大,如果增大交叉概率,减小变异概率,将加快进化进程;在进化后期,由于个体差异较小,导致交叉产生更好的个体的可能性减少,如果减小交叉概率可减小计算量,增大变异概率可保持群体的多样性.

2.3 AGA-ELM

为解决ELM随机初始化输入权值矩阵和隐含层偏差而带来的一系列问题[13].本文利用AGA优化ELM的输入权值矩阵和隐含层偏差.

算法的具体步骤如下:

1)产生初始种群,粒子数N,取N=10.种群个体即粒子数是由隐层节点K和粒子数N组成的,粒子长度D=N·K.

2)确立适应度函数,利用ELM算法计算出输出权值矩阵,其中隐含层激活函数为sigmoid函数.再利用训练样本计算初始化种群的每个个体的分类准确率f(nint),由f(x)=1-f(nint)计算出误分类率f(x).根据公式(4)计算出该自适应遗传算法的适应度函数.

3)判断是否满足终止条件,若满足则停止;否则,继续下一步.

4)以交叉概率,即公式(5)进行交叉操作.

5)以变异概率,即公式(6)进行变异操作.

6)采用轮盘赌注法进行选择,产生新群体.

7)解码,得到输入权重Wi,和隐含层偏差bi.

8)利用ELM算法计算出分类精度并输出分类精度.先计算隐含层矩阵H,计算出连接权值,求出分类精度.返回3).

9)结束.

算法流程图如图1.

3 实 验

为了评估AGA-ELM算法的性能,本文对该算法进行了实验分析与仿真,从UCI标准测试数据集中选择Breast、Brain、Colon以及Leukemia四个基因数据集进行实验训练与测试,这4个数据集分别为肿瘤数据中的乳腺癌数据集、脑癌数据集、结肠癌数据集以及白血病数据集。选用的每个数据集经过ReliefF[14]降维后的基本信息的如表1.

表1 数据集信息表

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

本实验是在Core i5-4790 CPU 3.6 GHz,6 G内存,操作系统为Windows8.1的环境下,通过Matlab编程实现仿真的.

为了验证AGA-ELM算法高效性,分别用ELM、GA-ELM、以及SVM算法分别在4个数据集上分别采用10次5折交叉验证,将数据集分成五份,轮流将其中4份作为训练数据集,1份作为测试数据集,进行实验[15].取10次结果精度的平均值作为算法的精度,各数据集在不同迭代次数下的分类精度如表2.为了更直观地表示出随着迭代次数的变化分类精度也相应地变化,各数据集下的分类精度图如图2～5.

图2 Breast数据集下各算法分类精度Figure 2 Classification accuracy of Breast dataset

图3 Brain数据集下各算法分类精度Figure 3 Classification accuracy of Brain dataset

表2 基因数据集下各算法的分类精度

图4 Colon数据集下各算法分类精度Figure 4 Classification accuracy of Colon dataset

图5 Leukemia数据集下各算法分类精度Figure 5 Classification accuracy of Leukemia dataset

由上述实验结果可知:在基因数据集上,ELM算法随着迭代次数增加,分类精度一直处于上下波动的状态,极不稳定.分别用GA、AGA算法对ELM算法进行参数优化后,算法的分类精度不再上下波动.随着迭代次数增加,算法的分类精度稳步上升,这说明了采用参数优化的必要性.但是,由于GA算法容易导致早熟收敛,而AGA算法克服了早熟收敛这一缺点,所以AGA-ELM算法的优化的效果是最好的.

本文将AGA-ELM算法在迭代次数为55次时与目前流行的支持向量机(SVM)[16]的精度对比可知,AGA-ELM算法在Breast、Brain以及Colon数据集的精度都比SVM高.见表3.

表3 AGA-ELM与SVM算法分类精度对比

综上所述,AGA-ELM算法通过利用AGA算法优化ELM的输入权值矩阵和隐含层偏差,取得良好效果,在分类精度以及稳定性上均优于其他算法,说明AGA-ELM是一种十分可靠有效的分类算法.

4 结 论

采用AGA对ELM输入权值矩阵和隐含层偏差进行优化,避免了输入权值矩阵和隐含层偏差随机性对ELM预测精度的影响,提高了预测准确率.与已有类似算法在不同数据集上进行分类对比实验,证明提出的方法具有更好的分类性能;并且在基因数据分类等领域有较好的应用前景,值得进一步深入研究.

[1] 李珉.基于基因表达谱的肿瘤数据分类[D].长沙:湖南大学,2012. LI M. The Research on Gene Expression Profiles Data for Tumor Classification[D].Changsha: Hunan University,2012.

[2] 陆慧娟,安春霖,马小平,等.基于输出不一致测度的极限学习机集成的基因表达数据分类[J].计算机学报,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] 罗庚合.基于可拓聚类的极限学习机神经网络[J].计算机应用,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] 王杰,毕浩洋.一种基于粒子群优化的极限学习机[J].郑州大学学报,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的冲击地压危险性预测研究[J].中国安全生产科学技术,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] 赵志勇,李元香,喻飞,等.基于极限学习的深度学习算法[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] 梁亚澜,聂长海.覆盖表生成的遗传算法配置参数优化[J].计算机学报,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] 雷英杰,张善文,李续武,等.MATLAB遗传算法工具箱及应用[M].西安:西安电子科技大学出版社,2014:2.

[10] 苑士义,撒力.基本遗传算法设计及改进[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].计算机学报,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] 胡强,郝晓燕,雷蕾.基于遗传算法和BP神经网络的孤立性肺结节分类算法[J].计算机科学,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].计算机应用研究,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 《中国计量大学学报》网址：zgjl.cbpt.cnki.net

国家自然科学基金资助项目(No.61272315,61602431),浙江省自然科学基金资助项目(No.Y1110342,LY14F020041).

孟亚琼(1992- ),女,安徽省芜湖人,硕士研究生,主要研究方向为机器学习.E-mail:825726214@qq.com 通信联系人：陆慧娟,女,教授.E-mail:hjlu@cjlu.edu.cn

TP391

A