概念漂移數據流集成分類算法綜述

杜詩語,韓 萌,申明堯,張春硯,孫 蕊

(北方民族大學 計算機科學與工程學院,銀川 750021)

0 概述

在信息時代,人們每時每刻都在產生海量數據,例如社交網絡、交通流量和各種傳感器等。數據通常以流的形式出現,數據流是隨時間推移到達的潛在無界且有序的實例序列。數據流挖掘是大數據時代最重要的研究領域之一,其目標是從連續的數據流中提取出隱藏的信息。

數據流分為靜態數據流和動態數據流(概念漂移數據流)。靜態中的實例雖然以未知的概率分布,但以固定的來源出現。動態目標概念(實例類)或屬性分布隨時間演變,即概念漂移。概念漂移反映在傳入的實例中,其降低了從歷史訓練實例中得到分類器的準確性。概念漂移問題是一個急需解決的問題,如分類器不能及時獲取新知識且不能較好保存歷史數據等。在現實生活中受概念漂移影響的實例有很多,如交通監控、金融詐騙檢測、天氣預報和醫療決策輔助等。

在對數據流分類時,根據處理數據實例的方式可以將分類算法分為基于塊的算法、在線學習算法和增量學習算法等。Bagging++[1]和在線順序極限學習機(Online Sequential Extreme Learning Machine,OS-ELM)[2]是基于塊技術的算法。在線學習算法有LevBag[3]和知識最大化集成算法(Knowledge-maximized Ensemble,KME)[4]等。增量學習算法有精度更新集成算法(Accuracy Updated Ensemble,AUE)[5]和預測檢測流框架[6]等。集成分類算法與概念漂移檢測算法結合動態更新策略,可以對數據流進行更加精準的分類。

集成算法是數據流分類中使用最廣泛的技術之一,其與單分類器相比具有更好的性能,且在實際應用程序中更容易部署,其主要優點是易于更新、適應性強、性能好。經典的集成算法有AdaBoost[7]、在線精度更新集成算法(Online Accuracy Updated Ensemble,OAUE)[8]、窗口自適應在線精度更新集成算法(Window-Adaptive Online Accuracy Updated Ensemble,WAOAUE)[9]。近年來提出的集成分類算法包括動態集成算法(Dynamic Ensemble of Ensembles,DE2)[10]、迭代提升流集成算法(Iterative Boosting Streaming,IBS)[11]、動態集成選擇算法(Dynamic Ensemble Selection,DES)[12]等,在分類過程中可以得到準確率更高、魯棒性更強的最終結果。

集成分類算法可以較好地處理概念漂移問題。經典算法有流集成算法(Streaming Ensemble Algorithm,SEA)[13]和精度加權集成算法(Accuracy Weighted Ensemble,AWE)[14]等。近年來提出的算法有基于熵的集成算法(Entropy Based Ensemble,EBE)[15]、確定性概念漂移檢測算法(Deterministic Concept Drift Detection,DCDD)[16]、基于選擇重采樣集成算法(Selection-based Resampling Ensemble,SRE)[17]等,這些算法在處理概念漂移問題時,具有較高的分類精度及準確性。本文對概念漂移類型、概念漂移數據流集成分類算法及其關鍵策略和技術進行分析與研究。

1 概念漂移

數據流是隨時間推移到達的潛在無界且有序的實例序列。設D={d1,d2,…,di-1,di,di+1,…}表示數據流,其中,di={ai,bi},ai是每個屬性的第i個數據的值,bi是實例的類標簽。數據流分類的目標是訓練分類器,建立特征向量和類標簽之間的映射關系。概念漂移數據流的特點是數據量無限、維數多且數據流中蘊含的概念隨時間改變。為更好地解決數據流中的概念漂移問題,需了解概念漂移的特性,本節將從3個角度介紹概念漂移類型。

隨著數據實例的引入,集群的結構會發生變化,導致集群中表示的概念發生變化,這種概念變化稱為概念漂移。研究人員對概念漂移的深入理解是通過分析概念漂移的種類及產生原因逐步得到的。實際問題中會出現不同類型的概念漂移,例如在社會網絡分析中,一個社會群體中的人在某一特定時期對某一特定事物感興趣。興趣的突然改變或逐漸改變,對人類來說是顯而易見的。研究人員把這種情況的漂移稱為真實概念漂移,認為漂移不僅因為所處環境發生變化導致,而且因為數據流的概率分布模型發生變化,并把后者的漂移稱為虛擬概念漂移。真實概念漂移會改變類間的決策邊界,而虛擬概念漂移會影響類間的比例,這與類間的不平衡問題有關,真實概念漂移與虛擬概念漂移分布類型如圖1所示。

圖1 真實概念漂移與虛擬概念漂移的分布類型

Fig.1 Distribution types of real concept drift and virtual concept drift

文獻[13]指出概念漂移的具體表現為:1)類標號的先驗概率P(a1),P(a2),…,P(ak)可能發生變化,其中,a為傳入的數據實例,k為一條數據流中實例的最大個數;2)類標號的條件概率P(X|ai)(i=1,2,…,k)可能發生變化;3)類標號的后驗概率P(ai|X)(i=1,2,…,k)可能發生變化。P(X|ai)的改變可能不會影響類標號的分布及數據源機制的產生,其被認為是虛擬概念漂移。P(ai|X)的改變是相同的實例在不同的時間戳下會存在不同的類標,其被認為是真實概念漂移。

現階段對概念漂移的種類還沒有達成統一的描述,除虛擬與真實概念漂移外,研究人員還根據概念漂移變化的速度,將概念漂移分為突變型、漸變型、重復型和增量型。突變漂移是指集群結構在短時間內發生巨大變化,類標號的分配與之前不同。漸變漂移是指概念的變化隨著時間的推移而逐漸發生,變化頻率低、幅度小。重復漂移是指當概念不規則或周期性重復出現時,就會出現重復漂移情況。增量漂移是指隨時間推移概念發生緩慢演變的過程,該過程與漸變漂移有些類似,變化窗口會對應整個流程?；谧兓俣鹊母拍钇品植碱愋腿鐖D2所示。

圖2 基于變化速度的概念漂移分布類型

2 概念漂移集成分類算法

在數據流傳輸中,單分類器在對概念漂移數據流分類時會有限制,不能達到預期效果。集成分類器將基分類器組合起來,具有比單分類器更好的性能?，F有算法大多只專注于一種類型的概念漂移,但是實際數據中可能會同時發生多種漂移,集成的出現可以解決此類問題,從而更好地檢測出概念漂移,迅速對其做出反應,達到理想的分類效果。

2.1 突變型和漸變型概念漂移集成分類算法

突變型和漸變型概念漂移是最容易發生的兩種情況。漸變比突變更具挑戰性,因為其變化小,且數據分布重疊。如果變化是周期性的,則之前的變化情況可能在一段時間后重新出現。

突變漂移檢測算法(Detect Abrupt Drift,DetectA)[18]是一種利用自身的主動性來檢測即將發生的突變漂移機制,其優勢在于主動性較好,不像大多數漂移檢測程序只能檢測概念漂移發生后的情況。文獻[19]提出漂移檢測法(Drift Detection Method,DDM),該方法在突變漂移時表現良好,但其很難發現漸變漂移。早期漂移檢測法(Early Drift Detection Method,EDDM)[20]與DDM相似,只是其分析了連續錯誤之間的距離,而不是錯誤率,該算法可以改善漸變漂移的檢測效果。文獻[21]基于DDM提出反應漂移檢測方法(Reactive Drift Detection Method,RDDM),通過添加一個顯式機制來丟棄較長概念的舊實例,以減輕DDM的性能損失。該方法旨在更早地檢測漂移,在預測精度上顯著優于DDM,更加適合突變和漸變漂移。文獻[22]提出一種由投票法、分類器組合和去除低質量分類器組成的集成分類器。在不同的數據輸入條件下使用兩個加權函數,可使其在決策階段對基分類器加權,有利于提高分類器對漂移的適應性,使分類器具有更高的效率,該算法在漸變漂移和組合漂移下具有較高的精度。

SEA[13]算法對數據分類時使用新生成的基分類器替換分類中性能最弱的基分類器。該算法在所有數據的基礎上構建一個決策樹,可快速調整以適應突變和漸變漂移。AWE[14]算法適用于時間演化環境,根據測試數據對分類精度的期望,對集成中的分類器進行合理加權,可以較好地適應突變漂移,具有一定的預測精度。研究人員在AWE算法基礎上提出了AUE[5]算法。該算法相比AWE算法不僅能選擇分類器,而且可根據當前分布對分類器更新,不限制基分類器大小,適用于突變和漸變漂移。重復概念漂移算法(Recurring Concept Drifts,RCD)[23]是一種處理突變和漸變概念漂移的數據流算法。該算法使用一個可配置的多元非參數統計測試對數據樣本進行比較,確定是否出現新概念或歷史概念,重用并存儲已有的分類器,用于數據樣本的構建。EBE[15]算法將信息熵與集成相結合用于檢測數據流中突變和漸變概念漂移,提高算法分類準確性。概念漂移和類不平衡在線主動學習配對集成算法(Online Active Learning Paired Ensemble for Concept Drift and Class Imbalance,OAL-DI)[24]由一個長期穩定的分類器和一個動態分類器組成,分別處理概念的突變和漸變。該算法對不同類別不平衡比的概念漂移能進行有效分類,并使用較少的真實標簽,以較低的標注成本獲得較高的AUC值。

適應性多元化在線提升算法(Adaptable Diversity-based Online Boosting,ADOB)[25]可以在分類器之間有效地分配實例,旨在加速分類器在概念漂移后的恢復,可以更好地適應概念漂移的發生,并且在突變和重復概念漂移的情況下特別有效。在對新實例進行分類時,ADOB分類器的誤差率計算為:

(1)

(2)

(3)

2.2 其他概念漂移集成分類算法

在概念漂移問題中,重復和增量漂移也時常發生。除了單類型的概念漂移情況,有時也會同時發生多類型漂移情況,使漂移類型變得更加復雜。

粗糙高斯樸素貝葉斯分類器(Rough Gaussian Naive Bayes Classifier,RGNBC)適用于重復型概念漂移[27]。該分類器通過自動檢測重復型概念漂移對數據流進行分類,實現概念漂移的檢測和分類模型的更新。樸素貝葉斯的動態特征空間集成算法(Dynamic Feature Space Ensemble of Naive Bayes,DFS-ENB)[28]對于概念重復情況可提高分類準確率。該算法在數據流動態特征空間的基礎上,通過存儲歷史模型及概念的相似性度量,從模型庫中獲取與當前概念高度相關的模型進行整合更新,動態計算集成中基分類器的權重,使之前傳入的數據實例得到更加有效的利用。在線順序極值學習機集成(Ensemble of Subset Online Sequential Extreme Learning Machine,ESOS-ELM)[29]是一種計算效率較高的在線順序極值學習機,利用循環概念先驗知識的高效存儲方案,適合重復漂移情況,并對突變和漸變漂移可以迅速做出反應。DCDD[16]模型具有較高的概念漂移檢測精度和較好的可擴展性以及較小的虛警率和漏報率,可以有效檢測突變、漸變與重復的概念漂移。在AUE算法的基礎上,研究人員提出精度更新集成算法(Accuracy Updated Ensemble,AUE2)[5],該算法引入一個新的加權函數,無需對候選分類器進行交叉驗證,不保留分類器緩沖區,始終更新其基分類器,適用于突變、漸變和重復漂移。

KME[4]結合了基于塊和在線集成的機制,可以對不同類型的概念漂移數據流進行分類?；诜至吭u價和權重機制,KME漂移檢測系統容易發現突變漂移,同時適用于增量型、漸變型和重復型漂移。該算法將數據流分為M個數據塊,對集成成員的訓練復雜度為O(Mlml),其中ml是在滑動窗口中標記的觀察數。在訓練階段的時間復雜度為O(2Mlml+2Mumu+2Mly+4Muy+Mm|ZV|+Mm),其中,m是集成大小,y是當前數據塊中保留的窗口數,|ZV|是驗證集中帶有標簽的實例數量。KME算法的內存使用量為O(mbvlc+mslb+mub+4y+m+c),其中,b是VFDT的屬性數,v是每個屬性的最大值數,l是樹中的葉子數,c是類數。SRE[17]算法將重采樣操作策略和定期更新操作策略相結合,共同處理數據流分類問題。在學習非平穩數據流有效性時,SRE可以對所有類型的漂移問題和新環境快速做出反應。wt,n(xj)是實例xj(xj∈Sj)被集成選中更新的第n(1

(4)

(5)

(6)

(7)

(8)

概念漂移集成決策樹算法(Ensemble Decision Trees for Concept-drifting,EDTC)[30]引入隨機特征選擇的3種變體實現分裂測試,并利用Hoeffding邊界的不等式中指定的兩個閾值區分概念漂移和噪聲數據。該算法能有效地解決概念漂移數據流在噪聲環境下的學習問題。Hoeffding邊界可定義為:

(9)

3 集成分類學習策略

集成分類器通過加權或非加權投票方法將多個基分類器決策進行組合,共同執行分類任務,可以使整體魯棒性更強,并且對概念漂移數據流進行有效分類。目前主流的集成學習算法是Bagging和Boosting,兩種算法可在不同訓練集上多次執行學習算法,并利用組合策略提升集成算法性能。

3.1 Bagging算法

Bagging根據均勻概率分布從數據集中重復抽樣。給定K個樣本的數據集,K次隨機采樣,訓練K個分類器后,測試樣本被指派到得票數最高的類中。樣本在K次采樣中不被采集的概率為(1-1/K)K,可得出初始訓練集樣本出現在采樣集中的概率為:

(10)

Bagging++[1]通過對Bagging算法的改進,利用輸入的數據塊來構建新模型學習C++。該集成分類器是包含4個基分類器的異構分類器,其算法速度顯著加快。Levbag[3]算法在此基礎上,做出以下改進:1)增加泊松分布中的多樣性值,從而增加分類器在同一實例上的訓練概率;2)改變預測實例的方式、增加多樣性及降低相關性,具有更好的精確度。處理漂移的多樣性算法(Diversity for Dealing with Drifts,DDD)[34]通過EDDM算法來檢測漂移前和漂移后的最佳集成,再使用4個具有高和低多樣性的基分類器,在不同多樣性水平的集成分類器中能夠獲得更好的分類準確性,具有更強的魯棒性。

概率閾值Bagging算法(Probability Threshold Bagging,PT-Bagging)[35]依賴于簡單的Bootstrap采樣,通過閾值移動分配類標簽。利用Bagging算法的優勢,在閾值確定的情況下可成功應用于多類數據,但只適用于靜態環境。GU[36]設計了Bagging分類樹-徑向基函數網絡(Bagging Classification Tree-Radial Basis Function Network,BAGCT-RBFN)。該算法可成功監測信息變量,具有更高的分類準確度及更好的分類性能?；诼摵线M化集成算法(Association-based Evolutionary Ensemble,AEE)[37]可以提高大規模數據集下變量選擇精度。該算法對數據流分類時迭代次數較少,改進了獲取變量組合的集成方法,達到預期的分類精度,節省了大量計算時間。

UnderBagging[38]算法通過對多數類樣本的隨機欠采樣創建了平衡的訓練子集。該算法使用內核化ELM作為基分類器使集成穩定并具有較好的泛化性能?；赨nderBagging的內核化極限學習機算法(Under Bagging Based Kernelized ELM,UBKELM)[39]可有效處理類不平衡問題并降低成本。文獻[40]提出基于SMOTE的決策樹集成和具有差異化采樣率的Bagging算法(Decision Tree Ensemble Based on SMOTE and Bagging with Differentiated Sampling Rates,DTE-SBD)。由于在不同的迭代次數中采用不同的采樣率,因此不同DT基分類器的訓練樣本數也不同,DTE-SBD可以增加DT基分類器的多樣性。Bagging C4.5[41]算法可以有效處理心電數據集,防止數據失真,支持醫療保健領域的臨床決策,與C4.5算法相比提高了預測分類精度。

3.2 Boosting算法

Boosting算法是一個迭代過程,用于自適應改變訓練樣本分布,使基分類器聚焦在較難分類的樣本上。Boosting替換加權數據后進行隨機抽樣,把若干分類器整合為一個分類器,用于提高學習算法的預測性能。與Bagging相比,Boosting可以訓練出更多樣化的分類器。

Boosting主要用于批處理模式,當需要隨機訪問數據時會受到限制,其要求整個分類訓練集同時可用。文獻[25]提出了ADOB算法,該算法在分類器之間可更有效地分配實例,旨在加速基分類器在概念漂移后的恢復,可以更好地適應概念漂移情況。但該算法在處理每個實例之前都要根據精度進行分類,影響了分類器的多樣性分布方式。BOLE[26]算法對ADOB和OzaBoost算法進行了改進,通過弱化基分類器投票的要求和改變內部使用的漂移檢測方法,提高整體精度。為適應概念漂移頻繁和突變的情況,該算法提出不同策略來提高在線提升算法的準確性和集成精度,在具有更多概念漂移的數據集中效果更明顯,精度增益更高。

多數在線提升算法(Online Boost-by-majority,Online BBM)[42]可以提高在線學習算法的準確性。該算法利用匹配下界,證明其在確定基分類器的數量和達到指定精度所需實例的復雜度方面具有較強的優勢。漸進子空間集成學習算法(Progressive Subspace Ensemble Learning,PSEL)[43]解決了隨機子空間技術的局限性。PSEL不僅適用于維數較高的數據集,而且適用于一類廣泛數據集,可以得到更準確、穩定、魯棒的分類結果。PSEL的時間復雜度TPSEL為:

TPSEL=TOE+TPSP

(11)

其中,TOE和TPSP分別表示原始集成生成和逐漸選擇過程的計算成本。

TOE=O(B·l·m·logam)

(12)

TPSP=O(G(B(l·m·logam))+BlogaB)

(13)

其中,l為訓練樣本數量,屬性數量m與分類器B的數量有關,G為迭代次數。因為G和B為常數,所以說明該算法的計算成本約為O(l·mlogam)。

AdaBoost[7]算法通過迭代過程對Boosting算法進行改進,將訓練集中的所有模式分配相同權重值。在此過程中,錯誤分類實例的權重值增加,而正確分類實例權重值減少。AdaBoost.M1[44]算法一旦發現錯誤大于50%的分類器,便會停止對給定的數據實例分類,其使用預定數量的基分類器處理整個數據流,再以新的數據塊更新,以便為加權投票組合提供有效的近似權重。投票提升集成算法[45]沒有AdaBoost的限制,可用于構建性能更加魯棒的集成分類器。對特定訓練實例的漸變關注取決于整體分類器的預測之間的不一致程度。與標準Boosting算法相比,該算法對類標簽中的噪聲檢測更準確且穩定。IBS算法[11]是一種基于Boosting的增量學習算法。該算法依賴于在每次獲得批處理時添加適當數量的基分類器,而不像大多數批處理增量算法只添加一個基分類器,是一種有效且計算成本低的數據流分類算法。

3.3 基分類器組合

將基分類器的預測結果進行組合可以提高分類器的整體性能,常見的組合策略有平均法、投票法等。如果數據是數值型,則常用算法是平均法。投票法是組合基本學習算法的簡單形式,通過對基分類器分配不同權重來選擇輸出結果的算法。集成結構影響投票結果,可以將投票分為排序投票、多數投票和加權投票等。其中多數投票法是假設每一個分類器對總體集成決策有相同的權重。加權投票法根據式(14)對分類器的預測進行加權。

(14)

其中,wi是ni的權重。

在加權投票中,最簡單的算法是按照分類器的準確性進行分類。AWE[14]算法是利用加權投票策略挖掘概念漂移數據流的算法,但AWE只能適應潛在的概念漂移并且準確率也有待進一步提高。SEA[13]算法利用與AWE不同的修剪策略進行分類。該算法用新的基分類器替換了性能最弱的分類器,但當數據集較小且無漂移情況時,精度不高。文獻[46]在AWE的基礎上提出CVFDT更新集成算法(CVFDT Update Ensemble,CUE)。CUE在基分類器的權值分配、算法對數據塊大小的敏感性和增加基分類器間相異度等方面進行改進,算法分類準確性高于AWE,對帶有概念漂移的數據流具有較好的分類準確率和快速反應能力。在算法AWE和CUE中,通過均方誤差來分配基分類器權重均方誤差計算如式(15)所示。

(15)

分類器隨機均方誤差計算如式(16)所示。

(16)

其中,p(y)為在最新傳入的數據塊An中每個類所占的比例。

CUE基分類權重計算如式(17)所示。為避免分母為0的情況發生,ε通常取一個很小的正數值。

(17)

該算法的更新代價為L·O(M),其中,L是需要更新的基分類器個數,M是數據流中的數據塊大小。該算法的分類代價為R·O(M),R為基分類器個數。

文獻[47]提出一種單分類器高效集成技術。該技術結合剔除不相關基分類器的集成剪枝算法和加權融合模塊,控制所選分類器對最終集成決策的影響,具有較低的計算復雜度。DE2是可以將基分類器從連續且非平穩的數據流中動態提取出的集成算法[10]。指數加權平均算法具有較好的學習性能和泛化能力,但該算法忽略了需要分類的查詢樣本周圍的本地信息。誤差和趨勢分集驅動的集成算法(Error and Trend Diversity Driven Ensemble,ETDDE)[48]利用投票思想能有效更新集成的組合和融合參數,可以提高分類精度和準確性?；谛畔㈧氐募煞诸愃惴?Ensemble Classification Algorithm Based on Information Entropy,ECBE)[49]利用分類前后熵值的變化來檢測概念漂移并決定基分類器的權重。權重低于預定閾值的分類器將被舍棄,從而獲得較高的分類精度。動態集成選擇算法(Dynamic Ensemble Selection,DES)[12]是一種動態加權算法。該算法在獲得DES系統的最終輸出時進行分類,可以較好地解決需要分類的數據實例被忽略的問題。

4 集成分類關鍵技術

在集成分類過程中,為達到理想的分類效果,會對基分類器使用多種關鍵技術,例如在線學習、基于塊的集成技術、增量學習等。

4.1 在線學習

在線學習是一種按照順序學習進行不斷修正的模型,可以對數據流分類做出快速反應。OAUE算法基于在線學習技術,可以在固定時間和內存中,只對最后實例的窗口估計分類器誤差。OAUE的訓練和加權時間復雜度為O(2m),m是被選定的分量數?？臻g復雜度為O(kavcl(k(d+c)),其中,a是屬性數,v是每個屬性的最大值數,c是類數,l是樹上的葉子數,k、d和c是常數。WAOAUE[9]算法在OAUE的基礎上進行改進。該算法利用變化檢測器提高OAUE的性能,在集成中加入一個變化檢測器來確定每個候選分類器的窗口大小,適用于實時環境下的大數據挖掘。

概念漂移檢測方法是一種在線學習方法,可以在數據流變化后改進基分類器,從而提高分類準確性。文獻[4]結合ACE和AUE兩種集成算法提出KME算法。KME算法結合了基于塊的集成和在線集成的機制,可以對不同類型的概念漂移數據流進行分類。DDM[19]算法利用在線學習技術,可應用于數據實例隨時間而變化的數據流。該算法提高了非平穩問題的建模算法學習能力,其應用方便,且計算效率高。RDDM[21]算法基于DDM算法,可定期重新計算由DDM負責統計的檢測預警和漂移水平,且使用較小數量的實例參數化處理DDM的靈敏度損失問題,具有更高的檢測精度。對概念變化的預期和動態適應算法(Anticipative and Dynamic Adaptation to Concept Change,ADACC)[50]也是一種在線學習算法。該算法使用新的二階學習機制對動態環境做出反應。在線Biterm主題模型(Online Biterm Topic Model,BTM)[51]可以改善數據稀疏性并降低數據維度,在概念漂移檢測和數據流分類中均具有較好的性能。Online BBM[42]利用在線損失最小化工具,推導出一種自適應的在線提升算法。該算法中的基分類器可以直接處理權重較高的實例,也可以對權重較低的實例拒絕采樣。

4.2 基于塊的集成

數據以塊的形式進行傳輸,其中每個塊包含固定數量的訓練實例。算法對每個塊中的實例進行多次迭代,并利用批處理算法來訓練基分類器。

AdaBoost.M1[44]將資源分配網絡與長期記憶相結合,該算法使用預定數量的基分類器處理整個數據流,并使用新的數據塊進行逐步更新,以便為加權投票組合提供有效的近似權重。AWE[14]算法在連續的數據塊上訓練基分類器,并利用最新的塊來評估所有基分類器,在最后的投票中選出多個最優的基分類器,達到較好的分類效果。逐漸重采樣集成算法(Gradual Resampling Ensemble,GRE)[52]采用選擇性重采樣機制,通過重用保留的歷史數據塊來平衡當前的類分布,具有較高的分類精度。該算法在當前塊中處理時間復雜度為O(|Pm| loga|Pm|+|Nm| loga|Nm|)。一個塊在該階段的時間復雜度為O(amlogaa),其中,a是訓練塊大小,m是數據流中塊的數量。如果一次處理所有數據項,則需要的時間復雜度為O(|S| loga|S|),其中|S|是數據流中實例的數量。

極限學習機(Extreme Learning Machine,ELM)被廣泛用于數據流集成分類問題,適合于實時反應數據。OS-ELM[2]是ELM的延伸之一,其可以通過具有固定或不同大小的塊增量學習數據,而不是批量學習,無需保留舊的訓練實例。在OS-ELM中,輸出層的更新規則權重矩陣β可表示為:

(18)

其中,Hm+1和Tm+1對應于第(k+1)個塊中的隱藏層輸出矩陣和新的目標矩陣,β(m)和β(m+1)在接收到第k個和第(k+1)個塊后,表示輸出層權重矩陣β。Pm+1可由式(19)得出:

(19)

其中,I為單位矩陣,Pm可以迭代更新,P0表示為:

(20)

MOS-ELM算法結合了OS-ELM和WELM算法,考慮到集成學習的穩健性,可以提升在線分類器在偏斜數據流中的分類性能。文獻[53]提出集成OS-ELM算法(Ensemble OS-ELM,EOS-ELM)和在線連續極端學習機的并行集成算法(Parallel Ensemble of Online Sequential Extreme Learning Machine,PEOS-ELM)。兩個算法的訓練精度和測試精度都優于OS-ELM,且訓練速度更快,可以準確有效地學習大規模數據。在ESOS-ELM[33]算法中,每個OS-ELM網絡都使用一個平衡的數據流子集進行訓練。該算法提出的框架包括表示短期記憶的主要集成,在平穩和非平穩環境下都能有效解決類不平衡問題。

4.3 增量學習

增量學習是指一個學習體系不斷地從新樣本數據中學習知識。增量學習技術適用于數據流中實例依次到達且能夠從新的數據中不斷學習的情況。

在集成分類算法中有很多算法應用了增量學習技術,除了Bagging++和LevBag算法采用增量學習技術外,還有在線順序極端學習機OS-ELM支持增量學習,其提供了一種分析增量數據的方法。IDS-ELM[54]是一種用于數據流分類的快速增量極值學習機算法。該算法將ELMS作為基分類器,自適應地確定隱層神經元的數目,并從一系列函數中隨機選取激活函數,以提高算法綜合性能。

EDTC[30]是一種基于集成決策樹的概念漂移數據流增量算法。與其他隨機決策樹不同,該算法提出了3種不同的隨機特征選擇方法來確定樹的增量生長中的切點,其是一種利用循環概念先驗知識的高效存儲方案,具有較高的分類預測精度。預測檢測流框架[6]是一種新的處理對抗性概念漂移的框架。該框架通過對概念進行預先考慮,在動態對抗性概念領域具有一定優勢。該框架作為一種有限內存的增量算法被用于處理不平衡和標記稀疏的數據流。IBS算法[11]能夠處理數據流環境中的分類任務。該算法隨著時間的推移對模型進行改進,根據當前準確度自動調整基分類器,并結合批量增量算法的特點,提高了模型靈活性及分類性能。

AUE[5]算法使用最近塊中的觀察值增量地更新歷史數據塊。該算法不限制基分類器的大小,不使用任何窗口。OAUE[8]是在AUE的基礎上提出的一種增量算法。該算法在每次觀測后對基分類器進行訓練和加權,基分類器的權重與恒定時間和內存中的誤差相關。AUE2[5]算法結合了塊集成算法中AWE算法和Hoeffding樹的增量特性,并對AUE算法進行了改進。目標是保留基分類器的簡單模式,并對基于塊的算法特征預測值進行加權。該算法不僅有較高的分類精度,還有較低的內存消耗。AWE、AUE和AUE2算法的均方誤差和隨機均方誤差可由式(15)、式(16)得出,但其基分類權重不同,如式(21)～式(23)所示。

(21)

(22)

(23)

其中,ε為大于0的常數。

5 下一步研究方向

雖然現有數據流集成分類算法大多可以有效地解決分類問題,但研究人員仍有一些問題亟待解決,例如集成基分類器的動態更新、集成基分類器的加權組合、多類型概念漂移的快速檢測以及復雜數據流類型的靈活處理等。筆者將對這些問題進行分析并作為本文下一步的主要研究方向。

1)集成基分類器的動態更新

在現實生活中,需要結合實際情況選擇合適的算法和數據預處理方式,從而達到較好的分類效果。在處理數據流時,現今主流方法是集成分類。雖然集成分類算法在處理數據流分類問題時被廣泛應用,但是仍然有很多問題尚待解決。如何在集成分類算法中實現對基分類器的動態更新已成為專家們十分關注的問題。隨著新數據實例的傳入,集成中分類性能較弱的基分類器將由新數據實例訓練出的基分類器替換,但是對于界定集成中基分類器準確性的邊界值還沒有得到專家們的一致確定。因此,本文將把獲得一個理想的分類錯誤邊界值作為研究重點,利用此錯誤邊界值將集成中性能較差的基分類器自動淘汰,并且加入新的基分類器實現集成的動態更新。

2)集成基分類器的加權組合

現有的集成分類器大多是以空間換時間,在對數據流分類時雖然在時間效率上得到了提升,但存在較高的內存消耗。通過合理組合多種算法,可以正確預測難以分類實例的類標簽,從而減少計算的操作次數和運行的內存空間。其主要難點是如何對基分類器添加合適的加權策略,使基分類器可以更加合理地組合,從而提高分類器的整體性能。在下一步的研究中,筆者擬利用加權投票方法和Boosting策略對基分類器權重進行重新加權,使得構建的集成分類器具有較高的分類精度與計算效率,以及較低的內存消耗。

3)多類型概念漂移的快速檢測

隨著科技的發展,數據量呈爆炸式增長,產生了大量的數據。海量數據蘊含較多有益信息的同時,也使數據流類型變得更加復雜。數據流在傳輸過程中可能會同時產生多種漂移類型,例如突變與增量、全部漂移類型同時出現等更加復雜的情況。目前的技術仍有很多限制,研究人員依然有很多問題亟需解決,例如需進一步研究可以直接處理概念漂移問題的特征和實例選擇方法[55]。在對概念漂移的集成算法進行整理時,發現同時針對全部漂移問題的算法幾乎不存在,且算法會受到數據類別的限制。在下一步的研究中,筆者擬設計一個集成分類算法,使其既可以針對所有類型的概念漂移,又可以快速檢測概念漂移。

4)復雜數據流類型的靈活處理

在數據流傳輸過程中需解決概念漂移、復雜數據流類型等問題。復雜的數據流類型包括類不平衡、維度高、錯誤分類成本高及數據延遲等。數據通常展現出高維問題和類不平衡的雙重特點[56]。一般把數據流中類的不平衡問題稱為數據集不平衡問題,其體現在樣本的數量差異較大[57]。在復雜的數據流中,每一種類型都引起了研究人員的廣泛關注。在下一步的研究中,筆者擬設計一個高性能算法及用于測試流的算法框架,使其對復雜動態的數據流類型可以做出快速反應并加以處理。

6 結束語

本文介紹突變型、漸變型、重復型和增量型概念漂移,闡述國內外概念漂移集成分類算法的研究現狀,同時分析Bagging、Boosting、基分類器組合、在線學習、基于塊的集成和增量學習等關鍵策略與技術。下一步將針對集成基分類器的動態更新與加權組合、多類型概念漂移的快速檢測以及復雜數據流類型的靈活處理展開研究,設計新的集成分類算法以應對日益復雜的數據流環境。