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

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

0 引 言

近年來(lái)，隨著技術(shù)的快速發(fā)展，互聯(lián)網(wǎng)每天都會(huì)產(chǎn)生海量的數(shù)據(jù)，如超市交易、互聯(lián)網(wǎng)搜索請(qǐng)求、電話記錄、衛(wèi)星數(shù)據(jù)和天文學(xué)等。數(shù)據(jù)流的出現(xiàn)改變了人們存儲(chǔ)、通信和處理數(shù)據(jù)的方式。與傳統(tǒng)的數(shù)據(jù)集相比，數(shù)據(jù)流呈現(xiàn)出連續(xù)、高容量、開(kāi)放式和概念漂移的新特征[1]。在數(shù)據(jù)流中，數(shù)據(jù)到達(dá)的速度遠(yuǎn)快于傳統(tǒng)算法中多遍掃描和重復(fù)分析的速度，因此傳統(tǒng)算法無(wú)法有效處理數(shù)據(jù)流。目前，數(shù)據(jù)流模型已廣泛應(yīng)用于生活中的各個(gè)領(lǐng)域，逐漸成為數(shù)據(jù)傳輸?shù)闹髁髭厔?shì)。決策樹(shù)算法作為數(shù)據(jù)流分類(lèi)最有效的方法之一，具有速度快、實(shí)用、易于理解、容易提取規(guī)則等優(yōu)點(diǎn)[2]，在醫(yī)療診斷、天氣預(yù)報(bào)、行為分析和網(wǎng)絡(luò)安全等領(lǐng)域發(fā)揮出越來(lái)越重要的作用。

數(shù)據(jù)流決策樹(shù)分類(lèi)算法按照分類(lèi)模型可分為決策樹(shù)單分類(lèi)算法和決策樹(shù)集成分類(lèi)算法。相較于單分類(lèi)算法，決策樹(shù)集成分類(lèi)算法具有更好的時(shí)空效率和更高的準(zhǔn)確性，因此被廣泛應(yīng)用于各種分類(lèi)任務(wù)。其中，隨機(jī)決策樹(shù)(Random Decision Tree, RDT)[3]和隨機(jī)森林(Random Forest, RF)[4]是經(jīng)典的兩個(gè)算法，后續(xù)出現(xiàn)的大部分算法都是基于它們實(shí)現(xiàn)的。例如，數(shù)據(jù)流的半隨機(jī)多決策樹(shù)算法(Semi-Random Multiple decision Trees for Data Streams, SRMTDS)[5]、多個(gè)半隨機(jī)決策樹(shù)算法(Multiple SemiRandom Decision Trees, MSRT)[6]、隨機(jī)普通集成算法(Random Ordinality Ensembles, ROE)[7]、基于聚類(lèi)的分類(lèi)器選擇算法(Classifier Selection Based on Clustering, CSBC)[8]和在線隨機(jī)森林算法(Online Random Forest, ORF)[9]等。此外，用于概念漂移檢測(cè)和處理的決策樹(shù)集成算法有基于隨機(jī)決策樹(shù)的概念漂移檢測(cè)算法(Concept Drifting Detection Based on Random Ensembling Decision Tree, CDRDT)[10]、不確定處理概念漂移快速?zèng)Q策樹(shù)算法(Uncertainty-handling Concept-adapting Very Fast Decision Tree, UCVFDT)[11]、基于概念漂移數(shù)據(jù)流的集成決策樹(shù)算法(Ensemble Random Decision Trees for Concept-drifting Data Streams, EDTC)[12]、隨機(jī)決策樹(shù)算法(Random Decision Tree, RDT)和霍夫丁選項(xiàng)樹(shù)算法(Hoeffding Option Tree, HOT)[13]等。

本文的主要貢獻(xiàn)如下：(1) 分別從Bagging、Boosting和Stacking三種集成學(xué)習(xí)框架的角度對(duì)決策樹(shù)集成分類(lèi)算法進(jìn)行了詳細(xì)的分類(lèi)和總結(jié)。(2) 對(duì)數(shù)據(jù)流中存在的概念漂移問(wèn)題及其處理方法進(jìn)行了分析和總結(jié)。(3) 從多角度對(duì)文章中所提及的算法進(jìn)行分析，有助于研究者們根據(jù)算法的優(yōu)缺點(diǎn)選擇合適的算法進(jìn)行下一步研究工作。

1 集成學(xué)習(xí)框架

集成學(xué)習(xí)的思路是通過(guò)合并多個(gè)模型來(lái)提升機(jī)器學(xué)習(xí)性能，這種方法相較于單個(gè)模型通常能夠獲得更好的預(yù)測(cè)結(jié)果。集成方法是目前最有前途的研究方向之一[14]，已經(jīng)被證明是提高預(yù)測(cè)精度或者可以將復(fù)雜、困難的學(xué)習(xí)問(wèn)題分解為更簡(jiǎn)單、容易的子問(wèn)題的有效方法[15]。其目標(biāo)為將不同的分類(lèi)器組成一個(gè)元分類(lèi)器，與單分類(lèi)器相比，元分類(lèi)器具有更好的泛化性能。集成分類(lèi)器的大致圖解如圖1所示。

圖1 集成分類(lèi)器圖解

一般來(lái)說(shuō)，集成學(xué)習(xí)框架主要分為三大類(lèi)，分別為用于減少方差的Bagging、用于減少偏差的Boosting和用于提升預(yù)測(cè)結(jié)果的Stacking。

1.1 Bagging

Bagging是一種簡(jiǎn)單而有效的方法，用于生成獨(dú)立模型的集合，其中使用從原始數(shù)據(jù)集中取得的實(shí)例樣本來(lái)訓(xùn)練每個(gè)誘導(dǎo)器[16]。它從訓(xùn)練集中進(jìn)行子抽樣組成每個(gè)基模型所需要的子訓(xùn)練集，對(duì)所有基模型預(yù)測(cè)的結(jié)果進(jìn)行綜合產(chǎn)生最終的預(yù)測(cè)結(jié)果。算法具體過(guò)程如圖2所示。

圖2 Bagging算法圖解

(1)

國(guó)內(nèi)外的研究者們已對(duì)基于Bagging集成學(xué)習(xí)框架的決策樹(shù)分類(lèi)算法進(jìn)行了相關(guān)研究，開(kāi)發(fā)并更新了大量的算法模型，以滿足人們的需求。Fan等[3]提出了一種隨機(jī)決策樹(shù)(RDT)算法，該算法只需掃描一次訓(xùn)練數(shù)據(jù)，以更新多個(gè)隨機(jī)樹(shù)中的統(tǒng)計(jì)數(shù)據(jù)，且所構(gòu)造樹(shù)的結(jié)構(gòu)完全獨(dú)立于訓(xùn)練數(shù)據(jù)。結(jié)果表明，隨機(jī)樹(shù)算法的存儲(chǔ)器需求明顯少于學(xué)習(xí)單個(gè)最佳樹(shù)，即使非常大的訓(xùn)練數(shù)據(jù)也可能完全保存在主存儲(chǔ)器中。此外，基于Breiman提出的隨機(jī)森林算法[18]，Abdulsalam等[19]提出了一種擴(kuò)展的在線流隨機(jī)森林算法，使用節(jié)點(diǎn)窗口和樹(shù)窗口來(lái)決定何時(shí)構(gòu)建新樹(shù)、轉(zhuǎn)換邊界節(jié)點(diǎn)或執(zhí)行有限形式的修剪。同時(shí)，Hu等[5]設(shè)計(jì)了一種用于數(shù)據(jù)流的半隨機(jī)多決策樹(shù)增量(Semi-Random Multiple decision Trees for Data Streams, SRMTDS)算法，其在葉片處引入樸素貝葉斯分類(lèi)器，提高了樹(shù)的預(yù)測(cè)精度。在此基礎(chǔ)上，Li等[6]提出了一種基于半隨機(jī)多決策樹(shù)的MSRT概念漂移數(shù)據(jù)流算法。與SRMTDS算法相反，它首先生成不同類(lèi)型節(jié)點(diǎn)對(duì)應(yīng)的備選子樹(shù)，然后利用Hoeffding界的不等式，使用兩個(gè)閾值來(lái)區(qū)分真正的概念漂移和噪聲。但是，由于在構(gòu)建原始樹(shù)時(shí)需要準(zhǔn)備額外的子樹(shù)，因此對(duì)空間和運(yùn)行時(shí)開(kāi)銷(xiāo)的要求更高。Oza等[20]引入了在線套袋，它提出了標(biāo)準(zhǔn)套袋的限制，要求提供預(yù)先提供的整套訓(xùn)練套件用于學(xué)習(xí)。假設(shè)在線學(xué)習(xí)中，每個(gè)新的傳入實(shí)例可以在每個(gè)基類(lèi)分類(lèi)器的更新過(guò)程中被復(fù)制零次、一次或多次。Lee等[21]進(jìn)一步發(fā)展了這種方法的理論基礎(chǔ)，提出了一個(gè)貝葉斯在線Bagging，相當(dāng)于批量貝葉斯版本，與無(wú)損學(xué)習(xí)算法相結(jié)合，獲得了無(wú)損的在線裝袋方法。Bifet等介紹了Oza算法的兩種修改，稱(chēng)為自適應(yīng)大小Hoeffding樹(shù)(Adaptive-Size Hoeffding Tree, ASHT)[22]和Leveraging Bagging[23]，旨在為基類(lèi)分類(lèi)的輸入和輸出增加更多隨機(jī)化?；舴蚨∵x項(xiàng)樹(shù)(Hoeffding Option Trees, HOT)[24]可以看作是Kirkby選項(xiàng)樹(shù)的擴(kuò)展。它允許每個(gè)訓(xùn)練示例更新一組選項(xiàng)節(jié)點(diǎn)而不僅僅是一個(gè)單獨(dú)的葉子。它提供了一個(gè)緊湊的結(jié)構(gòu)，就像一組加權(quán)分類(lèi)器一樣。和常規(guī)的Hoeffding樹(shù)相似，它們是以增量方式構(gòu)建的。Gama等[25]提出了一種超快速樹(shù)木森林(Ultra Fast Forest of Trees, UFFT)算法，使用Hoeffding樹(shù)的集合進(jìn)行在線學(xué)習(xí)。它們的拆分標(biāo)準(zhǔn)僅適用于二元分類(lèi)任務(wù)。為了處理多類(lèi)問(wèn)題，應(yīng)用二進(jìn)制分解，為每個(gè)可能的類(lèi)對(duì)構(gòu)造二叉樹(shù)。當(dāng)新實(shí)例到達(dá)時(shí)，只有當(dāng)二進(jìn)制基類(lèi)分類(lèi)器使用此實(shí)例的真實(shí)類(lèi)標(biāo)簽時(shí)，才會(huì)更新每個(gè)分類(lèi)器[26]。裝袋算法的另一種變型是改進(jìn)的裝袋算法(Improved Bagging Algorithm, IBA)[27]。IBA通過(guò)用信息熵標(biāo)記每個(gè)樣本來(lái)改進(jìn)重采樣過(guò)程。Bagging++[28]是通過(guò)利用Bagging從傳入的數(shù)據(jù)塊構(gòu)建新模型而設(shè)計(jì)的，作為對(duì)Learn++的優(yōu)化。

1.2 Boosting

Boosting指的是通過(guò)算法集合將弱學(xué)習(xí)器轉(zhuǎn)換為強(qiáng)學(xué)習(xí)器，其主要原則是訓(xùn)練一系列的弱學(xué)習(xí)器。所謂弱學(xué)習(xí)器是指僅比隨機(jī)猜測(cè)好一點(diǎn)點(diǎn)的模型，例如較小的決策樹(shù)，訓(xùn)練的方式是利用加權(quán)的數(shù)據(jù)，在訓(xùn)練的早期對(duì)于錯(cuò)分?jǐn)?shù)據(jù)給予較大的權(quán)重。Boosting是一個(gè)迭代的過(guò)程，每次在新分類(lèi)器中強(qiáng)調(diào)上一個(gè)分類(lèi)器中被錯(cuò)誤分類(lèi)的樣本(增加錯(cuò)誤分類(lèi)樣本的權(quán)重)，最后將這些模型組合起來(lái)的方法。每次對(duì)正確分類(lèi)的樣本降權(quán)，對(duì)錯(cuò)誤分類(lèi)的樣本加權(quán)，最后分類(lèi)器是多個(gè)弱分類(lèi)器的加權(quán)組合。算法具體過(guò)程如圖3所示。Boosting不是像Bagging那樣重新采樣訓(xùn)練數(shù)據(jù)集，而是調(diào)整訓(xùn)練數(shù)據(jù)集的分布[29]。

圖3 Boosting算法圖解

Boosting方法大多采用加性模型來(lái)組合弱學(xué)習(xí)器，即可以將集成的學(xué)習(xí)器表示為如下形式[30]：

(2)

式中：hm表示第m個(gè)基學(xué)習(xí)器；βm表示第m個(gè)基學(xué)習(xí)器的系數(shù)；am表示第m個(gè)基學(xué)習(xí)器的參數(shù)；M表示基學(xué)習(xí)器的個(gè)數(shù)。對(duì)于Boosting樹(shù)方法，由于基學(xué)習(xí)器的系數(shù)βm為1，可將加性模型簡(jiǎn)寫(xiě)為：

(3)

在給定損失函數(shù)L及訓(xùn)練數(shù)據(jù)的條件下，學(xué)習(xí)加性模型就是一個(gè)搜尋參數(shù)使得損失函數(shù)極小化的過(guò)程，即：

(4)

此時(shí)，直接求解這個(gè)極小值是個(gè)很復(fù)雜的優(yōu)化問(wèn)題，采用前向分步算法來(lái)簡(jiǎn)化這一問(wèn)題。前向分步算法本質(zhì)上是一種貪心算法，它通過(guò)每一步只學(xué)習(xí)一個(gè)基函數(shù)及其系數(shù)，逐步逼近優(yōu)化目標(biāo)來(lái)簡(jiǎn)化復(fù)雜度。

首先，重寫(xiě)一下加性模型的表達(dá)形式，共生成M個(gè)基分類(lèi)器，當(dāng)前迭代次數(shù)為m，即在第m個(gè)循環(huán)中，Boosting樹(shù)的加性模型可以寫(xiě)為：

Hm(x)=Hm-1(x)+hm(x;am)

(5)

前向分步算法只要求在第m輪時(shí)，優(yōu)化當(dāng)前輪次的基學(xué)習(xí)器的參數(shù)，使得損失函數(shù)最小以簡(jiǎn)化算法，即：

(6)

這里優(yōu)化當(dāng)前輪次的基學(xué)習(xí)器的參數(shù)，在經(jīng)典的GBDT[31]算法中，采取的是非常暴力的遍歷的方式，即在每個(gè)節(jié)點(diǎn)劃分的時(shí)候，遍歷所有屬性和可能的節(jié)點(diǎn)劃分?jǐn)?shù)值，在當(dāng)前指定的損失函數(shù)下使損失達(dá)到最小。

當(dāng)采用平方損失函數(shù)，即：

L(y,Hm)=(y-Hm)2

(7)

得到：

L(y,Hm-1(x)+hm(x;am))=

[y-Hm-1(x)-hm(x;am)]2=

[r-hm(x;am)]2

(8)

式中：r=y-Hm-1(x)即上一輪基學(xué)習(xí)器訓(xùn)練完成以后，m-1個(gè)基學(xué)習(xí)器與標(biāo)簽的殘差。所以，對(duì)于回歸問(wèn)題的Boosting樹(shù)而言，每一步只需要擬合當(dāng)前模型的殘差即可。

在應(yīng)用Boosting進(jìn)行分類(lèi)的決策樹(shù)集成算法中，最經(jīng)典的算法便是梯度提升決策樹(shù)算法(Gradient Boosting Decision Tree, GBDT)[31]。它是建立在一堆回歸決策樹(shù)之上的集合模型，具有眾所周知的泛化能力。作為基于迭代積累的監(jiān)督?jīng)Q策樹(shù)算法，它構(gòu)造了一組弱學(xué)習(xí)器(樹(shù))并將結(jié)果累積為最終預(yù)測(cè)輸出。它具有適應(yīng)性，易于理解。此外，它產(chǎn)生高度精確的模型[32]，并成功應(yīng)用于各種應(yīng)用中。XGBoost[33]是一個(gè)相當(dāng)成熟的基于GBDT的機(jī)器學(xué)習(xí)范例。它是一個(gè)大規(guī)模的分布式梯度提升庫(kù)，實(shí)現(xiàn)了尋找近似分裂點(diǎn)并允許并行計(jì)算的GBDT算法。此外，基于Online Boosting算法，Pocock等[34]提出了一種在線非平穩(wěn)提升算法(Online Non-Stationary Boosting, ONSBoost)，該算法提供了一種應(yīng)對(duì)流數(shù)據(jù)中概念漂移的方法，同時(shí)保持在線提升的有用屬性，即處理流數(shù)據(jù)的增量學(xué)習(xí)的能力，以及固定數(shù)量的分類(lèi)，從而固定內(nèi)存使用。Freund等[35]提出了一種自適應(yīng)提升算法(AdaBoost)，它是用于構(gòu)建集合模型的著名的依賴(lài)算法之一，其主要思想是關(guān)注以前在訓(xùn)練新誘導(dǎo)器時(shí)錯(cuò)誤分類(lèi)的實(shí)例。Chu等[36]提出了數(shù)據(jù)流自適應(yīng)挖掘的快速輕增壓算法。它基于動(dòng)態(tài)樣本權(quán)重分配方案，該方案通過(guò)變化檢測(cè)進(jìn)行擴(kuò)展以處理概念漂移。變化檢測(cè)方法旨在實(shí)現(xiàn)可能導(dǎo)致整體性能?chē)?yán)重惡化的重要數(shù)據(jù)變化，并將過(guò)時(shí)的集合替換為從頭開(kāi)始構(gòu)建的集合。

1.3 Stacking

Stacking是通過(guò)一個(gè)元分類(lèi)器或者元回歸器來(lái)整合多個(gè)分類(lèi)模型或回歸模型的集成學(xué)習(xí)技術(shù)。與投票和平均不同，Stacking是一個(gè)通用的組合過(guò)程，其中基本分類(lèi)器在一個(gè)串行模型中非線性組合。在疊加過(guò)程中，基分類(lèi)器稱(chēng)為一級(jí)分類(lèi)器，組合器稱(chēng)為二級(jí)分類(lèi)器(或元分類(lèi)器)。Stacking的基本思想是利用原始訓(xùn)練數(shù)據(jù)集訓(xùn)練多個(gè)一級(jí)分類(lèi)器，然后利用第一級(jí)分類(lèi)器生成的新數(shù)據(jù)集訓(xùn)練第二級(jí)分類(lèi)器，將第一級(jí)分類(lèi)器的輸出作為新訓(xùn)練數(shù)據(jù)集的輸入特征，原始標(biāo)簽仍然是新訓(xùn)練數(shù)據(jù)的標(biāo)簽[29]。

Stacking最初來(lái)源于Wolpert[37]提出的“堆疊泛化”思想，它通?？梢酝ㄟ^(guò)從元數(shù)據(jù)中提取知識(shí)來(lái)提高分類(lèi)性能。然而，疊加泛化是非常耗時(shí)的，因?yàn)橥ǔＲ蕾?lài)于V-fold交叉驗(yàn)證過(guò)程來(lái)估計(jì)作為元分類(lèi)器輸入的每個(gè)樣本的后驗(yàn)類(lèi)概率，以及許多其他疊加方法[38-39]。Bifet等[40]提出了一種使用堆疊結(jié)合受限制的Hoeffding樹(shù)算法，該算法使用堆疊結(jié)合有限屬性集樹(shù)分類(lèi)的窮舉集合，可為給定用戶指定大小k的所有可能屬性子集生成樹(shù)分類(lèi)。此外，由于其算法局限性，該算法僅適用于具有少量屬性的數(shù)據(jù)集。Mashayekhi等[41]根據(jù)規(guī)則選擇的規(guī)則準(zhǔn)確性和覆蓋率計(jì)算了決策樹(shù)集合獲得的規(guī)則得分，并使用爬山法搜索了一組好的規(guī)則。在另一項(xiàng)研究中，Mashayekhi等[42]基于具有下坡移動(dòng)的爬山方法和稀疏組套索方法，設(shè)計(jì)了一種啟發(fā)式搜索方法，從黑箱隨機(jī)森林模型中提取有效規(guī)則。Wang等[43]提出了一種基于XGBoost-LR的Stacking集合信用評(píng)分模型。該模型使用XGBoost作為基類(lèi)分類(lèi)器，并結(jié)合隨機(jī)子空間和Bootstrap算法來(lái)增加基類(lèi)分類(lèi)之間的多樣性。Logistic回歸模型用作次要學(xué)習(xí)者，將每個(gè)XGBoost的結(jié)果作為特征變量學(xué)習(xí)以獲得評(píng)估模型。Necati等[44]通過(guò)修改模型生成和選擇技術(shù)，采用不同的分類(lèi)算法作為組合器方法，對(duì)Stacking方法進(jìn)行了改進(jìn)，與純機(jī)器學(xué)習(xí)技術(shù)相比，該方法始終能提供更高的精度結(jié)果。

2 概念漂移問(wèn)題

2.1 問(wèn)題描述

概念漂移(Concept Drift)表示目標(biāo)變量的統(tǒng)計(jì)特性隨著時(shí)間的推移以不可預(yù)見(jiàn)的方式變化的現(xiàn)象。隨著時(shí)間的推移，模型的預(yù)測(cè)精度將降低。

根據(jù)預(yù)測(cè)分類(lèi)的類(lèi)別，概念漂移問(wèn)題可以分為兩類(lèi)，分別為真實(shí)概念漂移和虛假概念漂移,如圖4所示。

(a) 原始數(shù)據(jù) (b) 真實(shí)漂移 (c) 虛假漂移圖4 概念漂移類(lèi)型

研究發(fā)現(xiàn)，許多學(xué)習(xí)算法都被用于處理概念漂移，它們分別是基于規(guī)則的學(xué)習(xí)、決策樹(shù)、樸素貝葉斯和基于實(shí)例的徑向基函數(shù)學(xué)習(xí)。此外，Cunningham等[45]提出了一種基于實(shí)例的動(dòng)態(tài)用于處理概念漂移。Schlimmer等[46]提出了一種基于增量學(xué)習(xí)的新方法。該方法基于分布式概念描述，分布式概念描述由一組加權(quán)符號(hào)描述組成。該方法通過(guò)在實(shí)例描述中為每個(gè)學(xué)習(xí)到的概念添加一個(gè)屬性，從而在隨后的學(xué)習(xí)中利用先前獲得的概念定義。Bifet等[47]提出了一種基于自適應(yīng)窗口的方法，該方法可以檢測(cè)不同類(lèi)型的漂移，其基礎(chǔ)是對(duì)數(shù)據(jù)塊進(jìn)行逐塊處理，測(cè)量連續(xù)兩個(gè)批次之間的差異，作為漂移指示器。實(shí)驗(yàn)結(jié)果表明，該方法具有較好的漂移檢測(cè)能力，可以近似地找到概念漂移位置。

2.2 概念漂移處理方法

DDM(漂移檢測(cè)方法)[48]是數(shù)據(jù)流概念漂移檢測(cè)方法中經(jīng)典算法之一，它使用二項(xiàng)分布來(lái)檢測(cè)變化，并可以處理在預(yù)測(cè)期間由學(xué)習(xí)模型產(chǎn)生的分類(lèi)錯(cuò)誤。在DDM的基礎(chǔ)上，Manuel等[49]提出了早期漂移檢測(cè)方法(Early drift detection method, EDDM)，該方法是對(duì)DDM的改進(jìn)，用以檢測(cè)概念漂移。其基本思想為找出分類(lèi)錯(cuò)誤之間的距離以檢測(cè)變化。它可以在不增加誤報(bào)率的情況下檢測(cè)變化，并能夠檢測(cè)緩慢的漸變。該研究表明，它將改善預(yù)測(cè)的結(jié)果。Bifet等[50]提出了一種基于自適應(yīng)窗口(ADWIN)的方法，該方法可以檢測(cè)不同類(lèi)型的漂移，基于通過(guò)塊處理數(shù)據(jù)塊并測(cè)量?jī)蓚€(gè)連續(xù)批次之間的差異，作為漂移指示器。實(shí)驗(yàn)結(jié)果表明，該方法能夠檢測(cè)漂移并且可以近似地找到概念漂移位置。Frias等[51]提出了一種基于Hoeffding邊界的漂移檢測(cè)方法(HDDM)，該方法是基于窗口的方法，它涉及移動(dòng)平均線以檢測(cè)突然變化，主要使用加權(quán)移動(dòng)平均值來(lái)檢測(cè)漸變。累積和檢測(cè)方法(CUSUM)[52]是一種順序分析技術(shù)，在漂移檢測(cè)中，它可用于監(jiān)視變化檢測(cè)，而且不需要存儲(chǔ)數(shù)據(jù)。同時(shí)，Ross等[53]提出了一種指數(shù)加權(quán)移動(dòng)平均線圖檢測(cè)方法(EWMAChartDM)，用于檢測(cè)概念漂移。該方法的設(shè)計(jì)使其能夠監(jiān)控流分類(lèi)器的錯(cuò)誤分類(lèi)率，同時(shí)還可以在不增加預(yù)測(cè)期間誤報(bào)率的情況下檢測(cè)變化。此外，Li等[10]提出了一種基于隨機(jī)決策樹(shù)的概念漂移檢測(cè)算法(CDRDT)，該算法可以有效且高效地檢測(cè)來(lái)自嘈雜流數(shù)據(jù)的概念漂移，并可以有效地區(qū)分不同類(lèi)型的概念漂移與噪聲。常見(jiàn)的概念漂移處理技術(shù)如表1所示。

表1 常見(jiàn)概念漂移處理技術(shù)

3 算法分析與總結(jié)

為了更好地分析和總結(jié)數(shù)據(jù)流決策樹(shù)集成分類(lèi)算法的性能，本節(jié)從集成學(xué)習(xí)框架、是否可以處理概念漂移、對(duì)比算法、數(shù)據(jù)集和算法優(yōu)缺點(diǎn)等幾個(gè)角度分析總結(jié)決策樹(shù)集成分類(lèi)算法，算法性能比較結(jié)果如表2所示。

表2 決策樹(shù)集成分類(lèi)算法性能比較

續(xù)表2

4 算法應(yīng)用

4.1 典型應(yīng)用

數(shù)據(jù)流決策樹(shù)集成分類(lèi)算法由于其高效的時(shí)空效率和較高的準(zhǔn)確率，被廣泛應(yīng)用于生活中的各個(gè)領(lǐng)域，在生物醫(yī)療、信用評(píng)價(jià)、電力預(yù)測(cè)和濕地測(cè)繪等均有突出表現(xiàn)。

在生物醫(yī)療領(lǐng)域的最新研究中，Yadav等[54]利用決策樹(shù)、隨機(jī)森林、額外樹(shù)對(duì)甲狀腺疾病進(jìn)行分類(lèi)和預(yù)測(cè)，并利用Bagging集成框架對(duì)得到的結(jié)果進(jìn)行提升，提高了預(yù)測(cè)的精度。該集成方法在特定參數(shù)下，數(shù)據(jù)集的預(yù)測(cè)精度達(dá)到了100%。Geurts等[55]提出了一種基于隨機(jī)森林的決策樹(shù)集成算法對(duì)蛋白質(zhì)組質(zhì)譜的分析和知識(shí)提取，用于識(shí)別臨床蛋白質(zhì)組學(xué)的生物標(biāo)志物，從而完成蛋白質(zhì)組質(zhì)譜的分類(lèi)和預(yù)測(cè)任務(wù)。此外，在藥物設(shè)計(jì)方面，數(shù)據(jù)流決策樹(shù)集成分類(lèi)算法也有所涉足。Pu等[56]通過(guò)對(duì)約160 000個(gè)特定藥物設(shè)計(jì)問(wèn)題的親和力預(yù)測(cè)實(shí)驗(yàn)對(duì)比，LightGBM[57]和XGBoost均表現(xiàn)出比神經(jīng)網(wǎng)絡(luò)更高的效率，并可以提取出比傳統(tǒng)方法更多的蛋白質(zhì)-配體結(jié)合信息，將藥物設(shè)計(jì)的篩選效率提高到原來(lái)的200～1 000倍。

在信用評(píng)價(jià)領(lǐng)域，Wang等[43]提出了一種基于Stacking的個(gè)人信用風(fēng)險(xiǎn)評(píng)估模型，該模型使用不同的訓(xùn)練子集及特征采樣和參數(shù)擾動(dòng)方法對(duì)個(gè)人的信用進(jìn)行風(fēng)險(xiǎn)評(píng)估預(yù)測(cè)。結(jié)合上述方法和企業(yè)信用評(píng)價(jià)模型研究的短缺，Sun等[58]提出了一種用于不平衡企業(yè)信用評(píng)價(jià)預(yù)測(cè)的新決策樹(shù)集成模型——DTE-SBD，該模型可以處理高風(fēng)險(xiǎn)企業(yè)與低風(fēng)險(xiǎn)企業(yè)之間的階級(jí)不平衡問(wèn)題。對(duì)552家中國(guó)上市公司的財(cái)務(wù)數(shù)據(jù)進(jìn)行了100次實(shí)證實(shí)驗(yàn)，證明對(duì)企業(yè)信用評(píng)價(jià)的不均衡性是有效的，并提高了企業(yè)信用評(píng)價(jià)的正確率。

在電力消耗預(yù)測(cè)方面，Galicia等[59]對(duì)西班牙10年的電力消耗數(shù)據(jù)進(jìn)行訓(xùn)練和預(yù)測(cè)，平均相對(duì)誤差達(dá)到了2%，并已將該模型應(yīng)用于澳大利亞的太陽(yáng)能預(yù)測(cè)。在濕地測(cè)繪和分類(lèi)方面，Berhane等[60]對(duì)俄羅斯貝加爾湖塞倫加河三角洲22種復(fù)雜淡水三角洲濕地植被和水生生境進(jìn)行有效監(jiān)督分類(lèi)，隨機(jī)森林算法在大多數(shù)情況下都表現(xiàn)出較高的精度，取得了理想的效果。

4.2 主要平臺(tái)

由于流數(shù)據(jù)具有連續(xù)性和實(shí)時(shí)性的特點(diǎn)，因此流數(shù)據(jù)處理平臺(tái)需要具有實(shí)時(shí)處理的特點(diǎn)，其將實(shí)時(shí)數(shù)據(jù)逐條加載至高性能內(nèi)存數(shù)據(jù)庫(kù)中進(jìn)行分析和處理，數(shù)據(jù)遲滯低。目前應(yīng)用較為廣泛的流數(shù)據(jù)處理平臺(tái)有Storm[61]、Spark Streaming[62]和Flink[63]等。

作為最佳的流式計(jì)算框架之一，Storm平臺(tái)是Twitter支持開(kāi)發(fā)，并由Clojure語(yǔ)言和Java語(yǔ)言寫(xiě)成，其優(yōu)點(diǎn)是全內(nèi)存計(jì)算。Storm可以用來(lái)處理源源不斷的數(shù)據(jù)，并在處理之后將結(jié)果保存在某個(gè)存儲(chǔ)中。此外，由于Storm的處理組件是分布式的，而且處理延遲極低，因此Storm可以作為分布式RPC框架進(jìn)行計(jì)算。

Spark Streaming是構(gòu)建在Spark基礎(chǔ)之上的流數(shù)據(jù)處理框架，具有吞吐量高和容錯(cuò)能力強(qiáng)的特點(diǎn)，同時(shí)支持多種數(shù)據(jù)輸入和輸出格式。Spark Streaming是將流式數(shù)據(jù)分解為一系列的微小數(shù)據(jù)集，形成離散流，并將其轉(zhuǎn)化為短小的批處理作業(yè)進(jìn)行計(jì)算。它是一個(gè)基于內(nèi)存的迭代計(jì)算框架，適用于需要多次操作特定數(shù)據(jù)集的應(yīng)用場(chǎng)合。需要反復(fù)操作的次數(shù)越多，所需的數(shù)據(jù)量越大，受益越大；數(shù)據(jù)量小且計(jì)算密集度較大時(shí)，受益相對(duì)較小。

Flink是一個(gè)用Java語(yǔ)言和Scala語(yǔ)言編寫(xiě)的開(kāi)源分布式流處理和批處理系統(tǒng)，在傳統(tǒng)數(shù)據(jù)庫(kù)系統(tǒng)和大數(shù)據(jù)分析框架之間起到鏈接的作用。Flink的核心功能是在數(shù)據(jù)流上提供數(shù)據(jù)分發(fā)、通信、具備容錯(cuò)的分布式計(jì)算。同時(shí)，F(xiàn)link在流處理引擎上構(gòu)建了批處理引擎，原生支持了迭代計(jì)算、內(nèi)存管理和程序優(yōu)化。

以上三種平臺(tái)分別具有不同的功能特點(diǎn)，對(duì)特定場(chǎng)景下的流數(shù)據(jù)處理均有理想的表現(xiàn)，在國(guó)內(nèi)外的研究中應(yīng)用廣泛。

5 結(jié) 語(yǔ)

本文以三種集成學(xué)習(xí)框架的角度介紹了數(shù)據(jù)流決策樹(shù)集成分類(lèi)的相關(guān)算法及研究現(xiàn)狀，同時(shí)對(duì)數(shù)據(jù)流中的概念漂移問(wèn)題及其處理算法做了詳細(xì)的闡述。文章的最后，分別以集成學(xué)習(xí)框架、處理概念漂移的能力、對(duì)比算法、數(shù)據(jù)集和優(yōu)缺點(diǎn)等角度對(duì)所提及的決策樹(shù)集成分類(lèi)相關(guān)算法進(jìn)行了分析與總結(jié)，并以此分析出集成學(xué)習(xí)的趨勢(shì)和未來(lái)的研究方向。

可以預(yù)見(jiàn)，集成學(xué)習(xí)方法將得到進(jìn)一步改進(jìn)，更適用于大數(shù)據(jù)流的學(xué)習(xí)，特別是不依賴(lài)于基礎(chǔ)學(xué)習(xí)器并且可以處理高維度的方法，因?yàn)檫@些方法可以很容易并行化并且可擴(kuò)展。這些努力通常涉及實(shí)現(xiàn)分布式機(jī)器學(xué)習(xí)以及平臺(tái)計(jì)算資源利用支撐和應(yīng)用模型的部署。此外，另一個(gè)有前途的研究方向是將集合模型轉(zhuǎn)換為更簡(jiǎn)單和更全面的模型，同時(shí)保持它們所源自的集合的預(yù)測(cè)準(zhǔn)確性[64]。新數(shù)據(jù)流集成學(xué)習(xí)方法應(yīng)該從傳統(tǒng)的分類(lèi)設(shè)置轉(zhuǎn)向處理具有挑戰(zhàn)性的真實(shí)世界場(chǎng)景的新方法，尤其是半監(jiān)督(部分標(biāo)記)和不平衡分類(lèi)的數(shù)據(jù)流，使得集成學(xué)習(xí)應(yīng)用的靈活性和準(zhǔn)確性得到更好的價(jià)值體現(xiàn)。