DE-ELM-SSC+半監(jiān)督分類算法*

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

1.武漢科技大學(xué)計算機科學(xué)與技術(shù)學(xué)院，武漢430070

2.智能信息處理與實時工業(yè)系統(tǒng)湖北省重點實驗室，武漢430070

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

1 引言

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

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

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

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

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

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

（1）提出了一種基于DE和ELM的半監(jiān)督分類方法DE-ELM-SSC。針對不同目標(biāo)數(shù)據(jù)集，選擇合適的差分進化策略，優(yōu)化了ELM的網(wǎng)絡(luò)參數(shù)。

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

（3）在5個UCI標(biāo)準(zhǔn)真實數(shù)據(jù)集上進行了大量的實驗，驗證了本文提出方法的有效性。

2 相關(guān)工作

2.1 差分進化算法

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

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

2.2 基于超限學(xué)習(xí)機的半監(jiān)督分類

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

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

3 DE-ELM-SSC算法

3.1 算法概述

DE-ELM-SSC首先進行預(yù)處理，選擇差分進化策略；然后將選出的策略應(yīng)用于標(biāo)準(zhǔn)的DE算法，增強對ELM網(wǎng)絡(luò)參數(shù)優(yōu)化效果，接著無縫融合Tritraining算法實現(xiàn)3個基分類器的協(xié)同訓(xùn)練，構(gòu)造半監(jiān)督分類預(yù)測模型。其算法概述如圖1所示。

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

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

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

3.2 策略選擇

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

算法1策略選擇

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

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

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

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

3.3 算法內(nèi)容描述

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

算法2DE-ELM-SSC算法

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

下文分析DE-ELM-SSC算法關(guān)鍵步驟的時間復(fù)雜度。DE-ELM-SSC算法主要包含3個關(guān)鍵步驟：（1）利用兩個輔助分類器從大小為N3的無標(biāo)簽數(shù)據(jù)集中獲得高置信度數(shù)據(jù)集。根據(jù)DE-ELM-SSC算法，可知計算兩個輔助分類器模型的時間復(fù)雜度為O(2GN2(l3d+Nl2d+l(Nmd+m+d+1)+Nm+d))，計算高置信度數(shù)據(jù)的時間復(fù)雜度為O(2N3lmd)。因此，該步驟的時間復(fù)雜度為O(2GN2(l3d+Nl2d+l(Nmd+m+d+1)+Nm+d)+2N3lmd)。（2）使用MeasureError()函數(shù)計算輔助分類器的分類錯誤率，并與上一輪計算得到的分類錯誤率進行比較，從而判斷是否需要用擴展后的數(shù)據(jù)集對主分類器進行更新。因為通過兩個輔助分類器判斷其分類錯誤率，因此該步驟時間復(fù)雜度為O(2GN2(l3d+Nl2d+l(Nmd+m+d+1)+Nm+d)+2Nlmd)。（3）若需要對分類器更新，則擴大后的數(shù)據(jù)集大小為N+N4（N4表示主分類器對應(yīng)的高置信度數(shù)據(jù)集的大?。蝗缓罄脭U大后的數(shù)據(jù)集對分類器進行更新。經(jīng)分析，該步驟時間復(fù)雜度為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]。為了取得更優(yōu)的優(yōu)化效果，縮放因子取值應(yīng)在迭代演化過程中變化[32]。不失一般性，本文采用了文獻[13]提出的一種慣性策略自適應(yīng)方法，并使用非線性方法進行改進：為了更好地保持種群多樣性，種群迭代初期，F(xiàn)取值縮小速度比線性的慢；為了更快地收斂，種群迭代后期，F(xiàn)取值縮小速度比線性的快，獲得一種非線性的縮放因子自適應(yīng)方法。將該縮放因子自適應(yīng)方法應(yīng)用于DE-ELM-SSC中，提出一種改進的DE-ELM-SSC算法DE-ELM-SSC+，提高了DE-ELM-SSC算法性能。本文通過差分進化策略選擇、縮放因子自適應(yīng)調(diào)整和Tri-training技術(shù)融合等步驟實現(xiàn)了DE-ELM-SSC+算法。由于差分進化策略選擇與Tri-training技術(shù)融合等步驟與DE-ELM-SSC相同，本章主要介紹縮放因子的自適應(yīng)調(diào)整。

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

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

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

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

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

將方程組（Ⅰ）的計算結(jié)果代入等式（1），化簡后得到改進后的自適應(yīng)函數(shù)：

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

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

算法3采用縮放因子自適應(yīng)的SS-DE-ELM算法

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

例2對于給定的有標(biāo)簽數(shù)據(jù)集D，縮放因子最大值Fmax為0.6，最小值Fmin為0.2，神經(jīng)元個數(shù)為30，種群大小為20，最大迭代次數(shù)為20。假設(shè)θ是第10代種群G中的某個個體，通過θ計算得到的網(wǎng)絡(luò)輸出權(quán)重的范數(shù)||βθ||為0.8，均方根誤差為0.9。根據(jù)公式計算當(dāng)代縮放因子F=0.6-(0.6-0.2)/(e-1)×(e10/20-1)≈0.448 9。θ經(jīng)過變異和交叉產(chǎn)生個體u，然后進行選擇產(chǎn)生下一代個體。若通過個體u計算得到的網(wǎng)絡(luò)輸出權(quán)值的范數(shù)||β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，并重復(fù)變異、交叉和選擇操作，更新種群直至滿足迭代停止條件。最后返回種群G中的最優(yōu)個體和與之對應(yīng)的輸出權(quán)重。

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

5 實驗與分析

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

5.1 數(shù)據(jù)集和實驗環(huán)境

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

Table 1 Datasets statistics表1 數(shù)據(jù)集統(tǒng)計信息

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

Table 2 Number of neurons nh and scaling factor F表2 神經(jīng)元個數(shù)nh 和縮放因子F

5.2 DE-ELM-SSC性能驗證

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

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

5.3 DE-ELM-SSC+性能驗證

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

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

5.4 不同比例有標(biāo)簽樣本對分類性能的影響

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

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

5.5 Fmax 與Fmin 的求解

不失一般性，本節(jié)選擇Mushroom數(shù)據(jù)集進行實驗，說明求解Fmax與Fmin的過程。實驗結(jié)果如表6所示?！啊北硎緦?yīng)的Fmin和Fmax取值組合不在討論范圍內(nèi)。

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

Table 5 Classification accuracy comparison on datasets with different labeled proportions表5 不同比例有標(biāo)簽數(shù)據(jù)集上的分類準(zhǔn)確率比較

Table 6 Classification accuracy comparison of different Fmax and Fmin表6 不同F(xiàn)max 和Fmin 的分類準(zhǔn)確率比較

5.6 隱含層神經(jīng)元個數(shù)性能評價

本節(jié)在Mushroom數(shù)據(jù)集上評估不同神經(jīng)元個數(shù)對各算法分類準(zhǔn)確率的影響。報道100次實驗的平均結(jié)果。其實驗結(jié)果如圖3和圖4所示。

Fig.3 Experimental results on training datasets with variable number of hidden neurons圖3 不同隱含層神經(jīng)元個數(shù)測試集上的實驗結(jié)果

Fig.4 Experimental results on valid datasets with variable number of hidden neurons圖4 不同隱含層神經(jīng)元個數(shù)驗證集上的實驗結(jié)果

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

6 結(jié)論

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