復(fù)雜數(shù)據(jù)流在線集成分類算法綜述

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

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

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

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

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

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

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

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

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

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

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

1 在線集成策略

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

1.1 bagging

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

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

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

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

在線bagging由于其弱分類器投票組合的簡易性以及對新實例的泊松重采樣理論，經(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是一種序列化的集成方法。它通過迭代地訓(xùn)練一組弱分類器（例如決策樹）來構(gòu)建一個強(qiáng)分類器。在每次迭代中，boosting算法根據(jù)先前分類器的表現(xiàn)來調(diào)整樣本的權(quán)重，將更多的關(guān)注放在分類錯誤的樣本，逐步提高對難以分類的樣本的預(yù)測準(zhǔn)確性。OzaBoost［6］通過泊松分布參數(shù)確定實例的權(quán)重，該算法通過式（1）對實例權(quán)重進(jìn)行調(diào)整。

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

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

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

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

由于基于累積權(quán)重的實例分配方案容易受到噪聲等數(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)前實例分配當(dāng)前分類器權(quán)重，這些改進(jìn)和新定義的加權(quán)方案提高了集成的整體精度。最近，Honnikoll 等人［26］提出了平均錯誤率加權(quán)在線提升方法（mean error rate weighted online boosting，MWOB），該算法利用個體基分類器的平均錯誤率來實現(xiàn)實例的有效權(quán)重分布，而不是OzaBoost中基于弱分類器之前的累積權(quán)重，MWOB在實驗數(shù)據(jù)集上均取得了最佳的預(yù)測性能。

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

1.3 stacking

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

受限于stacking模型的訓(xùn)練過程，大多stacking算法及其變體都應(yīng)用于批量環(huán)境，對于在線環(huán)境下的研究屈指可數(shù)，以下是本文對現(xiàn)有的在線 stacking算法的總結(jié)。Frías-Blanco 等人［28］提出了一種快速自適應(yīng)堆疊集成（fast adaptive stacking of ensembles，F(xiàn)ASE）方法，集成中包括一個用于穩(wěn)定概念的主分類器。出現(xiàn)漂移警告時則訓(xùn)練一個備選分類器，若出現(xiàn)漂移確認(rèn)，該分類器將取代主分類器，F(xiàn)ASE能夠在恒定的時間和空間計算復(fù)雜度下處理輸入數(shù)據(jù)。FASE-AL［29］提出了對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的基分類器，通過遺傳算法自動選擇最優(yōu)基分類器組合以及組合的超參數(shù)。GOOWE-ML［31］是一種用于多標(biāo)簽分類的在線動態(tài)加權(quán)堆疊集成算法，該集成為分類器的相關(guān)性得分構(gòu)建了一個空間模型，并使用該模型為其組件分類器分配最優(yōu)權(quán)重，該模型可用于任何現(xiàn)有的增量多標(biāo)簽分類算法作為其基分類器。

1.4 小結(jié)

本章從bagging、boosting、stacking三種常用集成策略的在線版本及變體介紹了在線集成分類算法。通過現(xiàn)有研究的實驗對比發(fā)現(xiàn)，一般的boosting模型在準(zhǔn)確度方面并不優(yōu)于bagging模型。潛在原因可能是：與bagging多數(shù)投票的簡單方式不同，boosting算法根據(jù)基分類器的預(yù)測性能進(jìn)行權(quán)重分配，這種方式在某些情況下的準(zhǔn)確度較不穩(wěn)定，且容易受到噪聲的影響，從而對噪聲數(shù)據(jù)進(jìn)行不必要的訓(xùn)練，并在之后影響到基分類器的權(quán)重分配。而stacking模型用于提升預(yù)測結(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ù)據(jù)集electricity中，最新的算法MWOB、AWDOB取得了最佳表現(xiàn)，分別為90%、93%，其次為LevBag、ADOB、AdwinBoost、AdwinBag，分別為90%、88%、87%、86%，這種情況可以解釋為MWOB、AWDOB分別基于精度和平均錯誤率修改了錯誤分類實例的權(quán)重計算公式，而不是之前的累積權(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ù)、對比算法和優(yōu)缺點等方面對在線集成分類算法進(jìn)行了總結(jié)。

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

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

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

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

2.1.1 基于主動檢測的方法

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

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

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

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

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

pt+σt≥pmin+2σminwarning

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

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

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

2）基于窗口的方法

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

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

ΔPt=Pt-Pmin（4）

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

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

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

1）基于性能反饋

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

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

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

2）多樣性集成

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

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

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

多樣性也可以通過異構(gòu)集成來實現(xiàn)。針對基分類器的類型異同，集成可分為同構(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］引入了一個在線性能評估框架，在整個流中該框架以不同的方式對集合成員的投票進(jìn)行加權(quán)，并應(yīng)用這種技術(shù)構(gòu)建一個簡單的新穎集成技術(shù)BLAST（best last的縮寫）以快速進(jìn)行異構(gòu)集成。Museba等人［55］提出一種基于精度和多樣性的異構(gòu)動態(tài)集成選擇方法（HDES-AD），該方法可以自動為特定概念選擇最多樣化和最準(zhǔn)確的基本模型，以便在動態(tài)環(huán)境中長時間使用。異構(gòu)動態(tài)加權(quán)多數(shù)（heterogeneous dynamic weighted majority，HDWM）［56］將DWM算法轉(zhuǎn)變?yōu)楫悩?gòu)集成，HDWM 會自動選擇當(dāng)前最佳的基本模型類型，通過智能切換基分類器來提高預(yù)測性能。ADES［57］提出了一種在線異構(gòu)集成，它使用多樣性和準(zhǔn)確性作為評估指標(biāo)來選擇最佳集成，并創(chuàng)建不同多樣性水平的集成，以最小的開銷表現(xiàn)出了良好的性能。DDCW［58］利用動態(tài)加權(quán)方案和一種保持集成多樣性的機(jī)制用于漂移數(shù)據(jù)流分類，該方法使用樸素貝葉斯（NB）以及霍夫丁樹（Hoeffding tree）來構(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í)場景中，這種困難會變得更加嚴(yán)重，因為無法看到數(shù)據(jù)的全貌，而且數(shù)據(jù)可能會動態(tài)變化。在線類不平衡問題的現(xiàn)有方法可大致分為算法級方法和數(shù)據(jù)級方法，前者通過在設(shè)計算法時考慮不同的誤分類成本，從而使正實例的誤分類代價高于負(fù)實例。在數(shù)據(jù)級方法的情況下，添加預(yù)處理步驟，通過對負(fù)類進(jìn)行欠采樣或?qū)φ愡M(jìn)行過采樣，重新平衡類分布。

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

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

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

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

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

2.2.2 基于代價敏感的方法

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

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

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

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

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

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

2.2.3 其他工作

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

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

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

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

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

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

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

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

3 算法性能對比與分析

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

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

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

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

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

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

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

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

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

3.3 算法性能對比

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

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

a）漂移檢測方法。在數(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的對比實驗中，基分類器分別采用HT以及NB，MDDM算法的平均準(zhǔn)確率最高為89.56。與基于窗口的算法FHDDM與MDDM相比，基于統(tǒng)計的算法SDDM具有最低的假陽性率和假陰性率，F(xiàn)PR及FNR均為0，而FHDDM與MDDM均為0.03與0.02。同樣在electricity真實數(shù)據(jù)集上，BDDM、MDDM算法均取得了最佳的準(zhǔn)確率，分別為85.68、83.47。在這兩個數(shù)據(jù)集的實驗數(shù)據(jù)中，基于統(tǒng)計的模型在平均準(zhǔn)確率上比基于窗口的模型高約2.5%。

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

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

random RBF數(shù)據(jù)集中，在與OOB等算法的對比實驗中，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，并無明顯差別，這表明SMOTE在過采樣少數(shù)類中的作用有限。而MUOB由于欠采樣的數(shù)據(jù)量過多，導(dǎo)致表現(xiàn)不佳，G-mean值僅為0.741。當(dāng)在數(shù)據(jù)流中加入了概念漂移之后，IOE的G-mean值沒有明顯的變化，而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的對比實驗中，不論不平衡比率如何，ROSE算法在Kappa值及AUC值均取得了最高值，在不平衡比率為5的情況下，ROSE、OOB、UOB的AUC值分別為88.33、85.93、85.87。并且在靜態(tài)及漂移不平衡比率的情況下ROSE的平均算法排名都在第二位左右。

4 下一步工作

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

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

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

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

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

5 結(jié)束語

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

參考文獻(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ù)據(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é)報：自然科學(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］翟婷婷，高陽，朱俊武.面向流數(shù)據(jù)分類的在線學(xué)習(xí)綜述［J］.軟件學(xué)報，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］王愛平，萬國偉，程志全，等.支持在線學(xué)習(xí)的增量式極端隨機(jī)森林分類器［J］.軟件學(xué)報，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］胡陽，孫自強(qiáng).基于 McDiarmid 邊界的自適應(yīng)加權(quán)概念漂移檢測方法［J］.華東理工大學(xué)學(xué)報：自然科學(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.