杜詩(shī)語(yǔ),韓 萌,申明堯,張春硯,孫 蕊

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

0 概述

在信息時(shí)代,人們每時(shí)每刻都在產(chǎn)生海量數(shù)據(jù),例如社交網(wǎng)絡(luò)、交通流量和各種傳感器等。數(shù)據(jù)通常以流的形式出現(xiàn),數(shù)據(jù)流是隨時(shí)間推移到達(dá)的潛在無(wú)界且有序的實(shí)例序列。數(shù)據(jù)流挖掘是大數(shù)據(jù)時(shí)代最重要的研究領(lǐng)域之一,其目標(biāo)是從連續(xù)的數(shù)據(jù)流中提取出隱藏的信息。

數(shù)據(jù)流分為靜態(tài)數(shù)據(jù)流和動(dòng)態(tài)數(shù)據(jù)流(概念漂移數(shù)據(jù)流)。靜態(tài)中的實(shí)例雖然以未知的概率分布,但以固定的來(lái)源出現(xiàn)。動(dòng)態(tài)目標(biāo)概念(實(shí)例類)或?qū)傩苑植茧S時(shí)間演變,即概念漂移。概念漂移反映在傳入的實(shí)例中,其降低了從歷史訓(xùn)練實(shí)例中得到分類器的準(zhǔn)確性。概念漂移問(wèn)題是一個(gè)急需解決的問(wèn)題,如分類器不能及時(shí)獲取新知識(shí)且不能較好保存歷史數(shù)據(jù)等。在現(xiàn)實(shí)生活中受概念漂移影響的實(shí)例有很多,如交通監(jiān)控、金融詐騙檢測(cè)、天氣預(yù)報(bào)和醫(yī)療決策輔助等。

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

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

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

1 概念漂移

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

隨著數(shù)據(jù)實(shí)例的引入,集群的結(jié)構(gòu)會(huì)發(fā)生變化,導(dǎo)致集群中表示的概念發(fā)生變化,這種概念變化稱為概念漂移。研究人員對(duì)概念漂移的深入理解是通過(guò)分析概念漂移的種類及產(chǎn)生原因逐步得到的。實(shí)際問(wèn)題中會(huì)出現(xiàn)不同類型的概念漂移,例如在社會(huì)網(wǎng)絡(luò)分析中,一個(gè)社會(huì)群體中的人在某一特定時(shí)期對(duì)某一特定事物感興趣。興趣的突然改變或逐漸改變,對(duì)人類來(lái)說(shuō)是顯而易見(jiàn)的。研究人員把這種情況的漂移稱為真實(shí)概念漂移,認(rèn)為漂移不僅因?yàn)樗幁h(huán)境發(fā)生變化導(dǎo)致,而且因?yàn)閿?shù)據(jù)流的概率分布模型發(fā)生變化,并把后者的漂移稱為虛擬概念漂移。真實(shí)概念漂移會(huì)改變類間的決策邊界,而虛擬概念漂移會(huì)影響類間的比例,這與類間的不平衡問(wèn)題有關(guān),真實(shí)概念漂移與虛擬概念漂移分布類型如圖1所示。

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

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

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

現(xiàn)階段對(duì)概念漂移的種類還沒(méi)有達(dá)成統(tǒng)一的描述,除虛擬與真實(shí)概念漂移外,研究人員還根據(jù)概念漂移變化的速度,將概念漂移分為突變型、漸變型、重復(fù)型和增量型。突變漂移是指集群結(jié)構(gòu)在短時(shí)間內(nèi)發(fā)生巨大變化,類標(biāo)號(hào)的分配與之前不同。漸變漂移是指概念的變化隨著時(shí)間的推移而逐漸發(fā)生,變化頻率低、幅度小。重復(fù)漂移是指當(dāng)概念不規(guī)則或周期性重復(fù)出現(xiàn)時(shí),就會(huì)出現(xiàn)重復(fù)漂移情況。增量漂移是指隨時(shí)間推移概念發(fā)生緩慢演變的過(guò)程,該過(guò)程與漸變漂移有些類似,變化窗口會(huì)對(duì)應(yīng)整個(gè)流程?；谧兓俣鹊母拍钇品植碱愋腿鐖D2所示。

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

2 概念漂移集成分類算法

在數(shù)據(jù)流傳輸中,單分類器在對(duì)概念漂移數(shù)據(jù)流分類時(shí)會(huì)有限制,不能達(dá)到預(yù)期效果。集成分類器將基分類器組合起來(lái),具有比單分類器更好的性能?，F(xiàn)有算法大多只專注于一種類型的概念漂移,但是實(shí)際數(shù)據(jù)中可能會(huì)同時(shí)發(fā)生多種漂移,集成的出現(xiàn)可以解決此類問(wèn)題,從而更好地檢測(cè)出概念漂移,迅速對(duì)其做出反應(yīng),達(dá)到理想的分類效果。

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

突變型和漸變型概念漂移是最容易發(fā)生的兩種情況。漸變比突變更具挑戰(zhàn)性,因?yàn)槠渥兓?且數(shù)據(jù)分布重疊。如果變化是周期性的,則之前的變化情況可能在一段時(shí)間后重新出現(xiàn)。

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

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

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

(1)

(2)

(3)

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

在概念漂移問(wèn)題中,重復(fù)和增量漂移也時(shí)常發(fā)生。除了單類型的概念漂移情況,有時(shí)也會(huì)同時(shí)發(fā)生多類型漂移情況,使漂移類型變得更加復(fù)雜。

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

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

(4)

(5)

(6)

(7)

(8)

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

(9)

3 集成分類學(xué)習(xí)策略

集成分類器通過(guò)加權(quán)或非加權(quán)投票方法將多個(gè)基分類器決策進(jìn)行組合,共同執(zhí)行分類任務(wù),可以使整體魯棒性更強(qiáng),并且對(duì)概念漂移數(shù)據(jù)流進(jìn)行有效分類。目前主流的集成學(xué)習(xí)算法是Bagging和Boosting,兩種算法可在不同訓(xùn)練集上多次執(zhí)行學(xué)習(xí)算法,并利用組合策略提升集成算法性能。

3.1 Bagging算法

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

(10)

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

概率閾值Bagging算法(Probability Threshold Bagging,PT-Bagging)[35]依賴于簡(jiǎn)單的Bootstrap采樣,通過(guò)閾值移動(dòng)分配類標(biāo)簽。利用Bagging算法的優(yōu)勢(shì),在閾值確定的情況下可成功應(yīng)用于多類數(shù)據(jù),但只適用于靜態(tài)環(huán)境。GU[36]設(shè)計(jì)了Bagging分類樹(shù)-徑向基函數(shù)網(wǎng)絡(luò)(Bagging Classification Tree-Radial Basis Function Network,BAGCT-RBFN)。該算法可成功監(jiān)測(cè)信息變量,具有更高的分類準(zhǔn)確度及更好的分類性能?；诼?lián)合進(jìn)化集成算法(Association-based Evolutionary Ensemble,AEE)[37]可以提高大規(guī)模數(shù)據(jù)集下變量選擇精度。該算法對(duì)數(shù)據(jù)流分類時(shí)迭代次數(shù)較少,改進(jìn)了獲取變量組合的集成方法,達(dá)到預(yù)期的分類精度,節(jié)省了大量計(jì)算時(shí)間。

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

3.2 Boosting算法

Boosting算法是一個(gè)迭代過(guò)程,用于自適應(yīng)改變訓(xùn)練樣本分布,使基分類器聚焦在較難分類的樣本上。Boosting替換加權(quán)數(shù)據(jù)后進(jìn)行隨機(jī)抽樣,把若干分類器整合為一個(gè)分類器,用于提高學(xué)習(xí)算法的預(yù)測(cè)性能。與Bagging相比,Boosting可以訓(xùn)練出更多樣化的分類器。

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

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

TPSEL=TOE+TPSP

(11)

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

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

(12)

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

(13)

其中,l為訓(xùn)練樣本數(shù)量,屬性數(shù)量m與分類器B的數(shù)量有關(guān),G為迭代次數(shù)。因?yàn)镚和B為常數(shù),所以說(shuō)明該算法的計(jì)算成本約為O(l·mlogam)。

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

3.3 基分類器組合

將基分類器的預(yù)測(cè)結(jié)果進(jìn)行組合可以提高分類器的整體性能,常見(jiàn)的組合策略有平均法、投票法等。如果數(shù)據(jù)是數(shù)值型,則常用算法是平均法。投票法是組合基本學(xué)習(xí)算法的簡(jiǎn)單形式,通過(guò)對(duì)基分類器分配不同權(quán)重來(lái)選擇輸出結(jié)果的算法。集成結(jié)構(gòu)影響投票結(jié)果,可以將投票分為排序投票、多數(shù)投票和加權(quán)投票等。其中多數(shù)投票法是假設(shè)每一個(gè)分類器對(duì)總體集成決策有相同的權(quán)重。加權(quán)投票法根據(jù)式(14)對(duì)分類器的預(yù)測(cè)進(jìn)行加權(quán)。

(14)

其中,wi是ni的權(quán)重。

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

(15)

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

(16)

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

CUE基分類權(quán)重計(jì)算如式(17)所示。為避免分母為0的情況發(fā)生,ε通常取一個(gè)很小的正數(shù)值。

(17)

該算法的更新代價(jià)為L(zhǎng)·O(M),其中,L是需要更新的基分類器個(gè)數(shù),M是數(shù)據(jù)流中的數(shù)據(jù)塊大小。該算法的分類代價(jià)為R·O(M),R為基分類器個(gè)數(shù)。

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

4 集成分類關(guān)鍵技術(shù)

在集成分類過(guò)程中,為達(dá)到理想的分類效果,會(huì)對(duì)基分類器使用多種關(guān)鍵技術(shù),例如在線學(xué)習(xí)、基于塊的集成技術(shù)、增量學(xué)習(xí)等。

4.1 在線學(xué)習(xí)

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

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

4.2 基于塊的集成

數(shù)據(jù)以塊的形式進(jìn)行傳輸,其中每個(gè)塊包含固定數(shù)量的訓(xùn)練實(shí)例。算法對(duì)每個(gè)塊中的實(shí)例進(jìn)行多次迭代,并利用批處理算法來(lái)訓(xùn)練基分類器。

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

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

(18)

其中,Hm+1和Tm+1對(duì)應(yīng)于第(k+1)個(gè)塊中的隱藏層輸出矩陣和新的目標(biāo)矩陣,β(m)和β(m+1)在接收到第k個(gè)和第(k+1)個(gè)塊后,表示輸出層權(quán)重矩陣β。Pm+1可由式(19)得出:

(19)

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

(20)

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

4.3 增量學(xué)習(xí)

增量學(xué)習(xí)是指一個(gè)學(xué)習(xí)體系不斷地從新樣本數(shù)據(jù)中學(xué)習(xí)知識(shí)。增量學(xué)習(xí)技術(shù)適用于數(shù)據(jù)流中實(shí)例依次到達(dá)且能夠從新的數(shù)據(jù)中不斷學(xué)習(xí)的情況。

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

EDTC[30]是一種基于集成決策樹(shù)的概念漂移數(shù)據(jù)流增量算法。與其他隨機(jī)決策樹(shù)不同,該算法提出了3種不同的隨機(jī)特征選擇方法來(lái)確定樹(shù)的增量生長(zhǎng)中的切點(diǎn),其是一種利用循環(huán)概念先驗(yàn)知識(shí)的高效存儲(chǔ)方案,具有較高的分類預(yù)測(cè)精度。預(yù)測(cè)檢測(cè)流框架[6]是一種新的處理對(duì)抗性概念漂移的框架。該框架通過(guò)對(duì)概念進(jìn)行預(yù)先考慮,在動(dòng)態(tài)對(duì)抗性概念領(lǐng)域具有一定優(yōu)勢(shì)。該框架作為一種有限內(nèi)存的增量算法被用于處理不平衡和標(biāo)記稀疏的數(shù)據(jù)流。IBS算法[11]能夠處理數(shù)據(jù)流環(huán)境中的分類任務(wù)。該算法隨著時(shí)間的推移對(duì)模型進(jìn)行改進(jìn),根據(jù)當(dāng)前準(zhǔn)確度自動(dòng)調(diào)整基分類器,并結(jié)合批量增量算法的特點(diǎn),提高了模型靈活性及分類性能。

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

(21)

(22)

(23)

其中,ε為大于0的常數(shù)。

5 下一步研究方向

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

1)集成基分類器的動(dòng)態(tài)更新

在現(xiàn)實(shí)生活中,需要結(jié)合實(shí)際情況選擇合適的算法和數(shù)據(jù)預(yù)處理方式,從而達(dá)到較好的分類效果。在處理數(shù)據(jù)流時(shí),現(xiàn)今主流方法是集成分類。雖然集成分類算法在處理數(shù)據(jù)流分類問(wèn)題時(shí)被廣泛應(yīng)用,但是仍然有很多問(wèn)題尚待解決。如何在集成分類算法中實(shí)現(xiàn)對(duì)基分類器的動(dòng)態(tài)更新已成為專家們十分關(guān)注的問(wèn)題。隨著新數(shù)據(jù)實(shí)例的傳入,集成中分類性能較弱的基分類器將由新數(shù)據(jù)實(shí)例訓(xùn)練出的基分類器替換,但是對(duì)于界定集成中基分類器準(zhǔn)確性的邊界值還沒(méi)有得到專家們的一致確定。因此,本文將把獲得一個(gè)理想的分類錯(cuò)誤邊界值作為研究重點(diǎn),利用此錯(cuò)誤邊界值將集成中性能較差的基分類器自動(dòng)淘汰,并且加入新的基分類器實(shí)現(xiàn)集成的動(dòng)態(tài)更新。

2)集成基分類器的加權(quán)組合

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

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

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

4)復(fù)雜數(shù)據(jù)流類型的靈活處理

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

6 結(jié)束語(yǔ)

本文介紹突變型、漸變型、重復(fù)型和增量型概念漂移,闡述國(guó)內(nèi)外概念漂移集成分類算法的研究現(xiàn)狀,同時(shí)分析Bagging、Boosting、基分類器組合、在線學(xué)習(xí)、基于塊的集成和增量學(xué)習(xí)等關(guān)鍵策略與技術(shù)。下一步將針對(duì)集成基分類器的動(dòng)態(tài)更新與加權(quán)組合、多類型概念漂移的快速檢測(cè)以及復(fù)雜數(shù)據(jù)流類型的靈活處理展開(kāi)研究,設(shè)計(jì)新的集成分類算法以應(yīng)對(duì)日益復(fù)雜的數(shù)據(jù)流環(huán)境。