基于McDiarmid 邊界的自適應(yīng)加權(quán)概念漂移檢測方法

胡 陽，孫自強

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

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

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

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

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

1.1 概念漂移

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

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

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

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

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

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

實際數(shù)據(jù)流中，概念漂移一般是混合出現(xiàn)，即多種類型的概念漂移可能出現(xiàn)在同一流中，理想的概念漂移檢測器應(yīng)能適應(yīng)多種類型的概念漂移。

1.2 FHDDM 算法

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

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

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

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

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

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

2.1 加權(quán)機制

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

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

圖3 加權(quán)窗口描述圖Fig.3 Weighted window description diagram

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

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

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

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

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

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

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

引理1 可變換成：

對于 ?t＞0 ，

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

2.2 WMDDM 算法

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

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

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

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

3 實驗與結(jié)果分析

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

3.1 評價指標(biāo)

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

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

TP 表示在 Δ 范圍內(nèi)檢測到漂移的個數(shù)；FP 表示在 Δ 范圍外檢測到漂移的個數(shù)；FN 表示在 Δ 范圍內(nèi)沒有檢測到漂移的個數(shù)。因此，誤報率（FPR，F(xiàn)alse Positive Rate）和漏報率（FNR，F(xiàn)alse Negative Rate）分別為：

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

3.2 數(shù)據(jù)集介紹

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

表1 數(shù)據(jù)集特征表Table 1 Data set feature table

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

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

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

CIRCLE：包含了漸進(jìn)漂移的數(shù)據(jù)集，由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＞，圓內(nèi)標(biāo)記為正，圓外為負(fù)。數(shù)據(jù)含有10%的噪聲，且每25 000個樣本出現(xiàn)一次漂移，共100 000 個樣本，產(chǎn)生3 次漂移。

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

3.3 自適應(yīng)權(quán)重有效性

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

表2 實驗1 結(jié)果Table 2 Results of experiment 1

表3 實驗2 結(jié)果Table 3 Results of experiment 2

3.4 算法性能對比

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

表4 在SINE 數(shù)據(jù)集上的實驗結(jié)果Table 4 Experimental results on the SINE dataset

表5 MIXED 數(shù)據(jù)集上的實驗結(jié)果Table 5 Experimental results on the MIXED dataset

表6 LED 數(shù)據(jù)集上的實驗結(jié)果Table 6 Experimental results on the LED dataset

表7 CIRCLE 數(shù)據(jù)集上的實驗結(jié)果Table 7 Experimental results on the CIRCLE dataset

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

圖6 Electricity 數(shù)據(jù)集上的分類準(zhǔn)確率對比圖Fig.6 Comparison chart of classification accuracy on the Electricity dataset

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

4 結(jié)束語

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

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