張喜龍，韓 萌，陳志強(qiáng)，武紅鑫，李慕航

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

傳統(tǒng)的機(jī)器學(xué)習(xí)算法主要處理靜態(tài)數(shù)據(jù)，但現(xiàn)有的數(shù)據(jù)多數(shù)以數(shù)據(jù)流的形式出現(xiàn)，這改變了人們存儲、通信和處理數(shù)據(jù)的方式。在許多新的應(yīng)用中，人們面臨著不斷變化的數(shù)據(jù)流。例如Web點(diǎn)擊流分析、網(wǎng)絡(luò)日志、交通流量監(jiān)控與管理、電信數(shù)據(jù)管理等[1]。隨著研究人員對數(shù)據(jù)流的研究，展開了對復(fù)雜數(shù)據(jù)流類型的鉆研。但是，在處理不平衡、高維、有噪聲數(shù)據(jù)時還是無法獲得令人滿意的性能。在這種背景下，如何有效地構(gòu)建一個高效的知識發(fā)現(xiàn)和挖掘模型成為數(shù)據(jù)挖掘領(lǐng)域的一個重要課題。

集成學(xué)習(xí)是目前的一個研究熱點(diǎn)內(nèi)容，旨在將數(shù)據(jù)融合、數(shù)據(jù)建模和數(shù)據(jù)挖掘整合到一個統(tǒng)一的框架。經(jīng)典的數(shù)據(jù)流集成分類算法有在線精度更新集成(online accuracy updated ensemble algorithm, OAUE)[2]、杠桿裝袋(leveraging bagging，LevBag)[3]等。其中有處理概念漂移的流集成算法(streaming ensemble algorithm，SEA)[4]、動態(tài)加權(quán)多數(shù)算法(accuracy weighted ensemble，AWE)[5]等;處理不平衡數(shù)據(jù)集的SRE[6]、RE-DI[7]算法等；處理多標(biāo)簽流的分類器鏈集成模型(ensemble of classifier chains，ECC)[8]和處理多實(shí)例數(shù)據(jù)流的OMB(online MIL boosting)[9]算法等。這些都是一些經(jīng)典的復(fù)雜數(shù)據(jù)流集成算法。

之前已有研究人員對數(shù)據(jù)流分類研究的綜述。如：Lemaire等[10]從數(shù)據(jù)流的學(xué)習(xí)方式入手，以單分類器處理數(shù)據(jù)流為主要方法，簡要介紹了常見的數(shù)據(jù)集以及評估方法；Gomes等[11]對數(shù)據(jù)流集成分類進(jìn)行了全面綜述，涉及到分類多樣性以及動態(tài)更新，主要是針對概念漂移數(shù)據(jù)流；Iwashita等[12]從穩(wěn)態(tài)到動態(tài)數(shù)據(jù)流進(jìn)行展開，從分類到回歸進(jìn)行詳細(xì)介紹，還對數(shù)據(jù)流的一些高級問題進(jìn)行了探討。以上數(shù)據(jù)流的綜述，雖然介紹了常見數(shù)據(jù)流的處理方法，但是沒有細(xì)分?jǐn)?shù)據(jù)流的種類，大多數(shù)還是以處理單類型數(shù)據(jù)流為主要研究對象，同時數(shù)據(jù)流的評估技術(shù)、指標(biāo)只是簡要提及，沒有歸納總結(jié)。本文的綜述框架如圖1所示，主要貢獻(xiàn)如下：

圖1 復(fù)雜數(shù)據(jù)流分類框架

1)全面歸納近些年集成學(xué)習(xí)研究穩(wěn)態(tài)、概念漂移、不平衡、多標(biāo)簽、多實(shí)例數(shù)據(jù)流，并對提出的集成算法進(jìn)行對比。

2)首次歸納近些年集成學(xué)習(xí)處理文本、圖、傳感器領(lǐng)域數(shù)據(jù)流的算法研究進(jìn)展。

3)對復(fù)雜數(shù)據(jù)流用到的驗證技術(shù)、評估指標(biāo)進(jìn)行全面總結(jié)。

1 復(fù)雜數(shù)據(jù)流集成分類

訓(xùn)練過程經(jīng)過基分類器的組合，然后使用組合策略(例如經(jīng)典的多數(shù)投票)得出最終的預(yù)測結(jié)果。單分類器在快速到來的數(shù)據(jù)流中無法很好適應(yīng)變化，但是集成結(jié)構(gòu)可以使分類模型更加高效[14]。集成學(xué)習(xí)對不同的復(fù)雜數(shù)據(jù)流會有不同的實(shí)施策略，使用在線學(xué)習(xí)、塊學(xué)習(xí)以及增量學(xué)習(xí)等關(guān)鍵技術(shù)使模型擬合效果更好。本章將在最后總結(jié)集成學(xué)習(xí)處理復(fù)雜數(shù)據(jù)流算法性能的對比，從集成方式以及優(yōu)劣勢等方面進(jìn)行概括。

數(shù)據(jù)流類型中穩(wěn)態(tài)數(shù)據(jù)流最平穩(wěn)，它不需要考慮復(fù)雜情況，逐漸淡出人們的研究熱點(diǎn)。但是一些經(jīng)典的算法值得大家去探討，它是人們早期研究數(shù)據(jù)流的一種探索。在穩(wěn)態(tài)數(shù)據(jù)流中，使用塊的算法相對于在線學(xué)習(xí)研究得不多。早期經(jīng)典的Learn++[15]是一種神經(jīng)網(wǎng)絡(luò)分類器集成算法，在很多實(shí)驗的對比算法中被提及。該算法對到來的數(shù)據(jù)塊構(gòu)建新的神經(jīng)網(wǎng)絡(luò)模型進(jìn)行增量訓(xùn)練，然后采用多數(shù)投票的決策機(jī)制進(jìn)行預(yù)測。研究人員在分析了Learn++優(yōu)缺點(diǎn)的基礎(chǔ)上，提出了異構(gòu)Bagging++算法[16]，它使用Bagging為每個數(shù)據(jù)塊生成一個增量集成算法，該算法利用Bagging從傳入的數(shù)據(jù)塊中構(gòu)建新的模型。

在線學(xué)習(xí)是集成學(xué)習(xí)中常用的技術(shù)，在線學(xué)習(xí)算法對到達(dá)的實(shí)例進(jìn)行一次處理，可以對數(shù)據(jù)流分類做出更快速的反應(yīng)。OzaBag算法[17]要求整個訓(xùn)練集立即可用，它使每個基分類器都用新到達(dá)數(shù)據(jù)的k個副本進(jìn)行更新，其中k服從k～Possion(1)分布，在精度方面與批處理分類的版本相當(dāng)。而OzaBoost集成算法[17]維護(hù)一個固定大小的集成，這些分類器根據(jù)收到的實(shí)例進(jìn)行訓(xùn)練,每個新實(shí)例都按順序更新分類器。如果實(shí)例被前一個分類器誤分類則會更新其權(quán)重，以供后一個分類器更加重視錯誤分類的實(shí)例。另外，Bifet等[3]提出了LevBag算法，該算法將Bagging技術(shù)的簡單性與分類器輸入和輸出中添加更多隨機(jī)化相結(jié)合，通過對輸入實(shí)例的權(quán)值進(jìn)行隨機(jī)化來提高集成的精度。

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

在動態(tài)環(huán)境中處理數(shù)據(jù)流的一個最大挑戰(zhàn)就是概念漂移[18]，當(dāng)被收集的數(shù)據(jù)所涉及的概念經(jīng)過一段時間的穩(wěn)定后發(fā)生變化，概念漂移就會發(fā)生。如今的概念漂移數(shù)據(jù)流主要采用主動和被動2種方式來進(jìn)行處理，圖2展示了概念漂移處理的常規(guī)過程。本節(jié)主要討論基于塊學(xué)習(xí)和基于在線學(xué)習(xí)的集成學(xué)習(xí)方法角度去處理概念漂移數(shù)據(jù)流。

圖2 概念漂移處理過程

1.1.1 基于塊學(xué)習(xí)的集成

基于塊學(xué)習(xí)集成的思想是將到來的數(shù)據(jù)流劃分為數(shù)據(jù)塊去更新基分類器，如果分類器數(shù)目超過設(shè)定的集成大小，則用新構(gòu)建的分類器替換效果差的分類器，之后采用組合策略預(yù)測結(jié)果。動態(tài)替換分類器的思想是適應(yīng)概念漂移常用的辦法。

Wang等[5]提出一種精度加權(quán)集成分類(accuracy weighted ensemble, AWE)算法，它能適應(yīng)潛在的概念漂移，但在漸變漂移方面效果并不佳。為了改進(jìn)算法，Deckert等[19]提出一種新的概念漂移處理算法，即批處理加權(quán)集成分類算法(batch weighted ensemble, BWE)，用于處理帶有突變性和漸變性漂移的數(shù)據(jù)。該算法將數(shù)據(jù)流實(shí)例處理成相同大小的塊，并將漂移檢測器引入集成框架，比AWE算法有著更好的精度。為了更好應(yīng)對各種漂移類型的數(shù)據(jù)流，Brzezinski等[20]提出一個基于塊的流集成分類模型AUE2(accuracy updated ensemble)，旨在對不同類型的概念漂移做出反應(yīng)。該算法的主要新穎之處在于將集成加權(quán)機(jī)制與基分類器的增量訓(xùn)練相結(jié)合，與AWE中使用的線性函數(shù)不同，其加權(quán)函數(shù)采用非線性加權(quán)函數(shù)，計算公式為：

(1)

(2)

(3)

目前一些方法認(rèn)為，在連續(xù)處理數(shù)據(jù)流的同時更新集成的方法是不合適的，會面臨一些問題，例如無限增長的集成大小或在處理概念漂移時刪除其所有的基分類器的情況。Bertini Junior等[21]提出迭代Boosting流集成(iterative boosting streaming ensemble, IBS)算法，它將集成算法Boosting應(yīng)用于數(shù)據(jù)塊，通過添加一定數(shù)量的基分類器來維持集成結(jié)構(gòu)。潘吳斌等[22]提出一種基于信息熵的自適應(yīng)網(wǎng)絡(luò)流概念漂移分類方法，根據(jù)特征屬性的信息熵變化檢測概念漂移，使用增量集成學(xué)習(xí)策略引入新樣本建立的分類器，這是一種新穎的訓(xùn)練分類器方式。

傳統(tǒng)數(shù)據(jù)流挖掘階段中概念漂移的檢測需要標(biāo)記樣本的可用性，在實(shí)際情況中就時間和資源利用率而言，獲取帶標(biāo)簽的樣本成本比較高。Abdualrhman等[23]提出基于集成分類器的確定性概念漂移檢測(DCDD)方法，集成算法選用經(jīng)典的AdaBoost算法，該漂移檢測方法可以檢測概念漂移的存在，但它與分配給樣本的標(biāo)簽無關(guān)。該方法具有較高的漂移檢測率和較小的虛假警告率及漏失率，可以擴(kuò)展檢測概念漂移，然后通過集成分類器進(jìn)行預(yù)測。

1.1.2 基于在線學(xué)習(xí)的集成

在線學(xué)習(xí)集成算法采用一種實(shí)時處理數(shù)據(jù)的思路，它不是以存儲到一定量數(shù)據(jù)的塊方式學(xué)習(xí)。隨著類標(biāo)簽的在線到達(dá)，在線算法可以比在處理數(shù)據(jù)塊的環(huán)境中更快地對概念漂移做出反應(yīng)，是一種按照時間順序?qū)W習(xí)并不斷修正的模型，能更好地擬合數(shù)據(jù)[24]。

分類器或?qū)嵗訖?quán)的思想一直是大家研究的重點(diǎn)內(nèi)容，通過不斷創(chuàng)新加權(quán)方式來適應(yīng)概念漂移是一種常見的被動式方法。OAUE[2]是一種經(jīng)典的算法，該方法將基于塊的集成優(yōu)點(diǎn)和在線集成優(yōu)點(diǎn)相結(jié)合，對存入的每個實(shí)例進(jìn)行訓(xùn)練以及對分類器進(jìn)行加權(quán)，創(chuàng)新之處是提出高效的基分類器加權(quán)函數(shù)。Ancy等[25]提出一種基于自適應(yīng)在線學(xué)習(xí)規(guī)則(stream data mining on the fly using an adaptive online learning rule, SOAR)挖掘方法。SOAR綜合了基于塊和網(wǎng)絡(luò)集成的基本特征，并根據(jù)其分類效果更新每個基分類器的權(quán)重。它使用了自適應(yīng)窗口以處理漸進(jìn)和突然的概念漂移。Feitosa等[26]提出一種處理概念漂移的集成優(yōu)化分類算法(ensemble optimization approach for concept drift，EOCD)。它使用基于優(yōu)化技術(shù)的顯式自適應(yīng)機(jī)制來為檢測到的概念漂移定義最合適的集成結(jié)構(gòu)，主要優(yōu)點(diǎn)是通過已構(gòu)建的集成結(jié)構(gòu)去處理反復(fù)出現(xiàn)的漂移。

多樣性處理概念漂移是一種很新穎的技術(shù)。Liu等[27]提出一種多樣性實(shí)例加權(quán)集成算法(diverse instance weighting ensemble, DiwE)，同時還提出一種新的多樣性度量方法。該方法對區(qū)域分布變化的評估概率被用作實(shí)例權(quán)值，通過不同的方案構(gòu)造不同的區(qū)域集，會導(dǎo)致不同的漂移估計結(jié)果，從而產(chǎn)生子集。該研究新穎之處在于根據(jù)集成之間區(qū)域漂移概率的不同來測量多樣性。Sidhu等[28]提出多樣化在線集成檢測(diversified online ensembles detection, DOED)，該方法保留了2個加權(quán)分類器集成結(jié)構(gòu)，一個是低多樣性的集成，另一個是高多樣性的集成，并根據(jù)其對新數(shù)據(jù)實(shí)例的分類精度進(jìn)行更新。近些年也有研究將動態(tài)加權(quán)和多樣性相結(jié)合來提高精度。Sidhu等[29]提出多樣化動態(tài)加權(quán)多數(shù)(diversity dynamic weighted majority，DDWM)算法,對具有不同概念分布的新實(shí)例進(jìn)行分類。該方法維持了2組在多樣性水平上不同的加權(quán)集成結(jié)構(gòu)，根據(jù)分類精度更新或刪除一個集成中的基分類器，并根據(jù)算法的最終全局預(yù)測和任何實(shí)例集成的全局預(yù)測添加一個新的基分類器。

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

非平穩(wěn)數(shù)據(jù)流除了要考慮概念漂移問題外，還受數(shù)據(jù)復(fù)雜性的影響。經(jīng)常遇到的類不平衡，主要特點(diǎn)是某一類別的樣本數(shù)量明顯多于其他類別的樣本數(shù)量。類不平衡甚至對靜態(tài)數(shù)據(jù)學(xué)習(xí)也是一個障礙，因為分類器偏向的是大多數(shù)類，并傾向于對少數(shù)類實(shí)例進(jìn)行錯誤分類[30]。使用集成學(xué)習(xí)處理不平衡問題是一種有效的方法，本節(jié)將從數(shù)據(jù)預(yù)處理和代價敏感算法結(jié)合集成學(xué)習(xí)來處理不平衡數(shù)據(jù)流展開討論。

1.2.1 基于預(yù)處理的集成

在不平衡數(shù)據(jù)中，研究人員希望能從數(shù)據(jù)層面降低少數(shù)類與多數(shù)類樣本的不平衡程度，其中數(shù)據(jù)的重采樣是代表性的方法，它可以獲得均勻的類分布。基于重采樣的方法主要有欠采樣、過采樣以及兩者結(jié)合的混合采樣。欠采樣從多數(shù)類樣本中刪除一些實(shí)例，過采樣則增加少數(shù)類樣本的實(shí)例。集成學(xué)習(xí)與預(yù)處理的技術(shù)結(jié)合是目前處理不平衡問題的主要研究方向之一，它可以極大地提高算法的預(yù)測性能。

近些年隨著研究人員對不平衡數(shù)據(jù)的研究深入，集成學(xué)習(xí)與重采樣技術(shù)結(jié)合屢見不鮮。Wang等[31]改進(jìn)了基于在線Bagging的過采樣(oversampling based online bagging, OOB)和欠采樣(under-sampling based online bagging, UOB)技術(shù)，利用重采樣和時間衰減度量對OOB和UOB集成學(xué)習(xí)方法進(jìn)行改進(jìn)，以克服在線類不平衡問題，最后結(jié)合各自優(yōu)點(diǎn)提出加權(quán)集成方法WEOB1和WEOB2，兩者的準(zhǔn)確性優(yōu)于OOB和UOB。肖梁等[32]采用Bagging集成框架，算法采用多集構(gòu)建和特征提取與多集融合模塊構(gòu)成，通過改進(jìn)重采樣構(gòu)建多個不平衡訓(xùn)練集，有效緩解數(shù)據(jù)分布不平衡、噪聲和樣本重疊問題。最近，Zyblewski等[33]提出結(jié)合動態(tài)集成和預(yù)處理技術(shù)的框架來處理高度不平衡的數(shù)據(jù)流，利用分層Bagging分類器對少數(shù)類和多數(shù)類分類進(jìn)行替換抽樣的方法。Ren等[6]提出一種選擇的重采樣集成(selection-based resampling ensemble, SRE)算法，用于學(xué)習(xí)復(fù)雜數(shù)據(jù)分布下的不平衡數(shù)據(jù)流中的概念漂移。SRE結(jié)合重采樣和定期更新的結(jié)構(gòu)來處理聯(lián)合問題。在基于塊的集成框架中，首先采用基于選擇的重采樣機(jī)制來重新平衡最新塊的類分布，然后，使用最新的樣本定期更新先前的集成成員，并確定更新權(quán)值同時對錯誤分類的分類器給予懲罰。段化娟等[34]采用Tomek link欠采樣技術(shù)和集成方法結(jié)合的策略來獲得多個平衡后的子集，每個子集使用決策樹訓(xùn)練，最后集成多個決策樹。

在不平衡數(shù)據(jù)流中也面臨著概念漂移的問題，是目前研究的一個新興內(nèi)容。Ancy等[35]提出動態(tài)采樣和集成學(xué)習(xí)技術(shù)相結(jié)合處理帶有概念漂移的不平衡數(shù)據(jù)流分類算法(handling imbalanced data with concept drift, HIDC)。當(dāng)面臨類不平衡的情況則采用過采樣和欠采樣技術(shù)，其中不平衡率θ的檢測使用公式(4)，

(4)

式中Amaj和Amin分別代表多數(shù)類和少類數(shù)的初始分類精度。HIDC采樣模型訓(xùn)練候選分類器，并用候選分類器替換最差的集成成員。Zhang等[7]提出基于重采樣的處理概念漂移不平衡數(shù)據(jù)流的集成分類框架(resembling-based ensemble framework for drifting imbalanced stream, RE-DI)。該集成框架由處理漸變概念漂移的長期靜態(tài)分類器和處理突變概念漂移的多個動態(tài)分類器組成。集成分類器的權(quán)重從2個方面進(jìn)行調(diào)整：首先，時間衰減策略降低動態(tài)分類器的權(quán)重，使集成分類器更加關(guān)注數(shù)據(jù)流的新概念；其次，提出一種新的強(qiáng)化機(jī)制來增加在少數(shù)類上表現(xiàn)更好的基分類器權(quán)重，并降低表現(xiàn)較差的分類器權(quán)重。

1.2.2 基于代價敏感的集成

除了通過改變數(shù)據(jù)的分布來降低類別不平衡對分類的影響，還可以從算法層面去考慮，設(shè)計適應(yīng)于不平衡數(shù)據(jù)特征的模型。代價敏感[30]考慮不同誤分類類型的代價，代價矩陣將樣本從一個類別分類為另一個類別的懲罰進(jìn)行編碼。針對二分類定義一個代價矩陣，如表1，C(i,j)表示將類別i中的一個實(shí)例預(yù)測為類別j的代價。在處理類別不平衡問題時，辨別正實(shí)例的重要性高于負(fù)實(shí)例，因此，誤分類一個正實(shí)例的代價大于誤分類一個負(fù)實(shí)例的代價,即C(+,-)>C(-,+)。做出正確的分類通常不會帶來任何懲罰，代價敏感學(xué)習(xí)過程尋求最大限度地減少高代價錯誤的數(shù)量和總錯誤分類代價。

表1 代價矩陣

Sun等[36]將代價敏感與集成算法Boosting進(jìn)行結(jié)合，綜合分析AdaBoost算法在解決類不平衡問題上的優(yōu)勢和不足，探索了3種代價敏感的Boosting算法，即AdaC1、AdaC2、AdaC3，將代價項引入到AdaBoost學(xué)習(xí)框架中，進(jìn)一步分析所提出的算法符合統(tǒng)計中的階段性加法建模，以減少代價指數(shù)損失。Tao等[37]提出一種基于代價權(quán)重的支持向量機(jī)的代價敏感集成算法。該方法為了保證基分類器優(yōu)化目標(biāo)與Boosting方案的一致性，不僅將帶有代價敏感的支持向量機(jī)作為基分類器，同時將標(biāo)準(zhǔn)的Boosting方案修改為代價敏感。為了保證連續(xù)分類器有更多的訓(xùn)練實(shí)例，特別是分布在邊界的少數(shù)分類實(shí)例，其提出一種自適應(yīng)順序誤分類代價權(quán)重確定方法。

神經(jīng)網(wǎng)絡(luò)的集成也被應(yīng)用到處理不平衡數(shù)據(jù)過程中。Wong等[38]提出2種新的代價敏感方法——代價敏感深度神經(jīng)網(wǎng)絡(luò)(CSDNN)和代價敏感深度神經(jīng)網(wǎng)絡(luò)集成(CSDE)來解決類不平衡問題。其中CSDE是CSDNN的集成學(xué)習(xí)版本。為了提高CSDNN的泛化性能，在CSDE中采用隨機(jī)欠采樣和深度神經(jīng)網(wǎng)絡(luò)隱含層的分層特征提取。另外，Loezer等[39]提出代價敏感的自適應(yīng)隨機(jī)森林(cost-sensitive adaptive random forest, CSARF)算法，并與自適應(yīng)隨機(jī)森林(ARF)和帶重采樣的隨機(jī)森林(ARFRE)進(jìn)行比較，結(jié)果表明CSARF在平均召回率和平均F1值上均優(yōu)于ARF。

1.3 多標(biāo)簽數(shù)據(jù)流

在形式上，多標(biāo)簽流分類(multi-label classification, MLC)[40]問題就是在高速數(shù)據(jù)流中對每個實(shí)例(帶有子標(biāo)簽Y?L，L是標(biāo)簽集)訓(xùn)練一個模型。雖然在傳統(tǒng)的數(shù)據(jù)挖掘場景中已經(jīng)對多標(biāo)簽分類進(jìn)行了研究，但多標(biāo)簽數(shù)據(jù)流分類是一個比較新的概念，還沒有得到充分解決。本節(jié)將從二元相關(guān)的集成和算法自適應(yīng)的集成分類展開探討。

1.3.1 基于二元相關(guān)的集成

解決多標(biāo)簽分類最直接的方案就是將多標(biāo)簽轉(zhuǎn)換為熟知的單標(biāo)簽分類，其中二元相關(guān)(binary relevance, BR)[8]方法是這種問題轉(zhuǎn)換中最常用的技術(shù)，它將多標(biāo)簽問題轉(zhuǎn)化為一些不同的二元單標(biāo)簽分類問題。

多標(biāo)簽分類器的層次結(jié)構(gòu)(hierarchy of multilabel classifiers, HOMER)[41]是一種為具有大量標(biāo)簽域設(shè)計的方法。它將多標(biāo)簽分類問題轉(zhuǎn)換為更簡單的樹形層次結(jié)構(gòu)。為了對新實(shí)例進(jìn)行分類，HOMER從根分類器開始，并且僅當(dāng)父分類器預(yù)測其任何標(biāo)簽時才將實(shí)例傳遞給每個子分類器。葉子分類器的預(yù)測標(biāo)簽的聯(lián)合即為給定實(shí)例的輸出。Zhang等[42]也提出一種用于HMC(hierarchical multi-label classification)的局部層次集成分類框架,即全關(guān)聯(lián)集成學(xué)習(xí)。其在所有節(jié)點(diǎn)的全局預(yù)測和局部預(yù)測之間建立了一個多變量回歸模型，將基本模型擴(kuò)展為稀疏模型、核模型和二值約束模型。二元相關(guān)性為多標(biāo)簽數(shù)據(jù)的每個不同標(biāo)簽學(xué)習(xí)單個二元模型。它相對于標(biāo)簽數(shù)量具有線性復(fù)雜度，但沒有考慮標(biāo)簽相關(guān)性，可能無法準(zhǔn)確預(yù)測標(biāo)簽組合并根據(jù)與新實(shí)例的相關(guān)性對標(biāo)簽進(jìn)行排序。Tsoumakas等[43]使用集成Stacking結(jié)構(gòu)BR的模型，以學(xué)習(xí)將其輸出與每個標(biāo)簽的真實(shí)值相關(guān)聯(lián)的模型是緩解此問題的一種方法。其通過使用phi系數(shù)顯式地測量標(biāo)簽相關(guān)程度，并對參與Stacking過程的模型進(jìn)行修剪。

在分類器鏈方法中，每個二元分類器以有序鏈的方式排列和連接。Read等[8]提出分類器鏈集成分類模型(ensembles of classifier chains, ECC)來處理多標(biāo)簽分類。該方法是在二元相關(guān)方法的基礎(chǔ)上發(fā)展而來，與目前使用的更復(fù)雜的方法相比降低了計算復(fù)雜度，通過將標(biāo)簽相關(guān)信息沿著分類器鏈傳遞，克服了二元關(guān)聯(lián)方法的缺點(diǎn)，在保持較低計算復(fù)雜度的同時獲得了較好的預(yù)測性能。近年來，文本分類、Web、社交媒體挖掘等應(yīng)用對多標(biāo)簽分類算法的要求越來越高。Nguyen等[44]提出一種可擴(kuò)展的基于在線可變推理的多標(biāo)簽數(shù)據(jù)集成分類方法(MVI)，其使用隨機(jī)投影創(chuàng)建集成系統(tǒng)。作為一種二階生成方法，該分類器在學(xué)習(xí)過程中可以有效地利用數(shù)據(jù)的底層結(jié)構(gòu)。

1.3.2 基于算法自適應(yīng)的集成

多標(biāo)簽算法中自適應(yīng)方法通常是基于考慮相似性或目標(biāo)函數(shù)，對某一子集的特征和學(xué)習(xí)其部分的聯(lián)合標(biāo)簽分布。Wang等[45]提出一種無縫融合多模態(tài)特征和多標(biāo)簽相關(guān)性的超圖學(xué)習(xí)算法。新的特征融合策略將多模態(tài)特征集成到一個統(tǒng)一的超圖中，構(gòu)造一種高效的多模態(tài)超圖，解決了該融合方案計算復(fù)雜度高的問題。采用自適應(yīng)學(xué)習(xí)算法，結(jié)合兩超圖同時學(xué)習(xí)標(biāo)簽分?jǐn)?shù)和超邊權(quán)值，實(shí)驗表明，與具有代表性的算法相比，該文提出的方法具有優(yōu)越性。Wang等[46]提出 SWMEC(streaming weighting ML-KNN based ensemble classifier)算法，該算法是基于ML-KNN的多標(biāo)簽數(shù)據(jù)流分類方法的集成模型。其提出的加權(quán)集成模型，利用多標(biāo)簽數(shù)據(jù)流對模型進(jìn)行有效更新?，F(xiàn)有的多標(biāo)簽分類方法很少采用Stacking集成結(jié)構(gòu)，Xia等[47]提出一種新的多標(biāo)簽加權(quán)分類器選擇和Stacking集成算法(weighted classifier selection and stacked ensemble, MLWSE)，利用稀疏性進(jìn)行正則化，促進(jìn)分類器選擇和集成構(gòu)建，同時利用分類器權(quán)值和標(biāo)簽相關(guān)性提高分類性能。另一方面，集成方法不僅提供一種標(biāo)簽元特定特征的選擇方法，而且可以兼容任何現(xiàn)有的多標(biāo)簽分類算法作為其基分類器。

多數(shù)多標(biāo)簽分類方法側(cè)重于對現(xiàn)有的二值和多類學(xué)習(xí)方法的有效適應(yīng)或轉(zhuǎn)換，但未能對標(biāo)簽的聯(lián)合概率建模。為了解決這些問題，Szymański等[48]提出一種新的多標(biāo)簽分類方案LNEMLC(label network embedding for multi-label classification)。該方案嵌入了標(biāo)簽網(wǎng)絡(luò)，并將其用于擴(kuò)展任意多標(biāo)簽分類器的學(xué)習(xí)和推理的輸入空間。LNEMLC改進(jìn)了算法自適應(yīng)方法，為它們提供額外的輸入特征以供區(qū)分，增加了關(guān)于特征數(shù)量的復(fù)雜度。另外，多標(biāo)簽受到概念漂移挑戰(zhàn)驅(qū)使，Sun等[49]提出MLAW(multi-label ensemble with adaptive windowing)算法，為多標(biāo)簽數(shù)據(jù)流分類設(shè)計一種有效的集成范例。該算法基于Jensen-Shannon散度部署一種新穎的變化檢測，以識別數(shù)據(jù)流中不同類型的概念漂移。Wang等[50]提出一種主動k標(biāo)簽集集成范式(activek-labelsets ensemble for multi-label，ACKEL)，借鑒主動學(xué)習(xí)的思想，提出一個標(biāo)簽選擇標(biāo)準(zhǔn)來評估從標(biāo)簽子集轉(zhuǎn)換而來的類的可分離性和平衡水平。ACKEL可以在不相交和重疊2種模式下實(shí)現(xiàn)，分別采用基于池和基于流的框架。

1.4 多實(shí)例數(shù)據(jù)流

在流挖掘任務(wù)中，多實(shí)例學(xué)習(xí)(multi instance learning, MIL)[51]是一個較少被研究的領(lǐng)域。在傳統(tǒng)的監(jiān)督學(xué)習(xí)中，只有單一的實(shí)例，該實(shí)例只會被一個標(biāo)簽識別，如圖3(a)。然而在多實(shí)例學(xué)習(xí)中，數(shù)據(jù)結(jié)構(gòu)更加復(fù)雜，每個對象或者目標(biāo)變量都是被不確定數(shù)量特征向量所定義，如圖3(b)所示。MIL是一種對一組實(shí)例進(jìn)行分類的方法，每個實(shí)例組都表示為一個包。它的主要任務(wù)是根據(jù)實(shí)例的標(biāo)簽和特征來生成預(yù)測測試包標(biāo)簽的模型。使用集成學(xué)習(xí)的方法處理多實(shí)例數(shù)據(jù)流是研究的新興方向，本節(jié)將從神經(jīng)網(wǎng)絡(luò)的集成和在線學(xué)習(xí)的集成處理多實(shí)例數(shù)據(jù)進(jìn)行介紹。

圖3 單實(shí)例學(xué)習(xí)和多實(shí)例學(xué)習(xí)

1.4.1 基于在線的集成

大多數(shù)傳統(tǒng)MIL算法由于需要進(jìn)行參數(shù)調(diào)整，需要花費(fèi)大量時間進(jìn)行訓(xùn)練。研究者針對學(xué)習(xí)時間問題，提出基于極限學(xué)習(xí)機(jī)的多實(shí)例學(xué)習(xí)方法。Sastrawaha 等[52]提出一種基于集成多數(shù)投票方法的多實(shí)例學(xué)習(xí)集成極限學(xué)習(xí)機(jī)(E-ELM-MIL)方法來提高泛化性能，結(jié)合幾個單一的隱含層神經(jīng)網(wǎng)絡(luò)，并使用多數(shù)投票機(jī)制預(yù)測最終的標(biāo)簽，性能優(yōu)于其他先進(jìn)的MIL算法。近年來，基于神經(jīng)網(wǎng)絡(luò)的多實(shí)例分類算法BP-MIP和多實(shí)例回歸算法BP-MIR相繼被提出。圖像可以獲得多個實(shí)例，這使得圖像分類成為一個MIL問題。Kocyigit等[53]開發(fā)一種利用稀疏特征表示和分類器集成技術(shù)的多實(shí)例主動學(xué)習(xí)方法，即字典集成多實(shí)例主動學(xué)習(xí)(dictionary ensembles multiple instance active learning, DEMIAL)。在提出的主動學(xué)習(xí)框架中采用字典學(xué)習(xí)，對比了基于不確定性和基于熵的實(shí)例選擇技術(shù)，實(shí)驗結(jié)果表明，分類器集成受益于主動學(xué)習(xí)，DEMIAL算法性能優(yōu)于基于核的多實(shí)例主動學(xué)習(xí)框架。

集成學(xué)習(xí)的主要目標(biāo)是將多個學(xué)習(xí)模型結(jié)合起來，并從這些模型的所有輸出中獲得決策?；诖藙訖C(jī)，Taer等[54]提出一種基于集成的多實(shí)例學(xué)習(xí)方法，將標(biāo)準(zhǔn)算法MIWrapper、SimpleMI與集成學(xué)習(xí)方法Bagging、AdaBoost相結(jié)合，以提高分類能力。實(shí)驗結(jié)果表明，基于集成的方法比傳統(tǒng)方法具有更高的分類能力。Tu等[55]提出一種新的基于端到端的圖神經(jīng)網(wǎng)絡(luò)(GNN)的包嵌入算法，將每個包作為一個圖，使用GNN學(xué)習(xí)包嵌入，以探索包實(shí)例之間有用的結(jié)構(gòu)信息，最終的圖表示被送入分類器用于標(biāo)簽預(yù)測。該算法是第一次嘗試將GNN用于MIL。

1.4.2 基于神經(jīng)網(wǎng)絡(luò)的集成

在圖像的目標(biāo)檢測中，Babenko等[9]提出一種在線Boosting改進(jìn)方案(online MILBoost，OMB)。該算法認(rèn)為一旦將一個包標(biāo)記為陽性包，那么其中的所有實(shí)例也是陽性的，因此可以用于訓(xùn)練，可使用與集成算法Boosting類似的訓(xùn)練過程，用新模型更新該集成結(jié)構(gòu)。同樣的目標(biāo)檢測任務(wù)，Wang等[56]提出半監(jiān)督的在線加權(quán)多實(shí)例學(xué)習(xí)集成方法(semi-weighted multi instance learning，Semi-WMIL)。為了充分利用目標(biāo)及其周圍背景信息，結(jié)合半監(jiān)督學(xué)習(xí)、多實(shí)例學(xué)習(xí)和貝葉斯定理，其提出一種新的單目標(biāo)檢測跟蹤器，在每一幀的參數(shù)更新階段，跟蹤器在選擇最優(yōu)基分類器時，使用基于塊的標(biāo)記和未標(biāo)記訓(xùn)練樣本的不一致性函數(shù)。多視圖學(xué)習(xí)結(jié)合了來自多個異構(gòu)源的數(shù)據(jù)，由于不同的多實(shí)例視圖具有不同的基數(shù)和特征空間，因此不能將不同的多實(shí)例視圖數(shù)據(jù)融合簡單地連接到一組特征中。Cano[57]提出一種結(jié)合視點(diǎn)學(xué)習(xí)器并尋求加權(quán)類預(yù)測一致性的集成方法，以利用多個視點(diǎn)的互補(bǔ)信息，重要的是集成必須處理來自每個視圖的不同特征空間，而包的數(shù)據(jù)可能在視圖中部分表示。

一種稱為“檢測跟蹤”的跟蹤技術(shù)已經(jīng)被證明具有較好的跟蹤效果和實(shí)時速度，該方法以在線的方式訓(xùn)練一個分類器來從背景中分離物體。Babenko等[9]提出一種新的在線MIL目標(biāo)跟蹤算法，該算法使用多實(shí)例學(xué)習(xí)而不是傳統(tǒng)的監(jiān)督學(xué)習(xí)，跟蹤器更具魯棒性且參數(shù)調(diào)整較少，具有較好的實(shí)時性。集合分類器的一種眾所周知的策略是隨機(jī)化，其中學(xué)習(xí)算法被隨機(jī)化，以便從同一數(shù)據(jù)集中獲得不同的分類模型。Bjerring等[58]提出一種隨機(jī)化集成方法MIRI(multi-instance rule induction)。該方法基于MITI算法進(jìn)行改進(jìn)，是一個決策樹的單學(xué)習(xí)器，專門為多實(shí)例分類而設(shè)計。但是該算法的分裂準(zhǔn)則對精度有顯著影響，通過修改，將算法變?yōu)橐?guī)則的學(xué)習(xí)器，最終該隨機(jī)化方法生成隨機(jī)森林集成模型。

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

驗證一個算法性能的好壞，除了通過實(shí)驗數(shù)據(jù)分析其運(yùn)行時間、精度等指標(biāo)外，研究人員還應(yīng)該通過理論計算來分析算法的時空效率，時空效率分析可以直觀地了解算法性能，從而促使研究者通過各種優(yōu)化策略(例如剪枝、優(yōu)化算法等)來提高算法的效率，因此時空效率分析是必要的。本節(jié)將對以上經(jīng)典算法的時空效率進(jìn)行詳細(xì)分析來進(jìn)一步深入了解算法，表2羅列了一些代表性算法的復(fù)雜度數(shù)據(jù)分析。

在概念漂移數(shù)據(jù)流算法中，算法的主要時間消耗來自處理概念漂移的情況，算法需要進(jìn)行加權(quán)來不斷更新分類器。AWE算法[5]使用精度加權(quán)集成來挖掘帶有概念漂移的數(shù)據(jù)流，該算法的復(fù)雜度為O(n×f(s/n)+Ks)，其中s代表數(shù)據(jù)塊的大小，K是分類器的數(shù)目，它的復(fù)雜度主要在于訓(xùn)練每個基分類器。比較經(jīng)典的OAUE[2]算法是結(jié)合在線和塊訓(xùn)練技術(shù)的方法，它的復(fù)雜度是O(kpvl+k(d+c))，其中p代表數(shù)據(jù)的數(shù)目，v代表數(shù)值的數(shù)目。由于算法中K、d、c為常數(shù)，因此與沒有加權(quán)的集成相比，該加權(quán)方案并沒有增加空間復(fù)雜度。EOCD[26]算法的復(fù)雜度為O(KCVP)，其中C為類數(shù)目，K為分類器數(shù)量，采用了復(fù)雜度為O(1)的RDDM漂移檢測器，為了優(yōu)化模塊的復(fù)雜性，其使用了遺傳算法。

在不平衡數(shù)據(jù)流算法中，算法的時間消耗主要來自處理不平衡數(shù)據(jù)和對不平衡數(shù)據(jù)進(jìn)行分類。DES[33]算法的復(fù)雜度主要由用于動態(tài)選擇方法的分類器池中的模型數(shù)量，以及預(yù)處理技術(shù)中單個數(shù)據(jù)塊中的實(shí)例數(shù)量決定，其中動態(tài)選擇方法的復(fù)雜度是O(n),預(yù)處理技術(shù)復(fù)雜度為O(nlogn)。SRE是基于重采樣的集成方法，復(fù)雜度為O(N|M|log(|M|+s)+sNlogs+3|M|N)，其中M為塊數(shù)量，N為數(shù)據(jù)流實(shí)例的數(shù)量。SRE復(fù)雜度的一部分是為了處理不平衡狀態(tài)下的概念漂移，另一部分是使用重采樣技術(shù)來平衡數(shù)據(jù)流。

多標(biāo)簽數(shù)據(jù)流目前在圖像和目標(biāo)檢測領(lǐng)域應(yīng)用較多，它的時空效率相對于其他數(shù)據(jù)流較復(fù)雜。這由它本身的復(fù)雜性決定，一個目標(biāo)具有多個標(biāo)簽，這時分類的范圍也增大。ACKEL[50]算法的復(fù)雜度為O(N2n)，其中N為樣本數(shù)量，n為特征數(shù)量，主要計算代價來自算法中核函數(shù)的計算。LNEMLC算法[48]的復(fù)雜度是嵌入方法、分類器和回歸計算過程的總和，其復(fù)雜度不會高于O(ld+2n(m+d)+2mn+ln)，算法的復(fù)雜度主要來自KNN分類器采樣的數(shù)目。經(jīng)典算法ECC[8]分類器鏈的復(fù)雜度為O(LV×f(1,N))，其中L為額外屬性的數(shù)目。

近些年集成學(xué)習(xí)在各種場景下使用，雖然在評估指標(biāo)(如精度等)上有極大的提高，但是總體來說其時空復(fù)雜度還是比較高，這是由于它不斷增加的集成大小以及集成結(jié)構(gòu)所致。為了提高效率，研究人員需要從它的剪枝策略進(jìn)行入手研究。表3列舉了集成學(xué)習(xí)處理復(fù)雜數(shù)據(jù)流算法性能的對比。

表 2 代表性算法復(fù)雜度分析

表3 復(fù)雜數(shù)據(jù)流集成分類算法性能比較

2 領(lǐng)域數(shù)據(jù)流集成分類

數(shù)據(jù)流分類已經(jīng)被研究人員拓展到很多領(lǐng)域進(jìn)行挖掘，提取有用的信息進(jìn)行該領(lǐng)域的研究。隨著現(xiàn)在互聯(lián)網(wǎng)不斷觸及各行各業(yè)，人們對于分類任務(wù)的需求也在不斷擴(kuò)展。在流挖掘任務(wù)中，文本數(shù)據(jù)、圖數(shù)據(jù)以及傳感器數(shù)據(jù)，這些領(lǐng)域是研究人員鉆研的數(shù)據(jù)流分類的高級問題。由于數(shù)據(jù)的表示、結(jié)構(gòu)以及數(shù)據(jù)的量級發(fā)生了重大變化，分析起來需要更加復(fù)雜的算法來進(jìn)行處理，本章將對這些數(shù)據(jù)流近些年的研究成果進(jìn)行分析。

2.1 文本數(shù)據(jù)流

在自然語言處理(nature language processing, NLP)[59]領(lǐng)域，文本分類一直都是一個熱門的研究方向，像Twitter和微博這樣受歡迎的社交平臺，會涉及到新聞內(nèi)容、社交、廣告等方面進(jìn)行分析。然而文本流分類還是目前文本分類的一個新興方向，涉及數(shù)據(jù)流的及時到達(dá)以及一次處理等特點(diǎn)都需要研究人員進(jìn)行考慮。目前文本數(shù)據(jù)流分類集成學(xué)習(xí)方法是應(yīng)用最廣泛的方法之一。

基于概念漂移的文本流挖掘是一個非常具有挑戰(zhàn)性的研究課題。Song等[60]提出一種新的集成模型——動態(tài)聚類森林(dynamic cluster forest, DCF)，用于存在概念漂移的文本流分類。其提出的集成模型是基于多個聚類樹(CTs)構(gòu)建的。特別地，DCF模型有2種新穎的策略：1)根據(jù)數(shù)據(jù)流的固有特性動態(tài)選擇判別性CTs的自適應(yīng)集成策略；2)同時考慮分類器可信度和準(zhǔn)確性的雙投票策略。由于短文本流的稀疏性、高維性和快速變異性，短文本流分類面臨著巨大的挑戰(zhàn)。Hu等[61]提出一種基于在線的短文本擴(kuò)展和概念漂移檢測的短文本流分類方法，首先從外部資源中擴(kuò)展短文本流，以彌補(bǔ)數(shù)據(jù)的稀疏性，并使用在線BTM(bitterm topic model)算法選擇具有代表性的主題，而不是用詞向量來表示短文本的特征。其次，作者利用多個數(shù)據(jù)塊建立集成模型，并利用最新的數(shù)據(jù)塊和概念漂移檢測結(jié)果進(jìn)行更新。實(shí)驗表明，在分類和概念漂移檢測方面取得了更好的性能。

文本分類通過將完成的任務(wù)劃分為不同的類別，降低了時空復(fù)雜度。文本分類的主要問題是從文本數(shù)據(jù)中提取大量的特征。Khurana等[62]提出一種基于自然啟發(fā)算法和集成分類器的文本最優(yōu)分類方法，采用基于生物地理學(xué)的優(yōu)化算法BBO(biogeography based optimization)和集成分類器Bagging進(jìn)行特征選擇，與單獨(dú)的分類器相比，使用集成分類器進(jìn)行分類可以提供更好的文本分類性能，從而提高準(zhǔn)確率。Upadhyay等[63]提出一種加權(quán)分類器集成算法來解決文本分類問題。該算法在組合分類器時，將每個分類器的預(yù)測與不同的權(quán)重相關(guān)聯(lián)，而不是使用多數(shù)投票作為組合方法，并利用粒子群優(yōu)化算法對訓(xùn)練數(shù)據(jù)進(jìn)行損失函數(shù)最小化，得到最優(yōu)權(quán)重。Samami等[64]提出一種基于自然啟發(fā)算法和集成分類器的最優(yōu)文本分類方法，與單個分類器相比，使用集成分類器進(jìn)行特征選擇可以為最優(yōu)文本分類提供更好的性能。

2.2 圖數(shù)據(jù)流

圖分類的問題出現(xiàn)在許多經(jīng)典領(lǐng)域，如化學(xué)和生物數(shù)據(jù)、高光通信網(wǎng)絡(luò)等。近年來，隨著互聯(lián)網(wǎng)應(yīng)用的出現(xiàn)，人們對動態(tài)圖數(shù)據(jù)流應(yīng)用的興趣越來越大，這種網(wǎng)絡(luò)應(yīng)用程序是在大量節(jié)點(diǎn)的基礎(chǔ)上定義的。圖數(shù)據(jù)流分類最具挑戰(zhàn)性的情況，即數(shù)據(jù)僅以圖形流的形式存在。因此在圖數(shù)據(jù)流分類中要檢測到數(shù)據(jù)流中的變化來進(jìn)行實(shí)時分類，集成學(xué)習(xí)也逐漸在圖結(jié)構(gòu)領(lǐng)域中受到關(guān)注。

標(biāo)簽的動態(tài)變化可能表明重要事件或活動模式，Aggarwal等[65]研究圖數(shù)據(jù)流中的差分分類問題，其中預(yù)測重要的分類事件表現(xiàn)在節(jié)點(diǎn)分類標(biāo)簽的變化。與靜態(tài)的集成分類問題不同，該方法側(cè)重于動態(tài)、實(shí)時地檢測節(jié)點(diǎn)分類的變化，而不是對節(jié)點(diǎn)進(jìn)行實(shí)際的分類。在許多實(shí)際應(yīng)用中，圖可以在一個非常大的節(jié)點(diǎn)集合上定義。底層圖的許多域大小使得學(xué)習(xí)分類問題的概要結(jié)構(gòu)信息變得困難，尤其是在數(shù)據(jù)流的情況下。Tuncer等[66]開發(fā)一種新的基于集成局部圖結(jié)構(gòu)LGS(local graph structure)的輕量級和認(rèn)知特征提取框架，并通過使用該框架，提出一種新的腦電圖(Electroencephalogram, EEG)信號識別方法，包括預(yù)處理、使用基于集成LGS的方法進(jìn)行特征提取以及使用基準(zhǔn)分類器進(jìn)行分類。結(jié)果表明，其成功地利用LGS算法開發(fā)了一種更準(zhǔn)確、更認(rèn)知的腦電信號識別方法。

在圖數(shù)據(jù)流的分類任務(wù)中也存在不平衡的問題，Pan等[67]提出一種分類模型來處理帶有噪聲的不平衡圖數(shù)據(jù)流即圖集成，使用集成框架來將圖數(shù)據(jù)流劃分成包含許多類分布不平衡的噪聲圖的塊。針對每個獨(dú)立的數(shù)據(jù)塊提出一種基于集成的Boosting算法，將判別子圖模式選擇和模型學(xué)習(xí)結(jié)合起來作為統(tǒng)一的圖分類框架?；ゎI(lǐng)域經(jīng)常存在故障分類，Liu等[68]提出一種基于流形保持稀疏圖的集成FDA(fisher discriminant analysis)模型。首先，在保持訓(xùn)練樣本基本流形結(jié)構(gòu)的前提下，利用保留流形的稀疏圖對一些錯誤標(biāo)記的樣本進(jìn)行過濾。其次，為了提高模型對錯誤樣本的魯棒性，利用基于FDA的Bagging算法構(gòu)建多個子分類器，并將這些子分類器組合形成魯棒的分類器。Su等[69]提出一種多標(biāo)簽分類的新方法，依賴于多標(biāo)簽上的隨機(jī)輸出圖集合的集成學(xué)習(xí)。對于集成學(xué)習(xí)，輸出圖之間的差異提供了所需的基分類器的多樣性，并在集成規(guī)模不斷增加的情況下提高性能。

2.3 傳感器數(shù)據(jù)流

人們的生產(chǎn)生活中，有大量的數(shù)據(jù)來自智能設(shè)備，這些設(shè)備自帶的傳感器時刻傳遞不同的信息。傳感器數(shù)據(jù)流分析是當(dāng)前數(shù)據(jù)挖掘熱門的研究領(lǐng)域之一，目前集成學(xué)習(xí)是挖掘該領(lǐng)域數(shù)據(jù)流的主要方法。

傳感器數(shù)據(jù)流挖掘方法最近引起了智能家居研究的廣泛關(guān)注。Shahi等[70]提出一種新的基于自適應(yīng)聚類的流傳感器數(shù)據(jù)集成學(xué)習(xí)事件分類方法，包含一些理想的特性，如基于窗口的自適應(yīng)傳感器事件，使用時間衰減函數(shù)檢測相關(guān)傳感器事件，在當(dāng)前窗口保存過去的傳感器信息，以及形成在線的流傳感器數(shù)據(jù)集群。該方法改進(jìn)了流傳感器事件的表示，可以使用在線方式學(xué)習(xí)和識別活動。無線身體傳感器網(wǎng)絡(luò)(BSNs)是一種可穿戴傳感器，具有傳感、存儲、計算和傳輸能力。當(dāng)數(shù)據(jù)來自多個設(shè)備時，需要進(jìn)行多傳感器融合，將潛在的錯誤傳感器數(shù)據(jù)轉(zhuǎn)化為高質(zhì)量的融合數(shù)據(jù)。Muzammal等[71]提出一種數(shù)據(jù)融合的集成方法，用于在霧計算環(huán)境下處理BSNs獲得的醫(yī)療數(shù)據(jù)。在分類方面，該方法采用一種新的核隨機(jī)森林集成，其質(zhì)量顯著優(yōu)于隨機(jī)森林。

由于數(shù)據(jù)的高維特性，分析生產(chǎn)環(huán)境中的傳感器數(shù)據(jù)相當(dāng)具有挑戰(zhàn)性。Iftikhar等[72]提出一種基于滑動窗口的集成方法，以流的方式檢測異常值。該方法結(jié)合聚類算法構(gòu)造表示不同數(shù)據(jù)結(jié)構(gòu)的子集合，模型集成技術(shù)通過提供一種合適的聚合機(jī)制來有效地解決分類應(yīng)用。Alippi等[73]提出使用模型集成來在線重建傳感器網(wǎng)絡(luò)的缺失數(shù)據(jù)。重建缺失數(shù)據(jù)對于任何數(shù)據(jù)處理都是至關(guān)重要的，必須在線進(jìn)行以避免利用數(shù)據(jù)決策或控制行動時引入不必要的延遲。集成的設(shè)計利用了構(gòu)成網(wǎng)絡(luò)的傳感器之間的時間和空間依賴性。Rodríguez等[74]介紹一類k均值隨機(jī)投影特征算法OCKRA(one-classk-means with randomly-projected features algorithm)。它是根據(jù)隨機(jī)特征子集在數(shù)據(jù)集的多個投影上構(gòu)建的一類分類器集成，實(shí)驗數(shù)據(jù)通過嵌入在可穿戴手環(huán)上的一組傳感器獲取。

3 數(shù)據(jù)流評估方法

正確評估分類器或者回歸模型是機(jī)器學(xué)習(xí)的一個關(guān)鍵問題。圖4為數(shù)據(jù)流完整的分類過程，其中包含評估的環(huán)節(jié)。采用正確、適合的評估措施也是實(shí)驗驗證的重要過程，但只有通過科學(xué)嚴(yán)謹(jǐn)?shù)臄?shù)據(jù)評估才能展現(xiàn)出算法優(yōu)勢。性能評估是分類的最后一個環(huán)節(jié)，下面將詳細(xì)討論在數(shù)據(jù)流環(huán)境中，研究人員經(jīng)常使用的數(shù)據(jù)流分類的驗證技術(shù)，以及復(fù)雜數(shù)據(jù)流各自特有的性能評估方法。

圖4 數(shù)據(jù)流評估過程

3.1 驗證技術(shù)

在靜態(tài)和批處理學(xué)習(xí)的背景下，最常用的評估措施是交叉驗證。由于傳統(tǒng)的數(shù)據(jù)量有限，根據(jù)交叉驗證來提高數(shù)據(jù)使用率最大的缺點(diǎn)是耗費(fèi)時間。然而在具有嚴(yán)格計算要求和概念漂移的數(shù)據(jù)流環(huán)境中，它并不直接適用。盡管流學(xué)習(xí)算法的數(shù)量不斷增加，但評估學(xué)習(xí)模型質(zhì)量的指標(biāo)和實(shí)驗設(shè)計仍然是一個開放的問題。評估技術(shù)決定哪些實(shí)例用于訓(xùn)練，哪些實(shí)例用于測試學(xué)習(xí)模型。本節(jié)將總結(jié)在數(shù)據(jù)流實(shí)驗中廣泛使用的驗證技術(shù)。

Holdout：Holdout是一個獨(dú)立的測試集，使用這種評估方法需要2個數(shù)據(jù)子集：訓(xùn)練數(shù)據(jù)集和獨(dú)立測試集。在進(jìn)行模型評估的任何時刻，都有一個模型之前沒有使用過的測試集合，通過在不斷更新的集合上測試學(xué)習(xí)模型就得到了模型誤差的無偏估計。Gama等[75]在超快速森林樹系統(tǒng)UFFT(ultra fast forest tree system)使用該驗證技術(shù),同時許多研究人員在綜述論文[11-12]中對Holdout評估方法進(jìn)行了詳細(xì)介紹，從傳統(tǒng)的批處理對Hold的應(yīng)用拓展到數(shù)據(jù)流場景。

Prequential：該方法是數(shù)據(jù)流中最常用的評估技術(shù)，其思想是先用實(shí)例測試模型，然后再訓(xùn)練模型。每當(dāng)一個實(shí)例經(jīng)過時，當(dāng)前的模型就會做出預(yù)測，同時會得出模型的損失。為了使誤差估計對這種情況更有魯棒性，必須實(shí)現(xiàn)適當(dāng)?shù)倪z忘機(jī)制，即結(jié)合滑動窗口或衰減因子。Brzezinski等[2]在進(jìn)行OAUE算法的實(shí)驗設(shè)置時，其Prequential評估方法采用滑動窗口和衰減因子作為遺忘條件，窗口大小d=1 000，衰減因子α=0.01，通過調(diào)整這2個變量來驗證算法。Bertini Junior等[21]的IBS算法使用了同樣的窗口和衰減因子結(jié)合的評估方法進(jìn)行實(shí)驗。

Cross-validated prequential：當(dāng)前社會面臨的數(shù)據(jù)流具有來源多樣、實(shí)時性強(qiáng)、數(shù)據(jù)量大等特性。Bifet等[76]提出了新的對大數(shù)據(jù)流評估的分布式K折驗證方法。在使用真實(shí)數(shù)據(jù)對分類器進(jìn)行訓(xùn)練時，優(yōu)先評估方法相較于交叉驗證只能運(yùn)行一次實(shí)驗，標(biāo)準(zhǔn)的交叉驗證獨(dú)立地處理數(shù)據(jù)流的每個折疊，因此可能會錯過數(shù)據(jù)流中發(fā)生的概念漂移。為了克服這個挑戰(zhàn)，該文提出3種策略：1)交叉驗證(cross-validation)；2)分割驗證(split-validation)；3)采樣驗證(bootstrap validation)。理論證明，使用K折方法的誤差比優(yōu)先方法低。在Gomes等[77]提出的自適應(yīng)隨機(jī)森林(ARF)算法實(shí)驗驗證中也用到了K折驗證方法。

Latency Verification：流式挖掘的很大一部分研究都是在做出預(yù)測后，立即對真實(shí)標(biāo)簽的可用性進(jìn)行分類。但是在許多實(shí)際情況下，給數(shù)據(jù)貼標(biāo)簽的延遲不可忽略，這就提出了在這種情況下如何評估分類器的問題。Gomes等[77]在ARF算法的評估中進(jìn)行了及時設(shè)置和延遲設(shè)置來模擬實(shí)驗，提出一種評估分類性能的方法，其假設(shè)存在標(biāo)簽不易獲得的問題，標(biāo)識為“延遲標(biāo)簽設(shè)置”，并且定義非常簡單：根據(jù)其正確預(yù)測實(shí)例的能力來評估，只能在固定的時間單位后使用。Grzenda等[78]提出一種新的對數(shù)據(jù)流標(biāo)簽延遲的評估方法，即連續(xù)重新評估，它應(yīng)用于參考數(shù)據(jù)流，并基于新到達(dá)實(shí)例細(xì)化預(yù)測的能力來區(qū)分流挖掘技術(shù)。

3.2 評估指標(biāo)

隨著數(shù)據(jù)流挖掘不斷受到重視，各種復(fù)雜數(shù)據(jù)流的算法也被相繼提出。然而一個好的處理數(shù)據(jù)流分類算法，需要相應(yīng)的評估指標(biāo)去驗證。本節(jié)對廣泛研究的復(fù)雜數(shù)據(jù)流的評估指標(biāo)進(jìn)行討論，同時對比總結(jié)各種常見數(shù)據(jù)流算法的評估指標(biāo)。表4列舉了數(shù)據(jù)流算法實(shí)驗中各自適配的評估指標(biāo)。

表4 復(fù)雜數(shù)據(jù)流算法的評估指標(biāo)

3.2.1 傳統(tǒng)分類評估指標(biāo)

在傳統(tǒng)穩(wěn)態(tài)數(shù)據(jù)流的機(jī)器學(xué)習(xí)分類中，算法的評估指標(biāo)多集中在準(zhǔn)確率(accuracy, Acc)、錯誤率(error rate)、內(nèi)存(memory, M)和運(yùn)行時間(running time, RT)。無論是回歸還是分類任務(wù)，這4個指標(biāo)是最優(yōu)先考慮的。然而，為了全方位評估算法的性能，更加復(fù)雜的評估指標(biāo)，即精準(zhǔn)率(precision, P)和召回率(recall, R)被提出,它們能更好地評估傳統(tǒng)的分類或者回歸任務(wù)。Precision用于衡量分類器的查準(zhǔn)率，表示辨識為正的正樣本占所有辯識為正的樣本比重，而Recall用于衡量分類器的查全率，表示辨識為正的正樣本占所有正樣本的比重。

3.2.2 復(fù)雜數(shù)據(jù)流分類評估指標(biāo)

在數(shù)據(jù)流分類場景中會面臨各種復(fù)雜的情況，如前后分類的概念不一樣、標(biāo)簽數(shù)量不相同，等等。這些復(fù)雜情況的評估需要研究者分門別類研究，下面將總結(jié)在非靜態(tài)分類中，研究者在文獻(xiàn)中所使用到的分類評估指標(biāo)，同時在非靜態(tài)環(huán)境中，傳統(tǒng)的分類評估指標(biāo)依然可以作為通用的評估指標(biāo)。Bifet等[79]提出在非靜態(tài)環(huán)境中對時間評估的新指標(biāo)RAM-Hours，它是一種基于云計算服務(wù)租賃成本的一維度量。

概念漂移數(shù)據(jù)流：在含有概念漂移的數(shù)據(jù)流中，有時需要主動檢測漂移是否發(fā)生，再根據(jù)設(shè)計的算法進(jìn)行處理，以便讓分類器更好地進(jìn)行學(xué)習(xí)而不用一直降低精度。Abdualrhman等[23]在DCDD算法中使用到漂移檢測率(drift detection rate，DDR)、漂移檢測錯誤率(drift detection error rate, DDER)。DDR=正確檢測到飄移的數(shù)量/檢測漂移的總數(shù)量；DDER=錯誤檢測漂移的數(shù)量/檢測漂移的總數(shù)量。

不平衡數(shù)據(jù)流：在不平衡數(shù)據(jù)流中，傳統(tǒng)的指標(biāo)已經(jīng)不適用于不平衡的分類場景。分類器總傾向多數(shù)類別，因此針對不平衡分類性能評估，相關(guān)學(xué)者提出F-Measure(F)、G-Mean(G)。F-Measure與召回率(recall)和精確率(precision)相關(guān)，它可以正確評價分類器對于多數(shù)類和少數(shù)類樣本的分類性能。G-mean是Kubat等[80]提出的幾何均值，它同時考慮了少數(shù)類和多數(shù)類的精度，常用于評估不平衡數(shù)據(jù)的分類。Sensitivity是對模型正確預(yù)測正例樣本的度量，它有時被稱為真陽性率(TPR)。Specificity是模型正確預(yù)測負(fù)類樣本的度量，它有時被稱為真負(fù)率(TNR)。Kappa統(tǒng)計在不平衡數(shù)據(jù)流中是經(jīng)常使用的統(tǒng)計方法，其中標(biāo)準(zhǔn)的KappaK(K)也是常用的評估指標(biāo)，而Bifet等[76]提出廣義的KappaM，它比標(biāo)準(zhǔn)的KappaK更適合不平衡數(shù)據(jù)流。另外，受試者工作特征(receiver operating characteristic, ROC)曲線和曲線下面積(area under ROC curve，AUC)也常用于評估分類器性能。為了表述以上指標(biāo)，以二分類為主，采用混淆矩陣(見表5)來表示常用的不平衡數(shù)據(jù)評估的公式(見表6)。

表5 混淆矩陣

表6 評估指標(biāo)的公式

多標(biāo)簽數(shù)據(jù)流：在流數(shù)據(jù)挖掘任務(wù)中，多標(biāo)簽數(shù)據(jù)流相關(guān)算法始終是研究較少的一個方向。由于它本身的復(fù)雜性對于實(shí)驗設(shè)計有著不同的要求，但是仍然有它特有的分類性能評估方法，許多文獻(xiàn)提出相應(yīng)的評估指標(biāo)，如漢明損失(hamming loss, HL)、子集精度(subset-accuracy)、排序損失(ranking loss, RL)等[81]。Hamming loss考慮了預(yù)測錯誤和丟失錯誤，評估的是一個實(shí)例標(biāo)簽對被錯誤分類的頻率。Subset-accuracy是一個非常嚴(yán)格的精度度量標(biāo)準(zhǔn)，如果分類器預(yù)測的所有標(biāo)簽都是正確的，就認(rèn)為分類是正確的。

除了以上常用的評估指標(biāo)外，也有文獻(xiàn)提出更復(fù)雜的方法來評估算法特性。Shaker等[82]提出恢復(fù)分析(recovery analysis)，它提供一個概念學(xué)習(xí)器快速發(fā)現(xiàn)概念漂移的能力，并采取適當(dāng)?shù)拇胧﹣肀３帜Ｐ偷馁|(zhì)量和泛化性能。不僅考慮模型在新的決策空間中減少誤差的效果，而且還考慮所需的時間。

4 展望

雖然現(xiàn)在很多類型的數(shù)據(jù)流都有各自的解決方案，但是還有很多類型的數(shù)據(jù)流無論是在算法層面，還是評估方面都需要去探究。例如挖掘延遲的標(biāo)簽流、多種類型并存的數(shù)據(jù)流、不確定數(shù)據(jù)流以及數(shù)據(jù)流的評估方法等，下面將對這些問題進(jìn)行仔細(xì)分析。

4.1 不確定數(shù)據(jù)流集成分類的挑戰(zhàn)

很少有學(xué)者進(jìn)行不確定數(shù)據(jù)流的挖掘研究，目前可用的數(shù)據(jù)流分類算法都致力于精確數(shù)據(jù)的挖掘，但不確定的數(shù)據(jù)在現(xiàn)實(shí)應(yīng)用中卻很常見。如在傳感器網(wǎng)絡(luò)采集和傳輸過程中，濕度、溫度等天氣信息含有大量的不確定性。Yu等[83]提出一種的混合增量回歸神經(jīng)網(wǎng)絡(luò)，能夠從大量不確定數(shù)據(jù)中學(xué)習(xí)準(zhǔn)確的回歸模型。近幾年對不確定數(shù)據(jù)的其他研究較多，但對于它的分類研究，尤其是集成分類這個方向的研究仍然稀缺。

4.2 多種數(shù)據(jù)流并存集成分類的挑戰(zhàn)

現(xiàn)在大多數(shù)研究的流集成處理的是單個流，然而在一些應(yīng)用中，例如歷史事件分析中涉及數(shù)據(jù)的審查可能會存在多個流[84]。在這樣的多個流中，相同的數(shù)據(jù)事件可能出現(xiàn)在每個流中的不同時刻，并且可能具有不同的描述。這帶來了幾個有趣且新的挑戰(zhàn)，例如，如何匯總不同流中可用的同一事件的信息，如何預(yù)測事件在其中一個流中出現(xiàn)的時刻，等等。在大數(shù)據(jù)分析中整合不同數(shù)據(jù)存儲庫的背景下，這些方面應(yīng)該特別重要。集成學(xué)習(xí)在多個數(shù)據(jù)流中的應(yīng)用將是一個新的研究和挑戰(zhàn)。

4.3 延遲數(shù)據(jù)流集成分類的挑戰(zhàn)

目前大多數(shù)框架都假定對目標(biāo)值的訪問是實(shí)時的，或者沒有太大延遲的，然而現(xiàn)實(shí)生活中很多事件是延遲預(yù)測的。當(dāng)不能快速標(biāo)記所有的實(shí)例時，仍然有可能以合理的代價為有限數(shù)量的實(shí)例獲得真正的標(biāo)簽。?liobaitē等[85]提出數(shù)據(jù)流中主動學(xué)習(xí)的理論框架，給出主動學(xué)習(xí)策略的3個條件：在無限長的時間內(nèi)平衡標(biāo)簽預(yù)算;感知實(shí)例空間中的任何位置變化；保持傳入數(shù)據(jù)的分布以檢測變化。未來研究可以將主動學(xué)習(xí)與集成框架相結(jié)合來處理延遲的樣本標(biāo)簽。

4.4 數(shù)據(jù)流分類評估方法的挑戰(zhàn)

目前各種復(fù)雜數(shù)據(jù)流的實(shí)驗測量都有各自適配的評估指標(biāo)，但是也存在相應(yīng)的問題。在實(shí)際算法應(yīng)用中，研究人員需要根據(jù)需求來選擇合適的度量指標(biāo)，有很多方面需要完善：第一，如何綜合各類性能度量指標(biāo)，給出一個更加準(zhǔn)確、全面的算法性能評價結(jié)果，將是一個非常值得研究的問題；第二，在延遲到來的數(shù)據(jù)流中應(yīng)該有延遲率的評估，這樣可以采取適當(dāng)方法提高分類性能；第三，不僅需要提供分類學(xué)習(xí)算法的AUC度量，還需要提供它的方差或置信區(qū)間，以給出更加準(zhǔn)確的算法性能度量結(jié)果。

5 結(jié)語

本文對現(xiàn)有的復(fù)雜數(shù)據(jù)流集成分類的算法進(jìn)行了綜述。首先，從研究背景的概述、復(fù)雜數(shù)據(jù)流集成分類算法、領(lǐng)域數(shù)據(jù)流、數(shù)據(jù)流的評估方法以及研究展望進(jìn)行了詳細(xì)分析，其中對復(fù)雜數(shù)據(jù)流集成算法和相關(guān)評估方法進(jìn)行了詳細(xì)討論，包括基分類器、集成技術(shù)和集成策略等。然后，從數(shù)據(jù)集、集成方式、優(yōu)缺點(diǎn)、復(fù)雜度方面對所提到的算法進(jìn)行對比，同時對現(xiàn)有數(shù)據(jù)流的應(yīng)用領(lǐng)域進(jìn)行總結(jié)。最后，對復(fù)雜數(shù)據(jù)流集成分類所面臨的挑戰(zhàn)提出未來的研究方向，以便這些問題可以得到解決和研究。