李春鵬 韓萌 孟凡興 何菲菲 張瑞華

摘 要：復(fù)雜數(shù)據(jù)流中所存在的概念漂移及不平衡問(wèn)題降低了分類器的性能。傳統(tǒng)的批量學(xué)習(xí)算法需要考慮內(nèi)存以及運(yùn)行時(shí)間等因素，在快速到達(dá)的海量數(shù)據(jù)流中性能并不突出，并且其中還包含著大量的漂移及類失衡現(xiàn)象，利用在線集成算法處理復(fù)雜數(shù)據(jù)流問(wèn)題已經(jīng)成為數(shù)據(jù)挖掘領(lǐng)域重要的研究課題。從集成策略的角度對(duì)bagging、boosting、stacking集成方法的在線版本進(jìn)行了介紹與總結(jié)，并對(duì)比了不同模型之間的性能。首次對(duì)復(fù)雜數(shù)據(jù)流的在線集成分類算法進(jìn)行了詳細(xì)的總結(jié)與分析，從主動(dòng)檢測(cè)和被動(dòng)自適應(yīng)兩個(gè)方面對(duì)概念漂移數(shù)據(jù)流檢測(cè)與分類算法進(jìn)行了介紹，從數(shù)據(jù)預(yù)處理和代價(jià)敏感兩個(gè)方面介紹不平衡數(shù)據(jù)流，并分析了代表性算法的時(shí)空效率，之后對(duì)使用相同數(shù)據(jù)集的算法性能進(jìn)行了對(duì)比。最后，針對(duì)復(fù)雜數(shù)據(jù)流在線集成分類研究領(lǐng)域的挑戰(zhàn)提出了下一步研究方向。

關(guān)鍵詞：在線學(xué)習(xí)；集成學(xué)習(xí)；概念漂移；不平衡

中圖分類號(hào)：TP391?? 文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001-3695（2024）03-001-0641-11

doi：10.19734/j.issn.1001-3695.2023.06.0291

Survey of online ensemble classification algorithms for complex data streams

Li Chunpeng，Han Meng，Meng Fanxing，He Feifei，Zhang Ruihua

（School of Computer Science & Engineering，North Minzu University，Yinchuan 750021，China）

Abstract：The concept drift and imbalance problems in complex data streams reduce the performance of classifiers.Traditional batch learning algorithms need to consider factors such as memory and runtime，but their performance is not outstanding in ra-pidly arriving massive data streams，and they also contain a large number of drift and class imbalance phenomena.Utilizing online ensemble algorithms to handle complex data stream problems has become an important research topic in the field of data mining.Firstly，this paper introduced and summarized the online versions of bagging，boosting，and stacking ensemble methods from the perspective of ensemble strategies，and compared the performance of different models.Secondly，this paper conducted a detailed summary and analysis of online ensemble classification algorithms for complex data streams for the first time.This paper introduced conceptual drift data stream detection and classification algorithms from two aspects：active detection and passive adaptation.This paper introduced unbalanced data streams from two aspects：data preprocessing and cost sensitivity.This paper analyzed the spatiotemporal efficiency of representative algorithms，and then compared the performance of algorithms using the same dataset.Finally，this paper proposed the next research direction in response to the challenges in the field of online ensemble classification of complex data streams.

Key words：online learning；ensemble learning；concept drift；imbalance

0 引言

現(xiàn)代數(shù)據(jù)有兩個(gè)關(guān)鍵特征：無(wú)限到達(dá)的數(shù)據(jù)、不斷增長(zhǎng)的速度以及不斷變化的數(shù)據(jù)性質(zhì)，這兩個(gè)因素的結(jié)合產(chǎn)生了數(shù)據(jù)流的概念。數(shù)據(jù)流會(huì)隨著時(shí)間的推移而演變，其特征和定義也會(huì)發(fā)生變化，此外，數(shù)據(jù)流的初始分布可能會(huì)呈現(xiàn)出極不平衡的狀態(tài)。復(fù)雜數(shù)據(jù)流中所存在的這兩種現(xiàn)象分別被稱為概念漂移和類不平衡，目前已成為數(shù)據(jù)流學(xué)習(xí)中的關(guān)鍵問(wèn)題。風(fēng)險(xiǎn)管理［1］、異常檢測(cè)［2］和社交媒體挖掘［3］等各個(gè)領(lǐng)域的應(yīng)用都受到概念漂移和類不平衡的影響。傳統(tǒng)的批量學(xué)習(xí)方法（如ID3、C4.5等經(jīng)典決策樹(shù)算法）在學(xué)習(xí)海量數(shù)據(jù)流時(shí)存在內(nèi)存存儲(chǔ)問(wèn)題，并且無(wú)法根據(jù)新實(shí)例在舊模型的基礎(chǔ)上進(jìn)行增量更新。而在線學(xué)習(xí)［4］用于對(duì)按順序到達(dá)的數(shù)據(jù)進(jìn)行學(xué)習(xí)，無(wú)須將整個(gè)數(shù)據(jù)保存在內(nèi)存中，這種方法適用于挖掘高速生成的大量數(shù)據(jù)。

集成方法［5］通過(guò)將多個(gè)弱分類器組合成一個(gè)較強(qiáng)的分類器，往往能夠取得比單個(gè)分類器更好的性能。在數(shù)據(jù)流集成分類領(lǐng)域中，集成方法通?？煞譃榛趬K的集成和在線集成?；趬K的模型在處理時(shí)變數(shù)據(jù)流時(shí)適應(yīng)性較差，而在線模型則在準(zhǔn)確度和內(nèi)存等方面具有顯著優(yōu)勢(shì)。在線集成方法因其良好的時(shí)空效率和預(yù)測(cè)性能而得到研究人員的廣泛關(guān)注，圖1給出了在線集成分類模型的概述圖。Oza等人［6］將批量模式下的bagging和boosting算法推廣到在線版本，在測(cè)試大量連續(xù)到達(dá)的數(shù)據(jù)流時(shí)表現(xiàn)良好，非常適合實(shí)際應(yīng)用。Santos等人［7］基于在線boosting算法并進(jìn)行改進(jìn)，增加對(duì)困難分類實(shí)例的關(guān)注并根據(jù)當(dāng)前分類器的預(yù)測(cè)結(jié)果動(dòng)態(tài)選擇后續(xù)分類器，加快了集成模型從概念漂移中恢復(fù)的速度。Wang等人［8］將重采樣技術(shù)與在線bagging算法結(jié)合起來(lái)，并通過(guò)動(dòng)態(tài)捕捉失衡率對(duì)數(shù)據(jù)進(jìn)行再平衡，以解決數(shù)據(jù)流中的類不平衡問(wèn)題。

在現(xiàn)有的數(shù)據(jù)流集成分類研究成果中，大多數(shù)綜述都集中在集成學(xué)習(xí)或在線學(xué)習(xí)方面進(jìn)行研究。Gomes等人［9］基于多樣性、基分類器和集成方式的不同來(lái)總結(jié)集成相關(guān)技術(shù)。杜詩(shī)語(yǔ)等人［10］重點(diǎn)分析了突變型、漸變型、重復(fù)型和增量型概念漂移集成分類算法。張喜龍等人［11］ 從復(fù)雜數(shù)據(jù)流和領(lǐng)域數(shù)據(jù)流的角度重點(diǎn)介紹了當(dāng)前算法的核心思想和性能。Mienye等人［12］總結(jié)了bagging、boosting和stacking三種主要的集成方法，并總結(jié)了它們的數(shù)學(xué)和算法表示。Hoi等人［4］基于模型對(duì)學(xué)習(xí)器的反饋類型對(duì)在線學(xué)習(xí)算法進(jìn)行了分類總結(jié)。文獻(xiàn)［13］介紹了在線學(xué)習(xí)的基本框架和性能評(píng)估方法。在目前的研究中，還未有對(duì)復(fù)雜數(shù)據(jù)流的在線集成分類方法進(jìn)行介紹的綜述。

本文對(duì)近年來(lái)所提出的在線集成分類方法進(jìn)行了匯總，然后從集成策略的不同以及針對(duì)不同數(shù)據(jù)流對(duì)象所應(yīng)用的集成技術(shù)對(duì)在線集成分類算法進(jìn)行了詳細(xì)的描述和分析，本文的框架結(jié)構(gòu)如圖2所示，主要貢獻(xiàn)如下：

a）首次對(duì)在線集成分類算法進(jìn)行了詳細(xì)的介紹，包括online bagging、online boosting及online stacking等經(jīng)典模型及其最新變體，同時(shí)對(duì)提出模型進(jìn)行總結(jié)與比較。

b）對(duì)概念漂移數(shù)據(jù)流及不平衡數(shù)據(jù)流的在線集成分類方法進(jìn)行了詳細(xì)的闡述與分析，并對(duì)代表性算法進(jìn)行了時(shí)空復(fù)雜度的分析。

c）在使用同一數(shù)據(jù)集的條件下，對(duì)在線集成分類算法性能的實(shí)驗(yàn)結(jié)果進(jìn)行了分析與對(duì)比。

1 在線集成策略

在線集成學(xué)習(xí)方法對(duì)新到達(dá)的實(shí)例逐個(gè)進(jìn)行處理，是一種增量學(xué)習(xí)方法。裝袋（bagging）、提升（boosting）和堆疊（stacking）等是改進(jìn)單分類器性能的經(jīng)典集成方法［12］，同時(shí)研究人員們也提出了它們的在線版本及變體，以適應(yīng)不斷變化的數(shù)據(jù)流。本章主要從集成策略的在線版本進(jìn)行總結(jié)與比較。

1.1 bagging

標(biāo)準(zhǔn)的批量bagging方法是從原始樣本集中進(jìn)行抽樣，通過(guò)N輪抽取得到相應(yīng)的訓(xùn)練集，并通過(guò)訓(xùn)練得到N個(gè)模型。對(duì)于測(cè)試集的分類結(jié)果，由這些模型采用投票的方式來(lái)決定。最經(jīng)典的在線bagging算法是Oza等人［6］提出的OzaBag算法，該算法通過(guò)泊松分布來(lái)模擬批量環(huán)境，首先將集成分類器中的基分類器數(shù)量設(shè)置為N。對(duì)于每個(gè)新到達(dá)的實(shí)例d，根據(jù)泊松分布k-poisson（1），然后重復(fù)以下過(guò)程k次：將樣本d添加到訓(xùn)練集中，并用新的訓(xùn)練集更新所有的基分類器。最后，采用多數(shù)投票原則對(duì)新實(shí)例進(jìn)行預(yù)測(cè)。OzaBag算法過(guò)程如圖3所示。

2009年，Bifet等人［14］對(duì)OzaBag方法作出改進(jìn)，提出了ADWIN bagging（ADWINBag）和自適應(yīng)大小Hoeffding樹(shù)bagging（ASHTBag）兩種bagging變體。ADWINBag通過(guò)使用ADWIN作為漂移檢測(cè)器來(lái)決定何時(shí)丟棄表現(xiàn)不佳的集合成員，當(dāng)檢測(cè)到漂移時(shí)，進(jìn)行分類器的刪除與替換。ASHTBag使用不同大小的Hoeffding樹(shù)作為其組件分類器，同時(shí)利用 OzaBag 的重采樣方法使得每棵樹(shù)運(yùn)行在不同的實(shí)例集合上，通過(guò)增加樹(shù)的多樣性來(lái)提高bagging集成的性能。2010年，Bifet等人［15］又基于OzaBag算法，提出了LevBag（leverage bagging），將bagging采樣的泊松分布參數(shù)從固定值1改為較大的λ，從而增加了基分類器輸入的隨機(jī)性，以提高集成分類器的準(zhǔn)確性。

近年來(lái)，隨著機(jī)器學(xué)習(xí)技術(shù)的不斷發(fā)展，研究人員將各種方法與在線bagging相結(jié)合以提高分類器集成的整體性能，來(lái)處理不同環(huán)境下的學(xué)習(xí)任務(wù)。SMOTE-OB［16］將在線bagging算法和SMOTE［17］合成少數(shù)過(guò)采樣技術(shù)結(jié)合起來(lái)，通過(guò)使用隨機(jī)特征子集及利用在線bagging泊松分布中的概率更新實(shí)例，使其基分類器多樣化。進(jìn)化模糊系統(tǒng)（EFS）［18］可以在在線過(guò)程中以增量的方式從動(dòng)態(tài)數(shù)據(jù)中學(xué)習(xí)，Lughofer等人［19］結(jié)合EFS提出了一種新的自適應(yīng)在線集成變體，稱為在線袋裝EFS（OB-EFS），并采用兩種修剪策略對(duì)集成成員進(jìn)行動(dòng)態(tài)修剪，可以很好地處理漸進(jìn)和循環(huán)漂移。

在使用bagging方法進(jìn)行模型集成時(shí)，基模型可以是任意模型，當(dāng)基模型為決策樹(shù)時(shí)，集成模型即被稱之為隨機(jī)森林（random forest，RF），它是bagging的擴(kuò)展變體。在線隨機(jī)森林（online random forest，ORF）［20］通過(guò)連續(xù)在線bagging采樣將新的子節(jié)點(diǎn)從父節(jié)點(diǎn)中分離出來(lái)，最終可以獲得與傳統(tǒng)RF相當(dāng)?shù)男阅?。王?ài)平等人［21］提出了一種增量式極端隨機(jī)森林分類器（incremental extremely random forest，IERF），用于處理小樣本數(shù)據(jù)流的在線學(xué)習(xí)問(wèn)題。IERF算法通過(guò) Gini系數(shù)來(lái)確定是否對(duì)當(dāng)前葉節(jié)點(diǎn)進(jìn)行分裂擴(kuò)展，能夠快速高效地完成分類器的增量構(gòu)造。文獻(xiàn)［22］提出了自適應(yīng)隨機(jī)森林（adaptive random forest，ARF），ARF是對(duì)經(jīng)典隨機(jī)森林算法的改編。ARF 基于在線bagging的重采樣方法和自適應(yīng)策略來(lái)應(yīng)對(duì)不斷變化的數(shù)據(jù)流。該策略對(duì)每棵樹(shù)使用漂移監(jiān)視器來(lái)跟蹤警告和漂移，并用于集成替換。

在線bagging由于其弱分類器投票組合的簡(jiǎn)易性以及對(duì)新實(shí)例的泊松重采樣理論，經(jīng)常與其他數(shù)據(jù)重采樣技術(shù)相結(jié)合，用于處理不平衡數(shù)據(jù)，詳細(xì)的內(nèi)容將在第2章進(jìn)行描述。

1.2 boosting

傳統(tǒng)的批量boosting算法與bagging算法類似，但不同于bagging的并行學(xué)習(xí)，boosting是一種序列化的集成方法。它通過(guò)迭代地訓(xùn)練一組弱分類器（例如決策樹(shù)）來(lái)構(gòu)建一個(gè)強(qiáng)分類器。在每次迭代中，boosting算法根據(jù)先前分類器的表現(xiàn)來(lái)調(diào)整樣本的權(quán)重，將更多的關(guān)注放在分類錯(cuò)誤的樣本，逐步提高對(duì)難以分類的樣本的預(yù)測(cè)準(zhǔn)確性。OzaBoost［6］通過(guò)泊松分布參數(shù)確定實(shí)例的權(quán)重，該算法通過(guò)式（1）對(duì)實(shí)例權(quán)重進(jìn)行調(diào)整。

λscm=λscm+λdλd←λd（N2λscm），correct

λswm=λswm+λdλd←λd（N2λswm），wrong（1）

其中：λd表示新實(shí)例d的權(quán)重；N表示目前為止訓(xùn)練的實(shí)例總數(shù)；λscm表示第m階段正確分類的實(shí)例之和；λswm表示錯(cuò)誤分類實(shí)例的和。最后通過(guò)分類器的錯(cuò)誤率進(jìn)行加權(quán)投票得到預(yù)測(cè)結(jié)果。隨著新實(shí)例的到來(lái)不斷調(diào)節(jié)弱分類器的參數(shù)，使分類正確率高的分類器有較高的權(quán)重。

OzaBoost基于累積權(quán)重分配實(shí)例，一些研究者基于此進(jìn)一步提出了其他算法。基于自適應(yīng)多樣性的在線增強(qiáng)算法（adaptable diversity-based online boosting，ADOB）［7］，是OzaBoost的改進(jìn)版本，ADOB相對(duì)于OzaBoost來(lái)說(shuō)最值得關(guān)注的地方在于，它在處理每個(gè)實(shí)例之前根據(jù)準(zhǔn)確度對(duì)分類器進(jìn)行升序排序，并通過(guò)分類器的預(yù)測(cè)結(jié)果動(dòng)態(tài)選擇后續(xù)分類器?；趩l(fā)式修改的類boosting在線學(xué)習(xí)集成（boosting-like online learning ensemble，BOLE）［23］，是對(duì)ADOB算法的改進(jìn)，該方法削弱了分類器的錯(cuò)誤率閾值以使更多的分類器參與投票，并改變所使用的概念漂移檢測(cè)方法，經(jīng)實(shí)證研究在大多數(shù)測(cè)試情況下，準(zhǔn)確性得到了提高。文獻(xiàn)［24］提出了兩個(gè)在線版本的boosting，第一個(gè)是基于AdaBoost的在線M1算法（OABM1），負(fù)責(zé)更新權(quán)重的函數(shù)被修改為類似于傳統(tǒng)boosting中的相應(yīng)函數(shù)。第二種方法名為基于AdaBoost在線M2算法（OABM2），旨在處理多類問(wèn)題，因?yàn)榛贏daBoost M1的版本在此類場(chǎng)景中會(huì)受到限制。結(jié)果表明這兩種方法在不同環(huán)境下均具有良好的性能。

由于基于累積權(quán)重的實(shí)例分配方案容易受到噪聲等數(shù)據(jù)困難因素的影響而降低集成性能，所以基于分類器性能反饋的方案被研究者所提出。Baidari等人［25］在ADOB的基礎(chǔ)上，提出了基于準(zhǔn)確率加權(quán)多樣性的在線提升（accuracy weighted diversity-based online boosting，AWDOB）方法，引入了一種加權(quán)方案，使用分類器的準(zhǔn)確率為數(shù)據(jù)流中的當(dāng)前實(shí)例分配當(dāng)前分類器權(quán)重，這些改進(jìn)和新定義的加權(quán)方案提高了集成的整體精度。最近，Honnikoll 等人［26］提出了平均錯(cuò)誤率加權(quán)在線提升方法（mean error rate weighted online boosting，MWOB），該算法利用個(gè)體基分類器的平均錯(cuò)誤率來(lái)實(shí)現(xiàn)實(shí)例的有效權(quán)重分布，而不是OzaBoost中基于弱分類器之前的累積權(quán)重，MWOB在實(shí)驗(yàn)數(shù)據(jù)集上均取得了最佳的預(yù)測(cè)性能。

在線boosting算法中最值得注意的地方就是如何對(duì)訓(xùn)練實(shí)例進(jìn)行有效的權(quán)重分布，以達(dá)到良好的分類器性能。傳統(tǒng)算法通過(guò)前件分類器的預(yù)測(cè)結(jié)果對(duì)實(shí)例進(jìn)行相應(yīng)的權(quán)重分配，但是這種方式很容易受到噪聲影響。對(duì)于實(shí)例權(quán)重分配的研究一直是boosting集成中的一大熱點(diǎn)。

1.3 stacking

stacking是集成學(xué)習(xí)的第三類，大部分集成模型如bagging、boosting都通過(guò)一個(gè)基礎(chǔ)學(xué)習(xí)算法來(lái)生成同質(zhì)的基學(xué)習(xí)器，即同構(gòu)集成，而stacking為異構(gòu)集成，基礎(chǔ)模型通常包含不同的學(xué)習(xí)算法。stacking集成由兩個(gè)級(jí)別組成：基分類器和元分類器（meta-classifier，通常為線性模型LR）。stacking的概念最初是由文獻(xiàn)［27］提出的，基分類器采用k折交叉驗(yàn)證法將原始數(shù)據(jù)集分為訓(xùn)練集和測(cè)試集進(jìn)行訓(xùn)練和預(yù)測(cè)。元分類器將基分類器集合在訓(xùn)練集上的預(yù)測(cè)值作為特征輸入進(jìn)行訓(xùn)練并生成模型，使用訓(xùn)練好的模型對(duì)由基分類器集合在測(cè)試集上的預(yù)測(cè)值所構(gòu)建的特征數(shù)據(jù)集進(jìn)行預(yù)測(cè)，得出最終的預(yù)測(cè)結(jié)果。圖4展示了stacking集成的體系結(jié)構(gòu)。

受限于stacking模型的訓(xùn)練過(guò)程，大多stacking算法及其變體都應(yīng)用于批量環(huán)境，對(duì)于在線環(huán)境下的研究屈指可數(shù)，以下是本文對(duì)現(xiàn)有的在線 stacking算法的總結(jié)。Frías-Blanco 等人［28］提出了一種快速自適應(yīng)堆疊集成（fast adaptive stacking of ensembles，F(xiàn)ASE）方法，集成中包括一個(gè)用于穩(wěn)定概念的主分類器。出現(xiàn)漂移警告時(shí)則訓(xùn)練一個(gè)備選分類器，若出現(xiàn)漂移確認(rèn)，該分類器將取代主分類器，F(xiàn)ASE能夠在恒定的時(shí)間和空間計(jì)算復(fù)雜度下處理輸入數(shù)據(jù)。FASE-AL［29］提出了對(duì)FASE算法的改進(jìn)，該算法保持了其主要特性，使其能夠處理只有小部分?jǐn)?shù)據(jù)被標(biāo)記的數(shù)據(jù)流。自適應(yīng)堆疊集成模型（self-adaptive stacking ensemble model，SSEM）［30］選擇性地集成不同的低復(fù)雜度、高多樣性的基分類器，該文中選擇了樸素貝葉斯（NB）、隨機(jī)森林（RF）等五種最先進(jìn)的分類器作為SSEM的基分類器，通過(guò)遺傳算法自動(dòng)選擇最優(yōu)基分類器組合以及組合的超參數(shù)。GOOWE-ML［31］是一種用于多標(biāo)簽分類的在線動(dòng)態(tài)加權(quán)堆疊集成算法，該集成為分類器的相關(guān)性得分構(gòu)建了一個(gè)空間模型，并使用該模型為其組件分類器分配最優(yōu)權(quán)重，該模型可用于任何現(xiàn)有的增量多標(biāo)簽分類算法作為其基分類器。

1.4 小結(jié)

本章從bagging、boosting、stacking三種常用集成策略的在線版本及變體介紹了在線集成分類算法。通過(guò)現(xiàn)有研究的實(shí)驗(yàn)對(duì)比發(fā)現(xiàn)，一般的boosting模型在準(zhǔn)確度方面并不優(yōu)于bagging模型。潛在原因可能是：與bagging多數(shù)投票的簡(jiǎn)單方式不同，boosting算法根據(jù)基分類器的預(yù)測(cè)性能進(jìn)行權(quán)重分配，這種方式在某些情況下的準(zhǔn)確度較不穩(wěn)定，且容易受到噪聲的影響，從而對(duì)噪聲數(shù)據(jù)進(jìn)行不必要的訓(xùn)練，并在之后影響到基分類器的權(quán)重分配。而stacking模型用于提升預(yù)測(cè)結(jié)果，在整體上優(yōu)于bagging模型以及boosting模型，但通常復(fù)雜度較高。

其中在LED合成數(shù)據(jù)集上，AdwinBag在準(zhǔn)確率上居第一位，約為62%。ADOB、AdwinBoost、LevBag分別為59%、56%、61%，bagging模型整體上在準(zhǔn)確率方面要優(yōu)于一般的boosting模型約7%。而在真實(shí)數(shù)據(jù)集electricity中，最新的算法MWOB、AWDOB取得了最佳表現(xiàn)，分別為90%、93%，其次為L(zhǎng)evBag、ADOB、AdwinBoost、AdwinBag，分別為90%、88%、87%、86%，這種情況可以解釋為MWOB、AWDOB分別基于精度和平均錯(cuò)誤率修改了錯(cuò)誤分類實(shí)例的權(quán)重計(jì)算公式，而不是之前的累積權(quán)重，提升了boosting模型的整體穩(wěn)定性。在credit card數(shù)據(jù)集上，stacking模型如SSEM算法在accuracy、recall、AUC、F-measure、MCC均表現(xiàn)最佳，分別為0.975、0.977、0.976、0.970以及0.968。圖5從所用技術(shù)、對(duì)比算法和優(yōu)缺點(diǎn)等方面對(duì)在線集成分類算法進(jìn)行了總結(jié)。

2 復(fù)雜數(shù)據(jù)流在線集成分類技術(shù)

通常，數(shù)據(jù)流挖掘是指在快速到達(dá)的數(shù)據(jù)記錄序列上執(zhí)行的挖掘任務(wù)。由于收集數(shù)據(jù)的環(huán)境可能會(huì)動(dòng)態(tài)變化，數(shù)據(jù)分布也可能相應(yīng)變化，這種變化稱為概念漂移。而初始的數(shù)據(jù)可能會(huì)呈現(xiàn)出巨大的差異，即類不平衡。這些對(duì)分類器的性能均造成了一定的影響，同時(shí)也得到了研究人員的廣泛關(guān)注。

2.1 概念漂移數(shù)據(jù)流

在大數(shù)據(jù)時(shí)代背景下，概念漂移是一個(gè)非常重要的議題，因?yàn)閿?shù)據(jù)類型和分布的不確定性是大數(shù)據(jù)的固有性質(zhì)。在概念漂移數(shù)據(jù)流中，本文根據(jù)是否存在漂移檢測(cè)機(jī)制，將在線集成學(xué)習(xí)方法分為基于主動(dòng)檢測(cè)的在線集成算法和基于被動(dòng)自適應(yīng)的在線集成算法［32］，并在下面的小節(jié)中進(jìn)行展開(kāi)。

2.1.1 基于主動(dòng)檢測(cè)的方法

主動(dòng)方法通過(guò)監(jiān)測(cè)數(shù)據(jù)流分類性能指標(biāo)或者統(tǒng)計(jì)數(shù)據(jù)屬性分布，并設(shè)置一個(gè)閾值用來(lái)判別是否發(fā)生了概念漂移，一旦檢測(cè)到數(shù)據(jù)流中概念漂移的發(fā)生，算法將會(huì)采取重置學(xué)習(xí)模型等方法來(lái)適應(yīng)數(shù)據(jù)流中新的概念。概念漂移的檢測(cè)方式有多種，主要可分為基于統(tǒng)計(jì)的方法和基于窗口的方法。

1）基于統(tǒng)計(jì)的方法

基于統(tǒng)計(jì)的思想是比較數(shù)據(jù)分布之間的差異或者驗(yàn)證模型的誤差是否在可控范圍內(nèi)，數(shù)據(jù)分布之間若存在著明顯的差異則預(yù)示著概念漂移的發(fā)生，但在在線環(huán)境中通常無(wú)法提前得知數(shù)據(jù)的初始分布，所以在本小節(jié)中先討論后者。因?yàn)樵诟拍钇骗h(huán)境中集成的性能會(huì)隨著時(shí)間的推移而變化，當(dāng)概念漂移發(fā)生時(shí)，性能會(huì)顯著下降。如果模型達(dá)到了一定錯(cuò)誤率，就會(huì)發(fā)送警報(bào)。最經(jīng)典的算法漂移檢測(cè)法（drift detecting method，DDM）［33］背后的思想是控制算法的在線錯(cuò)誤率，當(dāng)概率分布發(fā)生變化即發(fā)生概念漂移時(shí)，模型的錯(cuò)誤率會(huì)上升。DDM估計(jì)t時(shí)間的錯(cuò)誤率Pt及其標(biāo)準(zhǔn)差σt，標(biāo)準(zhǔn)差可定義為

σ=pt（1-pt）n（2）

DDM會(huì)為錯(cuò)誤率設(shè)置兩個(gè)閾值warning和drift：

pt+σt≥pmin+2σminwarning

pt+σt≥pmin+3σmindrift（3）

如果錯(cuò)誤率到達(dá)了warning值，則發(fā)出漂移警報(bào)，若后續(xù)數(shù)據(jù)的到來(lái)沒(méi)有讓錯(cuò)誤率降低并到達(dá)了drift，則確認(rèn)發(fā)生概念漂移。DDM在突變漂移時(shí)性能良好，但是對(duì)于漸變型概念漂移的檢測(cè)比較困難。早期漂移檢測(cè)法（early drift detection method，EDDM）［34］以及反應(yīng)性漂移檢測(cè)方法（reactive drift detection method，RDDM）［35］等常用漂移檢測(cè)方法都受到DDM的啟發(fā)，并改良了DDM在漸變漂移時(shí)的性能損失問(wèn)題。

在數(shù)據(jù)流學(xué)習(xí)算法中，數(shù)據(jù)分布的變化對(duì)于分類器的預(yù)測(cè)性能影響是巨大的，重點(diǎn)是學(xué)習(xí)模型需具備跟蹤此變化的能力。Baidari等人［36］提出了一種基于Bhattacharyya距離的概念漂移檢測(cè)方法（Bhattacharyya distance-based concept drift detection method，BDDM），該方法通過(guò)Bhattacharyya距離度量數(shù)據(jù)之間的差異，并使用單窗口用于從真實(shí)值序列中估計(jì)平均值和方差，以檢測(cè)漂移。在實(shí)驗(yàn)中通過(guò)調(diào)節(jié)模型參數(shù)（窗口大小、差值和增量）達(dá)到了最佳性能，并在檢測(cè)漂移時(shí)的延遲和誤報(bào)率較對(duì)比算法更低。統(tǒng)計(jì)漂移檢測(cè)方法（statistical drift detection method，SDDM）［37］同樣也是通過(guò)檢測(cè)數(shù)據(jù)分布的變化來(lái)檢測(cè)概念漂移，不同的是其使用Kullback-Leibler散度作為距離度量，并通過(guò)參數(shù)化方法擴(kuò)展了基線算法，SDDM不僅能夠檢測(cè)到漂移，更提供了漂移的可解釋性。類似的距離度量還有Hellinger距離、總變異距離等，距離度量的選擇取決于流的特性。

2）基于窗口的方法

基于窗口的模型主要關(guān)注時(shí)間戳和事件的發(fā)生，自適應(yīng)滑動(dòng)窗口（adaptive windowing，ADWIN）［38］是最具有代表性的基于窗口的檢測(cè)方法，它保存了一個(gè)大小為W的滑動(dòng)窗口用于存儲(chǔ)最近實(shí)例，當(dāng)檢測(cè)到漂移時(shí)，W減小。同時(shí)還包含兩個(gè)子窗口用來(lái)存儲(chǔ)舊實(shí)例和新實(shí)例，當(dāng)這兩個(gè)子窗口的平均值之差高于給定閾值時(shí)，即報(bào)告漂移。近十年來(lái)，研究者將窗口模型和統(tǒng)計(jì)過(guò)程方法結(jié)合起來(lái)，提出了多種漂移檢測(cè)方法。文獻(xiàn)［39］提出了兩種漂移檢測(cè)方法，使用Hoeffding不等式作為平均值之間差值的上限。HDDMA-test比較滑動(dòng)窗口的平均值以檢測(cè)漂移，可用于檢測(cè)突然漂移。HDDMW-test使用遺忘方案首先對(duì)移動(dòng)平均線進(jìn)行加權(quán)，然后進(jìn)行比較以檢測(cè)漂移，更適合檢測(cè)增量漂移。Pesaranghader等人［40］提出的快速Hoeffding漂移檢測(cè)方法（FHDDM）使用滑動(dòng)窗口和Hoeffding不等式檢測(cè)漂移點(diǎn)。與其他基于窗口的方法不同，該方法包含一個(gè)歷史信息的窗口和另一個(gè)維護(hù)最新信息的窗口，使用單個(gè)滑動(dòng)窗口將分類器精度與迄今為止觀察到的最佳精度進(jìn)行比較，當(dāng)差值大于使用Hoeffding不等式確定的閾值時(shí)，發(fā)出漂移狀態(tài)的信號(hào)。Pesaranghader等人［41］將McDiarmid不等式引入概念漂移檢測(cè)，提出了McDiarmid漂移檢測(cè)方法（McDiarmid drift detection method，MDDM），該算法通過(guò)對(duì)預(yù)測(cè)結(jié)果應(yīng)用加權(quán)滑動(dòng)窗口，最近的條目被賦予更高的權(quán)重。在實(shí)例處理過(guò)程中，將滑動(dòng)窗口內(nèi)元素的加權(quán)平均值與迄今為止觀察到的最大加權(quán)平均值進(jìn)行比較，若兩者之間的差異大于McDiarmid不等式的上界，則意味著變化是顯著的，即發(fā)生了概念漂移。

最近，胡陽(yáng)等人［42］提出了一種基于 McDiarmid 邊界的自適應(yīng)加權(quán)概念漂移檢測(cè)方法WMDDM。引入衰減函數(shù)對(duì)實(shí)例加權(quán)，賦予舊數(shù)據(jù)更低權(quán)值，提升新數(shù)據(jù)的影響力。該算法利用 McDiarmid 不等式得到加權(quán)分類正確率的置信邊界，在檢測(cè)到分類正確率下降超過(guò)置信邊界時(shí)調(diào)節(jié)衰減因子，實(shí)現(xiàn)權(quán)值的動(dòng)態(tài)改變。Yan［43］利用Hoeffding不等式提出了精準(zhǔn)概念漂移檢測(cè)方法（accurate concept drift detection method，ACDDM），該算法利用Hoeffding不等式來(lái)觀察誤差率的不一致性。假設(shè)Pt是當(dāng)前的先驗(yàn)誤差，Pmin是每個(gè)時(shí)間步長(zhǎng)的最小誤差，則時(shí)間t處最小誤差和當(dāng)前誤差之間的差為ΔPt：

ΔPt=Pt-Pmin（4）

通過(guò)使用Hoeffding不等式確定漂移確認(rèn)閾值drift，若ΔPt的平均值大于drift，則表明由于概念漂移，誤差率出現(xiàn)不一致。實(shí)驗(yàn)表明ACDDM的漂移檢測(cè)性能總體上優(yōu)于其他算法。

2.1.2 基于被動(dòng)自適應(yīng)的方法

被動(dòng)方法不主動(dòng)檢測(cè)概念漂移的出現(xiàn)，但是會(huì)通過(guò)不斷地更新模型，如根據(jù)基分類器的性能動(dòng)態(tài)地調(diào)整其權(quán)重，使得模型適應(yīng)數(shù)據(jù)流中新的概念。被動(dòng)方法中一般有根據(jù)分類器的準(zhǔn)確率或其他性能指標(biāo)進(jìn)行動(dòng)態(tài)加權(quán)以及保持集成的多樣性水平等方法適應(yīng)概念漂移。

1）基于性能反饋

Kolter等人［44］提出了動(dòng)態(tài)加權(quán)多數(shù)算法（dynamic weighted majority，DWM），該算法根據(jù)分類器的錯(cuò)誤率來(lái)更新權(quán)重。當(dāng)集成性能嚴(yán)重下降時(shí)會(huì)訓(xùn)練新分類器用于更新集成。循環(huán)動(dòng)態(tài)加權(quán)多數(shù)（recurring dynamic weighted majority，RDWM）［45］由主集合和次集合組成。主集合代表當(dāng)前概念，并按照DWM算法進(jìn)行訓(xùn)練和更新；而次集合由發(fā)生漂移時(shí)從主集合中復(fù)制的最準(zhǔn)確的分類器組成。對(duì)于突變或漸變漂移，RDWM都具有良好的準(zhǔn)確率。

準(zhǔn)確度更新集成（accuracy updated ensemble，AUE）［46］算法通過(guò)使用在線組件分類器并根據(jù)當(dāng)前分布進(jìn)行更新來(lái)擴(kuò)展AWE［47］，這種擴(kuò)展使AUE在穩(wěn)定性上優(yōu)于AWE，同時(shí)對(duì)漸變漂移和突變漂移都能夠很好地適應(yīng)。在線準(zhǔn)確度更新集成（online accuracy updated ensemble，OAUE）［48］是基于AUE的增量算法，它根據(jù)最近d個(gè)實(shí)例的誤差來(lái)計(jì)算組件分類器的權(quán)重并創(chuàng)建一個(gè)新的分類器，以替換性能最弱的集成成員。Gu等人［49］提出了一種基于窗口自適應(yīng)在線精度更新集成（window-adaptive online accuracy updated ensemble，WAOAUE）算法，并在集成中加入變化檢測(cè)器來(lái)確定每個(gè)候選分類器的窗口大小，彌補(bǔ)了OAUE由于采用固定的窗口在適應(yīng)突變漂移時(shí)存在的缺陷。

結(jié)合在線和基于塊的集成的關(guān)鍵特征，可以有效地響應(yīng)漸變漂移并快速響應(yīng)突變漂移，上文所提AUE算法既是如此。知識(shí)最大化集成（knowledge-maximized ensemble，KME）［50］可以很好地解決具有有限標(biāo)記實(shí)例的各種漂移場(chǎng)景，并且可以復(fù)用過(guò)去塊中保存的標(biāo)記實(shí)例，增強(qiáng)候選分類器的識(shí)別能力。Kappa更新集成（Kappa update ensemble，KUE）［51］使用Kappa統(tǒng)計(jì)來(lái)動(dòng)態(tài)加權(quán)并選擇基分類器。通過(guò)在特征的隨機(jī)子集上訓(xùn)練基分類器，提供了更好的預(yù)測(cè)能力和對(duì)概念漂移的適應(yīng)性。為了減少不合格分類器的影響，增加了棄權(quán)機(jī)制，該機(jī)制將選定的分類器從投票過(guò)程中刪除。

2）多樣性集成

為了保持對(duì)新舊概念的高度概括，保持高度多樣化的集成是一個(gè)很好的策略。對(duì)于多樣性沒(méi)有單一的定義或衡量標(biāo)準(zhǔn)，在經(jīng)典算法DDD［52］中使用Q統(tǒng)計(jì)量來(lái)定義多樣性：

Qi，k=N11N00-N01N10N11N00+N01N10（5）

其中：Qi，k表示分類器Di和Dk之間的Q統(tǒng)計(jì)量；Nab表示Di分類結(jié)果為a，Dk分類結(jié)果為b的訓(xùn)練實(shí)例數(shù)量，1、0分別表示正確與錯(cuò)誤分類。對(duì)于分類器集合，所有分類器對(duì)的平均Q統(tǒng)計(jì)量可以用作多樣性的度量，較高/較低的平均值表示較低/較高的多樣性。多樣化動(dòng)態(tài)加權(quán)多數(shù)（diversified dynamic weighted majority，DDWM）［53］維持了兩組加權(quán)整體，它們?cè)诙鄻有运缴嫌兴煌?，并根?jù)準(zhǔn)確率對(duì)集成進(jìn)行動(dòng)態(tài)更新。實(shí)驗(yàn)表明，DDWM在Kappa統(tǒng)計(jì)、模型成本、評(píng)估時(shí)間和內(nèi)存需求等方面均是高度資源有效的。

多樣性也可以通過(guò)異構(gòu)集成來(lái)實(shí)現(xiàn)。針對(duì)基分類器的類型異同，集成可分為同構(gòu)與異構(gòu)，bagging及boosting集成均為同構(gòu)集成，而stacking算法屬于異構(gòu)集成。與同構(gòu)集成不同，異構(gòu)集成由不同的分類器模型組成，使得集成擁有較高的多樣性。異構(gòu)集成在批處理環(huán)境中已被證明是成功的，但不容易轉(zhuǎn)移到數(shù)據(jù)流設(shè)置中，故Van Rijn等人［54］引入了一個(gè)在線性能評(píng)估框架，在整個(gè)流中該框架以不同的方式對(duì)集合成員的投票進(jìn)行加權(quán)，并應(yīng)用這種技術(shù)構(gòu)建一個(gè)簡(jiǎn)單的新穎集成技術(shù)BLAST（best last的縮寫(xiě)）以快速進(jìn)行異構(gòu)集成。Museba等人［55］提出一種基于精度和多樣性的異構(gòu)動(dòng)態(tài)集成選擇方法（HDES-AD），該方法可以自動(dòng)為特定概念選擇最多樣化和最準(zhǔn)確的基本模型，以便在動(dòng)態(tài)環(huán)境中長(zhǎng)時(shí)間使用。異構(gòu)動(dòng)態(tài)加權(quán)多數(shù)（heterogeneous dynamic weighted majority，HDWM）［56］將DWM算法轉(zhuǎn)變?yōu)楫悩?gòu)集成，HDWM 會(huì)自動(dòng)選擇當(dāng)前最佳的基本模型類型，通過(guò)智能切換基分類器來(lái)提高預(yù)測(cè)性能。ADES［57］提出了一種在線異構(gòu)集成，它使用多樣性和準(zhǔn)確性作為評(píng)估指標(biāo)來(lái)選擇最佳集成，并創(chuàng)建不同多樣性水平的集成，以最小的開(kāi)銷表現(xiàn)出了良好的性能。DDCW［58］利用動(dòng)態(tài)加權(quán)方案和一種保持集成多樣性的機(jī)制用于漂移數(shù)據(jù)流分類，該方法使用樸素貝葉斯（NB）以及霍夫丁樹(shù)（Hoeffding tree）來(lái)構(gòu)建其分類器集成，結(jié)果表明該模型在一定程度上優(yōu)于其他同構(gòu)集成。表1列出了本文所提及的異構(gòu)在線集成算法所使用的基分類器，可以看出NB、Hoeffding tree等經(jīng)典算法常被用作異構(gòu)模型的基分類器。

2.2 不平衡數(shù)據(jù)流

不平衡數(shù)據(jù)流中最重要的特征就是傾斜的類分布。通常，少數(shù)類（正類）樣本是更感興趣的類別，但可能被忽略并被視為噪聲。在在線學(xué)習(xí)場(chǎng)景中，這種困難會(huì)變得更加嚴(yán)重，因?yàn)闊o(wú)法看到數(shù)據(jù)的全貌，而且數(shù)據(jù)可能會(huì)動(dòng)態(tài)變化。在線類不平衡問(wèn)題的現(xiàn)有方法可大致分為算法級(jí)方法和數(shù)據(jù)級(jí)方法，前者通過(guò)在設(shè)計(jì)算法時(shí)考慮不同的誤分類成本，從而使正實(shí)例的誤分類代價(jià)高于負(fù)實(shí)例。在數(shù)據(jù)級(jí)方法的情況下，添加預(yù)處理步驟，通過(guò)對(duì)負(fù)類進(jìn)行欠采樣或?qū)φ愡M(jìn)行過(guò)采樣，重新平衡類分布。

2.2.1 基于數(shù)據(jù)重采樣的方法

基于數(shù)據(jù)重采樣的方法主要有欠采樣、過(guò)采樣以及混合采樣，欠采樣通過(guò)減少多數(shù)類樣本的實(shí)例，而過(guò)采樣通過(guò)增加少數(shù)類樣本的數(shù)量以實(shí)現(xiàn)類分布的平衡。

Wang等人［8］將重采樣技術(shù)與在線bagging相結(jié)合，開(kāi)發(fā)了兩種基于重采樣的在線學(xué)習(xí)算法，基于過(guò)采樣的在線裝袋（oversampling based online bagging，OOB）和基于欠采樣的在線裝袋（under-sampling based online bagging，UOB），通過(guò)使用時(shí)間衰減函數(shù)來(lái)動(dòng)態(tài)捕捉失衡率，以解決數(shù)據(jù)流中的類不平衡問(wèn)題。如果新實(shí)例屬于少數(shù)類樣本則OOB就會(huì)將泊松分布的參數(shù)λ調(diào)優(yōu)為1/wk，wk代表當(dāng)前類所占的比例，通過(guò)此方法間接地增加了少數(shù)類的訓(xùn)練次數(shù)。與OOB對(duì)應(yīng)，當(dāng)新實(shí)例屬于多數(shù)類樣本UOB則將參數(shù)設(shè)為（1-wk），從而實(shí)現(xiàn)多數(shù)類樣本通過(guò)較小的k值進(jìn)行相應(yīng)的欠采樣。之后，文獻(xiàn)［59］又進(jìn)一步改進(jìn)了OOB和UOB內(nèi)部的重采樣策略，提出了使用自適應(yīng)權(quán)重來(lái)維護(hù)OOB和UOB的方法，即WEOB1和WEOB2。WEOB1 使用OOB和UOB的歸一化G-mean值作為它們的權(quán)重：

αo=gogo+gu，αu=gugo+gu（6）

其中：αo和αu分別表示OOB和UOB的權(quán)重；go和gu分別表示OOB和UOB的G-mean值。在WEOB2中，權(quán)重只能是二進(jìn)制值（0或1），研究表明這兩種加權(quán)集成方法的準(zhǔn)確性均優(yōu)于OOB，穩(wěn)健性均優(yōu)于UOB，而且WEOB2的G-mean值優(yōu)于WEOB1。

諸如以上所述，許多研究都集中在不平衡二元分類問(wèn)題上，對(duì)于多類不平衡問(wèn)題，需要考慮更多的因素和設(shè)計(jì)更復(fù)雜的算法來(lái)處理增加的類別數(shù)量，因?yàn)槎囝悊?wèn)題增加了數(shù)據(jù)復(fù)雜性并加劇了不平衡分布。Wang等人［60］將研究擴(kuò)展到多類場(chǎng)景，提出了基于多類過(guò)采樣的在線裝袋（MOOB）和基于多類欠采樣的在線裝袋（MUOB），該方法無(wú)須對(duì)多類問(wèn)題進(jìn)行類分解，并且允許集成學(xué)習(xí)器使用任何類型的基分類器。Olaitan等人［61］提出了一種基于窗口的方法（SCUT-DS），該算法應(yīng)用在線K-均值聚類分析算法對(duì)多數(shù)類進(jìn)行欠采樣，并利用SMOTE算法通過(guò)窗口對(duì)少數(shù)類進(jìn)行過(guò)采樣。該算法的優(yōu)點(diǎn)是不對(duì)類比率進(jìn)行假設(shè)，但是該方法僅在有監(jiān)督的學(xué)習(xí)環(huán)境中使用，因此有一定的局限性，在許多不平衡的在線學(xué)習(xí)應(yīng)用程序中，標(biāo)記所有實(shí)例是不可能的。Vafaie等人［62］提出了從具有缺失標(biāo)簽的多類不平衡流中學(xué)習(xí)的在線集成算法——基于SMOTE的改良在線集成（improved SMOTE online ensemble，ISOE）和改良的在線集成（improved online Snsemble，IOE）。在ISOE中使用SMOTE對(duì)最近窗口中的少數(shù)類實(shí)例進(jìn)行過(guò)采樣，同時(shí)根據(jù)召回率動(dòng)態(tài)采樣所有類，在IOE中根據(jù)性能和迄今為止看到的每個(gè)類的實(shí)例數(shù)量更改速率參數(shù)來(lái)重新平衡類的樣本量。

利用分治策略將多類問(wèn)題分解為單類子問(wèn)題同樣是一種可選的方法。Czarnowski［63］提出了使用過(guò)采樣和實(shí)例選擇技術(shù)（即欠采樣）（WECOI），基于將單個(gè)多類分類問(wèn)題分解為一組單類分類問(wèn)題，使用分類器加權(quán)集成進(jìn)行單類分類。該算法使用基于聚類的K均值算法合成實(shí)例，實(shí)現(xiàn)對(duì)少數(shù)類樣本進(jìn)行過(guò)采樣，簇的中心用于表示參考實(shí)例，通過(guò)識(shí)別參考示例鄰居之中的少數(shù)類，然后隨機(jī)生成位于所識(shí)別的鄰居之間的合成實(shí)例，如圖6所示。經(jīng)過(guò)驗(yàn)證所提消除數(shù)據(jù)流中類不平衡的方法有助于提高在線學(xué)習(xí)算法的性能。

2.2.2 基于代價(jià)敏感的方法

代價(jià)敏感算法考慮了不同的誤分類成本。代價(jià)矩陣編碼將樣本從一類分類為另一類的懲罰（表2）。設(shè)C（i，j）表示將類i的實(shí)例預(yù)測(cè)為類j的成本，C（0，1）表示將正實(shí)例錯(cuò)誤分類為負(fù)實(shí)例的成本。

代價(jià)敏感的集成學(xué)習(xí)方法通常通過(guò)在每次迭代bagging/boosting之前對(duì)數(shù)據(jù)進(jìn)行有偏差的重新采樣/重新加權(quán)來(lái)操縱誤分類成本。Wang等人［64］提出了一個(gè)在線代價(jià)敏感集成學(xué)習(xí)框架，該框架將一批廣泛使用的基于bagging和boosting的代價(jià)敏感學(xué)習(xí)算法推廣到其在線版本：RUSBoost、SMOTEBoost、SMOTEBagging、AdaC2等。online bagging中的代價(jià)敏感是通過(guò)操縱泊松分布的參數(shù)實(shí)現(xiàn)的。在online UnderOverBagging中，新實(shí)例的重采樣服從k-poisson（mC/M）（C>1），其中M為基分類器數(shù)量，m為基分類器編號(hào)。對(duì)于boosting算法則是通過(guò)制定權(quán)重更新規(guī)則來(lái)實(shí)現(xiàn)代價(jià)敏感。分析證實(shí)，由在線代價(jià)敏感集成學(xué)習(xí)算法生成的模型收斂于批量代價(jià)敏感集成的模型。Du等人［65］提出了EOBag算法，采用了多種均衡方法以減少不平衡數(shù)據(jù)流的影響。該算法通過(guò)式（7）計(jì)算誤分類成本。

CDj=12×|N+|xj∈N+

12×|N-|xj∈N-（7）

其中：N+、N-分別表示正類與負(fù)類的實(shí)例數(shù)。從式（7）可以看出，正類的誤分類成本CDj要明顯大于負(fù)類。最后通過(guò)計(jì)算泛化誤差進(jìn)行加權(quán)投票得出最終結(jié)果。不使用準(zhǔn)確率作為加權(quán)指標(biāo)的原因是因?yàn)椴煌悩颖镜恼`分類成本不同，無(wú)法簡(jiǎn)單地通過(guò)使用基分類器的準(zhǔn)確率來(lái)描述基分類器的權(quán)重。Loezer等人［66］提出的代價(jià)敏感自適應(yīng)隨機(jī)森林（cost-sensitive adaptive random forest，CSARF），是自適應(yīng)隨機(jī)森林（ARF）的變體并做了以下修改：使用馬修斯相關(guān)系數(shù)（MCC）［67］為內(nèi)部樹(shù)分配權(quán)重，在與ARF和帶重采樣的隨機(jī)森林（ARFRE）的對(duì)比中，表明基于誤分類成本評(píng)估策略的使用是有效的。

本節(jié)從數(shù)據(jù)級(jí)和算法級(jí)兩個(gè)方面介紹了在不平衡數(shù)據(jù)流中的在線集成分類算法。在數(shù)據(jù)級(jí)方法中，主要通過(guò)對(duì)數(shù)據(jù)進(jìn)行重采樣。在算法級(jí)方法，主要考慮的是不同類別的誤分類成本。表3從算法所使用技術(shù)對(duì)本節(jié)所介紹的部分不平衡數(shù)據(jù)流分類算法進(jìn)行了總結(jié)。

2.2.3 其他工作

在不平衡數(shù)據(jù)流方面同樣也存在著概念漂移的問(wèn)題，當(dāng)與概念漂移相結(jié)合時(shí)，不平衡比率不再是靜態(tài)的，它將隨著流的進(jìn)展而變化，例如少數(shù)類轉(zhuǎn)變?yōu)槎鄶?shù)類。因此，不僅要監(jiān)視每個(gè)類的屬性變化，還要監(jiān)視其頻率的變化。新類可能出現(xiàn)，舊類可能消失，這些現(xiàn)象對(duì)大多數(shù)現(xiàn)有算法構(gòu)成了重大挑戰(zhàn)。含概念漂移的不平衡數(shù)據(jù)分類也是目前研究的一個(gè)重點(diǎn)內(nèi)容，用戶興趣推薦、社交媒體分析等現(xiàn)實(shí)案例都是很好的應(yīng)用。

基于選擇的重采樣集成（selection-based resampling ensemble，SRE）［68］提出選擇性重采樣機(jī)制，該機(jī)制同時(shí)考慮概念漂移和數(shù)據(jù)困難因素，通過(guò)重用過(guò)去塊的少數(shù)類數(shù)據(jù)來(lái)平衡當(dāng)前類分布，然后通過(guò)評(píng)估每個(gè)保留的少數(shù)類樣本與當(dāng)前少數(shù)樣本集之間的相似度來(lái)避免吸收漂移數(shù)據(jù)，最后采用加權(quán)投票進(jìn)行預(yù)測(cè)。RE-DI集成模型［69］使用重采樣緩沖區(qū)用于存儲(chǔ)少數(shù)類的實(shí)例，以平衡數(shù)據(jù)隨時(shí)間變化的不平衡分布，對(duì)于流中存在的概念漂移問(wèn)題，RE-DI采用時(shí)間衰減策略以及增強(qiáng)機(jī)制進(jìn)行處理，使模型更加關(guān)注數(shù)據(jù)流的新概念以及增加對(duì)少數(shù)類表現(xiàn)更好的基分類器權(quán)重。

此外，根據(jù)類分布中不平衡比率的動(dòng)態(tài)變化進(jìn)行動(dòng)態(tài)采樣與集成分類同樣可以產(chǎn)生較好的效果。HIDC［70］通過(guò)估計(jì)類分布中的不平衡因子，對(duì)過(guò)采樣和欠采樣作出動(dòng)態(tài)決策，有效處理類不平衡問(wèn)題。并在集成性能下降時(shí)，將最差的集成成員替換為候選分類器，利用集成分類的加權(quán)機(jī)制快速響應(yīng)各種類型的概念漂移，結(jié)果表明HIDC的性能始終優(yōu)于對(duì)比算法DFGW-IS，并且隨著實(shí)例的增加，F(xiàn)-score有著明顯的提高。魯棒在線自調(diào)整集成（robust online self-adjusting ensemble，ROSE）［71］則不關(guān)注當(dāng)前的不平衡比率，而是通過(guò)在每個(gè)類上設(shè)置滑動(dòng)窗口，以此來(lái)創(chuàng)建對(duì)類失衡不敏感的基分類器，實(shí)驗(yàn)證實(shí)ROSE是一種魯棒且全面的集成模型，特別是在存在噪聲和類不平衡漂移的情況下，能夠同時(shí)保持競(jìng)爭(zhēng)性的時(shí)間復(fù)雜度和內(nèi)存消耗?；诖翱诘腄ESW-ID算法［72］使用雙重采樣技術(shù)，首先使用泊松分布對(duì)數(shù)據(jù)流進(jìn)行重新采樣，如果當(dāng)前數(shù)據(jù)處于高度不平衡狀態(tài)，則使用存儲(chǔ)少數(shù)類實(shí)例的窗口進(jìn)行二次采樣，以平衡數(shù)據(jù)分布。與UOB、OOB算法進(jìn)行了對(duì)比實(shí)驗(yàn)，結(jié)果表明DESW-ID在F-score、G-mean以及召回率等五個(gè)指標(biāo)中均具有很好的表現(xiàn)。

2.3 算法復(fù)雜度分析

算法復(fù)雜度是用來(lái)評(píng)價(jià)算法執(zhí)行時(shí)間和資源消耗的度量，可以用來(lái)衡量一個(gè)算法的優(yōu)劣，一般包括時(shí)間復(fù)雜度以及空間復(fù)雜度。通過(guò)研究算法的時(shí)空效率可以進(jìn)一步了解算法的性能，從而盡可能地探索各種優(yōu)化策略以提高算法效率。本節(jié)將對(duì)上文所涉及到的代表性算法進(jìn)行時(shí)空效率的詳細(xì)分析。

在概念漂移數(shù)據(jù)流算法中，DDM、RDDM以及BDDM等漂移檢測(cè)方法主要由處理概念漂移的時(shí)間來(lái)決定，完整學(xué)習(xí)過(guò)程的算法復(fù)雜度還需要結(jié)合使用的底層分類算法。RDDM中有一個(gè)使用數(shù)組實(shí)現(xiàn)的圓形隊(duì)列用于存儲(chǔ)穩(wěn)定概念的最小尺寸，故空間復(fù)雜度為O（min），而DDM無(wú)須存儲(chǔ)，空間復(fù)雜度僅為O（1）。RDDM、DDM的時(shí)間復(fù)雜度分別為O（n×min）和O（n），其中n是處理實(shí)例的數(shù)量，因?yàn)镽DDM在出現(xiàn)漂移時(shí)需要執(zhí)行更多的迭代，而最小迭代只對(duì)n的小部分執(zhí)行。對(duì)于BDDM算法，其使用了單窗口技術(shù)用于檢測(cè)概念漂移，在大小為w的滑動(dòng)窗口上計(jì)算，其時(shí)間復(fù)雜度為O（w），但在數(shù)據(jù)流的情況下其實(shí)例數(shù)n是未知的，故BDDM的時(shí)間復(fù)雜度是O（w×n）。而對(duì)于概念漂移自適應(yīng)集成分類算法，算法復(fù)雜度主要取決于訓(xùn)練和加權(quán)過(guò)程。OAUE算法使用Hoeffding樹(shù)作為其基分類器，由于Hoeffding樹(shù)可以在常數(shù)時(shí)間內(nèi)學(xué)習(xí)實(shí)例，訓(xùn)練k個(gè)樹(shù)集合的時(shí)間復(fù)雜度為O（k），加權(quán)過(guò)程同樣也僅需要恒定數(shù)量的操作，所以O(shè)AUE的時(shí)間復(fù)雜度為O（2k），其中k為用戶定義的集成基分類器總數(shù)，即時(shí)間復(fù)雜度可近似為O（1）。OAUE的空間復(fù)雜度取決于所學(xué)習(xí)的概念，表示為O（kavcl+k（d+c）），其中a是屬性的數(shù)量，v是每個(gè)屬性的最大值數(shù)，c是類的數(shù)量，l是樹(shù)中的葉子的數(shù)量。而k（d+c）為OAUE中的加權(quán)機(jī)制所需的時(shí)間，因?yàn)閗、d和c均為常數(shù)，所以提出的加權(quán)方案與沒(méi)有加權(quán)的模型相比，不會(huì)增加空間復(fù)雜度，即為O（kavcl）。KUE算法使用快速?zèng)Q策樹(shù)（VFDT）作為基分類器，在每個(gè)塊Si上更新k個(gè)VFDT樹(shù)的時(shí)間復(fù)雜度為O（k|Si|），此外，KUE會(huì)在塊Si上訓(xùn)練q個(gè)新樹(shù)（q≤k），以準(zhǔn)備替代最弱的集合成員，其時(shí)間復(fù)雜度為O（q|Si|），故KUE的時(shí)間復(fù)雜度為O（（k+q）|Si|）。VFDT的內(nèi)存復(fù)雜度為O（rvlc），其中r為對(duì)總特征數(shù)f進(jìn)行三維隨機(jī)子空間投影后的特征數(shù)（r

對(duì)于不平衡數(shù)據(jù)流，算法復(fù)雜度主要取決于數(shù)據(jù)預(yù)處理所需要的時(shí)間及對(duì)再平衡數(shù)據(jù)分類的時(shí)間等。SRE算法的時(shí)間復(fù)雜度為O（N|M| log （|M|+a）+aN log a+3|M|N），其中N是數(shù)據(jù)塊的數(shù)量，a是數(shù)據(jù)塊大小，|M|是每個(gè)塊包含的樣例數(shù)。ROSE算法所使用的基分類器是VFDT，在第一個(gè)實(shí)例塊S1集成初始化的時(shí)間復(fù)雜度為O（k），其中k為基分類器數(shù)量，集成模型在后續(xù)實(shí)例Si上的增量學(xué)習(xí)根據(jù)當(dāng)前λ更新k個(gè)現(xiàn)有分類器的時(shí)間復(fù)雜度為O（kλ）。此外，在檢測(cè)到概念漂移時(shí)，ROSE會(huì)訓(xùn)練另外k個(gè)分類器的背景集合，因此，ROSE的最壞情況下時(shí)間復(fù)雜度為O（2kλ|S|），其中|S|為數(shù)據(jù)塊的數(shù)量。與KUE相同，VFDT的內(nèi)存復(fù)雜度為O（fvlc），經(jīng)過(guò)r維隨機(jī)子空間投影后，有效地將VFDT的內(nèi)存復(fù)雜度降低到O（rvlc）。ROSE還為每個(gè)類創(chuàng)建了一個(gè)大小為w的存儲(chǔ)最新實(shí)例的滑動(dòng)窗口，因此，由主集成中的k個(gè)分類器加上背景集成中的k個(gè)分類器組成的ROSE的最壞情況下空間復(fù)雜度為O（（2krvlc）+（|w|f）），其中f為特征數(shù)。

與單分類器相比，分類器集成在準(zhǔn)確率、Kappa值等預(yù)測(cè)性能指標(biāo)上有著顯著的提升，但是時(shí)間和空間消耗都有所增加，這種情況是不可避免的，它是由集成結(jié)構(gòu)所決定的。通過(guò)優(yōu)化集成策略可以盡可能地提高時(shí)空效率，例如使用特征子空間對(duì)數(shù)據(jù)進(jìn)行壓縮、使用剪枝策略等。

3 算法性能對(duì)比與分析

本章對(duì)概念漂移數(shù)據(jù)流和不平衡數(shù)據(jù)流的部分在線集成分類方法進(jìn)行了性能分析與對(duì)比，對(duì)使用的同一數(shù)據(jù)集進(jìn)行了介紹并對(duì)比了所列算法的性能指標(biāo)，并匯總了本文所介紹的算法使用的數(shù)據(jù)集、對(duì)比算法以及優(yōu)缺點(diǎn)。

3.1 數(shù)據(jù)集介紹

本節(jié)對(duì)所使用的同一數(shù)據(jù)集進(jìn)行了介紹，表4展示了使用相同數(shù)據(jù)集的算法。數(shù)據(jù)集描述如下。

a）LED：包含漸變漂移的數(shù)據(jù)集，由LED生成器生成用于預(yù)測(cè)七段二極管上顯示的數(shù)據(jù)集，具有24個(gè)屬性和 10個(gè)類別。每25 000個(gè)樣本出現(xiàn)一次漸變漂移，共100 000個(gè)樣本。

b）electricity：真實(shí)數(shù)據(jù)集，來(lái)自澳大利亞新南威爾士州電力市場(chǎng)能源價(jià)格的數(shù)據(jù)，用來(lái)測(cè)試檢測(cè)器在真實(shí)數(shù)據(jù)中的效果，表中共有45 312個(gè)樣本，每個(gè)樣本具有7個(gè)屬性和2個(gè)類。

c）random RBF：RBF生成器是一個(gè)使用隨機(jī)質(zhì)心創(chuàng)建新實(shí)例的合成數(shù)據(jù)集，每個(gè)質(zhì)心由類標(biāo)簽、權(quán)重、位置和標(biāo)準(zhǔn)偏差定義。實(shí)例由50個(gè)屬性和2個(gè)類描述，其中一個(gè)類是欠采樣的，每1 000個(gè)實(shí)例產(chǎn)生一定的不平衡比率。

d）SEA：SEA生成器用于創(chuàng)建三個(gè)數(shù)據(jù)集，每個(gè)數(shù)據(jù)集包含10%的噪聲。它包含三個(gè)取值從0～10的屬性，第三個(gè)屬性被視為噪聲。并在每1 000個(gè)實(shí)例對(duì)其中一個(gè)類進(jìn)行欠采樣，以誘導(dǎo)類不平衡，少數(shù)類的基數(shù)占總數(shù)據(jù)的8%。

3.2 性能評(píng)估指標(biāo)

本節(jié)介紹了部分評(píng)估數(shù)據(jù)流分類算法性能的指標(biāo)，并結(jié)合2.2.2節(jié)的代價(jià)矩陣（混淆矩陣），給出了它們的計(jì)算方法，如表5所示。準(zhǔn)確率（accuracy）、假陽(yáng)性率（FPR）、假陰性率（FNR）、精度（precision）、召回率（recall） 等均為數(shù)據(jù)流分類算法中常用的性能評(píng)估指標(biāo)。

3.3 算法性能對(duì)比

本節(jié)通過(guò)在使用相同數(shù)據(jù)集的條件下，對(duì)算法進(jìn)行對(duì)比分析與總結(jié)，實(shí)驗(yàn)結(jié)論均由本文所提及的公開(kāi)發(fā)表算法中的實(shí)驗(yàn)數(shù)據(jù)得出。表6從數(shù)據(jù)集、對(duì)比算法以及優(yōu)缺點(diǎn)等方面對(duì)代表性算法進(jìn)行總結(jié)。

3.3.1 概念漂移數(shù)據(jù)流

a）漂移檢測(cè)方法。在數(shù)據(jù)大小為50 KB的LED突變漂移數(shù)據(jù)集上，相較于DDM與FHDDM，BDDM取得了50.24的最佳準(zhǔn)確率，其余兩者為49.14、47.66，并且在precision、recall、MCC指標(biāo)上BDDM均表現(xiàn)出最優(yōu)的性能，均為0.75。在與DDM、ADWIN、FHDDM的對(duì)比實(shí)驗(yàn)中，基分類器分別采用HT以及NB，MDDM算法的平均準(zhǔn)確率最高為89.56。與基于窗口的算法FHDDM與MDDM相比，基于統(tǒng)計(jì)的算法SDDM具有最低的假陽(yáng)性率和假陰性率，F(xiàn)PR及FNR均為0，而FHDDM與MDDM均為0.03與0.02。同樣在electricity真實(shí)數(shù)據(jù)集上，BDDM、MDDM算法均取得了最佳的準(zhǔn)確率，分別為85.68、83.47。在這兩個(gè)數(shù)據(jù)集的實(shí)驗(yàn)數(shù)據(jù)中，基于統(tǒng)計(jì)的模型在平均準(zhǔn)確率上比基于窗口的模型高約2.5%。

b）數(shù)據(jù)流分類方法。LED數(shù)據(jù)集中，在DDCW與DWM、KUE等算法的對(duì)比實(shí)驗(yàn)中，由KUE取得了最佳準(zhǔn)確率0.893，僅使用HT作為其基分類器的異構(gòu)算法DDCW具第二位0.873，DWM次之，為0.831。相較DDD算法，異構(gòu)算法HEDS-AD在準(zhǔn)確率以時(shí)間消耗方面均體現(xiàn)出明顯的優(yōu)勢(shì)，DDD時(shí)空復(fù)雜度較高的原因是因?yàn)槠渚S護(hù)了四個(gè)不同多樣性的集成。在electricity數(shù)據(jù)集中，異構(gòu)算法DDCW由于其較高的多樣性，在準(zhǔn)確率及F1-measure方面均優(yōu)于對(duì)比算法，平均準(zhǔn)確率與同構(gòu)模型相比高約10%。

3.3.2 不平衡數(shù)據(jù)流

random RBF數(shù)據(jù)集中，在與OOB等算法的對(duì)比實(shí)驗(yàn)中，SRE在F-measure、G-mean、recall、AUC指標(biāo)上均居于前列，其中F-measure、G-mean值取得了最佳，分別為62.22、84.35，準(zhǔn)確率為92.52，僅次于OOB的93.05。相較于MUOB，ISOE和IOE在G-mean值上表現(xiàn)最好，分別為0.850和0.847，并無(wú)明顯差別，這表明SMOTE在過(guò)采樣少數(shù)類中的作用有限。而MUOB由于欠采樣的數(shù)據(jù)量過(guò)多，導(dǎo)致表現(xiàn)不佳，G-mean值僅為0.741。當(dāng)在數(shù)據(jù)流中加入了概念漂移之后，IOE的G-mean值沒(méi)有明顯的變化，而MUOB的G-mean從0.833降到了0.414。相較于OOB、UOB，DESW-ID算法在所有指標(biāo)上均表現(xiàn)最佳，尤其是AUC達(dá)到了0.976 1，而OOB與UOB僅為0.760 9、0.638 8。SEA數(shù)據(jù)集中所有算法的平均表現(xiàn)不如RBF數(shù)據(jù)集，在ROSE與OOB、UOB的對(duì)比實(shí)驗(yàn)中，不論不平衡比率如何，ROSE算法在Kappa值及AUC值均取得了最高值，在不平衡比率為5的情況下，ROSE、OOB、UOB的AUC值分別為88.33、85.93、85.87。并且在靜態(tài)及漂移不平衡比率的情況下ROSE的平均算法排名都在第二位左右。

4 下一步工作

目前針對(duì)復(fù)雜數(shù)據(jù)流的在線集成分類算法的研究已經(jīng)有了很大的進(jìn)展，但是仍然存在著許多挑戰(zhàn)及有待解決的問(wèn)題，需要進(jìn)一步研究以優(yōu)化算法來(lái)處理更加復(fù)雜的問(wèn)題。下面將探討目前所存在的挑戰(zhàn)和問(wèn)題，并給出下一步研究方向。

a）概念漂移數(shù)據(jù)流中動(dòng)態(tài)選擇集成的研究。概念漂移的存在對(duì)分類器的性能有很大的影響，一般處理方法包括主動(dòng)檢測(cè)漂移然后更新集成以及根據(jù)分類器的性能反饋?zhàn)赃m應(yīng)調(diào)整權(quán)重，但是在一些復(fù)雜概念漂移的情況下效果可能不太理想。未來(lái)可以考慮設(shè)計(jì)一種在線集成框架，包含一個(gè)靜態(tài)分類器用于保存歷史信息及多個(gè)動(dòng)態(tài)分類器用于學(xué)習(xí)最新概念，根據(jù)分類器對(duì)最近實(shí)例的分類誤差進(jìn)行動(dòng)態(tài)選擇并加權(quán)決策。

b）不平衡數(shù)據(jù)流中的混合概念漂移問(wèn)題研究。

對(duì)于不平衡數(shù)據(jù)流，概念漂移會(huì)變得更加難以處理，特別是在流中存在著多種漂移類型的情況下。在動(dòng)態(tài)學(xué)習(xí)框架中，少數(shù)類實(shí)例沒(méi)有得到充分的表示，在學(xué)習(xí)過(guò)程中容易被忽視，從而對(duì)于概念的變化非常的不敏感。在之后的研究中，可以考慮結(jié)合bagging集成和動(dòng)態(tài)選擇集成，并使用Kappa值與準(zhǔn)確率的加權(quán)和組合基分類器的結(jié)果，處理類不平衡和多種概念漂移共存的問(wèn)題。

c）噪聲及其他復(fù)雜因素對(duì)在線學(xué)習(xí)的挑戰(zhàn)。在線學(xué)習(xí)由于其過(guò)程的特殊性，一次學(xué)習(xí)一個(gè)實(shí)例，所以噪聲對(duì)于在線算法的影響是極大的。且現(xiàn)實(shí)世界中的數(shù)據(jù)更加復(fù)雜，多標(biāo)簽、類重疊、多類不平衡等問(wèn)題也對(duì)分類器的性能造成了極大的挑戰(zhàn)。因此，在線集成分類算法如何應(yīng)對(duì)噪聲以及在更復(fù)雜的數(shù)據(jù)流中學(xué)習(xí)也是一個(gè)值得探討的問(wèn)題。

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

本文首次從概念漂移數(shù)據(jù)流以及不平衡數(shù)據(jù)流兩個(gè)方面對(duì)復(fù)雜數(shù)據(jù)流在線集成分類算法進(jìn)行了綜述。首先，從集成策略的角度對(duì)算法進(jìn)行了分類與總結(jié)，并對(duì)比了使用不同集成模型的在線集成分類算法的性能。其次，從主動(dòng)和被動(dòng)兩方面對(duì)概念漂移、從算法級(jí)和數(shù)據(jù)級(jí)兩方面對(duì)概念漂移數(shù)據(jù)流、不平衡數(shù)據(jù)流的在線集成分類方法做了詳細(xì)的總結(jié)，并分析對(duì)比了代表性算法的時(shí)空復(fù)雜度以及在相同數(shù)據(jù)集下的實(shí)驗(yàn)結(jié)果，對(duì)算法所用的技術(shù)以及優(yōu)缺點(diǎn)等進(jìn)行了總結(jié)。最后，針對(duì)復(fù)雜數(shù)據(jù)流的在線集成分類算法所面臨的挑戰(zhàn)，提出了下一步研究方向以及復(fù)雜問(wèn)題的解決思路。

參考文獻(xiàn)：

［1］Sousa M R，Gama J，Brandao E.A new dynamic modeling framework for credit risk assessment［J］.Expert Systems with Applications，2016，45：341-351.

［2］Meseguer J，Puig V，Escobet T.Fault diagnosis using a timed discrete-event approach based on interval observers：application to sewer networks［J］.IEEE Trans on Systems，Man，and Cybernetics-Part A：Systems and Humans，2010，40（5）：900-916.

［3］Sun Yu，Tang Ke，Minku L L，et al.Online ensemble learning of data streams with gradually evolved classes［J］.IEEE Trans on Know-ledge and Data Engineering，2016，28（6）：1532-1545.

［4］Hoi S C H，Sahoo D，Lu Jing，et al.Online learning：a comprehensive survey［J］.Neurocomputing，2021，459：249-289.

［5］Dong Xibin，Yu Zhiwen，Cao Wenming，et al.A survey on ensemble learning［J］.Frontiers of Computer Science，2020，14：241-258.

［6］Oza N C，Russell S J.Online bagging and boosting［C］//Proc of the 8th International Workshop on Artificial Intelligence and Statistics.Piscataway，NJ：IEEE Press，2001：229-236.

［7］Santos S G T C，Gon?alves J P M，Silva G D S，et al.Speeding up recovery from concept drifts［C］//Proc of European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases.Piscataway，NJ：IEEE Press，2014：179-194.

［8］Wang Shuo，Minku L L，Yao Xin.A learning framework for online class imbalance learning［C］//Proc of IEEE Symposium on Computational Intelligence and Ensemble Learning.Piscataway，NJ：IEEE Press，2013：36-45.

［9］Gomes H M，Barddal J P，Enembreck F，et al.A survey on ensemble learning for data stream classification［J］.ACM Computing Surveys，2017，50（2）：1-36.

［10］杜詩(shī)語(yǔ)，韓萌，申明堯，等.概念漂移數(shù)據(jù)流集成分類算法綜述［J］.計(jì)算機(jī)工程，2020，46（1）：15-24，30.（Du Shiyu，Han Meng，Shen Mingyao，et al.Survey of ensemble classification algorithms for data streams with concept drift［J］.Computer Engineering，2020，46（1）：15-24，30.

［11］張喜龍，韓萌，陳志強(qiáng)，等.面向復(fù)雜數(shù)據(jù)流的集成分類綜述［J］.廣西師范大學(xué)學(xué)報(bào)：自然科學(xué)版，2022，40（4）：1-21.（Zhang Xilong，Han Meng，Chen Zhiqiang，et al.Survey of ensemble classification methods for complex data stream［J］.Journal of Guangxi Normal University：Natural Science Edition，2022，40（4）：1-21.

［12］Mienye I D，Sun Yanxia.A survey of ensemble learning：concepts，algorithms，applications，and prospects［J］.IEEE Access，2022，10：99129-99149.

［13］翟婷婷，高陽(yáng)，朱俊武.面向流數(shù)據(jù)分類的在線學(xué)習(xí)綜述［J］.軟件學(xué)報(bào)，2020，31（4）：912-931.（Zhai Tingting，Gao Yang，Zhu Junwu.Survey of online learning algorithms for streaming data classification［J］.Journal of Software，2020，31（4）：912-931.）

［14］Bifet A，Holmes G，Pfahringer B，et al.Improving adaptive bagging methods for evolving data streams［C］//Proc of the 1st Asian Confe-rence on Machine Learning.Berlin：Springer，2009：23-37.

［15］Bifet A，Holmes G，Pfahringer B.Leveraging bagging for evolving data streams［C］//Proc of European conference on Machine Learning and Knowledge Discovery in Databases.Berlin：Springer，2010：135-150.

［16］Bernardo A，Della V E.SMOTE-OB：combining SMOTE and online bagging for continuous rebalancing of evolving data streams［C］//Proc of IEEE International Conference on Big Data.Piscataway，NJ：IEEE Press，2021：5033-5042.

［17］Fernández A，Garcia S，Herrera F，et al.SMOTE for learning from imbalanced data：progress and challenges，marking the 15-year anniversary［J］.Journal of Artificial Intelligence Research，2018，61：863-905.

［18］Lughofer E.Evolving fuzzy systems—fundamentals，reliability，interpretability，useability，applications［M］//Handbook on Computational Intelligence.2016：67-135.

［19］Lughofer E，Pratama M，krjanc I.Online bagging of evolving fuzzy systems［J］.Information sciences，2021，570：16-33.

［20］Saffari A，Leistner C，Santner J，et al.On-line random forests［C］//Proc of the 3rd IEEE ICCV Workshop on On-line Computer Vision.Piscataway，NJ：IEEE Press，2009：1393-1400.

［21］王愛(ài)平，萬(wàn)國(guó)偉，程志全，等.支持在線學(xué)習(xí)的增量式極端隨機(jī)森林分類器［J］.軟件學(xué)報(bào)，2011，22（9）：2059-2074.（Wang Ai-ping，Wan Guowei，Cheng Zhiquan，et al.Incremental learning extremely random forest classifier for online learning［J］.Journal of Software，2011，22（9）：2059-2074.）

［22］Gomes H M，Bifet A，Read J，et al.Adaptive random forests for evolving data stream classification［J］.Machine Learning，2017，106：1469-1495.

［23］De Barros R S M，De Carvalho S S G T，Júnior P M G.A boosting-like online learning ensemble［C］//Proc of International Joint Conference on Neural Networks.Piscataway，NJ：IEEE Press，2016：1871-1878.

［24］Santos S G T C，De Barros R S M.Online AdaBoost-based methods for multiclass problems［J］.Artificial Intelligence Review，2020，53：1293-1322.

［25］Baidari I，Honnikoll N.Accuracy weighted diversity-based online boosting［J］.Expert Systems with Applications，2020，160：113723.

［26］Honnikoll N，Baidari I.Mean error rate weighted online boosting me-thod［J］.The Computer Journal，2023，66（1）：1-15.

［27］Matthews B W.Comparison of the predicted and observed secondary structure of T4 phage lysozyme［J］.Biochimica et Biophysica Acta（BBA）-Protein Structure，1975，405（2）：442-451.

［28］Frías-Blanco I，Verdecia-Cabrera A，Ortiz-Díaz A，et al.Fast adaptive stacking of ensembles［C］//Proc of the 31st Annual ACM Symposium on Applied Computing.New York：ACM Press，2016：929-934.

［29］Ortiz-Díaz A A，Baldo F，Marino L M P，et al.Fase-AL-adaptation of fast adaptive stacking of ensembles for supporting active learning［EB/OL］.（2020）.https：//arxiv.org/abs/2001.11466.

［30］Jiang Weili，Chen Zhenhua，Xiang Yan，et al.SSEM：a novel self-adaptive stacking ensemble model for classification［J］.IEEE Access，2019，7：120337-120349.

［31］Büyük?akir A，Bonab H，Can F.A novel online stacked ensemble for multi-label stream classification［C］//Proc of the 27th ACM International Conference on Information and Knowledge Management.New York：ACM Press，2018：1063-1072.

［32］Guo Husheng，Zhang Shuai，Wang Wenjian.Selective ensemble-based online adaptive deep neural networks for streaming data with concept drift［J］.Neural Networks，2021，142：437-456.

［33］Gama J，Medas P，Castillo G，et al.Learning with drift detection［C］//Proc of the 17th Advances in Artificial Intelligence.Berlin：Springer，2004：286-295.

［34］Baena-García M，Del Campo-vila J，F(xiàn)idalgo R，et al.Early drift detection method［C］//Proc of the 4th International Workshop on Knowledge Discovery from Data Streams.2006：77-86.

［35］Barros R S M，Cabral D R L，Gon?alves Jr P M，et al.RDDM：reactive drift detection method［J］.Expert Systems with Applications，2017，90：344-355.

［36］Baidari I，Honnikoll N.Bhattacharyya distance based concept drift detection method for evolving data stream［J］.Expert Systems with Applications，2021，183：115303.

［37］Micevska S，Awad A，Sakr S.SDDM：an interpretable statistical concept drift detection method for data streams［J］.Journal of Intelligent Information Systems，2021，56：459-484.

［38］Bifet A，Gavalda R.Learning from time-changing data with adaptive windowing［C］//Proc of SIAM International Conference on Data Mi-ning.［S.l.］：Society for Industrial and Applied Mathematics，2007：443-448.

［39］Frias-Blanco I，Del Campo-vila J，Ramos-Jimenez G，et al.Online and non-parametric drift detection methods based on Hoeffdings bounds［J］.IEEE Trans on Knowledge and Data Engineering，2014，27（3）：810-823.

［40］Pesaranghader A，Viktor H L.Fast Hoeffding drift detection method for evolving data streams［C］//Proc of Machine Learning and Knowledge Discovery in Databases.Cham：Springer，2016：96-111.

［41］Pesaranghader A，Viktor H L，Paquet E.McDiarmid drift detection methods for evolving data streams［C］//Proc of International Joint Conference on Neural Networks.Piscataway，NJ：IEEE Press，2018：1-9.

［42］胡陽(yáng)，孫自強(qiáng).基于 McDiarmid 邊界的自適應(yīng)加權(quán)概念漂移檢測(cè)方法［J］.華東理工大學(xué)學(xué)報(bào)：自然科學(xué)版，2023，49（2）：1-10.（Hu Yang，Sun Ziqiang.Weight adaptive concept drift detection me-thod based on McDiarmid boundary［J］.Journal of East China University of Science and Technology，2023，49（3）：1-10.）

［43］Yan M M W.Accurate detecting concept drift in evolving data streams［J］.ICT Express，2020，6（4）：332-338.

［44］Kolter J Z，Maloof M A.Dynamic weighted majority：an ensemble method for drifting concepts［J］.The Journal of Machine Learning Research，2007，8：2755-2790.

［45］Sidhu P，Bhatia M P S.A two ensemble system to handle concept drifting data streams：recurring dynamic weighted majority［J］.International Journal of Machine Learning and Cybernetics，2019，10：563-578.

［46］Brzeziński D，Stefanowski J.Accuracy updated ensemble for data streams with concept drift［C］//Proc of the 6th International Confe-rence on Hybrid Artificial Intelligence Systems.Berlin：Springer，2011：155-163.

［47］Wang Haixun，F(xiàn)an Wei，Yu P S，et al.Mining concept-drifting data streams using ensemble classifiers［C］//Proc of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York：ACM Press，2003：226-235.

［48］Brzezinski D，Stefanowski J.Combining block-based and online me-thods in learning ensembles from concept drifting data streams［J］.Information Sciences，2014，265：50-67.

［49］Gu Xiaofeng，Xu Jiawen，Huang Shijing，et al.An improving online accuracy updated ensemble method in learning from evolving data streams［C］//Proc of the 11th International Computer Conference on Wavelet Active Media Technology and Information Processing.Pisca-taway，NJ：IEEE Press，2014：430-433.

［50］Ren Siqi，Liao Bo，Zhu Wen，et al.Knowledge-maximized ensemble algorithm for different types of concept drift［J］.Information Sciences，2018，430：261-281.

［51］Cano A，Krawczyk B.Kappa updated ensemble for drifting data stream mining［J］.Machine Learning，2020，109：175-218.

［52］Minku L L，Yao Xin.DDD：a new ensemble approach for dealing with concept drift［J］.IEEE Trans on Knowledge and Data Enginee-ring，2011，24（4）：619-633.

［53］Sidhu P，Bhatia M P S.A novel online ensemble approach to handle concept drifting data streams：diversified dynamic weighted majority［J］.International Journal of Machine Learning and Cyberne-tics，2018，9：37-61.

［54］Van Rijn J N，Holmes G，Pfahringer B，et al.Having a blast：meta-learning and heterogeneous ensembles for data streams［C］//Proc of IEEE International Conference on Data Mining.Piscataway，NJ：IEEE Press，2015：1003-1008.

［55］Museba T，Nelwamondo F，Ouahada K.An adaptive heterogeneous online learning ensemble classifier for nonstationary environments［J］.Computational Intelligence and Neuroscience，2021，2021：article ID 6669706.

［56］Idrees M M，Minku L L，Stahl F，et al.A heterogeneous online lear-ning ensemble for non-stationary environments［J］.Knowledge-Based Systems，2020，188：104983.

［57］Museba T，Nelwamondo F，Ouahada K.ADES：a new ensemble diversity-based approach for handling concept drift［J］.Mobile Information Systems，2021，2021：1-17.

［58］Sarnovsky M，Kolarik M.Classification of the drifting data streams using heterogeneous diversified dynamic class-weighted ensemble［J］.PeerJ Computer Science，2021，7：e459.

［59］Wang Shuo，Minku L L，Yao Xin.Resampling-based ensemble me-thods for online class imbalance learning［J］.IEEE Trans on Know-ledge and Data Engineering，2014，27（5）：1356-1368.

［60］Wang Shuo，Minku L L，Yao Xin.Dealing with multiple classes in online class imbalance learning［C］//Proc of the 25th International Joint Conference on Artificial Intelligence.Palo Alto，CA：AAAI Press，2016：2118-2124.

［61］Olaitan O M，Viktor H L.SCUT-DS：learning from multi-class imba-lanced Canadian weather data［C］//Proc of the 24th International Symposium on Foundations of Intelligent Systems.Cham：Springer，2018：291-301.

［62］Vafaie P，Viktor H，Michalowski W.Multi-class imbalanced semi-supervised learning from streams through online ensembles［C］//Proc of International Conference on Data Mining Workshops.Washington DC：IEEE Computer Society，2020：867-874.

［63］Czarnowski I.Weighted ensemble with one-class classification and over-sampling and instance selection（WECOI）：an approach for lear-ning from imbalanced data streams［J］.Journal of Computational Science，2022，61：101614.

［64］Wang Boyu，Pineau J.Online bagging and boosting for imbalanced data streams［J］.IEEE Trans on Knowledge and Data Engineering，2016，28（12）：3353-3366.

［65］Du Hongle，Zhang Yan，Gang Ke，et al.Online ensemble learning algorithm for imbalanced data stream［J］.Applied Soft Computing，2021，107：107378.

［66］Loezer L，Enembreck F，Barddal J P，et al.Cost-sensitive learning for imbalanced data streams［C］//Proc of the 35th Annual ACM Symposium on Applied Computing.New York：ACM Press，2020：498-504.

［67］Zhu Qiuming.On the performance of Matthews correlation coefficient（MCC） for imbalanced dataset［J］.Pattern Recognition Letters，2020，136：71-80.

［68］Ren Siqi，Zhu Wen，Liao Bo，et al.Selection-based resampling ensemble algorithm for nonstationary imbalanced stream data learning［J］.Knowledge-Based Systems，2019，163：705-722.

［69］Zhang Hang，Liu Weike，Wang Shuo，et al.Resample-based ensemble framework for drifting imbalanced data streams［J］.IEEE Access，2019，7：65103-65115.

［70］Ancy S，Paulraj D.Handling imbalanced data with concept drift by applying dynamic sampling and ensemble classification model［J］.Computer Communications，2020，153：553-560.

［71］Cano A，Krawczyk B.ROSE：robust online self-adjusting ensemble for continual learning on imbalanced drifting data streams［J］.Machine Learning，2022，111（7）：2561-2599.

［72］Han Men，Zhang Xilong，Chen Zhiqiang，et al.Dynamic ensemble selection classification algorithm based on window over imbalanced drift data stream［J］.Knowledge and Information Systems，2023，65（3）：1105-1128.