復雜數據流在線集成分類算法綜述

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

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

關鍵詞：在線學習；集成學習；概念漂移；不平衡

中圖分類號：TP391?? 文獻標志碼：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 引言

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

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

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

本文對近年來所提出的在線集成分類方法進行了匯總，然后從集成策略的不同以及針對不同數據流對象所應用的集成技術對在線集成分類算法進行了詳細的描述和分析，本文的框架結構如圖2所示，主要貢獻如下：

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

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

c）在使用同一數據集的條件下，對在線集成分類算法性能的實驗結果進行了分析與對比。

1 在線集成策略

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

1.1 bagging

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

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

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

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

在線bagging由于其弱分類器投票組合的簡易性以及對新實例的泊松重采樣理論，經常與其他數據重采樣技術相結合，用于處理不平衡數據，詳細的內容將在第2章進行描述。

1.2 boosting

傳統的批量boosting算法與bagging算法類似，但不同于bagging的并行學習，boosting是一種序列化的集成方法。它通過迭代地訓練一組弱分類器（例如決策樹）來構建一個強分類器。在每次迭代中，boosting算法根據先前分類器的表現來調整樣本的權重，將更多的關注放在分類錯誤的樣本，逐步提高對難以分類的樣本的預測準確性。OzaBoost［6］通過泊松分布參數確定實例的權重，該算法通過式（1）對實例權重進行調整。

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

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

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

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

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

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

1.3 stacking

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

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

1.4 小結

本章從bagging、boosting、stacking三種常用集成策略的在線版本及變體介紹了在線集成分類算法。通過現有研究的實驗對比發現，一般的boosting模型在準確度方面并不優于bagging模型。潛在原因可能是：與bagging多數投票的簡單方式不同，boosting算法根據基分類器的預測性能進行權重分配，這種方式在某些情況下的準確度較不穩定，且容易受到噪聲的影響，從而對噪聲數據進行不必要的訓練，并在之后影響到基分類器的權重分配。而stacking模型用于提升預測結果，在整體上優于bagging模型以及boosting模型，但通常復雜度較高。

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

2 復雜數據流在線集成分類技術

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

2.1 概念漂移數據流

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

2.1.1 基于主動檢測的方法

主動方法通過監測數據流分類性能指標或者統計數據屬性分布，并設置一個閾值用來判別是否發生了概念漂移，一旦檢測到數據流中概念漂移的發生，算法將會采取重置學習模型等方法來適應數據流中新的概念。概念漂移的檢測方式有多種，主要可分為基于統計的方法和基于窗口的方法。

1）基于統計的方法

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

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

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

pt+σt≥pmin+2σminwarning

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

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

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

2）基于窗口的方法

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

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

ΔPt=Pt-Pmin（4）

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

2.1.2 基于被動自適應的方法

被動方法不主動檢測概念漂移的出現，但是會通過不斷地更新模型，如根據基分類器的性能動態地調整其權重，使得模型適應數據流中新的概念。被動方法中一般有根據分類器的準確率或其他性能指標進行動態加權以及保持集成的多樣性水平等方法適應概念漂移。

1）基于性能反饋

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

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

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

2）多樣性集成

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

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

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

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

2.2 不平衡數據流

不平衡數據流中最重要的特征就是傾斜的類分布。通常，少數類（正類）樣本是更感興趣的類別，但可能被忽略并被視為噪聲。在在線學習場景中，這種困難會變得更加嚴重，因為無法看到數據的全貌，而且數據可能會動態變化。在線類不平衡問題的現有方法可大致分為算法級方法和數據級方法，前者通過在設計算法時考慮不同的誤分類成本，從而使正實例的誤分類代價高于負實例。在數據級方法的情況下，添加預處理步驟，通過對負類進行欠采樣或對正類進行過采樣，重新平衡類分布。

2.2.1 基于數據重采樣的方法

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

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

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

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

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

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

2.2.2 基于代價敏感的方法

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

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

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

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

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

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

2.2.3 其他工作

在不平衡數據流方面同樣也存在著概念漂移的問題，當與概念漂移相結合時，不平衡比率不再是靜態的，它將隨著流的進展而變化，例如少數類轉變為多數類。因此，不僅要監視每個類的屬性變化，還要監視其頻率的變化。新類可能出現，舊類可能消失，這些現象對大多數現有算法構成了重大挑戰。含概念漂移的不平衡數據分類也是目前研究的一個重點內容，用戶興趣推薦、社交媒體分析等現實案例都是很好的應用。

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

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

2.3 算法復雜度分析

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

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

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

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

3 算法性能對比與分析

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

3.1 數據集介紹

本節對所使用的同一數據集進行了介紹，表4展示了使用相同數據集的算法。數據集描述如下。

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

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

c）random RBF：RBF生成器是一個使用隨機質心創建新實例的合成數據集，每個質心由類標簽、權重、位置和標準偏差定義。實例由50個屬性和2個類描述，其中一個類是欠采樣的，每1 000個實例產生一定的不平衡比率。

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

3.2 性能評估指標

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

3.3 算法性能對比

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

3.3.1 概念漂移數據流

a）漂移檢測方法。在數據大小為50 KB的LED突變漂移數據集上，相較于DDM與FHDDM，BDDM取得了50.24的最佳準確率，其余兩者為49.14、47.66，并且在precision、recall、MCC指標上BDDM均表現出最優的性能，均為0.75。在與DDM、ADWIN、FHDDM的對比實驗中，基分類器分別采用HT以及NB，MDDM算法的平均準確率最高為89.56。與基于窗口的算法FHDDM與MDDM相比，基于統計的算法SDDM具有最低的假陽性率和假陰性率，FPR及FNR均為0，而FHDDM與MDDM均為0.03與0.02。同樣在electricity真實數據集上，BDDM、MDDM算法均取得了最佳的準確率，分別為85.68、83.47。在這兩個數據集的實驗數據中，基于統計的模型在平均準確率上比基于窗口的模型高約2.5%。

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

3.3.2 不平衡數據流

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

4 下一步工作

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

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

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

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

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

5 結束語

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

參考文獻：

［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］杜詩語，韓萌，申明堯，等.概念漂移數據流集成分類算法綜述［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］張喜龍，韓萌，陳志強，等.面向復雜數據流的集成分類綜述［J］.廣西師范大學學報：自然科學版，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］翟婷婷，高陽，朱俊武.面向流數據分類的在線學習綜述［J］.軟件學報，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］王愛平，萬國偉，程志全，等.支持在線學習的增量式極端隨機森林分類器［J］.軟件學報，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，Fidalgo 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］胡陽，孫自強.基于 McDiarmid 邊界的自適應加權概念漂移檢測方法［J］.華東理工大學學報：自然科學版，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，Fan 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.