基于自適應(yīng)隨機森林的數(shù)據(jù)流分類算法*

張馨予,安建成,曹 銳

(太原理工大學(xué)軟件學(xué)院,山西 晉中 030600)

1 引言

處理源源不斷的數(shù)據(jù)流的需求越來越多，應(yīng)用場景無處不在，如信用卡欺詐監(jiān)測、網(wǎng)絡(luò)流量監(jiān)控和在線金融交易等場景，這些數(shù)據(jù)流中往往蘊含著巨大的信息量。為了獲取并掌握這些信息，人們開啟了對數(shù)據(jù)流分析方法的探索。

傳統(tǒng)的機器學(xué)習(xí)算法大多針對離線數(shù)據(jù)反復(fù)訓(xùn)練模型，而數(shù)據(jù)流[1]中的數(shù)據(jù)具有高速到達(dá)、變化多樣以及規(guī)模龐大等特點，這些特點對傳統(tǒng)的機器學(xué)習(xí)算法提出了新的挑戰(zhàn)。

大多數(shù)數(shù)據(jù)流都具有概念漂移[2]的特點，“概念漂移”是指隨著時間的推移，目標(biāo)變量的統(tǒng)計特性以不可預(yù)見的方式發(fā)生變化的現(xiàn)象。對具有概念漂移的數(shù)據(jù)流進(jìn)行預(yù)測的模型，如果不采取適當(dāng)?shù)膽?yīng)對概念漂移的措施，預(yù)測精度會隨著時間的推移而降低。

數(shù)據(jù)流分類研究領(lǐng)域的專家們已經(jīng)證明了相對于單分類器，集成分類器具有更優(yōu)的學(xué)習(xí)性能[3]，這是由于集成分類器不需要復(fù)雜的優(yōu)化過程且能靈活處理概念漂移的問題?，F(xiàn)有的典型的分類器集成方法大多分為3類，分別是基于bagging、基于boosting和基于隨機森林的集成方法。Bifet等人[4]介紹的leveraging bagging是基于bagging的集成方法。Chen等人[5]提出的online smooth-boost是基于boosting的集成方法的典型代表。國內(nèi)對數(shù)據(jù)流分類器集成過程的一些研究是通過結(jié)合bagging和boosting的部分特點進(jìn)行的。比如文獻(xiàn)[6]依據(jù)不同數(shù)據(jù)特征對分類的影響程度不同的理論,提出基于特征漂移的數(shù)據(jù)流集成分類方法。文獻(xiàn)[7]在經(jīng)典的精度加權(quán)集成AWE(Accuracy Weighted Ensemble)算法[8]的基礎(chǔ)上提出概念自適應(yīng)快速決策樹更新集成算法。而基于隨機森林的算法在處理具有概念漂移的數(shù)據(jù)流分類時性能較優(yōu)，主要是由于該算法對輸入數(shù)據(jù)的預(yù)處理以及對超參數(shù)設(shè)置的要求較低。利用隨機森林算法對數(shù)據(jù)流分類的代表是Abdulsalam等人[9]2008年提出的動態(tài)流隨機森林算法。但是，該算法缺少重采樣方法，使用的漂移探測算法缺少可靠的理論依據(jù)，且該算法提出時僅在合成數(shù)據(jù)集上被評估，缺乏普適性。2017年Gomes等人[10]在已有算法基礎(chǔ)上提出了自適應(yīng)隨機森林分類ARF(Adaptive Random Forest)算法，該算法的優(yōu)勢在于結(jié)合在線bagging的重采樣方法生成訓(xùn)練集，在每棵基礎(chǔ)樹上增加概念漂移探測器、背景樹訓(xùn)練等機制自適應(yīng)更新集成器來應(yīng)對概念漂移。但是，該算法在有效提高分類性能的同時，消耗的時間和內(nèi)存空間較大。

本文針對具有概念漂移的較平衡數(shù)據(jù)流提出了一種改進(jìn)的自適應(yīng)隨機森林集成分類算法RARF(Revised Adaptive Random Forest)，算法將探測器設(shè)置在集成器上，增加了移除基礎(chǔ)樹機制和統(tǒng)一訓(xùn)練背景樹機制，不僅使得算法具有較高的準(zhǔn)確率，還有效降低了運行時間和內(nèi)存消耗。

2 自適應(yīng)隨機森林分類算法

ARF將批處理算法的特點與動態(tài)更新方法結(jié)合起來用于處理不斷變化的數(shù)據(jù)流。創(chuàng)新優(yōu)勢及存在的問題如下所示：

2.1 創(chuàng)新優(yōu)勢

ARF的主要目標(biāo)是處理帶有概念漂移的數(shù)據(jù)流。當(dāng)有新數(shù)據(jù)流進(jìn)來時，每棵基礎(chǔ)樹都會對新數(shù)據(jù)流進(jìn)行預(yù)測，根據(jù)預(yù)測結(jié)果更新基礎(chǔ)樹權(quán)重。ARF為每棵基礎(chǔ)樹設(shè)置了漂移探測器，漂移探測器有2個超參數(shù)：警告閾值δw和漂移閾值δd。當(dāng)漂移探測器的探測結(jié)果達(dá)到δw時，開始在背景上同步訓(xùn)練1棵全新的基礎(chǔ)樹(稱為背景樹)，當(dāng)漂移探測器的探測結(jié)果達(dá)到δd時，背景樹代替原基礎(chǔ)樹作為集成器的一份子。背景樹是提前接受過訓(xùn)練的，這種替換機制有效克服了傳統(tǒng)直接替代法中新基礎(chǔ)樹沒有受過任何實例訓(xùn)練，無法對集成器產(chǎn)生積極影響的問題。

2.2 存在的問題

ARF在每棵基礎(chǔ)樹上分別配置漂移探測器，運行過程中經(jīng)常會同時觸發(fā)多個探測器，引起多棵背景樹同時開始訓(xùn)練，導(dǎo)致運行時間較長，運行資源占用較多。

3 改進(jìn)的自適應(yīng)隨機森林集成分類器

RARF是本文提出的一種基于自適應(yīng)隨機森林的數(shù)據(jù)流分類算法，該算法主要包含基礎(chǔ)樹的訓(xùn)練過程和集成器的更新過程。

3.1 基礎(chǔ)樹的訓(xùn)練過程

RARF算法根據(jù)式(1)對實例進(jìn)行重采樣，為同一實例分配不同權(quán)重用于訓(xùn)練不同基礎(chǔ)樹。

Poisson(λ=6)

(1)

對Hoeffding樹[11]進(jìn)行改進(jìn)得到基礎(chǔ)樹。首先，基礎(chǔ)樹在訓(xùn)練之前不會進(jìn)行任何形式的預(yù)剪枝。其次，基礎(chǔ)樹的任何1個節(jié)點在分裂的過程中都會從所有的M個特征中隨機選取m個特征作為分裂的依據(jù)。m的計算如式(2)所示：

(2)

基礎(chǔ)樹在對實例進(jìn)行訓(xùn)練之前首先根據(jù)預(yù)測結(jié)果更新基礎(chǔ)樹在集成器中的權(quán)重，在沒有發(fā)生概念漂移前通過削弱表現(xiàn)不好的基礎(chǔ)樹的權(quán)重減少其對集成器的影響；當(dāng)發(fā)生概念漂移時，通過使用背景樹集替換的方式移除表現(xiàn)差的基礎(chǔ)樹，兩者結(jié)合可消除歷史數(shù)據(jù)對集成器的消極影響。

3.2 集成器的更新過程

RARF在集成器上設(shè)置1個探測器，對實例的集成預(yù)測結(jié)果的變化進(jìn)行探測，當(dāng)發(fā)生概念漂移警告時，根據(jù)式(3)確定需要同時訓(xùn)練的背景樹個數(shù)b。該改進(jìn)使得探測器的個數(shù)由n降為1，由于集成預(yù)測結(jié)果相較于基礎(chǔ)樹的預(yù)測結(jié)果更為準(zhǔn)確全面，所以在集成器上設(shè)置探測器能更準(zhǔn)確地捕獲概念漂移。

b=n(1-ln(1+AccE(e-1)))+n/10

(3)

文獻(xiàn)[12]提出了一種根據(jù)準(zhǔn)確率計算替換基礎(chǔ)樹個數(shù)的公式，考慮到文獻(xiàn)[12]中的公式會引入2個超參數(shù)，所以對其進(jìn)行改進(jìn)得到式(3)。其中，n為集成器中基礎(chǔ)樹的總數(shù)量，AccE為集成器的準(zhǔn)確率，e為自然底數(shù)，準(zhǔn)確率越高，1+AccE(e-1)的值越趨近于e。集成器的準(zhǔn)確率越高，背景樹數(shù)量b越小，可以通過替換少量基礎(chǔ)樹來保持性能；當(dāng)集成器的準(zhǔn)確率較低時，可以通過替換更多的基礎(chǔ)樹來快速恢復(fù)準(zhǔn)確率。

若探測器的結(jié)果達(dá)到漂移閾值，此時的背景樹集已是同步經(jīng)過訓(xùn)練后的候選樹集。由于基礎(chǔ)樹的權(quán)重是實時更新的，且權(quán)重的大小反映基礎(chǔ)樹表現(xiàn)的優(yōu)劣，RARF將與背景樹集中樹數(shù)量一致的權(quán)重較小的基礎(chǔ)樹集移除，用背景樹集替換。這種機制使得當(dāng)發(fā)生概念漂移時，迅速用背景樹集替換1組基礎(chǔ)樹，集成器性能可更快地從概念漂移中恢復(fù)，同時增強了算法在準(zhǔn)確性和內(nèi)存消耗方面的自主性。

3.3 算法流程

算法參數(shù)：集成器中的基礎(chǔ)樹集T;集成器中基礎(chǔ)樹的數(shù)量n=|T|；用于評估每個分裂節(jié)點的最大特征數(shù)α；數(shù)據(jù)流S；警告閾值δw；漂移閾值δd；漂移探測器C(·)；背景樹數(shù)量b；背景樹集合B；移除樹集合R；樹t的權(quán)重W(t)；學(xué)習(xí)性能評估器P(·)；集成器E(T);具體實例(x,y),其中，x為特征，y為類別。

算法1RARF算法

輸入：S，m,n,δw,δd。

輸出：S的分類結(jié)果。

1.T=CreateTrees(n);

2.W=InitWeights(n);

3.B=?;

4. whileHasNext(S) do

5. (x,y)=Next(S);

6. for allt∈Tdo

9.RFTreeTrain(α,t,x,y);

10: end for

12. ifC(δw,E(T),x,y) then

13.B=CreateTree(b);//創(chuàng)建背景樹集

14. for allt∈Bdo

15.RFTreeTrain(α,t,x,y);/*訓(xùn)練背景樹集中的每棵樹*/

16: end for

17. end if

18. ifC(δd,E(T),x,y) then

19.E(T)=E(T)-R(b)+B(b);/*用背景樹集替換效果差的樹集*/

20. end if

21. end while

4 實驗及結(jié)果分析

為驗證RARF算法的有效性，選用LED、“森林覆蓋類型”和SEA(Streaming Ensemble Algorithm)3個數(shù)據(jù)集進(jìn)行仿真實驗，在每個數(shù)據(jù)集上分別使用ARF和RARF 2種模型進(jìn)行對比實驗。

4.1 訓(xùn)練數(shù)據(jù)集描述

LED顯示域數(shù)據(jù)集[13]屬于合成數(shù)據(jù)集，共包含1 000 000個實例，每個實例有24個布爾類型的特征，其中17個是不相關(guān)的，具有逐漸漂移的特性。分類目標(biāo)是預(yù)測在7段LED顯示屏上顯示的數(shù)字，共有10個類別，每個類別的樣本數(shù)基本均勻。

“森林覆蓋類型”數(shù)據(jù)集[14]來源于美國地質(zhì)調(diào)查局和美國森林服務(wù)中心的原始數(shù)據(jù)。數(shù)據(jù)包含定性自變量(荒野地區(qū)和土壤類型)的二進(jìn)制(0或1)列數(shù)據(jù)。整個數(shù)據(jù)集共包含分屬于7個不均勻等級的581 012個樣例，每個樣例由 54個特征組成，包括 10個數(shù)量變量，4個二進(jìn)制自然保護(hù)區(qū)，40個二進(jìn)制土壤類型變量。

SEA數(shù)據(jù)集是合成數(shù)據(jù)集，在數(shù)據(jù)挖掘中經(jīng)常用到，它包含3個隨機生成的實數(shù)特征和2個正負(fù)類別，區(qū)分類別的邊界由f1+f2 ≤θ給出，通過改變θ的值來引入概念漂移。SEA數(shù)據(jù)集首先被用于數(shù)據(jù)流集成算法 SEA[15]的實驗部分。

4.2 實驗環(huán)境

實驗環(huán)境使用Windows 10操作系統(tǒng)，CPU為Intel 4核，內(nèi)存為8 GB，開發(fā)語言使用Python 3.6，開發(fā)工具使用PyCharm 2018，實驗框架為大規(guī)模在線分析平臺MOA(Massive Online Analysis)[16]。

4.3 評價策略

實驗采用prequential評價策略[17]，即每條實例先作為測試實例而后作為訓(xùn)練實例，準(zhǔn)確率增量更新。采用這種評價策略不用為了測試而保留數(shù)據(jù)集，從而保證了最大化地利用每個實例的信息，也保證準(zhǔn)確率隨時間具有平滑性。

4.4 實驗分析

2個算法的參數(shù)設(shè)置如表1所示。實驗主要從時間消耗、內(nèi)存消耗、準(zhǔn)確率和Kappa值對比3方面進(jìn)行分析。

Table 1 Default experimental parameter Settings表1 默認(rèn)實驗參數(shù)設(shè)置

4.4.1 參數(shù)影響

對待分類的實例進(jìn)行分類需要選擇合適數(shù)量的基礎(chǔ)樹，在此過程中，RARF需要根據(jù)基礎(chǔ)樹數(shù)量決定背景樹個數(shù)和移除基礎(chǔ)樹的個數(shù)，而ARF需要根據(jù)基礎(chǔ)樹數(shù)量配置相同數(shù)量的探測器。對2個算法而言，基礎(chǔ)樹的數(shù)量不能過大。通過實驗得出，設(shè)置20棵基礎(chǔ)樹可以保證較高的準(zhǔn)確率，同時加強了時間和空間消耗的對比性。因此，在以下實驗中，均取基礎(chǔ)樹數(shù)量n=20。

4.4.2 時間效率

圖1～圖3所示為ARF算法和RARF算法分別在LED、“森林覆蓋類型”、SEA 3個數(shù)據(jù)集上的時間消耗。如圖1～圖3所示，RARF算法的時間消耗在各數(shù)據(jù)集上均少于ARF算法的。這是因為RARF算法的每棵基礎(chǔ)樹只負(fù)責(zé)實例的訓(xùn)練和預(yù)測，在集成器端對實例預(yù)測結(jié)果進(jìn)行1次探測檢查，而ARF算法每棵基礎(chǔ)樹在訓(xùn)練和預(yù)測結(jié)束后要對實例進(jìn)行k次探測檢查。因此,RARF算法消耗的時間更短，性能更高。

Figure 1 Time consumption comparison on LED data set圖1 LED數(shù)據(jù)集上的時間消耗對比

Figure 2 Time consumption comparison on “Forest cover” type data set圖2 “森林覆蓋類型”數(shù)據(jù)集上時間消耗對比

Figure 3 Time consumption comparison on SEA data set圖3 SEA數(shù)據(jù)集上時間消耗對比

4.4.3 內(nèi)存消耗情況

2種算法內(nèi)存消耗對比情況如圖4～圖6所示。由圖4～圖6可以看出，RARF算法的內(nèi)存消耗在LED和SEA數(shù)據(jù)集上少于ARF算法的，在“森林覆蓋類型”數(shù)據(jù)集上大于ARF算法的。這是因為“森林覆蓋類型”數(shù)據(jù)集是1個不平衡的數(shù)據(jù)集，正負(fù)樣本比例懸殊，當(dāng)出現(xiàn)正樣本時，準(zhǔn)確率迅速下降，集成端探測器發(fā)現(xiàn)漂移，觸發(fā)一批背景樹同步訓(xùn)練，空間消耗較大。在LED和SEA這種基本平衡的數(shù)據(jù)流上，2種算法的準(zhǔn)確率不會出現(xiàn)驟變，RARF算法所需的內(nèi)存遠(yuǎn)小于ARF算法的。這是由于ARF中的各基礎(chǔ)樹選取的特征不同，同一實例在不同基礎(chǔ)樹上的權(quán)重也不同，預(yù)測結(jié)果出現(xiàn)多樣化，更容易在一些并未發(fā)生漂移的情況下檢測出漂移，進(jìn)而觸發(fā)訓(xùn)練背景樹的動作，使得內(nèi)存占用增大。而RARF算法克服了該問題，僅在漂移真正出現(xiàn)時訓(xùn)練背景樹，因此對于比較平衡的數(shù)據(jù)流而言，RARF算法消耗的內(nèi)存更少。

Figure 4 Memory consumption comparison on LED data set圖4 LED數(shù)據(jù)集上的內(nèi)存消耗對比

Figure 5 Memory consumption comparison on “Forest cover type” data set圖5 “森林覆蓋類型”數(shù)據(jù)集上的內(nèi)存消耗對比

Figure 6 Memory consumption comparison on SEA data set圖6 SEA數(shù)據(jù)集上的內(nèi)存消耗對比

4.4.4 準(zhǔn)確率和Kappa值

圖7～圖9顯示的是2種算法在3個數(shù)據(jù)集上準(zhǔn)確率和Kappa值的變化過程，表2記錄了2種算法在3個數(shù)據(jù)集上當(dāng)前和平均的準(zhǔn)確率、Kappa值。從圖7～圖9以及表2可以看出，2種算法的平均準(zhǔn)確率和Kappa值十分接近，這是因為RARF算法雖然只在集成器端探測1次漂移情況，但相較于ARF在各個基礎(chǔ)樹上設(shè)置探測器更加準(zhǔn)確全面，不會出現(xiàn)漏測情況。

Figure 7 Accuracy and Kappa comparison on LED data set圖7 “森林覆蓋類型”數(shù)據(jù)集上的準(zhǔn)確率和Kappa值對比

Figure 8 Accuracy and Kappa comparison on “Forest cover type” data set圖8 “森林覆蓋類型”數(shù)據(jù)集上的準(zhǔn)確率和Kappa值對比

Figure 9 Accuracy and Kappa comparison on SEA data set圖9 SEA數(shù)據(jù)集上準(zhǔn)確率和Kappa值對比

Table 2 Current and average accuracy,Kappa
表2 當(dāng)前和平均準(zhǔn)確率與kappa值

數(shù)據(jù)集算法當(dāng)前準(zhǔn)確率 Kappa平均準(zhǔn)確率 KappaLEDARF0.660 00.619 20.754 10.726 8RARF0.710 00.675 40.706 20.673 5森林覆蓋類型ARF0.730 00.533 40.753 80.712 3RARF0.815 00.701 90.783 70.747 1SEAARF0.935 00.840 10.879 80.687 9RARF0.920 00.804 10.866 60.655 2

當(dāng)發(fā)生概念漂移需要替換基礎(chǔ)樹時，ARF用背景樹根據(jù)基礎(chǔ)樹預(yù)測準(zhǔn)確率的變化情況替換檢測到漂移的基礎(chǔ)樹，RARF是根據(jù)遞增的基礎(chǔ)樹的預(yù)測準(zhǔn)確率用提前訓(xùn)練好的基礎(chǔ)樹集替換部分基礎(chǔ)樹集，所以在2種算法中表現(xiàn)差的基礎(chǔ)樹都可以被及時替換掉。而RARF可以同時用背景樹替換一批表現(xiàn)差的基礎(chǔ)樹，能更快速地更新集成器的信息而不受到歷史數(shù)據(jù)的影響，使得準(zhǔn)確率變化相對更穩(wěn)定，且能快速從概念漂移中恢復(fù)。

4.4.5 實驗結(jié)論

通過實驗對比分析可得出以下結(jié)論：RARF算法在類別分布較為平衡的數(shù)據(jù)集上能保證較高準(zhǔn)確率，時間和內(nèi)存消耗更少。

5 結(jié)束語

使用集成器對數(shù)據(jù)流分類是當(dāng)前數(shù)據(jù)挖掘領(lǐng)域的一個熱點，實時預(yù)測并有效應(yīng)對概念漂移是數(shù)據(jù)流處理過程中的難點之一。本文在ARF算法基礎(chǔ)上加以改進(jìn)，提出了一種改進(jìn)的隨機森林自適應(yīng)集成分類算法，該集成算法通過在集成器上增加漂移探測器，設(shè)置警告閾值，并在發(fā)出警告后，根據(jù)集成器準(zhǔn)確率訓(xùn)練適當(dāng)數(shù)目的背景樹；設(shè)置漂移閾值，在發(fā)生漂移后，用訓(xùn)練好的背景樹替換集成器中表現(xiàn)不好的基礎(chǔ)樹，在保證了準(zhǔn)確率的前提下，盡可能地減少了運行所耗時間和內(nèi)存。通過分析和實驗仿真，驗證了RARF算法相較于ARF算法，在處理概念漂移問題中整體表現(xiàn)更穩(wěn)定，內(nèi)存和時間消耗更少。而如何進(jìn)一步提升自適應(yīng)隨機森林集成模型對不平衡以及不確定數(shù)據(jù)流[18]分類的預(yù)測效果，是下一步研究的方向。