基于McDiarmid 邊界的自適應加權概念漂移檢測方法

胡 陽，孫自強

（華東理工大學能源化工過程智能制造教育部重點實驗室, 上海 200237）

智能手機、運動手表、便攜式電腦等各種互聯網設備已經成為人們必不可缺的物品，部署在這些設備上的傳感器時刻感知周圍的信息，如汽車的環境溫度、濕度和兩車間距等。海量的信息被傳感器采集，以數據流的形式實時傳輸到終端進行處理分析，挖掘出潛在的信息。隨著信息技術的發展，越來越多的場景不僅面對靜態數據，還需要面對不斷到來的動態數據。因為數據流的持續抵達、高基數、統計特征變化等特點，數據處理需要在有限的計算和內存資源下，實時處理大量數據，并且能適應數據流發生的概念漂移，顯然傳統的數據挖掘方法不再適用。

概念漂移是指數據流的統計特征隨時間的變化。在考慮數據流分類問題時，需要思考如何設計概念漂移檢測器。概念漂移檢測器可分為兩類：第一類是在發生數據流變化時進行標記，并允許做出一些反饋，讓分類器適應數據流的變化，這類檢測器可以和分類器分開設計；第二類是檢測器與分類器一起設計，是分類器的一部分，即分類器自身就有適應數據流變化的能力，不需要檢測數據流中是否存在概念漂移。概念漂移檢測方法可分為主動方法和被動方法[1-3]，兩者的區別主要有3 點：第一，主動方法包含檢測機制和適應機制，在檢測到數據分布變化時對模型進行調整或者重建，通過判斷數據流中分類器的性能改變幅度是否超預定閾值來判定概念漂移的發生。被動方法只有適應機制，不檢測數據流中是否存在概念漂移，而是根據數據流的變化不斷地調整模型以適應環境。第二，主動方法適合處理突變型概念漂移，被動方法適合處理漸變型和重現型概念漂移。第三，主動方法適用于在線學習的框架中，而被動方法常用于基于塊的學習框架中。Yu 等[4]將主動檢測方法分成了3 類：第一類是基于錯誤率的概念漂移檢測方法；第二類是基于數據分布的概念漂移檢測方法；第三類是多假設檢驗漂移檢測方法?；阱e誤率的檢測方法以PAC（Probably Approximately Correct）學習理論[5]為基礎，在假設樣本分布平穩的前提下，通過分析模型性能指標是否超過某一閾值以判斷概念漂移的發生。Gama 等[6]提出了DDM（Drift Detection Method）方法，假定測量值服從伯努利分布，當樣本量足夠大時，二項分布將近似于高斯分布。該方法保留錯誤率的均值和方差的歷史最小值，并設定警告邊界和漂移邊界，若當前錯誤率超過設定的閾值，則給出相應反饋。當概念較長時，DDM 算法具有較高的檢測延遲。為解決這一問題，Barros 等[7]提出了RDDM（Reactive Drift Detection Method）算法，該算法為降低檢測延遲，丟棄了較長概念的舊樣本。然而，RDDM 舍棄大量舊樣本會導致模型泛化能力變差，出現較多的漏檢、誤報。為了提高檢測性能，Frias-Blanco 等[8]提出了HDDM（Drift Detection Method based on the Hoeffding’s inequality）算法，該算法假設檢測值是獨立隨機的有界變量，利用Hoeffding 不等式得到類Ⅰ和類Ⅱ錯誤率的統計檢驗邊界，以 1-δ 的概率對結果進行保證，并提出兩種方法分別檢測突變和漸進型漂移。Pesaranghader 等[9]在HDDM 算法中引入了滑動窗口，提出了FHDDM（Fast Hoeffding Drift Detection Method）算法，其相對于HDDM 算法減少了漏檢、誤報，但檢測延遲更高。

目前，主動檢測方法主要存在兩個問題：第一，大多數主動方法處理概念漂移有較大的檢測延遲；第二，主動方法更適用于處理突變型概念漂移，處理漸變型概念漂移會出現較多的誤報、漏報，影響分類器性能。本文從以上兩點出發改進主動方法，提出了基于McDiarmid 邊界的自適應加權概念漂移檢測方法（WMDDM）。WMDDM 通過衰減函數對分類結果加權，并根據反饋的檢測信號實時調整模型，提高模型對數據流的適應能力。實驗結果表明，WMDDM能降低檢測延遲、誤報率和漏檢率，并且能適應多種類型的概念漂移，提高分類器性能。

1 基于Hoeffding 界的漂移檢測方法

1.1 概念漂移

貝葉斯決策理論通常根據分類的先驗概率分布p(y)和條件概率分布p(X|y) 描述分類過程，分類決策與類別的后驗概率有關。給定樣本X，類別ci相應的后驗概率為：

概念是指樣本在某一時間點的整體分布 P ，P的改變稱為概念漂移。若t1時刻，存在隨機變量X使得式(2)成立，t1時刻前后數據的聯合概率分布不同，P 發生改變，t1時刻出現概念漂移。

根據分布情況的變化，概念漂移可分為實漂移和虛漂移兩種類型[10]。如圖1 所示，圖1(a)所示為兩類數據的初始分布，經過一段時間后，整體分布變為圖1(b)示出的分類邊界發生變化而數據分布不變，這種變化稱為實漂移。若經過一段時間后，分布變為圖1(c)示出的分類邊界不變而數據分布發生改變，則稱這類變化為虛漂移。

圖1 實漂移和虛漂移概念圖Fig.1 Conceptual diagram of real drift and virtual drift

根據概念的變化率，可將概念漂移分為突變型漂移、漸進型漂移、增量型漂移和重現型漂移[3]。圖2(a)所示為突變型漂移，表示數據分布突然發生改變。圖2(b)所示為漸進型漂移，類1 逐漸減少，類2 逐漸增多，導致分布差異不斷變大，直到類2 取代類1。圖2(c)所示為增量型漂移，其變化率較小，兩個數據分布的差異變化不顯著。圖2(d)所示為重現型漂移，指先前的概念在之后某個時間又再次出現。

圖2 概念漂移類型圖Fig.2 Concept drift type diagram

實際數據流中，概念漂移一般是混合出現，即多種類型的概念漂移可能出現在同一流中，理想的概念漂移檢測器應能適應多種類型的概念漂移。

1.2 FHDDM 算法

根據計算機學習理論[4]，當假設空間h在數據集D的經驗誤差為0，則稱h與D一致。然而，學習算法事先并不知道概念類C 的存在，在假設空間里不總能找到一個零錯誤率的假設，在考慮學習器有非零錯誤率假設時，需要找到一個邊界來限定學習器所需的樣本數量。

Hoeffding 不等式[11]刻畫了某個事件的真實概率及與每個伯努利實驗估計概率的差異。該不等式給出一個概率邊界，并說明多少訓練樣本才足以保證真實錯誤率和訓練錯誤率接近。

定理1（Hoeffding 不等式）：設X1,···,Xn是一列獨立隨機變量，且Xi∈[ai,bi] ，對于 ε ＞0 ，有：

式中：Pr表示概率值，E表示期望值。式(3)和式(4)中，樣本均值顯著性水平 δ 表示真實錯誤率和訓練錯誤率不一致的事件發生的最大概率。給定顯著性水平 δ 和樣本量n，由式(2)可求出錯誤邊界（Hoeffding 不等式得出）εδ：

FHDDM 算法通過固定大小的滑動窗口觀察n個分類結果，根據式(5)得到 εδ，假設表示窗口在t時刻觀測到的分類正確率，表示t時刻觀測到的歷史最大分類正確率。若，則未漂移；若≥εδ，則發生漂移。

2 基于McDiarmid 界的漂移檢測方法

2.1 加權機制

流數據處理模型的核心思想是支持數據的在線持續處理，主要場景是處理無界數據[9]。大多數檢測策略是維持一個固定窗口（如FHDDM 算法），這種檢測策略會受到窗口大小的影響，大窗口可以降低誤判次數，但檢測延遲高；小窗口檢測延遲低，但會增加誤判次數，并對噪聲敏感。因此，FHDDM 算法處理不同漂移類型數據集時需要調節不同的窗口值。若在檢測過程中引入自適應更新規則，能提高檢測效率和準確率[12-13]。

假設某分類器的分類結果如圖3 所示，使用FHDDM 分別對分類結果和加權分類結果進行概念漂移檢測，設n和 δ 分別為10 和0.2，由式(5)可求得錯誤邊界 εd（McDiamid 不等式得出）為0.28。t/f表示分類結果（1 為正確，0 為錯誤），p是窗口左端滑動到序號i位置時觀察到的分類正確率，pw是經過加權后的分類正確率，Δp=pmax-p，Δpw=pwmax-pw，真實漂移發生在序號i=12 處。使用Sigmoid函數w(x)計算各個數據的權值：

圖3 加權窗口描述圖Fig.3 Weighted window description diagram

若不考慮分類結果加權后的錯誤邊界計算問題，觀察圖3 中的 Δp和 Δpw，FHDDM 在序號18 處檢測到漂移。加權后，FHDDM 在序號17 處檢測到漂移。考慮加權后的錯誤邊界計算問題，Hoeffding不等式不再適用求解加權后的漂移邊界。下面將介紹McDiarmid 不等式及錯誤邊界的計算過程。

定理2（McDiarmid 不等式[14]）：設X1,···,Xn是一組獨立隨機變量，值域分別為R1,···,Rn。f:R1×···×Rn→R是一個滿足獨立有界差分條件的可測函數。設d=(d1,···,dn) 是f(Y) 與f(Y′) 的差異向量，若存在di＞0 ，?xi,xi’(i=1,···,n) ，其他自變量不變，有：

那么，存在加權后的錯誤邊界 εD＞0 ，滿足：

定理2 的證明需要用到以下引理：

引理1（Hoeffding 引理）：令隨機變量X滿足E[X]=0且a≤X≤b，對于 ?t＞0 ，有：

引理2（Markov 不等式）：對于非負隨機變量X，有：

證明：設Vi=E(f|X1,···,Xi)-E(f|X1,···,Xi-1) ，其中E(Vi|X1,···,Xi-1)=0[15]，那么：

引理1 可變換成：

對于 ?t＞0 ，

利用式(19)算得圖3 中加權后的漂移邊界εD=0.295 ＜0.316 ，在序號17 處能檢測到漂移的發生。

2.2 WMDDM 算法

Bifet 等[16]提出的窗口（ADWIN）算法可自適應調節滑動窗口，當檢測到警告信號時減小檢測窗口。由于該方法摒棄一部分數據，會產生欠擬合導致模型泛化能力降低、誤報次數增加且對噪聲敏感。WMDDM 算法檢測到警告信號時調節衰減參數λ、θ，調整模型以適應數據流的變化。

回顧式(6)，當 λ ＜1 時，w(x) 主要由 θ 調節，θ 越大，w(x) 下降速度越緩；當 λ ＞1 時，λ 越大，w(x) 下降速度越快。加權準確率pw由式(20)求得，f(x)={0,1}，1 表示分類成功，0 為失敗。

如圖4 所示，首先初始化WMDDM 檢測器，將分類結果添加至滑動窗口，當數據量等于窗口大小時，計算pw并更新歷史最大加權正確率。若pw＞，則未漂移；若-pw＞εdrift，將漂移信號反饋到分類器，并初始化檢測器；若-pw＞εwarning，發出警告信號，調節衰減參數 λ、θ ，更新檢測器。

圖4 WMDDM 算法流程圖Fig.4 WMDDM algorithm flow chart

3 實驗與結果分析

MOA[17]（Massive Online Analysis）是一個基于Java 開發的數據流挖掘平臺，該平臺集成了各種數據流算法、數據流生成器以及評估機制。本節將WMDDM 與FHDDM、HDDM、DDM、RDDM 以及ADWIN 進行對比實驗，從誤報率、漏報率、平均檢測延遲和分類正確率4 個指標驗證WMDDM 的概念漂移檢測性能，實驗采用HT（Hoeffding Tree）和NB（Na?ve Bayes）分類器。

3.1 評價指標

概念漂移檢測通常采用真陽率（TP）、假陽率（FP）、假陰率（FN）和分類器的正確率作為評價指標，理想的檢測器具有更高的TP 和更低的FP、FN，本文采用可接受延遲長度 Δ 來統計上述指標[8]。Δ用來定義檢測到漂移的位置與漂移的真實位置間的最大距離，突變型漂移通常設置為250，漸進型漂移通常為概念長度的2%。檢測點的表示如圖5 所示。

圖5 檢測點示意圖Fig.5 Schematic diagram of detection points

TP 表示在 Δ 范圍內檢測到漂移的個數；FP 表示在 Δ 范圍外檢測到漂移的個數；FN 表示在 Δ 范圍內沒有檢測到漂移的個數。因此，誤報率（FPR，False Positive Rate）和漏報率（FNR，False Negative Rate）分別為：

平均檢測延遲（Average Delay of Detection，ADOD）評價檢測速度，若Di表示第i個漂移發生的位置，D′i表示漂移被檢測到位置，n'為檢測到的漂移個數，則：

3.2 數據集介紹

本文使用4 個人工數據集和1 個真實數據集測試檢測器的性能，如表1 所示，人工數據集有：

表1 數據集特征表Table 1 Data set feature table

SINE：包含突變漂移的數據集，具有x、y兩個屬性。函數y=sin(x) 對樣本分類，樣本被正弦曲線分為上下兩類，分別用正負號標記，每達到一次漂移點，兩類的正負標記交換。每20 000 個樣本出現一次漂移，共100 000 個樣本，產生4 次漂移。

MIXED：包含突變漂移的數據集，具有兩個布爾屬性和兩個連續屬性x、y。當屬性值滿足{true，true，y ＜(0.5+0.3*sine2πx)}時，樣本被標記為正，否則為負。數據含有10%的噪聲，且每20 000 個樣本出現一次漂移，共100 000 個樣本，產生4 次漂移。

LED：包含漸進型漂移的數據集，是由LED 生成器生成、用于預測七段二極管上顯示的數據集，具有24 個屬性和10 個類別。每25 000 個樣本出現一次漸進型漂移，共100 000 個樣本。

CIRCLE：包含了漸進漂移的數據集，由4 個圓形方程表示4 個不同概念，分別為＜(0.2,0.5)0.15＞、＜(0.4,0.5)0.2＞、＜(0.6,0.5)0.25＞和＜(0.8,0.5)0.3＞，圓內標記為正，圓外為負。數據含有10%的噪聲，且每25 000個樣本出現一次漂移，共100 000 個樣本，產生3 次漂移。

表1 示出的真實數據集為Electricity：該數據集是來自澳大利亞新南威爾士州電力市場，其能源價格受市場需求、供給、季節和天氣等因素影響的數據，用來測試檢測器在真實數據中的效果，表中共有45 312個樣本，每個樣本具有7 個屬性和2 個類。

3.3 自適應權重有效性

為驗證自適應加權的有效性，本節將WMDDM與不含自適應機制的WMDDM#1 以及FHDDM 算法進行對比實驗，實驗分為2 組。實驗1 使用SINE數據集，NB 分類器，滑動窗口為100，初始參數為θ=100、λ=0.5 ，δdrift=0.001 ，δwarning=0.005 ，Δ=250 。實驗1 結果見表2。由結果可得，在平均檢測延遲和正確率方面，WMDDM 優于FHDDM。在誤報率方面，WMDDM算法與FHDDM 算法都沒發生誤報，而WMDDM#1誤報率高。實驗2 使用CIRCLE 數據集，Δ=400，其他設置與實驗1 相同。實驗2 結果見表3，在平均檢測延遲和正確率方面，WMDDM 優于FHDDM。雖然WMDDM#1 平均檢測延遲最低，但誤報率高。綜合兩組實驗結果，在兩種不同漂移類型的數據集上，WMDDM 的性能優于FHDDM，且不存在誤報、漏報，而WMDDM#1 的誤報率高。因此，自適應調節衰減函數能降低檢測延遲，減少誤報。

表2 實驗1 結果Table 2 Results of experiment 1

表3 實驗2 結果Table 3 Results of experiment 2

3.4 算法性能對比

本節將WMDDM 與FHDDM、HDDM、DDM、RDDM 及ADWIN 等算法對比，分別用于HT 和NB分類器，4 個人工數據集上的實驗結果見表4～表7。由結果可知，WMDDM 與FHDDM 比較，二者在4 個數據集上沒有發生漏檢，WMDDM 在4 個數據集的誤報率、平均檢測延遲和分類正確率高于或等于FHDDM。WMDDM 與HDDM 比較，無論分類器采用HT 還是NB，WMDDM 在LED 數據集上取得最低的平均檢測延遲和最高分類正確率。HDDM 的誤報率和漏報率在MIXED、LED 和CIRCLE 數據集上高于或等于WMDDM。DDM、RDDM 和ADWIN 在4 個數據集上具有較高的誤報率、漏報率和平均檢測延遲。綜上所述，WMDDM 在不同數據集上都能取得較好的結果，具有最低的誤報率和漏檢率，且平均檢測延遲和正確率在6 種算法中排前2。

表4 在SINE 數據集上的實驗結果Table 4 Experimental results on the SINE dataset

表5 MIXED 數據集上的實驗結果Table 5 Experimental results on the MIXED dataset

表6 LED 數據集上的實驗結果Table 6 Experimental results on the LED dataset

表7 CIRCLE 數據集上的實驗結果Table 7 Experimental results on the CIRCLE dataset

圖6 是HT-WMDDM、HT-FHDDM 和HT 在真實數據集Electricity 的分類準確率對比圖，橫坐標表示樣本量，縱坐標表示分類正確率。由于真實數據集中概念漂移發生的位置和次數都是未知的，因此更能體現WMDDM 的泛化能力。由圖6 可看出，HTFHDDM 和HT-WMDDM 的分類正確率高于HT，說明加入檢測器能提升分類器的性能。HT-WMDDM 的分類正確率要高于HT-FHDDM。實驗表明，WMDDM算法對于真實數據環境有較好的適應能力，具有較強的抗漂移能力。

圖6 Electricity 數據集上的分類準確率對比圖Fig.6 Comparison chart of classification accuracy on the Electricity dataset

通過上述對比實驗，可以得出：第一，WMDDM算法的自適應加權機制具有自我調節能力，且具有較強的魯棒性；第二，WMDDM 算法具有更低的誤報率、漏報率和平均檢測延遲，能夠快速準確地檢測到突變型和漸進型概念漂移；第三，WMDDM 算法具有較強的數據流適應能力，無論是人工數據集或是真實數據集，都能夠快速適應數據變化，提高分類器的性能。

4 結束語

本文提出了一種基于McDiarmid 邊界的自適應加權概念漂移檢測方法WMDDM，它先對分類結果加權，求出漂移和警告的McDiarmid 邊界，再通過分析加權錯誤率的變化幅度以判斷當前數據流的狀態，根據反饋信號自動調節衰減函數以降低過時數據影響，提升檢測效率和分類準確率。通過人工和真實數據集上的實驗結果表明，WMDDM 在平均檢測延遲、誤報率和分類準確率上都具有一定優勢。

本文只考慮了突變型和漸進型概念漂移的問題，無法解決重現型概念漂移所帶來的額外消耗，且所采用的數據集是類別平衡的，而現實中存在許多類別不平衡的問題。因此，下一步將考慮多分類器和類別不平衡問題，以擴大概念漂移檢測器的適用范圍。