基于特征結構不變性思想的自適應在線神經網絡算法

韋 磊, 姜海富, 于化龍,2*

(1.江蘇科技大學 計算機學院, 鎮江 212100)(2.四川輕化工大學 人工智能四川省重點實驗室, 宜賓 643000)

在線學習(online learning)，又稱數據流學習(learning from data stream)，是機器學習領域的重要研究分支之一[1].所謂在線學習，是指數據的獲取不是一次性的，而是隨著時間不斷動態累加的.當前，隨著移動互聯網與物聯網等技術的高速發展，在線學習在智能交通[2]、市場分析[3]、網絡安全[4]，乃至更多的應用領域都存在著廣泛的應用價值.

相比于傳統的依賴于靜態數據的機器學習，在線學習通常要面臨更多的挑戰，主要包括：① 考慮到數據流高頻、量大的特點，以及存儲的限制，通常數據都是在使用后即被拋棄的，因此要求模型只能訪問數據一次(one pass)；② 數據的分布可能會隨著時間的延展而發生各種動態改變，即概念漂移(concept drift)問題[5]，因此要求模型要能實時跟蹤分布的變化而不斷實現自我進化.

對于one pass 問題，現有的解決策略大體可以分為兩類：一是對傳統的單一靜態學習模型進行改進，令其可適應在線學習環境，當接收到新數據時，通過自動修正模型參數使其同時適應新舊兩類數據[6-7]；二是將傳統的單一靜態學習模型與集成學習框架相結合，不同的個體學習器建立于不同的數據塊之上，通過投票規則相關聯，同時兼顧新舊經驗[8-10].對于概念漂移問題，通常采用一個獨立的分布漂移檢測模塊來對漂移的發生進行監測，進而將監測的結果反饋給單一學習模型以調控其對舊經驗的遺忘[5,11-12]，或集成學習模型以分配不同個體學習器的決策權重.上述策略盡管有效，但如何設計合理的遺忘函數及決策權重分配函數卻是一個困難的問題，其很可能直接影響到最終的學習效果.

文中從一個全新的角度來考慮在線學習模型對概念漂移的自適應問題，即，模型能否不通過對分布漂移的檢測與量化來適應概念漂移.文獻[13]研究發現：大部分所謂的概念漂移實質上只是分布的值域隨時間而發生了變化，而其內在的概念結構卻并未改變，因此采用增量離散化的方法來追蹤特征的值域變化，從而實現了對特征結構的動態保持，有效解決了概念漂移的問題.但增量離散化也存在一個問題，即采用離散化屬性值來取代連續型屬性值，很可能會造成信息損失，進而影響到學習的效果.

基于特征結構不變性思想，文中提出了一種概念漂移自適應在線神經網絡算法，首先采用增量離散化技術來適應概念漂移，并保持特征結構，然后利用增量聚類技術來挖掘并細化特征的內在結構，進而采用一種類似深度森林算法[14]中的特征構造策略在特征內在結構上提取連續型的輔助結構特征，最后將這些輔助特征與原始特征相結合，擴充數據的特征空間，用來訓練并更新在線神經網絡模型.顯然，輔助特征既體現了原始特征的潛在內部結構，對分布漂移不敏感，同時又體現了樣本在原始特征潛在內部結構中的細微差異性，從而為學習提供了更為豐富的信息.此外，考慮到在線學習所普遍具有的實時性需求，采用在線序列極限學習機算法(online sequential extreme learning machine，OS-ELM)[15]作為在線神經網絡的訓練算法，該算法同時兼具訓練速度快與魯棒性高的特點.通過8個基準的在線數據集驗證文中算法的有效性、可行性和優越性進行了驗證，結果表明：文中算法不但對概念漂移可以自適應，而且相比于傳統的概念漂移自適應策略，要具有更好的性能.

1 研究方法

1.1 增量離散化

離散化(discretization)是數據挖掘領域中一種常用的技術，用于將連續型的屬性轉化為離散型屬性[16].離散化技術采用設置斷點的方式將連續的屬性取值區間轉化為若干的容器(bin)，每一個容器對應于一段連續取值區間，取值于某一區間的屬性值則用對應容器的離散值來取代.

文獻[13]提出了兩種增量的離散化算法，分別命名為Ida和Idaw，在動態數據流中，前者可保持近似的等頻分布，而后者則可保持完整的等頻分布.采用增量離散化能有效追蹤數據分布的變化，并很好地保留特征結構中潛在概念，適合解決概念漂移問題，但由于將連續屬性轉化為離散屬性，也將會導致大量的有效信息損失，進而影響到最終的學習效果.

在IDA和IDAW算法中，均采用等頻方式來實現屬性的離散化，即保證在每一個容器內的樣例數近似相等.初始的樣本集記做V，首先對其等頻離散化，得到斷點序列〈κ1,κ2,...,κm-1〉，然后，在增量的過程中，使用新接收到的樣例來取代V中的舊樣例，并對斷點序列進行更新，實現增量離散化.上述過程中，IDA和IDAW算法之間的不同之處在于：前者在新接收樣例中隨機選擇個體進行斷點序列的更新，且用新樣例隨機取代V中的樣例，而后者則采用每一個新接收的樣例來更新斷點序列，且新樣例取代V中最舊的樣例.因此，相比于IDA算法，IDAW算法對數據分布的跟蹤要更及時，但時間復雜度也要更高.

IDA和IDAW算法的流程簡單描述如下：

算法1 s: m: 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18.IDA算法thevolumeoftheuser-definedrandominstancesetthenumberoftheuser-definedbinsprocedureD=IDA(S={x1,...,xn},s,m) collecttheinitialsinstancesasV fori=1toado Qi=INITIALDISCRETIZATION(Vi,m) endfor fori=1tosdo Di=DETECTDISCRETIZATION(xi,Q,m) endfor fori=s+1tondo ifrand()≤s/ithen V=UPDATESAMPLES(xi,V) forj=1toado (Dji,Qj)=INSERTVALUE(V,m,Qj) endfor else Di=DETECTDISCRETIZATION(xi,Q,m) endif endforendprocedure

算法2 s: m: 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15.IDAW算法thevolumeoftheuser-definedrandominstancesetthenumberoftheuser-definedbinsprocedureD=IDAW(S={x1,...,xn},s,m) collecttheinitialsinstancesasV putVintoabufferBbasedontheorderofreceiving fori=1toado Qi=InitialDiscretization(Vi,m) endfor fori=1tosdo Di=DetectDiscretization(xi,Q,m) endfor fori=s+1tondo (V,B)=UpdateSamples(xi,V,B) forj=1toado (Dji,Qj)=InsertValue(V,m,Qj) endfor endforendprocedure

其中，InitialDiscretization函數用于搜尋初始斷點，劃分容器；DetectDiscretization函數用于將原始的連續型屬性值轉化為對應的離散化值；UpdateSamples函數負責新樣例對保留樣例集V的更新；而InsertValue函數用于更新斷點序列，并完成對新樣例的離散化.

1.2 增量聚類

聚類技術是機器學習與數據挖掘領域的重要組成部分之一，有助于發現數據潛在的內在結構[17].其中K-means[18]最為經典.

在一個給定的數據集S={x1,x2,...,xi,...,xn}上，其中，xi∈Ra，采用K-means算法就是要根據樣本在特征空間中的距離關系將S中所有樣本劃分入k個類簇c1,c2,...,ck，并最小化優化函數Z：

(1)

式中：ω1,ω2,...,ωk為各類簇的質心.

文中采用文獻[19]中提出的序列K-means(sequentialK-means)算法來實現流數據的增量聚類，序列K-means算法每次對一個樣本進行更新，即當接收到一個新樣本xi時，采用下式來調整與其最近的聚類cj的質心：

(2)

式中：n為類簇cj中原有的樣本數.

文中提出的IncrementalKmeans算法的流程描述如下：

算法3 s: k: 1. 2. 3. 4. 5. 6. 7. 8.IncrementalKmeans算法theuser-definedinitialnumberoflabeledinstancestheuser-definednumberofclustersprocedurec=IncrementalKmeans(S={x1,...,xn},s,k) collecttheinitialsinstancesasS0 [cl1～cls,ω1～ωk,P1～Pk]=InitialKmeans(S0,k) fori=s+1tondo findωjwhichisthenearestclustercentertoxi tuneωjwithPjandxiaccordingtoEq.(2) letcli=j endforendprocedure

其中，InitialKmeans函數在初始的S個樣本上執行聚類，并為其分配類簇標記cl1～cls，生成各類簇質心ω1～ωk，以及統計各類簇中初始的樣本數P1～Pk.在在線學習過程中，新接收的樣例將會不斷更新ω和P的取值.考慮到IncrementalKmeans算法運行于IDA或IDAW算法所構造的離散特征空間之上，故特征空間的穩定性可以得到有效保障，這也將有助于搜尋到數據真實的潛在內部結構.

1.3 結構特征抽取

在發現數據潛在內部結構的基礎上，對結構進行描述，并進一步生成可量化的結構特征兩方面入手：一方面提取能反應數據內部結構的全局描述特征，另一方面則充分利用聚類信息提取局部描述特征.

(3)

新的特征序列指明了樣本在整體特征空間中的相對位置.

參照深度森林算法的思想，給出了一個結構特征抽取的示意圖，如圖1.假定真實類別數q與聚類數k均為3，則c1,c2,c3分別表示3個類簇，而g1,g2,g3表示樣本到3個類簇質心的距離.從圖1可以看出，在添加結構特征后，特征空間得到了有效擴充，維度從a轉化為a+q+k，其中a與q是確定的，而聚類數k則是人為指定的.在實際應用中，可以通過仔細調控變量k，來保證對樣本的最優描述.

圖1 結構特征抽取過程

1.4 在線序列極限學習機

樣本在經過維度擴增后，需要輸入分類器進行學習和訓練.文中采用單隱層前饋神經網絡(single-hidden-layer feedback neural networks，SLFNs)作為分類模型，其優點在于可以以任意精度近似任意的非線性函數.圖2為SLFNs的結構.

圖2 單隱層前饋神經網絡結構

對于SLFNs，已有多種成熟的學習算法，如誤差反傳(back-propagation,BP)算法[21]，但該算法需要通過迭代的方式來完成網絡訓練，因此，提出時間復雜度較高，極限學習機算法(extreme learning machine，ELM)算法來快速地訓練SLFNs[22-23].相比于BP算法，ELM算法不但訓練速度快，而且魯棒性也通常更好[24].

假設對于一個具有n個訓練樣本的q分類問題，第i個樣本表示為(xi,ti)，其中xi對應于一個a×1的輸入向量，而ti對應于一個q×1的輸出向量，若SLFNs中有L個隱層節點，且輸入層與隱藏層間的權重和偏置均隨機生成，則樣本xi在隱藏層的對應輸出可以描述為h(xi)=[h1(xi), }),...,hL(xi)]，ELM的數學模型可表示為：

Hβ=T

(4)

式中：H=[h(x1),h(x2),...,h(xn)]T為所有訓練樣本在隱藏層的輸出；β為隱藏層與輸出層間的連接權重；T=[t1,t2,...,tn]為全部訓練樣本的期望輸出.顯然，在上式中，只有β未知，故可通過最小二乘法對其進行求解，結果如下：

(5)

式中：H?為隱藏層輸出矩陣H的Moore-Penrose廣義逆，這可以保證所求得的解為公式(4)中方程的最小范數最小二乘解，進而保證模型的泛化性能.

對于在線學習，文獻[15]基于ELM提出了一種在線序列極限學習機OS-ELM算法，該算法采用遞歸最小二乘策略擬合新接收的數據.通過大量理論推導，得出輸出權重矩陣的更新規則為：

(6)

式中：Hi+1和Ti+1分別為所收到的第i+1個樣本所對應的隱層輸出和期望輸出；而β(i)和β(i+1)則分別為更新前后的輸出權重.Pi+1為：

(7)

表明Pi也是可以通過迭代的方式進行更新的，其初始值P0為：

(8)

式中：H0為最初的隱藏層輸出矩陣.顯然，無論Hi+1,Ti+1，還是Pi+1，均可用新接收的樣本來進行計算和更新，故可保證β同時擬合新舊兩類樣本，而無需重新訓練.因此，文中采用OS-ELM算法來訓練在線神經網絡模型.

1.5 文中算法

文中算法整合了增量離散化、增量聚類、結構特征抽取及在線序列極限學習機等技術，實現了在線學習對概念漂移的自適應.其中，增量離散化和增量聚類用于跟蹤特征空間的變化，結構特征抽取用于適應概念漂移，在線序列極限學習機用于實現學習模型的動態更新.

文中提出的IncreFull算法流程描述如下：

算法4 s: m: k: L: 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19.IncreFull算法theuser-definedinitialnumberoflabeledinstancestheuser-definednumberofbinstheuser-definednumberofclusterstheuser-definednumberofhiddennodesinELMprocedureΘ=IncreFull(S={x1,...,xn},s,m,k,L) collecttheinitialsinstancesasVandlabelthemast1～tsmanually Q=InitialDiscretization(V,m) D=DetectDiscretization(x1～xs,Q,m) [cl,ω,P]=InitialKmeans(D,k) [g1～gs,l1～ls]=NewFeatureExtraction(cl,ω,P) integrateg1～gsandl1～lswithx1～xstoformthenewfeaturevectorf1～fsβ=InitialElm(f1～fs,t1～ts,L) fori=s+1tondo updateQandVwithIDAorIDAW Di=DetectDiscretization(xi,Q,m) [cli,ω,P]=IncrementalKmeans(Di,ω,P) [gi,li]=NewFeatureExtraction(cli,ω,P) integrategiandlitoformthenewfeaturevectorfi Θi-s=Elm(fi,β) collecttherealclasslabeltifortheinstancexi β=OsElm(fi,ti,β) endforendprocedure

其中，NewFeatureExtraction函數用于抽取結構特征，InitialElm、Elm及OsElm函數則分別用于訓練初始的學習模型，對新接收的數據進行預測及在接收到新數據時，對學習模型進行更新，而Θ則用于存儲樣本的預測類標，可通過與真實類標序列t的比較，計算出分類的精度.

2 實驗結果與討論

2.1 數據集

采用8個數據集驗證所提算法的有效性、可行性與優越性.其中，Powersupply和HyperPlane數據集獲取自Data Mining Repository；electricity來源于MOA網站；noaa數據集獲取自美國國家環境信息中心，而其它4個，即SEA, spiral, Gaussian 和checkerboard，均為人工數據集，由對應的數據流生成器直接生成得到.這些數據集都或多或少地含有概念漂移，漂移類型與漂移量有所不同[25].表1給出了這些數據集的數據屬性描述.

表1 數據集描述

2.2 實驗設置

實驗采用IDA和IDAW策略，并將算法簡寫為IncreFull-IDA和IncreFull-IDAW.同時，與以下幾類算法進行了比較：

(1)IncreOnly: 該算法沒有增量離散化，增量聚類和結構特征的提取過程，而只是采用數據原始特征結合OS-ELM算法來進行建模.

(2)IncreForg: 該算法不執行增量離散化，增量聚類和結構特征的提取過程，而是在OS-ELM模型上添加遺忘因子，遺忘系數采用缺省值0.01，即每一次更新，遺忘1%的舊經驗[11].

(3)IncreDisc: 利用增量離散化技術生成離散特征，并用其取代原始的連續型特征，利用OS-ELM算法建模.

(4)IncreExtra: 該算法不執行增量離散化，而直接在原始的連續特征空間上直接進行增量聚類和結構特征抽取，并對原始特征空間進行擴增，最后通過OS-ELM算法進行建模.

(5)IncreMix: 利用增量離散化技術生成離散特征，并與原始的連續型特征進行整合，利用OS-ELM算法建模.

顯然，可以將IncreOnly算法視為基線算法，IncreForg算法用于檢測遺忘機制是否能真的適應概念漂移，同時與文中算法在概念漂移的適應性方面進行比較，IncreDisc與IncreMix算法用于驗證采用離散化的特征是否會造成信息損失，對最終結果的影響又會是多大；IncreExtra算法用于驗證增量離散化的作用，觀察其是否適應概念漂移.關于各種算法分別采用了哪些功能模塊，以及它們之間的具體區別，請參照表2.

表2 各種算法對不同功能模塊的使用情況，√ 和 ×分別表示算法中包含/不包含對應功能模塊

文中實驗環境：Intel i7 6700HQ 8核CPU，每個核的主頻為2.60 GHz，內存為16 G，代碼運行環境為Matlab 2013a.

為了保證實驗比較的公正性，所有的數據都做了標準化處理，即每個特征均等比例縮放到[0,1]區間.至于各比較算法中的共有參數，也根據經驗對其進行了統一的設置，其中，離散化區間數m設為10，聚類數k設為5，ELM中隱藏層節點個數L設置為50.表1中所給出的初始標注樣本數為初始模型建模的訓練集，其它樣本按照在數據集中的順序逐一接收.此外，考慮到極限學習機作為在線學習器，其本身的隨機性，每個實驗均隨機重復執行50次，并以均值±標準差的形式給出最終的結果.

2.3 結果分析

表3給出了各種比較算法的實驗結果，評價指標為分類精度，其中，在每個數據集上，表現最好的算法所對應的實驗結果已經做了加粗處理.

表3 各種算法的實驗比較結果

從表3的實驗結果中，可以得出以下結論：

(1)增量離散化策略確實可以有效地解決數據流中的概念漂移問題，這一結論可以通過比較IncreMix與IncreOnly算法的實驗結果而得出，也與文獻[13]的結論是完全吻合的.同時，從上述兩類算法的實驗對比結果中也可以看出：在noaa, HyperPlane和spiral等3個數據集上，融合了離散化特征后的分類精度反倒出現了下降，認為其可能與離散化自身的信息損失特點有關，在這幾個數據集上，這一特點可能被放大了.

(2)采用在在線學習模型上添加遺忘機制的策略確實能緩解概念漂移的影響，這一結論可以通過比較IncreForg和IncreOnly算法的實驗結果的得出.但同時也發現：采用遺忘機制能起到的性能提升作用非常有限的，其遠不如IncreFull-IDA和IncreFull-IDAW.出現這種現象的原因可能在于：IncreForg采用的是固定的遺忘系數，而沒有考慮概念漂移是否發生，發生時漂移的幅度又是多大這兩個重要因素.當然，可以通過加入概念漂移檢測模塊來動態調控遺忘系數，相信學習性能會有一定的提升，但也必然會大幅增加算法的時間開銷.

(3)與IncreOnly算法的實驗結果相比，IncreExtra算法在大部分數據集上有明顯的性能提升.盡管IncreExtra遺棄了增量離散化的過程，但其仍然整合了不算精確的高層結構特征，顯然，這些特征是有助于改進模型質量的.原因可能有以下兩方面：一是這些高層結構特征盡管不夠精確，但仍能在一定程度上反應數據的全局與局部分布；二是盡管沒有執行增量離散化過程，增量聚類技術也可能在一定程度上實現對概念漂移的自適應，從而提升學習性能.

(4)所提出IncreFull-IDA和IncreFull-IDAW算法在大部分數據集上，其分類性能要顯著優于其它5種算法，再次表明了利用增量離散化來跟蹤數據漂移，利用增量聚類來描述數據潛在的內部結構，利用結構特征抽取來提取高層結構特征的策略在解決漂移數據流建模問題上是有效的和可行的.

(5)對比IncreFull-IDA算法，IncreFull-IDAW算法在大部分數據集上都獲得了或多或少的性能提升.這與兩種算法的離散區間跟蹤密度直接相關，IncreFull-IDA算法是間歇性隨機對離散化區間進行跟蹤，而IncreFull-IDAW算法則能實現對離散化區間的完全跟蹤.事實上，文獻[13]指出：IDA策略可適應逐漸演化的概念漂移和循環發生的概念漂移，但不適應突發的概念漂移，而IDAW策略對所有的概念漂移類型均適用.

2.4 參數討論

文中算法中，有兩個重要的參數可能會極大地影響到學習模型的最終質量，一是增量離散化的區間數m，另一個則是增量聚類的類簇數k.不失一般性，以Powersupply和SEA數據集為例，分別測試了所提出的兩種算法隨上述兩參數變化而產生的性能變化.其中，m的取值變化區間為[4,12]，變化步長為2，而k的取值變化區間為[3,11]，變化步長為1.性能隨參數變化結果如圖3.

圖3 文中算法隨參數m與k的變化而產生的性能

從圖3可以看出，盡管性能曲面的變化存在一些波動，但仍能反映出一定的規律.對于參數m，當其取值較小時，模型的性能通常較差，這主要是因為m的取值直接關系到了接下來增量聚類的特征空間大小，若其取值過小，則可能會導致增量聚類對數據內在結構描述的不夠精確，必然會降低模型的質量.當m的取值逐漸增大時，模型的性能將會隨之提升并逐漸趨于穩定.當然，取一個較大的m值盡管可以充分地保證建模的質量，但也存在時間復雜度過高的問題，可能會與在線學習的實時性需求相沖突，故建議在實際應用中對該參數取一個適中值即可.對于k的取值，發現兩個數據集反饋回了完全不同的規律，在Powersupply數據集上，當k值過小時，學習算法的性能非常差，而在SEA數據集上，k值取為3反而保證了最好的模型質量.對比這兩個數據集的描述信息，不難發現：Powersupply數據集包含24個類別，而SEA數據集只有兩個類別.由于局部的結構特征可表示為類簇中的每類樣本占比，因此，在類別數較多的數據集上，若聚類數設置的過小，則不能充分描述數據的結構，進而導致結構特征的提取缺乏精確性，從而降低學習算法的性能；而在類別數較少的數據集上，若聚類數設置的過大，又會導致對數據深層內在結構的過份解讀，同樣會影響算法的泛化性能.建議在實際應用中，根據數據中的具體類別數來設置對應的k值.

2.5 運行時間比較

測試各種比較算法在每個數據集上運行時間，結果可參見表4.

表4 各種算法的運行時間比較

從表4的結果可以看出：

(1)IncreOnly算法最為省時，原因在于該算法只實現了學習模型的動態更新，而省略了所有中間的處理步驟.

(2)相比于除IncreOnly外的其它算法，IncreForg算法通常都要更為省時，這與該算法采用固定遺忘系數，而未采用概念漂移檢測模塊有關.

(3)增量離散化和增量聚類都是較為耗時的數據處理過程.比較IncreDisc 和IncreExtra算法的運行時間結果，不難發現：當數據中的特征數較多時(如HyperPlane，electricity和noaa數據集)，增量離散化要普遍比增量聚類更耗時，而當數據中的特征數很少時，增量離散化通常要比增量聚類更省時.

(4)用于建模的特征向量的長短也會直接影響到算法的時間復雜度.特征向量越長，所需的運行時間往往也會越多，該結論可通過比較IncreDisc 和 IncreMix算法的運行時間結果直接得出.

(5)文中所提兩種算法中，IncreFull-IDAW顯然要比IncreFull-IDA更耗時.這是因為二者對離散區間的跟蹤密度不同，IncreFull-IDAW算法每接收到一個新樣本時，均會對離散區間進行跟蹤，而IncreFull-IDA算法則是間歇性的隨機跟蹤.在實際應用中，若對實時性的需求很高，建議采用IncreFull-IDA算法，而若對實時性要求不高，則建議采用IncreFull-IDAW算法.

3 結論

利用流數據的特征結構不變性，文中提出了一種在線學習概念漂移自適應算法.通過理論分析與比較實驗，得出以下結論：

(1)通過融合流數據的結構不變性特征，在線學習模型往往能獲得比采用遺忘機制的模型更好的概念漂移自適應性及更優的分類性能.

(2)相比于傳統的基于遺忘機制的在線學習模型，文中算法的時間復雜度并無顯著增加，可以適應各類實際在線學習應用場景的需求.