蔡 桓 陸克中 伍啟榮 吳定明

(深圳大學(xué)計算機(jī)與軟件學(xué)院 廣東深圳 518061)

在當(dāng)今的數(shù)字時代，數(shù)據(jù)起著至關(guān)重要的作用，它以驚人的速度增長，如何處理和分析這些數(shù)據(jù)變得越來越重要[1].與在靜態(tài)場景中構(gòu)建模型的批處理學(xué)習(xí)不同，在線學(xué)習(xí)面臨2個重大挑戰(zhàn):1)分類器必須在每個實(shí)例到達(dá)后立即進(jìn)行處理，而無需使用存儲或重新處理[2].2)數(shù)據(jù)流可能會發(fā)生概念漂移，即數(shù)據(jù)分布與輸入變量和輸出變量之間的關(guān)系可能會隨時間發(fā)生變化[3].因此，部署在非平穩(wěn)數(shù)據(jù)流中的分類器必須通過1次遍歷來學(xué)習(xí)，同時能適應(yīng)數(shù)據(jù)分布的動態(tài)變化.

近些年來，在處理概念漂移數(shù)據(jù)流分類問題上取得了很多研究成果.圍繞概念漂移的研究可以歸納為主動檢測[4-6]和被動適應(yīng)[7-8]2大類.主動檢測算法通過檢測分類器性能或數(shù)據(jù)流的特征分布來確定數(shù)據(jù)流的穩(wěn)定性，當(dāng)判斷發(fā)生概念漂移時觸發(fā)概念漂移處理機(jī)制來適應(yīng)新環(huán)境.被動適應(yīng)方法不去主動檢測是否發(fā)生概念漂移，而是通過不斷對數(shù)據(jù)或者模型進(jìn)行更新以適應(yīng)新環(huán)境，主要有塊學(xué)習(xí)、增量更新、遺忘因子機(jī)制和集成方法等.主動檢測方法通常具有更好的概念漂移適應(yīng)能力，但也往往具有更高的時間和空間復(fù)雜度.

隨著神經(jīng)網(wǎng)絡(luò)的迅速發(fā)展，研究人員已開始開發(fā)基于神經(jīng)網(wǎng)絡(luò)的數(shù)據(jù)流分類方法.由新加坡南洋理工大學(xué)Huang等人[9]提出的極限學(xué)習(xí)機(jī)(extreme learning machine, ELM)是一種具有單隱層的高效前饋神經(jīng)網(wǎng)絡(luò)，研究人員被廣泛吸引來開發(fā)ELM方法.ELM隨機(jī)選擇輸入層權(quán)重和隱含層偏差.一旦確定了輸入權(quán)重，就不會通過迭代進(jìn)行調(diào)整.因此，與傳統(tǒng)的神經(jīng)網(wǎng)絡(luò)相比，ELM具有學(xué)習(xí)時間短、泛化能力強(qiáng)的優(yōu)勢[10].而Liang等人[11]進(jìn)一步提出的在線順序極限學(xué)習(xí)機(jī)(online sequential extreme learning machine, OSELM)是一種增量學(xué)習(xí)算法，可滿足數(shù)據(jù)流分類的要求[12].該算法可以逐步更新分類模型而無需重新訓(xùn)練.由于OSELM相對于其他算法具有速度快、分類性能好的優(yōu)勢，基于OSELM算法進(jìn)行優(yōu)化成為數(shù)據(jù)流分類研究的一個重要方向，也產(chǎn)生了很多衍生算法[13-17].但OSELM算法也存在不足，比如只能處理漸進(jìn)的概念漂移，而無法適應(yīng)突然改變的概念[18].而大多數(shù)基于OSELM優(yōu)化的算法直接提前指定1個隱含層節(jié)點(diǎn)數(shù)且在不同數(shù)據(jù)集上保持固定，這很容易產(chǎn)生欠擬合或過擬合問題.也有學(xué)者將遺忘因子引入OSELM，但同樣提前指定1個固定的遺忘因子，導(dǎo)致分類器無法在數(shù)據(jù)流穩(wěn)定階段和概念漂移階段取得良好的平衡.此外，數(shù)據(jù)流往往存在噪音，而原始OSELM及大多數(shù)優(yōu)化算法沒有對噪音進(jìn)行有效區(qū)分，而是對每個新到達(dá)的實(shí)例都相同處理，因此分類決策邊界很容易被噪音(異常值)破壞.

針對上面提到的問題，以及在FROSELM(online sequential extreme learning machine based on regularization and forgetting factor)[19]和FGROSELM(online sequential extreme learning machine with generalized regularization and adaptive forgetting factor)[20]等算法的啟發(fā)下，本文提出了一種自適應(yīng)在線順序極限學(xué)習(xí)機(jī)(adaptive online sequential extreme learning machine, AOSELM)分類算法.AOSELM算法首先引入自適應(yīng)模型復(fù)雜度機(jī)制，在初始化階段可以自適應(yīng)確定出最佳隱含層節(jié)點(diǎn)數(shù)，并加入正則項(xiàng)，優(yōu)化模型復(fù)雜度.其次通過自適應(yīng)遺忘因子和概念漂移檢測機(jī)制，將概念漂移和遺忘因子結(jié)合，使分類模型在發(fā)生概念漂移時自動調(diào)小遺忘因子，而在數(shù)據(jù)流穩(wěn)定時自動調(diào)大遺忘因子，從而適應(yīng)數(shù)據(jù)流的動態(tài)變化.最后通過引入異常點(diǎn)檢測機(jī)制，增強(qiáng)模型抗噪音能力.

1 相關(guān)工作

本節(jié)我們將重點(diǎn)介紹OSELM和FROSELM這2種算法.為了簡單起見，2種算法都考慮用于2分類問題，即只有單個輸出節(jié)點(diǎn).

1.1 OSELM算法

在線順序極限學(xué)習(xí)機(jī)OSELM算法是由Liang等人[11]于2006年提出，該算法是Huang等人[9]提出的ELM算法的在線學(xué)習(xí)方法.算法分為初始化階段和在線學(xué)習(xí)階段2個階段.

(1)

Wi和bi分別為輸入權(quán)重和第i個隱含層偏置，而Y0=(y1,y2,…,yN0)T.根據(jù)廣義逆求解方法可計算得:

(2)

在線學(xué)習(xí)階段，數(shù)據(jù)流逐條被處理，無需保存歷史數(shù)據(jù).當(dāng)新實(shí)例(Xk+1,yk+1)到達(dá)時，記hk+1=(g(W1,b1,Xk+1)…g(WL,bL,Xk+1))，可計算得過渡矩陣P和輸出層權(quán)重β的更新:

(3)

(4)

從式(3)(4)可以看出，OSELM的輸出權(quán)重是根據(jù)最后一次迭代的結(jié)果和新到達(dá)的數(shù)據(jù)進(jìn)行遞歸更新的，一旦新數(shù)據(jù)被學(xué)習(xí)，就可以立即丟棄，符合在線學(xué)習(xí)處理方式的要求，因此該算法的計算開銷和內(nèi)存要求大大降低.OSELM具備速度快和泛化能力強(qiáng)的特點(diǎn)，并且可以增量更新模型.

1.2 FROSELM算法

具有遺忘機(jī)制的正則在線順序極限學(xué)習(xí)機(jī)FROSELM算法是由杜占龍等人[19]于2015年提出.該算法將遺忘因子(forgetting factor, FF)方法和正則化技術(shù)引入OSELM，根據(jù)實(shí)例的時間順序分別為每個樣本分配不同的權(quán)重.初始化階段過渡矩陣P0和輸出層權(quán)重β0分別為

(5)

(6)

其中,C為懲罰項(xiàng)系數(shù)，I為單位矩陣.在線學(xué)習(xí)階段過渡矩陣P和輸出層權(quán)重β的更新公式分別為

(7)

(8)

其中，λ為遺忘因子，當(dāng)λ=1且C=0時，F(xiàn)ROSELM退化為原始OSELM.FROSELM算法為最近的樣本分配較高的權(quán)重，而為舊的樣本分配較低的權(quán)重，以表示它們對學(xué)習(xí)模型的不同貢獻(xiàn)，因此使模型能夠適應(yīng)數(shù)據(jù)流的動態(tài)變化.

2 自適應(yīng)在線順序極限學(xué)習(xí)機(jī)算法

數(shù)據(jù)流的動態(tài)變化特點(diǎn)要求分類器能夠不斷地更新，以便更改分類器使其適應(yīng)當(dāng)前的數(shù)據(jù)分布.而概念漂移的發(fā)生使得不同時刻目標(biāo)概念與當(dāng)前特征的映射關(guān)系不斷變化，且是否發(fā)生概念漂移、概念漂移的位置以及概念漂移的類型均無法提前獲知.目前大多數(shù)算法都采用提前指定模型參數(shù)的方式進(jìn)行學(xué)習(xí)，比如對模型復(fù)雜度直接影響的隱含層節(jié)點(diǎn)數(shù)以及決定概念漂移適應(yīng)能力的遺忘因子等.這種做法使得分類模型只能在特定的數(shù)據(jù)集才能發(fā)揮較好的性能，因此，本文提出的AOSELM算法引入自適應(yīng)機(jī)制來增強(qiáng)模型的分類效果和概念漂移適應(yīng)能力，此外，還引入異常點(diǎn)檢測機(jī)制，增強(qiáng)模型抗噪音能力.本節(jié)將對AOSELM算法的基本思想及其實(shí)現(xiàn)過程進(jìn)行詳細(xì)介紹.

2.1 算法基本思想

現(xiàn)有的數(shù)據(jù)流分類算法大致可分為3種：1)大部分傳統(tǒng)算法是對數(shù)據(jù)流新到達(dá)實(shí)例(Xi,yi)進(jìn)行增量式處理(稱為批學(xué)習(xí))，這種方法需要保存大量的歷史數(shù)據(jù)，且反復(fù)學(xué)習(xí)會消耗大量時間，因此逐漸不適合用于處理大規(guī)模數(shù)據(jù)流任務(wù)；2)將數(shù)據(jù)流劃分為相同大小的數(shù)據(jù)塊B1，B2，…，Bi，…(稱為塊學(xué)習(xí))，分類器只針對最新的數(shù)據(jù)塊進(jìn)行學(xué)習(xí)和更新；3)分類器只針對最新的單個實(shí)例進(jìn)行1對1的分類和學(xué)習(xí)，而不保存歷史實(shí)例數(shù)據(jù)(稱為在線學(xué)習(xí))，這種方法更適合大數(shù)據(jù)時代數(shù)據(jù)不斷快速產(chǎn)生的特點(diǎn)，也是當(dāng)前研究的熱門方向，因此本文采用這種方式進(jìn)行處理.

AOSELM算法分為初始化階段和在線學(xué)習(xí)階段.在初始化階段，在OSELM算法初始化階段的基礎(chǔ)上，引入自適應(yīng)模型復(fù)雜度機(jī)制.采用2折交叉驗(yàn)證的方法，確定最佳的隱含層節(jié)點(diǎn)數(shù)(number of hidden layer nodes),記為Nh.然后使用最優(yōu)的隱含層節(jié)點(diǎn)數(shù)以及加入懲罰項(xiàng)學(xué)習(xí)訓(xùn)練集，得到自適應(yīng)優(yōu)化后的初始模型，并保存輸出層權(quán)重β0.在在線學(xué)習(xí)階段，AOSELM算法針對每個到達(dá)的實(shí)例，先進(jìn)行分類.如果分類正確，則直接結(jié)束本輪學(xué)習(xí)并進(jìn)入下一個實(shí)例，不對模型進(jìn)行更新.如果分類不正確，則引入自適應(yīng)遺忘因子和概念漂移檢測機(jī)制，提出概念漂移指數(shù)(concept drift index)，記為ICD.通過ICD判斷數(shù)據(jù)流是否產(chǎn)生概念漂移，如果發(fā)生概念漂移，則將ICD和遺忘因子λ結(jié)合，使模型根據(jù)當(dāng)前數(shù)據(jù)流自適應(yīng)調(diào)整遺忘因子λ大小，從而使模型更好地適應(yīng)數(shù)據(jù)流的變化.此外還引入異常點(diǎn)檢測機(jī)制，防止模型因異常點(diǎn)而過度更新，從而增強(qiáng)分類器的抗噪音能力.圖1展示了所提出的自適應(yīng)在線順序極限學(xué)習(xí)機(jī)算法的總體框架：

Fig. 1 The overall framework of AOSELM圖1 AOSELM算法的整體框架

2.2 自適應(yīng)模型復(fù)雜度機(jī)制

分類器的分類性能通常都會受到模型復(fù)雜度的影響，如圖2所示.當(dāng)模型復(fù)雜度太低時，分類決策邊界就會像線條1那樣欠擬合；而當(dāng)模型復(fù)雜度太高時，分類決策邊界又會像線條2那樣過擬合.機(jī)器學(xué)習(xí)的目的就是學(xué)習(xí)產(chǎn)生如線條3那樣的理想決策邊界.因此，選擇合適的模型復(fù)雜度對分類器的性能起著至關(guān)重要的影響.

Fig. 2 Model complexity and decision boundary圖2 模型復(fù)雜度與決策邊界示意圖

對于OSELM算法而言，隱含層節(jié)點(diǎn)數(shù)是決定模型復(fù)雜度的關(guān)鍵參數(shù)，Nh的選擇也對分類器的分類性能和泛化能力起著重要影響.在處理分類任務(wù)時，不同數(shù)據(jù)流因?yàn)樘卣鲾?shù)不同、輸入和輸出之間的映射關(guān)系復(fù)雜程度不同等原因，往往適合不同大小的模型復(fù)雜度.然而大多數(shù)算法直接提前指定1個隱含層節(jié)點(diǎn)數(shù)且在不同數(shù)據(jù)集上保持固定，明顯不符合現(xiàn)實(shí)需求.因此，AOSELM算法引入了自適應(yīng)模型復(fù)雜度(adaptive model complexity, AMC)機(jī)制.

自適應(yīng)模型復(fù)雜度機(jī)制的具體方法是在初始化學(xué)習(xí)階段，與大多數(shù)算法直接指定1個固定的隱含層節(jié)點(diǎn)數(shù)Nh不同，首先設(shè)定Nh∈[2,2Nin]，其中Nin為輸入層節(jié)點(diǎn)數(shù)，即數(shù)據(jù)流的特征數(shù)，使用2折交叉驗(yàn)證的方式計算每個Nh對應(yīng)的平均分類準(zhǔn)確率.然后通過加入節(jié)點(diǎn)數(shù)量懲罰項(xiàng)來選出最佳的隱含層節(jié)點(diǎn)數(shù)Nh.進(jìn)一步使用最佳的Nh和訓(xùn)練集進(jìn)行學(xué)習(xí)，并加入懲罰項(xiàng)，最終學(xué)習(xí)得到更加合適的初始分類模型.這樣算法在處理不同數(shù)據(jù)流任務(wù)時，就會自適應(yīng)地計算出最合適的Nh，從而確定最合適的模型復(fù)雜度，避免出現(xiàn)欠擬合或者過擬合問題.另外，在處理數(shù)據(jù)流任務(wù)中，在線學(xué)習(xí)階段規(guī)模往往比初始化階段大很多，比如本文的實(shí)驗(yàn)中初始化階段實(shí)例數(shù)占比均小于3%，因此，AMC機(jī)制并不會明顯增加模型整體的時間開銷.

2.3 自適應(yīng)遺忘因子和概念漂移檢測機(jī)制

在FROSELM算法中，遺忘因子λ大小是決定分類器遺忘速度和適應(yīng)速度的關(guān)鍵參數(shù)，而算法提前指定遺忘因子λ值且一直保持固定，無法有效地適應(yīng)數(shù)據(jù)流的概念漂移.另外，由于我們往往無法提前獲知是否發(fā)生概念漂移、概念漂移發(fā)生的位置以及概念漂移發(fā)生的類型，因此有必要引入自適應(yīng)遺忘因子機(jī)制.AOSELM算法引入自適應(yīng)遺忘因子和概念漂移檢測(adaptive forgetting factor and concept drift detection, AFF)機(jī)制.該機(jī)制借鑒漂移檢測方法(drift detection method, DDM)提出概念漂移指數(shù)ICD，并將概念漂移指數(shù)ICD和遺忘因子λ相結(jié)合，使模型能夠根據(jù)當(dāng)前數(shù)據(jù)流概念漂移情況自適應(yīng)地調(diào)整遺忘因子λ大小，從而使模型能更好地適應(yīng)數(shù)據(jù)流的變化.

(9)

基于DDM本文提出了概念漂移指數(shù)ICD來描述當(dāng)前數(shù)據(jù)流概念漂移的程度，ICD的計算方法：

ICD=(Pw-Sw-Pmax)/Smin.

(10)

將遺忘因子λ與概念漂移指數(shù)ICD結(jié)合，使遺忘因子λ能夠隨概念漂移指數(shù)ICD自適應(yīng)地調(diào)整.遺忘因子λ的計算方法：

λ=1+0.01ICD.

(11)

當(dāng)遺忘因子λ=1時，則退化為OSELM，不具備遺忘能力，因此將λ最大值設(shè)為0.999.結(jié)合式(9)～(11)可以看出，當(dāng)概念漂移系數(shù)ICD≥-1時，則判斷數(shù)據(jù)流處于穩(wěn)定階段；當(dāng)概念漂移系數(shù)ICD←1時，則發(fā)出概念漂移警告，在線更新模型；當(dāng)概念漂移系數(shù)ICD←2時，則判定數(shù)據(jù)流已經(jīng)發(fā)生概念漂移，根據(jù)式(11)自適應(yīng)更新遺忘因子λ.隨著概念漂移系數(shù)ICD的變小，遺忘因子λ也在自適應(yīng)變小，從而使分類器具有更強(qiáng)的遺忘能力，能更快地適應(yīng)新概念.

2.4 異常點(diǎn)檢測機(jī)制

數(shù)據(jù)流往往存在噪音，而原始OSELM算法及大多數(shù)改進(jìn)算法沒有對噪音進(jìn)行有效區(qū)分，而是對每一個新到達(dá)的實(shí)例都相同處理，全部進(jìn)行更新，因此分類決策邊界很容易被噪音(異常值)破壞.

AOSELM算法引入異常點(diǎn)檢測(outlier detection, OD)機(jī)制，對預(yù)測錯誤且概念漂移系數(shù)ICD≥-1(即數(shù)據(jù)流處于穩(wěn)定狀態(tài))的實(shí)例進(jìn)行異常點(diǎn)檢測.如果判斷為異常點(diǎn)，則直接跳過該實(shí)例，不在線更新分類器；如果判斷不是異常點(diǎn)，則按照OSELM算法在線更新分類器.OD機(jī)制可以避免決策邊界過多受到異常點(diǎn)的影響，從而提升模型整體的抗噪音能力.

(12)

如果式(12)成立，則認(rèn)為當(dāng)前實(shí)例沒有遠(yuǎn)離分類決策邊界，從而判斷不是異常點(diǎn)；否則認(rèn)為當(dāng)前實(shí)例遠(yuǎn)離分類決策邊界，判斷屬于異常點(diǎn).

2.5 算法偽代碼

AOSELM算法通過引入自適應(yīng)策略和異常點(diǎn)檢測形成較優(yōu)分類模型，使其更好地適應(yīng)概念漂移，算法偽代碼見算法1所示：

算法1.AOSELM算法.

輸入：數(shù)據(jù)流(X,y)、訓(xùn)練集實(shí)例數(shù)N0、保留模型數(shù)Nm、保留預(yù)測數(shù)Np；

① 初始化階段，隨機(jī)生成輸入層權(quán)重和隱含層偏置；

② 基于訓(xùn)練集(Xtrain,ytrain)進(jìn)行交叉驗(yàn)證；

③ 引入AMC機(jī)制，計算最佳隱含層節(jié)點(diǎn)數(shù)Nh；

④ 加入L2正則化參數(shù)C；

⑤ 計算出輸出層權(quán)重β0，得到初始分類模型；

⑥ 將β0保存到模型表中，結(jié)束初始化階段；

⑧ 計算相關(guān)參數(shù)P,Pw,Sw,Pmax,Smin；

⑨ 將P保存到預(yù)測表中；

⑩ 更新Pnew=(Pnew+1)%Np；

2.6 復(fù)雜度分析

本節(jié)將從時間復(fù)雜度與空間復(fù)雜度2個層面分析AOSELM算法的計算復(fù)雜度.初始化階段，假設(shè)用于訓(xùn)練的實(shí)例數(shù)為N0，由于AMC模塊需要交叉驗(yàn)證確定最佳的隱含層節(jié)點(diǎn)數(shù)，因此初始化階段時間開銷為O(N0×(Tp+Tu)×2Nin)，其中Tp和Tu分別為OSELM算法1次預(yù)測和更新的時間開銷，Nin為輸入層的節(jié)點(diǎn)數(shù).但由于實(shí)驗(yàn)中N0占總實(shí)例數(shù)的比值均小于3%，且實(shí)際應(yīng)用中數(shù)據(jù)流往往不斷產(chǎn)生，因此我們更關(guān)心在線學(xué)習(xí)階段的時間和空間復(fù)雜度.

在時間復(fù)雜度方面，假設(shè)在線學(xué)習(xí)階段數(shù)據(jù)總數(shù)為N.首先所有實(shí)例都需要進(jìn)行預(yù)測，因此時間開銷為O(N×Tp).假設(shè)有N1個正確預(yù)測實(shí)例，由于預(yù)測正確則直接結(jié)束這一輪的在線學(xué)習(xí)，避免更新模型，所以這部分額外的時間開銷可以忽略.對于預(yù)測錯誤的N-N1個實(shí)例，首先需要進(jìn)行概念漂移檢測，當(dāng)發(fā)生概念漂移檢測結(jié)果是警告或漂移時(假設(shè)有N2個實(shí)例)，均需要在線更新模型，由于概念漂移檢測和更新遺忘因子的時間開銷可以忽略，因此AFF模塊時間開銷為O(N2×Tu).剩下的N-N1-N2個實(shí)例需要進(jìn)行異常點(diǎn)檢測，由于需要Nm個模型進(jìn)行預(yù)測，因此OD模塊時間開銷為O((N-N1-N2)×Nm×Tp)的時間.最后，當(dāng)判斷為異常點(diǎn)時，直接跳過本次實(shí)例，而當(dāng)判斷不是異常點(diǎn)時(假設(shè)有N3個實(shí)例)，需要在線更新模型，這部分時間消耗為O(N3×Tu).因此AOSELM在線學(xué)習(xí)階段時間開銷為O(N×Tp+(N2+N3)×Tu+(N-N1-N2)×Nm×Tp).由于Tu?Tp，因此AOSELM算法的時間復(fù)雜度與模型預(yù)測錯誤的實(shí)例個數(shù)(N-N1)成正比.

在空間復(fù)雜度方面，AOSELM算法采取的是在線學(xué)習(xí)方式，對每個實(shí)例逐個處理，學(xué)習(xí)完后直接刪除舊的實(shí)例數(shù)據(jù)，只是額外增加了1個(Nh×No+1,Nm)大小的矩陣儲存模型參數(shù)β以及1個(Np,1)大小的矩陣儲存最近的Np個預(yù)測結(jié)果.由于本文實(shí)驗(yàn)中輸出層節(jié)點(diǎn)數(shù)No均為1，因此，額外增加的內(nèi)存消耗約為O(Nh×Nm+Nm+Np)，由于Nh,Nm和Np都是常量，且實(shí)驗(yàn)中設(shè)定的數(shù)值都很小，所以AOSELM算法的空間復(fù)雜度為O(1).

3 實(shí)驗(yàn)與結(jié)果

為了驗(yàn)證本文提出的AOSELM算法的性能以及其對概念漂移數(shù)據(jù)流的適應(yīng)性，本文在理論研究的基礎(chǔ)上進(jìn)行了大量的實(shí)驗(yàn).本節(jié)主要介紹實(shí)驗(yàn)環(huán)境和數(shù)據(jù)集、參數(shù)敏感性分析、算法性能對比以及通過消融實(shí)驗(yàn)來衡量AOSELM算法所引入的3個機(jī)制的效果.驗(yàn)證實(shí)驗(yàn)的設(shè)計、性能評估以及算法機(jī)制分析是本節(jié)的核心內(nèi)容.

3.1 實(shí)驗(yàn)數(shù)據(jù)集

為了驗(yàn)證AOSELM算法的性能，實(shí)驗(yàn)數(shù)據(jù)集選取5個人工合成數(shù)據(jù)集和2個真實(shí)數(shù)據(jù)集，實(shí)驗(yàn)數(shù)據(jù)集簡要信息如表1所示.實(shí)驗(yàn)中默認(rèn)所有算法的訓(xùn)練集實(shí)例數(shù)為500，懲罰參數(shù)C=0.1.本文實(shí)驗(yàn)平臺為Windows 10，CPU為Intel i7-2.5 GHz，內(nèi)存為8 GB，所有分類算法均基于Python語言實(shí)現(xiàn).

Table 1 Experimental Data Set Information表1 實(shí)驗(yàn)數(shù)據(jù)集信息

1) SEAs，SEAg和SEAm數(shù)據(jù)集.SEA生成器在SEA算法[22]中被提出.通過改變閾值，可以模擬概念漂移.數(shù)據(jù)集中含有3個屬性，其中只有2個屬性是相關(guān)的.通過使用SEA生成器生成了3個數(shù)據(jù)集，每個數(shù)據(jù)集包含20 000個實(shí)例，并添加了3%的噪聲.另外，3個數(shù)據(jù)集均包含2次概念漂移，且都發(fā)生在實(shí)例編號為5 000和15 000的位置.其中，SEAs數(shù)據(jù)集包含2次突變型概念漂移；SEAg數(shù)據(jù)集包含2次漸變型概念漂移；SEAm數(shù)據(jù)集包含1次突變型概念漂移和1次漸變型概念漂移.

2) Sine數(shù)據(jù)集.數(shù)據(jù)集中含有4個屬性，其中只有2個屬性是相關(guān)的.數(shù)據(jù)集包含20 000個實(shí)例，且在5 000，10 000，15 000這3個位置發(fā)生突變型反轉(zhuǎn)，即概念漂移前后目標(biāo)值剛好相反.

3) Mixed數(shù)據(jù)集.數(shù)據(jù)集中含有4個屬性，其中只有2個屬性是相關(guān)的.數(shù)據(jù)集包含20 000個實(shí)例，且在5 000，10 000，15 000這3個位置發(fā)生漸變型反轉(zhuǎn)，即概念漂移前后目標(biāo)值剛好相反.

4) Elec數(shù)據(jù)集.是廣泛應(yīng)用于數(shù)據(jù)流學(xué)習(xí)中的真實(shí)數(shù)據(jù)集.該數(shù)據(jù)集是來自澳大利亞新南威爾士州電力市場1995—1998年的部分?jǐn)?shù)據(jù)，包含45 312個實(shí)例.數(shù)據(jù)集一共包含6個相關(guān)屬性，由于那里的電力價格不是固定的，而是根據(jù)供求關(guān)系而變化，因此目標(biāo)是預(yù)測每天電力價格的變化(1表示上升，0表示下降).

5) Weather數(shù)據(jù)集.包含1949—1999年在內(nèi)布拉斯加州Bellevue收集的天氣信息，包含18 159個實(shí)例.數(shù)據(jù)集一共包含8個相關(guān)屬性，目的是預(yù)測給定日期是否下雨.

3.2 對比算法

將本文提出的AOSELM算法與其他6種數(shù)據(jù)流在線分類算法進(jìn)行性能比較，分別是：

1) OSELM算法.由Liang等人[11]于2006年提出，該算法是Huang等人[9]提出的極限學(xué)習(xí)機(jī)ELM算法的在線學(xué)習(xí)方法，具有速度快、分類性能好的優(yōu)勢，被廣泛應(yīng)用.

2) ROSELM(regularized online sequential extreme learning machine)算法.由Huynh等人[23]于2011年提出，該算法將正則化技術(shù)引入OSELM，從而提高了分類器的泛化能力.

3) FROSELM算法.由杜占龍等人[19]于2015年提出，該算法將將遺忘因子FF方法和正則化技術(shù)引入OSELM，根據(jù)實(shí)例的時間順序分別為每個樣本分配不同的權(quán)重.

4) FGROSELM算法.由Guo等人[20]于2018年提出，該算法采用一種新的廣義正則化方法來代替?zhèn)鹘y(tǒng)的指數(shù)遺忘正則化，使算法具有恒定的正則化效果以及更好的概念漂移適應(yīng)能力.

5) 霍夫丁樹(Hoeffding tree, HT)算法.由Domingos等人[24]提出，是一個流行的增量決策樹算法，其創(chuàng)造性地使用Hoeffding界確定選擇劃分屬性時所需的樣本數(shù)，在很多研究中具有優(yōu)秀的分類性能.

6) 樸素貝葉斯(naive Bayes, NB)[25]算法.是一種廣泛應(yīng)用的分類算法，以其簡單性和低計算量而聞名，實(shí)驗(yàn)中使用的是傳統(tǒng)樸素貝葉斯算法的在線學(xué)習(xí)版.

3.3 參數(shù)敏感性分析

為了解釋引入自適應(yīng)模型復(fù)雜度機(jī)制(AMC)、自適應(yīng)遺忘因子和概念漂移檢測機(jī)制(AFF)的動機(jī)，本節(jié)設(shè)計了參數(shù)敏感性分析實(shí)驗(yàn)，用來驗(yàn)證隱含層節(jié)點(diǎn)數(shù)Nh和遺忘因子λ對模型分類性能的影響.

圖3展示了不同隱含層節(jié)點(diǎn)數(shù)Nh值下OSELM算法在不同數(shù)據(jù)集上的分類準(zhǔn)確率.從中可以發(fā)現(xiàn)，當(dāng)隱含層節(jié)點(diǎn)數(shù)Nh太小時，模型的學(xué)習(xí)能力不夠，因此分類器的性能不佳.而隱含層節(jié)點(diǎn)數(shù)Nh太大又會加大模型的復(fù)雜度，從而大大增加模型的學(xué)習(xí)時間.目前大多數(shù)算法都采用提前指定隱含層節(jié)點(diǎn)數(shù)Nh的方式進(jìn)行學(xué)習(xí)，這顯然不能取得最佳的性能，不同數(shù)據(jù)流因?yàn)樘卣鲾?shù)不同、輸入和輸出之間的映射關(guān)系復(fù)雜程度不同等原因，具有不同的最佳隱含層節(jié)點(diǎn)數(shù)Nh.因此AOSELM算法引入了自適應(yīng)模型復(fù)雜度機(jī)制，在初始化階段，采用交叉驗(yàn)證的方式確定該數(shù)據(jù)集的最佳隱含層節(jié)點(diǎn)數(shù).

Fig. 3 Classification accuracy of OSELM with different Nh values on different data sets圖3 不同Nh值OSELM在不同數(shù)據(jù)集的分類準(zhǔn)確率

圖4和圖5分別展示了不同遺忘因子λ值下FROSELM算法在Sine數(shù)據(jù)集上的分類準(zhǔn)確率和累計分類準(zhǔn)確率.從圖4、圖5中可以發(fā)現(xiàn)，當(dāng)遺忘因子λ較大時，雖然分類器能夠在數(shù)據(jù)流穩(wěn)定時期取得更好的分類準(zhǔn)確率，但當(dāng)數(shù)據(jù)流發(fā)生概念漂移時卻更難適應(yīng)新概念，從而降低了模型累計分類準(zhǔn)確率.相反地，當(dāng)遺忘因子λ較小時，雖然分類器能夠更快地遺忘舊模型，從而更好地適應(yīng)概念漂移，但在數(shù)據(jù)流穩(wěn)定時期卻喪失了更好的分類性能.由于我們往往無法提前獲知是否發(fā)生概念漂移、概念漂移發(fā)生的位置以及概念漂移發(fā)生的類型，因此有必要引入自適應(yīng)遺忘因子機(jī)制.

Fig. 4 Classification accuracy of FROSELM with different λ on Sine圖4 不同λ值FROSELM在Sine的分類準(zhǔn)確率

Fig. 5 Cumulative classification accuracy of FROSELM with different λ on Sine圖5 不同λ值FROSELM在Sine的累計分類準(zhǔn)確率

AOSELM算法借鑒DDM方法提出了概念漂移指數(shù)ICD，并將概念漂移指數(shù)ICD和遺忘因子λ相結(jié)合，使模型能夠根據(jù)當(dāng)前數(shù)據(jù)流概念漂移情況自適應(yīng)地調(diào)整遺忘因子λ大小，從而使模型能更好地適應(yīng)數(shù)據(jù)流的變化.

3.4 對比實(shí)驗(yàn)

在對比實(shí)驗(yàn)中，將AOSELM算法與相關(guān)的算法進(jìn)行對比，包括FGROSELM，F(xiàn)ROSELM，ROSELM，OSELM，HT，NB.其中HT和NB是傳統(tǒng)分類器的在線方法，具有簡單、高效、易于理解的特點(diǎn).而FGROSELM，F(xiàn)ROSELM，ROSELM以及本文所提出來的AOSELM均是基于OSELM優(yōu)化的算法.在對比的7種算法中，只有FGROSELM，F(xiàn)ROSELM，AOSELM這3種算法引入了遺忘機(jī)制.

Fig. 6 Classification accuracy of contrast algorithm on SEAm圖6 對比算法在SEAm上的分類準(zhǔn)確率

Fig. 7 Cumulative classification accuracy of contrast algorithm on SEAm圖7 對比算法在SEAm上的累計分類準(zhǔn)確率

Fig. 8 Classification accuracy of OSELM optimization algorithm on SEAm圖8 OSELM優(yōu)化算法在SEAm上的分類準(zhǔn)確率

圖6～9分別展示了全部7種對比算法和具有遺忘機(jī)制的3種OSELM優(yōu)化算法在SEAm數(shù)據(jù)集上的分類準(zhǔn)確率和累計分類準(zhǔn)確率.從圖7中可以看出7種算法均能在面對概念漂移時更新分類器，從而適應(yīng)新概念，但ROSELM，OSELM，NB這3種算法表現(xiàn)較差.而從圖8的分類準(zhǔn)確率中可以看出，當(dāng)發(fā)生概念漂移后，AOSELM算法相比另外2種同樣具有遺忘機(jī)制的FGROSELM和FROSELM算法能夠更快地適應(yīng)概念漂移，分類性能也能在概念漂移發(fā)生后更快反彈.從累計分類準(zhǔn)確率中可以看出，AOSELM算法具有更好的分類性能，分類準(zhǔn)確率比FGROSELM和FROSELM這2種算法提高了大約2.5%.

Fig. 9 Cumulative classification accuracy of OSELM optimization algorithm on SEAm圖9 OSELM優(yōu)化算法在SEAm上的累計分類準(zhǔn)確率

圖10～13分別展示了全部7種對比算法和具有遺忘機(jī)制的3種OSELM優(yōu)化算法在Sine數(shù)據(jù)集上的分類準(zhǔn)確率和累計分類準(zhǔn)確率.從圖10～13中可以看出，當(dāng)出現(xiàn)反轉(zhuǎn)型概念漂移時，ROSELM，OSELM，HT，NB這4種算法由于不具備遺忘機(jī)制，因此完全無法適應(yīng)反轉(zhuǎn)型概念漂移，整體分類性能也非常糟糕.而具有遺忘機(jī)制的AOSELM，F(xiàn)GROSELM，F(xiàn)ROSELM這3種算法在面對反轉(zhuǎn)型概念漂移時均能做出有效反應(yīng)，適應(yīng)新概念.其中，AOSELM算法又比另外2種算法具有更高的分類準(zhǔn)確率以及更快的概念漂移適應(yīng)能力.當(dāng)檢測到發(fā)生概念漂移時，AOSELM算法能夠自適應(yīng)地調(diào)小遺忘因子λ，可以更快地遺忘舊概念，從而具有更高的整體分類準(zhǔn)確率，實(shí)驗(yàn)結(jié)果顯示比FGROSELM和FROSELM算法高大約3%.

Fig. 10 Classification accuracy of contrast algorithm on Sine圖10 對比算法在Sine上的分類準(zhǔn)確率

Fig. 11 Cumulative classification accuracy of contrast algorithm on Sine圖11 對比算法在Sine上的累計分類準(zhǔn)確率

Fig. 12 Classification accuracy of OSELM optimization algorithm on Sine圖12 OSELM優(yōu)化算法在Sine上的分類準(zhǔn)確率

Fig. 13 Cumulative classification accuracy of OSELM optimization algorithm on Sine圖13 OSELM優(yōu)化算法在Sine上的累計分類準(zhǔn)確率

表2、圖14和圖15展示了AOSELM算法和對比算法在不同數(shù)據(jù)集上的平均分類準(zhǔn)確率.從表2中可以看出，在5個人工數(shù)據(jù)集上，AOSELM均展示了更好的分類性能，分類準(zhǔn)確率比其他對比算法提高明顯.尤其是在反轉(zhuǎn)型數(shù)據(jù)集Sine和Mixed上，不具備遺忘機(jī)制的ROSELM，OSELM，HT，NB這4種算法表現(xiàn)十分糟糕，而AOSELM卻仍然能保持很高的預(yù)測準(zhǔn)確率.相比另外2種具有遺忘機(jī)制的FGROSELM和FROSELM算法，AOSELM也能提高2～3%.

Table 2 Classification Accuracy of Contrast Algorithms on Different Data Sets表2 對比算法在不同數(shù)據(jù)集上的分類準(zhǔn)確率 %

Fig. 14 Classification accuracy of contrast algorithm on different data sets圖14 對比算法在不同數(shù)據(jù)集上的分類準(zhǔn)確率

Fig. 15 Classification accuracy of OSELM optimization algorithm on different data sets圖15 OSELM優(yōu)化算法在不同數(shù)據(jù)集的分類準(zhǔn)確率

但在2個人工數(shù)據(jù)集上，AOSELM算法雖然比多數(shù)對比算法具有明顯性能優(yōu)勢，但與FROSELM算法表現(xiàn)相當(dāng)，并未能取得更高的分類準(zhǔn)確率.針對這種情況，畫出人工數(shù)據(jù)集Sine、真實(shí)數(shù)據(jù)集Elec和Weather的概念漂移指數(shù)ICD監(jiān)控過程圖，如圖16～18所示.

圖16～18分別展示了人工數(shù)據(jù)集Sine、真實(shí)數(shù)據(jù)集Elec以及真實(shí)數(shù)據(jù)集Weather的概念漂移監(jiān)控過程圖.對比可以發(fā)現(xiàn)，在人工數(shù)據(jù)集中，概念漂移是明確發(fā)生的，且在非概念漂移位置，數(shù)據(jù)流是穩(wěn)定的，概念漂移指數(shù)ICD也基本穩(wěn)定在[-1, 0]之間.而在真實(shí)數(shù)據(jù)集Elec和Weather中，數(shù)據(jù)流一直處于混亂的狀態(tài)，概念漂移指數(shù)ICD一直在-1上下波動，同時沒有明確的概念漂移發(fā)生點(diǎn)，并不能激活A(yù)OSELM算法中的自適應(yīng)遺忘因子和概念漂移檢測機(jī)制.這解釋了為何AOSELM算法沒有比FROSELM算法在真實(shí)數(shù)據(jù)集上具有更好的分類性能.

Fig. 16 Concept drift monitoring diagram on Sine圖16 人工數(shù)據(jù)集Sine概念漂移監(jiān)控過程圖

Fig. 17 Concept drift monitoring diagram on Elec圖17 真實(shí)數(shù)據(jù)集Elec概念漂移監(jiān)控過程圖

Fig. 18 Concept drift monitoring diagram on Weather圖18 真實(shí)數(shù)據(jù)集Weather概念漂移監(jiān)控過程圖

3.5 算法機(jī)制分析

本節(jié)通過消融實(shí)驗(yàn)來測量AOSELM算法所引入的自適應(yīng)模型復(fù)雜度(AMC)、自適應(yīng)遺忘因子和概念漂移檢測(AFF)以及異常點(diǎn)檢測(OD)這3種機(jī)制的效果.在消融實(shí)驗(yàn)中，通過將AOSELM算法中省略機(jī)制相應(yīng)的模塊，得到AOSELM_del_AMC，AOSELM_del_AFF，AOSELM_del_OD這3種算法，然后對比性能.

圖19～22分別展示了消融實(shí)驗(yàn)在SEAm和Sine數(shù)據(jù)集上的分類準(zhǔn)確率和累計分類準(zhǔn)確率.從圖19～22中可以發(fā)現(xiàn)，當(dāng)刪除了AMC機(jī)制后，AOSELM_del_AMC算法在在線學(xué)習(xí)的初始階段性能表現(xiàn)較差.而當(dāng)刪除了AFF機(jī)制后，AOSELM_del_AFF算法在面對概念漂移時適應(yīng)的速度最慢，整體性能也更容易受到概念漂移的影響，尤其在Sine數(shù)據(jù)集發(fā)生反轉(zhuǎn)型概念漂移時，分類器整體性能損失非常大.

Fig. 19 Classification accuracy of ablation experiment on SEAm圖19 消融實(shí)驗(yàn)在SEAm上的分類準(zhǔn)確率

Fig. 20 Cumulative classification accuracy of ablation experiment on SEAm圖20 消融實(shí)驗(yàn)在SEAm上的累計分類準(zhǔn)確率

Fig. 21 Classification accuracy of ablation experiment on Sine圖21 消融實(shí)驗(yàn)在Sine上的分類準(zhǔn)確率

Fig. 22 Cumulative classification accuracy of ablation experiment on Sine圖22 消融實(shí)驗(yàn)在Sine上的累計分類準(zhǔn)確率

表3和圖23展示了消融實(shí)驗(yàn)在不同數(shù)據(jù)集上的平均分類準(zhǔn)確率.實(shí)驗(yàn)結(jié)果表明:AOSELM算法引入的自適應(yīng)模型復(fù)雜度(AMC)、自適應(yīng)遺忘因子和概念漂移檢測(AFF)以及異常點(diǎn)檢測(OD)這3種機(jī)制均起到了很好的效果，在人工數(shù)據(jù)集上均提高了分類器的分類準(zhǔn)確率.

Table 3 Classification Accuracy of Ablation Experiment on Different Data Sets

Fig. 23 Classification accuracy of ablation experiment on different data sets圖23 消融實(shí)驗(yàn)在不同數(shù)據(jù)集上的分類準(zhǔn)確率

3.6 算法效率分析

在線學(xué)習(xí)要求分類算法能及時反饋分類結(jié)果，為了驗(yàn)證AOSELM算法的分類效率，實(shí)驗(yàn)統(tǒng)計了AOSELM算法的時間開銷，并與原始的OSELM算法進(jìn)行對比.實(shí)驗(yàn)結(jié)果為重復(fù)10次實(shí)驗(yàn)的平均值，如表4所示：

Table 4 Running Time of Contrast Algorithms on Different Data Sets

從表4中可以看出，在初始化階段，AOSELM算法由于引入AMC機(jī)制，運(yùn)行時間比原始OSELM算法高出50倍以上，但由于用于訓(xùn)練的實(shí)例數(shù)占比很小，因此初始化階段的時間消耗在整體上可以忽略.在線學(xué)習(xí)階段，AOSELM算法的運(yùn)行時間為OSELM算法的2～3倍.此外，AOSELM算法的預(yù)測準(zhǔn)確率越高，運(yùn)行時間相比OSELM的倍數(shù)越低，驗(yàn)證了AOSELM算法的時間復(fù)雜度與模型預(yù)測錯誤率成正比.

4 總 結(jié)

本文提出了一種自適應(yīng)在線順序極限學(xué)習(xí)機(jī)(AOSELM)算法，其基于在線學(xué)習(xí)方式，引入了自適應(yīng)模型復(fù)雜度機(jī)制、自適應(yīng)遺忘因子和概念漂移檢測機(jī)制以及異常點(diǎn)檢測機(jī)制，從而可以在動態(tài)變化的數(shù)據(jù)流環(huán)境下應(yīng)對多種類型的概念漂移.通過自適應(yīng)模型復(fù)雜度機(jī)制，在初始化階段可以自適應(yīng)確定出最佳的隱含層節(jié)點(diǎn)數(shù)Nh，并加入正則項(xiàng)，優(yōu)化模型復(fù)雜度.其次通過自適應(yīng)遺忘因子和概念漂移檢測機(jī)制，將概念漂移和遺忘因子結(jié)合，使分類模型在發(fā)生概念漂移時自動調(diào)小遺忘因子，而在數(shù)據(jù)流穩(wěn)定時自動調(diào)大遺忘因子，從而適應(yīng)數(shù)據(jù)流的動態(tài)變化.最后通過異常點(diǎn)檢測機(jī)制，增強(qiáng)模型抗噪音能力，使分類的決策邊界不易被異常點(diǎn)破壞.因此，AOSELM算法能夠自適應(yīng)地在線處理各種類型的概念漂移數(shù)據(jù)流.

在仿真實(shí)驗(yàn)部分，通過參數(shù)敏感性分析驗(yàn)證了隱含層節(jié)點(diǎn)數(shù)Nh和遺忘因子λ對模型分類性能的影響，解釋了引入自適應(yīng)模型復(fù)雜度機(jī)制與自適應(yīng)遺忘因子和概念漂移檢測機(jī)制的動機(jī).然后在對比實(shí)驗(yàn)中，通過將AOSELM算法與其他6個數(shù)據(jù)流分類器進(jìn)行對比，驗(yàn)證了AOSELM算法的有效性，尤其是在5個人工數(shù)據(jù)集上，AOSELM算法表現(xiàn)出了更穩(wěn)定、更準(zhǔn)確的分類效果.最后，通過消融實(shí)驗(yàn)驗(yàn)證所引入AMC，AFF，OD這3種機(jī)制的效果，證實(shí)了3種機(jī)制對AOSELM算法性能提升的有效性.然而，如何解決更復(fù)雜的真實(shí)數(shù)據(jù)流分類問題仍然是研究的難點(diǎn)，下一步工作將結(jié)合代價敏感學(xué)習(xí)和在線集成方法解決概念漂移數(shù)據(jù)流中的復(fù)雜分布問題.

作者貢獻(xiàn)聲明：蔡桓提出了算法思路并撰寫論文；陸克中提出了實(shí)驗(yàn)方案；伍啟榮負(fù)責(zé)完成實(shí)驗(yàn)；吳定明提出指導(dǎo)意見并修改論文.