随着互联网技术的迅猛发展，大量网络应用和服务不断地产生了海量的数据，使得传统分类算法遇到了极大的挑战.其中基于核函数的极限学习机(kernelized extreme learning machine，KELM)^[1]主要的计算量是矩阵求逆和矩阵相乘等运算，随着训练样本规模的增加，庞大的核函数矩阵会严重影响矩阵运算效率.作为海量数据处理的代表技术，MapReduce^[2]计算模型不天然支持全局信息交换和迭代，无法直接部署核函数极限学习机.因此，本文针对海量数据规模下核函数极限学习机的训练效率问题，提出了基于MapReduce的分布式核函数极限学习机(MapReduce based kernelized ELM，MR-KELM).

极限学习机(extreme learning machine，ELM)^[3,4]是一种广义单隐层前馈神经网络，在随机生成输入权值和偏置后，通过矩阵计算得到输出权值，从而确定分类器学习模型.相比传统的前馈后传神经网络，极限学习机的训练速度极快，泛化性能更好，实现更容易.Huang等^[5]指出极限学习机和支持向量机(support vector machine，SVM)^[6]的优化角度是一致的，并提出了核函数极限学习机KELM，将最小二乘支持向量机LS-SVM^[7]中的核函数引入极限学习机中，使得该优化问题无需关注输入权值、输出权值、隐藏层节点数、激活函数及偏置，并且相比最小二乘支持向量机具有更快的训练速度和泛化性能.

极限学习机的输出权重矩阵β通过矩阵计算公式β=H^†T计算，其中H^†是特征映射矩阵H的广义逆矩阵.H是极限学习机的随机特征映射矩阵，它将输入样本映射到L维隐藏层空间上，L是隐藏层节点数，h(x)=[h₁(x),...,h_L(x)]是输入x经过隐藏层映射后的输出.由此，极限学习机的输出函数如下：

传统极限学习机的隐藏层输出函数G(w,x,b)已知时，h(x)的计算公式如下：

核函数极限学习机引入核函数代替特征矩阵运算H^TH，其输出函数如下：

核函数极限学习机的训练阶段包括3个计算：1)核函数矩阵Ω的计算；2)Ω逆矩阵的计算；3)矩阵和向量乘法.计算仅与训练数据有关，并且随着样本个数N的增大，Ω矩阵的运算代价急剧增加，单台机器有限的内存资源使得训练效率大大降低.

MapReduce^[2]是一个批处理分布式计算框架，支持海量规模数据的高效分布式处理.MapReduce主要包含Map，Shuffle和Reduce三个阶段.其中：1)Map对于输入数据进行并行处理，产生中间结果形式的＜key,value＞键值对；2)Shuffle将Map产生的中间结果根据key进行排序并分组传输至相应的Reduce；3)Reduce整合每个key的value列表进行进一步聚合处理并生成最终结果.

根据核函数极限学习机的计算理论，其基于MapReduce的并行化主要需要考虑以下两方面：

1) 数据分片.在云计算技术体系下，数据根据一定的规则进行分片并存储在分布式文件系统中.核函数极限学习机的主要计算代价是核函数矩阵运算，任意两个训练数据集样本之间都会产生计算过程，因此可以将数据集按列分片，以列编号和列数据作为Map的输入键值对.

2) 计算模型.极限学习机中的伪逆矩阵运算涉及矩阵及其转置相乘，可看作矩阵元素之间内部运算，因此天然支持在MapReduce框架上进行扩展.核函数极限学习机中的核矩阵运算没有这种特性，其求逆过程无法直接利用传统极限学习机的计算方法.此外，目前还没有能在不修改MapReduce框架的前提下进行分布式矩阵求逆的方法，矩阵之间的乘法也涉及大量的中间结果交换和循环迭代，这与MapReduce模型的理念相冲突.因此如何将核函数极限学习机的计算过程在MapReduce上最大程度地并行化是研究重点.

根据奇异值分解定理，式(3)中需要求解逆矩阵的部分首先被分解为3个矩阵，即

由此可得核函数极限学习机的输出权重

式(6)可分为VΣ和U^TT两个部分，由于对角矩阵Σ按照对角线元素存储为N×1的向量，因此这两个乘积的计算形式都可视为一个N×N的矩阵乘以一个N×1的向量，从而可以被整合在同一个MapReduce计算逻辑中.

在RBF核函数的分布式计算方面，如图 1所示，按列存储的训练样本以＜colID,column＞键值对作为Map的输入，其中的列数据column首先被转换成向量X.向量X中的任意两个元素相减并平方，即两个样本向量之间某列的二范数平方和，并以＜＜i,j＞,X(i,j)＞键值对的形式发送给Reduce.Reduce将相同＜i,j＞对应的部分和进行进一步计算，得到最终矩阵的结果.算法1给出了核函数矩阵的分布式计算的详细过程.

图 1(Figure 1)

Fig. 1

图 1 分布式核函数计算 Fig. 1 Distributed kernel calculation

算法1 分布式核函数
输入：训练数据集
输出：核函数矩阵
1. Function Map(colID,column)
2.      Vector X=parse(column);
3.      For i=1 to X.size() Do
4.        For j=1 to i Do
5.          X(i,j)=(X[i]-X[j])×(X[i]-X[j]);
6.        emit(<i,j>,X(i,j));
7.       EndFor
8.     EndFor
9. EndFunction
10.Function Reduce(<i,j>,list[X(i,j)],σ)
11.      value=list[X(i,j)].sum();
12.      value=exp(-value/(2σ²));
13.      emit(<i,j>,value);
14.      emit(<j,i>,value);
15.EndFunction

在计算出核函数矩阵后，首先要将核函数矩阵进行奇异值分解.这一步通过Mahout项目中的相关API可直接实现.在获取核函数矩阵的3个分解矩阵后，对角矩阵Σ和类标签向量T均以向量的形式存储在DistributedCache中作为全局输入.随后开启新一轮MapReduce任务，对上述中间结果矩阵进行相乘运算，如图 2所示.

图 2(Figure 2)

Fig. 2

图 2 分布式矩阵相乘 Fig. 2 Distributed matrix multiplication

由于VΣ和U^TT的计算细节不完全一致，因此需要在Map中对V，U矩阵的计算过程通过标记matID进行区别.算法中Z矩阵泛指U或V矩阵.

对于VΣ的情况，由于向量Σ本质上是N×N的对角矩阵，其计算的结果是一个N×N的矩阵.因此Z[i]S[i]是矩阵相乘的最终元素；对于UT的情况，每个Z[i]T[i]是结果矩阵中元素的部分和，所有同一个元素的部分和都被相同的＜matID,rowID,colID＞标记.由于U^TT的结果是一个N×1的向量，因此无需对结果所属的列进行标记，colID被设为null.Reduce将所有属于结果向量中的同一个元素的中间结果相加，得到矩阵相乘最终结果向量.具体过程如算法2所示.

算法2 MR-KELM
输入：核函数矩阵
输出：输出权重
1. Function Map(＜matID,rowID＞,row)
2.     Vector S=DistributedCache.get(SIGMA);
3.     Vector T=DistributedCache.get(T);
4.     Vector Z=parse(row);
5.      For i=1 to Z.size() Do
6.       If matID==“U” Then
7.          colID=null;
8.       Else If matID==“V” Then
9.          colID=i;
10.      EndIf
11.      value=Z[i]T[i];
12.      emit(＜matID,rowID,colID＞,value);
13.      EndFor
14.EndFunction
15.Function Reduce(＜matID,rowID,colID＞,list[value])
16.     sum=list[value].sum();
17.     emit(＜matID,rowID,colID＞,sum);
18.EndFunction

由此，MR-KELM已计算出极限学习机的输出权重矩阵，从而确定了整个分类器模型.

本文的实验环境包括1台Master节点和8台Slave节点组成的Hadoop 0.20.2集群，每台机器配有2.66 GHz的英特尔酷睿四核处理器、4 GB内存和CentOS 5.6操作系统.MR-KELM中的SVD矩阵分解通过Apache Mahout实现.

图 3展示了在0.92，1.5，2.0和2.5 GB四种不同数据集规模下，MR-KELM算法各个阶段所消耗的时间.随着样本数N的增加，核函数矩阵规模呈平方倍增长，因此核函数矩阵的计算时间理论上同样应为平方倍增长；此外，矩阵计算涉及嵌套循环，因此矩阵计算的时间理论上也呈平方倍增长.实验结果表明，MR-KELM有效地控制了数据集增长时运算代价的平方倍增长，训练阶段的时间增长幅度较为理想.

图 3(Figure 3)

Fig. 3

图 3 数据集大小与MR-KELM性能 Fig. 3 Time of MR-KELM on varied datasets

图 4是MR-KELM算法在不同集群规模下的运行时间.从图中可以看出，由于核函数的并行计算和矩阵相乘需要分别启动各自的MapReduce任务按照先后顺序执行，当Slave节点数为1时，需要消耗大量时间进行训练；然而随着集群的计算节点增加，MR-KELM的训练时间急剧减少，这反映出MR-KELM良好的加速比和扩展性能.

图 4(Figure 4)

Fig. 4

图 4 集群大小与MR-KELM运行时间 Fig. 4 Time of MR-KELM on varied slaves number (a)—0.92 GB数据集；(b)—1.5 GB数据集; (c)—2 GB数据集；(d)—2.5 GB数据集.

本文针对大规模训练数据规模下核函数极限学习机性能下降的问题，提出了基于MapRedcue的分布式核函数极限学习机MR-KELM，实现了分布式核函数矩阵的计算和矩阵向量相乘.实验结果表明，MR-KELM在不影响核函数极限学习机理论的前提下，具有良好的加速比和扩展性.