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

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

0 引言

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

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

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

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

本文的主要工作有：

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

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

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

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

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

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

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

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

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

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

為從批量可用的新數(shù)據(jù)中學(xué)習(xí)，且不必訪問(wèn)以前批量中的數(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)召回或幾何平均單個(gè)類的表現(xiàn)，對(duì)概念漂移進(jìn)行有效的跟蹤識(shí)別，提高少數(shù)類上的分類性能，避免多數(shù)類分類性能下降。

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

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

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

ECISD（Ensemble Classifier for mining Imbalanced Streaming Data）［19］利用過(guò)采樣技術(shù)平衡各類樣本，并周期更新分類器權(quán)重以應(yīng)對(duì)概念漂移在分類器的淘汰過(guò)程中考慮了各個(gè)分類器對(duì)集成分類的影響，從而達(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)滑動(dòng)窗口技術(shù)對(duì)應(yīng)用流數(shù)據(jù)中的概念漂移進(jìn)行識(shí)別，通過(guò)應(yīng)用堆疊自動(dòng)編碼器進(jìn)行概念漂移分類以增強(qiáng)估計(jì)措施。最后，利用ADODNN 算法進(jìn)行分類。圖2 展示了ADODNN 算法框架。

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

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

在線學(xué)習(xí)方法可以應(yīng)用于數(shù)據(jù)以塊形式到達(dá)的問(wèn)題，在線學(xué)習(xí)中，實(shí)例不斷從數(shù)據(jù)流中獲得并且只能被處理一次，不需要再次存儲(chǔ)和再處理。在數(shù)據(jù)連續(xù)到達(dá)的情況下，在線算法比典型的批處理算法運(yùn)行更快、精度更高，因此在線技術(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］利用差異因子估計(jì)多數(shù)類和少數(shù)類的分類精度之間的差異，對(duì)過(guò)采樣和欠采樣過(guò)程進(jìn)行動(dòng)態(tài)決策，解決了類分布不平衡的問(wèn)題。通過(guò)對(duì)候選分類器的效率進(jìn)行評(píng)估，從而替換集合分類器中最差的分類器成員，以此解決概念漂移問(wèn)題。

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

圖3 TSCS框架Fig.3 TSCS framework

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

標(biāo)簽對(duì)之間的相關(guān)性以及標(biāo)簽和特征之間的關(guān)系是多標(biāo)簽數(shù)據(jù)流分類中的重要問(wèn)題。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)機(jī)制應(yīng)對(duì)概念的逐漸漂移，選擇Jensen-Shannon 散度作為度量?jī)蓚€(gè)連續(xù)窗口之間分布的指標(biāo)，通過(guò)維護(hù)一個(gè)分類器池處理循環(huán)概念漂移問(wèn)題。通過(guò)刪除一些不常見(jiàn)的標(biāo)簽組合考慮標(biāo)簽依賴，更高效地處理多標(biāo)簽數(shù)據(jù)，提高分類器的性能。

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

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

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

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

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

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

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

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

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

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

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

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

從基于塊和基于在線的學(xué)習(xí)方式對(duì)不平衡概念漂移數(shù)據(jù)流的處理方法進(jìn)行了介紹。將根據(jù)在相同條件下進(jìn)行實(shí)驗(yàn)的算法進(jìn)行對(duì)比，進(jìn)行算法性能小結(jié)。對(duì)所使用相同數(shù)據(jù)集進(jìn)行了介紹，表1 是在相同數(shù)據(jù)集下進(jìn)行實(shí)驗(yàn)的算法，表2是對(duì)所用算法在所用技術(shù)、數(shù)據(jù)集、對(duì)比算法和優(yōu)缺點(diǎn)方面的總結(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ù)集 漂移超平面問(wèn)題是由Sea 數(shù)據(jù)集引入的，數(shù)據(jù)集的特點(diǎn)是周期延長(zhǎng)，類邊界偶爾會(huì)出現(xiàn)急劇變化，即突然漂移或概念變化。數(shù)據(jù)集包括2 個(gè)類和3 個(gè)特征，其中只有2 個(gè)是相關(guān)的，第3 個(gè)是噪聲。該數(shù)據(jù)集生成器有10 個(gè)屬性，通過(guò)連續(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兩個(gè)特征的總和是否超過(guò)了定義的閾值決定了類標(biāo)簽，c可被視為噪聲用于測(cè)試算法的魯棒性。概念漂移被設(shè)計(jì)成周期性調(diào)整閾值。

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

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

1）HeperPlane數(shù)據(jù)集中算法性能對(duì)比小結(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 為代價(jià)的。在比較運(yùn)行速度時(shí)，UCB 是最快的。DUE 的AUC 值隨著塊大小的增加而增加，在不平衡比率為3∶17 時(shí)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、運(yùn)行時(shí)間為156.41 s（此時(shí)NIE 對(duì)應(yīng)的值分別為0.89、0.35、51.23），TSCS 優(yōu)于對(duì)比算法，并在常用的度量指標(biāo)評(píng)估中獲得了較好性能，特別是在類別不平衡環(huán)境下的演化數(shù)據(jù)流。CSDS 的G-mean 值為0.97，運(yùn)行時(shí)間為18.10 s，在時(shí)間復(fù)雜度方面略高，但總體性能方面較好，CSDS 在大多數(shù)情況下能夠較好地兼顧G-mean 和運(yùn)行時(shí)間，且比AUE2 等集成方法更能適應(yīng)漂移。OGUEIL 在不同參數(shù)P（基分類器更新周期）下對(duì)G-mean 性能進(jìn)行了實(shí)驗(yàn)，在P=500 時(shí)G-mean 值最高為0.87。Accuracy 為0.92、Recall 值為0.81，ROC 值分別為0.80、0.61和0.46。

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

對(duì)于UCB、SERA、CDS、NIE 這4 個(gè)算法，在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 的對(duì)比 實(shí)驗(yàn)中，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 的對(duì)比實(shí)驗(yàn)中，TSCS 的G-mean、F-measure、運(yùn)行時(shí)間分別為0.79 s、0.26 s、67.45 s，NIE 分別為0.64、0.02、55.47。CSDS 在實(shí)驗(yàn) 中G-mean 值達(dá)到 了0.88、運(yùn)行時(shí) 間10.60 s 為最短。OGUEIL 在 與OOB、REA 的對(duì)比 實(shí)驗(yàn)中，Accuracy、G-mean、Recall 分別平均為0.94、0.89、0.84，OOB分別為0.90、0.86、0.82，REA 分別為0.72、0.82、0.84，相較于實(shí)驗(yàn)中對(duì)比算法取得了最佳性能。

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

在NIE、CDS、SERA、UCB的對(duì)比實(shí)驗(yàn)中，CDS在ROC達(dá)到了最高值為0.88，NIE 在F-measure 和AUC 中達(dá)到了最高，分別為0.21、0.70，UCB 在Recall 達(dá)到了最高，UCB 在召回率上表現(xiàn)出較好的性能但是以非常差的ROC 為代價(jià)的。在NIE、ESOS-ELM 和MOS-ELM 的對(duì)比 實(shí)驗(yàn)中，G-mean 值分別 為0.58、0.62、0.63。在DUE與UCB、SERA、CDS的對(duì)比實(shí)驗(yàn)中，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 對(duì)比，TCSC 的G-mean 值為0.76、F-measure 值為0.07、運(yùn)行時(shí)間為35.02 s，NIE 分別為0.80、0.10 和25.33。CSDS 在其實(shí)驗(yàn)中，CSDS 的G-mean 值為0.73、運(yùn)行時(shí)間為31.63 s。OGUEIL 與OOB 和REA 的對(duì)比實(shí)驗(yàn)中，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ù)流分類方法的對(duì)比

從基于聚類和基于模型的學(xué)習(xí)方法的角度對(duì)概念演化概念漂移數(shù)據(jù)流的處理方法進(jìn)行了介紹。為進(jìn)一步探討各種方法的性能，本節(jié)對(duì)使用相同數(shù)據(jù)集且實(shí)驗(yàn)環(huán)境相同條件下的算法進(jìn)行了對(duì)比分析，對(duì)使用相同數(shù)據(jù)集進(jìn)行了介紹，表3 是使用相同數(shù)據(jù)集的算法，表4 對(duì)所用算法的詳細(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é)院林肯實(shí)驗(yàn)室兩周的局域網(wǎng)流量中提取的TCP連接記錄，每條記錄指向正常連接或攻擊。有22 種類型的攻擊，在該數(shù)據(jù)集里不同的類頻繁出現(xiàn)和消失。

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

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

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

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

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

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

相較于W-OP 和W-OS，MineClass 的ERR 值均為最低為5.4，W-OP 和W-OS分別為19.2和8.9。在ECSMiner與W-OP和W-OS 對(duì)比中，ECSMiner 的ERR 值最低為3.6，W-OP 和W-OS 分別為7.9 和8.5，此時(shí)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 具有更好的性能，此時(shí)MCM 具有更少的時(shí)間消耗為0.9 s。ESCR 與SAND 和ECSMiner 相比，置信閾值τ 為0.9時(shí)ERR 最低為0.04。ECSR還具有檢測(cè)重復(fù)漂移的能力，在誤報(bào)的性能方面表現(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 更低的錯(cuò)誤率。在新類探測(cè)的結(jié)果中ECSMiner具有比SAND更低的M_new值。

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

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

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

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

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

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

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

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

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

6 下一步工作

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

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

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

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

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

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

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

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

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

7 結(jié)語(yǔ)

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

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