面向概念漂移數據流的自適應增量集成分類算法

呂艷霞,劉波男,王翠榮,王 聰,萬 聰

1(東北大學 計算機科學與工程學院,沈陽 110004)2(東北大學 秦皇島分校 計算機與通信工程學院,河北 秦皇島 066004)

1 引 言

在大數據時代,互聯網應用的普及、移動通信網絡的發展,使得數據的獲取速度與數據量迅速增加,數據成為了重要的生產資料.由于數據中蘊含著大量有價值的信息,且很多信息具有很強的時效性,如醫療診斷[1]、社交網絡[2]、推薦系統以及異常檢測等眾多領域都需要對數據進行實時分析從而及時獲取其中蘊含的有價值的知識.為了快速處理如此龐大的數據,我們需要快速有效的方法,使用合理的資源來完成實時處理分析[3].

實時數據分析是大數據分析場景中的一種特定情況.對于特定應用場景來說,重要的不僅僅是及時獲得查詢的結果,還要能夠根據剛剛產生的最新數據獲得查詢結果.數據流是一種支持實時分析的算法抽象,抽象為無限的樣本序列,每個樣本都有一個時間戳,因此樣本是有時序的.樣本一個接一個的到達,需要對這些樣本實時的構建和維護表示它們的模型.本文主要研究的是數據流在分類問題中的算法及相應的模型構建.

數據流分為穩定的數據流和動態的數據流,穩定的數據流具有穩定獨立同分布的特點,易于預測和控制;而動態數據流則是非獨立同分布的,并且可能隨著時間變化而發生改變,使得在之前數據集上建立的預測模型不再適用于當前的數據分布,這種現象稱之為概念漂移[4].例如大型商場中顧客的購物傾向會隨著時間變化、網絡安全中的入侵檢測[5]也隨著用戶不同而變化等.在進行流數據分類時,有兩個主要的算法挑戰:數據流龐大且速度快,并且我們需要實時從中提取信息.這意味著為了節省時間和內存,通常需要接受近似的解決方案;此外,數據可能正在演變即發生概念漂移,模型必須能夠適應概念漂移的情況.

解決概念漂移是數據流分類面對的最重要的問題之一.通常的解決辦法是:首先,檢測到數據流中概念漂移的發生;然后,通過對概念漂移的衡量來使得模型進行自適應.利用集成學習的靈活特性可以通過對模型進行集成應對概念漂移.數據流的特點之一就是數據的源源不斷的特點,在不考慮數據快速到來這一特點,數據量的巨大則要求整個模型的自適應的調整不能讓模型隨著數據量的增大速度逐漸變慢.在許多經典的集成學習算法中,通過對單模型的集成來解決數據流產生的概念漂移問題以及可能會出現的數據不平衡現象[6,7],但是沒有很好的機制去合理的使得所有基模型僅利用當前的一部分數據建立,因此存在一些基模型從數據流的開始就一直存在.雖然利用替換策略等方法可以使得整體模型的性能保持在一個合理的范圍,但是如何使得整體模型隨著數據不斷到達,適應不同的樣本窗口也是一個需要解決的問題.

在集成學習中公認的在適當的組合方案下,基模型之間的多樣性是必不可少的[8].集成模型通常利用特征的采樣或者樣本的采樣來制造基模型之間的多樣性,并且整體模型針對預測的準確率或者其他針對當前模型的衡量指標進行自適應調整.然而,在數據流環境下,通常集成模型中每一個基模型都是建立在過去所有或者大部分數據的基礎上的,即使有自適應的調整,也需要依賴對概念漂移檢測算法以及不同的策略去修改或者刪除在過去概念上已經建立好的基模型.這中間就會產生這樣一個問題:如何使得對數據變化敏感又不至于太過敏感且在當前數據窗口上分類性能良好的模型不被刪掉.

具體來說,在含有概念漂移的數據流分類模型的構建過程中,設計增量集成學習模型需要解決兩個研究問題:保留哪些之前訓練的歷史模型用來對新到達的樣本進行預測以及如何利用保留的歷史模型更好的適應發生概念漂移時的學習.為此,本文中提出了一種用于數據流分類的增量集成模型,基模型之間的多樣性不再僅僅通過樣本的采樣來實現,而是通過引入用于集成學習的多樣性策略[9]來保持基模型之間的多樣性最大化.在數據流分類研究中,大多采用增量集成模型的算法都采用決策樹作為基模型,本文選擇自適應霍夫丁決策樹[10]作為基模型,結合模型遷移的思想使歷史模型高效的適應最新數據.并且利用基于當前數據的基模型的適應性更新集成模型,使其保持對當前數據的性能最優.

2 相關研究

當前針對具有概念漂移的數據流分類方法,可分為增量分類模型和集成分類模型.集成模型是數據流研究領域中普遍使用的方法之一,它可以同時處理機器學習問題和數據流中的概念漂移,并且能夠取得很好的效果.由于在數據流中數據不斷到達,不能一次性獲得全部數據,需要不斷訓練模型以適應最新數據分布,因此增量模型也是數據流分類研究中經常使用的方法之一.

在增量學習中,常用的處理概念漂移的策略包括:滑動窗口、概念漂移檢測和集成方法.滑動窗口方法[11]主要應用于在線學習場景,保留部分最近到達的數據,并用保留的數據和新到達的訓練樣本更新當前模型.另外一些模型[12]在學習算法中使用概念漂移檢測模塊.如果未檢測到概念漂移,則使用新到達的數據更新當前模型.否則,當前模型(可能是單個模型[12]或集成模型[13])將被丟棄,并從頭開始構建新模型.以上兩種策略都不需要保留先前獲得的知識/模型.然而,在概念重復出現的情況下,保留歷史模型將是有益的,可以直接使用歷史模型進行預測.在更一般的情況下,如果兩個概念是相關的,但是出現的時間并不連續,則調整歷史模型可能比優化當前模型或構建新模型更容易.因此,保留歷史模型的集成方法近年來越來越受歡迎[14].

Leverage Bagging[15]在模型的輸入和輸出中引入隨機性進一步使集成模型具有更好的多樣性.該模型主要是通過對樣本采樣,并且根據模型對樣本預測的準確率的變化對輸出進行隨機化的改變,來應對概念漂移.通過對模型在當前樣本的表現能力進行監測,當預測準確率下降時,進行被動調整.自適應隨機森林[16](ARF)是基于隨機森林提出的處理數據流分類的集成模型,ARF通過對概念漂移的檢測并設立警告機制,通過訓練替換樹加速概念漂移發生時集成模型的更新.Online Smooth Boosting[17]是處理概念漂移的另外一種常用集成方法,通過對已經到達的數據進行評估得到其權重以及每個基模型的權重,實現集成模型的多樣性.以上集成方法都是通過對數據進行采樣或者通過對樣本和基模型賦予不同的權重實現集成模型中基模型的多樣性,提升模型對當前數據的泛化能力.當數據流中相同或相似的概念重復出現時,利用已經建立的歷史模型對當前數據進行準確預測可以節省資源同時加速模型的概念漂移適應性.在基于增量學習的基礎上提出了DTEL[18],在集成模型的更新策略上采用最大化模型多樣性的更新策略,同時利用模型遷移的思想使歷史模型快速適應當前數據窗口.為了使得模型可以更好的應對概念漂移,不僅可以利用部分的歷史信息,而且可以不通過樣本采樣或者屬性采樣實現模型多樣性,利用自適應霍夫丁決策樹作為基模型,本文提出了基于歷史模型的自適應集成分類算法HAEL算法.

3 基模型自適應集成分類算法

本文主要在增量學習的基礎上將遷移學習融入到集成模型的更新過程,提出了新的更新策略,并且采用自適應霍夫丁決策樹作為基模型,從而得到更加適合含有概念漂移的數據流分類模型.該模型在保存必要的歷史信息的前提下可以針對當前的數據,并且不需要采樣來得到單模型之間的差異性.在面對概念漂移的時候具有更好的適應能力.

3.1 集成框架

在基于Bagging的集成模型當中,基模型的訓練數據集是通過各種不同的采樣技術得到的.在發生概念漂移的時候多是利用概念漂移檢測機制來確定模型是否更新.在基于Boosting的集成模型當中,通過利用樣本的真實標簽對預測標簽進行評估,從而對集成模型中的基模型和每一條樣本賦予一個權值來得到.當數據變化足夠強烈的時候,如發生突變漂移,以上兩種模型均能很快的做出應對,但是在漸進漂移的時候,數據的分布緩慢發生變化,導致兩種模型不能及時的適應這類概念漂移的發生.不同于傳統的增量模型的集成策略,利用歷史知識進行概念漂移自適應的DTEL集成模型,基模型的訓練基于每一個最新到達的窗口數據,并且集成模型的更新是以基于多樣性的標準來代替基于準確率的標準.本文提出的HAEL采用基于準確率的模型更新策略,使用當前最新數據對歷史模型進行遷移更新,并且保留更新之后的基模型,使得集成模型更加專注于當前的數據.通過參數的控制可以靈活的選擇對歷史知識的保留,同時,在基模型的選擇上也選擇了更適合數據流分類的自適應霍夫丁決策樹,相比于DTEL利用普通決策樹作為基模型更適用于數據流分類的環境.HAEL的整體框架如算法1所示.

算法1.HAEL集成框架

輸入:(D1,D2,…,Dt,…)代表數據流在t時刻的窗口數據,S代表的是集成模型中基模型的集合.

輸出:在每一個時刻t的集成模型St

1.Whilet時刻的窗口數據Dt可用時 do

2. 基于數據Dt訓練一棵新的霍夫丁決策樹st;

5. 根據集成模型的規模更新S使其準確率最大化;

6.end

與傳統的基于窗口的集成模型相比,首先,HAEL并沒有直接利用集成模型中的歷史模型進行預測,也沒有重新訓練集成模型,而是對歷史模型進行遷移以快速適應當前最新窗口的數據,如圖1所示.然后使用基于最新窗口的數據訓練得到的基模型替換掉遷移之后的基模型中準確率最低的基模型(如圖1(b)中虛線圓圈代表的基模型),得到新的集成模型St.其次,新的集成模型會根據準確率對集成模型以固定的規模進行更新,使得預測準確率最低的某個歷史模型被最新窗口的數據訓練得到的基模型替換掉.

圖1 數據流分類集成模型說明Fig.1 Ensembled model of data stream classification

(1)

其中,Ε(·)表示一個隨機變量的期望值,l是損失函數.假設數據流的底層數據分布式以Ft(x,y)序列來表示,整個增量數據流分類過程的目標如公式(2)所示.

(2)

3.2 自適應霍夫丁決策樹

適當的數據窗口大小對概念漂移有一定的應對能力,然而當概念漂移出發生在窗口中間位置附近時,即基于當前窗口數據訓練的基模型是在兩種不同底層數據分布下建立的,則集成模型的準確率會受到影響.由于窗口大小固定,實際的數據流隨時都有可能發生概念漂移,所以這種情況難以避免.為了解決該問題,本文選擇自適應霍夫丁決策樹作為HAEL的基模型.自適應霍夫丁決策樹會在每一條樣本數據到來時對其所有子節點進行重新評估,當檢測到概念漂移時對子節點進行替換或者刪除.這種針對概念漂移的處理方式可以在概念漂移發生在數據窗口中時,對基模型有一定的調節能力,使其適應新的概念.相比于DTEL中的普通決策樹或者是針對數據流處理的霍夫丁決策樹,自適應霍夫丁決策樹可以更好的應對在同一窗口數據內發生概念漂移帶來的模型準確率降低的問題.

3.3 注意力增量學習

數據流的一個特點就是數據是源源不斷到達,利用所有的數據建立模型是不可能的.并且數據流經常伴隨著概念漂移發生,如何使模型更快更好的適應當前數據流中的概念是需要解決的問題.本文將注意力集中在最新窗口的數據上,在數據流發生概念漂移時,使得模型能夠快速的適應且保證較高的準確率.

在構造集成模型的初始階段,基模型的數量還沒有達到規定的閾值.每次到達一個窗口的數據,訓練一個最新的基模型,之前訓練得到的基模型也會利用當前的窗口數據進行更新.當基模型的數量達到了集成模型規定的閾值,在當前窗口的數據上訓練得到的基模型會替換掉之前的某一個歷史基模型.因此,在整個集成模型當中始終存在著在不同窗口的數據上建立的基模型,與基于Bagging,Boosting的集成模型采用對數據進行采樣或者增加權重等方式相比,HAEL的模型構建方式更加直接,并且可以利用到所有的數據樣本而不需要采樣.

為了將注意力始終聚焦在當前窗口數據上,當新的窗口數據到達完畢,HAEL集成模型并不直接使用歷史模型與當前窗口數據訓練得到的模型進行組合來對樣本進行預測,而是采用一種知識遷移的方法,將歷史基模型進行遷移以適應當前窗口數據的分布.決策樹的構建過程是遞歸的把特征空間劃分為更小的子空間的過程,每一個子空間對應一個葉子節點且擁有一個類標簽.決策樹的這種結構天然包含了歷史知識片段,本文為了將注意力遷移到當前窗口數據中,使用當前窗口的數據對歷史基模型進行更新,然后使用更新后的基模型與當前窗口數據訓練得到的基模型進行組合構建集成模型.主要包括以下兩個過程:

1)將最新窗口中的樣本在歷史基模型中執行到葉子節點,并按照樣本的標簽更新歷史基模型葉子節點的類標簽.這種知識遷移的思想可以利用歷史知識快速適應新知識.

2)為了對最新窗口的數據正確分類,需要在歷史基模型的葉子節點繼續訓練一棵子樹,直到達到決策樹的停止生長標準.

選擇更新之后的歷史基模型中性能最差的一個被基于當前窗口數據訓練得到的基模型替換掉.保證模型中始終存在某個單模型建立在最新的窗口數據上,并且隨著時間的推移,建立在歷史窗口數據上的基模型逐漸被替換掉,模型的注意力將持續關注于當前的數據.針對不同的數據集,對當前的數據的關注程度也是需要調整的,所以添加比較范圍參數來確定在哪些樣本上進行更新后的歷史基模型的評價.通過該參數可以調整評價歷史基模型的數據范圍,調整關注當前數據的程度.合理的比較范圍也可以適當的保留過去的信息.所以建立的模型始終都是將整體的注意力放在當前窗口的數據上,而對當前窗口數據的注意程度則由參數控制.和非增量式的集成模型相比,HAEL不需要概念漂移的檢測來決定集成模型何時更新,也不需要采樣保證基模型的多樣性,每一個基模型都是建立在不同的窗口數據上的.加入比較范圍參數更可以使得集成模型更加的靈活,在應對不同的數據流的時候都有更好的應對能力.如果將比較的范圍參數較大,則歷史窗口數據的結果會更重要,當前窗口數據的注意力相對較小;相反,如果設定較小的范圍參數,則注意力更加關注當前窗口數據,歷史知識的影響較小.

3.4 預測策略

在進行預測階段,HAEL集成模型中的每一個基模型對窗口數據Dt進行預測.將每一個模型中預測過的所有的數據的歷史準確率進行歸一化處理,之后得到每一個模型的預測的權重作為每一個基模型的預測權重,根據其預測結果得到最終的預測數值,根據預測數值和0.5進行比較得到最終的預測結果.這種預測策略是比較常見的加權投票,在一般的集成模型中每一個基模型預測的樣本的數量是相同的,所以每一個基模型在計算歷史數據準確率時是具有相同的地位的.在HAEL的整體集成策略中,每一個基模型進行預測的樣本的數量是不同的,集成模型中存在時間越長的模型其預測過的樣本就越多,如果在平穩非概念漂移的情況下,該模型因為通過大量數據訓練所以擁有較好的準確率,從而不易被替換,然而在概念漂移的情況下,也是因為在過去數據上建立的模型可能由于對過去數據的擬合效果比較好所以在面對當前發生概念漂移的數據流上泛化能力較弱,準確率會下降,從而在替換策略中會被優先替換.

3.5 HAEL算法實現

HAEL的實現過程見算法2,假設t個窗口數據D1,D2,…,Dt不斷到達,HAEL首先基于第一個窗口數據訓練一棵霍夫丁自適應決策樹s1,當新的窗口數據Dt樣本全部到達,之前的決策樹要基于Dt進行遷移以適應最新數據,同時,基于Dt重新訓練一棵新的決策樹st.然后將兩者使用AUE2中使用的加權投票策略進行組合,因為該策略在增量集成模型中展示了最好的總體準確性[11].之前的決策樹更新后的權值計算如公式(3)所示,基于當前窗口數據重新訓練得到的決策樹的權值計算如公式(4)所示.

(3)

(4)

(5)

(6)

(7)

算法2.HAEL算法

輸入:(D1,D2,…,Dt,…)代表數據流在t時刻的窗口數據,S代表的是集成模型中基模型的集合.M代表指定的集成模型中的基模型的數量.Rel代表指定的準確率比較范圍.

輸出:在每一個時刻t的集成模型St

1.whilet時刻的窗口數據Dt可用時do

2. 基于數據Dt訓練一棵新的霍夫丁決策樹st;

4.if模型的數量少于Mthen

6.if當前時刻的模型數量大于Mthen

10. 如公式(4)計算st的權重;

11. 如公式(7)所示得到此時刻的集成模型St;

12.returnSt;

3.6 復雜性分析

4.1 實驗平臺

實驗使用大規模在線分析平臺MOA[19],MOA是最流行的數據流挖掘開源框架.

4.2 實驗數據

實驗使用了三個人工數據集,其詳細信息如表1所示.其中SEA200G表示在SEA數據集上,窗口大小為200條樣本,R表示是循環漂移,G表示是漸進漂移,A表示是突變漂移,SEA-R;SEA-G表示在SEA數據流中同時存在循環概念漂移和漸進概念漂移.

LED Generator:生成一個預測在7段LED顯示屏上的數字的問題.其中的每個屬性有10%的幾率被倒置.它的貝葉斯分類率為74%.用于實驗的生成模型的特殊配置產生了24個二進制屬性,其中17個是無關的.

SEA Generator[22]:此數據集包含突變概念漂移.他一般使用三個屬性,所有的屬性值都在0和10之間.其中只有兩個屬性是相關的(如x1和x2),x3則只是含隨機值的噪聲屬性.數據集被分為四個不同概念的塊.在每個塊中,使用f1+f2≤θ分類,其中f1、f2是前兩個屬性,θ是閾值.在數據塊中9,8.7,9.5是常見的值.類標簽由公式決定:ax1+bx2≤/≥θ.

Sine Generator[20]:在二維特征空間中,通過正弦曲線來確定數據的標簽,定義如下:asin(bx1+θ)+c≤/≥x2.在實驗中,兩個維度和的所有數據都在范圍(-5,5)中.θ是均勻變化的價值生成數據分布的變化.

STAGGER Boolean Concepts(STA)[20,21]:生成具有分類特征的數據使用一組規則來確定類標簽.根據文獻[10,19],特征值為:顏色{紅色(R)、藍色(B)、綠色(G)}、形狀{圓形(C)、正方形(S)、三角形(T)}、大小{小(S)、中(M)、大(L)}.決策規則可以表述為:y=((color=1/≠1a)∨1/∧1(shape=2/≠2b))∨2/∧2(size=3/≠3c)通過改變規則項來模擬概念漂移.

表1 數據集
Table 1 Data sets

數據集特征數樣本數量類別概念漂移類型LED40024160002LED-R;LED-GLED5024160002LED-R;LED-ASEA2003160002SEA-R;SEA-GSEA503160002SEA-R;SEA-ASTA4003160002STA-R;STA-G

4.3 實驗結果分析

整個實驗主要是在四種不同的人工數據集上進行測試.分別與目前經典的和最新的數據流分類算法:自適應隨機森林(Adaptive Random Forest,ARF)、Leverage Bagging(LB)、Online Smooth Boosting(SMOOTH)、OzaBoost(BOOST)以及OzaBag(OB)進行對比.

其中表2和表3是在LED數據集上,分別存在循環出現的漸進概念漂移和循環出現的突變概念漂移時,算法在執行時間和準確率上的結果對比.表4和表5是在SEA數據集上,分別存在循環出現的漸進概念漂移和循環出現的突變概念漂移時,算法在執行時間和準確率上的結果對比.表6是在STA數據集上,存在循環出現的漸進概念漂移,算法在執行時間和準確率上的結果對比.可以看出在大部分情況下HAEL都具有更高的準確率,但是執行時間只有在SEA數據集上循環突變概念漂移的情況下是最快的,其余雖然不是最快的,但是與其它模型的執行時間相差不大.

表2 LED中循環漸進概念漂移的時間和準確率
Table 2 Time and accuracy of recurrent and
gradually concept drift in LED

集成模型 時間(s)準確率(%)HAEL3.9871.40ARF2.3366.06LB5.6471.18SMOOTH3.7870.38BOOST2.4570.51OB2.4170.34

表3 LED中循環突變概念漂移的時間和準確率
Table 3 Time and accuracy of recurrent and abrupt concept drift in LED

集成模型時間(s)準確率(%)HAEL3.4471.84ARF2.6666.68LB5.3171.80SMOOTH34.0570.80BOOST2.3970.43

表4 SEA中循環漸進概念漂移的時間和準確率
Table 4 Time and accuracy of recurrent and gradually concept drift in SEA

集成模型時間(s)準確率(%)HAEL3.5585.06ARF10.8883.24LB11.0083.52SMOOTH3.8884.36BOOST2.9883.53OB3.6783.51

圖2和圖3是在LED數據集上,分別存在循環出現的漸進概念漂移和循環出現的突變概念漂移時,算法執行準確率的結果對比;圖4和圖5是在SEA數據集上,分別存在循環出現的漸進概念漂移和循環出現的突變概念漂移時,算法執行準確率的結果對比;圖6是在STA數據集上,存在循環出現的漸進概念漂移時,算法執行準確率的結果對比.通過觀察實驗結果圖,可以更加直觀的看出,多數情況下,在發生概念漂移時,HAEL在模型預測準確率方便表現出色且更加穩定.相比于對具有漸進和循環特點的LED數據進行預測,突變的概念漂移會突然發生,固定的窗口大小下建立模型相比于利用采樣的方法Leverage Bagging并不具有優勢.雖然采用了自適應霍夫丁決策樹來盡量應對這一問題,但是效果還是有限.

模型的整體框架是增量式的集成學習.在初始階段根據不斷到達的樣本逐漸構建.在樣本沒有達到一定數量的時候即模型沒有達到規定的集成數量時模型不會依據設定的更新策略進行更新.這也導致在實驗中,模型在樣本數量較小的時候準確率比較低,此時模型并沒有構建完整.

表5 SEA中循環突變概念漂移的時間和準確率
Table 5 Time and accuracy of recurrent and abrupt concept drift in SEA

集成模型時間(s)準確率(%)HAEL1.0985.58ARF11.6783.89LB11.5284.26SMOOTH3.9785.03BOOST3.2384.14OB3.3483.94

表6 STA中循環漸進概念漂移的時間和準確率
Table 6 Time and accuracy of recurrent and gradually concept drift in STA

集成模型時間(s)準確率(%)HAEL0.8892.08ARF0.9891.55LB1.5092.01BOOST0.5390.14SMOOTH0.6984.06OB0.5885.09

圖2 LED上循環漸進概念漂移的準確率Fig.2 Accuracy of recurrent and gradually concept drift in LED

圖3 LED上循環突變概念漂移的準確率Fig.3 Accuracy of recurrent and abrupt concept drift in LED

圖4 SEA上循環漸進概念漂移的準確率Fig.4 Accuracy of recurrent and gradually concept drift in SEA

圖5 SEA上循環突變概念漂移的準確率Fig.5 Accuracy of recurrent and abrupt concept drift in SEA

圖6 STA上循環漸進概念漂移的準確率Fig.6 Accuracy of recurrent and gradually concept drift in STA

5 總 結

本文針對數據流中的概念漂移問題,提出了在面對不同類型的循環概念漂移時具有更高準確率的HAEL集成模型.在基于增量學習的基礎上,利用知識遷移以達到快速的模型更新;同時,添加比較范圍參數來進行模型替換,使得模型對歷史知識和當前知識的注意力可以調節,在應對概念漂移時有比較靈活的自適應能力;并且采用自適應霍夫丁決策樹作為集成模型的基模型,進一步提高整體模型對概念漂移的自適應能力.