基于自適應深度集成網絡的概念漂移收斂方法

郭虎升 孫 妮 王嘉豪 王文劍

1 （山西大學計算機與信息技術學院 太原 030006）

2 （計算智能與中文信息處理教育部重點實驗室（山西大學） 太原 030006）

（guohusheng@sxu.edu.cn）

隨著大數據時代來臨，傳感器數據、在線交易數據、社交媒體數據、用戶在線行為數據等源源不斷地產生. 不同于傳統的靜態數據，這些數據具有實時性、無限性、不可再生性等特點，稱之為流數據. 近年來，互聯網產業與人工智能技術迅猛發展，流數據挖掘的研究價值正變得愈來愈重要.

在流數據挖掘任務中，學習器往往需要進行動態調整以適應數據的實時變化. 例如，對于推薦系統，用戶的喜好可能隨著時間改變，導致數據分布隨著時間變化，不同時刻的數據不再滿足獨立同分布假設，數據分布的這種變化將導致后驗概率的變化，因此先前訓練得到的學習模型不再適用于新分布的數據，流數據的這種分布變化被稱為概念漂移[1-3].

目前許多在線學習模型都基于集成學習技術，利用多個學習器的加權或投票來取得比單個學習器更好的性能[4-5]. 同時，根據學習模型是否主動對概念漂移進行檢測，在線學習方法可分為基于漂移檢測的主動在線集成方法和自適應的被動在線集成方法.基于漂移檢測的主動在線集成方法大多通過模型性能指標（例如準確率）的變化來檢測概念漂移，當模型性能發生大幅度波動時，說明流數據可能發生概念漂移，此時模型會用一個新的學習器來替換效果最差的舊學習器[6-10]. 然而，這種主動在線集成方法易受噪聲或數據塊大小的影響，造成學習器性能的大幅度波動，并且可能不能對概念漂移正確判斷，導致模型性能不佳. 自適應型的被動在線集成方法[11-14]不直接檢測概念漂移位點，而是根據流數據的變化情況動態地調整模型權重. 然而，這種方法難以利用歷史信息去調節每個學習器權重以達到適應性和穩定性之間的平衡，并且不能很好地處理概念漂移. 此外，大多數在線學習方法都是基于線性分類器或者簡單的非線性分類器（例如決策樹、支持向量機、聚類等）[15-17]，這些分類器表征能力較弱，且難以處理較復雜的流數據挖掘任務.

近年來，深度學習技術在圖像分類[18]、目標檢測[19]、機器翻譯[20]等領域取得了巨大成功. 與其他方法相比，深度學習技術擁有強大的表征能力，可以應用于許多復雜任務. 傳統的深度學習方法使用大規模數據集對模型進行訓練，并通過驗證集來選擇合適的模型架構（例如網絡層的數量、每層神經元數量等），使模型能夠有較好的泛化性能. 然而，在流數據挖掘任務中，模型每次只能在新進入的1 個或者一小部分數據上訓練和更新模型，無法利用驗證集來進行模型架構選擇，這就要求模型必須能夠實時地動態調整以適應不斷變化的數據流.

在線深度學習方法利用深度神經網絡強大的表征能力去處理流數據以得到更好的效果. 盡管可以利用反向傳播算法[21]對流數據直接優化損失函數，但這種方式仍存在一些問題. 首先，在流數據挖掘任務中，模型單次只能處理1 個或一小批數據，這就要求模型要有很靈活的結構，能夠在動態變化的環境中進行實時調整. 然而，不同層次的深度網絡模型往往有不同的收斂速度和表征能力以適用于不同場景.對于較淺層的深度網絡，模型收斂速度較快，能夠快速地達到較好的性能，但表征能力較差，難以處理復雜分布的問題，較適用于概念漂移剛發生時的場景，以使模型性能在漂移發生后快速回升. 對于深度網絡，收斂速度往往比淺層網絡要緩慢，但具有比淺層神經網絡更強大的表征能力，因此更適用于數據流趨于穩定之后的場景. 此外，深度網絡所面臨的梯度消失等問題，也會影響其在流數據挖掘任務上的性能.

本文將梯度提升思想[22]引入含概念漂移的流數據挖掘問題中，提出了一種基于自適應深度集成網絡的概念漂移收斂方法（concept drift convergence method based on adaptive deep ensemble networks，CD_ADEN）.CD_ADEN 方法將若干淺層網絡作為基學習器進行集成，后序基學習器在前序基學習器輸出基礎上不斷進行糾錯，以提升學習模型在含概念漂移數據流分類任務中的實時泛化性能. 此外，由于每個基學習器均為淺層網絡，有較快的收斂速度，在概念漂移發生后，學習模型能夠較快地從漂移造成的性能下降中恢復. 實驗結果表明，對于不同的評價指標，該方法平均排名均為第一. 在Sea，RBFBlips，Tree，Covertype等數據集上，最終累積精度相對于對比方法分別提高了1.63%，0.73%，3.48%，2.2%. 本文的主要貢獻包括2 個方面：

1） 通過在前序輸出的基礎上對損失函數進行優化來替代學習損失函數梯度的方法，提升學習模型對前序學習器輸出的糾錯性能.

2） 將梯度提升思想引入含概念漂移的流數據挖掘任務中，后序基學習器在前序學習器輸出的基礎上不斷糾錯，為解決含概念漂移的流數據挖掘問題提供了一個新思路.

1 相關工作

隨著互聯網技術的迅速發展，越來越多的機器學習任務的數據以流數據的形式呈現，概念漂移作為流數據挖掘領域中的一個重要難題，受到越來越多的關注. 針對含概念漂移的流數據挖掘任務，目前已經有較多研究. 根據是否對概念漂移的發生進行檢測，大致可分為基于主動漂移檢測的方法和被動漂移適應的方法[23].

基于主動漂移檢測的方法將概念漂移檢測融入模型中，通過對學習模型的性能指標進行監測來判斷是否發生概念漂移. 一旦檢測到模型的性能指標出現大幅度下降，就認為數據流中發生了概念漂移，并對模型做出相應調整. 典型的如：滑動窗口方法[24]通過窗口不斷向前滑動，利用標準差等指標判斷是否發生概念漂移，若發生了概念漂移，就將已失效的樣本丟棄以適應新的數據分布；增量貝葉斯方法[25]首先通過處理歷史數據得到先驗概率，再結合半監督方法計算后驗概率來檢測概念漂移；基于滑動窗口的ACDWM 算法[4]通過設置1 個滑動窗口來保存最新的數據，當任意2 個子窗口中數據的平均值的差別大于一定閾值的時候，就認為發生了概念漂移，就會丟棄過時的數據；CD-TW 算法[26-27]構建2 個相鄰的時序窗口，通過比較2 個窗口所對應數據的分布變化情況來檢測概念漂移節點. 文獻[4, 24-27]所述的這些方法雖然能在一定程度上處理概念漂移問題，但仍存在概念漂移誤報、概念漂移檢測延遲和處理概念漂移類型單一等問題.

被動漂移適應的方法并不直接對概念漂移進行檢測，而是通過逐漸更新學習器以及根據每個基學習器的實時表現動態更新權重來適應概念漂移. 典型的如：SEA 算法[28]在每個數據塊上都訓練一個分類器，然后將其加入集成學習模型中，當集成學習模型中的基學習器的數量達到上限時，替換表現最差的基學習器；動態加權投票算法DWM[29]根據每個基學習器的實時表現來動態地調整權重，在更新權重的同時，將權重小于某一閾值的基學習器移除；CondorForest 算法[30]通過決策樹模型重用機制動態調整模型中的基學習器；重用模型Learn++.NSE 算法[31]是一種基于AdaBoost 的動態加權算法，該算法根據每個基學習器與當前數據分布的一致性來對基學習器進行加權，并且在訓練階段通過一種遺忘機制來處理已過時的基學習器，在不同類型的概念漂移都取得了較好的效果. 文獻[28-29, 31]所述的這些方法在對基學習器進行加權時無法有效利用基學習器的歷史信息達到適應性與穩定性之間的平衡，往往不能很好地處理概念漂移.

盡管以上方法可以很好地解決概念漂移問題，但多數算法都是通過在線凸優化方法來訓練的一些簡單模型，對于復雜非線性任務往往難以處理. 而深度網絡模型能夠很好地擬合復雜的非線性函數，但往往需要對大量數據進行批量訓練. 目前用于專門處理流數據的深度網絡模型仍比較少，根據是否對網絡架構進行動態調整可分為動態調整的在線深度網絡和結構穩定的在線深度網絡. 動態調整的在線深度網絡不斷對網絡參數進行調整以適應最新的數據分布，并根據網絡實時性能來決定調整速率，典型的如MOS-ELM 算法[32]、ELM 算法[33]、ADL 算法[34]、AO-LEM 算法[35]等. 結構穩定的在線深度網絡并不對網絡架構進行直接調整，而是通過集成學習思想將多個（層）網絡結合起來，通過調整網絡權重來適應流數據中的概念漂移，典型的如HBP 算法[36]、SEOA算法[37]等.

本文將梯度提升思想引入含概念漂移的流數據挖掘問題，提出了一種基于自適應深度集成網絡的概念漂移收斂方法，通過集成多個淺層網絡，將后序基學習器的輸出加到前序輸出上對損失函數進行優化，以提升學習模型的實時泛化性能. 與傳統方法相比，該方法通過對前序學習器輸出進行不斷糾錯，加速模型收斂，并為解決含概念漂移的流數據挖掘問題提供了一個新思路.

2 基于自適應深度集成網絡的概念漂移收斂方法

盡管深度學習在圖像分類、目標檢測、機器翻譯等領域取得了較大成功，但在流數據場景下，深度學習算法難以通過驗證集來對模型的架構進行選擇，深層網絡與淺層網絡分別適用于不同場景，在線深度學習算法需要根據數據流的變化實時調整自身架構以達到收斂速度與表征能力間的有效平衡.

為解決上述問題，本文將梯度提升思想的糾錯機制引入含概念漂移的流數據分類中，提出了一種基于自適應深度集成網絡的概念漂移收斂方法. 該方法集成多個淺層網絡作為基學習器，后序基學習器在前序基學習器輸出的基礎上進行糾錯，雖然淺層網絡表征能力較弱，難以擬合復雜的非線性映射，但是通過集成多個淺層網絡進行多輪糾錯操作，最終的學習模型在經過多輪更新后能夠得到較好的實時泛化性能. 此外，由于淺層網絡收斂速度快，模型能夠較快地從概念漂移造成的精度下降中恢復過來，較好地解決了其他在線深度學習方法在處理含概念漂移的流數據問題時難以兼顧模型精度與恢復速度這一問題，從而能夠適用于含概念漂移的流數據挖掘任務之中. 模型的基本架構如圖1 所示.

Fig.1 Framework of concept drift convergence method based on adaptive deep ensemble networks圖1 基于自適應深度集成網絡的概念漂移收斂方法框架圖

2.1 模型架構

基于自適應深度集成網絡的概念漂移收斂方法集成m個淺層網絡作為基學習器，第i個基學習器的輸出為fi(x,θi),i=0,1,…,m，其中 θi為第i個基學習器的對應參數，對于分類問題，這里的輸出指Softmax操作之前的網絡輸出，每個基學習器對應一個權重 αi，因此模型的輸出為

前序學習器的隱藏層輸出與原始輸入x合并在一起作為后序基學習器的輸入. 由于后序基學習器的輸入部分來自前序基學習器，因此每添加1 個基學習器可視為增加了1 層網絡深度，即對輸入數據進一步地處理與變換，提高了模型容量. 通過各學習器的實時性能來動態調整權重 αi，以動態控制模型容量.

從圖1 可以看出，后序基學習器的任務相當于在前序基學習器輸出的基礎上進行糾錯，假設

為第m-1 個基學習器的輸出，那么第m個基學習器的學習目標即為在添加對應的輸出以及權重之后的輸出：

能夠進一步減小損失函數，即在添加上后序基學習器的輸出之后，能夠對前序輸出糾錯，以得到較好的實時泛化性能. 在該模型中，即使單個淺層網絡難以達到較好的性能，但在添加上多個基學習器的輸出，經過多輪糾錯操作后的實時泛化性能可能較之前有明顯提升. 此外，由于淺層網絡的收斂速度較快，因此所提出的模型能夠較快地從概念漂移造成的性能下降中恢復，有效兼顧了模型性能與收斂速度，可有效處理含概念漂移的流數據分類.

2.2 糾錯操作

為使添加后序基學習器輸出后損失函數的結果有所下降，梯度提升思想借鑒最優化理論中梯度下降算法，每個基學習器相應的損失函數利用前序輸出的梯度信息來進行優化，以提升模型性能.

其中L為損失函數. 為做到這一點，梯度提升算法采用梯度下降法近似逼近最優解，對于j=1,2,…,m,令

代表第j個基學習器上輸出損失的梯度. 由于梯度下降只關心梯度的方向信息而不關心梯度的具體大小，因此這里可以設置一個縮放因子 β，按照式（6）訓練第j個基學習器：

在訓練好第j個基學習器后，利用線搜索來求得梯度下降步長對應權重 αj：

在求得步長之后，利用式（8）更新模型：

在經過m步梯度下降，即訓練好m個基學習器之后,即可得到最終的模型.

然而，梯度提升思想不能直接應用于流數據挖掘中，這是由于流數據分類的高實時性要求模型能夠1 次只訓練1 個或一小批數據，且數據流分布動態變化，這使得后序基學習器輸出的梯度信息包含較大誤差，難以對損失函數在前序輸出處的梯度信息進行準確學習. 為此，本文改進了梯度提升機思想，使其能夠適用于含概念漂移的流數據分類.

具體地，在分類任務中，假設在時刻t基學習器f0,f1,…,fj-1的參數均已更新完畢，fj的參數按照式（9）更新，即首先利用時刻t-1 的參數計算

即先添加時刻t-1 的模型的輸出結果，并令

為fj的分類輸出，利用

以及

對fj的參數以及權重進行更新，將更新后的fj添加到模型中即得到

在經過m輪更新后，模型最終的輸出結果即為S o ftmax(Fm(x)).

該方法通過直接對損失函數進行優化來更新各基學習器的參數，使得更新后的基學習器損失減小.相較于傳統的梯度提升思想通過學習梯度信息來減小損失的方式，本文直接對損失函數優化，避免了流數據挖掘中基學習器難以準確學習梯度信息的問題.

2.3 算法總結

根據流數據到達的先后順序將數據塊賦予一個時間戳，流數據可以表示為

按照流數據的這種表示形式，可以將本文所提出的基于自適應深度集成網絡的概念漂移收斂方法總結如算法1 所示.

算法1. 基于自適應深度集成網絡的概念漂移收斂算法.

輸入：初始化各基學習器，設每個學習器輸出的logits 為fi(x,θi),i=0,1,…,m，并且將權重初始化 為αi=1/m,i=1,2,···,m；

輸出：模型輸出結果S o ftmax(Fm(x)).

① fort=1,2,…,T

3 實驗結果與分析

為測試本文所提出的CD_ADEN 方法的性能，本文在多個真實數據集以及合成數據集上對模型的實時精度、累積精度及概念漂移發生后的恢復性等評價指標進行了測試. 所采用的深度學習框架為Tensorflow，實驗所用計算機的配置為Intel?CoreTMi5-8300H 2.30 GHz CPU, 16 GB DDR4L RAM 以及 NVIDIA GeForce GTX1050 Ti 4GB GPU.

3.1 數據集及對比方法

本文所用的數據集既有真實數據集，又有模擬概念漂移的合成數據集，包含了突變型概念漂移與漸變型概念漂移，數據集[37]的具體信息見表1.

Table 1 Datasets Used in Experiment表1 實驗采用的數據集

在本文中將所提出的方法CD_ADEN 與4 種在線深度學習方法HBP[36]，Resnet[38]，Highway[39]，DNN進行了對比，實驗中數據塊大小為 100，隱藏節點為100，使用ReLU 激活函數，設置固定學習率為0.001.

3.2 評價指標

本文從3 個指標對模型的泛化性能及概念漂移發生后模型的收斂性能進行測試與分析.

1） 平均實時精度. 平均實時精度即實時精度在每個時間節點上的平均值，定義為

其中acct為模型在時間節點t的實時精度. 平均實時精度越高，反映模型的實時性能越好. 由于本文使用的數據集多為類別不平衡的數據集，因此本文中的實時精度acct使用的是Balanced Accuracy Score[40]，acct被定義為各類別的平均值：

其中k為類別數目，cij指混淆矩陣中索引為(i,j)的元素為混淆矩陣第i列元素之和.

2） 最終累積精度. 最終累積精度即最終模型預測正確的樣本數與總樣本數的比值，即

其中n為每個數據塊中的數據數量，nt為模型在時間節點t對應的數據塊中分類正確的樣本數目. 最終累積精度越高，代表模型的整體分類性能越好.

3） 漂移恢復率. 一個好的在線學習算法不僅需要有較高的準確率，并且需要能夠較快地從概念漂移造成的影響中恢復，因此漂移恢復率Drr指標定義為

其中step代表模型從概念漂移造成的影響中恢復所需的時間步長，avg代表恢復過程中模型的平均錯誤率. 漂移恢復率取值越小，表示模型在漂移發生后，越能夠快速恢復到漂移之前的性能.

3.3 實驗結果及分析

為驗證本文所提方法的合理性，本節從實時精度、累積精度以及漂移恢復率3 個指標進行了實驗分析.

3.3.1 實時精度的結果與分析

模型的超參數往往對模型的性能有著至關重要的影響，本節在不同數據集上分析基學習器數量下模型的性能表現. 表2 展示了不同基學習器數量下模型的平均實時精度情況，本文分別測試了包含4個、8 個、12 個基學習器時模型的平均實時精度. 從表2 可以看出，在多數數據集上，基學習器數量n＞8時，性能差距不明顯. 因此，后續與其他方法對比時本文所提出的模型均包含8 個基學習器.

Table 2 Average Real-Time Accuracy with Different Numbers of Base Learners表2 不同基學習器數量下的平均實時精度

圖2 展示了不同方法的實時精度變化趨勢. 從圖2 中可以看出，不同方法實時精度波動趨勢基本一致，但CD_ADEN 方法波動較小，因此較好地處理了流數據中包含的不同類型概念漂移.

Fig.2 Comparison of real-time accuracy of different methods圖2 不同方法的實時精度比較

表3 展示了不同方法的平均實時精度以及相應排序情況. 可以看出，在多數情況下CD_ADEN 方法的平均實時精度最好. 然而在LED_abrupt，Electricity，Kddcup99 和Weather 上，CD_ADEN 方法并未取得最優結果，這可能是由于數據集的分布不同，較少基學習器模型不能很好地表示數據分布，而較多基學習器則會降低收斂速度，并且導致較低的平均實時精度.

Table 3 Average Real-Time Accuracy Comparison of Different Methods表3 不同方法的平均實時精度比較

本文通過非參數測試方法Friedman 檢驗[41]進行統計測試. 對于給定的k個算法和n個數據集，是第j個算法在第i個數據集上的排名，第j個算法的平均序值零假設H0為如果所有的方法性能相同，那么它們的平均序值是相等的. 在零假設下，當k和n足夠大時，FF服從自由度為k- 1 和（k- 1）（n- 1）的F分布：

其中

若零假設H0被拒絕，計算出的統計量大于FF的臨界值，表明學習方法在性能上有顯著差異，對上述方法的平均實時精度進行測試，得到統計值FF=9.75.由于其在顯著水平 α=0.05 處的臨界值為2.272，因此拒絕了算法之間性能不可區分的零假設.

此外，所有方法的臨界差（CD）都是通過Bonferroni-Dunn 檢驗計算的，用來顯示CD_ADEN 方法和對比方法之間的相對性能，如果2 個算法的平均序值之差超過了臨界差CD，則2 個分類器的性能有顯著差異：

其中qα是顯著級 α的臨界值. 可得在 α=0.05 時CD=2.195. 統計分析的結果如圖3 所示. 其中，平均序值在一個臨近值域內的方法用黑線連接. 結果表明，CD_ADEN 方法的平均實時精度顯著優于DNN8，Resnet，DNN4.

Fig.3 Bonferroni-Dunn test result for average real-time accuracy圖3 平均實時精度的Bonferroni-Dunn 檢驗結果

3.3.2 累積精度的結果與分析

表4 展示了不同基學習器數量n下模型的最終累積精度情況. 在大多數據集上，基學習器數量越大，模型的最終累積精度表現越好.

Table 4 Final Cumulative Accuracy with Different Numbers of Base Learners表4 不同基學習器數量下的最終累積精度

圖4 展示了不同方法的累積精度比較. 可以看出所有方法的累積精度趨勢相同，漂移發生后，CD_ADEN 的累積精度下降低于其他方法，這是由于后序基學習器在前序輸出基礎上不斷糾錯，提升了模型的泛化性能.

Fig.4 Comparison of cumulative accuracy on different methods圖4 不同方法的累積精度比較

表5 展示了不同方法的最終累積精度結果以及相應的排序. 通過平均序值的比較可以看出，CD_ADEN的性能最好，HBP 和DNN2 次之，DNN8 表現最差.CD_ADEN 在除了Hyperplane 的合成數據集上都取得最高的最終累積精度，在真實數據集Electricity，Weather 上表現稍差于DNN2 方法. CD_ADEN 通過將梯度提升算法的糾錯機制引入流數據挖掘任務中處理概念漂移，使模型具有較好的泛化性能. 然而，CD_ADEN 并不是均能保持最優精度，這可能是由于基學習器數量未選擇至合適數目，較少或較多的基學習器數量均會導致在部分數據集上取得較低的最終累積精度.

Table 5 Final Cumulative Accuracy Comparison of Different Methods表5 不同方法的最終累積精度比較

進一步分析計算出檢驗值FF=10.874 4，在顯著水平 α=0.05 處的臨界值為2.109，因此拒絕了方法之間性能不可區分的零假設. Bonferroni-Dunn 檢驗結果如圖5 所示，結果表明CD_ADEN 方法的最終累積精度顯著優于DNN4，DNN8，Resnet.

Fig.5 Bonferroni-Dunn test result for final cumulative accuracy圖5 最終累積精度的Bonferroni-Dunn 檢驗結果

3.3.3 漂移恢復率的結果與分析

在線學習模型不僅要考慮其準確率，同時也應該考慮概念漂移發生之后模型的恢復性能. 本文在突變型概念漂移數據集上對模型的恢復性能進行了測試. 當模型的實時精度恢復到概念漂移發生之前的 δ倍時即判斷為恢復，根據數據集的不同， δ相應被設置成不同的值.

表6 展示了不同基學習器數量n下模型的漂移恢復性能. 由表6 可以看出，不同于多層DNN，當模型的基學習器越多，就對應著更復雜、容量更大的模型，模型的恢復速度反而更快. 這可能是因為越多的基學習器對應越多的糾錯次數，可以使模型更快地從概念漂移導致的高錯誤率中恢復. 這也一定程度上印證了本文提出的糾錯機制是適用于含概念漂移的流數據挖掘問題的解決之中的.

Table 6 Drift Recovery Rate Under Different Numbers of Base Learners表6 不同基學習器數量下的漂移恢復率

表7 展示了CD_ADEN 與其他方法的對比. 可以看出，CD_ADEN 有較好的恢復速度，平均排名為各種方法中最高，能夠較好地應用于含概念漂移的流數據挖掘任務.

Table 7 Drift Recovery Rate of Different Methods表7 不同方法的漂移恢復率

進一步分析上述結果，比較CD_ADEN 和對比方法在漂移恢復方面的性能. 計算出FF=6.501 6，在顯著水平 α=0.05 處的臨界值為2.109，因此拒絕了方法之間性能不可區分的零假設. Bonferroni-Dunn 檢驗結果如圖6 所示，結果表明，CD_ADEN 方法的漂移恢復性能顯著優于DNN4，DNN8，Resnet.

Fig.6 Bonferroni-Dunn test result for drift recovery rate圖6 漂移恢復率的Bonferroni-Dunn 檢驗結果

4 總結與展望

本文針對流數據挖掘中概念漂移問題帶來的挑戰，將梯度提升的糾錯思想引入概念漂移問題的解決之中，提出了基于自適應深度集成網絡的概念漂移收斂方法CD_ADEN. CD_ADEN 方法通過集成多個淺層網絡構成集成學習模型，后序基學習器在前序輸出的基礎上對其進行糾錯以提升模型的實時泛化性能，在一定程度上緩解了傳統在線深度網絡難以兼顧模型精度與恢復性能的問題，從而更好地應用于含概念漂移的流數據挖掘任務當中.

作者貢獻聲明：郭虎升提出思路，設計方法，負責初稿寫作及論文修改；孫妮負責論文撰寫、數據測試及論文修改；王嘉豪負責代碼實現、數據測試及論文撰寫；王文劍負責寫作指導、論文修改審定.