趙仲愷

(中原銀行股份有限公司 信息技術(shù)部，河南 鄭州 450052)

基于組合分類器的神經(jīng)網(wǎng)絡算法

趙仲愷

(中原銀行股份有限公司 信息技術(shù)部，河南 鄭州 450052)

組合分類是一種有效的分類方法，然而訓練完成后該方法須要存儲大量的基分類器，并且每一次預測過程都需要統(tǒng)計每個基分類器的分類結(jié)果作最終的預測，同時具有較高的時間和空間復雜度。針對組合分類存在的問題提出了 EBNN，該方法使用神經(jīng)網(wǎng)絡從實例中學習值為實數(shù)、離散值或向量的函數(shù)，將組合分類器從實例到類標號的映射看成是一個函數(shù)，然后用神經(jīng)網(wǎng)絡來擬合這個函數(shù)，這樣訓練完成后只需存儲一個神經(jīng)網(wǎng)絡模型，大幅降低了預測時的時間和空間復雜度。在20個UCI數(shù)據(jù)集上的實驗結(jié)果表明，與決策樹、神經(jīng)網(wǎng)絡以及支持向量機相比，EBNN具有更好的泛化性能。與Bagging相比，EBNN 在提高準確率的情況下，同時也大幅降低了預測階段的相應時間和空間占用。

神經(jīng)網(wǎng)絡；組合分類器；組合剪枝；二次學習

組合分類器學習是機器學習、模式識別和數(shù)據(jù)挖掘中非?；钴S的研究領(lǐng)域[1-2]。已有的研究結(jié)果表明，使用同一的訓練信息，組合分類器通常表現(xiàn)出比單個分類器更好的泛化能力。但是，部分組合分類方法傾向構(gòu)建泛化性能高的和泛化性能低的基分類器，而后者的存在不僅沒有提高組合分類器的泛化能力，并且還可能造成組合分類器分類的準確率的下降，而且大規(guī)模的基分類器需要使用大量空間同時增加了組合分類器的預測響應時間。通常組合分類器選擇[3-4]是處理該問題的一種有效方法。

組合選擇是從組合分類器內(nèi)部的子成員中選擇一個最優(yōu)或次優(yōu)的子集作為子組合分類器以提高組合分類器分類性能的方法[5]。一個包含M個分類器的分類器庫可以構(gòu)造的子組合分類器的數(shù)目為2M-1(不包含空集)，即便某些子組合分類器的準確率優(yōu)于其它，但是-在計算機上窮舉搜索指數(shù)級空間上是不可行。通常的組合選擇方法使用貪心搜索方法，找到的并不一定是最優(yōu)的基分類器。目前，有使用向前選擇、向后刪除等貪心的方式對組合分類器剪枝[6-7]，盡管這些方式的采用有效地使組合分類器規(guī)模降低了并保持或者使組合分類器的性能得到提高，然而還有一些其他策略(如迭代置換)尚未探討，本文從另一個角度處理組合分類器存在的問題，即使用神經(jīng)網(wǎng)絡擬合組合分類器的結(jié)果。神經(jīng)網(wǎng)絡學習方法[8]對于逼近實數(shù)值、離散值或向量值的目標函數(shù)提供了一種健壯性較強的方法。對于某些類型的問題，如學習解釋復雜的現(xiàn)實世界中的傳感器數(shù)據(jù)，神經(jīng)網(wǎng)絡是目前知道最有效的學習方法[9]。基于以上分析，論文提出了基于組合分類器的神經(jīng)網(wǎng)絡算法(Ensemble Base Neural Network，EBNN)解決組合分類方法占用大量內(nèi)存和預測速度慢的問題，EBNN將組合分類器學到的模型看成是從實例集到類標號之間復雜的映射函數(shù)，利用組合分類器的訓練結(jié)果重新構(gòu)造數(shù)據(jù)集，然后利用神經(jīng)網(wǎng)絡擬合這個復雜的映射函數(shù)，EBNN訓練完成后會得到一個新的神經(jīng)網(wǎng)絡模型來做最終的預測。這種方法的兩種解釋：(1)利用神經(jīng)網(wǎng)絡簡化組合分類器訓練得到的復雜模型；(2)利用組合分類器學習的結(jié)果訓練神經(jīng)網(wǎng)絡，即從學習的結(jié)果中再次學習，即二次學習。

在10個UCI數(shù)據(jù)集上的實驗結(jié)果表明，和 Ensemble Pruning、Bagging、C4.5、BP 和SVM相比，EBNN算法具有較高的準確率，并且和組合分類器的預測過程相比，EBNN具有較小的時間和空間復雜度。

1 相關(guān)工作

1.1 BP神經(jīng)網(wǎng)絡

神經(jīng)網(wǎng)絡[10-11](Back-Propagation，BP)是一類前饋型神經(jīng)網(wǎng)絡，是使用最多的典型神經(jīng)網(wǎng)絡，它由輸入層、中間層和輸出層組成，中間層也稱隱含層，中間層可以是一個或多個。每層包含若干互不連接的神經(jīng)元節(jié)點，相鄰層之間各神經(jīng)元通過不斷變化的連接強度或權(quán)值進行全連接。神經(jīng)網(wǎng)絡分類過程可以分為訓練和分類兩個階段。在訓練階段，首先定義網(wǎng)絡的拓撲結(jié)構(gòu)，再對訓練樣本中的每個屬性的值進行規(guī)范化預處理， 然后用神經(jīng)網(wǎng)絡對已預處理的輸入進行學習。訓練完畢后，用訓練好的神經(jīng)網(wǎng)絡對標識樣本進行分類，圖1所示為BP神經(jīng)網(wǎng)絡的拓撲結(jié)構(gòu)。其中：輸入層有n個節(jié)點，對應輸入x1～xn；輸出層有m個節(jié)點，對應輸出y1～ym；隱含層有q個節(jié)點，對應的輸出z1～zq；輸入層與隱含層之間的權(quán)值vik，隱含層與輸出層之間的權(quán)值為wkj。BP 網(wǎng)絡中隱含層激活函數(shù)通常采用S型的對數(shù)或正切函數(shù)和線性函數(shù)。由于激活函數(shù)是連續(xù)可微的，不僅使得網(wǎng)絡的容錯性較好，而且可以嚴格利用剃度法進行推算。本文中所使用的反向傳播算法BP在許多實際問題中取得了成功。

圖1 BP 神經(jīng)網(wǎng)絡的拓撲結(jié)構(gòu)圖

1.2 組合分類器

組合分類器學習[12]是從給定的實例集中學習多個分類器，組合這些分類器的預測以獲得更好的分類準確率，通常組合分類器學習包括兩個階段，訓練基分類器階段以及組合這些基分類器預測實例類標號階段，把降低組合分類器規(guī)模作為中間階段放到預測之前，通常把這個階段叫做組合分類器剪枝(Ensemble Pruning)[13]，組合分類器往往能取得比單個分類器更好的泛化性能[14]。而構(gòu)建有差異而又準確的基分類器是成功構(gòu)建組合分類器的關(guān)鍵因素，常用的構(gòu)建有差異訓練集的方法大致有3種：(1)自助抽樣方法；(2)Boosting方法；(3)基于特征變換的方法。

自助抽樣方法的一個典型代表是Bagging，它的多樣性是通過有放回隨機抽取訓練樣本來實現(xiàn)的，用這種方式隨機產(chǎn)生多個訓練數(shù)據(jù)的子集，在每一個訓練集的子集上訓練一個分類器，最終分類結(jié)果是由多個分類器的分類結(jié)果多數(shù)投票而產(chǎn)生的。由于訓練每個分類器的實例集都是通過自助抽樣產(chǎn)生的，所以由Bagging學習的基分類器通常具有很高的準確率。然而，較之其它算法，即便Bagging使用對實例集差異性很敏感的分類器學習算法(如C4.5)構(gòu)建基分類器，自助抽樣方法構(gòu)建的組合分類器差異性較低。因此，Bagging需要構(gòu)建大量的基分類器才能獲得良好的泛化性能[16]。

Boosting方法[17]的核心思想是使用組合結(jié)構(gòu)提升“弱”分類器性能。Boosting方法是一個迭代過程，每次迭代都自適應地改變實例的分布特征，使得后建立的基分類器更關(guān)注于那些被前面的分類器錯誤分類的實例。與Bagging方法不同，Boosting為集合中的每個實例設置權(quán)值，并保證那些難分的實例具有更大的權(quán)重，以迫使后續(xù)分類器更關(guān)注它們。

不同于Bagging和Boosting方法，基于特征變換的組合分類器學習方法將訓練實例集映射到不同的特征空間，進而形成不同的訓練實例集以構(gòu)建組合分類器。作為該方法的一個代表，旋轉(zhuǎn)森林(Rotation Forest)表現(xiàn)出良好的泛化能力，但是旋轉(zhuǎn)森林缺乏很好的理論支持。

以上介紹的組合分類方法存在共同弱點：傾向于構(gòu)建過多的基分類器，大量的基分類器不僅需要大量的存儲空間而且增加了組合分類器預測響應時間。目前，Guo[6]等人提出了貪心組合分類器剪枝來進一步提高分類器的性能。

2 EBNN

針對組合分類器存在的弱點，下面介紹基于組合分類器的神經(jīng)網(wǎng)絡算法基本思想。

組合分類器，尤其是Bagging，分類準確率雖高，但是訓練完成后需要存儲大量的基分類器，使得預測時響應時間較長且占用較大的存儲空間。因此，結(jié)合組合分類器和神經(jīng)網(wǎng)絡提出了一種準確率又高，預測時響應速度又快的分類算法EBNN。神經(jīng)網(wǎng)絡選用BP神經(jīng)網(wǎng)絡，組合分類器選Bagging。

假設訓練集D中共有n個實例，每個實例有m個屬性，且訓練集上共有k個類。用Di(1

圖2 新實例的構(gòu)造示意圖

接下來，在新構(gòu)造的數(shù)據(jù)集D’上訓練一個神經(jīng)網(wǎng)絡，其中輸入層節(jié)點的個數(shù)為屬性個數(shù)m；隱藏層節(jié)點個數(shù)為傳統(tǒng)神經(jīng)網(wǎng)絡節(jié)點個數(shù)的k倍(k為類的個數(shù))；輸出層的節(jié)點個數(shù)為k，即類的個數(shù)。圖3給出一個屬性個數(shù)為5，類個數(shù)為3時，隱藏層節(jié)點個數(shù)為4×3的網(wǎng)絡結(jié)構(gòu)示意圖。具體過程見算法1。

算法1EBNN。

輸入D有n個實例的訓練集，每個實例有m個屬性，共有k個類 。

輸出訓練好的神經(jīng)網(wǎng)絡模型方法。

(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 網(wǎng)絡結(jié)構(gòu)訓練一個神經(jīng)網(wǎng)絡模型；

(4)return 學習到的神經(jīng)網(wǎng)絡模型。

圖3 EBNN 算法網(wǎng)絡拓撲結(jié)構(gòu)圖

3 實驗

3.1 數(shù)據(jù)集與實驗設置

20個數(shù)據(jù)集從UCI機器學習庫中隨機選取，數(shù)據(jù)集的詳細情況如表1所示。對于每個數(shù)據(jù)集，采用5-2折交叉驗證分析算法的性能，重復5遍這種實驗，因此，在每個數(shù)據(jù)集合上構(gòu)建50個模型。為了比較，本文采用組合剪枝、Bagging、決策樹、神經(jīng)網(wǎng)絡以及支持向量機與EBNN比較，所有的實驗是基于開源數(shù)據(jù)挖掘工具洛陽鏟(LySpoon)。

為方便說明，本實驗部分約定EP(Ensemble Pruning)表示組合剪枝，C4.5表示決策樹,BP(Back Propagation)表示神經(jīng)網(wǎng)絡，SVM(Support Vector Machine)。

表1 實驗數(shù)據(jù)集信息

3.2 實驗結(jié)果及相關(guān)分析

為了評估本文提出的算法性能，將EBNN分別與Ensemble Pruning(EP)、Bagging、C4.5、BP以及SVM5種分類方法對比。為了檢驗EBNN相對于其他算法的優(yōu)勢是否具有統(tǒng)計意義，本文選擇顯著度為95%的配對t測試對相關(guān)算法進行比較，如表2所示，粗體表示相應的算法(列)在相應的實例集(行)上具有最高的準確率或準確率相同但標準差最小，其中“*”表示EBNN顯著優(yōu)于其它方法；v表示EBNN顯著劣于其它算法。括號內(nèi)的是方差。例如，表2的第3行(對應于數(shù)據(jù)集balance-scale)第3列(對應算法C4.5)的結(jié)果顯示，EBNN在評估指標準確率上顯著優(yōu)于C4.5;在表2的第9行(對應于數(shù)據(jù)集glass)第4列(對應算法Bagging)的結(jié)果顯示，EBNN在評估指標準確率上顯著劣于Bagging。在表2中，最后一行中的W-T-L表示EBNN算法在多少個數(shù)據(jù)集上贏-平手-輸于其他算法。如C4.5那一列的W-T-L是16/1/3表示EBNN方法在16個數(shù)據(jù)集的分類準確率>C4.5，在3個數(shù)據(jù)集的分類準確率劣于C4.5，在1個數(shù)據(jù)集上兩者的準確率是相同的。EBNN只是在個別數(shù)據(jù)集上比C4.5顯著差。表2中的實驗結(jié)果表明，EBNN算法的準確率比C4.5高了4個百分點，比BP高了1個百分點，比SVM高了2個百分點。

當對比兩個或者多個算法時，一個合理的方法就是對比它們在每個數(shù)據(jù)集上的序(Rank)及在所有數(shù)據(jù)集上的平均序(Average Rank Across All Data Sets)。在一個數(shù)據(jù)集上，準確率最高的分類器的序為1，準確率次高的分類器的序為2，依次類推。當兩個或者多個分類算法平手時(準確率相同)，獲得一個平均序。圖4當中橫軸分別為表1中的對應的數(shù)據(jù)集的名稱，

縱軸代表EBNN、EP、Bagging、C4.5、BP和SVM在每一個數(shù)據(jù)集上的序，不同深度的條形顏色代表不同的分類方法；在圖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的分類性能之所以在大部分數(shù)據(jù)集上優(yōu)于其他分類算法，是因為EBNN用神經(jīng)網(wǎng)絡擬合了準確率較高的Bagging算法得到了和Bagging相似或更高的分類準確率；EBNN算法中又使用神經(jīng)網(wǎng)絡在Bagging算法學習的結(jié)果進行二次學習，使得神經(jīng)網(wǎng)絡的學習更具有目的性，取得了比傳統(tǒng)神經(jīng)網(wǎng)絡更好的泛化能力。

圖4 每個數(shù)據(jù)集在 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 結(jié)束語

本文從新的角度提出了一種結(jié)合神經(jīng)網(wǎng)絡和組合分類器的EBNN算法，該算法將組合分類器學習到的結(jié)果用于訓練神經(jīng)網(wǎng)絡，使得該算法既保持 Bagging算法較高的分類準確率，又保持了神經(jīng)網(wǎng)絡在預測階段較快的相應時間和較小的存儲占用。EBNN是一種算法框架，可以任意選擇其它泛化性能更好的分類算法替換文中采用的Bagging算法來學習一個分類準確率更高的模型，然后用神經(jīng)網(wǎng)絡去簡化這個模型。因此，下一步的工作將關(guān)注尋找準確率更高或適合特定領(lǐng)域的更復雜的算法進行學習，用它們學習到的結(jié)果進行神經(jīng)網(wǎng)絡的二次學習，以期得到更高的分類效果。

[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īng)網(wǎng)絡學習方法[J].小型微型計算機系統(tǒng),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īng)網(wǎng)絡算法及其應用[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] 職為梅,郭華平,張銀峰,等.一種面向非平衡數(shù)據(jù)集分類問題的組合選擇方法[J].小型微型計算機系統(tǒng),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)；河南省教育廳科學技術(shù)研究重點基金(14A520016)

趙仲愷(1990-)，男，碩士研究生。研究方向：數(shù)據(jù)挖掘等。

10.16180/j.cnki.issn1007-7820.2017.12.011

TP181

A

1007-7820(2017)12-039-05