基于McDiarmid 界的概念漂移數(shù)據(jù)流分類算法

梁 斌，李光輝+

1.江南大學 人工智能與計算機學院，江蘇 無錫 214122

2.物聯(lián)網(wǎng)技術應用教育部工程研究中心，江蘇 無錫 214122

隨著物聯(lián)網(wǎng)技術的快速發(fā)展，社會各個領域產(chǎn)生了大量數(shù)據(jù)流，如傳感器數(shù)據(jù)流、電子商務數(shù)據(jù)流等。隨著時間的推移，數(shù)據(jù)流的目標概念或潛在分布會發(fā)生變化，這種現(xiàn)象被稱為概念漂移[1-2]。例如顧客網(wǎng)上購物的喜好分析會隨著時間、商品的變化而改變；工廠的用電量隨著季節(jié)交替出現(xiàn)周期性變化[3]。概念漂移會導致已有的分類模型性能顯著下降，因此數(shù)據(jù)流挖掘算法要求快速準確地檢測出漂移并及時調(diào)整原分類模型，快速適應當前新概念，提高數(shù)據(jù)流的分類準確率。目前處理概念漂移的算法大致可分為兩類[4-5]：主動檢測和被動適應。

主動檢測算法具有顯式的漂移檢測機制，通常與在線分類器組合使用。檢測到漂移時，當前分類器被丟棄同時，訓練一個新的分類器。如Gama 等提出的DDM（drift detection method）[6]是第一個主動檢測型算法，它假設數(shù)據(jù)流服從正態(tài)分布，通過監(jiān)測分類模型的錯誤率變化檢測概念漂移，但該方法只適合檢測突變型漂移，不適合漸變型漂移。Barros 等提出的RDDM（reactive drift detection method）[7]通過周期性地重置DDM 的漂移檢測統(tǒng)計量解決DDM 在長期穩(wěn)定數(shù)據(jù)流下的漂移檢測敏感性下降的問題。Pears等提出的SeqDrift（sequential hypothesis testing drift detector）[8]維護兩個相鄰的滑動窗口，通過比較兩個窗口中的錯誤率差異是否超過某閾值檢測漂移，該閾值由Bernstein界確定。Frias-Blanco等提出的HDDM（drift detection methods based on Hoeffding bounds）[9]利用Hoeffding 界檢驗當前模型的錯誤率是否發(fā)生顯著性變化檢測漂移。Barros 等提出的FPDD（concept drift detection based on Fisher's exact test）[10]使 用Fisher's exact test 檢驗兩個相鄰窗口中的錯誤率是否存在統(tǒng)計學上顯著性差異，若存在則表明出現(xiàn)概念漂移。針對重復概念問題，Gon?alves 等提出的RCD（recurring concept drifts）[11]在DDM 的基礎上，結合多元非參數(shù)統(tǒng)計方法識別當前的新概念是否為過去概念的重現(xiàn)。類似的，白洋等提出的DRDM（drift recurrence detection method）[12]在SeqDrift 的基礎上，使用有向圖保存歷史概念并使用Hotelling's T2檢驗判斷新舊概念是否來自同一分布。

被動適應型算法大都為集成算法，沒有專門的漂移檢測機制，通過調(diào)整集成模型的結構和成員分類器的權重被動適應概念漂移。如Brzezinski 等提出的AUE 算法（accuracy updated ensemble）[13]，每到達一個數(shù)據(jù)塊訓練一個新的分類器添加至集成中，每個分類器的權重由它們的分類準確率決定。進一步，Brzezinski 等提出OAUE 算法（online accuracy updated ensemble）[14]，該算法在AUE 的加權公式中引入了時間概念，同時結合在線分類器，更好地處理各種類型概念漂移。Elwell 等提出的LearnNSE[15]使用復雜的加權策略，每個基分類器的權重需要綜合考慮當前和過去所有數(shù)據(jù)塊上的錯誤率。

目前處理概念漂移的數(shù)據(jù)流分類算法主要存在兩個問題：一是漂移檢測延遲和誤報率較高，且難以同時處理不同類型漂移；二是缺乏識別重復概念的能力，當歷史概念重現(xiàn)時，當前分類模型無法利用過去所學知識快速適應新概念。為此，本文基于雙層模糊窗口和McDiarmid 界，結合半?yún)?shù)對數(shù)似然比方法，提出了一種新的可以適應多類型概念漂移的數(shù)據(jù)流分類算法（data stream classification algorithm based on double-layer fuzzy sliding window and McDiarmid bound，DFWM）。該算法維護一個固定大小的雙層滑動窗口，保存當前模型最新的分類結果，根據(jù)隸屬度函數(shù)對窗口中每個數(shù)據(jù)分配對應權重并計算加權錯誤率，然后利用McDiarmid 界檢驗當前窗口中的錯誤率是否發(fā)生顯著性變化來檢測概念漂移。同時DFWM 維護一個分類器池保存已出現(xiàn)過的概念及其對應的分類器，檢測到漂移時，使用半?yún)?shù)對數(shù)似然方法判斷當前概念是否為某個舊概念的重現(xiàn)，若是則直接復用舊概念對應的分類器，否則重新構建一個新的分類器。實驗結果表明，與同類算法相比，所提算法在漂移檢測延遲、誤報率、分類精度和運行時間上均有一定優(yōu)勢。

1 相關知識

1.1 概念漂移定義和分類

根據(jù)文獻[2,16-17]，概念漂移的定義如下：

定義1概念漂移設[0，t]表示一段時間,數(shù)據(jù)流可表示為St={d0,d1,…,dt}，其中di=(Xi,yi)表示一個實例，Xi為特征向量，yi為標簽，i=1,2,…,t。假設St服從某分布Ft(X,y)，P(y|X)表示y關于X的條件概率分布，若在t+1 時刻有Ft(X,y)≠Ft+1(X,y)且Pt(y|X)≠Pt+1(y|X)，表明原有的決策邊界發(fā)生變化，這種現(xiàn)象稱為概念漂移。

概念漂移的分類普遍是基于概念變化的速度[1-2,7]。當新舊概念過渡很快，舊的概念突然被另一個數(shù)據(jù)分布完全不同的新概念取代，這種漂移屬于突變型概念漂移（abrupt concept drift），如圖1（a）所示，其中實心圓代表一段數(shù)據(jù)，圓內(nèi)的數(shù)字代表到達的時間；反之，新舊概念過渡較慢時，舊概念被新概念逐漸替換，且二者在漂移前后或多或少有些相似，如圖1（b）所示，這種漂移則屬于漸變型概念漂移（gradual concept drift）。

Fig.1 Abrupt and gradual concept drift圖1 突變型和漸變型概念漂移

重復概念漂移指過去的某個概念再次出現(xiàn)，既可以有規(guī)律地出現(xiàn)，也可以無規(guī)律地出現(xiàn)[11]，通常與突變型漂移或漸變型漂移聯(lián)合出現(xiàn)，如圖2（a）中的數(shù)據(jù)段7 和8 即是重復概念，圖2（b）中的數(shù)據(jù)段9 也是重復概念。

Fig.2 Recurring concept drift圖2 重復概念漂移

1.2 模糊集理論和隸屬度函數(shù)

若論域U中的任一元素x，都有一個值A(x)∈[0,1]與之對應，則稱A為U上的模糊集，A(x)稱為元素x對A的隸屬度。當x在U中變化時，A(x)則是關于x的函數(shù)，稱為A的隸屬度函數(shù)。在模糊集理論中，使用取值在區(qū)間[0,1]的隸屬度函數(shù)A(x)表征x屬于A的程度。A(x)的值越接近于1，表示x屬于A的程度越高；A(x)越接近于0，則表示x屬于A的程度越低。常見的隸屬度函數(shù)有梯形型、對數(shù)型和柯西型等[18]，本文主要使用了對數(shù)型隸屬度函數(shù)A(x)，如式（1）所示。

其中，a、b代表區(qū)間[a,b]的左右端點，xi為區(qū)間中的第i個元素，e為自然常數(shù)，λ為自定義常數(shù)，用于控制隸屬度函數(shù)的形狀。

1.3 半?yún)?shù)對數(shù)似然算法

文獻[19]提出了半?yún)?shù)對數(shù)似然算法（semiparametric log-likelihood，SPLL），它從似然的角度檢驗兩組多元樣本W(wǎng)1和W2是否來自同一概率分布。相較于傳統(tǒng)的K-L 散度檢驗和Hotelling's T2檢驗，SPLL 的計算更為簡單，檢驗效果更好。它假設樣本W(wǎng)1服從分布p1，W2服從p2，則W2中數(shù)據(jù)的對數(shù)似然比LLR如式（2）所示：

式中，L(?)代表似然函數(shù)。由于W2服從p2，故L(W2|p2)=1。式（2）可改寫為式（3），這意味著LLR代表W2中的數(shù)據(jù)擬合分布p1的程度。

LLR的縮放上界LL，如式（4）所示，其中x為樣本W(wǎng)1中的一個實例，n代表x的維度，u為距x馬氏距離最近的簇中心，簇中心由K-means 聚類得到，Σ為W1中數(shù)據(jù)的協(xié)方差矩陣。

使用LL，可得SPLL的檢驗統(tǒng)計量δ如式（5）所示：

若δ服從自由度為n的卡方分布，表明W2中的數(shù)據(jù)服從分布p1，即W1和W2中的數(shù)據(jù)來自相同的分布。

2 基于McDiarmid 界的概念漂移數(shù)據(jù)流分類算法（DFWM）

DFWM 由兩部分組成：概念漂移檢測模塊和重復概念識別模塊。本章先介紹基于雙層模糊窗口和McDiarmid 界的概念漂移檢測機制，并給出了漂移檢測閾值的計算方法，然后介紹如何識別重復概念，最后描述DFWM 的算法流程。

2.1 概念漂移檢測機制

根據(jù)PAC（probably approximately correct）理論，隨著數(shù)據(jù)流規(guī)模的增加，分類模型的錯誤率應該逐漸下降或保持不變。否則，數(shù)據(jù)流中有很大可能出現(xiàn)概念漂移[6]?；诖?，概念漂移檢測問題可轉化為檢測分類模型的錯誤率是否發(fā)生顯著性變化。數(shù)據(jù)流的長度是無限的，無法獲取所有數(shù)據(jù)，因此通常使用固定長度的滑動窗口來獲取當前最新數(shù)據(jù)，根據(jù)滑動窗口內(nèi)的錯誤率的變化情況檢測概念漂移也是漂移檢測領域的常用方法[8,18,20-21]。然而，滑動窗口大小的選擇對概念漂移檢測的效果至關重要。大量實驗發(fā)現(xiàn)（如3.4 節(jié)的實驗結果），面對突變型漂移，使用短窗口具有更低的檢測延遲。而面對漸變型漂移，使用長窗口的檢測延遲更低，漏報率也顯著低于使用短窗口，因此僅使用一個單層滑動窗口難以同時適應突變型和漸變型漂移。為此，本文在靠近長窗口頭部的位置分割窗口，形成長短嵌套的雙層滑動窗口。每次檢測先使用短窗口，若未檢測到漂移，再使用長窗口檢測，可以兼顧不同類型的漂移。雙層窗口結構如圖3 所示，短窗口位于長窗口的頭部（圖3 中雙層窗口的右側為窗口頭部，左側為窗口尾部），負責檢測突變型漂移，而長窗口用于檢測漸變型漂移。

Fig.3 Structure of double-layer window圖3 雙層窗口結構

窗口中每個數(shù)據(jù)的到達的時間不同，當前的數(shù)據(jù)必然比過去的數(shù)據(jù)更能代表當前概念，因此在計算窗口內(nèi)錯誤率時，應該對靠近窗口頭部的數(shù)據(jù)分配更大的權重，以便更快速地檢測概念漂移。隸屬度函數(shù)可以很好地反映集合中每個元素對集合的隸屬程度，當出現(xiàn)概念漂移時，窗口頭部的數(shù)據(jù)對新概念的隸屬程度必然大于窗口尾部的數(shù)據(jù)，因此使用1.2 節(jié)中介紹的對數(shù)型隸屬度函數(shù)對窗口中的每個數(shù)據(jù)分配權重，權重計算方法如式（6）所示：

其中，w(i)表示雙層窗口中第i個數(shù)據(jù)（窗口尾端的數(shù)據(jù)為第1 個數(shù)據(jù)）的權重，表示長窗口的大小，e為自然常數(shù)，λ為預設值，決定隸屬度函數(shù)的形狀。式（6）為分段函數(shù)，靠近窗口頭部，即短窗口中的數(shù)據(jù)最能代表當前概念，因此權重均設為最大值1，之后數(shù)據(jù)的權重根據(jù)對數(shù)函數(shù)逐漸衰減，當1

Fig.4 Weight distribution of each data in window圖4 窗口中每個數(shù)據(jù)權重的分布

DFWM 的漂移檢測過程如下：每到達一個實例，先使用當前模型獲取分類結果并添加至雙層窗口中，分類錯誤記為1，正確記為0。然后根據(jù)式（8）計算短窗口內(nèi)數(shù)據(jù)的加權錯誤率，其中di是窗口中第i個元素，wi是其對應的權重，如果psw

若當前短窗口內(nèi)錯誤率psw與其歷史最小值psw′滿足式（9），表明當前短窗口內(nèi)錯誤率psw較過去出現(xiàn)了顯著性變化，即數(shù)據(jù)流中出現(xiàn)了概念漂移。式（9）中閾值的θ1由McDiarmid 界決定（2.2 節(jié)詳細介紹閾值的計算）。

若使用短窗口未檢測到概念漂移，繼續(xù)計算長窗口內(nèi)數(shù)據(jù)的加權錯誤率plw，計算方法與計算psw相同。如果plw

若式（9）、式（10）均不滿足，表明當前數(shù)據(jù)流處于穩(wěn)定狀態(tài)，無概念漂移。

2.2 漂移檢測閾值計算

DFWM 中的漂移檢測閾值的計算依賴于McDiarmid 界[22-23]，該統(tǒng)計邊界不需要對數(shù)據(jù)流的分布做任何假設，給出了樣本的函數(shù)f與其期望值E[f]之差的上界，如定理1 所示。

定理1McDiarmid 界設X1,X2,…,Xn為n個獨立有界隨機變量，其中Xi∈A∈[a,b]。設f:An→R 為X1,X2,…,Xn上的一個函數(shù)，且滿足?i，?x1,x2,…,xi,…,xn，xi′∈A,|f(x1,x2,…,xi,…,xn)-f(x1,x2,…,xi′,…,xn)|≤ci，即使用集合A中的任意值xi′替換函數(shù)f中的第i個元素xi最多改變函數(shù)f的值為ci。對于任意θ>0，則有：

式（11）表明f與其期望值E[f]之差大于θ的概率受到關于θ的指數(shù)邊界控制，在給定顯著性水平α下，令式（11）中不等號的右側等于α，θ值可由式（12）獲得：

在DFWM 中，雙層窗口中保存的分類結果di均為二值變量，即di∈{0,1}，分類錯誤記為1，正確記為0。因此式（8）中的加權錯誤率就是窗口中數(shù)據(jù)的加權平均值。以短窗口檢測漂移為例，介紹2.1 節(jié)中的閾值θ1的計算過程（長窗口中的閾值θ2同理）。首先將式（8）改寫為式（13）：

其中，vi如式（14）所示，wi為短窗口中第i個數(shù)據(jù)di對應的權重，|SW|為短窗口大小。

式中，psw是關于di的函數(shù)，記作psw(d1,d2,…,di,…,d|sw|)，且滿足?i，?d1,d2,…,di,…,d|sw|，di′∈{0,1},|psw(d1,d2,…,di,…,d|sw|)-psw(d1,d2,…,di′,…,d|sw|)|≤ci，其中ci=(1-0)vi，即ci=vi。當數(shù)據(jù)流處在穩(wěn)定狀態(tài)，無概念漂移時，短窗口內(nèi)錯誤率psw會逐漸下降最終穩(wěn)定在其最小值psw′附近，因此psw′可以代表psw的期望值。將psw和psw′代入式（11）可得式（15）：

在給定的顯著性水平α下，根據(jù)式（12）可得短窗口漂移檢測閾值θ1，如式（16）所示：

2.3 重復概念的識別

DFWM 檢測到概念漂移時，表明數(shù)據(jù)流中出現(xiàn)了新概念，當前分類器不再適用。通常的做法是丟棄當前分類器，重新訓練一個新的分類器去適應新概念。然而，如果當前的新概念是某個歷史概念的重現(xiàn)，即數(shù)據(jù)流中出現(xiàn)了重復概念，重新訓練一個分類器的代價比復用舊分類器大得多。復用舊分類器可以充分利用過去已學習到的知識，更快地適應新概念。基于此，DFWM 使用分類器池和1.3 節(jié)中介紹的SPLL 處理重復概念。具體來說，使用C={C1,C2,…,Ci,…,Cm}表示由m個分類器組成的分類器池，其中每個分類器Ci附帶它的使用頻率k和一個數(shù)據(jù)塊Bi，Bi用于保存分類器Ci的錯誤率達到最小值時對應的若干數(shù)據(jù)，因為此時數(shù)據(jù)流最穩(wěn)定，這些數(shù)據(jù)最能代表當前概念，Bi的大小和長窗口|LW|大小相同。檢測到漂移時，若分類器池非空，根據(jù)池中每個分類器頻率的高低，使用SPLL 依次對每個分類器對應的數(shù)據(jù)塊和當前窗口中的數(shù)據(jù)檢驗，若二者來自相同分布，表明出現(xiàn)了重復概念，直接復用該分類器，并將它的使用頻率加1。否則，表明數(shù)據(jù)流中出現(xiàn)了全新的概念，將當前的分類器和它對應的數(shù)據(jù)塊添加至分類器池中，使用頻率置為1，然后使用當前數(shù)據(jù)重新訓練一個新分類器。出于占用內(nèi)存的考慮，不可能把所有出現(xiàn)過的概念及其對應分類器都保存到分類器池中。頻率最低的分類器表明它對應的概念最少出現(xiàn)，因此分類器池容量達到上限時移除該分類器。DFWM 是基于單分類器的分類算法，只使用當前分類器進行預測，分類器池只保存若干訓練過的舊分類器。如果被刪除的最低頻率分類器對應的概念再次出現(xiàn)，DFWM 會立即使用當前數(shù)據(jù)重新訓練一個分類器，這只會增加一定的時空開銷，不會影響信息的完整性。識別重復概念進而復用過去已訓練好的舊分類器，可以充分利用過去所學知識，快速適應當前概念，有效提高DFWM 的分類速度和準確率。同時避免了重復概念導致重復訓練的問題，降低時間和空間的開銷。

DFWM 的執(zhí)行流程圖如圖5 所示。

Fig.5 Flow diagram of DFWM圖5 DFWM 的流程圖

3 實驗與結果分析

3.1 實驗設置

為驗證DFWM 的性能，本文在6 個人工數(shù)據(jù)集和2 個真實數(shù)據(jù)集上進行了兩方面的實驗：（1）與DDM[6]、SeqDrift[8]、HDDM[9]、RDDM[7]和FPDD[10]五種算法進行對比實驗，從漂移檢測延遲、誤報率和漏報率三方面驗證DFWM的漂移檢測性能；（2）與RCD[11]、LearnNSE[15]和OAUE[14]三種算法進行對比實驗，從分類準確率和運行時間兩方面驗證DFWM 的分類性能。本文的實驗環(huán)境為一臺處理器為Intel Core i7-7700HQ，內(nèi)存為16 GB 的筆記本電腦，運行Windows 10 系統(tǒng)和python3.7。在該環(huán)境下，分別實現(xiàn)了本文算法和各種對比算法。DFWM 的參數(shù)均根據(jù)大量實驗結果設置：長窗口大小|LW|設為100，隸屬度函數(shù)參數(shù)λ設為0.75，顯著性水平α為10-7，分類器池的最大容量m為10，池中分類器對應的數(shù)據(jù)塊B的大小為100。對比算法保持與原論文完全相同的參數(shù)設置。所有實驗采用test-then-train 策略，即每個實例先用作測試數(shù)據(jù)，然后作為訓練數(shù)據(jù)，這種策略不用劃分數(shù)據(jù)集，可以充分利用每個數(shù)據(jù)的信息。

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

人工數(shù)據(jù)集在概念漂移檢測領域十分重要，因為可以人為定義概念漂移的數(shù)量、位置和持續(xù)時間，以模擬不同的場景。本文用到的6個人工數(shù)據(jù)集均為概念漂移領域的Benchmarks，可通過python 的skmultiflow[24]包生成，詳情如下所示：

SINE：該數(shù)據(jù)集包含突變重復型漂移，它有兩個屬性x和y。分類函數(shù)是y=sin(x)，在第一次漂移之前，函數(shù)曲線下方的實例被標記正，曲線上方的被標記為負，共有兩個類別。在漂移點，通過突然反轉分類規(guī)則來產(chǎn)生漂移。數(shù)據(jù)集共包含100 000 個實例，每隔20 000 個實例產(chǎn)生一次漂移，共有5 個概念，其中第1、3、5 個概念互為重復概念，第2、4 個概念互為重復概念，含10%噪聲。

STAGGER：該數(shù)據(jù)集包含突變型漂移，它有3 個離散屬性和2 個類別，每隔33 333 個實例通過突然反轉分類規(guī)則產(chǎn)生漂移，共100 000個實例，含10%噪聲。

SEA：該數(shù)據(jù)集包含漸變重復型漂移，有3 個連續(xù)屬性，其中第3 個屬性與類別無關，如果x1+x2<θ，實例分類為正，否則為負，x1、x2表示前兩個屬性。每隔20 000 個實例，通過逐漸改變閾值θ來產(chǎn)生漸變型漂移，共包含100 000 個實例，含10%噪聲。閾值θ∈{5,15,5,15,5}，其中第1、3、5 個概念互為重復概念，第2、4 個概念互為重復概念。

LED：該數(shù)據(jù)集包含漸變型漂移，有24 個屬性，共10 個類別。通過逐漸改變相關屬性值來產(chǎn)生漸變型概念漂移，共包含100 000 個實例，每隔25 000 個實例產(chǎn)生一次漸變型漂移，含10%噪聲。

MIXED：該數(shù)據(jù)集包含突變型漂移，它有兩個連續(xù)屬性x和y以及兩個布爾屬性v和w。如果滿足條件v,w,y<0.5+0.3×sin(2πx)，實例被分類為正，否則為負，共有兩個類別。在漂移點，通過突然反轉分類規(guī)則產(chǎn)生漂移。數(shù)據(jù)集共包含100 000 個實例，每隔20 000 個實例產(chǎn)生一次漂移，共有5 個概念，其中第1、3、5 個概念互為重復概念，第2、4 個概念互為重復概念，含10%噪聲。

CIRCLE：該數(shù)據(jù)集包含漸變型漂移，它有兩個連續(xù)屬性x和y。4 個圓方程表示4 個不同概念，圓內(nèi)的實例被分類為正，圓外為負，共2 個類別。在漂移點通過逐漸改變圓的方程來產(chǎn)生漂移。數(shù)據(jù)集共包含100 000 個實例，每隔25 000 個實例產(chǎn)生一次漸變型漂移，含10%噪聲。

人工數(shù)據(jù)集中的數(shù)據(jù)均為隨機產(chǎn)生，因此使用skmultiflow 包在每類人工數(shù)據(jù)集上生成10 個不同的子集，做10 次實驗，取平均值作為最終結果。

2個真實數(shù)據(jù)集均為概念漂移領域的Benchmarks，詳情如下所示：

Spam：該數(shù)據(jù)集包括9 324 個實例和500 個屬性，每個實例表示一個郵件的信息，有兩個類別垃圾郵件和合法郵件，其中垃圾郵件的特征會隨著時間變化。可在http://mlkd.csd.auth.gr/concept_drfit.html下載。

Electricity：該數(shù)據(jù)集收集了1996 年 至1998 年澳大利亞新南威爾士州電力市場的45 312 個實例，包含8 個屬性和2 個類別。該數(shù)據(jù)集可在http://sourceforge.net/projects/moa-datastream/files/Datasets/Classification/下載。

所有數(shù)據(jù)集的信息總結如表1 所示。

3.3 算法性能評價指標

根據(jù)文獻[2]，概念漂移數(shù)據(jù)流分類算法通用的評價指標有平均檢測延遲（average delay of detection，ADOD）、誤報率（false positive rate，F(xiàn)PR）、漏報率（false negative rate，F(xiàn)NR）、運行時間和分類準確率。特別地，平均檢測延遲、誤報率、漏報率定義如下：

（1）平均檢測延遲（ADOD）：假設第i個漂移發(fā)生的時刻為Ti，漂移被檢測到的時刻為Ti′，則檢測延遲為(Ti′-Ti)。平均檢測延遲，其中dist=為所有檢測延遲之和，n為檢測到的漂移個數(shù)。

根據(jù)文獻[7]，通過定義可容忍的最大檢測延遲Δd來定義誤報率和漏報率，Δd通常為概念長度的2%。例如在SINE數(shù)據(jù)集中，概念長度為20 000，則Δd為400。設漂移發(fā)生的時刻為T，則在區(qū)間[T,T+Δd]內(nèi)檢測到的漂移個數(shù)視為正確檢測個數(shù)（TP）?；诖耍`報率和漏報率的定義如下所示：

（2）誤報率（FPR）：在區(qū)間[T,T+Δd]外檢測到漂移的個數(shù)視為誤報個數(shù)（FP）。

（3）漏報率（FNR）：在區(qū)間[T,T+Δd]內(nèi)漏檢的漂移個數(shù)視為漏報個數(shù)（FN）。

Table 1 Datasets of experiments表1 實驗數(shù)據(jù)集

3.4 雙層窗口的有效性

本節(jié)通過與DFWM_S、DFWM_L 的對比實驗來驗證DFWM 中雙層窗口的有效性，其中DFWM_S 只使用大小為25 的短窗口，DFWM_L 只使用大小為100 的長窗口，其他設置相同。每個表中的檢測指標的最優(yōu)值加粗表示，排名1 表示在某個數(shù)據(jù)集上的效果最好。由表2 知，DFWM_S 在STAGGER、MIXED和SINE 3 個突變型漂移數(shù)據(jù)集上平均檢測延遲較低，與DFWM 相似；而在其他3 個漸變型漂移數(shù)據(jù)集上平均檢測延遲顯著高于DFWM。DFWM_L 與它正相反。誤報率方面，由表3 知，DFWM_S 沒有出現(xiàn)誤報，而DFWM、DFWM_L 在SEA 上出現(xiàn)了少量誤報。漏報率方面，由表4 知，DFWM_S 在LED、SEA和CIRCLE 3 個漸變型漂移數(shù)據(jù)集上的漏報率遠高于其他兩種算法。綜合來看，使用短窗口的DFWM_S適合檢測突變型漂移，而使用長窗口的DFWM_L 更適合檢測漸變型漂移，DFWM 使用雙層窗口結合了二者的優(yōu)點，在突變型和漸變型漂移數(shù)據(jù)集上均獲得了較好的檢測效果。

3.5 概念漂移檢測

表5～表7給出了6種算法（DFWM、DDM、SeqDrift、HDDM、RDDM 和FPDD）在6 個人工數(shù)據(jù)集上的平均檢測延遲、誤報率和漏報率的實驗結果。由表5知，在平均檢測延遲方面，DFWM 在MIXED、SEA、LED 和CIRCLE 這4 個數(shù)據(jù)集上最低，排名第1，較第2 名分別降低了0.12、66.9、54.3、123.5。在SINE 和STAGGER 數(shù)據(jù)集中位列第2，檢測延遲略高于FPDD，在所有數(shù)據(jù)集上平均排名第1。誤報率方面，如表6 所示，DFWM 僅在SEA 上出現(xiàn)了誤報，誤報率較第1 名高出了1.04%，在所有數(shù)據(jù)集上平均排名第1。由表7 知，DFWM 僅在SEA 數(shù)據(jù)集上存在漏報，漏報率較第1 名高出了3.33%，在所有數(shù)據(jù)集上平均排名第1。

具體來看，DDM 在各數(shù)據(jù)集上均有較高的檢測延遲和漏報率，在包含漸變型漂移的數(shù)據(jù)集上更為嚴重。RDDM 則在DDM 基礎上，通過設定閾值周期性地重置DDM 的漂移統(tǒng)計量來提高檢測漂移的敏感性，一定程度上降低了檢測延遲和漏報率，但也增加了誤報的風險。在6 個人工數(shù)據(jù)集上平均檢測延遲和漏報率都低于DDM，但誤報率都高于DDM。HDDM 的效果與RDDM 相似，在所有數(shù)據(jù)集上較DDM 有更低的檢測延遲和漏報率，但這以增加誤報為代價。FPDD 在STAGGER、SINE 和MIXED3 個突變型漂移的數(shù)據(jù)集上檢測效果很好，具有極低的檢測延遲、誤報率和漏報率，而在其他3 個漸變型漂移的數(shù)據(jù)集上效果很差。SeqDrift 在漸變型漂移的數(shù)據(jù)集上的檢測延遲要好于突變型漂移數(shù)據(jù)集，而在所有數(shù)據(jù)集上均存在較高的誤報率，但漏報率極低，僅在LED 數(shù)據(jù)集上出現(xiàn)了漏報。與其他算法相比，DFWM 處理突變型漂移的能力僅次于FPDD，由表5知，在STAGGER、SINE 和MIXED 3 個突變型數(shù)據(jù)集上，F(xiàn)PDD 的平均檢測延遲最低，DFWM 次之。而DFWM 處理漸變型漂移能力顯著強于其他算法，在LED、CIRCLE 和SEA 3 個漸變型數(shù)據(jù)集上平均檢測延遲、誤報率和漏報率均最低。這主要得益于DFWM 的雙層滑動窗口和基于隸屬度的加權機制，使其可以快速處理多種類型的概念漂移，具有較強的魯棒性。除DFWM 外，F(xiàn)PDD 和SeqDrift 也是基于滑動窗口的算法，但它們均使用一個固定長度的窗口，缺少加權機制，只適用于某一種特定類型概念漂移。由表5～表7 知，F(xiàn)PDD 只適合處理突變型漂移，而SeqDrift 只適合處理漸變型漂移，具有較大的局限性。而DDM、RDDM 和HDDM 三種算法是基于統(tǒng)計過程控制的算法，沒有使用滑動窗口，在所有數(shù)據(jù)集上的檢測延遲和誤報率均高于DFWM，因此處理突變型漂移和漸變型漂移的能力均弱于DFWM。

Table 2 Comparison of average delay of detection表2 平均檢測延遲對比

Table 3 Comparison of false positive rate表3 誤報率對比

Table 4 Comparison of false negative rate表4 漏報率對比

Table 5 Comparison of algorithm average delay of detection on synthesized datasets表5 人工數(shù)據(jù)集上的算法平均檢測延遲對比

Table 6 Comparison of algorithm false positive rate on synthesized datasets表6 人工數(shù)據(jù)集上的算法誤報率對比

Table 7 Comparison of algorithm false negative rate on synthesized datasets表7 人工數(shù)據(jù)集上的算法漏報率對比

3.6 分類準確率和運行時間

檢測概念漂移的目的是為了及時發(fā)現(xiàn)數(shù)據(jù)流中概念的變化，調(diào)整當前分類模型，提高分類準確率。為進一步驗證DFWM 的概念漂移檢測機制和重復概念識別機制能否有效提高分類準確率，本文選取了RCD、OAUE 和LearnNSE 三種算法進行對比。在SINE、SEA、Spam 和Electricity 4 個數(shù)據(jù)集上分別比較它們的分類準確率和運行時間。SINE 和SEA 包含重復概念，Spam 和Electricity 為含有概念漂移真實數(shù)據(jù)集，但漂移的類型、發(fā)生的時間未知。DFWM 和RCD 是基于單分類器的算法，使用skmultiflow 包中的HoeffdingTree做分類器。OAUE 和LearnNSE 為集成算法，根據(jù)文獻[14-15]，OAUE 使用Hoeffding Tree做基分類器，而LearnNSE 使用CART 決策樹做基分類器。

表8 給出了各算法在4 個數(shù)據(jù)集上的分類準確率。4 個算法中，只有DFWM 和RCD 具有重復概念識別機制?？梢钥闯?，在SINE 和SEA 兩個具有重復概念的數(shù)據(jù)集上，盡管DFWM 是單分類器算法，但由于可以識別重復概念，直接復用過去已訓練好的舊分類器，避免重建分類器，更快地適應新概念，獲得了最高準確率。在Spam 上，DFWM 的準確率最高，略高于RCD，而在Electricity 上，OAUE 獲得最高的準確率，DFWM 次之。

Table 8 Comparison of classification accuracy表8 分類準確率對比

每個算法的運行時間如表9 所示。在4 個數(shù)據(jù)集上，RCD 的運行時間最短，本文算法DFWM 略高于RCD。而OAUE 和LearnNSE 是集成算法，運行時間遠高于基于單分類器的RCD 和DFWM。特別地，在SINE 和SEA 兩個數(shù)據(jù)集上，LearnNSE 的運行時間顯著高于OAUE，而在Spam 和Electricity 上則相反。這主要因為LearnNSE 沒有剪枝策略，會保留在所有數(shù)據(jù)塊上訓練的分類器。而SINE 和SEA 數(shù)據(jù)集規(guī)模要遠大于Spam 和Electricity，因此LearnNSE 在前者上會訓練更多的分類器，運行時間更長。

Table 9 Comparison of running time表9 運行時間對比

由圖6 可知，SINE 數(shù)據(jù)集上共發(fā)生4 次漂移，分別位于數(shù)據(jù)流的20%、40%、60%和80%處。在初始階段，數(shù)據(jù)流中無概念漂移，所有算法的準確率的變化趨勢相似，先上升然后趨于穩(wěn)定。遭遇概念突變時，所有算法的準確率均出現(xiàn)了不同程度的下降，DFWM 由于可以快速檢測到概念漂移，并識別重復概念，及時調(diào)整當前分類器，抗漂移能力較強，準確率曲線僅出現(xiàn)了小幅下降，基本保持穩(wěn)定。而OAUE和RCD 的準確率在漂移處發(fā)生了顯著下降，然后緩慢上升。LearnNSE 的準確率也基本保持穩(wěn)定，但整體準確率始終較低。此外，SINE 中含有10%的噪聲，表明DFWM 具有一定的抗噪能力。

Fig.6 Comparison of classification accuracy on SINE dataset圖6 SINE 數(shù)據(jù)集上的分類準確率比較

圖7 展示了所有算法在Spam 上的準確率變化情況，Spam 為真實數(shù)據(jù)集，無法確切地知道概念的變化情況，更能反映算法的泛化能力。觀察圖7 可知，大約在數(shù)據(jù)流的10%處出現(xiàn)了概念漂移。所有算法的準確率開始不同程度地下降，其中OAUE 下降最嚴重。RCD 和DFWM 的變化趨勢相似，準確率小幅下降后緩慢上升，但DFWM 更為穩(wěn)定，始終保持最高的準確率，這表明本文算法的抗漂移能力較強，可以很好地適應真實數(shù)據(jù)環(huán)境。

Fig.7 Comparison of classification accuracy on Spam dataset圖7 Spam 數(shù)據(jù)集上的分類準確率比較

通過上述實驗，可以得出以下結論：（1）相比同類算法，DFWM 檢測漂移具有較低的平均檢測延遲、誤報率和漏報率，能夠快速檢測到不同類型的概念漂移。（2）DFWM 的概念漂移檢測機制和重復概念識別機制有效提高了分類準確率，尤其在含有重復概念的數(shù)據(jù)流中，并且在復雜的真實數(shù)據(jù)環(huán)境中也有較強的適應性。（3）如果已知數(shù)據(jù)流僅包含突變型或漸變型漂移，建議使用單層窗口版本的DFWM_S 或DFWM_L，可以降低一定的內(nèi)存占用和運行時間。如果數(shù)據(jù)流包含突變型、漸變型或重復型等多種類型的概念漂移，或者不清楚數(shù)據(jù)流中的漂移類型，建議使用雙層窗口版本的DFWM，它具有更強的性能和魯棒性。

4 結束語

本文提出了一種新的可以適于多類型概念漂移的數(shù)據(jù)流分類算法(DFWM)。針對當前主動檢測型數(shù)據(jù)流分類算法存在較高的檢測延遲和誤報率，無法有效處理不同類型漂移等問題，DFWM 在傳統(tǒng)滑動窗口的基礎上引入了雙層窗口，結合隸屬度函數(shù)和McDiarmid 界，通過分析當前窗口內(nèi)數(shù)據(jù)錯誤率是否發(fā)生顯著性變化，可以快速檢測到數(shù)據(jù)流中不同類型的概念漂移。而針對當前數(shù)據(jù)流分類算法無法有效利用歷史信息處理重復概念的問題，DFWM 通過SPLL 判斷當前概念是否為歷史概念的重現(xiàn)，只有檢測到新概念時才重新構建新分類器，否則直接復用舊分類器，有效減少了重復構建分類器的開銷，更快地適應當前概念。人工和真實數(shù)據(jù)集上的實驗結果表明，與以往同類算法相比，DFWM 在平均檢測延遲、誤報率、分類準確率和運行時間上都具有一定優(yōu)勢。

本文只考慮了類別平衡數(shù)據(jù)流中的概念漂移問題，而數(shù)據(jù)流中的類別不平衡問題會進一步增加處理概念漂移的難度，下一步將考慮如何處理不平衡數(shù)據(jù)流中的概念漂移問題，以便模擬更多的實際情況。