基于组合分类器的神经网络算法

赵仲恺

(中原银行股份有限公司 信息技术部，河南 郑州 450052)

基于组合分类器的神经网络算法

赵仲恺

(中原银行股份有限公司 信息技术部，河南 郑州 450052)

组合分类是一种有效的分类方法，然而训练完成后该方法须要存储大量的基分类器，并且每一次预测过程都需要统计每个基分类器的分类结果作最终的预测，同时具有较高的时间和空间复杂度。针对组合分类存在的问题提出了 EBNN，该方法使用神经网络从实例中学习值为实数、离散值或向量的函数，将组合分类器从实例到类标号的映射看成是一个函数，然后用神经网络来拟合这个函数，这样训练完成后只需存储一个神经网络模型，大幅降低了预测时的时间和空间复杂度。在20个UCI数据集上的实验结果表明，与决策树、神经网络以及支持向量机相比，EBNN具有更好的泛化性能。与Bagging相比，EBNN 在提高准确率的情况下，同时也大幅降低了预测阶段的相应时间和空间占用。

神经网络；组合分类器；组合剪枝；二次学习

组合分类器学习是机器学习、模式识别和数据挖掘中非常活跃的研究领域[1-2]。已有的研究结果表明，使用同一的训练信息，组合分类器通常表现出比单个分类器更好的泛化能力。但是，部分组合分类方法倾向构建泛化性能高的和泛化性能低的基分类器，而后者的存在不仅没有提高组合分类器的泛化能力，并且还可能造成组合分类器分类的准确率的下降，而且大规模的基分类器需要使用大量空间同时增加了组合分类器的预测响应时间。通常组合分类器选择[3-4]是处理该问题的一种有效方法。

组合选择是从组合分类器内部的子成员中选择一个最优或次优的子集作为子组合分类器以提高组合分类器分类性能的方法[5]。一个包含M个分类器的分类器库可以构造的子组合分类器的数目为2M-1(不包含空集)，即便某些子组合分类器的准确率优于其它，但是-在计算机上穷举搜索指数级空间上是不可行。通常的组合选择方法使用贪心搜索方法，找到的并不一定是最优的基分类器。目前，有使用向前选择、向后删除等贪心的方式对组合分类器剪枝[6-7]，尽管这些方式的采用有效地使组合分类器规模降低了并保持或者使组合分类器的性能得到提高，然而还有一些其他策略(如迭代置换)尚未探讨，本文从另一个角度处理组合分类器存在的问题，即使用神经网络拟合组合分类器的结果。神经网络学习方法[8]对于逼近实数值、离散值或向量值的目标函数提供了一种健壮性较强的方法。对于某些类型的问题，如学习解释复杂的现实世界中的传感器数据，神经网络是目前知道最有效的学习方法[9]。基于以上分析，论文提出了基于组合分类器的神经网络算法(Ensemble Base Neural Network，EBNN)解决组合分类方法占用大量内存和预测速度慢的问题，EBNN将组合分类器学到的模型看成是从实例集到类标号之间复杂的映射函数，利用组合分类器的训练结果重新构造数据集，然后利用神经网络拟合这个复杂的映射函数，EBNN训练完成后会得到一个新的神经网络模型来做最终的预测。这种方法的两种解释：(1)利用神经网络简化组合分类器训练得到的复杂模型；(2)利用组合分类器学习的结果训练神经网络，即从学习的结果中再次学习，即二次学习。

在10个UCI数据集上的实验结果表明，和 Ensemble Pruning、Bagging、C4.5、BP 和SVM相比，EBNN算法具有较高的准确率，并且和组合分类器的预测过程相比，EBNN具有较小的时间和空间复杂度。

1 相关工作

1.1 BP神经网络

神经网络[10-11](Back-Propagation，BP)是一类前馈型神经网络，是使用最多的典型神经网络，它由输入层、中间层和输出层组成，中间层也称隐含层，中间层可以是一个或多个。每层包含若干互不连接的神经元节点，相邻层之间各神经元通过不断变化的连接强度或权值进行全连接。神经网络分类过程可以分为训练和分类两个阶段。在训练阶段，首先定义网络的拓扑结构，再对训练样本中的每个属性的值进行规范化预处理， 然后用神经网络对已预处理的输入进行学习。训练完毕后，用训练好的神经网络对标识样本进行分类，图1所示为BP神经网络的拓扑结构。其中：输入层有n个节点，对应输入x1～xn；输出层有m个节点，对应输出y1～ym；隐含层有q个节点，对应的输出z1～zq；输入层与隐含层之间的权值vik，隐含层与输出层之间的权值为wkj。BP 网络中隐含层激活函数通常采用S型的对数或正切函数和线性函数。由于激活函数是连续可微的，不仅使得网络的容错性较好，而且可以严格利用剃度法进行推算。本文中所使用的反向传播算法BP在许多实际问题中取得了成功。

图1 BP 神经网络的拓扑结构图

1.2 组合分类器

组合分类器学习[12]是从给定的实例集中学习多个分类器，组合这些分类器的预测以获得更好的分类准确率，通常组合分类器学习包括两个阶段，训练基分类器阶段以及组合这些基分类器预测实例类标号阶段，把降低组合分类器规模作为中间阶段放到预测之前，通常把这个阶段叫做组合分类器剪枝(Ensemble Pruning)[13]，组合分类器往往能取得比单个分类器更好的泛化性能[14]。而构建有差异而又准确的基分类器是成功构建组合分类器的关键因素，常用的构建有差异训练集的方法大致有3种：(1)自助抽样方法；(2)Boosting方法；(3)基于特征变换的方法。

自助抽样方法的一个典型代表是Bagging，它的多样性是通过有放回随机抽取训练样本来实现的，用这种方式随机产生多个训练数据的子集，在每一个训练集的子集上训练一个分类器，最终分类结果是由多个分类器的分类结果多数投票而产生的。由于训练每个分类器的实例集都是通过自助抽样产生的，所以由Bagging学习的基分类器通常具有很高的准确率。然而，较之其它算法，即便Bagging使用对实例集差异性很敏感的分类器学习算法(如C4.5)构建基分类器，自助抽样方法构建的组合分类器差异性较低。因此，Bagging需要构建大量的基分类器才能获得良好的泛化性能[16]。

Boosting方法[17]的核心思想是使用组合结构提升“弱”分类器性能。Boosting方法是一个迭代过程，每次迭代都自适应地改变实例的分布特征，使得后建立的基分类器更关注于那些被前面的分类器错误分类的实例。与Bagging方法不同，Boosting为集合中的每个实例设置权值，并保证那些难分的实例具有更大的权重，以迫使后续分类器更关注它们。

不同于Bagging和Boosting方法，基于特征变换的组合分类器学习方法将训练实例集映射到不同的特征空间，进而形成不同的训练实例集以构建组合分类器。作为该方法的一个代表，旋转森林(Rotation Forest)表现出良好的泛化能力，但是旋转森林缺乏很好的理论支持。

以上介绍的组合分类方法存在共同弱点：倾向于构建过多的基分类器，大量的基分类器不仅需要大量的存储空间而且增加了组合分类器预测响应时间。目前，Guo[6]等人提出了贪心组合分类器剪枝来进一步提高分类器的性能。

2 EBNN

针对组合分类器存在的弱点，下面介绍基于组合分类器的神经网络算法基本思想。

组合分类器，尤其是Bagging，分类准确率虽高，但是训练完成后需要存储大量的基分类器，使得预测时响应时间较长且占用较大的存储空间。因此，结合组合分类器和神经网络提出了一种准确率又高，预测时响应速度又快的分类算法EBNN。神经网络选用BP神经网络，组合分类器选Bagging。

假设训练集D中共有n个实例，每个实例有m个属性，且训练集上共有k个类。用Di(1

图2 新实例的构造示意图

接下来，在新构造的数据集D’上训练一个神经网络，其中输入层节点的个数为属性个数m；隐藏层节点个数为传统神经网络节点个数的k倍(k为类的个数)；输出层的节点个数为k，即类的个数。图3给出一个属性个数为5，类个数为3时，隐藏层节点个数为4×3的网络结构示意图。具体过程见算法1。

算法1EBNN。

输入D有n个实例的训练集，每个实例有m个属性，共有k个类 。

输出训练好的神经网络模型方法。

(1)用 Bagging 算法在训练集D上训练一个分类模型Bagging；

(2)用学到的模型 Bagging 计算D中每个实例属于各个类的概率Pij(其中1

D’初始化为空集合

fori= 1 to n do

forj= 1 tokdo

用Pij替换Di的类标号得到新实例Dij

将Dij加入到D’中

end

for end

for；

(3)在D’上用图 3 网络结构训练一个神经网络模型；

(4)return 学习到的神经网络模型。

图3 EBNN 算法网络拓扑结构图

3 实验

3.1 数据集与实验设置

20个数据集从UCI机器学习库中随机选取，数据集的详细情况如表1所示。对于每个数据集，采用5-2折交叉验证分析算法的性能，重复5遍这种实验，因此，在每个数据集合上构建50个模型。为了比较，本文采用组合剪枝、Bagging、决策树、神经网络以及支持向量机与EBNN比较，所有的实验是基于开源数据挖掘工具洛阳铲(LySpoon)。

为方便说明，本实验部分约定EP(Ensemble Pruning)表示组合剪枝，C4.5表示决策树,BP(Back Propagation)表示神经网络，SVM(Support Vector Machine)。

表1 实验数据集信息

3.2 实验结果及相关分析

为了评估本文提出的算法性能，将EBNN分别与Ensemble Pruning(EP)、Bagging、C4.5、BP以及SVM5种分类方法对比。为了检验EBNN相对于其他算法的优势是否具有统计意义，本文选择显著度为95%的配对t测试对相关算法进行比较，如表2所示，粗体表示相应的算法(列)在相应的实例集(行)上具有最高的准确率或准确率相同但标准差最小，其中“*”表示EBNN显著优于其它方法；v表示EBNN显著劣于其它算法。括号内的是方差。例如，表2的第3行(对应于数据集balance-scale)第3列(对应算法C4.5)的结果显示，EBNN在评估指标准确率上显著优于C4.5;在表2的第9行(对应于数据集glass)第4列(对应算法Bagging)的结果显示，EBNN在评估指标准确率上显著劣于Bagging。在表2中，最后一行中的W-T-L表示EBNN算法在多少个数据集上赢-平手-输于其他算法。如C4.5那一列的W-T-L是16/1/3表示EBNN方法在16个数据集的分类准确率>C4.5，在3个数据集的分类准确率劣于C4.5，在1个数据集上两者的准确率是相同的。EBNN只是在个别数据集上比C4.5显著差。表2中的实验结果表明，EBNN算法的准确率比C4.5高了4个百分点，比BP高了1个百分点，比SVM高了2个百分点。

当对比两个或者多个算法时，一个合理的方法就是对比它们在每个数据集上的序(Rank)及在所有数据集上的平均序(Average Rank Across All Data Sets)。在一个数据集上，准确率最高的分类器的序为1，准确率次高的分类器的序为2，依次类推。当两个或者多个分类算法平手时(准确率相同)，获得一个平均序。图4当中横轴分别为表1中的对应的数据集的名称，

纵轴代表EBNN、EP、Bagging、C4.5、BP和SVM在每一个数据集上的序，不同深度的条形颜色代表不同的分类方法；在图5代表EBNN、EP、Bagging、C4.5、BP和SVM的平均序，分别为EBNN(2.45)、EP(2.65)、Bagging(3.3)、C4.5(4.7)、BP(3.55)和SVM(3.75)。显然EBNN的平均序低于其他5种方法的平均序。

EBNN的分类性能之所以在大部分数据集上优于其他分类算法，是因为EBNN用神经网络拟合了准确率较高的Bagging算法得到了和Bagging相似或更高的分类准确率；EBNN算法中又使用神经网络在Bagging算法学习的结果进行二次学习，使得神经网络的学习更具有目的性，取得了比传统神经网络更好的泛化能力。

图4 每个数据集在 EBNN、EP、Bagging等的等级

图5 EBNN、EP、Bagging等的平均序

datasetEBNNEPBaggingC4.5BPSVNaustralian86.3(4.17)87.03(4.16)86.3(3.6)86.01(4.47)84.78(4.64)*84.71(4.19)*balance-scale91.44(1.29)81.68(3.71)*82.32(3.72)*77.52(4.39)*90(2.15)*87.36(2.51)*balloons71.52(18.17)77.5(14.11)72.23(15.26)60.98(13.02)*77.05(14.67)74.37(13.06)banknote99.31(0.80)98.87(0.69)98.83(0.96)97.89(1.2)*100(0.00)v97.92(1.19)*breast-cancer73.95(6.61)73.26(7.57)73.24(6.92)75.89(5.66)v67.67(6.8)*69.05(8.53)*column84.84(4.81)82.26(6.82)*83.55(6.09)79.68(7.41)*84.84(6.29)79.35(7.5)*labor80.83(14.18)85(13.18)80.5(13.56)79.67(13.89)89.67(12.79)91.83(12.59)glass67.09(11.16)72.42(8.41)v73.86(11.47)v67.03(9.41)65.89(11.32)57.74(9.10)*hayes-roth79.81(8.85)72.94(10.77)*82.2(10.45)*70.3(10.67)*82.12(7.66)81.76(8.73)solar-flare86.8(1.36)86.8(1.36)86.8(1.36)86.8(1.36)82.44(4.37)86.65(1.40)average82.16381.32982.0577.88481.5780.093W-T-L-5/1/45/2/38/1/15/1/47/0/3

4 结束语

本文从新的角度提出了一种结合神经网络和组合分类器的EBNN算法，该算法将组合分类器学习到的结果用于训练神经网络，使得该算法既保持 Bagging算法较高的分类准确率，又保持了神经网络在预测阶段较快的相应时间和较小的存储占用。EBNN是一种算法框架，可以任意选择其它泛化性能更好的分类算法替换文中采用的Bagging算法来学习一个分类准确率更高的模型，然后用神经网络去简化这个模型。因此，下一步的工作将关注寻找准确率更高或适合特定领域的更复杂的算法进行学习，用它们学习到的结果进行神经网络的二次学习，以期得到更高的分类效果。

[1] Pangning T, Steinbach M, Kumar V. Introduction to data mining[J]. Data Analysis in the Cloud, 2014, 22(6):1-25.

[2] Thomas G Dietterich. Ensemble methods in machine learning[C].Cagliari:Proceedings of 1st International Workshop on Multiple Classifier Systems, 2000.

[3] Li Nan,Zhou Zhihua.Selective ensemble under regularization framework[C].Berlin:Proceedings of 8th Internationl Workshop on Multiple Classifier Systems,2009.

[4] Liu Zhuan,Dai Jun,Liu Ningzhong.Ensemble selection by GRASP[J].Applied Intelligence,2014,41(1):128-144.

[5] Li Kai,Han Yanxia.Study of selective ensemble learning method and its diversity based on decision tree and neural etwork[C].Xuzhou:Proceedings of 2010 Chinese Control and Decision Conference,2010.

[6] 郭华平,范明,职为梅.一种基于边界的贪心组合剪枝方法[J].模式识别与人工智能,2013,26(2):136-143.

[7] Markatopoulou F, Tsoumakas G, Vlahavas I. Dynamic ensemble pruning based on multi-label classification[J]. Neurocomputing, 2015, 150:501-512.

[8] Tom M Mitchell.Machine learning[M].United States of America:McGraw-Hill,1997.

[9] 王珣.一种基于多目标的自组织神经网络学习方法[J].小型微型计算机系统,2002,25(5):565-569.

[10] Wang Lin,Zeng Yi,Chen Tao.Back propagation neural network with adaptive differential evolution algorithm for time series forecasting[J].Expert Systems with Applications, 2015, 42(12):5019-5402.

[11] 冯立颖.改进的 BP 神经网络算法及其应用[J].计算机仿真,2010,27(12):172-175.

[12] Tulyakov S,Jaeger S,Govindaraju V,et a1.Review of classifier combination methods[J].Machine Learning in Document Analysis and Recognition,2008(90):361-386.

[13] Zhao Qiangli,Jiang Yanhuang,Xu Ming.A fast ensemble pruning algorithm based on pattern mining process[J].Data Ming and Knowledge Discovery,2009,19(2):277-292.

[14] 职为梅,郭华平,张银峰,等.一种面向非平衡数据集分类问题的组合选择方法[J].小型微型计算机系统,2014,35(4):770-775.

[15] Leo Breiman.Bagging predictors[J].Machine Learning,1996,24(2):123-140.

[16] La Lei,Guo Qiao,Cao Qiming,et al.Transfer learningwith reasonable boosting strategy[J].Neural Computing and Applications,2014,24(3-4):807-816.

[17] Rodríguez Juan J,Kuncheva Ludmila I,Alonso Carlos JRotation forest: A new classifier ensemble method[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2006,28(10):1619-1630.

Ensemble Based Neutral Network

ZHAO Zhongkai

(Information Technology Department,Zhong Yuan Bank,Zhengzhou 450052,China)

Ensemble is an effective classification method, however, the method needs to store a large number of base classifiers after training and every prediction process requires classification result of each base classifier, besides, it has higher time and space complexity. Aiming at problems of ensemble, EBNN (Ensemble Based Neural Network) was proposed. This method uses neural network to learn from function of instance values, the values are real numbers, discrete values or vector. We can consider the mapping of instances to class labels with ensemble as a function, and then use neural network to fit this function. So it only needs to store a neural network model after training, and reduces time and space complexity of predictions greatly. The results of experiments on 20 UCI data sets indicate that EBNN shows better generalization performance comparing to decision tree, neural network and support vector machine. Compared with Bagging, EBNN not only improves accuracy, but also greatly reduces the corresponding time and space of prediction stage.

neural network;classifier combination;ensemble pruning;secondary learning

2017- 02- 06

国家自然科学基金(61170223)；河南省教育厅科学技术研究重点基金(14A520016)

赵仲恺(1990-)，男，硕士研究生。研究方向：数据挖掘等。

10.16180/j.cnki.issn1007-7820.2017.12.011

TP181

A

1007-7820(2017)12-039-05