韓明明，孫廣路+，朱素霞

1.哈爾濱理工大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，哈爾濱150080

2.哈爾濱理工大學(xué) 信息安全與智能技術(shù)研究中心，哈爾濱150080

1 引言

數(shù)據(jù)流是數(shù)據(jù)最常見的形式之一，通常數(shù)據(jù)流具有非平穩(wěn)特性，容易發(fā)生概念漂移，從而導(dǎo)致機器學(xué)習(xí)模型的性能隨著概念漂移的發(fā)生而不斷降低，如何處理概念漂移問題是數(shù)據(jù)流學(xué)習(xí)中的關(guān)鍵問題[1-3]。由于數(shù)據(jù)流是快速持續(xù)到達的，在分類器學(xué)習(xí)過程中要求對每個樣本只進行一次處理，對內(nèi)存使用和處理時間上也提出更高的要求[4]。此外還要求更新現(xiàn)有分類器以適應(yīng)新概念的同時又不影響對舊數(shù)據(jù)的分類性能，這就造成了“穩(wěn)定性-可塑性困境”[5]。

集成分類器可以選擇性地刪除或添加弱分類器，比較適合處理概念漂移問題，依據(jù)每次輸入樣本數(shù)量不同，集成算法可分為在線學(xué)習(xí)和批量學(xué)習(xí)兩類，在線學(xué)習(xí)每次處理一個樣本，而批量學(xué)習(xí)每次處理一個數(shù)據(jù)塊，數(shù)據(jù)塊包含多個樣本。

典型的批量學(xué)習(xí)集成算法，當(dāng)一個新的數(shù)據(jù)塊到達后，首先用新數(shù)據(jù)塊評估已有的弱分類器，然后用新數(shù)據(jù)塊訓(xùn)練一個新的弱分類器并替換最差的弱分類器。SEA（streaming ensemble algorithm）[6]算法是最早被提出用于解決概念漂移的自適應(yīng)批量學(xué)習(xí)集成算法。AWE（accuracy weighted ensemble）[7]算法在SEA算法基礎(chǔ)上為弱分類器依據(jù)預(yù)測錯誤率進行加權(quán)，但是其難以調(diào)整數(shù)據(jù)塊的大小，從而在對漂移的快速反應(yīng)和概念穩(wěn)定期的高精度之間做出折衷，確定數(shù)據(jù)塊包含的樣本數(shù)量是概念漂移下批量學(xué)習(xí)算法的關(guān)鍵問題[8]。AUE2（accuracy updated ensemble）[1]算法通過引入弱分類器的增量訓(xùn)練有效避免了數(shù)據(jù)塊大小對分類器性能的影響，但AUE2算法也存在著問題：

（1）AUE2算法缺少增強弱分類器多樣性的處理方式，每次都用相同的數(shù)據(jù)塊對已有的所有弱分類器增量訓(xùn)練，而文獻[9-11]的研究證明，多樣性較高的集成分類器在漂移發(fā)生后的表現(xiàn)通常比多樣性低的集成分類器表現(xiàn)更好。

（2）AUE2 算法每次處理一個新數(shù)據(jù)塊時，首先基于弱分類器對數(shù)據(jù)塊的預(yù)測誤差更新權(quán)重，然后對弱分類器進行增量訓(xùn)練，且新弱分類器的權(quán)重是基于隨機分類器確定的。這種情況下，弱分類器權(quán)重在增量訓(xùn)練之前已經(jīng)確定，權(quán)重更新忽略了本輪增量訓(xùn)練過程對弱分類器產(chǎn)生的影響。

針對AUE2 集成算法所存在的問題，本文提出一種新的集成學(xué)習(xí)算法CIUE（concept-adaptive incremental update ensemble），主要作了如下改進：

（1）CIUE 在弱分類器增量更新過程中引入增強集成算法的思路，借鑒適用于多分類問題的集成算法AdaBoost.M1[12]的權(quán)重更新方式，在增量訓(xùn)練中動態(tài)修改樣本和弱分類器的權(quán)重，保證弱分類器的多樣性。

（2）每處理一個數(shù)據(jù)塊時，首先對弱分類器增量訓(xùn)練，然后基于訓(xùn)練誤差更新弱分類器權(quán)重，新弱分類器的權(quán)重也根據(jù)訓(xùn)練誤差計算。基于訓(xùn)練誤差的權(quán)重更新方式，依據(jù)弱分類器對新數(shù)據(jù)的學(xué)習(xí)情況來確定其權(quán)重，考慮到了本輪增量訓(xùn)練對弱分類器的影響。

2 相關(guān)工作

自概念漂移問題首次提出以來[13]，研究者對該問題進行了深入的研究并提出了很多針對概念漂移下的數(shù)據(jù)流學(xué)習(xí)算法，文獻[2-3，14-16]總結(jié)了近些年來概念漂移問題的研究成果。

數(shù)據(jù)流的概念漂移問題，會導(dǎo)致模型在測試數(shù)據(jù)上的泛化能力降低，以至于模型不可用。文獻[14]用更加規(guī)范的數(shù)學(xué)形式，從貝葉斯決策論角度對概念漂移問題進行闡述。文獻[17]從不同角度對概念漂移進行分類，比如從概念是否反復(fù)出現(xiàn)可分為周期性漂移和非周期性漂移；從漂移的速率可分為突變漂移和漸進漂移。

針對概念漂移問題的技術(shù)有不同的分類標準[16]，依據(jù)不同標準主要分為以下幾類：

（1）依據(jù)是否主動檢測概念漂移，可分為主動方法和被動方法；

（2）依據(jù)輸入樣本數(shù)量的不同，可分為在線學(xué)習(xí)和批量學(xué)習(xí)；

（3）依據(jù)弱分類器數(shù)量不同，可分為自適應(yīng)的基分類器和集成分類器。

同一個算法依據(jù)不同的標準往往可被劃分到不同類別中。

2.1 主動方法

主動方法使用一個漂移檢測器來檢測樣本是否發(fā)生概念漂移。DDM（drift detection method）[18]、EDDM（early drift detection method）[19]、STEPD（detection method using statistical testing）[20]、ADWIN（adaptive windowing）[21]、ADDM（adaptive sliding window based drift detection method）[22]等是主動方法的代表性算法。DDM 通過監(jiān)控分類器的錯誤率來檢測概念漂移，但該方法不擅長檢測漸進概念漂移。EDDM 對DDM進行改進以提高對漸變概念漂移的檢測能力。窗口技術(shù)是概念漂移檢測中常用的技術(shù)，窗口中包含一定數(shù)量的樣本。STEPD采用統(tǒng)計檢驗來檢測概念漂移，通過比較兩個不同滑動窗口的準確率指標來確定概念漂移，即全局準確率和最近的準確率。該方法的缺點是需要預(yù)先給定滑動窗口大小，如果窗口大小不合適，就會產(chǎn)生較多的誤報（false alarm）或者無法檢測到某些漂移（false negative）。ADWIN 引入動態(tài)大小窗口，基于霍爾丁界（Hoeffding bound）比較兩個子窗口之間的差異，以確定目標概念是否漂移。當(dāng)數(shù)據(jù)沒有明顯的變化時，算法自動增長窗口，否則自動收縮窗口。ADDM利用滑動窗口的熵作為變化指標，通過霍爾丁界動態(tài)確定滑動窗的大小，當(dāng)概念發(fā)生漂移時，ADDM 尋找確切時間戳重新訓(xùn)練分類器。

不難發(fā)現(xiàn)，主動方法關(guān)注的重點在于如何檢測漂移以及當(dāng)檢測到概念漂移后分類器如何處理。

2.2 被動方法

與主動方法不同，被動方法并不顯式地檢測漂移，而是不斷用新樣本更新分類器，以使分類器適應(yīng)概念漂移，即被動方法中的算法具有自適應(yīng)性。

2.2.1 自適應(yīng)的基分類器

理論上自適應(yīng)的基分類器是解決概念漂移問題的較為簡單的方法。Domingos 和Hulten[23]提出了一種基于霍爾丁界理論的快速決策樹學(xué)習(xí)算法（very fast decision tree，VFDT），又稱為霍爾丁樹（Hoeffding tree）。給定樣本流，第一批樣本被用來確定根節(jié)點，一旦確定了根屬性，那接下來的樣本就會傳遞到相應(yīng)的葉子節(jié)點上，并進行相應(yīng)屬性的選擇（信息增益或基尼指數(shù)），以此遞歸。VFDT 使用霍爾丁邊界來確定每個節(jié)點上的樣本數(shù)量達到多少時進行劃分，在樣本數(shù)n盡可能小的情況下，確保使用n個樣本選擇的屬性和使用無限樣本選擇的屬性是一致的，在高可信度下，VFDT系統(tǒng)所產(chǎn)生的決策樹能逐漸逼近由傳統(tǒng)的批處理模式所產(chǎn)生的決策樹。VFDT 不能用于解決概念漂移問題，為此Hulten等人[24]對其進行改進以適應(yīng)樣本隨時間變化的情況，提出CVFDT（concept-adaptive very fast decision tree）算法。

樸素貝葉斯分類器、最緊鄰算法具有天然的增量學(xué)習(xí)特性[25]。對于樸素貝葉斯算法，其類條件概率能夠隨著新樣本的到來而不斷更新，通過結(jié)合窗口技術(shù)，當(dāng)一個新樣本加入到窗口時，移除最老的樣本來加入遺忘機制，以適應(yīng)概念漂移。而最緊鄰算法通過動態(tài)更新參考樣本集合，能夠適用于變化的數(shù)據(jù)流學(xué)習(xí)問題。

2.2.2 集成分類器

相對于單個基分類器，集成分類器更加靈活，可以根據(jù)概念漂移的情況有選擇性地刪除或添加弱分類器，依據(jù)每次處理樣本數(shù)量的不同，將集成分類器分為在線學(xué)習(xí)集成和批量學(xué)習(xí)集成。

在線學(xué)習(xí)算法每次只處理一個樣本。Oza[26]提出的Online Bagging和Online Boosting是應(yīng)用于靜態(tài)環(huán)境下的在線學(xué)習(xí)集成算法，Bifet 等人[27]把Online Bagging 和ADWIN 算法結(jié)合提出ADWIN Bagging算法用于概念漂移下的在線學(xué)習(xí)。Bifet 等人[25]借鑒Online Bagging中對樣本的重采樣方法提出了適用于動態(tài)環(huán)境下的自適應(yīng)隨機森林算法（adaptive random forest，ARF）。Pocock 等人[28]在Online Boosting 的基礎(chǔ)上進行擴展提出ONSBoost（online non-stationary Boosting）算法來處理概念漂移。而Kolter和Maloof[29]提出的DWM（dynamic weighted majority）算法是經(jīng)典的概念漂移下在線學(xué)習(xí)集成算法，DWM 是WM（weighted majority）[30]算法的擴展，算法以單個樣本作為輸入，經(jīng)過一段時期后（處理了指定數(shù)量的樣本），如果弱分類器對樣本分類錯誤，則降低該弱分類器的權(quán)重（乘以一個小于1 的參數(shù)），否則權(quán)重不變，并根據(jù)權(quán)重決定是否要移除弱分類器并添加新的弱分類器。

與在線學(xué)習(xí)不同，批量學(xué)習(xí)算法每次處理一個數(shù)據(jù)塊，每個數(shù)據(jù)塊通常包含相同數(shù)量的多個樣本。

概念漂移下的批量集成學(xué)習(xí)算法可以追溯到由Street等人[6]提出的SEA算法，SEA算法以決策樹C4.5作為弱分類器，每當(dāng)有新數(shù)據(jù)塊到達后，首先用新數(shù)據(jù)塊作為測試集對已有的弱分類器進行評估，并用候選分類器替代集成中較差的弱分類器，然后用新數(shù)據(jù)塊訓(xùn)練一個分類器作為新的候選分類器，最后采用非加權(quán)多數(shù)投票方式組合各決策樹的預(yù)測結(jié)果。

Wang 等人[7]提出的AWE 算法，弱分類器根據(jù)對當(dāng)前訓(xùn)練數(shù)據(jù)的分類準確率進行加權(quán)。該算法以數(shù)據(jù)塊作為輸入并維護k個弱分類器，每次用新數(shù)據(jù)塊訓(xùn)練一個新分類器，如果弱分類器數(shù)量小于k，則將新分類器加入集成中，否則用新數(shù)據(jù)塊對已有的弱分類器進行評估，并用新的分類器替代權(quán)重最低的弱分類器組成新的集成，采用加權(quán)投票的方式整合弱分類器的預(yù)測結(jié)果。

基于AWE算法的分類器權(quán)重計算方式，Brzezinski等人[31]提出AUE算法，以解決AWE在處理突變概念漂移時表現(xiàn)較差的問題，該算法并不刪除舊分類器，而是每次從全部分類器中選出最好的k個分類器作為集成輸出。Brzezinski等人[1]在AUE的基礎(chǔ)上進一步提出AUE2算法，AUE2使用VFDT作為弱分類器，引入弱分類器增量訓(xùn)練的學(xué)習(xí)方式，每次用新弱分類器代替準確率最低的舊弱分類器。Brzezinski等人[8]進一步提出AUE2算法的線上學(xué)習(xí)版本OAUE（online accuracy updated ensemble），OAUE 算法每隔d個樣本更新弱分類器權(quán)重。

Learn++算法是由Polikar等人[32]提出的適用于靜態(tài)環(huán)境的集成學(xué)習(xí)算法。Learn++.NSE（nonstationary environments）[33]在Learn++的基礎(chǔ)上擴展而來以適應(yīng)動態(tài)環(huán)境下的概念漂移，該算法以數(shù)據(jù)塊為輸入，使用一個基于時間調(diào)整（time-adjusted）的損失函數(shù)來確保最近表現(xiàn)良好的弱分類器能獲得較高的權(quán)重，最近表現(xiàn)不好的弱分類器則獲得較低甚至是0的權(quán)重，集成并不刪除低權(quán)重的弱分類器，當(dāng)?shù)蜋?quán)重的分類器在未來某段時間表現(xiàn)良好又會被賦予較高的權(quán)重，這樣的一個好處是可以處理周期性的概念漂移。

KBS-Stream[34]在KBS（knowledge-based sampling）[35]的基礎(chǔ)上進行擴展以適應(yīng)概念漂移。該算法用一個LIFT值來衡量預(yù)測類標簽與真實類標簽之間的相關(guān)性，大于1的值表示正相關(guān)，并依據(jù)LIFT值來更新樣本權(quán)重。對新的數(shù)據(jù)塊，首先迭代作用于已有的弱分類器來更新樣本權(quán)重，在更新的權(quán)重基礎(chǔ)上訓(xùn)練新的弱分類器。KBS-Stream 每次生成兩個集成變體，一個是在已有的集成上添加新的弱分類器；另一個是將新的數(shù)據(jù)塊添加到前一個數(shù)據(jù)塊里，并以此為訓(xùn)練數(shù)據(jù)更新最新的弱分類器。當(dāng)下一個數(shù)據(jù)塊到達后，用新數(shù)據(jù)作為測試集從兩個變體中選擇最優(yōu)集成。

ADAIN[36]算法引入了一個權(quán)重映射函數(shù)，首先基于前一批數(shù)據(jù)及其權(quán)重來初始化新數(shù)據(jù)的初始權(quán)重，然后用新數(shù)據(jù)評估最新的弱分類器分類誤差，并更新訓(xùn)練樣本的權(quán)重，最后用新數(shù)據(jù)訓(xùn)練一個新的弱分類器。Chu等人[37]提出了Fast and Light Boosting算法，該算法以數(shù)據(jù)塊作為輸入，結(jié)合漂移檢測器，如果檢測到概念漂移則每個樣本的權(quán)重設(shè)為1；如果沒有檢測到概念漂移，則根據(jù)當(dāng)前集成的錯誤率和樣本是否被正確分類來為每個樣本設(shè)置權(quán)重；然后在此權(quán)重分布基礎(chǔ)上訓(xùn)練一個新弱分類器。

3 批量學(xué)習(xí)集成算法CIUE

為方便對算法進行描述，首先對問題進行符號化表示，用Di表示第i個數(shù)據(jù)塊，數(shù)據(jù)塊中包含n個樣本，分別為(x1,y1),(x2,y2),…,(xn,yn)，其中xi表示特征向量，yi表示類別標簽，目標是訓(xùn)練一個集成分類器E能夠?qū)颖菊_分類，其中集成E包含k個弱分類器h1,h2,…,hk。

同大多數(shù)算法一樣，CIUE 關(guān)注如何適應(yīng)突變漂移和漸變漂移。當(dāng)樣本發(fā)生突變漂移時，理論上分類器的分類準確率會出現(xiàn)驟降，這是很明顯的特征，因而突變漂移比較容易檢測；而對于漸變漂移，短時間內(nèi)分類器的準確率可能并沒有很明顯的變化，相較于突變漂移，漸變漂移比較難檢測，它適合用被動方法去解決。通過在每一輪迭代中刪除表現(xiàn)較差的弱分類器，增加用新數(shù)據(jù)訓(xùn)練的新弱分類器，充分利用集成分類器的靈活性來適應(yīng)概念的逐漸變化，這是很多集成算法所采用的方案。

為方便描述，首先給出CIUE 的總體框架如圖1所示。

Fig.1 Overall structure of CIUE圖1 CIUE的總體結(jié)構(gòu)

第2步中，依據(jù)評價指標將集成中不合格的弱分類器移到緩存中并從緩存中選擇合格的弱分類器加入集成；對已有的弱分類器篩選完成后，第4步中，對篩選出的弱分類器增量訓(xùn)練并根據(jù)訓(xùn)練誤差更新弱分類器權(quán)重；然后判斷當(dāng)前集成中包含的弱分類器數(shù)量n是否小于k，如果n小于k，則基于新數(shù)據(jù)塊及其權(quán)重進行重采樣獲得訓(xùn)練數(shù)據(jù)集，并訓(xùn)練一個新的弱分類器添加到集成中；第6 步中，通過加權(quán)投票的方式輸出集成分類器；第7步開始處理下一個數(shù)據(jù)塊。

3.1 弱分類器增量訓(xùn)練

CIUE 作為一個批量學(xué)習(xí)集成算法，使用較小的數(shù)據(jù)塊作為算法輸入，對弱分類器增量訓(xùn)練，同時考慮到弱分類器多樣性問題，在增量訓(xùn)練過程中動態(tài)修改樣本權(quán)重，基于權(quán)重有放回地重新采樣，以訓(xùn)練后續(xù)弱分類器并更新弱分類器權(quán)重。

在增量訓(xùn)練過程中，假設(shè)當(dāng)前集成E中已包含m個弱分類器h1,h2,…,hm，首先為每個樣本(xi,yi)賦予初始權(quán)重：

其中，|Dk|是數(shù)據(jù)塊Dk包含的樣本數(shù)。

計算樣本集Dk在弱分類器h1上的訓(xùn)練誤差：

其中，[h1(xi)≠yi]為判斷函數(shù)，如果h1(xi)≠yi成立則返回1，否則返回0。

樣本的權(quán)重更新為：

此時得到權(quán)重更新后的數(shù)據(jù)集Dk，根據(jù)權(quán)重有放回地重采樣得到訓(xùn)練數(shù)據(jù)集，用該數(shù)據(jù)集訓(xùn)練新的弱分類器hm+1：

計算新弱分類器hm+1在樣本集Dk上的加權(quán)錯誤率：

最后通過加權(quán)投票的方式整合弱分類器的預(yù)測結(jié)果作為集成的預(yù)測結(jié)果：

在增量訓(xùn)練過程中引入樣本權(quán)重，并根據(jù)前一個弱分類器對樣本的學(xué)習(xí)情況修改樣本的權(quán)重，減小前一個組建分類器正確分類的樣本的權(quán)重，增大前一個組建分類器錯誤分類的樣本的權(quán)重，保證了弱分類器的多樣性。

3.2 弱分類器的評價指標和緩存隊列

AdaBoost.M1 算法要求弱分類器的加權(quán)訓(xùn)練誤差ε≤1/2，訓(xùn)練過程中如果弱分類Ct的加權(quán)錯誤率εt＞1/2，則重新訓(xùn)練弱分類器Ct。動態(tài)環(huán)境下訓(xùn)練數(shù)據(jù)不斷變化，增量訓(xùn)練過程中ε＞1/2 的情況更為常見，尤其是突變漂移下受舊概念的影響，在舊數(shù)據(jù)上訓(xùn)練的弱分類器在用新數(shù)據(jù)塊進行增量訓(xùn)練過程中很容易出現(xiàn)ε＞1/2 的情況。為避免此類情況的出現(xiàn)，CIUE不僅在增量訓(xùn)練過程中對誤差進行控制，而且在增量訓(xùn)練前增加了對弱分類器篩選的過程。如果弱分類器對新數(shù)據(jù)塊的分類錯誤率大于1/2，則移除該分類器，相對于其他集成算法的弱分類器評價指標，這樣的做法對弱分類器的要求更嚴格。更嚴格的評價指標導(dǎo)致了每次移除的弱分類器數(shù)量是不固定的，如果概念比較穩(wěn)定則不移除或者移除較少的弱分類器；如果概念發(fā)生突變則會移除較多的弱分類器。

但是如果概念發(fā)生突變后又馬上恢復(fù)，即短暫突變漂移，那么在漂移點移除較多弱分類器顯然是不合適的，因為這些弱分類器很快會變得有用。為此，CIUE加入了一個弱分類器的緩存隊列，用于暫存從集成中移除的弱分類器，如果緩存已滿則遵循“先進先出”的原則刪除較早添加進隊列中的弱分類器后再將從集成中移除的弱分類器添加到隊列中，當(dāng)緩存中的弱分類器重新變得有用后會被再次加入到集成中。

3.3 偽代碼描述

算法1 描述了CIUE 算法的大體流程。第1 行，初始化集成和緩存隊列為空；第2 行至第23 行循環(huán)處理每一個到達的數(shù)據(jù)塊，每處理一個數(shù)據(jù)塊就在第22行以加權(quán)投票方式輸出一個集成分類器用于當(dāng)前數(shù)據(jù)流的分類。第3行初始化樣本權(quán)重；第4行從當(dāng)前集成中篩選出不合格的弱分類器并保存到ls中；此時，如果當(dāng)前集成的弱分類器小于k，則第6行從緩存隊列中選擇最多k-size(E)個滿足要求的弱分類器加入集成并從隊列中刪除這些弱分類器，如果隊列中滿足要求的弱分類器數(shù)大于k-size(E)，則選擇出準確率最高的k-size(E)個；第9 行至第12 行對集成中的弱分類器進行增量訓(xùn)練；第13 行判斷集成當(dāng)前包含的弱分類器數(shù)量，如果仍小于k，則添加一個新的弱分類器；第18行至第21行將ls中的弱分類器加入到緩存隊列中，如果隊列空間不足，則遵循“先進先出”的原則從隊列頭部移除指定數(shù)量的弱分類器后再將弱分類器添加到集成的尾部。

算法1CIUE算法

4 實驗評估

本文在多個實驗中對算法進行評估，以模擬不同類型變化的場景。本章將描述所有使用的數(shù)據(jù)集，討論實驗設(shè)置，并分析實驗結(jié)果。

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

大多數(shù)針對概念漂移的算法都使用兩類數(shù)據(jù)集進行實驗評估：人工數(shù)據(jù)（synthetic data）和真實數(shù)據(jù)（real data）。同大多數(shù)文獻一樣，本文用5個人工數(shù)據(jù)集和3個真實數(shù)據(jù)集進行實驗，并與其他算法進行比較。

實驗基于MOA（massive online analysis）[38]框架進行，MOA 是當(dāng)前用于數(shù)據(jù)流挖掘的最流行的開源框架，該框架提供了很多數(shù)據(jù)流生成器，本文所用的人工數(shù)據(jù)集都是使用MOA 框架生成的，而真實數(shù)據(jù)集是公開可用的。首先對各數(shù)據(jù)集進行簡要的描述。

SEA數(shù)據(jù)[6]：用SEA數(shù)據(jù)生成器創(chuàng)建一組包含突變概念漂移的數(shù)據(jù)集SEA-s，該數(shù)據(jù)集包含3 個數(shù)值型屬性x1、x2、x3和4 個類別標簽，每一組概念都通過兩個函數(shù)的和進行定義，其中第一個函數(shù)以x1作為自變量而第二個函數(shù)以x2作為輸入，x3是冗余屬性。隨機生成100 萬個樣本，每25 萬個樣本發(fā)生一次概念漂移，數(shù)據(jù)集包含10%的噪聲。

Hyp 數(shù)據(jù)[7]：Hyperplane 是數(shù)據(jù)流分類實驗中非常受歡迎的數(shù)據(jù)生成器，通過對每個連續(xù)樣本稍微旋轉(zhuǎn)決策邊界來引入增量式的概念漂移，用該數(shù)據(jù)生成器創(chuàng)建包含100 萬個樣本的數(shù)據(jù)集Hyp-s，每個樣本由10 個屬性組成，每產(chǎn)生一個樣本就修改權(quán)重使其變化0.001，數(shù)據(jù)集包含漸變漂移，除此之外該數(shù)據(jù)集還包含5%的噪聲。

LED 數(shù)據(jù)[39]：LED 是一個流行的人工數(shù)據(jù)集，由24 個二進制屬性組成，定義了在7 段LED 顯示器上顯示的數(shù)字。使用LED 數(shù)據(jù)生成器創(chuàng)建包含100 萬個樣本的數(shù)據(jù)集LED-m，該數(shù)據(jù)集包含兩組逐漸漂移的概念，兩組概念在50萬個樣本之后突然轉(zhuǎn)換。

RBF數(shù)據(jù)[1]：徑向基函數(shù)生成器會創(chuàng)建指定數(shù)量的漂移中心點，用該數(shù)據(jù)生成器創(chuàng)建兩組數(shù)據(jù)集RBF-b 和RBF-gr，每組數(shù)據(jù)集包含100 萬個樣本和4個類標簽，其中RBF-b 包含4 個非常短的突變漂移，而RBF-gr則包含4組循環(huán)出現(xiàn)的漸變漂移。

Elec 數(shù)據(jù)集[1]：Elec 數(shù)據(jù)集是來自澳大利亞新南威爾士州電力市場的真實數(shù)據(jù)集。在這個電力市場中，受到供求關(guān)系的影響，價格不是固定的。數(shù)據(jù)集包括45 312 個樣本，每個樣本由7 個屬性組成，任務(wù)為預(yù)測電價是上漲還是下跌。

Airlines 數(shù)據(jù)集[25]：Airlines 數(shù)據(jù)集的任務(wù)是預(yù)測給定的航班是否會延誤：延遲和非延遲。這個數(shù)據(jù)集包含539 383 條記錄，有7 個屬性（3 個數(shù)值屬性和4個標稱屬性）。

Cov 數(shù)據(jù)集[27]：CoverType 數(shù)據(jù)集的任務(wù)是預(yù)測某個區(qū)域的森林覆蓋類型，這個數(shù)據(jù)集包含581 012個實例、53個屬性和7個類標簽。

本文用人工數(shù)據(jù)集來衡量不同漂移類型下算法的表現(xiàn)，而對于真實的數(shù)據(jù)集，盡管不能明確地指出漂移發(fā)生的時間、漂移類型，但真實的數(shù)據(jù)集更能夠體現(xiàn)算法在真實場景中的性能。表1 總結(jié)了各個數(shù)據(jù)集的詳細信息。

Table 1 Characteristic of datasets表1 數(shù)據(jù)集特性

表1中，第2列為樣本數(shù)量（#I），第3列是屬性數(shù)量（#A），第4 列為類別標簽數(shù)量（#C），第5 列為噪音占總樣本數(shù)的百分比（N），第6列是數(shù)據(jù)集包含的漂移類型（T）。漂移類型S 代表突變漂移，G 代表漸變漂移，SS代表短暫突變漂移，而UN代表未知。

4.2 實驗設(shè)置和結(jié)果

實驗選取批量學(xué)習(xí)算法AWE、AUE2、NB（na?ve Bayes）以及在線學(xué)習(xí)算法DWM作為對比算法，其中樸素貝葉斯算法作為一個沒有漂移反映機制的算法被引入。AWE、樸素貝葉斯和DWM 在MOA 中都已實現(xiàn)，文獻[1]提供了AUE2算法的具體實現(xiàn)。

為了使比較更有意義，為所有算法設(shè)置相同的參數(shù)值。對于集成算法AUE2、AWE、DWM和CIUE，弱分類器采用霍爾丁樹，弱分類數(shù)量設(shè)置為10，數(shù)據(jù)塊大小統(tǒng)一設(shè)置為d=500，這個大小被認為是適合基于數(shù)據(jù)塊的集成的最小值[7]，盡管CIUE 可以使用更小的數(shù)據(jù)塊，實驗中依然采用這個值。霍爾丁樹的葉子節(jié)點的決策方式采用樸素貝葉斯，節(jié)點分裂的置信度δ=0.01，葉子節(jié)點在兩個分割嘗試間應(yīng)觀察的樣本數(shù)gracePeriod=100，其他參數(shù)設(shè)為默認值。此外，CIUE的緩存隊列大小設(shè)置為n=20。

所有的性能度量都基于數(shù)據(jù)塊計算，實驗過程采用test-then-train模式，在不進行處理的情況下緩存輸入的樣本，直到它們形成一個大小為d的數(shù)據(jù)塊，每個新的數(shù)據(jù)塊首先用于評估現(xiàn)有的分類器，然后更新分類器。

編碼統(tǒng)一采用Java 編程語言，JDK 版本為1.8.0-17，實驗在一臺裝備4 核i5-9300H 處理器和8 GB 內(nèi)存的PC機上進行。

實驗從分類精準率、內(nèi)存使用、塊訓(xùn)練時間和測試時間等方面對算法進行評價，表2～表5分別給出了上述性能指標的平均值。

Hyp-s 數(shù)據(jù)集上準確率最高的是AWE，其次是CIUE 和AUE2，而NB 和DWM 表現(xiàn)較差；其他數(shù)據(jù)集上CIUE的分類準確率都要優(yōu)于其他算法，尤其是在真實數(shù)據(jù)集上優(yōu)勢更明顯，比AUE2算法平均高出2～3 個百分點；比較出乎意料的是在Hyp-s 和SEA-s兩組數(shù)據(jù)上，沒有漂移反應(yīng)機制的NB分類器要好于DWM，除此之外，NB 都是分類準確率最低的；而在平均訓(xùn)練時間這一指標上，CIUE則是最耗時的算法，與之最接近的是AWE算法，CIUE的訓(xùn)練時間大概是AUE2 算法的3 倍左右；而在平均測試時間上，CIUE和AUE2基本相當(dāng)；在平均內(nèi)存使用上，NB毫無疑問是占用內(nèi)存最少的算法，其次是DWM 和AWE，而CIUE 和AUE2 比較占用內(nèi)存的算法，CIUE 大概是AUE2的3倍左右。

Table 2 Average classification accuracy表2 平均分類準確率 %

Table 4 Average chunk testing time表4 平均測試時間 ms

綜上可看出，CIUE 在各個數(shù)據(jù)集上的分類效果都表現(xiàn)很好，比AUE2 的分類精準率高，這是由于CIUE在弱分類器增量訓(xùn)練過程中保證了弱分類器的多樣性，且對弱分類器的性能要求更高，此外還加入了緩存隊列有效針對循環(huán)漂移和短暫性的突變漂移；準確率提高的代價是訓(xùn)練時間和內(nèi)存使用上的增加，增量訓(xùn)練過程中樣本權(quán)重的更新、基于權(quán)重的重采樣以及隊列的操作都增加了訓(xùn)練時間，而緩存隊列的存在占據(jù)了比集成更多的空間。

為更直觀地表現(xiàn)出各個算法在實驗過程中的分類效果，繪制了各個算法在3 組數(shù)據(jù)集RBF-gr、RBF-b和Cov上的分類準確率趨勢，如圖2、圖3和圖4所示。

從圖2 和圖3 中可以看到在RBF-gr 和RBF-b 數(shù)據(jù)集上，CIUE 和AUE2 準確率大體相當(dāng)，CIUE 略微好于AUE2，并且CIUE 和AUE2 都明顯好于其他算法；DWM和AWE的分類準確率較為接近，大部分時間AWE 都要略微強于DWM；NB 是最差的分類器，并且準確率隨著樣本的增加而下降。

Table 3 Average chunk training time表3 平均訓(xùn)練時間 ms

Table 5 Average memory usage表5 平均內(nèi)存使用 MB

Fig.2 Classification accuracy on RBF-gr圖2 數(shù)據(jù)集RBF-gr上的分類準確率

Fig.3 Classification accuracy on RBF-b圖3 數(shù)據(jù)集RBF-b上的分類準確率

Fig.4 Classification accuracy on Cov圖4 數(shù)據(jù)集Cov上的分類準確率

而從圖4 可以看出在Cov 數(shù)據(jù)集上，CIUE 是分類準確率最高的算法，其次是AUE2、DWM和AWE，NB 的準確率最低且遠遠低于其他算法；CIUE、AUE2、DWM 和AWE 算法在處理了1.00×105個樣本后準確率都趨于穩(wěn)定，NB則隨著樣本的增加準確率逐漸下降。

5 結(jié)束語

隨著概念漂移的發(fā)生，機器學(xué)習(xí)模型很難維持較高的分類性能。本文提出一種基于弱分類器增量訓(xùn)練的批量集成算法CIUE 用于動態(tài)環(huán)境下數(shù)據(jù)流的分類問題。該算法使用小數(shù)據(jù)塊增量訓(xùn)練弱分類器，并在增量訓(xùn)練過程中控制弱分類器的多樣性，動態(tài)修改弱分類器的權(quán)重，基于已有弱分類器對樣本的學(xué)習(xí)效果重采樣來訓(xùn)練新弱分類器，同時加入弱分類器緩存隊列以處理循環(huán)出現(xiàn)的概念。實驗結(jié)果表明，該算法能有效應(yīng)用于各種類型概念漂移下的數(shù)據(jù)流學(xué)習(xí)問題。CIUE 不需要復(fù)雜的參數(shù)，但是相對于其他算法，CIUE 需要更多的訓(xùn)練時間和內(nèi)存占用，如何在保證分類準確率的同時減少訓(xùn)練時間和內(nèi)存占用，是接下來要進行的工作。