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

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

在線學(xué)習(xí)(online learning)，又稱數(shù)據(jù)流學(xué)習(xí)(learning from data stream)，是機(jī)器學(xué)習(xí)領(lǐng)域的重要研究分支之一[1].所謂在線學(xué)習(xí)，是指數(shù)據(jù)的獲取不是一次性的，而是隨著時間不斷動態(tài)累加的.當(dāng)前，隨著移動互聯(lián)網(wǎng)與物聯(lián)網(wǎng)等技術(shù)的高速發(fā)展，在線學(xué)習(xí)在智能交通[2]、市場分析[3]、網(wǎng)絡(luò)安全[4]，乃至更多的應(yīng)用領(lǐng)域都存在著廣泛的應(yīng)用價值.

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

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

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

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

1 研究方法

1.1 增量離散化

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

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

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

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函數(shù)用于搜尋初始斷點，劃分容器；DetectDiscretization函數(shù)用于將原始的連續(xù)型屬性值轉(zhuǎn)化為對應(yīng)的離散化值；UpdateSamples函數(shù)負(fù)責(zé)新樣例對保留樣例集V的更新；而InsertValue函數(shù)用于更新斷點序列，并完成對新樣例的離散化.

1.2 增量聚類

聚類技術(shù)是機(jī)器學(xué)習(xí)與數(shù)據(jù)挖掘領(lǐng)域的重要組成部分之一，有助于發(fā)現(xiàn)數(shù)據(jù)潛在的內(nèi)在結(jié)構(gòu)[17].其中K-means[18]最為經(jīng)典.

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

(1)

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

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

(2)

式中：n為類簇cj中原有的樣本數(shù).

文中提出的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函數(shù)在初始的S個樣本上執(zhí)行聚類，并為其分配類簇標(biāo)記cl1～cls，生成各類簇質(zhì)心ω1～ωk，以及統(tǒng)計各類簇中初始的樣本數(shù)P1～Pk.在在線學(xué)習(xí)過程中，新接收的樣例將會不斷更新ω和P的取值.考慮到IncrementalKmeans算法運行于IDA或IDAW算法所構(gòu)造的離散特征空間之上，故特征空間的穩(wěn)定性可以得到有效保障，這也將有助于搜尋到數(shù)據(jù)真實的潛在內(nèi)部結(jié)構(gòu).

1.3 結(jié)構(gòu)特征抽取

在發(fā)現(xiàn)數(shù)據(jù)潛在內(nèi)部結(jié)構(gòu)的基礎(chǔ)上，對結(jié)構(gòu)進(jìn)行描述，并進(jìn)一步生成可量化的結(jié)構(gòu)特征兩方面入手：一方面提取能反應(yīng)數(shù)據(jù)內(nèi)部結(jié)構(gòu)的全局描述特征，另一方面則充分利用聚類信息提取局部描述特征.

(3)

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

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

圖1 結(jié)構(gòu)特征抽取過程

1.4 在線序列極限學(xué)習(xí)機(jī)

樣本在經(jīng)過維度擴(kuò)增后，需要輸入分類器進(jìn)行學(xué)習(xí)和訓(xùn)練.文中采用單隱層前饋神經(jīng)網(wǎng)絡(luò)(single-hidden-layer feedback neural networks，SLFNs)作為分類模型，其優(yōu)點在于可以以任意精度近似任意的非線性函數(shù).圖2為SLFNs的結(jié)構(gòu).

圖2 單隱層前饋神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)

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

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

Hβ=T

(4)

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

(5)

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

對于在線學(xué)習(xí)，文獻(xiàn)[15]基于ELM提出了一種在線序列極限學(xué)習(xí)機(jī)OS-ELM算法，該算法采用遞歸最小二乘策略擬合新接收的數(shù)據(jù).通過大量理論推導(dǎo)，得出輸出權(quán)重矩陣的更新規(guī)則為：

(6)

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

(7)

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

(8)

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

1.5 文中算法

文中算法整合了增量離散化、增量聚類、結(jié)構(gòu)特征抽取及在線序列極限學(xué)習(xí)機(jī)等技術(shù)，實現(xiàn)了在線學(xué)習(xí)對概念漂移的自適應(yīng).其中，增量離散化和增量聚類用于跟蹤特征空間的變化，結(jié)構(gòu)特征抽取用于適應(yīng)概念漂移，在線序列極限學(xué)習(xí)機(jī)用于實現(xiàn)學(xué)習(xí)模型的動態(tài)更新.

文中提出的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函數(shù)用于抽取結(jié)構(gòu)特征，InitialElm、Elm及OsElm函數(shù)則分別用于訓(xùn)練初始的學(xué)習(xí)模型，對新接收的數(shù)據(jù)進(jìn)行預(yù)測及在接收到新數(shù)據(jù)時，對學(xué)習(xí)模型進(jìn)行更新，而Θ則用于存儲樣本的預(yù)測類標(biāo)，可通過與真實類標(biāo)序列t的比較，計算出分類的精度.

2 實驗結(jié)果與討論

2.1 數(shù)據(jù)集

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

表1 數(shù)據(jù)集描述

2.2 實驗設(shè)置

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

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

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

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

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

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

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

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

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

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

2.3 結(jié)果分析

表3給出了各種比較算法的實驗結(jié)果，評價指標(biāo)為分類精度，其中，在每個數(shù)據(jù)集上，表現(xiàn)最好的算法所對應(yīng)的實驗結(jié)果已經(jīng)做了加粗處理.

表3 各種算法的實驗比較結(jié)果

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

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

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

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

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

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

2.4 參數(shù)討論

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

圖3 文中算法隨參數(shù)m與k的變化而產(chǎn)生的性能

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

2.5 運行時間比較

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

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

從表4的結(jié)果可以看出：

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

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

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

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

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

3 結(jié)論

利用流數(shù)據(jù)的特征結(jié)構(gòu)不變性，文中提出了一種在線學(xué)習(xí)概念漂移自適應(yīng)算法.通過理論分析與比較實驗，得出以下結(jié)論：

(1)通過融合流數(shù)據(jù)的結(jié)構(gòu)不變性特征，在線學(xué)習(xí)模型往往能獲得比采用遺忘機(jī)制的模型更好的概念漂移自適應(yīng)性及更優(yōu)的分類性能.

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