自適應(yīng)概念漂移問(wèn)題的增量集成分類(lèi)算法*

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

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

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

1 引言

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

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

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

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

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

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

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

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

2 相關(guān)工作

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

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

針對(duì)概念漂移問(wèn)題的技術(shù)有不同的分類(lèi)標(biāo)準(zhǔn)[16]，依據(jù)不同標(biāo)準(zhǔn)主要分為以下幾類(lèi)：

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

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

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

同一個(gè)算法依據(jù)不同的標(biāo)準(zhǔn)往往可被劃分到不同類(lèi)別中。

2.1 主動(dòng)方法

主動(dòng)方法使用一個(gè)漂移檢測(cè)器來(lái)檢測(cè)樣本是否發(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]等是主動(dòng)方法的代表性算法。DDM 通過(guò)監(jiān)控分類(lèi)器的錯(cuò)誤率來(lái)檢測(cè)概念漂移，但該方法不擅長(zhǎng)檢測(cè)漸進(jìn)概念漂移。EDDM 對(duì)DDM進(jìn)行改進(jìn)以提高對(duì)漸變概念漂移的檢測(cè)能力。窗口技術(shù)是概念漂移檢測(cè)中常用的技術(shù)，窗口中包含一定數(shù)量的樣本。STEPD采用統(tǒng)計(jì)檢驗(yàn)來(lái)檢測(cè)概念漂移，通過(guò)比較兩個(gè)不同滑動(dòng)窗口的準(zhǔn)確率指標(biāo)來(lái)確定概念漂移，即全局準(zhǔn)確率和最近的準(zhǔn)確率。該方法的缺點(diǎn)是需要預(yù)先給定滑動(dòng)窗口大小，如果窗口大小不合適，就會(huì)產(chǎn)生較多的誤報(bào)（false alarm）或者無(wú)法檢測(cè)到某些漂移（false negative）。ADWIN 引入動(dòng)態(tài)大小窗口，基于霍爾丁界（Hoeffding bound）比較兩個(gè)子窗口之間的差異，以確定目標(biāo)概念是否漂移。當(dāng)數(shù)據(jù)沒(méi)有明顯的變化時(shí)，算法自動(dòng)增長(zhǎng)窗口，否則自動(dòng)收縮窗口。ADDM利用滑動(dòng)窗口的熵作為變化指標(biāo)，通過(guò)霍爾丁界動(dòng)態(tài)確定滑動(dòng)窗的大小，當(dāng)概念發(fā)生漂移時(shí)，ADDM 尋找確切時(shí)間戳重新訓(xùn)練分類(lèi)器。

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

2.2 被動(dòng)方法

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

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

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

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

2.2.2 集成分類(lèi)器

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.2 弱分類(lèi)器的評(píng)價(jià)指標(biāo)和緩存隊(duì)列

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

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

3.3 偽代碼描述

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

算法1CIUE算法

4 實(shí)驗(yàn)評(píng)估

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4.2 實(shí)驗(yàn)設(shè)置和結(jié)果

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

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

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

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

實(shí)驗(yàn)從分類(lèi)精準(zhǔn)率、內(nèi)存使用、塊訓(xùn)練時(shí)間和測(cè)試時(shí)間等方面對(duì)算法進(jìn)行評(píng)價(jià)，表2～表5分別給出了上述性能指標(biāo)的平均值。

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

Table 2 Average classification accuracy表2 平均分類(lèi)準(zhǔn)確率 %

Table 4 Average chunk testing time表4 平均測(cè)試時(shí)間 ms

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

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

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

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

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

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

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

Fig.4 Classification accuracy on Cov圖4 數(shù)據(jù)集Cov上的分類(lèi)準(zhǔn)確率

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

5 結(jié)束語(yǔ)

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