基于MapReduce的GA—BP神经网络算法并行化设计及实现
2017-09-05杨婉婧邢洪嘉曹建芳
杨婉婧+邢洪嘉+曹建芳
摘 要：为提高BP神经网络算法的运行效率，利用遗传算法和并行编程思想，提出了Hadoop平台下基于MapReduce的遗传算法优化BP神经网络的并行化设计及实现方法。利用遗传算法优化BP神经网络的初始权值和阈值，提高算法分类准确率；采用MapReduce并行编程模型实现算法的并行化处理，解决BP神经网络在处理大规模样本数据集时存在的硬件开销和通信开销大的问题。选用Caltech 256图像数据集，与传统的串行遗传算法优化BP神经网络算法实验对比，验证了并行化GA-BP神经网络算法的优越性。
关键词：遗传算法；BP神经网络；MapReduce并行编程模型；并行化设计
DOIDOI：10.11907/rjdk.171303
中图分类号：TP312
文献标识码：A 文章编号：1672-7800（2017）007-0040-04
0 引言
BP（Back Propagation）神经网络是一种多层前馈型神经网络，是一种通过不断修改各层神经元之间的连接权值以及各神经元的阈值，以使网络输出不断逼近期望输出的学习过程[1]。由于它具有很强的泛化能力，并可实现任何复杂程度的非线性映射关系，因此在很多领域得到了广泛应用[2]。然而，BP神经网络算法是基于函数误差梯度下降的思想，不具备全局搜索能力；而且，网络各层之间的连接权值和神经元的阈值在初始训练时是0～1的任意值，这会导致算法收敛速度慢，而且不一定得到最优解。近年来，学者们先后提出一些改进的算法来优化BP神经网络的初始权值和阈值，如遗传算法[3]、粒子群算法、萤火虫算法[4]等。然而，伴随着大数据时代的到来，样本规模愈来愈大，上述传统的串行算法不仅存在硬件支撑瓶颈的问题，而且算法训练时间会变得很长，系统效率明显下降。目前，算法的并行化设计受到广泛关注。郑晓薇等[5]在MPI集群环境下设计了一种多BP神经网络并行集成模型，实现了图像的多语义分类，实验效果良好。刘晶[6]在PVM并行环境下，对大型矩阵运行进行了并行处理，有效降低了矩阵运算的耗时。但是，基于MPI和PVM的并行设计需要开发者对计算机硬件体系结构有较清晰的了解，并且各节点间通信耗时较大，实现也较困难[7]。而近年流行起来的Hadoop平台下的MapReduce框架是一种面向分布式环境的并行计算模式，它向开发人员提供了完整的编程接口，并不需要开发者了解计算机的体系结构，因而逐渐成为当前算法并行化设计的研究热点[8]。针对上述问题，本文提出一种GA-BP神经网络的并行算法，并将其应用于图像分类问题中。该算法在MapReduce并行编程模型下设计并行处理机制，使用遗传算法（Genetic Algorithm，GA）优化BP神经网络的初始权值和阈值，再使用不同的优化后的多个并行BP神经网络训练采用不同的样本集，既保证了BP神经网络能获得最优解，又加快了网络收敛速度，而且在有效降低样本多样性和复杂性对BP神经网络性能影响的同时，大大缩短了训练时间。
1 GA-BP神经网络算法
BP神经网络算法具有很强的自学习和自适应能力，能够很好地解决非线性映射问题，但因其初始权值和阈值的任意性，导致网络收敛速度慢，并且不一定能获得最优解。因此，有必要对BP神经网络的初始权值和阈值进行优化。遗传算法是一种源于生物进化的智能优化搜索算法，因其设置参数少、收敛速度快，且在计算精度要求时，计算时间少、鲁棒性高、易于实现等特点而得到广泛应用。将遗传算法引入BP神经网络中，优化BP神经网络的初始权值和阈值，将很好地解决BP神经网络由于初始权值阈值的任意性而造成的一些缺陷。其算法分为遗传算法优化阶段和BP神经网络训练阶段。
1.1 遗传算法优化阶段
（1）种群初始化。个体采用实数编码，由BP神经网络输入层与隐含层的连接权值、隐含层阈值、隐含层与输出层的连接权值、输出层阈值4部分组成。
（2）适应度函数确定。根据个体得到BP神经网络的初始权值和阈值，用训练样本训练BP神经网络后预测系统输出，将预测输出和期望输出之间的误差绝对值和E作为个体适应度值
（6）更新适应度值并判断是否结束迭代，产生BP神经网络的最优初始权值和阈值。
1.2 BP神经网络训练阶段
（1）网络初始化。根据样本特征确定网络结构、期望输出、学习速率，接收遗传算法优化得到的最优解个体作为网络的初始权值和阈值。
（2）输入训练样本，计算网络各层输出。
（3）计算网络学习误差。
（4）修正各层连接权值和阈值。
（5）判断误差是否满足期望的要求或训练达到设置的迭代次数，如满足条件，则训练结束，否则，继续迭代学习。
2 GA-BP神经网络算法并行化设计与实现
PSO-BP神经网络算法虽然改善了传统BP神经网络算法的性能，但随着数据规模的不断扩大，BP神经网络训练时间会很长，效率问题逐渐暴露。MapReduce并行编程框架为大数据的处理提供了一种分布式并行计算环境，为提高BP神经网络的时间效率和测试准确率，本文对PSO-BP神经网络算法在MapReduce框架下进行了并行化设计。
2.1 MapReduce编程模型
Hadoop下的MapReduce是由Google公司提出的一种处理大规模数据的分布式并行编程模型，它将数据的计算过程划分成Map和Reduce两个阶段，分别对应Mapper（）函数和Reducer（）函数实现，要求数据以键值对
2.2 遗传算法并行化设计及实现
2.2.1 GA-Map（）设计及实现
根据MapReduce编程模型的数据输入格式，本文也将遗传算法输入的数据转化为
输入：个体id，个体属性值
输出：key，最优个体集
GA-Map（个体id，个体属性值）
{
对每个个体，获取value值；
fit-value=fit（value）；//计算更新个体的适应度值//迭代更新个体If（满足条件）key=new-key（key）；输出key，最优个体集； }
2.2.2 GA-Reduce（）设计及实现
Reduce阶段，接收Map任务生成的最优个体集，对信息进行整合，全局更新最优个体集，如果达到终止条件，输出整个种群的最优个体。遗传算法的Reduce过程设计如下：
输入：key，最优个体集输出：key，最优个体PSO-Reduce（key，最优个体集）{对各种群中的每一个最优个体，获取其fit-value值；//全局迭代更新种群if（获得问题最优解||达到最大迭代次数）输出key，最优个体；}
当遗传算法并行迭代完成后，得到的最优个体即为BP神经网络的初始权值和阈值。
2.3 BP神经网络并行化设计及实现
为克服BP神经网络在样本数量增多时硬件开销大、训练时间长等缺陷，本文基于MapReduce模型对BP神经网络进行了并行化设计，通过Map任务和Reduce任务实现多BP神经网络内部的自动并行运行，在大大缩短样本训练时间的同时，进而提高了训练的精度。其模型结构如图2所示。
2.3.1 BP-Map（）设计及实现
Map阶段，Map任务根据输入逐层计算网络实际输出，并将实际输出与期望输出相比较，计算网络学习误差，然后根据学习误差计算网络中各连接权值的更新量。BP神经网络的Map任务设计如下：输入：样本id，样本特征值输出：样本对应权值ω，权值更新量ΔωBP-Map（样本id，样本特征值）{//对每个样本计算网络各层输出；
计算网络学习误差；对每个连接权值ω，计算权值更新量Δω；输出（ω，Δω）； }
2.3.2 BP-Combine（）函数设计及实现
在MapReduce并行编程模型中，Combine（）函数可以对Map阶段产生的中间结果作本地处理，从而大大降低通信开销。由于使用BP神经网络训练的样本数据日趋增多，因此有必要在进入Reduce任务之前使用Combine（）函数对Map任务产生的结果先进行处理。在BP神经网络并行化设计过程中，Combine（）函数设计如下：
输入：键值对<ω，Δω>输出：键值对<ω′，Δω′>BP-Combine（ω，Δω）{初始化变量count=0；//统计训练样本的数目//对每个训练样本解析并处理Δω的各维坐标值；count←count+1；ω′←ω；收集所有ω相同的键值对，进行本地归约，得到Δω′；输出ω′，Δω′；}
2.3.3 BP-Reduce（）设计及实现Reduce阶段，接收Combine（）函数的输出，然后统计所有权值相同样本的总体更新量和平均更新量，并更新网络权值。BP神经网络的Reduce任务设计如下：
输入：Combine函数的输出：<ω′，Δω′>输出：<ω′，∑ni=1Δω′/n>BP-Reduce（ω′，Δω′）{累加所有ω′相同样本的Δω′，得到∑ni=1Δω′；计算每个权值的平均更新量；输出ω′，∑ni=1Δω′/n； }BP神经网络一直重复上述Map和Reduce任务，直至误差满足规定的精度或达到迭代次数。
3 实验及结果分析
为验证本文提出的并行GA-BP神经网络算法的性能，本文在Hadoop平台下对大量图像的分类效果进行了测试。
3.1 实验环境及数据
实验环境是局域网内5台计算机构成的Hadoop集群，1台计算机做Master节点，其余4台做Slave节点；所有节点配置都是4G双核处理器、1T硬盘，操作系统是Ubuntu。
实验数据来自Caltech 256图像库，该图像库可供免费使用，包含30 607幅、256个类別。
3.2 实验结果及分析
为验证所提出算法的性能，本文从分类准确率、加速比与效率等方面作了实验比较。
3.2.1 分类准确率
本文在不同的图像规模下，以训练样本数与测试样本数约4：1的比例，对传统的GA-BP神经网络算法和本文提出的并行GA-BP神经网络算法就分类准确率进行比较。本文采用计算机随机结合人工选择构造了5个数据集Data1、Data2、Data3、Data4和Data5。其中，Data1包含了3个类别的300幅场景图像，Data2包含了5个类别的800幅场景图像，Data3包含了8个类别的2 000幅场景图像，Data4包含了12个类别的5 000幅图像，Data5包含了15个类别的15 000幅场景图像。实验结果如表1所示。
从表1可以明显看到，本文算法分类效果明显优于传统的GA-BP神经网络算法，而且，随着数据规模的增大，虽然两种算法的分类准确率都在降低，但本文提出的并行GA-BP神经网络算法显然没有下降到很低。这充分说明，基于MapReduce并行编程模型的算法在大规模数据集下的优越性非常明显。
3.2.2 加速比与效率
对于MapReduce并行编程模型，衡量算法性能的两个重要指标是加速比与效率。加速比是指同一任务在单个计算节点运行与在多个计算节点运行的时间之比，而效率是加速比与计算节点数量的比值[8]。理想情况下，加速比应随着计算节点数量的增加而线性增长，效率是1保持不变。但由于受到负载平衡、通信开销等因素的影响，加速比不会线性增长，效率也不可能达到1。研究表明，在效率达到0.5时，系统就获得了很好的性能[9]。为更好地验证MapReduce并行编程模型的优势，本文随机从Caltech 256图像库随机选取了1 000幅以上的5个不同规模的图像数据集，图3和图4分别是本文提出的算法在不同规模数据集下加速比与效率的实验对比。
从图3可以看出，加速比在随着计算节点数的增加呈增长趋势，而且数据规模越大，加速比增长的幅度越大，这也进一步说明越大规模的数据集才越能充分发挥多个计算节点的性能。从图4中系统效率对比可以看出，数据集小的效率低于数据集大的效率，而且随着计算节点数的增加，数据集规模较小时，系统效率下降较快，而当数据集规模不断增大时，随着计算节点个数增多，系统效率虽有降低，但下降幅度较小。系统效率的下降主要是因为一方面数据规模增大，系统处理的时间会增多，另一方面，随着计算节点数的增加，节点间的通行开销也会增加，但系统效率一直都在0.5以上，说明算法具有很好的并行性能和可扩展性能。
4 结语
本文对GA-BP神经网络算法的并行化设计与实现进行了深入的探讨和分析，研究了遗传算法如何优化BP神经网络的初始权值和阈值、遗传算法及BP神经网络的并行化设计及实现，并选择Caltech 256图像库中的图像数据，对算法的性能从多方面进行了验证。实验结果表明，本文提出的算法具有很好的并行性，可以充分利用分布式系统资源，改善算法分类效果；另外，基于MapReduce的分布式并行系统相对于单节点架构性能有很大提高，充分体现了并行处理的强大计算能力。随着大数据、云计算等技术的迅速发展，对大规模数据集的处理和分析必将是今后一段时间的研究热点。本文下一步研究的内容主要有：①改变Hadoop分布式平台节点数量，调节相关参数，进一步提高算法效率；②改进遗传算法，能更快、更容易地找到全局最优解；③优化算法Map任务和Reduce任务设计，进而提高算法分类准确率和时间性能。
参考文献：
[1] 胡月.BP算法并行化及在数据挖掘中的应用研究[D].重庆：重庆大学，2003.
[2] JIANFANG CAO，LICHAO CHEN.Fuzzy emotional semantic analysis and automated annotation of scene images[J].Computational Intelligence and Neuroscience，2015：1-10.
[3] 高玉明，张仁津.基于遗传算法和BP神经网络的房价预测分析[J].计算机工程，2014，40（4）：187-191.
[4] 王改革，郭立红，段红，等.基于萤火虫算法优化BP神经网络的目标威胁估计[J].吉林大学学报：工学版，2013，43（4）：1064-1069.
[5] 鄭晓薇，李玉丹，马名威.MPI 集群环境下图像语义分类算法的并行化设计[J].小型微型计算机系统，2014，35（6）：1348-1352.
[6] 刘晶.基于PVM的并行计算[J].广东石油化工学院学报，2012，12（4）：34-35.
[7] 赵玖玲，卫海鹏.基于MPI的并行遗传算法的设计与实现[J].计算机科学，2006，33（9）：186-189.
[8] 朱为盛，王鹏.基于Hadoop 云计算平台的大规模图像检索方案[J].计算机应用，2014，34（3）：695-699.
[9] 金伟健，王春枝.适于进化算法的迭代式MapReduce框架[J].计算机应用，2013，33（12）：3591-3595.
