DE-ELM-SSC+半監督分類算法*

龐 俊，黃 恒，張 壽，舒智梁，趙宇海

1.武漢科技大學計算機科學與技術學院，武漢430070

2.智能信息處理與實時工業系統湖北省重點實驗室，武漢430070

3.東北大學計算機科學與工程學院，沈陽110169

1 引言

演化算法（evolutionary algorithms，EA）是一類啟發式優化算法，通過變異繁殖和優勢選擇模擬自然的演化，能有效解決全局搜索優化問題[1-2]。目前，演化算法和分析方法的結合是機器學習領域的一個研究熱點[3-5]。文獻[3]采用演化算法和決策樹算法相結合，優化了生成的股票選擇模型。文獻[4]將社交網絡表示為一個無加權的無向圖，并使用不同節點的自適應算法從節點角度分析社交網絡的演化，提升了預測性能。

作為一種基于種群迭代的演化算法，差分進化算法通過個體的變異、交叉和選擇，使種群向更好的方向進化，具有簡單易用、魯棒性高和較強全局尋優能力等優點[6-7]。此外，針對大多數數值函數的優化問題，DE（differential evolution）算法在收斂速度和穩定性方面均優于其他演化算法[8-9]。因此，本文研究將DE與基于ELM的半監督分類算法相結合，優化ELM的網絡參數，提高算法性能。該問題的研究剛剛起步，已報道的相關工作很少。文獻[10]采用協同訓練（tri-training）技術實現了多個ELM（extreme learning machine）基分類器的協同訓練，然后采用標準的DE算法進行優化，得到了一種半監督分類算法Tri-DE-ELM（tritraining-DE-ELM）；雖然分類準確率有提高，但是分類準確率尚不夠高，不能完全滿足市場決策的需求。

針對上述問題，本文提出了一種基于DE和ELM的半監督分類方法（semi-supervised classification algorithm based on DE and ELM，DE-ELM-SSC），選擇適合目標數據集的差分進化策略，實現了分類準確率的提高。由于不同種類的進化策略一般適宜不同函數特征的應用場景[6]（例如：單峰函數適合采用de/best/1策略，多峰函數適合采用de/rand/1策略），且不同數據集有可能具有不同的函數特征，因此針對不同數據集，宜采用與數據集特征相適應的進化策略，以增強ELM網絡參數優化效果。DE-ELM-SSC的簡要步驟是：首先于預處理階段針對目標數據集離線選出最優進化策略：以均方根誤差（root mean square error，RMSE）為評價標準，從de/rand/1、de/best/1、de/best/2這3種具有代表性的進化策略中選出最優的策略；然后，將上一步選出的最優進化策略應用于DE算法，從而達到優化ELM網絡參數的目的；最后，將優化后的ELM作為基分類器，與Tri-training技術[11]相融合，生成半監督分類預測模型。DE-ELM-SSC和Tri-DE-ELM均采用了DE和協同訓練技術，分別優化了ELM網絡參數和實現了半監督分類，但是DE-ELM-SSC從多種典型差分進化策略中選擇出最適合目標數據集的策略，用于差分進化，獲得了比Tri-DE-ELM更強的網絡參數優化能力。

雖然通過使用策略選擇技術，DE-ELM-SSC算法獲得了比Tri-DE-ELM算法更高的分類準確率。但仍存在不足：固定縮放因子F值為1。首先，“1”超出了F取值的經驗范圍。根據文獻[12]的研究，一般情況下，F的最佳取值范圍為[0.2，0.9]；但當優化問題含有10個以上變量時，F的最佳取值范圍為[0.2，0.6]。其次，縮放因子應當能自適應調整?？s放因子對差分進化算法的優化能力有較大影響：如果縮放因子過小，存在降低種群多樣性和容易導致早熟收斂的問題；反之，種群迭代后期容易在最優解附近徘徊，導致搜索速度慢，求解精度低。為了達到較為理想的效果，縮放因子應采用自動調整的方式進行取值。

針對上述不足，本文采用縮放因子自適應方法，在差分進化算法種群迭代過程中，調整縮放因子的取值，從而加快收斂速度并提高網絡參數的尋優能力。不失一般性，本文采用了文獻[13]提出的一種慣性策略方法，并優化了自適應函數，實現了縮放因子自適應，從而得到了DE-ELM-SSC的一種改進算法DE-ELMSSC+。原慣性策略方法基本思想是：為了保持種群多樣性從而有利于全局搜索，在種群迭代初期使F取較大值；為了利于局部搜索并提高收斂速度，種群迭代后期F取較小值；迭代過程中，F取值線性逐代縮小。為取得更好的尋優效果，本文將迭代過程中的F取值按非線性方式逐代縮?。簽榱烁玫乇３址N群多樣性，種群迭代初期，F取值縮小速度比線性的慢；為了更快地收斂，種群迭代后期，F取值縮小速度比線性的快（詳情參見第4章），與DE-ELM-SSC方法相比，DE-ELM-SSC+算法任意選取并改進一種現有縮放因子自適應方法，進一步增強算法網絡參數的優化能力。本文提出的算法經擴展，可以解決多分類問題。

本文的主要貢獻如下所示：

（1）提出了一種基于DE和ELM的半監督分類方法DE-ELM-SSC。針對不同目標數據集，選擇合適的差分進化策略，優化了ELM的網絡參數。

（2）采用非線性方法改進現有的一種基于慣性策略的縮放因子自適應方法，進而優化了DE-ELMSSC算法。并分析了策略選擇、DE-ELM-SSC算法和改進的DE-ELM-SSC算法的關鍵步驟的時間復雜度。

（3）在5個UCI標準真實數據集上進行了大量的實驗，驗證了本文提出方法的有效性。

2 相關工作

2.1 差分進化算法

差分進化算法是由Storn和Price[8]于1995年提出的一種演化算法，被認為是最有效的演化算法之一。DE算法的數學問題可以形式化描述為：minf(x),x=[x1,x2,…,xd],pj≤xj≤qj，其中j=1,2,…,d，d是解空間維數；pj和qj分別表示變量x第j維的上界和下界。差分進化算法是基于種群迭代的隨機搜索算法，其基本思想[6]是通過種群個體的變異、交叉和選擇，使種群向更好的方向進化，從而逼近問題最優解。

為適應不同類型的優化問題，Price和Storn先后提出了10種不同策略差分進化算法[14]。由于出色的尋優能力，差分進化算法已成功應用到許多科學和工程領域[15-17]。縮放因子是用于控制變異過程中差異矢量的縮放程度，在差分進化算法中有至關重要的作用。于是，大量關于縮放因子自適應的方法被提出，產生了許多DE算法的變體[18-19]。本文根據目標數據集，從de/rand/1、de/best/1和de/best/2這3種具有代表性的策略中進行策略選擇。此外，不失一般性，選擇了一種慣性策略方法實現縮放因子自適應，并且通過非線性方法對其進行了改進。

2.2 基于超限學習機的半監督分類

超限學習機[20]是Huang等人提出的一種單隱層前饋神經網絡，通過隨機初始化輸入層到隱層神經元的輸入權重和隱層偏置，采用最小二乘法求解隱層神經元到輸出節點之間的輸出權重，實現全局逼近。其數學模型可以表示為：j=1,2,…,N。wi表示輸入層到第i個隱層節點的輸入權重，bi表示第i個隱含節點的偏置，βi表示第i個隱含節點的輸出權重。相對于采用梯度下降迭代調整網絡權值參數的傳統神經網絡算法，由于不需要對神經元網絡參數進行調優，超限學習機具有學習速度快的特點[21-22]。原始超限學習機[20]為解決有監督學習問題而設計，不適合處理半監督學習問題。因此基于超限學習機的半監督分類算法應運而生[23-28]。

現有基于超限學習機的半監督分類方法根據實現方式的不同主要分為兩類：基于圖的方法[23-27]和基于差異化協同訓練方法[10,28]。第一類方法通過構造圖模型（將樣本作為頂點），計算頂點之間的相似度，用有標簽的樣本信息預測無標簽樣本的信息，從而實現基于ELM的半監督分類。文獻[24]提出了SSELM（semi-supervised ELM）算法，通過構造圖的拉普拉斯正則化來解決多分類問題。雖然SS-ELM能利用無標簽數據輔助分類，但忽略了無標簽數據間的成對約束。因此，文獻[25]實現了一種基于ELM的流形和成對約束正則化的半監督分類。文獻[26]針對SS-ELM對異常值敏感的問題，提出了RSS-ELM（robust SS-ELM）算法，采用非凸平方損失函數增強算法的魯棒性。文獻[27]通過結合SS-ELM方法與ZGS（zero-gradient-sum）分布式優化策略，提出了DSS-ELM（distributed SS-ELM）算法，解決了時變通信網絡中分布式的半監督學習問題。第二類方法通過有標簽數據訓練多個ELM基分類器對無標簽數據進行標記，將置信度高的無標簽數據加入到有標簽數據中擴大有標簽數據集。文獻[28]通過co-training方法從無標簽數據中獲得置信度高的數據并打上標簽，逐步擴大已標記的訓練集，從而實現ELM的半監督分類。雖然方法比較簡單，但需要兩個視圖充分且條件獨立。文獻[10]提出了一種基于協同訓練、差分進化與ELM的半監督分類方法（Tri-DE-ELM），解決半監督分類問題。Tri-DE-ELM先采用差分進化方法改進ELM，達到優化ELM算法中網絡參數隨機取值的目的；然后將改進后的ELM算法作為基分類器，采用協同訓練技術，實現了半監督分類算法。Tri-DE-ELM是目前最新的將演化計算和基于ELM的半監督分類相結合的算法，取得了較高的分類準確率。但是其分類準確率尚不夠高，不能完全滿足市場決策的需求。第一類方法適用于相似特征的數據點趨向于在同一個類別內的情況；第二類方法適用于數據特征具有天然的子集劃分的情況[29]。Tri-DEELM是第二類方法，也是研究演化計算和基于ELM的半監督分類算法結合的最新方法。本文提出的方法雖然與Tri-DE-ELM都使用了DE和Tri-training技術，但是本文采用了策略選擇和改進的縮放因子自適應算法來優化ELM算法的隨機網絡參數，從而進一步提高了算法的分類準確率。

3 DE-ELM-SSC算法

3.1 算法概述

DE-ELM-SSC首先進行預處理，選擇差分進化策略；然后將選出的策略應用于標準的DE算法，增強對ELM網絡參數優化效果，接著無縫融合Tritraining算法實現3個基分類器的協同訓練，構造半監督分類預測模型。其算法概述如圖1所示。

DE-ELM-SSC算法包含兩個階段：（1）預處理階段，選擇差分進化策略；（2）訓練階段，構建預測模型（測試階段因過程類似而未進行介紹）。預處理階段針對給定數據集，從de/rand/1、de/best/1和de/best/2進化策略中選出與數據集相適應的最優策略，主要包括兩步：獲取有標簽訓練數據集L、驗證數據集V和計算不同策略的均方根誤差與策略選中次數。第一步采用隨機采樣的方法將給定數據集中的有標簽數據集D均分成有標簽訓練數據集L和驗證數據集V。第二步采用均方根誤差的值作為不同策略在數據集上的性能評價指標，在訓練數據集L上分別訓練采用de/rand/1、de/best/1和de/best/2差分進化策略的ELM模型；然后，分別用獲得的3個模型在驗證數據集V上進行標簽預測，通過與驗證數據集V的真實標簽比較，計算各模型在驗證數據集的均方根誤差。均方根誤差值越小，性能就越好，獲得均方根誤差最小的策略被選中次數加1。通過125次獨立重復選擇實驗（為了實驗結果穩定，進行了125次實驗）將選中次數最多的策略作為最終的進化策略并輸出（詳情見3.2節）。

訓練階段基于Tri-training思想，首先將前一階段選出的最優進化策略用于差分進化算法，然后用該差分進化算法優化ELM，接著以優化后的ELM（extreme learning machine based on strategy selection and differential evolution，SS-DE-ELM）為基分類器生成半監督分類預測模型。簡言之，首先通過重采樣從有標簽數據L采集3個子數據集，并分別訓練出3個基分類器（SS-DE-ELM）；然后通過給定數據集中的無標簽數據U迭代更新基分類器，當達到迭代停止條件時終止迭代，得到由3個穩定的基分類器構成的預測模型（具體步驟見3.3節）。

Fig.1 Overview of DE-ELM-SSC algorithm圖1 DE-ELM-SSC算法概述

3.2 策略選擇

策略選擇（strategy selection，SS）旨在從多種差分進化策略中選出適合已知數據集的策略。其基本思想是：由于不同策略有不同的使用場景，因此采用常用的均方根誤差作為評價指標（均方根誤差值越小，策略優化的性能越好），進行進化策略的選擇。具體而言，每次實驗計算并比較不同策略的均方根誤差，其中均方根誤差值最小的策略是當前實驗的最優策略。通過多次獨立實驗，統計各策略被選中次數，獲得被選中次數最多的策略，即最終所求的目標策略。若存在兩種策略被選中次數相同且同為最大值的情況，則選擇均方根誤差總和最小的策略。其算法偽代碼如算法1所示。

算法1策略選擇

首先獲取驗證數據集V和有標簽訓練數據集L：采用隨機取樣的方法從有標簽數據集D中抽取1/2數量的樣本組成V，剩余樣本構成L（步驟1）；然后，在有標簽訓練數據集L上，訓練3個分別采用de/rand/1、de/best/1和de/best/2差分進化策略的DE優化后的ELM模型；接下來，用訓練得到的3個模型在驗證數據集上進行計算，獲得預測結果；計算預測結果與驗證數據集真實標簽結果的均方根誤差，分別統計采用3種不同策略的模型在驗證數據集上的均方根誤差，將均方根誤差最小的策略的被選中次數Cj（j=1,2或3）增加1次（C1、C2和C3分別表示de/rand/1、de/best/1和de/best/2被選中的次數），循環125次（設置1 000、500、250、125、64和32等不同次數進行實驗，結果表明當次數在125及以上時結果比較穩定，因此進行了125次實驗），得到各策略的均方根誤差總和為Sumj（j=1,2或3）（步驟2～步驟8）。如果Cj是被選中次數中唯一的最大值，則返回Cj對應的策略作為輸出（步驟9）。如果Cj和Ck同時是被選中次數的最大值，則比較它們的均方根誤差總和Sumj與Sumk，輸出其中較小者對應的策略（步驟10）。由于總次數125不能被3整除，因此不存在C1、C2和C3同時取最大值的情況。此外由于神經元網絡的參數是隨機生成的，并且均方根誤差的總和可計算到小數點后10位，因此Sumj=Sumk（j≠k）取值相同的概率趨近于0（SS算法的示意圖如圖2所示）。

例1已知一個有標簽數據集D，從D中隨機抽取一半數據V作為驗證數據集，剩下數據作為有標簽訓練數據集L，使用數據集L分別訓練采用de/rand/1、de/best/1和de/best/2這3種進化策略的DE-ELM算法，獲得3個預測模型H1、H2和H3。然后分別計算H1、H2和H3在驗證數據集V上的均方根誤差R1、R2和R3。假設R1=min{R1,R2,R3}，則R1對應的進化策略de/rand/1被選擇。如此重復125次，假設策略de/rand/1被選擇次數為100次（即唯一的最大值），那么最終被選擇的進化策略是de/rand/1。假設策略de/rand/1與de/best/1被選擇次數都是60次（即同時為最大值），且de/rand/1的均方根誤差總和小于de/best/1的均方根誤差總和，那么最終被選擇的進化策略是de/rand/1。

Fig.2 Illustration diagram of strategy selection圖2 策略選擇示意圖

接下來分析策略選擇算法關鍵步驟的時間復雜度。策略選擇包含兩大關鍵步驟：使用傳統ELM算法計算輸出權重β和使用DE算法優化ELM網絡參數。對于傳統ELM算法計算輸出權重β，其時間復雜度為O(l3d+Nl2d+Nlmd+d)[30]。其中，l表示隱層神經元個數，d是輸入樣本向量的維度，N為給定訓練樣本的數量，m表示樣本類標簽向量的維度。對于第二大關鍵步驟，設種群規模大小為N2，最大迭代次數為G。使用DE算法優化ELM網絡參數需要經過多次迭代，其中1次迭代又包含3個關鍵步驟：（1）對種群所有個體進行變異產生新個體，其時間復雜度為O(N2(dl+l))[31]；（2）對所有變異的個體和與之對應的當前個體進行交叉獲得新的個體，其時間復雜度為O(N2(dl+l))[31]；（3）計算所有交叉后獲得的新個體在ELM算法中的輸出權重的范數和在訓練數據集上的RMSE，并在交叉后獲得的新個體和與之對應的當前個體之間進行選擇；將選擇結果作為下一代個體，從而得到下一代種群。根據策略選擇算法，容易分析出：單個個體在ELM算法中獲得輸出權重范數的時間復雜度為O(l3d+Nl2d+Nlmd+d+lm)，單個個體在訓練數據集上RMSE的計算時間復雜度為O(Nm)，步驟3的時間復雜度為O(N2(l3d+Nl2d+Nlmd+d+lm+Nm))。此外，最壞情況下，需要迭代G次。則使用DE算法優化ELM網絡參數的時間復雜度為O(GN2(l3d+Nl2d+l(Nmd+m+2d+2)+Nm+d))，可簡化為O(GN2(l3d+Nl2d+l(Nmd+m+d+1)+Nm+d))。

3.3 算法內容描述

本節采用Tri-training對SS-DE-ELM進行協同訓練得到DE-ELM-SSC算法。其基本思想是：首先根據已知有標簽數據集分別計算de/rand/1、de/best/1、de/best/2對應的RMSE，實現進化策略的選擇；然后通過重采樣的方法從有標簽數據集獲取3個子集訓練，并以SS-DE-ELM為基分類器，通過Tri-training算法構造由3個穩定分類器組成的預測模型。DEELM-SSC算法的偽代碼如算法2所示。

算法2DE-ELM-SSC算法

首先，根據算法1從de/rand/1、de/best/1和de/best/2策略中選出較為合適的策略C（步驟1），使用策略選擇后的DE算法優化ELM，獲得使用策略C的SS-DE-ELM算法，簡稱H（步驟2）。然后，從有標簽訓練數據重采樣得到3個子集L1′、L2′和L3′，并分別在L1′、L2′和L3′上使用算法H學習得到3個不同的基分類器H1、H2和H3（步驟3、步驟4）。接著，以H1為主分類器，采用輔分類器H2和H3預測無標簽數據集U的標簽。將H2和H3模型預測結果相同的標簽作為置信度高的標簽，并打上標簽。將具有置信度高的標簽樣本組成數據集L1，同時使用MeasureError(H2&H3)計算H2和H3模型在L上的分類錯誤率（在不引起歧義的前提下，下文簡稱為分類錯誤率）。MeasureError(H2&H3)=(H2與H3在L上預測結果相同且同時預測錯誤的樣本數量)/(H2與H3在L上預測結果相同的樣本數量)（預測錯誤的樣本數量是指預測的標簽類別與真實的標簽類別不同的樣本的數量）。為了保證引入的高置信度標簽的可靠性，分類錯誤率初始值統一設置為0.5。若當前分類錯誤率比上一輪的小，則判定需要用L∪L1對主分類器H1進行更新；否則，則判定不需要。類似地，依次以H2、H3為主分類器進行處理。最后，對需要更新的基分類器進行更新，當通過分類錯誤率判定3個基分類器都不再需要更新時，認定Tri-training算法獲得由3個穩定基分類器組成的預測模型，停止循環；否則，繼續使用3個基分類器利用無標簽數據進行迭代更新（步驟5～步驟13）。其中，步驟7～步驟11是用于遍歷更新3個基分類器對應的置信度高的無標簽數據集，進行判斷和記錄各基分類器是否需要更新。并根據記錄信息對需要更新的分類器進行更新（步驟12）。最后，當所有基分類器不再更新（即達到穩定）時，獲得基分類器的輸出權重（步驟14）。

下文分析DE-ELM-SSC算法關鍵步驟的時間復雜度。DE-ELM-SSC算法主要包含3個關鍵步驟：（1）利用兩個輔助分類器從大小為N3的無標簽數據集中獲得高置信度數據集。根據DE-ELM-SSC算法，可知計算兩個輔助分類器模型的時間復雜度為O(2GN2(l3d+Nl2d+l(Nmd+m+d+1)+Nm+d))，計算高置信度數據的時間復雜度為O(2N3lmd)。因此，該步驟的時間復雜度為O(2GN2(l3d+Nl2d+l(Nmd+m+d+1)+Nm+d)+2N3lmd)。（2）使用MeasureError()函數計算輔助分類器的分類錯誤率，并與上一輪計算得到的分類錯誤率進行比較，從而判斷是否需要用擴展后的數據集對主分類器進行更新。因為通過兩個輔助分類器判斷其分類錯誤率，因此該步驟時間復雜度為O(2GN2(l3d+Nl2d+l(Nmd+m+d+1)+Nm+d)+2Nlmd)。（3）若需要對分類器更新，則擴大后的數據集大小為N+N4（N4表示主分類器對應的高置信度數據集的大?。?；然后利用擴大后的數據集對分類器進行更新。經分析，該步驟時間復雜度為O(GN2(l3d+(N+N4)l2d+l((N+N4)md+m+d+1)+(N+N4)m+d))。

4 DE-ELM-SSC+算法

縮放因子F(F∈[0,2])是DE算法中用于控制差異矢量的縮放程度，對算法收斂速度和求解精度有重要影響[8]。為了取得更優的優化效果，縮放因子取值應在迭代演化過程中變化[32]。不失一般性，本文采用了文獻[13]提出的一種慣性策略自適應方法，并使用非線性方法進行改進：為了更好地保持種群多樣性，種群迭代初期，F取值縮小速度比線性的慢；為了更快地收斂，種群迭代后期，F取值縮小速度比線性的快，獲得一種非線性的縮放因子自適應方法。將該縮放因子自適應方法應用于DE-ELM-SSC中，提出一種改進的DE-ELM-SSC算法DE-ELM-SSC+，提高了DE-ELM-SSC算法性能。本文通過差分進化策略選擇、縮放因子自適應調整和Tri-training技術融合等步驟實現了DE-ELM-SSC+算法。由于差分進化策略選擇與Tri-training技術融合等步驟與DE-ELM-SSC相同，本章主要介紹縮放因子的自適應調整。

文獻[13]提出的慣性策略方法基本思想如下：為了保持種群的多樣性從而有利于全局搜索，在種群迭代初期使F取較大值；為了利于局部搜索并提高收斂速度，種群迭代后期F取較小值。迭代過程中，F取值按公式逐代縮小。Fmax為初始第0代時的縮放因子，Fmin為最后一代的縮放因子，t為當前種群進化到的代數，T是種群進化的最大代數。本文通過非線性方法改進迭代過程中F的取值，使其按以下公式逐代縮?。?/p>

根據假設條件，種群處于第0代個體時（即t=0），縮放因子取值為Fmax，可得：

并且根據假設條件，種群處于第T代個體時（即t=T），縮放因子取值為Fmin，可得：

等式（2）和等式（3）組成方程組（Ⅰ）：

求解方程組（Ⅰ），可得：

將方程組（Ⅰ）的計算結果代入等式（1），化簡后得到改進后的自適應函數：

此外，由于Fmax和Fmin的取值將影響算法性能，因此本文設計了實驗，尋找不同數據集的Fmax和Fmin的次優解。其基本思想是：首先確定F的取值范圍，然后在取值范圍內，通過驗證數據集分類準確率確定不同數據集的次優Fmax和Fmin。因為F∈[0,2]且F＞1的情況很少出現[33]，所以本文將F取值范圍設為[0,1]。首先將連續型變量F離散化，得到F的離散值取值范圍{0.1,0.2,…,1.0}，然后在此范圍內求解Fmax和Fmin的次優解：首先Fmin和Fmax在{0.1,0.2,…,1.0}中分別取值（Fmin≤Fmax），然后比較每組Fmin與Fmax條件下的訓練模型在驗證數據集上的準確率；準確率最高的組合相應的Fmin與Fmax為尋找的次優解。縮放因子取值固定，是自適應方法的一種特殊情況，即Fmin=Fmax。實驗結果參見本文5.5節。

采用改進后的縮放因子自適應方法對SS-DEELM基分類器進行優化，相應算法的偽代碼如算法3所示。

算法3采用縮放因子自適應的SS-DE-ELM算法

首先采用隨機取樣的方法從有標簽數據集D中抽取1/2數量的樣本組成驗證數據集V，剩余樣本構成有標簽訓練數據集L（步驟1）；然后隨機生成由NP個個體組成的種群（一個個體表示神經元網絡參數的一種隨機取值），并計算每個個體的輸出權重和均方根誤差（步驟2、步驟3）；接著，在種群迭代更新之前，先根據公式計算當代縮放因子的值。再根據差分進化策略st進行變異、交叉和選擇操作，種群不斷迭代更新種群個體，直到到達種群最大迭代次數（步驟4～步驟9）。變異是指當前種群突變，下文以個體θi,g采用de/rand/1策略變異獲得個體Vi,g為例講述其過程：首先從種群中隨機選擇兩個不同個體進行減法向量運算獲取兩者之間的差異向量，并用縮放因子對差異向量進行放大；然后隨機從種群中選擇第三個個體加上放大后的差異向量，獲得變異后的個體Vi,g。交叉是為了增加干擾參數向量的多樣性。對于N維個體，通過N個隨機生成的0到1之間的隨機數與交叉因子CR比較，決定交叉后新生成的個體ui,g的N個維度的取值。若第i維的隨機數小于或等于CR，則將突變個體Vi,g的第i維賦值給ui,g的第i維；反之，將個體θi,g的第i維賦值給ui,g的第i維。選擇操作是在當前個體θi,g與ui,g之間選擇誰成為下一代個體。種群中交叉的個體ui,g能否成為種群的下一代，由個體的輸出權重的范數與RMSE決定。交叉個體的輸出權重范數比當代個體的輸出權重范數小，或者交叉個體的RMSE取值更小，交叉的個體就作為種群的下一代個體。否則，當前個體保持不變作為下一代種群的個體（不同差分進化策略st變異的詳細過程參考文獻[6]）。最后返回種群的最優個體和該個體對應的輸出權重。最優個體是優化后的ELM算法的輸入權重和偏置參數（步驟10）。

例2對于給定的有標簽數據集D，縮放因子最大值Fmax為0.6，最小值Fmin為0.2，神經元個數為30，種群大小為20，最大迭代次數為20。假設θ是第10代種群G中的某個個體，通過θ計算得到的網絡輸出權重的范數||βθ||為0.8，均方根誤差為0.9。根據公式計算當代縮放因子F=0.6-(0.6-0.2)/(e-1)×(e10/20-1)≈0.448 9。θ經過變異和交叉產生個體u，然后進行選擇產生下一代個體。若通過個體u計算得到的網絡輸出權值的范數||βu|||為1.1，均方根誤差為1.0，則個體θ保持不變保留到下一代（1.1>0.8且1.0>0.9）。種群G中所有個體都進行變異、交叉和選擇操作后，種群進化成為第11代種群，再重新計算縮放因子F=0.6-(0.6-0.2)/(e-1)×(e11/20-1)≈0.429 3，并重復變異、交叉和選擇操作，更新種群直至滿足迭代停止條件。最后返回種群G中的最優個體和與之對應的輸出權重。

DE-ELM-SSC+的優點如下所示：（1）策略選擇步驟從3種策略中選擇一個性能較優且穩定的優化策略，使得網絡參數的性能更優，從而使通過該網絡參數訓練得到的分類器性能更好；（2）改進的縮放因子自適應方法改善縮放因子取值固定的問題，優化差分進化對網絡參數的局部和全局搜索，加速迭代并提高網絡參數的搜索精度。由于DE-ELM-SSC+比DE-ELM-SSC僅多了計算縮放因子的步驟，且依等式（4）可知，縮放因子計算的時間復雜度是O(1)；因此DE-ELM-SSC+的關鍵步驟和其時間負責度與DEELM-SSC的相同。

5 實驗與分析

本章首先介紹了實驗數據集和實驗環境，然后分別驗證了本文提出算法的有效性。接著比較了各算法在不同比例的有標簽數據下的準確率，并討論了有標簽數據量占比對分類準確率的影響，以及探索了不同數據集上縮放因子最大值Fmax與最小值Fmin的次優取值。最后研究了隱藏神經元個數對算法性能的影響。

5.1 數據集和實驗環境

采用UCI數據集上的5個真實數據集進行實驗：Australian Credit Approval（Australian）、Breast Cancer Wisconsin（Cancer）、Congressional Voting Records（Vote）、Wisconsin Diagnostic Breast Cander（Wdbc）和Mushroom（統計信息如表1所示）。表1中，L和U分別表示有標簽訓練數據集和無標簽樣本數據集，V和T分別表示驗證和測試數據集，S表示所有數據的總和。本文實驗代碼采用Python編程語言，在如下配置的單機上運行：3.5 GHz CPU、8 GB內存、Windows7 64位操作系統和Python3.6.3。以最新的Tri-DE-ELM為baseline方法，并采用準確率（Accuracy）作為性能評價標準。Accuracy=（預測正確的樣本數）/（預測的總樣本數）。每次實驗運行50次，報道平均實驗結果。

Table 1 Datasets statistics表1 數據集統計信息

本文實驗中測試數據占總數據的25%，訓練數據占總數據的75%。訓練數據由60%的有標簽和40%的無標簽數據U組成。隨機抽取有標簽數據D的50%作為驗證數據集V，剩下50%作為有標簽訓練數據集L。本文所有實驗中，如無特殊說明，算法參數均采用如下默認設置：差分進化的種群大小NP為20，變異因子CR為0.8，種群最大迭代次數Gmax為20。各算法在5個數據集上的神經元個數nh與縮放因子F的取值如表2所示。

Table 2 Number of neurons nh and scaling factor F表2 神經元個數nh 和縮放因子F

5.2 DE-ELM-SSC性能驗證

文獻[10]已在相同真實數據集上進行了大量實驗，驗證了Tri-DE-ELM算法的分類準確率高于ELM、DE改進后的DE-ELM、Tri-training優化后的Tri-ELM算法。因此為驗證DE-ELM-SSC的有效性，比較了DE-ELM-SSC與Tri-DE-ELM算法的分類準確率。測試數據集的分類準確率結果如表3所示。從表3可知，在Wdbc、Mushroom和Australian數據集上，DE-ELM-SSC的分類準確率大于Tri-DE-ELM的；在Vote和Cancer數據集上，DE-ELM-SSC的分類準確率等于Tri-DE-ELM的。主要因為DE-ELM-SSC算法在Wdbc、Mushroom和Australian數據集上選擇了與數據集自身相適應的進化策略de/rand/1、de/best/1和de/best/2；這些策略應用于ELM算法后，增強了ELM算法的尋優能力，進一步提高了基分類器的分類準確率，從而使最終算法取得了更高的分類正確率。由于DE-ELM-SSC在Vote和Cancer數據集上選出的進化策略與Tri-DE-ELM的一致（均為de/rand/1），因此它們的分類準確率相同。總之，選擇適合不同目標數據集的進化策略，能增強網絡參數尋優效果，實現分類性能的提升。

Table 3 Comparison of accuracy between Tri-DE-ELM and DE-ELM-SSC表3 Tri-DE-ELM與DE-ELM-SSC的準確率比較

5.3 DE-ELM-SSC+性能驗證

本節在5個真實數據集上比較了DE-ELM-SSC與DE-ELM-SSC+在測試數據集的分類準確率和訓練時間。實驗結果如表4所示：與DE-ELM-SSC算法相比，DE-ELM-SSC+的訓練時間更少，分類準確率更高。因為它采用了改進的自適應縮放因子策略，在種群迭代過程中既保持了初期種群的多樣性，又加快了后期的收斂速度和搜索精度，進一步提高了基分類器SS-DE-ELM的分類準確率，從而提高了協同訓練的分類準確率。因為策略選擇在預處理階段離線進行，所以表4中DE-ELM-SSC算法與DE-ELMSSC+算法的訓練時間是從訓練基分類器到構建分類預測模型的時間，而未包含策略選擇所用時間。

Table 4 Strategy and classification accuracy comparison of two algorithms表4 兩種算法選擇策略和分類準確率比較

5.4 不同比例有標簽樣本對分類性能的影響

為檢測不同比例有標簽樣本對提出算法的分類準確率的影響，從訓練數據集中隨機抽取30%作為驗證數據集V，剩下70%數據作為訓練數據L∪U。分別隨機設置L∪U中20%、40%、60%和80%的數據作為有標簽訓練數據L，其余數據作為無標簽訓練數據U。Tri-DE-ELM與DE-ELM-SSC+在測試數據集上的分類準確率結果如表5所示。

表5表明隨著有標簽樣本比例的增加，用于訓練模型的數據增加，模型能夠學到的信息越多，從訓練數據中得到的模型的分類性能越來越好。本文以Australian數據集為例，當有標簽數據為20%時，Tri-DE-ELM和DE-ELM-SSC+分類準確率分別為0.731 4和0.738 7；當有標簽數據為80%時，它們的分類準確率上漲到0.802 4和0.812 3。相同條件下，因為進行策略選擇和縮放因子自適應，DE-ELM-SSC+算法的準確率均高于Tri-DE-ELM。

5.5 Fmax 與Fmin 的求解

不失一般性，本節選擇Mushroom數據集進行實驗，說明求解Fmax與Fmin的過程。實驗結果如表6所示?！啊北硎緦腇min和Fmax取值組合不在討論范圍內。

表6表明縮放因子Fmax與Fmin的取值會對DE-ELM-SSC+分類準確率產生較大影響，不應固定為1。例如當Fmin=0.3，Fmax=0.5時，驗證數據集和測試數據集的分類準確率分別為0.978 4和0.976 7。顯然，其分類準確率大于固定F=1（即Fmin=Fmax=1.0）的0.944 7和0.945 6。由于當Fmin=0.3，Fmax=0.5時，驗證數據集上的分類準確率取得最大值0.978 4，因此對于Mushroom數據集，Fmin取值為0.3，Fmax取值為0.5。此時，DE-ELM-SSC+算法的分類準確率相對于Tri-DE-ELM算法有較大提升。其他數據集的Fmax與Fmin求解過程與此類似，不再一一闡述。

Table 5 Classification accuracy comparison on datasets with different labeled proportions表5 不同比例有標簽數據集上的分類準確率比較

Table 6 Classification accuracy comparison of different Fmax and Fmin表6 不同Fmax 和Fmin 的分類準確率比較

5.6 隱含層神經元個數性能評價

本節在Mushroom數據集上評估不同神經元個數對各算法分類準確率的影響。報道100次實驗的平均結果。其實驗結果如圖3和圖4所示。

Fig.3 Experimental results on training datasets with variable number of hidden neurons圖3 不同隱含層神經元個數測試集上的實驗結果

Fig.4 Experimental results on valid datasets with variable number of hidden neurons圖4 不同隱含層神經元個數驗證集上的實驗結果

圖3和圖4顯示：隨著神經元個數的增加，Tri-DE-ELM、DE-ELM-SSC和DE-ELM-SSC+的準確率先不斷增加，然后趨于穩定。當神經元個數在[5,38]范圍內時，由于算法訓練不充分，因此分類準確率隨著神經元個數的增加而增加。當神經元個數在[38,40]范圍內時，如果訓練充分，訓練和驗證準確率均趨于平穩。對于相同的隱層神經元個數，DE-ELM-SSC+算法分類準確率高于Tri-DE-ELM和DE-ELM-SSC算法。因為DE-ELM-SSC+采用了策略選擇和改進的縮放因子自適應技術。

6 結論

本文將差分進化演化算法與基于ELM的半監督分類方法相結合，提出了一種基于DE和ELM的方法DE-ELM-SSC，能有效處理半監督分類問題。針對不同差分進化策略適合不同數據特征數據集的特點，以均方根誤差為選擇標準，從多種典型策略中選出適合給定數據集的策略。并且，采用改進的縮放因子自適應方法對DE-ELM-SSC進行優化，得到DE-ELMSSC+方法。改進的非線性縮放因子自適應方法不但在差分進化的種群迭代初期保持了種群多樣性，而且在種群迭代后期達到了局部精細化搜索的目的，從而進一步提高了分類準確率和加快了模型訓練速度。5個真實數據集的大量實驗結果表明，與Tri-DEELM相比，DE-ELM-SSC+具有更高的分類準確率。