一種基于小生境的負相關神經網絡集成算法

盛偉國，單鵬霄

(浙江工業大學 計算機科學與技術學院，浙江 杭州 310023)

?

一種基于小生境的負相關神經網絡集成算法

盛偉國，單鵬霄

(浙江工業大學 計算機科學與技術學院，浙江 杭州 310023)

提出了一種基于小生境的負相關神經網絡集成算法.所提方法結合了負相關學習和進化算法，采用同時訓練的方式對多個神經網絡進行訓練，不僅能使網絡之間產生有效的差異度，而且能促進網絡之間的交互性和合作性.此外，在進化過程中引入了一種改進的小生境技術，能更有效地維持網絡種群的多樣性，從而保證神經網絡集成的差異度.所提方法在6個分類數據集上進行了測試，并且與一些相關神經網絡集成方法進行對比.實驗結果表明所提方法能得到一個有效的神經網絡集成.

神經網絡；集成學習；負相關學習；小生境；進化算法

神經網絡(Neural network)方法已經廣泛地應用于許多領域[1-2]，但是依然存在諸多問題.例如，神經網絡在訓練過程中很不穩定，且容易陷入局部最優等，這都將限制神經網絡的泛化能力.當訓練的神經網絡框架越大時，上述問題表現得越為嚴重.Hansen等[3]于1990年開創性地提出了神經網絡集成(Neural network ensemble)方法，即組合多個訓練好的神經網絡，這種方法能有效地提高神經網絡的穩定性和泛化能力.理論和實驗結果[4-5]進一步指出一個有效的神經網絡集成方法不僅要提高集成中單個網絡的精確度，而且要使網絡之間產生差異度，差異度是指個體網絡位于相同輸入的不同部分的誤差.迄今為止，已經有大量的方法被提出致力于構造個體網絡精確度高且個體網絡間差異度大的神經網絡集成.其中大多數方法采用獨立訓練方式和順序訓練方式對集成中個體網絡進行訓練，如Bagging[6]和Boosting[7]方法.然而，Liu等[8]提出了一種負相關學習方法，采用同時訓練方式訓練集成中的網絡，并且在每個網絡的誤差函數中加入一個相關性的懲罰項，該懲罰項能使個體網絡之間生成負相關的誤差.因為負相關學習方法能使個體網絡間產生有效的差異度，所以受到了很多關注和發展[9-10].研究指出負相關學習方法與進化算法相結合具有更好的性能.如Liu等[11]提出了負相關學習與進化算法相結合的方式來訓練神經網絡集成.Chandra等[12]提出了Diverse and accurate ensemble learning algorithm (DIVACE)用于訓練神經網路集成,在DIVACE中使用了多目標進化算法(Multi-objective evolutionary algorithm).這些算法不僅能促進神經網絡集成的差異度，而且能鼓勵集成中個體網絡的合作.然而，使用傳統的進化算法[13]存在一些嚴重的問題，容易發生“早熟”或非全局性收斂等，這會導致進化過程中網絡之間的差異度得不到很好的維持，最終影響神經網絡集成的性能.因此如何在進化過程中維持種群內的多樣性是至關重要的.

鑒于上述的研究狀況，筆者提出了一種基于小生境的負相關神經網絡集成算法，結合了負相關學習方法和進化算法，并在此基礎上又引入了一種改進的小生境技術[14-15]，能更有效地維持種群的多樣性，確保神經網絡集成的差異度.

1 基于小生境的負相關神經網絡集成算法

所提方法使用了負相關學習方法對多個神經網絡同時訓練，使個體網絡之間存在負相關性；同時，結合了進化算法，并且引入了一種改進的小生境技術維持種群的多樣性，保證了神經網絡集成的差異度.算法的具體步驟如下：

Step 1 初始化神經網絡種群，采用了隨機初始化的方式對每個網絡框架內隱結點數量和權值進行賦值.

Step 2 計算種群中每個網絡的適應度值，適應度值為網絡誤差的倒數.

Step 3 將種群中所有個體網絡進行組合構造成神經網絡集成，并且計算神經網絡集成的泛化誤差E，如果E

Step 4 使用改進的小生境方法選擇個體進行交叉和變異操作.

Step 5 計算每個網絡負相關學習的泛化誤差Ei，并使用BP算法對網絡內的權值進行優化調整.

Step 6 合并父代和子代，使用輪盤法選擇個體生成新的種群，返回至Step 3.

1.1 編碼方式

1.2 遺傳操作

為了減輕單點交叉操作帶來的permutationproblem，所提方法采用雙點交叉操作，具體實現過程分別為

P1：

P2：

其中：P1和P2分別為父代個體，分別包含3個隱節點和4個隱節點.在交叉操作過程中，P1的第1個隱節點的權值與P2的第2個隱節點的權值進行交換，產生子代off1和off2，即

off1：

off2：

對于突變操作，所提算法采用了三種類型用于增加網絡框架的多樣性，包括：權值的高斯突變、節點間鏈接的刪除和節點間鏈接的增加.

2 負相關神經網絡集成算法

集成學習的相關理論分析指出，平衡集成中個體的精確度和個體間的差異度是至關重要的.對于該問題，負相關學習方法是一種有效的神經網絡集成算法.

2.1 集成學習的理論分析

對于回歸問題的集成學習，Krogh等[16]提出了Ambiguity分解，并且通過該分解給出了集成學習的泛化誤差公式為

fens(x))2

(1)

(2)

從式(1)中可以看出：集成學習的泛化誤差取決于個體的泛化誤差和集成的差異度.因此要降低集成的泛化誤差，必須盡量減小個體的泛化誤差，同時增大集成中個體的差異度.不幸的是提高集成中個體的精確度必然降低個體間的差異度，反之亦然.因此，如何平衡集成中個體的精確度與個體間的差異度的關系仍是一個研究難點和熱點.關于分類問題的集成學習，毫無疑問存在相同的問題.對于該問題，負相關學習是一種很有潛力的方法.

2.2 負相關學習

假設給定一個訓練集T，T={(x(1),t(1)),(x(2),t(2)),…,(x(n),t(n))},其中x為網絡的輸入，t為網絡的期望.

Step 1 計算整個神經網絡集成的輸出F(n)，其表達式為

(3)

式中：M為集成中成員網絡的數量；Fi(n)為成員網絡i在第n個訓練樣本上的輸出；F(n)為集成在第n個訓練樣本上的輸出.

Step 2 計算第i個成員網絡的誤差函數，其表達式為

(4)

式中：第一項為第i個成員網絡在訓練集上的誤差；第二項是相關懲罰項，λ(0≤λ≤1)是懲罰項的參數，用于調整懲罰強度；最小化Pi的目的是使每個網絡與集成中剩余的網絡產生負相關的誤差，相關懲罰項的計算方法為

(5)

Step 3 使用BP算法和引入了懲罰項的新誤差函數來訓練神經網絡并調整權值.

3 小生境技術

在使用進化算法訓練神經網絡集成時，保證種群中個體網絡間存在差異度是至關重要的.該問題的關鍵在于怎樣從上一代種群中選擇具有差異度的個體網絡.小生境技術[14-15]能夠維持種群的多樣性并且允許算法擴大搜索的范圍.因此，所提方法引入一種改進的適應度共享機制的小生境技術[17-18]，能更好地維持網絡種群的多樣性，從而保證神經網絡集成的差異度.改進的小生境技術優點：1)采用自適應的方式設置共享半徑δs；2)維持種群中網絡框架的多樣性；3)鼓勵相似的個體網絡進行競爭.

傳統的適應度共享機制的小生境技術根據個體網絡之間的相似程度，將整個網絡種群劃分成一系列的小生境群體，然后利用適應度共享機制對每個小生境群體中的個體網絡的適應度進行重新調整，從而降低相似的個體網絡的選擇概率.適應度共享機制的具體操作如下：

首先給定一個共享函數sh(dij)，用于計算小生境群體中個體網絡之間的距離.在使用小生境維持神經網絡種群的過程中，如何計算兩個網絡之間的距離尤為重要，因為網絡之間的距離代表著網絡之間的差異度，使用合適的方式計算距離能使進化過程有效地維持網絡種群內個體網絡間的差異度.在所提方法中使用如下公式來計算個體網絡之間的距離為

(6)

式中：N為訓練樣本數量；fi(xn)和fj(xn)分別為個體網絡i和個體網絡j在第n個樣本上的輸出.

然后計算小生境群體的共享度，共享度是指個體網絡與小生境內剩余個體網絡之間共享函數的總和sh，其表達式為

(7)

式中：m為種群中個體網絡的數量；dij為網絡i和網絡j之間的距離；sh(dij)為共享函數，計算式為

(8)

式中δs為共享半徑.如果兩個網絡的相似度大于δs，那么它們不存在共享適應度;當兩個網絡之間的相似度小于δs才能共享適應度.

最后基于共享度重新調整種群中網絡的適應度值，計算方式為

(9)

式中：fsi為網絡共享后的適應度；fi為網絡共享前的適應度.

傳統的適應度共享機制的小生境方法存在一個嚴重的問題，共享半徑需要被人為提前設定.然而，在很多應用中無法得到適應度搜索空間的先驗知識，所以不能有效預先設定一個合適的共享半徑.為了克服該問題，筆者采用了自適應的方式設定共享半徑δs，其表達式為

(10)

式中：m為種群中個體網絡的數量；dij為網絡i和網絡j之間的距離.

在進化過程中，維持個體網絡框架的多樣性也是很有必要的.因為神經網絡的性能在很大程度上取決于網絡框架，尤其是網絡框架中隱節點的數量.不同框架的個體網絡擁有不同的學習能力，可以促進個體網絡間產生差異度.為此，在初始化過程中，采用隨機方式初始化網絡框架中的節點數量，并且使用了雙點交叉的方法.在交叉過程中，兩個含有相同或不同隱節點數量的網絡都會被允許交換隱節點的權值，從而維持網絡框架中隱節點數量的多樣性.此外，由于相似度遠的個體網絡進行交叉往往會導致生成表現型差的后代，所以改進的小生境技術鼓勵相似度近的個體網絡進行交叉操作.具體實現過程：在選擇交叉過程中，首先種群隨機選取一個網絡P1，然后在種群中隨機選擇若干個體網絡組成一個交叉池，在這里交叉池中個體數量設為3，最后在交叉池中選取與P1最相似(距離最小)的網絡P2進行交叉.通過使用改進的小生境技術，能夠更好地維持種群的多樣性，并且促進搜索更優的個體網絡.

4 實驗與分析

實驗過程選擇了Australian credit card，Diabe-

tes，Glass，Breast cancer，Image和Heart 6個分類數據集進行測試，這些數據集來源于The university of california at irvine (UCI) machine learning repository，并且有著不同的特征，如表1所示.

表1 6個分類數據集的特征

在實驗測試過程中，采用了10-fold交叉驗證方法，先將每個數據集分成數目相同的10子集，每次訓練網絡時，循環選擇其中的9個子集用于訓練，剩余1個子集用于測試.下述的實驗結果是在數據集上獨立運行30次然后取其平均值.此外，在實驗過程中還有一些參數需要被提前設置，種群大小為30，隱結點的初始值范圍為3～15，權值的初始范圍為-1～1，神經網絡集成的泛化誤差為0.05.負相關學習中，懲罰項參數λ=0.8，BP算法的學習率和學習動量分別為0.3和0.8.實驗中使用的這些參數值并不意味著是最優值.

所提方法先在Australian credit card和Diabetes這兩個數據集上進行測試，并觀察神經網絡集成的分類錯誤率的變化.如圖1所示，所提出的方法能在進化20代后就得到一個分類錯誤率較低的神經網絡集成，這說明所提出的方法能快速設計一個有效的神經網絡集成.

圖1 筆者方法在2個數據集上的分類錯誤率變化Fig.1 The variance of two classification error rate on two data sets of this method

為了進一步證明所提方法的有效性，實驗測試了一些相關的神經網絡集成方法，如Bagging，Boosting和傳統的負相關學習，并且將其實驗結果進行對比.這些實驗結果的對比的目的不是為了說明所提方法優越于其他方法，而是為了對所提方法有一個更深入的了解.

表2列出了4種方法在6個數據集上的實驗結果，表中可以看出，在所有實驗的數據集上所提方法取得了最低的分類錯誤率.傳統的負相關學習方法的性能有效地被提高.如傳統的負相關學習方法在Glass數據集上分類錯誤率為0.312，所提方法的錯誤分類率為0.269，提高了0.053.這是因為所提方法加入了基于改進的小生境算法，能有效地維持神經網絡集成的差異度.與Bagging和Boosting方法相比，所提方法能有效地提高神經網絡集成的泛化能力.如Bagging和Boosting在Australian credit card上的分類錯誤率分別為0.148和0.157，所提方法的分類錯誤率為0.121.原因在于所提方法通過結合了負相關學習和進化算法同時多個訓練神經網絡，使網絡之間進行信息交流和合作，產生有效的差異度.

表2 4種神經網絡集成方法在6個數據集上分類錯誤率的比較

Table 2 Comparing the classification error rate of four methods on six classification problems

5 結 論

筆者提出了一種基于小生境的神經網絡集成算法，用于提高神經網絡集成的泛化能力.所提方法集合了負相關學習和進化算法，促進了集成中個體網絡之間的交互性和合作性.此外，引入了一種基于共享適應度的小生境技術，用于維持網絡種群在進化過程中的多樣性，保證了神經網絡集成的差異度.實驗證明，所提方法具有很好的泛化能力.下一步研究工作主要是如何合適地設置負相關學習中懲罰項的參數來平衡神經網絡集成中的精確度和差異度，提高負相關學習的能力.

[1] 呂剛，郝平.基于神經網絡的數字驗證碼識別研究[J].浙江工業大學學報，2010，38(4):433-436.

[2] 張洪濤，計時鳴.基于改進的BP神經網絡鋼板表面缺陷分類算法研究[J].浙江工業大學學報，2010，38(4):388-390.

[3] HANSEN L K， SALAMON P. Neural network ensembles[J]. IEEE transactions on pattern analysis & machine intelligence，1990，12(10):993-1001.

[4] 傅向華，馮博琴，馬兆豐,等.一種異構神經網絡集成協同構造算法[J].小型微型計算機系統，2005，26(4):641-645.

[5] ISLAM M M， XIN Y， MURASE K. A constructive algorithm for training cooperative neural network ensembles[J]. IEEE transactions on neural networks，2003，14(4):820-834.

[6] BREIMAN L. Using iterated bagging to debias regressions[J]. Machine learning，2001，45(3):261-277.

[7] FREUND Y， SCHAPIRE R E. A decision theoretic generalization of on-fine learning and an application to boosting[J]. Journal of computer & system sciences，1997，55(1):119-139.

[8] LIU Y， YAO X. Ensemble learning via negative correlation[J]. Neural networks，1999，12(10):1399-1404.

[9] 謝錚桂，韋玉科，鐘少丹.基于負相關神經網絡集成算法及其應用的研究[J].計算機應用與軟件，2009，26(10):27-29.

[10] 周志華，陳世福.神經網絡集成[J].計算機學報，2002，25(1):1-8.

[11] LIU Y， YAO X. Simultaneous training of negatively correlated neural networks in an ensemble[J]. IEEE transactions on systems man & cybernetics part B cybernetics，1999，29(6):716-725.

[12] CHANDRA A， YAO X. Ensemble learning using multi-objective evolutionary algorithms[J]. Journal of mathematical modelling & algorithms，2006，5(4):417-445.

[13] EIBEN A E， MICHALEWICZ Z， SCHOENAUER M， et al. Parameter control in evolutionary algorithms[J]. IEEE transactions on evolutionary computation，1999，3(2):124-141.

[14] SARENI B， KRAHENBUHL L. Fitness sharing and niching methods revisited[J]. IEEE transactions on evolutionary computation，1998，2(3):97-106.

[15] 董輝，黃勝.二維排樣中小生境粒子群算法的研究與應用[J].浙江工業大學學報，2014，43(3):257-259.

[16] KROGH A， VEDELSBY J. Neural network ensembles， cross validation， and active learning[J]. Advances in neural information processing systems，1995，7:231-238.

[17] 崔挺，孫元章，徐箭,等.基于改進小生境遺傳算法的電力系統無功優化[J].中國電機工程學報，2011，31(19):43-50.

[18] KIM K J， CHO S B. Evolutionary ensemble of diverse artificial neural networks using speciation[J]. Neurocomputing，2008，71(7/8/9):1604-1618.

(責任編輯：劉 巖)

Negative correlation neural network ensemble based on a niching algorithm

SHENG Weiguo， SHAN Pengxiao

(College of Computer Science and Technology， Zhejiang University of Technology， Hangzhou 310023， China)

This paper proposes a niching evolutionary algorithm with negatively correlation learning (NCL) for training neural network (NN) ensemble. The proposed algorithm combining NCL with evolutionary algorithm trains simultaneously the NN individuals in the ensemble, which not only can create the diversity among the NN individuals, but also helps to promote the interaction and collaboration among the NN individuals. In addition, an improved niching method is introduced for preserving the diversity of population during training, thus ensure the diversity of the NN ensemble. The proposed algorithm is evaluated on six classification problems and compared with related ensemble learning algorithms. The experimental results show that the proposed algorithm can be used to design a satisfactory NN ensemble.

neural network; ensemble learning; NCL; niching; evolutionary algorithm

2016-03-11

國家自然科學基金資助項目(61573316)；浙江省自然科學基金資助項目(LY15F020032)

盛偉國(1977—)，男，浙江溫州人，教授，博士，研究方向為智能算法和數據挖掘，E-mail：wsheng@zjut.edu.cn.

TP391

A

1006-4303(2016)05-0482-05