韋 磊, 姜海富, 于化龍,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)策略,要具有更好的性能.
離散化(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ù)用于更新斷點序列,并完成對新樣例的離散化.
聚類技術(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).
在發(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)特征抽取過程
樣本在經(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ò)模型.
文中算法整合了增量離散化、增量聚類、結(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的比較,計算出分類的精度.
采用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ù)集描述
實驗采用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é)果.
表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策略對所有的概念漂移類型均適用.
文中算法中,有兩個重要的參數(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值.
測試各種比較算法在每個數(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算法.
利用流數(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)用場景的需求.