2. 河北大学计算机科学与技术学院, 保定, 071002
2. College of Computer Science and Technology, Hebei University, Baoding, 071002, China
极限学习机(Extreme learning machine, ELM)[1, 2]是一种随机化快速学习算法,具有很好的泛化能力, 是近几年机器学习的研究热点领域之一,已成功应用于模式识别[3-5]、预测预报[6, 7]和分类与回归等领域[8, 9]。陶卿等[10]对机器学习随机优化方法进行了综述,具有较高的参考价值。
作为一种数据挖掘算法,ELM既可以解决分类问题,也可以解决回归问题。本文考虑分类问题,在分类的框架下,研究人员提出了许多基于ELM的分类算法。极限学习机是一种批处理学习模型,处理的数据是静态数据。针对在线序列数据的分类问题,Liang等[11]提出了在线序列极限学习机(Online sequential-extreme learning machine, OS-ELM)模型。因为OS-ELM能处理源源不断出现的数据,所以从某种意义上来说,OS-ELM是一种解决大数据分类问题的方法。但是OS-ELM和ELM一样,有预测不稳定的问题[12]。
针对类别非平衡数据的分类问题,Zong等[13]于2013年提出了加权ELM学习模型,用于处理类别不平衡学习问题,通过不同的惩罚系数对样例加权,并把惩罚系数嵌入到优化模型中。Li等[14]将加权ELM和AdaBoost结合起来,将惩罚系数作为AdaBoost权值,提出了Boosting加权ELM学习模型,用于处理类别不平衡学习问题。实际上,对样例加权是用代价敏感性的方法处理类别不平衡问题。Lin等[15]提出了基于ELM和合成小类上采样相结合的方法,用于处理两类不平衡学习问题。
针对含有噪声或有缺失值数据的分类问题,Man等[16]通过分析输出权矩阵关于隐含层输出矩阵的敏感性,提出了一种称为有限脉冲响应的极限学习机模型。该模型可以改进极限学习机对含有噪声数据分类的性能,还可以提高模型的鲁棒性。在这一工作的基础上, 基于离散傅里叶变换技术,Man等[17]提出了另外一种对噪声数据更鲁棒的学习模型。Yu等[18]研究了具有缺失数据的ELM回归问题,提出了Tikhonov正则化优化剪枝ELM学习模型。因为分类是回归的特殊情况,所以该模型也适用于具有缺失数据的分类问题。
针对大数据分类问题,基于MapReduce编程框架,He等[19]分别提出了并行增量ESVM算法和并行ELM算法[20],这是用ELM解决大数据分类问题的较早工作。Wang等[21]提出了基于MapReduce的并行序列ELM算法,用于解决序列大数据分类问题。Xin等[22]将矩阵运算分解到不同的云计算节点上以实现并行化,同时提出了ELM*算法,应用于解决大数据ELM广义逆矩阵的计算问题。沿着这一技术路线,文献[23]提出了面向大样本数据的核化ELM学习模型。
对于上面的数据分类问题,研究人员还提出了许多基于集成学习的分类算法。例如,Liu等[24]提出了基于集成的ELM学习模型EELM,目的是为了提高学习模型的泛化能力。文献[24]采用了静态集成方法,在分类测试样例时,各个基本分类器被看作具有同等的重要性。Wang等[25]提出了一种动态集成ELM学习模型,其动态性体现在所用的集成策略上,即AdaBoost集成学习策略。基于样本的信息熵,Zhai等[26]提出了另一种动态集成ELM学习模型,该模型在泛化能力和稳定性上均有好的表现。
集成学习模型可以较好地解决各种ELM模型的预测不稳定、容易产生过拟合以及最优隐含层结点数难于确定等问题。本文提出了一种简单有效的集成数据分类方法,可在一定程度上解决以上问题,该方法分为3步:(1)用ELM算法重复训练若干个单隐含层前馈神经网络;(2)用多数投票法集成训练好的神经网络;(3)用集成模型对数据进行分类。在10个数据集上实验比较结果表明,本文提出的方法优于极限学习机和集成极限学习机。
1 极限学习机给定如图 1所示的单隐含层前馈神经网络(Extreme learning machine neural networks, SLFNNs),其中输入层结点的个数为d,d描述样例的特征或属性个数;隐含层结点个数为m,m为特征空间的维数;输出层结点个数为k,k为样例的类别个数。SLFNNs的这种网络结构可用一个三元组(d, m, k)表示。
给定训练集
$ f({\mathit{\boldsymbol{x}}_i}) = \sum\limits_{j = 1}^m {} {\mathit{\boldsymbol{\beta }}_j}g({\mathit{\boldsymbol{w}}_j}\cdot{\mathit{\boldsymbol{x}}_i} + {b_j})\;\;\;{\rm{ }}i = 1, 2, \ldots , n $ | (1) |
式中:wj和bj分别为随机生成的输入层连接权和隐含层结点偏置;βj为由式(2)确定的输出层连接权。
$ f({\mathit{\boldsymbol{x}}_i}) = \sum\limits_{j = 1}^m {} {\mathit{\boldsymbol{\beta }}_j}g({\mathit{\boldsymbol{w}}_j}\cdot{\rm{ }}{\mathit{\boldsymbol{x}}_i} + {\rm{ }}{b_j}) = {\mathit{\boldsymbol{y}}_i}\;\;\;\;{\rm{ }}i = 1, 2, \ldots , n $ | (2) |
式(2)可等价为
$ \mathit{\boldsymbol{H\beta }} = \mathit{\boldsymbol{Y}} $ | (3) |
其中
$ \mathit{\boldsymbol{H}} = \left( {\begin{array}{*{20}{c}} {g({\mathit{\boldsymbol{w}}_1}\cdot{\mathit{\boldsymbol{x}}_1} + {\rm{ }}{b_1})}& \ldots &{g({\mathit{\boldsymbol{w}}_m}\cdot{\mathit{\boldsymbol{x}}_1} + {b_m})}\\ \vdots&\vdots&\vdots \\ {g({\mathit{\boldsymbol{w}}_1}\cdot{\mathit{\boldsymbol{x}}_n} + {b_1})}& \ldots &{g{\rm{ }}({\mathit{\boldsymbol{w}}_m}\cdot{\mathit{\boldsymbol{x}}_n} + {b_m})} \end{array}} \right) $ | (4) |
$ \mathit{\boldsymbol{\beta }} = {(\mathit{\boldsymbol{\beta }}_1^{\rm{T}}, \mathit{\boldsymbol{\beta }}_2^{\rm{T}}, \ldots , \mathit{\boldsymbol{\beta }}_m^{\rm{T}})^{{\rm{T}}}} $ | (5) |
$ \mathit{\boldsymbol{Y}} = {(\mathit{\boldsymbol{y}}_1^{\rm{T}}, \mathit{\boldsymbol{y}}_2^{\rm{T}}, \ldots , \mathit{\boldsymbol{y}}_n^{\rm{T}})^{{\rm{T}}}} $ | (6) |
一般情况下,难以得到式(3)的精确解,用下面优化问题的解逼近。
$ \mathop {{\rm{min}}}\limits_\beta \parallel \mathit{\boldsymbol{H\beta }} - \mathit{\boldsymbol{Y}}\parallel $ | (7) |
式(7)的解可表示为
$ \mathit{\boldsymbol{\hat \beta }} = {\mathit{\boldsymbol{H}}^ + }\mathit{\boldsymbol{Y}} $ | (8) |
其中,H+是H的广义逆矩阵。算法1给出了ELM的伪代码描述。
算法1 极限学习机算法
(1) 输入:训练集
(2) 输出:权值矩阵
(3) for
(4) 随机给定输入权值wj和偏置bj;
(5) end
(6) 计算隐含层输出矩阵H;
(7) 计算矩阵H的广义逆矩阵H+;
(8) 计算权矩阵
(9) 输出权矩阵
集成重复训练极限学习机的数据分类方法是受下面思想的启发:对于给定的单隐含层前馈神经网络结构,重复训练该网络,会得到结构相同,但是模型参数不同的SLFNNs。如果隐含层结点个数也随机生成,那么可以得到结构和参数均不同的SLFNNs。本文方法就是用多数投票法集成这些重复训练得到的SLFNNs,并用于分类新的数据。
在各种ELM模型中,一般地,
算法2 集成重复训练极限学习机的数据分类方法
(1) 输入:训练集
(2) 输出:测试样例x的类标y(x)。
(3) for
(4) 运用极限学习机算法重复训练结构为(d, m, k)的SLFNN,得到SLFNN1,SLFNN 2,…,SLFNNp,设SLFNNi的输出为k维0-1二元组
(5) end
(6) for
(7) 运用训练好的SLFNNi计算测试样例x的输出,即x的类标向量
(8) 运用多数投票法确定测试样例x的类别:
(9) end
(10) 输出测试样例x的类标y(x)。
在算法2中,对于给定的测试样例x,步骤(8)中公式计算的是把x分类到每一类的结果。根据算法步骤(4)的描述容易看出,这一结果就是每一类的得票数。
3 实验结果及分析为了验证本文方法的有效性,在10个数据集上进行了3个实验: (1)用于发现集成分类器的个数对测试精度的影响; (2)与ELM算法进行比较; (3)与文献[24]中的算法进行比较。实验所用的数据集包括2个真实数据集(CT和RenRu)[27]和8个UCI数据集[28], 基本信息如表 1所示。
实验1 集成分类器的个数对测试精度的影响
首先在训练集上用ELM算法重复训练用于集成的SLFNNs,然后集成不同个数的分类器SLFNNs,并记录相应的测试精度,最后绘制集成分类器的个数与测试精度之间关系的曲线图,以发现比较合适的分类器集成个数。为了表述结果的清晰,在前5个数据集上的实验结果如图 2所示,在后5个数据集上的实验结果如图 3所示。
从图 2和图 3可看出随着集成分类器个数的增加,测试精度也随着增加,但增加到一定程度时,例如集成分类器的个数为4或5时,测试精度不会再有较大幅度的增加,有的甚至会略有下降。在实验2和实验3中,选择集成分类器的个数都为5。
实验2 本文方法与ELM的比较
在实验2中,单隐含层前馈神经网络的结构是固定的,即隐含层结点个数是固定的。对于不同的数据集,利用文献[29]中的方法确定网络隐含层最优结点个数,选择的结果列于表 2。
网络结构确定后,用服从[-1, +1]区间均匀分布U[-1,+1]的随机数初始输入层权值和隐含层偏置,并用极限学习机算法重复训练5个SLFNNs,最后用多数投票法集成训练好的这5个SLFNNs,用于测试新样例的类别。在10个数据集上与ELM进行比较的实验结果如图 4-13所示。
从图 4-13所示的实验结果可以看出,集成重复训练的ELM在10个数据集上的测试精度都优于ELM。此外,还用T-检验对实验结果进行了统计分成。T-检验中的显著性水平α=0.05,结果如表 3所示。从列于表 3的P值可以看出,因为除了在Pen数据集上,P值都非常小,所以集成重复训练的ELM的测试精度和ELM的测试精度有本质的区别,这一结论成立的概率至少为0.95。因此,上述结论具有可信性。
实验3 本文方法与EELM的比较
在实验3中,本文方法与文献[24]中的集成ELM模型(即EELM),从测试精度和CPU时间两方面进行了比较。用于集成的分类器的个数和实验2一致,也设定为5,但为了进一步增加分类器的多样性,在这个实验中,隐含层结点的个数也随机生成。具体地,若训练集的维数为d,在区间(pd, qd)中随机生成一个正整数m作为隐含层结点的个数。其中,p和q是严格大于1的正整数。对于实验所用的10个数据集,这些参数的设置如表 4所示。
网络结构确定后,在训练集上重复训练5个SLFNNs,然后用多数投票法进行集成,并用于分类测试样例。本文方法与EELM的比较结果如表 5所示。从表 5的实验结果可以清楚地发现本文提出的方法,无论在测试精度和CPU时间上,均优于EELM。
4 结束语
本文提出了一种集成重复训练极限学习机的数据分类方法,该方法利用了极限学习机随机初始化的思想。具体地,如果重复训练隐含层结点个数相同的SLFNNs,那么可得到结构相同但参数不同的学习模型。如果重复训练隐含层结点个数不同的SLFNNs(即隐含层结点个数也随机生成),那么可得到结构和参数都不同的学习模型。这两类模型都能从不同层面反应数据集不同视角的特征,可以保证分类器模型的多样性,特别是后者。集成这些学习模型用于数据分类,可起到取长补短的作用,提高数据分类的精度。本文方法的特点是思想简单、易于实现。与ELM和EELM在10个数据集上的实验结果及对实验结果的统计分析均表明本文方法优于其他两种算法。本文下一步的研究工作包括:(1)将研究集成重复训练异构SLFNNs问题,即SLFNNs用服从不同概率分布的随机数初始化网络参数,并研究集成重复训练同构SLFNNs和集成重复训练异构SLFNNs在测试精度上有无本质区别;(2)本文方法在大数据环境中的可扩展性问题。针对大数据问题,特别是具有现实背景意义的大数据问题,研究本文算法的可扩展性性问题。
[1] |
Huang G B, Zhu Q Y, Siew C K. Extreme learning machine: A new learning scheme of feedforward neural networks[C]//IEEE International Joint Conference on Neural Networks (IJCNN 2004). Budapest: IEEE, 2004: 985-990.
|
[2] |
Huang G B, Chen L, Siew C K. Universal approximation using incremental constructive feedforward networks with random hidden nodes[J]. IEEE Transactions on Neural Networks, 2006, 17(4): 879-892. DOI:10.1109/TNN.2006.875977 |
[3] |
Mohammed A A, Minhas R, Jonathan Q M, et al. Human face recognition based on multidimensional PCA and extreme learning machine[J]. Pattern Recognition, 2011, 44(10/11): 2588-2597. |
[4] |
Chacko B P, Vimal V R V, Raju G, et al. Handwritten character recognition using wavelet energy and extreme learning machine[J]. International Journal of Machine Learning and Cybernetics, 2012, 3(2): 149-161. DOI:10.1007/s13042-011-0049-5 |
[5] |
余丹, 吴小俊. 一种卷积神经网络和极限学习机相结合的人脸识别方法[J]. 数据采集与处理, 2016, 31(5): 996-1003. Yu Dan, Wu Xiaojun. Face recognition algorithm based on combination of convolutional neural networks and extreme learning machine[J]. Journal of Data Acquisition and Processing, 2016, 31(5): 996-1003. |
[6] |
张弦, 王宏力. 基于贯序正则极端学习机的时间序列预测及其应用[J]. 航空学报, 2011, 32(7): 1302-1308. Zhang Xian, Wang Hongli. Time series prediction based on sequential regularized extreme learning machine and its application[J]. Acta Aeronautica et Astronautica Sinica, 2011, 32(7): 1302-1308. |
[7] |
Yang H, Thomas P, Olga F. Fault detection based on signal reconstruction with auto-associative extreme learning machines[J]. Engineering Applications of Artificial Intelligence, 2017, 57: 105-117. DOI:10.1016/j.engappai.2016.10.010 |
[8] |
Zhu H, Tsang E C C, Wang X Z, et al. Monotonic classification extreme learning machine[J]. Neurocomputing, 2017, 225: 205-213. DOI:10.1016/j.neucom.2016.11.021 |
[9] |
Chen Y L, Wu W. Mapping mineral prospectivity using an extreme learning machine regression[J]. Ore Geology Reviews, 2017, 80: 200-213. DOI:10.1016/j.oregeorev.2016.06.033 |
[10] |
陶卿, 马坡, 张梦晗, 等. 机器学习随机优化方法的个体收敛性研究综述[J]. 数据采集与处理, 2017, 32(1): 17-25. Tao Qing, Ma Po, Zhang Menghan, et al. Individual convergence of stochastic optimization methods in machine learning[J]. Journal of Data Acquisition and Processing, 2017, 32(1): 17-25. |
[11] |
Liang N N, Huang G B, Saratchandran P, et al. A fast and accurate on-line sequential learning algorithm for feedforward networks[J]. IEEE Transactions on Neural Networks, 2006, 7(6): 1411-1423. |
[12] |
Zhai J H, Wang J G, Hu W X. Combination of OSELM classifiers with fuzzy integral for large scale classification[J]. Journal of Intelligent & Fuzzy Systems, 2015, 28(5): 2257-2268. |
[13] |
Zong W W, Huang G B, Chen Y Q. Weighted extreme learning machine for imbalance learning[J]. Neurocomputing, 2013, 101: 229-242. DOI:10.1016/j.neucom.2012.08.010 |
[14] |
Li K, Kong X F, Lu Z, et al. Boosting weighted ELM for imbalanced learning[J]. Neurocomputing, 2014, 128: 15-21. DOI:10.1016/j.neucom.2013.05.051 |
[15] |
Lin S J, Chang C H, Hsu M F. Multiple extreme learning machines for a two-class imbalance corporate life cycle prediction[J]. Knowledge-Based Systems, 2013, 39: 214-223. DOI:10.1016/j.knosys.2012.11.003 |
[16] |
Man Z H, Lee K, Wang D H, et al. A new robust training algorithm for a class of single-hidden layer feedforward neural networks[J]. Neurocomputing, 2011, 74(16): 2491-2501. DOI:10.1016/j.neucom.2010.11.033 |
[17] |
Man Z H, Lee K, Wang D H, et al. Robust single-hidden layer feedforward network-based pattern classifier[J]. IEEE Transactions on Neural Networks and Learning Systems, 2012, 23(12): 1974-1986. DOI:10.1109/TNNLS.2012.2218616 |
[18] |
Yu Q, Miche Y, Eirola E, et al. Regularized extreme learning machine for regression with missing data[J]. Neurocomputing, 2013, 102: 45-51. DOI:10.1016/j.neucom.2012.02.040 |
[19] |
He Q, Du C G, Wang Q, et al. A parallel incremental extreme SVM classifier[J]. Neurocomputing, 2011, 74(16): 2532-2540. DOI:10.1016/j.neucom.2010.11.036 |
[20] |
He Q, Shang T F, Zhuang F Z, et al. Parallel extreme learning machine for regression based on MapReduce[J]. Neurocomputing, 2013, 102: 52-58. DOI:10.1016/j.neucom.2012.01.040 |
[21] |
Wang B T, Huang S, Qiu J H, et al. Parallel online sequential extreme learning machine based on MapReduce[J]. Neurocomputing, 2015, 149(A): 224-232. |
[22] |
Xin J C, Wang Z Q, Chen C, et al. ELM*:Distributed extreme learning machine with MapReduce[J]. World Wide Web, 2014, 17(5): 1189-1204. DOI:10.1007/s11280-013-0236-2 |
[23] |
邓万宇, 郑庆华, 陈琳. 面向大样本数据的核化极速神经网络[J]. 计算机学报, 2014, 37(11): 2235-2246. Deng Wanyu, Zheng Qinghua, Chen Lin. Large-scale kernel extreme learning machine[J]. Chinese Journal of Computers, 2014, 37(11): 2235-2246. |
[24] |
Liu N, Wang H. Ensemble based extreme learning machine[J]. IEEE Signal Processing Letters, 2010, 17(8): 754-757. DOI:10.1109/LSP.2010.2053356 |
[25] |
Wang G, Li P. Dynamic Adaboost ensemble extreme learning machine[C]//International Conference on Advanced Computer Theory and Engineering.[S.l.]: IEEE, 2010: 54-58.
|
[26] |
Zhai J H, Xu H Y, Wang X Z. Dynamic ensemble extreme learning machine based on sample entropy[J]. Soft Computing, 2012, 16(9): 1493-1502. DOI:10.1007/s00500-012-0824-6 |
[27] |
翟俊海, 臧立光, 张素芳. 随机权分布对极限学习机性能影响的实验研究[J]. 计算机科学, 2016, 43(12): 125-129. Zhai Junhai, Zang Liguang, Zhang Sufang. Experimental research on effects of random weight distributions on performance of extreme leaming machine[J]. Computer Science, 2016, 43(12): 125-129. DOI:10.11896/j.issn.1002-137X.2016.12.022 |
[28] |
Frank A, Asuncion A. UCI machine learning repository[EB/OL]. http://archive.ics.uci.edu/ml, 2013-01-25.
|
[29] |
翟俊海, 李塔, 翟梦尧, 等. ELM中随机映射作用的实验研究[J]. 计算机工程, 2012, 38(20): 164-168. Zhai Junhai, Li Ta, Zhai Mengyao, et al. Experimental research on random mapping function in ELM[J]. Computer Engineering, 2012, 38(20): 164-168. DOI:10.3778/j.issn.1002-8331.2012.20.034 |