穆棟梁，韓 萌，李 昂，劉淑娟，高智慧

（北方民族大學(xué) 計算機科學(xué)與工程學(xué)院，銀川 750021）

0 引言

在信息時代，數(shù)據(jù)不斷高速產(chǎn)生且隨時間的推移不斷變化、增長，量是無限的，含有這些特征的數(shù)據(jù)被稱為數(shù)據(jù)流，如網(wǎng)絡(luò)數(shù)據(jù)、金融數(shù)據(jù)、傳感數(shù)據(jù)和電網(wǎng)數(shù)據(jù)等。研究發(fā)現(xiàn)，在真實的數(shù)據(jù)流環(huán)境中，還存在著多種復(fù)雜數(shù)據(jù)流類型，如不平衡、多標(biāo)簽、概念演化和含噪聲的數(shù)據(jù)流。隨著時間的推移，流數(shù)據(jù)的數(shù)據(jù)分布發(fā)生了不可預(yù)見的變化，這些變化被認(rèn)為是概念漂移［1］。概念漂移指目標(biāo)類的底層分布的變化，具體地，概念漂移就是在一組有序?qū)嵗竭_(dá)后，之前的目標(biāo)概念發(fā)生了改變。概念漂移使前后數(shù)據(jù)的分布發(fā)生變化，影響了數(shù)據(jù)流的穩(wěn)定性，使得之前的分類模型不再適用于漂移后的數(shù)據(jù)，導(dǎo)致傳統(tǒng)的機器學(xué)習(xí)模型在發(fā)生了概念漂移時分類性能顯著下降。含有漂移特征的數(shù)據(jù)流，稱為可變數(shù)據(jù)流或概念漂移數(shù)據(jù)流［1］。當(dāng)概念漂移問題出現(xiàn)在復(fù)雜類型數(shù)據(jù)流中，這一問題就會隨著底層數(shù)據(jù)的演變更加難以處理。例如：顧客的網(wǎng)上購物偏好，由于內(nèi)部或外部原因，不常購買物品轉(zhuǎn)變成了常購買物品；某地天氣預(yù)報由于特殊原因出現(xiàn)了極端天氣的情況；網(wǎng)絡(luò)攻擊檢測中，首次出現(xiàn)新類型的攻擊方式等。

目前多種數(shù)據(jù)流分類方法大多都僅處理復(fù)雜類型數(shù)據(jù)流的分類問題，沒有考慮復(fù)雜數(shù)據(jù)流類型和概念漂移聯(lián)合條件下的數(shù)據(jù)流分類問題。Wu 等［2］提出基于不平衡數(shù)據(jù)集重采樣的集成學(xué)習(xí)模型。Tao 等［3］提出基于自適應(yīng)代價權(quán)重的支持向量機代價敏感集成方法用于不平衡數(shù)據(jù)流分類。Nguyen 等［4］介紹了一種可擴展的基于在線可變推理的多標(biāo)簽數(shù)據(jù)分類集成方法，其中使用隨機投影創(chuàng)建集成系統(tǒng)。Xia 等［5］利用標(biāo)簽相關(guān)性和集成成員的權(quán)值學(xué)習(xí)過程解決分類器選擇的問題，并處理成對標(biāo)簽相關(guān)性與多標(biāo)簽分類性能之間的關(guān)系。以上方法是高效的數(shù)據(jù)流分類方法，然而這些方法的分類器在概念漂移復(fù)雜數(shù)據(jù)流中受到概念漂移的干擾，從而出現(xiàn)類不平衡、標(biāo)簽轉(zhuǎn)換、新類出現(xiàn)以及噪聲干擾的問題，使得性能嚴(yán)重下降，因此這些方法并不適應(yīng)于概念漂移復(fù)雜數(shù)據(jù)流分類。

在現(xiàn)有的數(shù)據(jù)流分類綜述中，杜詩語等［6］對突變、漸變、重復(fù)和增量四種類型的漂移數(shù)據(jù)流的分類方法進(jìn)行綜述，主要從集成學(xué)習(xí)的策略角度進(jìn)行了分析；Hu 等［7］僅從概念漂移的類型方面進(jìn)行了綜述，對漂移檢測方法進(jìn)行了分類，沒有將漂移處理方法與集成方法聯(lián)合進(jìn)行闡述；Zhang 等［8］對不平衡數(shù)據(jù)流、非標(biāo)準(zhǔn)數(shù)據(jù)流等復(fù)雜數(shù)據(jù)流集成分類進(jìn)行了綜述，但未對含概念漂移的復(fù)雜數(shù)據(jù)流分類進(jìn)行介紹。以上研究沒有專門從概念漂移復(fù)雜數(shù)據(jù)流分類的角度展開闡述。本文根據(jù)不同的數(shù)據(jù)流特征，在包含概念漂移的情況下，將其劃分為4 類最常見的類型：不平衡概念漂移數(shù)據(jù)流、概念演化概念漂移數(shù)據(jù)流、多標(biāo)簽概念漂移數(shù)據(jù)流和含噪聲概念漂移數(shù)據(jù)流，并對相應(yīng)的分類方法進(jìn)行了分類。本文框架如圖1 所示。

圖1 本文框架Fig.1 Framework of this paper

本文的主要工作有：

1）對不平衡概念漂移、概念演化概念漂移、多標(biāo)簽概念漂移和含噪聲概念漂移這4 個方面數(shù)據(jù)流分類方法進(jìn)行介紹，并從學(xué)習(xí)方式的角度對分類方法進(jìn)行了分析總結(jié)。

2）從基于塊和基于在線學(xué)習(xí)方式的角度對不平衡概念漂移數(shù)據(jù)流分類算法進(jìn)行分析；從基于聚類和基于模型學(xué)習(xí)方式的角度對概念演化概念漂移數(shù)據(jù)流分類算法進(jìn)行分析；從基于問題轉(zhuǎn)換和算法適應(yīng)的角度對多標(biāo)簽漂移數(shù)據(jù)流分類算法進(jìn)行分析，對使用同一數(shù)據(jù)集的算法，在實驗結(jié)果方面進(jìn)行了詳細(xì)的分析對比。

3）對目前存在于概念漂移復(fù)雜數(shù)據(jù)流中所面臨的挑戰(zhàn)，如在復(fù)雜數(shù)據(jù)流類型中的概念漂移類型檢測及方法、多類不平衡概念漂移數(shù)據(jù)流的分類問題和在特征演化數(shù)據(jù)流中的新穎類檢測問題，進(jìn)行了總結(jié)并提出下一步研究方向。

1 不平衡概念漂移數(shù)據(jù)流分類

在數(shù)據(jù)流環(huán)境下，數(shù)據(jù)流樣本中存在類失衡情況，出現(xiàn)了多數(shù)類和少數(shù)類的區(qū)別，在此過程中同時受到概念漂移的影響，多數(shù)類和少數(shù)類之間發(fā)生轉(zhuǎn)變，從而大幅降低了分類器的分類效果，需要動態(tài)化的學(xué)習(xí)框架以適應(yīng)不穩(wěn)定類概念的演化（概念漂移）是不平衡概念漂移數(shù)據(jù)流中面臨的一個重要難題?；趬K和基于在線的學(xué)習(xí)方式是數(shù)據(jù)流分類中有效的方法，在概念漂移和類不平衡同時存在的條件下，將現(xiàn)有處理不平衡概念漂移數(shù)據(jù)流方法從學(xué)習(xí)方式的角度進(jìn)行劃分。

1.1 基于塊的學(xué)習(xí)方式

基于塊的學(xué)習(xí)方式，實例以數(shù)據(jù)塊的形式連續(xù)出現(xiàn)，數(shù)據(jù)塊的大小通常相等，基于數(shù)據(jù)塊完成對分類器的構(gòu)造、評估和更新，基于塊的方法是數(shù)據(jù)流分類常用的訓(xùn)練方式。

UCB（UnCorrelated Bagging）［9］是解決概念漂移和類失衡最早的算法之一，它基于一個Bagging 框架，通過重采樣平衡數(shù)據(jù)集，基于平衡的數(shù)據(jù)集訓(xùn)練分類器，并根據(jù)基分類器的鑒別能力對其進(jìn)行加權(quán)，被動克服概念漂移。Chen 等［10］提出了一種選擇性遞歸算法SERA（SElectively Recursive Approach），通過引入馬氏距離衡量少數(shù)類概念漂移的嚴(yán)重程度，增加少數(shù)類數(shù)據(jù)的采樣權(quán)重來解決少數(shù)類漂移的問題，對發(fā)生概念漂移的少數(shù)類給予更多的關(guān)注，及時修正分類器。之后，Chen 等［11］又提出了一個遞歸集成算法REA（REcursive Approach），以動態(tài)加權(quán)的方式結(jié)合所有隨時間建立的假設(shè)，對測試數(shù)據(jù)集進(jìn)行預(yù)測，在時間上解決概念漂移。

基于舊實例和新的少數(shù)類是同一分布概率的實例選擇策 略，Hoens 等［12］提出了HUWRS.IP（Heuristic Updatable Weighted Random Subspaces IP），從類不平衡中獲得魯棒性，使用海林格距離（式（1））作為概念漂移檢測的加權(quán)測度，漂移檢測的海林格權(quán)重計算為兩個特征分布之間的少數(shù)類和多數(shù)類海林格距離的平均值（式（2））。

其中：P1和P2是概率測度；p（P1，P2）是P1和P2之間的距離系數(shù)；D1和D2是獨立的概率分布集；f表示特征；n表示特征數(shù)；dH表示海林格距離。

為從批量可用的新數(shù)據(jù)中學(xué)習(xí)，且不必訪問以前批量中的數(shù)據(jù)，Ditzler 等［13-14］基于Learn++學(xué)習(xí)框架提出了集成的增量學(xué)習(xí)法Learn++.CDS（incremental Learning for Concept Drift from Streaming imbalance data）和Learn++.NIE（incremental Learning for Nonstationary and Imbalanced Environments）。Learn++.CDS 使用合成少數(shù)類采樣技術(shù)（Synthetic Minority class Over-sampling TEchnique，SMOTE）減小數(shù)據(jù)的不平衡比例，然后使用Learn++.NSE（incremental Learning for NonStationary Environments）在重新平衡的數(shù)據(jù)集中學(xué)習(xí)概念漂移。Learn++.NIE 使用加權(quán)召回或幾何平均單個類的表現(xiàn)，對概念漂移進(jìn)行有效的跟蹤識別，提高少數(shù)類上的分類性能，避免多數(shù)類分類性能下降。

在DWSE（Dynamic Weighted Selective Ensemble）算法［15］中，對之前數(shù)據(jù)塊中的少數(shù)樣本進(jìn)行重采樣，并吸收之前數(shù)據(jù)塊中的信息構(gòu)建分類器，減少概念漂移的影響。DWSE 算法中定義了基分類器動態(tài)衰減因子計算方法，根據(jù)衰減情況選擇子分類器進(jìn)行消除，使算法更好地處理概念漂移問題。

基于學(xué)習(xí)機的方法為解決不平衡和概念漂移的聯(lián)合問題提供了很好的思路，MOS-ELM（Meta-cognitive Online Sequential Extreme Learning Machine）［16］利用一種基于變化檢測器的自適應(yīng)窗口方法和基于OS-ELM（Online Sequential Extreme Learning Machine）的輸出更新方程同時針對類不平衡和概念漂移，通過減小數(shù)據(jù)塊大小提高處理概念漂移的能力。ESOS-ELM（Ensemble of Subset Online Sequential Extreme Learning Machine）［17］使用重采樣方法進(jìn)行類的平衡。根據(jù)基分類器在與當(dāng)前訓(xùn)練數(shù)據(jù)驗證數(shù)據(jù)集上的性能均值更新基分類器的投票權(quán)重解決概念漂移問題。利用獨立倉庫模塊處理重復(fù)出現(xiàn)的概念漂移，維護一個加權(quán)極端學(xué)習(xí)機器池以保留舊的信息，采用基于閾值技術(shù)和假設(shè)檢驗主動檢測突然和逐漸的概念漂移。

基于塊的集成會消耗大量的內(nèi)存，DUE（Dynamic Updated Ensemble）［18］采用基于塊的增量動態(tài)更新集成方法解決內(nèi)存消耗問題。DUE 使用了一個基于Bagging 的框架獲得相對平衡的數(shù)據(jù)塊，通過分量加權(quán)機制和分量更新機制對概念漂移作出快速反應(yīng)，使用最新的實例周期性地更新先前的分類器以應(yīng)對多種概念漂移。

ECISD（Ensemble Classifier for mining Imbalanced Streaming Data）［19］利用過采樣技術(shù)平衡各類樣本，并周期更新分類器權(quán)重以應(yīng)對概念漂移在分類器的淘汰過程中考慮了各個分類器對集成分類的影響，從而達(dá)到提高分類效果的目的。CIDD-ADODNN（Class Imbalance with concept Drift Detection-ADadelta Optimizer-based Deep Neural Network）［20］采用自適應(yīng)合成技術(shù)處理類不平衡數(shù)據(jù)，此外，應(yīng)用自適應(yīng)滑動窗口技術(shù)對應(yīng)用流數(shù)據(jù)中的概念漂移進(jìn)行識別，通過應(yīng)用堆疊自動編碼器進(jìn)行概念漂移分類以增強估計措施。最后，利用ADODNN 算法進(jìn)行分類。圖2 展示了ADODNN 算法框架。

圖2 ADODNN算法框架Fig.2 ADODNN algorithm framework

1.2 基于在線的學(xué)習(xí)方式

在線學(xué)習(xí)方法可以應(yīng)用于數(shù)據(jù)以塊形式到達(dá)的問題，在線學(xué)習(xí)中，實例不斷從數(shù)據(jù)流中獲得并且只能被處理一次，不需要再次存儲和再處理。在數(shù)據(jù)連續(xù)到達(dá)的情況下，在線算法比典型的批處理算法運行更快、精度更高，因此在線技術(shù)被廣泛地應(yīng)用在數(shù)據(jù)流分類中。基于在線學(xué)習(xí)方式的代表 是Wang 等［21］提出的OOB（Oversampling-based Online Bagging）和UOB（Under-sampling-based Online Bagging）。

Somasundaram 等［22］提出了事務(wù)窗口打包（Transaction Window Bagging，TWB）模型，即并行增量學(xué)習(xí)集成。TWB 使用了一種增量學(xué)習(xí)模型，使用事務(wù)窗口在流事務(wù)數(shù)據(jù)上創(chuàng)建包，處理逐漸的概念漂移；采用貝葉斯基礎(chǔ)學(xué)習(xí)器處理噪聲和邊界數(shù)據(jù)。HIDC（Handling Imbalanced Data with Concept drift）［23］利用差異因子估計多數(shù)類和少數(shù)類的分類精度之間的差異，對過采樣和欠采樣過程進(jìn)行動態(tài)決策，解決了類分布不平衡的問題。通過對候選分類器的效率進(jìn)行評估，從而替換集合分類器中最差的分類器成員，以此解決概念漂移問題。

梁斌等［24］結(jié)合重采樣和自適應(yīng)滑動窗口技術(shù)，提出了一種基于G 均值加權(quán)的不平衡數(shù)據(jù)流在線分類方法OGUEIL（Online G-mean Update Ensemble for Imbalance Learning），根據(jù)當(dāng)前數(shù)據(jù)分布及時調(diào)整每個成員分類器的權(quán)重，解決不平衡數(shù)據(jù)流中的概念漂移問題。Sun 等［25］提出的TSCS（Two-Stage Cost-Sensitive）是一種兩階段代價敏感的數(shù)據(jù)流分類框架。在特征選擇階段，利用成本敏感主成分分析進(jìn)行特征選擇，提高算法的泛化能力，從而適應(yīng)各種概念漂移；在分類階段，建立代價敏感加權(quán)模型，將代價信息引入學(xué)習(xí)框架。TSCS 框架如圖3所示。

圖3 TSCS框架Fig.3 TSCS framework

CSDS（Cost-Sensitive based Data Stream）［26］同樣是基于代價敏感的算法。該算法在數(shù)據(jù)預(yù)處理過程中引入了成本信息，以解決數(shù)據(jù)級的類不平衡問題；在分類過程中，設(shè)計了一種對成本敏感的加權(quán)模式，以提高集成的整體性能。

2 概念演化的概念漂移數(shù)據(jù)流分類

在數(shù)據(jù)流的分類過程中，隨著時間的推移出現(xiàn)了離群點和新穎類，這種情況被稱為概念演化。新穎類的出現(xiàn)使原有的分類器分類效果降低，因此在數(shù)據(jù)流中對新穎類的檢測并與原有已知類進(jìn)行區(qū)分非常有必要。本章針對數(shù)據(jù)流受概念漂移影響的情況，從基于聚類和基于模型兩種傳統(tǒng)高效方法的角度對新穎類檢測的分類算法進(jìn)行介紹。圖4 表示初始數(shù)據(jù)分布發(fā)生演變，最終出現(xiàn)了概念漂移、噪聲和新穎類的情況。

圖4 初始數(shù)據(jù)分布演變Fig.4 Evolution of initial data distribution

2.1 基于聚類的學(xué)習(xí)算法

基于聚類的學(xué)習(xí)算法是一種新穎類別識別方法?；诰垲愃惴ǖ闹饕枷胧峭ㄟ^應(yīng)用一些聚類算法表示正?；蛞阎母拍睿悾?，為學(xué)習(xí)模型創(chuàng)建決策邊界以區(qū)分正常概念和異常值（可能是新的類實例）。

Spinosa 等［27］提出一種基于k-means 聚類方法的在線新穎性和漂移檢測算法（OnLIne Novelty and Drift Detection Algorithm，OLINDDA），首次基于單一學(xué)習(xí)策略解決了數(shù)據(jù)流上的概念漂移和新穎類別探測問題。De Faria 等［28］提出了MINAS（MultIclass learning algorithm for Novelty detection in dAta Streams）技術(shù)，用于對多個類別進(jìn)行分類。Masud 等［29］提出了數(shù)據(jù)流分類框架MineClass（Mining novel Classes），該框架基于集成分類技術(shù)，并用k-means 算法作為探測新穎類別的聚類算法，解決了數(shù)據(jù)流中包含多個已知類別的新穎類別探測問題。Masud 等［30］針對概念演變問題，提出了MCM（stands for MultiClass Miner）集成分類框架，利用離散基尼系數(shù)篩選過濾點。其中每個分類器配備了一個新的類檢測器，以解決概念漂移和概念演化問題。

采用分類誤差率檢測重復(fù)出現(xiàn)的概念漂移是常用的方法。Zheng 等［31］采用了基于Jensen-Shannon 散度的分類器置信度變化檢測技術(shù)，提出了一個帶有重復(fù)概念漂移的半監(jiān)督框架和一種新的類檢測方法ESCR（sEmi-Supervised framework with recurring concept drift and novel Class detection），利用遞歸函數(shù)和動態(tài)規(guī)劃策略，有選擇地執(zhí)行漂移檢測模塊；同時，通過監(jiān)測有強內(nèi)聚性的離群值，將概念演化考慮在內(nèi)。

根據(jù)動態(tài)學(xué)習(xí)微觀數(shù)據(jù)流的變化研究概念漂移和演化是非常高效的一種方法。Din 等［32］基于此提出了新的數(shù)據(jù)流分類方法EMC（Evolving Micro-Clusters）。EMC 動態(tài)地維護了一組在線微簇，通過演化微簇探索數(shù)據(jù)流分類中的概念漂移和演化，并且在線微簇對概念漂移和演化進(jìn)行動態(tài)建模?；谘苌莼奈⒋?，從局部密度的角度直觀地檢測概念演化（即新的類識別）。由于微簇建模的不斷發(fā)展，EMC分別提供了更好的概念漂移適應(yīng)和新的類檢測。

Mustafa 等［33］提出了一種結(jié)合深度學(xué)習(xí)、異常值檢測和基于集成的分類技術(shù)的新類檢測方法NovelDetectorDAE（Novel class Detector with Denoising AutoEncoder）。該方法將特征學(xué)習(xí)、去噪自編碼與新類檢測相結(jié)合，通過一個新的類檢測器豐富集成中的每個分類器，如果所有的分類器都發(fā)現(xiàn)了一個新類，那么就聲明一個新類的發(fā)現(xiàn)，并且潛在的新類實例被分離并分類為新類的成員。該方法使用一種非參數(shù)多維變化點檢測方法檢測概念漂移（數(shù)據(jù)特征值隨時間的變化），并且使用無監(jiān)督學(xué)習(xí)方法豐富傳統(tǒng)的分類模型。

Haque 等［34］提出了 一個半 監(jiān)督框 架SAND（Semisupervised Adaptive Novel class Detection），該框架使用變化檢測技術(shù)檢測概念漂移和塊邊界，通過檢測具有強內(nèi)聚性的離群值解決概念演化問題。為解決SAND 時間開銷大的問題，基于SAND 利用動態(tài)規(guī)劃有選擇地執(zhí)行變更檢測模塊。Haque 等［35］又提出了一種半監(jiān)督分類框架ECHO（Efficient Concept drift and concept evolution Handling Over stream data），通過發(fā)現(xiàn)分類器置信度的任何顯著變化檢測概念漂移和動態(tài)確定塊邊界；此外，還使用置信度分?jǐn)?shù)智能地從最新的塊中選擇有限數(shù)量的數(shù)據(jù)實例進(jìn)行標(biāo)記，然后使用這些數(shù)據(jù)實例更新分類器。

為了緩解概念漂移和概念演化對新類檢測和分類的影響，Li 等［36］提出了基于馬氏距離內(nèi)聚性和分離指數(shù)的新類檢測分類算法（Classification and Novel Class detection algorithm Based on Mahalanobis distance，C&NCBM）。該算法將數(shù)據(jù)流劃分為大小相同的數(shù)據(jù)塊，對數(shù)據(jù)塊中的實例進(jìn)行分類，確定是否為異常值，對異常值集合進(jìn)行聚類，從而確定新類，通過隨時維護當(dāng)前最新概念的分類模型解決概念漂移問題。基于馬氏距離的方法更注重實例之間的相似性，能敏感地檢測離群點之間的微小變化，對于判斷新穎類更具優(yōu)勢。

AnyNovel（An application for activity recognition，detection of Novel concepts in evolving data streams）［37］是一種基于類（如圖5 所示）的集成方法，將訓(xùn)練數(shù)據(jù)分成不同的類，然后為每個類創(chuàng)建集群，在每個集群周圍創(chuàng)建一個彈性間隙，以區(qū)分一個全新的概念和一個現(xiàn)有概念的擴展或漂移。AnyNovel應(yīng)用持續(xù)學(xué)習(xí)方法監(jiān)控流中的進(jìn)化，從而檢測正常和異常的概念的出現(xiàn)和消失；通過合并檢測到的新概念或刪除過時的概念動態(tài)調(diào)整學(xué)習(xí)模型，經(jīng)過調(diào)整的學(xué)習(xí)模型能夠識別新概念重復(fù)出現(xiàn)。

圖5 基于類的集成分類器的訓(xùn)練和更新過程Fig.5 Training and updating process of class-based ensemble classifiers

2.2 基于模型的學(xué)習(xí)算法

與基于聚類的技術(shù)不同，基于模型的學(xué)習(xí)算法的目的是找到可以用于分類和檢測新類的模型。

Masud 等［38］通過引入延遲數(shù)據(jù)標(biāo)記和分類決策的時間約束提出了一種數(shù)據(jù)流分類技術(shù)ECSMiner（Enhanced Classifier for data Streams with novel class Miner）。該技術(shù)將一種新的類檢測機制集成到傳統(tǒng)的分類器中，使之能夠在新類實例的真實標(biāo)簽到達(dá)之前自動檢測新類，在分類時考慮了時間限制。Masud 等［39］根據(jù)循環(huán)類這一概念演化的特殊情況，提出了一個解決存在概念漂移的循環(huán)類問題的方法SCANR（Stream Classifier And Novel and Recurring class detector）。該方法用來作為概念漂移數(shù)據(jù)流的多類分類器，檢測新的類，并區(qū)分重復(fù)類和新的類。

基于決策樹模型是檢測新穎類最常用到的方法之一。Farid 等［40］提出基于決策樹分類器的技術(shù)NCDC（Novel Class Detection in Concept-drifting data stream），從概念漂移數(shù)據(jù)流中發(fā)現(xiàn)新穎類并進(jìn)行分類，計算樹中每個葉節(jié)點的數(shù)據(jù)點相對于訓(xùn)練數(shù)據(jù)集中總數(shù)據(jù)點的百分比，從而判斷新類的出現(xiàn)。SENCForest（classification under Streaming Emerging New Class Forest）［41］是一種隨機決策樹集合的方法，它基于無監(jiān)督異常檢測器，在構(gòu)建檢測器后，使用稱為路徑長度的閾值將數(shù)據(jù)空間劃分為正常和異常區(qū)域，根據(jù)實例位置確定新類。AhtNODE（Adaptive hoeffding tree based NOvel class DEtection）［42］使用自適應(yīng)Hoeffding 樹（Adaptive Hoeffding Tree，AHT）分類器檢測概念漂移和數(shù)據(jù)流中存在概念漂移時的新類，用規(guī)劃的方法求解無限長度、概念漂移和概念演化問題。

Gao 等［43］提出了一個半監(jiān)督流分類框架SACCOS（Semisupervised Adaptive ClassifiCation Over data Stream），使用基于相互圖模型的聚類技術(shù)解決概念漂移和概念演化的問題。Bouguelia 等［44］提出的GNG（Growing Neural Gas algorithm）是一種基于圖模型的算法，以實例作為節(jié)點進(jìn)行圖拓?fù)洌呑鳛椴煌?jié)點之間的連接構(gòu)建圖。當(dāng)新數(shù)據(jù)到達(dá)時，通過創(chuàng)建新節(jié)點和節(jié)點之間的連接定期更新此圖。GNG 在靜態(tài)環(huán)境中學(xué)習(xí)數(shù)據(jù)的拓?fù)浣Y(jié)構(gòu)如圖6 所示，GNG 通過遺忘機制以自適應(yīng)的方式消除獨立無關(guān)的神經(jīng)元處理概念漂移數(shù)據(jù)，根據(jù)引入的局部變量公式（3）計算神經(jīng)元相關(guān)性。

其中：Cn是局部變量，每個神經(jīng)元用n表示，x表示實例，t是當(dāng)前的時間步長（即流中的第t個實例），n*和n**表示最近的兩個神經(jīng)元。1（Cond）是條件Cond的0-1 指示器功能。

3 多標(biāo)簽概念漂移數(shù)據(jù)流分類

多標(biāo)簽數(shù)據(jù)流是隨著時間的推移到達(dá)多標(biāo)簽分類器的多標(biāo)簽實例的序列，在多標(biāo)簽數(shù)據(jù)流中數(shù)據(jù)的底層分布可能還會隨著時間而改變，即概念漂移。因為多標(biāo)簽數(shù)據(jù)流中的每個實例含有多個標(biāo)簽，所以處理概念漂移會更加有難度。問題轉(zhuǎn)換方法和算法適應(yīng)方法是處理多標(biāo)簽問題的有效途徑，本章將結(jié)合概念漂移問題的處理對相關(guān)算法進(jìn)行介紹。

3.1 基于問題轉(zhuǎn)換方法

問題轉(zhuǎn)換方法是處理多標(biāo)簽數(shù)據(jù)的經(jīng)典方法，該方法的主要思想就是將多標(biāo)簽的分類問題轉(zhuǎn)化成一個或多個單標(biāo)簽的分類或回歸問題，即將每個標(biāo)簽視為一個獨立的二元問題。

Qu 等［45］提出了一種加權(quán)投票集成算法DCEBR（Dynamic Classifier Ensemble with Binary Relevance-based algorithm），將數(shù)據(jù)流劃分為連續(xù)的數(shù)據(jù)塊，使用二進(jìn)制關(guān)聯(lián)方法將每個數(shù)據(jù)塊轉(zhuǎn)換為一組單標(biāo)簽數(shù)據(jù)塊，對每個單獨數(shù)據(jù)塊構(gòu)建分類器；通過在最新模塊上建立模型取代實例中最老的模型從而處理概念漂移；使用堆疊二進(jìn)制相關(guān)性從每個塊中學(xué)習(xí)，利用類標(biāo)簽之間的依賴信息；通過改進(jìn)的BR（Binary Relevance-based）分類器進(jìn)行動態(tài)分類集成，實現(xiàn)概念漂移的多標(biāo)簽分類。MINAS-BR（MultIlabel learNing Algorithm for data Streams with Binary Relevance transformation）［46］同樣利用二元關(guān)聯(lián)問題變換策略為每個類建立一個決策模型，使用新穎性檢測程序檢測概念演化和概念漂移，以無監(jiān)督的方式更新。MINAS-PS（MINAS-Pruned Sets）［47］應(yīng)用了新的剪枝方法，該算法可以在沒有樣本真實標(biāo)簽和任何外部反饋的情況下更新模型。在訓(xùn)練階段，使用基于PS 的策略對多標(biāo)簽數(shù)據(jù)進(jìn)行轉(zhuǎn)換，然后利用標(biāo)簽集對樣本進(jìn)行分離，利用聚類算法對微簇進(jìn)行聚類，并建立決策模型。在分類階段，使用決策模型分類新的例子或標(biāo)記為未知。為更新決策模型，在未知的例子中應(yīng)用了聚類算法，能夠適應(yīng)不同類型的概念漂移。

Spyromitros-Xioufis 等［48］提出了一種多窗口方法處理多標(biāo)簽數(shù)據(jù)流方法MW（Multiple Windows），MW 為每個標(biāo)簽設(shè)置了基于正面實例和負(fù)面實例雙窗口，從而處理每個標(biāo)簽正負(fù)樣本分布中的概念漂移和偏斜的類分布。另外，該方法使用KNN（KNearest Neighbors）作為基分類器，使用批量增量閾值技術(shù)進(jìn)一步解決類不平衡問題，使用BR 進(jìn)行獨立建模，從而有效地處理標(biāo)簽之間頻率和概念漂移的預(yù)期差異。

Wang 等［49］提出了一種基于集成的主動學(xué)習(xí)框架（Ensemble-based Active Learning Framework，EALF）處理數(shù)據(jù)量巨大、標(biāo)簽成本高以及多標(biāo)簽數(shù)據(jù)流中的概念漂移問題。采用主動學(xué)習(xí)方法降低多標(biāo)簽流上的標(biāo)簽成本，應(yīng)用最大后驗權(quán)模式不斷更新集合模型的權(quán)值和在多標(biāo)簽數(shù)據(jù)流上增加加權(quán)模式處理概念漂移問題。

標(biāo)簽對之間的相關(guān)性以及標(biāo)簽和特征之間的關(guān)系是多標(biāo)簽數(shù)據(jù)流分類中的重要問題。Nguyen 等［50］提出了BBML（Bayesian-Based Method for Learning from multi-label data streams），將更多注意力放在了新樣本上以適應(yīng)概念漂 移 。MLAW（Multi-Label ensemble with Adaptive Window）［51］采用了周期性加權(quán)機制應(yīng)對概念的逐漸漂移，選擇Jensen-Shannon 散度作為度量兩個連續(xù)窗口之間分布的指標(biāo)，通過維護一個分類器池處理循環(huán)概念漂移問題。通過刪除一些不常見的標(biāo)簽組合考慮標(biāo)簽依賴，更高效地處理多標(biāo)簽數(shù)據(jù)，提高分類器的性能。

3.2 基于算法適應(yīng)方法

算法適應(yīng)方法就是通過擴展特定的學(xué)習(xí)算法來直接處理多標(biāo) 簽數(shù)據(jù)。如ML-KNN（Multi-Label lazy learning approach withKNearest Neighbors）［52］適應(yīng)性懶惰學(xué)習(xí)方法就是一個經(jīng)典算法適應(yīng)方法。

分類器必須能夠處理大量的示例，并在任何時候進(jìn)行預(yù)測的同時，使用有限的時間和內(nèi)存適應(yīng)變化。Read 等［53］提出了一種基于多標(biāo)簽剪枝集分類器的Hoeffding 樹分類方法。這種方法繼承了增量決策樹的高性能，以及高效的多標(biāo)簽方法的預(yù)測能力。該方法實時學(xué)習(xí)和預(yù)測，并在每個示例中更新模型——在檢測到漂移時重新啟動模型。

Roseberry 等［54］提出了一種用于漂移數(shù)據(jù)流的多標(biāo)簽分類器 MLSAMkNN（Multi-Label kNN with Self Adjusting Memory），使用自調(diào)整存儲器來處理漂移數(shù)據(jù)流，并將這種存儲結(jié)構(gòu)與簡單的多標(biāo)簽KNN 分類器相結(jié)合，用于處理混合概念漂移的多標(biāo)簽數(shù)據(jù)流。隨后，Roseberry 等［55］又提出MLSAMPkNN（Multi-Label Punitive kNN with Self-Adjusting Memory），在自調(diào)整內(nèi)存中只包含當(dāng)前的概念，懲罰系統(tǒng)會從窗口中刪除錯誤示例，MLSAMPkNN 使用多數(shù)投票KNN，作用于最新數(shù)據(jù)示例的一個小窗口，該窗口根據(jù)數(shù)據(jù)流中的概念漂移進(jìn)行自我調(diào)整。一個健壯有效的算法必須不斷適應(yīng)新的數(shù)據(jù)分布，AESAKNNS（Adaptive Ensemble of Self-Adjusting Nearest Neighbor Subspaces）［56］利用自調(diào)整KNN 作為基分類器，每個基分類器被賦予一個獨特的特征子集和樣本進(jìn)行訓(xùn)練，利用漂移探測器的集合監(jiān)測子空間上的概念漂移，在新的可變大小特征子空間上建立一個背景集合。

4 含噪聲概念漂移數(shù)據(jù)流分類

數(shù)據(jù)污染是一個嚴(yán)重的問題，因為噪聲會嚴(yán)重?fù)p害學(xué)習(xí)的質(zhì)量和速度。在許多源數(shù)據(jù)可能不可靠的應(yīng)用程序中都會遇到這個問題，并且在數(shù)據(jù)傳輸過程中也可能注入錯誤。對于數(shù)據(jù)流，這個問題更具有挑戰(zhàn)性，因為在數(shù)據(jù)流中很難區(qū)分噪聲和概念漂移引起的數(shù)據(jù)。如果一種算法過于急于適應(yīng)概念的變化，它可能就會過擬合噪聲。

袁泉等［57］提出了一種新型的增量式學(xué)習(xí)的數(shù)據(jù)流集成分類算法（Ensemble Classification Algorithm for data streams with Noise and Concept Drifts，ECANCD）。引入噪聲過濾機制過濾噪聲，引入假設(shè)檢驗方法對概念漂移進(jìn)行檢測。Myint 等［58］提出了一種基于自適應(yīng)窗口的精度更新集成方法A-AUE2（AccurAcy Updated Ensemble-2），采用基于KNN 的噪聲濾波方法去除每個自適應(yīng)窗口中的噪聲樣本。

Luo 等［59］提出了基于塊動態(tài)加權(quán)的方法GBDT（Gradient Boosting Decision Tree framework）處理含噪聲的漂移數(shù)據(jù)流。在分類過程中去除不能適應(yīng)當(dāng)前概念分布的弱分類器，創(chuàng)建新的弱分類器以應(yīng)對發(fā)生的概念漂移。將逐塊處理樣本的塊動態(tài)加權(quán)多數(shù)模塊與在線梯度推進(jìn)決策樹框架相結(jié)合，以應(yīng)對含有噪聲的漂移數(shù)據(jù)流，并開發(fā)了一個穩(wěn)健的損失函數(shù)，避免了噪聲樣本的過擬合。SPL（Selective Prototypebased Learning）［60］通過動態(tài)選擇最重要的實例捕捉當(dāng)前的概念。SPL 進(jìn)一步檢查存儲的錯誤分類的實例，從而檢測突然的概念漂移。由于SPL 可以檢測所有錯誤分類的例子，因此可以有效地識別代表新概念的例子，并通過錯誤驅(qū)動的代表性學(xué)習(xí)進(jìn)一步去除噪聲。

Li 等［61］提出了一種基于集成決策樹的概念漂移（Ensemble Decision Trees for Concept-drifting，EDTC）數(shù)據(jù)流增量算法，引入3 種隨機特征選擇變量實現(xiàn)分裂測試，并利用Hoeffding 邊界不等式區(qū)分概念漂移和噪聲數(shù)據(jù)，有效提高了分類器的性能。Krawczyk 等［62］提出了一種新的在線集成動態(tài)輕量級的方法，通過棄權(quán)修改提高在線集成系統(tǒng)對噪聲的魯棒性，為每個實例有效地選擇最不可能受到噪聲分布影響的分類器，這允許利用基礎(chǔ)學(xué)習(xí)器的潛在多樣性，并大幅減小了漂移恢復(fù)期間的誤差。

5 算法分析對比及性能總結(jié)

本章對不平衡和概念演化概念漂移數(shù)據(jù)流的分類方法性能進(jìn)行分析，介紹了所使用的相同數(shù)據(jù)集，并在使用同一數(shù)據(jù)集的情況下對實驗結(jié)果進(jìn)行了詳細(xì)的對比分析。對多標(biāo)簽和含噪聲概念漂移數(shù)據(jù)流的分類方法進(jìn)行了性能總結(jié)。

5.1 不平衡概念漂移數(shù)據(jù)流分類方法對比

從基于塊和基于在線的學(xué)習(xí)方式對不平衡概念漂移數(shù)據(jù)流的處理方法進(jìn)行了介紹。將根據(jù)在相同條件下進(jìn)行實驗的算法進(jìn)行對比，進(jìn)行算法性能小結(jié)。對所使用相同數(shù)據(jù)集進(jìn)行了介紹，表1 是在相同數(shù)據(jù)集下進(jìn)行實驗的算法，表2是對所用算法在所用技術(shù)、數(shù)據(jù)集、對比算法和優(yōu)缺點方面的總結(jié)。

表1 使用相同數(shù)據(jù)集的不平衡分類算法Tab.1 Unbalanced classification algorithms using same dataset

表2 不平衡概念漂移數(shù)據(jù)流分類方法Tab.2 Classification methods for imbalanced concept drift data streams

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

HyperPlane 數(shù)據(jù)集 漂移超平面問題是由Sea 數(shù)據(jù)集引入的，數(shù)據(jù)集的特點是周期延長，類邊界偶爾會出現(xiàn)急劇變化，即突然漂移或概念變化。數(shù)據(jù)集包括2 個類和3 個特征，其中只有2 個是相關(guān)的，第3 個是噪聲。該數(shù)據(jù)集生成器有10 個屬性，通過連續(xù)旋轉(zhuǎn)決策超平面產(chǎn)生漂移。

Sea 數(shù)據(jù)集 該數(shù)據(jù)集是經(jīng)典的突變式概念漂移數(shù)據(jù)集，基本結(jié)構(gòu)是a，b，c，C，其中a、b和c是條件屬性，C是類屬性。a、b和C有關(guān)，a和b兩個特征的總和是否超過了定義的閾值決定了類標(biāo)簽，c可被視為噪聲用于測試算法的魯棒性。概念漂移被設(shè)計成周期性調(diào)整閾值。

Electricity 數(shù)據(jù)集 該數(shù)據(jù)集是真實數(shù)據(jù)集，收集了澳大利亞新南威爾士州電力市場的45 312 個電價數(shù)據(jù)，該數(shù)據(jù)集包含8 個屬性和2 個類別。

5.1.2 算法性能對比小結(jié)

1）HeperPlane數(shù)據(jù)集中算法性能對比小結(jié)。

相較于SERA 和UCB，Learn++.CDS 在ROC（Receiver Operating Characteristic）曲線中平均值高，平均在0.95，Learn++.CDS受到漂移影響最小。在AUC（Area Under Curve）中Learn++.NIE 的值最高。Learn++.CDS 的F-measure 值最高。召回率（Recall）曲線上表現(xiàn)最好的分別是UCB 和Learn++.NIE。UCB在召回率上也表現(xiàn)出較好的性能，但這種好的召回率是以非常差的ROC 為代價的。在比較運行速度時，UCB 是最快的。DUE 的AUC 值隨著塊大小的增加而增加，在不平衡比率為3∶17 時AUC 值達(dá)到最高為0.85；與UCB、CDS、OOB 和UOB 等算法相比，Accuracy、F-measure、G-mean、Recall、AUC 值分別達(dá)到0.92、0.50、0.80、0.75 和0.84，均為第一名。TSCS的G-maen值為0.84、F-measure值為0.22、運行時間為156.41 s（此時NIE 對應(yīng)的值分別為0.89、0.35、51.23），TSCS 優(yōu)于對比算法，并在常用的度量指標(biāo)評估中獲得了較好性能，特別是在類別不平衡環(huán)境下的演化數(shù)據(jù)流。CSDS 的G-mean 值為0.97，運行時間為18.10 s，在時間復(fù)雜度方面略高，但總體性能方面較好，CSDS 在大多數(shù)情況下能夠較好地兼顧G-mean 和運行時間，且比AUE2 等集成方法更能適應(yīng)漂移。OGUEIL 在不同參數(shù)P（基分類器更新周期）下對G-mean 性能進(jìn)行了實驗，在P=500 時G-mean 值最高為0.87。Accuracy 為0.92、Recall 值為0.81，ROC 值分別為0.80、0.61和0.46。

2）Sea數(shù)據(jù)集上算法性能對比小結(jié)。

對于UCB、SERA、CDS、NIE 這4 個算法，在ROC 和F-measure 中CDS 平均表現(xiàn)最好，在AUC 和Recall 中NIE 平均表現(xiàn)最 好。DWSE 的Accuracy、AUC、F-measure、G-mean、Recall 平均值分別為0.90、0.88、0.48、0.80、0.75，整體性能最 好。MOS-ELM 的G-mean 值為0.84（NIE 和ESOS-ELM 的G-mean 值分別為0.82、0.84）。DUE 在與UB、SERA、CDS、OOB、UOB 的對比 實驗中，DUE 的Precision、F-measure、G-mean、Recall、AUC 值均為最高，分別為0.48、0.60、0.85、0.82、0.88。ECISD 的平均G-mean 值為0.82，NIE 為0.84。TSCS 在與NIE 的對比實驗中，TSCS 的G-mean、F-measure、運行時間分別為0.79 s、0.26 s、67.45 s，NIE 分別為0.64、0.02、55.47。CSDS 在實驗 中G-mean 值達(dá)到 了0.88、運行時 間10.60 s 為最短。OGUEIL 在 與OOB、REA 的對比 實驗中，Accuracy、G-mean、Recall 分別平均為0.94、0.89、0.84，OOB分別為0.90、0.86、0.82，REA 分別為0.72、0.82、0.84，相較于實驗中對比算法取得了最佳性能。

3）Electricity數(shù)據(jù)集中算法性能對比小結(jié)。

在NIE、CDS、SERA、UCB的對比實驗中，CDS在ROC達(dá)到了最高值為0.88，NIE 在F-measure 和AUC 中達(dá)到了最高，分別為0.21、0.70，UCB 在Recall 達(dá)到了最高，UCB 在召回率上表現(xiàn)出較好的性能但是以非常差的ROC 為代價的。在NIE、ESOS-ELM 和MOS-ELM 的對比 實驗中，G-mean 值分別 為0.58、0.62、0.63。在DUE與UCB、SERA、CDS的對比實驗中，DUE 的F-measure、G-mean 和AUC 值均為最高，分別為0.54、0.75 和0.88，UCB 在Accuracy 和Precision 取得了最高值分別為0.92 和0.64，CDS 在Recall 取得了最高值0.63。TSCS 與NIE 對比，TCSC 的G-mean 值為0.76、F-measure 值為0.07、運行時間為35.02 s，NIE 分別為0.80、0.10 和25.33。CSDS 在其實驗中，CSDS 的G-mean 值為0.73、運行時間為31.63 s。OGUEIL 與OOB 和REA 的對比實驗中，Accuracy、G-mean 和Recall 值分別為0.91、0.91 和0.91，OOB 的值分別為0.77、0.76和0.71，ROC的值分別為0.73、0.65和0.45。

5.2 概念演化概念漂移數(shù)據(jù)流分類方法的對比

從基于聚類和基于模型的學(xué)習(xí)方法的角度對概念演化概念漂移數(shù)據(jù)流的處理方法進(jìn)行了介紹。為進(jìn)一步探討各種方法的性能，本節(jié)對使用相同數(shù)據(jù)集且實驗環(huán)境相同條件下的算法進(jìn)行了對比分析，對使用相同數(shù)據(jù)集進(jìn)行了介紹，表3 是使用相同數(shù)據(jù)集的算法，表4 對所用算法的詳細(xì)分析匯總。

表3 使用相同數(shù)據(jù)集的概念演化分類算法Tab.3 Conceptual evolution classification algorithms using same dataset

表4 概念演化和多標(biāo)簽概念漂移數(shù)據(jù)流分類方法Tab.4 Classification methods for concept evolution and multi-label concept drift data streams

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

KddCup 包含麻省理工學(xué)院林肯實驗室兩周的局域網(wǎng)流量中提取的TCP連接記錄，每條記錄指向正常連接或攻擊。有22 種類型的攻擊，在該數(shù)據(jù)集里不同的類頻繁出現(xiàn)和消失。

Pamap UCI 數(shù)據(jù)集。在這組數(shù)據(jù)中，有9 個人配備了傳感器，當(dāng)他們執(zhí)行活動時，這些傳感器收集了52 個流數(shù)據(jù)。

Forest Cover 植被覆蓋類型數(shù)據(jù)集，所有觀測均為30 m×30 m 森林區(qū)域采樣。樣本總數(shù)581 012，每個樣本有54個特征，且有7 種類型。

5.2.2 算法性能對比小結(jié)

1）KddCup 數(shù)據(jù)集上算法對比分析。

MINAS 比OLINDDA 具有更高的新穎類識別率，且獲得更低的時間消耗。對比W-OP（WCE-OLINDDA PARALLEL）和W-OS（WCE-OLINDDA SINGLE），MineClass 以決策樹為基分類器獲得了最低的誤分類（ERR）值為1.7，而W-OP 和W-OS 分別為11.6 和8.7，在KddCup 數(shù)據(jù)集上運行速度比W-OP 快2 095 倍，比W-OS 快246 倍。ECSMiner 以決策樹為基分類器的最低ERR 值為1.0，在運行速度上ECSMiner 比W-OP快26.9倍。EMC與ECSMiner、SENCForest、MINAS相比獲得了最低的ERR 值為0.53，SENCForest 整體錯誤率最高。C&NCBM 在整個數(shù)據(jù)流分類過程中與MineClass 和KNN 兩種算法對比，C&NCBM 的準(zhǔn)確性非常穩(wěn)定，顯著高于其他兩種，C&NCBM 算法的運行時間明顯長于其他兩種算法，C&NCBM比MineClass 具有更高的準(zhǔn)確性，但它也需要更多的評估時間。SCANR 與OLINDDA-WCE、ECSMiner 相比獲得最低的ERR 值為0.107，此時OLINDDA-WCE、ECSMiner 的ERR 值分別為0.307 和0.130。NCDC 與傳統(tǒng)的決策樹分類器和KNN分類器進(jìn)行對比，在ERR值方面分別下降了1.3和2.3。在新的類檢測方面，SENCForest 與表3 所提對比算法相比產(chǎn)生了最高的F-measure，Accuracy 方面SENCForest 性能最高，SENCForest 作為分類器具有較強競爭優(yōu)勢。AhtNODE 與W-OP 和W-OS 進(jìn)行了錯誤率的對比分析，AhtNODE 的ERR、F_new（已存在類實例最終確定為新類的百分比）、M_new（錯誤分類為現(xiàn)有類的新類實例的百分比）值分別為7.2、11 和5.3，此時W-OP 的值分別為11.6、26.7 和7.5，W-OS 的值分別為8.7、99.4 和0。由此可見，AhtNODE 的整體性能最好。SACCOS擁有較高的檢測精度，但也有較高的開銷。

2）Forest Cover數(shù)據(jù)集上算法對比分析。

相較于W-OP 和W-OS，MineClass 的ERR 值均為最低為5.4，W-OP 和W-OS分別為19.2和8.9。在ECSMiner與W-OP和W-OS 對比中，ECSMiner 的ERR 值最低為3.6，W-OP 和W-OS 分別為7.9 和8.5，此時W-OS 有最低的F_new 值。MCM 與MineClass 相比，ERR、M_new、F_new 和AUC 值分別為3.1、4.0、0.68 和0.99，MineClass 的值分別為3.6、8.4、1.30和0.97，MCM 具有更好的性能，此時MCM 具有更少的時間消耗為0.9 s。ESCR 與SAND 和ECSMiner 相比，置信閾值τ 為0.9時ERR 最低為0.04。ECSR還具有檢測重復(fù)漂移的能力，在誤報的性能方面表現(xiàn)最好。DAE 與ECSMiner 和ECHO 相比，ERR 值為最低為0.02，ECSMiner 和ECHO 分別為0.05 和0.03。SAND 在分類結(jié)果和使用有限數(shù)量的標(biāo)記數(shù)據(jù)進(jìn)行分類結(jié)果中，都展示出了比ECSMiner 更低的錯誤率。在新類探測的結(jié)果中ECSMiner具有比SAND更低的M_new值。

3）Pamap數(shù)據(jù)集中算法對比分析。

EMC 與其他8 種數(shù)據(jù)流分類算法（AWE、OAUE、DWM、LNSE、AHT、OBA、NBDM、HOT）在18個數(shù)據(jù)集上的誤分類錯誤性能對比，除在Sea和HyperPlane數(shù)據(jù)集上均展示了最好的效果，與ECSMiner、SENForest、SENCForest和MINAS算法對比具有最低的ERR值。DAE與ECSMiner和ECHO相比具有最低的ERR 值 為2.46，此 時，ECSMiner 和ECHO 分別為17.38 和2.37。SAND 在Pamap 數(shù)據(jù)集 中，雖 然M_new 值不如ECSMiner，但通過使用有限數(shù)量的標(biāo)記數(shù)據(jù)和有選擇地執(zhí)行變更檢測，SAND還可以在不犧牲準(zhǔn)確性的情況下節(jié)省時間和資源。ECHO與ECSMiner、AHT和OBA相比，在使用有限數(shù)量的標(biāo)記數(shù)據(jù)進(jìn)行分類性能的性能比較和整體分類效果中都獲得了最好的效果。對于Pamap 數(shù)據(jù)集，ECHO-D 的所有M_new、F_new和F-Score（α=2）性能都優(yōu)于ECSMiner。在SACCOS與其對比算法實驗中，SACCOS具有最好的分類性能，要求較少的標(biāo)簽同時解決了概念漂移檢測和新出現(xiàn)的類檢測問題。

5.3 多標(biāo)簽概念漂移數(shù)據(jù)流分類方法總結(jié)

本節(jié)對基于問題轉(zhuǎn)換和算法擴展的算法進(jìn)行分析總結(jié)，其中問題轉(zhuǎn)換方法就是將多標(biāo)簽分類問題轉(zhuǎn)換成單一標(biāo)簽問題進(jìn)行處理；算法適應(yīng)方法是擴展特定的學(xué)習(xí)算法直接處理多標(biāo)簽數(shù)據(jù)。表4是對相應(yīng)算法特點的總結(jié)。DCEBR算法在大數(shù)據(jù)塊的情況下漢明損失更小，且具有很強的利用不同標(biāo)簽之間相關(guān)性的能力。EALF更好地解決了概念漂移問題、過擬合問題、標(biāo)簽不平衡問題和標(biāo)簽成本問題，獨立更新每個類的集合可以為每個標(biāo)簽保留最佳分類器。MW 提出的閾值技術(shù)能夠有效地調(diào)整決策閾值，在AUC 值上優(yōu)于對比方法；但這種方法與主動學(xué)習(xí)方法不兼容。MLAW 在預(yù)測性能的大多數(shù)度量下優(yōu)于所有其他對比算法，該算法能夠根據(jù)概念的變化及時檢測到概念漂移，并及時構(gòu)建分類器，實現(xiàn)對這類概念漂移的快速處理。MINAS-BR 在所有數(shù)據(jù)集上都優(yōu)于下界方法，并且在某些情況下優(yōu)于上界方法，在更新時不需要示例的真正標(biāo)簽，也不需要任何外部反饋。MINAS-PS離線階段的剪枝過程有時會丟失重要的信息，在F-measure、Accuracy 方面優(yōu)于基準(zhǔn)方法。BBML 通過以樣本的時間為中心的衰減機制處理概念漂移，對于處理缺失值也有良好的效果，在分類精確度等性能上優(yōu)于基準(zhǔn)方法，但運行時間開銷較大，時間復(fù)雜度在相當(dāng)大程度上依賴于數(shù)據(jù)的維度。

MLSAMkNN 在測試的23 個數(shù)據(jù)集上獲得了最佳的子集精度和F-measure 值，并在準(zhǔn)確度和召回率方面同樣表現(xiàn)良好。MLSAMPkNN 是適用于各種學(xué)習(xí)場景（包括概念漂移、不平衡數(shù)據(jù)和噪聲）的通用分類器，它是一種易于使用的現(xiàn)成分類器，因為不需要任何繁瑣的模型選擇和參數(shù)調(diào)優(yōu)。AESAKNNS在12項實驗指標(biāo)中，有9項達(dá)到最佳性能，對概念漂移具有高度適應(yīng)性，并克服了其他各種多標(biāo)簽數(shù)據(jù)困難，是一個全面的分類器。

5.4 含噪聲概念漂移數(shù)據(jù)流分類方法總結(jié)

本節(jié)對處理含噪聲的概念漂移數(shù)據(jù)流分類方法進(jìn)行了性能分析匯總，表5 是對相關(guān)算法的匯總。

表5 含噪聲概念漂移數(shù)據(jù)流分類方法Tab.5 Classification methods for data streams with noisy concept drift

ECANCD 與其對比算法相比，以C4.5 作為基分類器在真實動態(tài)數(shù)據(jù)中的分類時間、分類精度、Kappa 統(tǒng)計量、均方根誤差和相對均方根誤差均比支持向量機分類器優(yōu)越。A-AUE2 在每個窗口上使用了噪聲濾波方法（KNN）和自適應(yīng)加窗方法（BSS）。在F1（即F-Measure）、Precision、Recall、MCC（Matthews Correlation Coefficient）和AUC 這5 個預(yù)測指標(biāo)上進(jìn)行了驗證，在與8 種最先進(jìn)的概念漂移檢測和處理方法對比中，A-AUE2 在兩種基礎(chǔ)學(xué)習(xí)器中都表現(xiàn)出色。GBDT 能夠在有噪聲的數(shù)據(jù)流中準(zhǔn)確地識別出真實模式，在6 種在線集成學(xué)習(xí)方法的15 個實驗中，GBDT 表現(xiàn)最好，在15 個實驗中有12 個實驗排名第一。結(jié)果表明，與其他在線集成學(xué)習(xí)方法相比，GBDT 對噪聲的敏感性較低，在訓(xùn)練集包含噪聲時具有較好的魯棒性。SPL 使用自適應(yīng)窗口來關(guān)注最近的數(shù)據(jù)，因此比傳統(tǒng)的單模型算法要慢。與其他基于實例的算法相比，SPL 顯示了它的優(yōu)勢，它只需要動態(tài)地維護一小組實例。DyAbst 能夠提高在線集成對數(shù)據(jù)流中噪聲的魯棒性，引入了一個動態(tài)的、自適應(yīng)的閾值，它能夠通過監(jiān)控集合的輸出來適應(yīng)數(shù)據(jù)流中的變化，有效地預(yù)測漂移。

6 下一步工作

雖然目前已經(jīng)提出了許多算法處理相應(yīng)的概念漂移復(fù)雜數(shù)據(jù)流，但現(xiàn)有的算法仍存在一些問題，限制了它們在許多實際應(yīng)用中的適用性。許多問題仍然是有待解決的研究問題，下面將探討現(xiàn)有困難和挑戰(zhàn)，并提出下一步研究方向。

1）復(fù)雜數(shù)據(jù)流中的概念漂移檢測。

概念漂移的檢測在復(fù)雜類型數(shù)據(jù)流中是一個急切需要解決的難題。在數(shù)據(jù)流中，分類器性能除受概念漂移問題影響外，還受數(shù)據(jù)復(fù)雜性的影響，如類不平衡、多標(biāo)簽、噪聲等，這些問題導(dǎo)致現(xiàn)有漂移檢測器在檢測精度和時空復(fù)雜度上面臨巨大的挑戰(zhàn)。我們下一步擬提出一個基于半監(jiān)督的多尺度窗口漂移檢測器，大尺度窗口用來進(jìn)行數(shù)據(jù)與標(biāo)記樣本的對比檢測，小窗口用于檢測概念漂移。將該檢測器應(yīng)用在概念漂移復(fù)雜數(shù)據(jù)流中，旨在更精確檢測概念漂移的同時能識別漂移類型。

2）含概念漂移的多類不平衡數(shù)據(jù)流分類。

截至目前，相當(dāng)多的研究僅處理二類不平衡數(shù)據(jù)流的情況，但二類問題的解決方案不能直接適用于多類問題。在多類不平衡數(shù)據(jù)流的情況下，處理概念漂移問題就不得不考慮多個類概念的變化。分類器精確度受多類和概念漂移的影響較大，我們將提出新的動態(tài)集成方法檢測多類不平衡數(shù)據(jù)流中多種類型的概念漂移，并加以處理，以此提高分類精確度。

3）多標(biāo)簽中類不平衡數(shù)據(jù)流分類。

在多標(biāo)簽數(shù)據(jù)流分類中，類不平衡問題仍然是一個具有挑戰(zhàn)性和重要性的問題。有些標(biāo)簽有更多的少數(shù)實例，而有些標(biāo)簽具有更多的多數(shù)實例?，F(xiàn)有的研究只考慮了不平衡類中最簡單的條件，并假設(shè)不平衡比例隨著時間的推移是靜態(tài)的；但在現(xiàn)實世界中并非如此，研究多標(biāo)簽中少數(shù)類的變化有助于提高分類性能。未來將采用半監(jiān)督增量的方法結(jié)合采樣方法來解決這一問題。

4）在特征演化數(shù)據(jù)流中的新類探測。

目前大多數(shù)的算法都使用固定的特征集，只有少數(shù)的算法考慮了特征演化的問題。然而，現(xiàn)實世界中，數(shù)據(jù)流是動態(tài)的，因此數(shù)據(jù)的特征也會隨著時間進(jìn)行演化，新的特征可能會增強，舊的特征可能會消失，特征演化可能會導(dǎo)致不相關(guān)的分類器預(yù)測未來的實例時性能下降。在多個特征的空間中，一些關(guān)鍵特征可能丟失，同樣會導(dǎo)致分類器性能下降。因此，如何在特征演化的數(shù)據(jù)流中檢測出新出現(xiàn)的模式并加以處理也是一個重要的問題。

7 結(jié)語

本文首次從不平衡概念漂移數(shù)據(jù)流、概念演化概念漂移數(shù)據(jù)流、多標(biāo)簽概念漂移數(shù)據(jù)流和含噪聲漂移數(shù)據(jù)流這4 個方面對概念漂移復(fù)雜數(shù)據(jù)流分類方法進(jìn)行了介紹。從不同學(xué)習(xí)方式的角度對算法進(jìn)行了分析，對不平衡概念漂移數(shù)據(jù)流和概念演化概念漂移數(shù)據(jù)流的分類方法進(jìn)行了詳細(xì)的實驗結(jié)果對比，對多標(biāo)簽概念漂移數(shù)據(jù)流和含噪聲概念漂移數(shù)據(jù)流的分類方法進(jìn)行了性能總結(jié)，并對所用方法的技術(shù)、數(shù)據(jù)集、對比算法，以及優(yōu)缺點方面進(jìn)行了列表匯總。

最后，針對目前現(xiàn)實世界中復(fù)雜數(shù)據(jù)流所面臨的挑戰(zhàn)和問題，對復(fù)雜數(shù)據(jù)流的漂移檢測、多類不平衡概念漂移數(shù)據(jù)流分類、多標(biāo)簽數(shù)據(jù)流中類不平衡，以及特征演化數(shù)據(jù)流中的新類探測等問題進(jìn)行了總結(jié)，并且提出下一步的研究方向。